* No space is available in bucket. Randomly evict an item, then try to find an * alternate location for that item. Iteratively repeat this * eviction/relocation procedure until either success or detection of an * eviction/relocation bucket cycle. */
| 131 | * eviction/relocation bucket cycle. |
| 132 | */ |
| 133 | static bool |
| 134 | ckh_evict_reloc_insert(ckh_t *ckh, size_t argbucket, void const **argkey, |
| 135 | void const **argdata) { |
| 136 | const void *key, *data, *tkey, *tdata; |
| 137 | ckhc_t *cell; |
| 138 | size_t hashes[2], bucket, tbucket; |
| 139 | unsigned i; |
| 140 | |
| 141 | bucket = argbucket; |
| 142 | key = *argkey; |
| 143 | data = *argdata; |
| 144 | while (true) { |
| 145 | /* |
| 146 | * Choose a random item within the bucket to evict. This is |
| 147 | * critical to correct function, because without (eventually) |
| 148 | * evicting all items within a bucket during iteration, it |
| 149 | * would be possible to get stuck in an infinite loop if there |
| 150 | * were an item for which both hashes indicated the same |
| 151 | * bucket. |
| 152 | */ |
| 153 | i = (unsigned)prng_lg_range_u64(&ckh->prng_state, |
| 154 | LG_CKH_BUCKET_CELLS); |
| 155 | cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i]; |
| 156 | assert(cell->key != NULL); |
| 157 | |
| 158 | /* Swap cell->{key,data} and {key,data} (evict). */ |
| 159 | tkey = cell->key; tdata = cell->data; |
| 160 | cell->key = key; cell->data = data; |
| 161 | key = tkey; data = tdata; |
| 162 | |
| 163 | #ifdef CKH_COUNT |
| 164 | ckh->nrelocs++; |
| 165 | #endif |
| 166 | |
| 167 | /* Find the alternate bucket for the evicted item. */ |
| 168 | ckh->hash(key, hashes); |
| 169 | tbucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1); |
| 170 | if (tbucket == bucket) { |
| 171 | tbucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) |
| 172 | - 1); |
| 173 | /* |
| 174 | * It may be that (tbucket == bucket) still, if the |
| 175 | * item's hashes both indicate this bucket. However, |
| 176 | * we are guaranteed to eventually escape this bucket |
| 177 | * during iteration, assuming pseudo-random item |
| 178 | * selection (true randomness would make infinite |
| 179 | * looping a remote possibility). The reason we can |
| 180 | * never get trapped forever is that there are two |
| 181 | * cases: |
| 182 | * |
| 183 | * 1) This bucket == argbucket, so we will quickly |
| 184 | * detect an eviction cycle and terminate. |
| 185 | * 2) An item was evicted to this bucket from another, |
| 186 | * which means that at least one item in this bucket |
| 187 | * has hashes that indicate distinct buckets. |
| 188 | */ |
| 189 | } |
| 190 | /* Check for a cycle. */ |
no test coverage detected