[8] | 1 | /* BDD system cache routines */ |
---|
| 2 | |
---|
| 3 | |
---|
| 4 | #include "bddint.h" |
---|
| 5 | |
---|
| 6 | |
---|
| 7 | #define HASH1(d1) ((INT_PTR)d1) |
---|
| 8 | #define HASH2(d1, d2) ((INT_PTR)(d1)+(((INT_PTR)(d2)) << 1)) |
---|
| 9 | #define HASH3(d1, d2, d3) ((INT_PTR)(d1)+(((INT_PTR)(d2)) << 1)+(((INT_PTR)(d3)) << 2)) |
---|
| 10 | |
---|
| 11 | |
---|
| 12 | static |
---|
| 13 | void |
---|
| 14 | bdd_purge_entry(cmu_bdd_manager bddm, cache_entry *bin) |
---|
| 15 | { |
---|
| 16 | void (*purge_fn)(cmu_bdd_manager, cache_entry); |
---|
| 17 | cache_entry p; |
---|
| 18 | |
---|
| 19 | p= *bin; |
---|
| 20 | purge_fn=bddm->op_cache.purge_fn[TAG(p)]; |
---|
| 21 | p=CACHE_POINTER(p); |
---|
| 22 | if (purge_fn) |
---|
| 23 | (*purge_fn)(bddm, p); |
---|
| 24 | bddm->op_cache.entries--; |
---|
| 25 | BDD_FREE_REC(bddm, (pointer)p, sizeof(struct cache_entry_)); |
---|
| 26 | *bin=0; |
---|
| 27 | } |
---|
| 28 | |
---|
| 29 | |
---|
| 30 | static |
---|
| 31 | void |
---|
| 32 | bdd_purge_lru(cmu_bdd_manager bddm, cache_entry *bin) |
---|
| 33 | { |
---|
| 34 | if (bin[1]) |
---|
| 35 | bdd_purge_entry(bddm, bin+1); |
---|
| 36 | bin[1]=bin[0]; |
---|
| 37 | } |
---|
| 38 | |
---|
| 39 | |
---|
| 40 | static |
---|
| 41 | cache_entry |
---|
| 42 | bdd_get_entry(cmu_bdd_manager bddm, int tag, cache_entry *bin) |
---|
| 43 | { |
---|
| 44 | void (*purge_fn)(cmu_bdd_manager, cache_entry); |
---|
| 45 | cache_entry p; |
---|
| 46 | |
---|
| 47 | if (bin[0] && bin[1]) |
---|
| 48 | { |
---|
| 49 | p=bin[1]; |
---|
| 50 | purge_fn=bddm->op_cache.purge_fn[TAG(p)]; |
---|
| 51 | p=CACHE_POINTER(p); |
---|
| 52 | if (purge_fn) |
---|
| 53 | (*purge_fn)(bddm, p); |
---|
| 54 | bddm->op_cache.collisions++; |
---|
| 55 | if (bddm->op_cache.cache_level == 0) |
---|
| 56 | bin[1]=bin[0]; |
---|
| 57 | else |
---|
| 58 | ++bin; |
---|
| 59 | } |
---|
| 60 | else |
---|
| 61 | { |
---|
| 62 | p=(cache_entry)BDD_NEW_REC(bddm, sizeof(struct cache_entry_)); |
---|
| 63 | bddm->op_cache.entries++; |
---|
| 64 | if (bin[0]) |
---|
| 65 | ++bin; |
---|
| 66 | } |
---|
| 67 | *bin=(cache_entry)SET_TAG(p, tag); |
---|
| 68 | return (p); |
---|
| 69 | } |
---|
| 70 | |
---|
| 71 | |
---|
| 72 | static |
---|
| 73 | long |
---|
| 74 | bdd_rehash1(cmu_bdd_manager bddm, cache_entry p) |
---|
| 75 | { |
---|
| 76 | return (HASH1(p->slot[0])); |
---|
| 77 | } |
---|
| 78 | |
---|
| 79 | |
---|
| 80 | static |
---|
| 81 | long |
---|
| 82 | bdd_rehash2(cmu_bdd_manager bddm, cache_entry p) |
---|
| 83 | { |
---|
| 84 | return (HASH2(p->slot[0], p->slot[1])); |
---|
| 85 | } |
---|
| 86 | |
---|
| 87 | |
---|
| 88 | static |
---|
| 89 | long |
---|
| 90 | bdd_rehash3(cmu_bdd_manager bddm, cache_entry p) |
---|
| 91 | { |
---|
| 92 | return (HASH3(p->slot[0], p->slot[1], p->slot[2])); |
---|
| 93 | } |
---|
| 94 | |
---|
| 95 | |
---|
| 96 | void |
---|
| 97 | bdd_rehash_cache(cmu_bdd_manager bddm, int grow) |
---|
| 98 | { |
---|
| 99 | long i; |
---|
| 100 | long hash; |
---|
| 101 | int j; |
---|
| 102 | long oldsize; |
---|
| 103 | cache_bin *newtable; |
---|
| 104 | cache_entry *bin; |
---|
| 105 | cache_entry *newbin; |
---|
| 106 | cache_entry p; |
---|
| 107 | cache_entry q; |
---|
| 108 | |
---|
| 109 | oldsize=bddm->op_cache.size; |
---|
| 110 | if (grow) |
---|
| 111 | bddm->op_cache.size_index++; |
---|
| 112 | else |
---|
| 113 | bddm->op_cache.size_index--; |
---|
| 114 | bddm->op_cache.size=TABLE_SIZE(bddm->op_cache.size_index); |
---|
| 115 | newtable=(cache_bin *)mem_get_block((SIZE_T)(bddm->op_cache.size*sizeof(struct cache_bin_))); |
---|
| 116 | for (i=0; i < bddm->op_cache.size; ++i) |
---|
| 117 | for (j=0; j < 2; ++j) |
---|
| 118 | newtable[i].entry[j]=0; |
---|
| 119 | /* Rehash LRU first. */ |
---|
| 120 | for (j=1; j >= 0; --j) |
---|
| 121 | for (i=0; i < oldsize; ++i) |
---|
| 122 | { |
---|
| 123 | bin=bddm->op_cache.table[i].entry; |
---|
| 124 | if ((p=bin[j])) |
---|
| 125 | { |
---|
| 126 | q=CACHE_POINTER(p); |
---|
| 127 | hash=(*bddm->op_cache.rehash_fn[TAG(p)])(bddm, q); |
---|
| 128 | BDD_REDUCE(hash, bddm->op_cache.size); |
---|
| 129 | newbin=newtable[hash].entry; |
---|
| 130 | bdd_purge_lru(bddm, newbin); |
---|
| 131 | newbin[0]=p; |
---|
| 132 | } |
---|
| 133 | } |
---|
| 134 | mem_free_block((pointer)(bddm->op_cache.table)); |
---|
| 135 | bddm->op_cache.table=newtable; |
---|
| 136 | } |
---|
| 137 | |
---|
| 138 | |
---|
| 139 | /* The routines bdd_insert_in_cachex insert things in the cache. */ |
---|
| 140 | /* The routines bdd_lookup_in_cachex look up things in the cache. */ |
---|
| 141 | |
---|
| 142 | void |
---|
| 143 | bdd_insert_in_cache31(cmu_bdd_manager bddm, int tag, INT_PTR d1, INT_PTR d2, INT_PTR d3, INT_PTR result) |
---|
| 144 | { |
---|
| 145 | long hash; |
---|
| 146 | cache_entry p; |
---|
| 147 | |
---|
| 148 | hash=HASH3(d1, d2, d3); |
---|
| 149 | BDD_REDUCE(hash, bddm->op_cache.size); |
---|
| 150 | if (hash < 0) |
---|
| 151 | hash= -hash; |
---|
| 152 | p=bdd_get_entry(bddm, tag, bddm->op_cache.table[hash].entry); |
---|
| 153 | p->slot[0]=d1; |
---|
| 154 | p->slot[1]=d2; |
---|
| 155 | p->slot[2]=d3; |
---|
| 156 | p->slot[3]=result; |
---|
| 157 | bddm->op_cache.inserts++; |
---|
| 158 | } |
---|
| 159 | |
---|
| 160 | |
---|
| 161 | #define RETURN_BDD_FN ((void (*)(cmu_bdd_manager, cache_entry))-1) |
---|
| 162 | |
---|
| 163 | |
---|
| 164 | int |
---|
| 165 | bdd_lookup_in_cache31(cmu_bdd_manager bddm, int tag, INT_PTR d1, INT_PTR d2, INT_PTR d3, INT_PTR *result) |
---|
| 166 | { |
---|
| 167 | long hash; |
---|
| 168 | cache_entry *bin; |
---|
| 169 | cache_entry p; |
---|
| 170 | cache_entry q; |
---|
| 171 | bdd f; |
---|
| 172 | void (*return_fn)(cmu_bdd_manager, cache_entry); |
---|
| 173 | |
---|
| 174 | bddm->op_cache.lookups++; |
---|
| 175 | hash=HASH3(d1, d2, d3); |
---|
| 176 | BDD_REDUCE(hash, bddm->op_cache.size); |
---|
| 177 | bin=bddm->op_cache.table[hash].entry; |
---|
| 178 | if ((p=bin[0])) |
---|
| 179 | { |
---|
| 180 | q=CACHE_POINTER(p); |
---|
| 181 | if (q->slot[0] != d1 || q->slot[1] != d2 || q->slot[2] != d3 || TAG(p) != tag) |
---|
| 182 | { |
---|
| 183 | if ((p=bin[1])) |
---|
| 184 | { |
---|
| 185 | q=CACHE_POINTER(p); |
---|
| 186 | if (q->slot[0] != d1 || q->slot[1] != d2 || q->slot[2] != d3 || TAG(p) != tag) |
---|
| 187 | return (0); |
---|
| 188 | bin[1]=bin[0]; |
---|
| 189 | bin[0]=p; |
---|
| 190 | } |
---|
| 191 | else |
---|
| 192 | return (0); |
---|
| 193 | } |
---|
| 194 | } |
---|
| 195 | else |
---|
| 196 | return (0); |
---|
| 197 | bddm->op_cache.hits++; |
---|
| 198 | if ((return_fn=bddm->op_cache.return_fn[TAG(p)])) |
---|
| 199 | { |
---|
| 200 | if (return_fn == RETURN_BDD_FN) |
---|
| 201 | { |
---|
| 202 | f=(bdd)q->slot[3]; |
---|
| 203 | { |
---|
| 204 | BDD_SETUP(f); |
---|
| 205 | BDD_TEMP_INCREFS(f); |
---|
| 206 | } |
---|
| 207 | } |
---|
| 208 | else |
---|
| 209 | (*return_fn)(bddm, q); |
---|
| 210 | } |
---|
| 211 | *result=q->slot[3]; |
---|
| 212 | return (1); |
---|
| 213 | } |
---|
| 214 | |
---|
| 215 | |
---|
| 216 | void |
---|
| 217 | bdd_insert_in_cache22(cmu_bdd_manager bddm, int tag, INT_PTR d1, INT_PTR d2, INT_PTR result1, INT_PTR result2) |
---|
| 218 | { |
---|
| 219 | long hash; |
---|
| 220 | cache_entry p; |
---|
| 221 | |
---|
| 222 | hash=HASH2(d1, d2); |
---|
| 223 | BDD_REDUCE(hash, bddm->op_cache.size); |
---|
| 224 | p=bdd_get_entry(bddm, tag, bddm->op_cache.table[hash].entry); |
---|
| 225 | p->slot[0]=d1; |
---|
| 226 | p->slot[1]=d2; |
---|
| 227 | p->slot[2]=result1; |
---|
| 228 | p->slot[3]=result2; |
---|
| 229 | bddm->op_cache.inserts++; |
---|
| 230 | } |
---|
| 231 | |
---|
| 232 | |
---|
| 233 | int |
---|
| 234 | bdd_lookup_in_cache22(cmu_bdd_manager bddm, int tag, INT_PTR d1, INT_PTR d2, INT_PTR *result1, INT_PTR *result2) |
---|
| 235 | { |
---|
| 236 | long hash; |
---|
| 237 | cache_entry *bin; |
---|
| 238 | cache_entry p; |
---|
| 239 | cache_entry q; |
---|
| 240 | void (*return_fn)(cmu_bdd_manager, cache_entry); |
---|
| 241 | |
---|
| 242 | bddm->op_cache.lookups++; |
---|
| 243 | hash=HASH2(d1, d2); |
---|
| 244 | BDD_REDUCE(hash, bddm->op_cache.size); |
---|
| 245 | bin=bddm->op_cache.table[hash].entry; |
---|
| 246 | if ((p=bin[0])) |
---|
| 247 | { |
---|
| 248 | q=CACHE_POINTER(p); |
---|
| 249 | if (q->slot[0] != d1 || q->slot[1] != d2 || TAG(p) != tag) |
---|
| 250 | { |
---|
| 251 | if ((p=bin[1])) |
---|
| 252 | { |
---|
| 253 | q=CACHE_POINTER(p); |
---|
| 254 | if (q->slot[0] != d1 || q->slot[1] != d2 || TAG(p) != tag) |
---|
| 255 | return (0); |
---|
| 256 | bin[1]=bin[0]; |
---|
| 257 | bin[0]=p; |
---|
| 258 | } |
---|
| 259 | else |
---|
| 260 | return (0); |
---|
| 261 | } |
---|
| 262 | } |
---|
| 263 | else |
---|
| 264 | return (0); |
---|
| 265 | bddm->op_cache.hits++; |
---|
| 266 | if ((return_fn=bddm->op_cache.return_fn[TAG(p)])) |
---|
| 267 | (*return_fn)(bddm, q); |
---|
| 268 | *result1=q->slot[2]; |
---|
| 269 | *result2=q->slot[3]; |
---|
| 270 | return (1); |
---|
| 271 | } |
---|
| 272 | |
---|
| 273 | |
---|
| 274 | void |
---|
| 275 | bdd_insert_in_cache13(cmu_bdd_manager bddm, int tag, INT_PTR d1, INT_PTR result1, INT_PTR result2, INT_PTR result3) |
---|
| 276 | { |
---|
| 277 | long hash; |
---|
| 278 | cache_entry p; |
---|
| 279 | |
---|
| 280 | hash=HASH1(d1); |
---|
| 281 | BDD_REDUCE(hash, bddm->op_cache.size); |
---|
| 282 | p=bdd_get_entry(bddm, tag, bddm->op_cache.table[hash].entry); |
---|
| 283 | p->slot[0]=d1; |
---|
| 284 | p->slot[1]=result1; |
---|
| 285 | p->slot[2]=result2; |
---|
| 286 | p->slot[3]=result3; |
---|
| 287 | bddm->op_cache.inserts++; |
---|
| 288 | } |
---|
| 289 | |
---|
| 290 | |
---|
| 291 | int |
---|
| 292 | bdd_lookup_in_cache13(cmu_bdd_manager bddm, int tag, INT_PTR d1, INT_PTR *result1, INT_PTR *result2, INT_PTR *result3) |
---|
| 293 | { |
---|
| 294 | long hash; |
---|
| 295 | cache_entry *bin; |
---|
| 296 | cache_entry p; |
---|
| 297 | cache_entry q; |
---|
| 298 | void (*return_fn)(cmu_bdd_manager, cache_entry); |
---|
| 299 | |
---|
| 300 | bddm->op_cache.lookups++; |
---|
| 301 | hash=HASH1(d1); |
---|
| 302 | BDD_REDUCE(hash, bddm->op_cache.size); |
---|
| 303 | bin=bddm->op_cache.table[hash].entry; |
---|
| 304 | if ((p=bin[0])) |
---|
| 305 | { |
---|
| 306 | q=CACHE_POINTER(p); |
---|
| 307 | if (q->slot[0] != d1 || TAG(p) != tag) |
---|
| 308 | { |
---|
| 309 | if ((p=bin[1])) |
---|
| 310 | { |
---|
| 311 | q=CACHE_POINTER(p); |
---|
| 312 | if (q->slot[0] != d1 || TAG(p) != tag) |
---|
| 313 | return (0); |
---|
| 314 | bin[1]=bin[0]; |
---|
| 315 | bin[0]=p; |
---|
| 316 | } |
---|
| 317 | else |
---|
| 318 | return (0); |
---|
| 319 | } |
---|
| 320 | } |
---|
| 321 | else |
---|
| 322 | return (0); |
---|
| 323 | bddm->op_cache.hits++; |
---|
| 324 | if ((return_fn=bddm->op_cache.return_fn[TAG(p)])) |
---|
| 325 | (*return_fn)(bddm, q); |
---|
| 326 | *result1=q->slot[1]; |
---|
| 327 | *result2=q->slot[2]; |
---|
| 328 | *result3=q->slot[3]; |
---|
| 329 | return (1); |
---|
| 330 | } |
---|
| 331 | |
---|
| 332 | |
---|
| 333 | static |
---|
| 334 | int |
---|
| 335 | cmu_bdd_ite_gc_fn(cmu_bdd_manager bddm, cache_entry p) |
---|
| 336 | { |
---|
| 337 | int i; |
---|
| 338 | bdd f; |
---|
| 339 | |
---|
| 340 | for (i=0; i < 4; ++i) |
---|
| 341 | { |
---|
| 342 | f=(bdd)p->slot[i]; |
---|
| 343 | { |
---|
| 344 | BDD_SETUP(f); |
---|
| 345 | if (!BDD_IS_USED(f)) |
---|
| 346 | return (1); |
---|
| 347 | } |
---|
| 348 | } |
---|
| 349 | return (0); |
---|
| 350 | } |
---|
| 351 | |
---|
| 352 | |
---|
| 353 | static |
---|
| 354 | int |
---|
| 355 | bdd_two_gc_fn(cmu_bdd_manager bddm, cache_entry p) |
---|
| 356 | { |
---|
| 357 | int i; |
---|
| 358 | bdd f; |
---|
| 359 | |
---|
| 360 | for (i=1; i < 4; ++i) |
---|
| 361 | { |
---|
| 362 | f=(bdd)p->slot[i]; |
---|
| 363 | { |
---|
| 364 | BDD_SETUP(f); |
---|
| 365 | if (!BDD_IS_USED(f)) |
---|
| 366 | return (1); |
---|
| 367 | } |
---|
| 368 | } |
---|
| 369 | return (0); |
---|
| 370 | } |
---|
| 371 | |
---|
| 372 | |
---|
| 373 | static |
---|
| 374 | int |
---|
| 375 | bdd_two_data_gc_fn(cmu_bdd_manager bddm, cache_entry p) |
---|
| 376 | { |
---|
| 377 | int i; |
---|
| 378 | bdd f; |
---|
| 379 | |
---|
| 380 | for (i=1; i < 3; ++i) |
---|
| 381 | { |
---|
| 382 | f=(bdd)p->slot[i]; |
---|
| 383 | { |
---|
| 384 | BDD_SETUP(f); |
---|
| 385 | if (!BDD_IS_USED(f)) |
---|
| 386 | return (1); |
---|
| 387 | } |
---|
| 388 | } |
---|
| 389 | return (0); |
---|
| 390 | } |
---|
| 391 | |
---|
| 392 | |
---|
| 393 | static |
---|
| 394 | int |
---|
| 395 | cmu_bdd_one_data_gc_fn(cmu_bdd_manager bddm, cache_entry p) |
---|
| 396 | { |
---|
| 397 | bdd f; |
---|
| 398 | |
---|
| 399 | f=(bdd)p->slot[1]; |
---|
| 400 | { |
---|
| 401 | BDD_SETUP(f); |
---|
| 402 | return (!BDD_IS_USED(f)); |
---|
| 403 | } |
---|
| 404 | } |
---|
| 405 | |
---|
| 406 | |
---|
| 407 | /* bdd_purge_cache(bddm) purges the cache of any entries which mention */ |
---|
| 408 | /* a BDD node that is about to be garbage collected. */ |
---|
| 409 | |
---|
| 410 | void |
---|
| 411 | bdd_purge_cache(cmu_bdd_manager bddm) |
---|
| 412 | { |
---|
| 413 | long i; |
---|
| 414 | int j; |
---|
| 415 | cache_entry *bin; |
---|
| 416 | cache_entry p; |
---|
| 417 | cache_entry q; |
---|
| 418 | |
---|
| 419 | for (i=0; i < bddm->op_cache.size; ++i) |
---|
| 420 | { |
---|
| 421 | bin= &bddm->op_cache.table[i].entry[0]; |
---|
| 422 | for (j=0; j < 2; ++j) |
---|
| 423 | if ((p=bin[j])) |
---|
| 424 | { |
---|
| 425 | q=CACHE_POINTER(p); |
---|
| 426 | if ((*bddm->op_cache.gc_fn[TAG(p)])(bddm, q)) |
---|
| 427 | bdd_purge_entry(bddm, bin+j); |
---|
| 428 | else if (j == 1 && !bin[0]) |
---|
| 429 | { |
---|
| 430 | bin[0]=bin[1]; /* LRU is only one left */ |
---|
| 431 | bin[1]=0; |
---|
| 432 | } |
---|
| 433 | } |
---|
| 434 | else |
---|
| 435 | break; |
---|
| 436 | } |
---|
| 437 | } |
---|
| 438 | |
---|
| 439 | |
---|
| 440 | /* bdd_flush_cache(bddm, flush_fn, closure) purges all entries for which */ |
---|
| 441 | /* the given function returns true. */ |
---|
| 442 | |
---|
| 443 | void |
---|
| 444 | bdd_flush_cache(cmu_bdd_manager bddm, int (*flush_fn)(cmu_bdd_manager, cache_entry, pointer), pointer closure) |
---|
| 445 | { |
---|
| 446 | long i; |
---|
| 447 | int j; |
---|
| 448 | cache_entry *bin; |
---|
| 449 | |
---|
| 450 | for (i=0; i < bddm->op_cache.size; ++i) |
---|
| 451 | { |
---|
| 452 | bin=bddm->op_cache.table[i].entry; |
---|
| 453 | for (j=0; j < 2; ++j) |
---|
| 454 | if (bin[j]) |
---|
| 455 | { |
---|
| 456 | if ((*flush_fn)(bddm, bin[j], closure)) |
---|
| 457 | bdd_purge_entry(bddm, bin+j); |
---|
| 458 | else if (j == 1 && !bin[0]) |
---|
| 459 | { |
---|
| 460 | bin[0]=bin[1]; /* LRU is only one left */ |
---|
| 461 | bin[1]=0; |
---|
| 462 | } |
---|
| 463 | } |
---|
| 464 | else |
---|
| 465 | break; |
---|
| 466 | } |
---|
| 467 | } |
---|
| 468 | |
---|
| 469 | |
---|
| 470 | /* bdd_flush_all(bddm) flushes the entire cache. */ |
---|
| 471 | |
---|
| 472 | void |
---|
| 473 | bdd_flush_all(cmu_bdd_manager bddm) |
---|
| 474 | { |
---|
| 475 | long i; |
---|
| 476 | int j; |
---|
| 477 | cache_entry *bin; |
---|
| 478 | |
---|
| 479 | for (i=0; i < bddm->op_cache.size; ++i) |
---|
| 480 | { |
---|
| 481 | bin=bddm->op_cache.table[i].entry; |
---|
| 482 | for (j=0; j < 2; ++j) |
---|
| 483 | if (bin[j]) |
---|
| 484 | bdd_purge_entry(bddm, bin+j); |
---|
| 485 | else |
---|
| 486 | break; |
---|
| 487 | } |
---|
| 488 | } |
---|
| 489 | |
---|
| 490 | |
---|
| 491 | /* bdd_cache_functions(bddm, args, gc_fn, purge_fn, return_fn, flush_fn) */ |
---|
| 492 | /* controls the user cache types. Allocates an unused cache entry type */ |
---|
| 493 | /* tag and returns the tag, or -1 if no more tags are available. */ |
---|
| 494 | |
---|
| 495 | int |
---|
| 496 | bdd_cache_functions(cmu_bdd_manager bddm, |
---|
| 497 | int args, |
---|
| 498 | int (*gc_fn)(cmu_bdd_manager, cache_entry), |
---|
| 499 | void (*purge_fn)(cmu_bdd_manager, cache_entry), |
---|
| 500 | void (*return_fn)(cmu_bdd_manager, cache_entry), |
---|
| 501 | int (*flush_fn)(cmu_bdd_manager, cache_entry, pointer)) |
---|
| 502 | { |
---|
| 503 | long (*rehash_fn)(cmu_bdd_manager, cache_entry); |
---|
| 504 | int i; |
---|
| 505 | |
---|
| 506 | if (args == 1) |
---|
| 507 | rehash_fn=bdd_rehash1; |
---|
| 508 | else if (args == 2) |
---|
| 509 | rehash_fn=bdd_rehash2; |
---|
| 510 | else if (args == 3) |
---|
| 511 | rehash_fn=bdd_rehash3; |
---|
| 512 | else |
---|
| 513 | { |
---|
| 514 | rehash_fn=0; |
---|
| 515 | cmu_bdd_fatal("bdd_cache_functions: illegal number of cache arguments"); |
---|
| 516 | } |
---|
| 517 | for (i=CACHE_TYPE_USER1; i < CACHE_TYPE_USER1+USER_ENTRY_TYPES; ++i) |
---|
| 518 | if (!bddm->op_cache.rehash_fn[i]) |
---|
| 519 | break; |
---|
| 520 | if (i == CACHE_TYPE_USER1+USER_ENTRY_TYPES) |
---|
| 521 | return (-1); |
---|
| 522 | bddm->op_cache.rehash_fn[i]=rehash_fn; |
---|
| 523 | bddm->op_cache.gc_fn[i]=gc_fn; |
---|
| 524 | bddm->op_cache.purge_fn[i]=purge_fn; |
---|
| 525 | bddm->op_cache.return_fn[i]=return_fn; |
---|
| 526 | bddm->op_cache.flush_fn[i]=flush_fn; |
---|
| 527 | return (i); |
---|
| 528 | } |
---|
| 529 | |
---|
| 530 | |
---|
| 531 | static |
---|
| 532 | int |
---|
| 533 | bdd_flush_tag(cmu_bdd_manager bddm, cache_entry p, pointer tag) |
---|
| 534 | { |
---|
| 535 | /*return (TAG(p) == (int)tag);*/ |
---|
| 536 | return (TAG(p) == (long)tag); |
---|
| 537 | } |
---|
| 538 | |
---|
| 539 | |
---|
| 540 | /* cmu_bdd_free_cache_tag(bddm, tag) frees a previously allocated user */ |
---|
| 541 | /* cache tag. */ |
---|
| 542 | |
---|
| 543 | void |
---|
| 544 | cmu_bdd_free_cache_tag(cmu_bdd_manager bddm, long tag) |
---|
| 545 | { |
---|
| 546 | if (tag < CACHE_TYPE_USER1 || |
---|
| 547 | tag >= CACHE_TYPE_USER1+USER_ENTRY_TYPES || |
---|
| 548 | !bddm->op_cache.rehash_fn[(long)tag]) |
---|
| 549 | cmu_bdd_fatal("cmu_bdd_free_cache_tag: attempt to free unallocated tag"); |
---|
| 550 | bdd_flush_cache(bddm, bdd_flush_tag, (pointer)tag); |
---|
| 551 | bddm->op_cache.rehash_fn[tag]=0; |
---|
| 552 | bddm->op_cache.gc_fn[tag]=0; |
---|
| 553 | bddm->op_cache.purge_fn[tag]=0; |
---|
| 554 | bddm->op_cache.return_fn[tag]=0; |
---|
| 555 | bddm->op_cache.flush_fn[tag]=0; |
---|
| 556 | } |
---|
| 557 | |
---|
| 558 | |
---|
| 559 | static |
---|
| 560 | int |
---|
| 561 | bdd_two_flush_fn(cmu_bdd_manager bddm, cache_entry p, pointer closure) |
---|
| 562 | { |
---|
| 563 | int id_to_nuke; |
---|
| 564 | |
---|
| 565 | id_to_nuke=(long)closure; |
---|
| 566 | return (p->slot[0] == OP_RELPROD+id_to_nuke || |
---|
| 567 | p->slot[0] == OP_QNT+id_to_nuke || |
---|
| 568 | p->slot[0] == OP_SUBST+id_to_nuke); |
---|
| 569 | } |
---|
| 570 | |
---|
| 571 | |
---|
| 572 | /* cmu_bdd_init_cache(bddm) initializes the cache for a BDD manager. */ |
---|
| 573 | |
---|
| 574 | void |
---|
| 575 | cmu_bdd_init_cache(cmu_bdd_manager bddm) |
---|
| 576 | { |
---|
| 577 | long i; |
---|
| 578 | int j; |
---|
| 579 | |
---|
| 580 | bddm->op_cache.size_index=13; |
---|
| 581 | bddm->op_cache.size=TABLE_SIZE(bddm->op_cache.size_index); |
---|
| 582 | bddm->op_cache.table=(cache_bin *)mem_get_block((SIZE_T)(bddm->op_cache.size*sizeof(cache_bin))); |
---|
| 583 | for (i=0; i < bddm->op_cache.size; ++i) |
---|
| 584 | for (j=0; j < 2; ++j) |
---|
| 585 | bddm->op_cache.table[i].entry[j]=0; |
---|
| 586 | /* ITE cache control functions. */ |
---|
| 587 | bddm->op_cache.rehash_fn[CACHE_TYPE_ITE]=bdd_rehash3; |
---|
| 588 | bddm->op_cache.gc_fn[CACHE_TYPE_ITE]=cmu_bdd_ite_gc_fn; |
---|
| 589 | bddm->op_cache.purge_fn[CACHE_TYPE_ITE]=0; |
---|
| 590 | bddm->op_cache.return_fn[CACHE_TYPE_ITE]=RETURN_BDD_FN; |
---|
| 591 | bddm->op_cache.flush_fn[CACHE_TYPE_ITE]=0; |
---|
| 592 | /* Two argument op cache control functions. */ |
---|
| 593 | bddm->op_cache.rehash_fn[CACHE_TYPE_TWO]=bdd_rehash3; |
---|
| 594 | bddm->op_cache.gc_fn[CACHE_TYPE_TWO]=bdd_two_gc_fn; |
---|
| 595 | bddm->op_cache.purge_fn[CACHE_TYPE_TWO]=0; |
---|
| 596 | bddm->op_cache.return_fn[CACHE_TYPE_TWO]=RETURN_BDD_FN; |
---|
| 597 | bddm->op_cache.flush_fn[CACHE_TYPE_TWO]=bdd_two_flush_fn; |
---|
| 598 | /* One argument op w/ data result cache control functions. */ |
---|
| 599 | bddm->op_cache.rehash_fn[CACHE_TYPE_ONEDATA]=bdd_rehash2; |
---|
| 600 | bddm->op_cache.gc_fn[CACHE_TYPE_ONEDATA]=cmu_bdd_one_data_gc_fn; |
---|
| 601 | bddm->op_cache.purge_fn[CACHE_TYPE_ONEDATA]=0; |
---|
| 602 | bddm->op_cache.return_fn[CACHE_TYPE_ONEDATA]=0; |
---|
| 603 | bddm->op_cache.flush_fn[CACHE_TYPE_ONEDATA]=0; |
---|
| 604 | /* Two argument op w/ data result cache control functions. */ |
---|
| 605 | bddm->op_cache.rehash_fn[CACHE_TYPE_TWODATA]=bdd_rehash3; |
---|
| 606 | bddm->op_cache.gc_fn[CACHE_TYPE_TWODATA]=bdd_two_data_gc_fn; |
---|
| 607 | bddm->op_cache.purge_fn[CACHE_TYPE_TWODATA]=0; |
---|
| 608 | bddm->op_cache.return_fn[CACHE_TYPE_TWODATA]=0; |
---|
| 609 | bddm->op_cache.flush_fn[CACHE_TYPE_TWODATA]=0; |
---|
| 610 | /* User-defined cache control functions. */ |
---|
| 611 | for (j=CACHE_TYPE_USER1; j < CACHE_TYPE_USER1+USER_ENTRY_TYPES; ++j) |
---|
| 612 | { |
---|
| 613 | bddm->op_cache.rehash_fn[j]=0; |
---|
| 614 | bddm->op_cache.gc_fn[j]=0; |
---|
| 615 | bddm->op_cache.purge_fn[j]=0; |
---|
| 616 | bddm->op_cache.return_fn[j]=0; |
---|
| 617 | bddm->op_cache.flush_fn[j]=0; |
---|
| 618 | } |
---|
| 619 | bddm->op_cache.cache_ratio=4; |
---|
| 620 | bddm->op_cache.cache_level=0; |
---|
| 621 | bddm->op_cache.entries=0; |
---|
| 622 | bddm->op_cache.lookups=0; |
---|
| 623 | bddm->op_cache.hits=0; |
---|
| 624 | bddm->op_cache.inserts=0; |
---|
| 625 | bddm->op_cache.collisions=0; |
---|
| 626 | } |
---|
| 627 | |
---|
| 628 | |
---|
| 629 | /* cmu_bdd_free_cache(bddm) frees the storage associated with the cache of */ |
---|
| 630 | /* the indicated BDD manager. */ |
---|
| 631 | |
---|
| 632 | void |
---|
| 633 | cmu_bdd_free_cache(cmu_bdd_manager bddm) |
---|
| 634 | { |
---|
| 635 | bdd_flush_all(bddm); |
---|
| 636 | mem_free_block((pointer)bddm->op_cache.table); |
---|
| 637 | } |
---|