| 99 | } |
| 100 | |
| 101 | static bool |
| 102 | ckh_try_bucket_insert(ckh_t *ckh, size_t bucket, const void *key, |
| 103 | const void *data) { |
| 104 | ckhc_t *cell; |
| 105 | unsigned offset, i; |
| 106 | |
| 107 | /* |
| 108 | * Cycle through the cells in the bucket, starting at a random position. |
| 109 | * The randomness avoids worst-case search overhead as buckets fill up. |
| 110 | */ |
| 111 | offset = (unsigned)prng_lg_range_u64(&ckh->prng_state, |
| 112 | LG_CKH_BUCKET_CELLS); |
| 113 | for (i = 0; i < (ZU(1) << LG_CKH_BUCKET_CELLS); i++) { |
| 114 | cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + |
| 115 | ((i + offset) & ((ZU(1) << LG_CKH_BUCKET_CELLS) - 1))]; |
| 116 | if (cell->key == NULL) { |
| 117 | cell->key = key; |
| 118 | cell->data = data; |
| 119 | ckh->count++; |
| 120 | return false; |
| 121 | } |
| 122 | } |
| 123 | |
| 124 | return true; |
| 125 | } |
| 126 | |
| 127 | /* |
| 128 | * No space is available in bucket. Randomly evict an item, then try to find an |
no test coverage detected