Changes in kernel/generic/src/adt/hash_table.c [1b20da0:a35b458] in mainline
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
kernel/generic/src/adt/hash_table.c
r1b20da0 ra35b458 96 96 assert(h); 97 97 assert(op && op->hash && op->key_hash && op->key_equal); 98 98 99 99 /* Check for compulsory ops. */ 100 100 if (!op || !op->hash || !op->key_hash || !op->key_equal) 101 101 return false; 102 102 103 103 h->bucket_cnt = round_up_size(init_size); 104 104 105 105 if (!alloc_table(h->bucket_cnt, &h->bucket)) 106 106 return false; 107 107 108 108 h->max_load = (max_load == 0) ? HT_MAX_LOAD : max_load; 109 109 h->item_cnt = 0; … … 115 115 h->op->remove_callback = nop_remove_callback; 116 116 } 117 117 118 118 return true; 119 119 } … … 128 128 assert(h && h->bucket); 129 129 assert(!h->apply_ongoing); 130 130 131 131 clear_items(h); 132 132 133 133 free(h->bucket); 134 134 … … 159 159 assert(h && h->bucket); 160 160 assert(!h->apply_ongoing); 161 161 162 162 clear_items(h); 163 163 164 164 /* Shrink the table to its minimum size if possible. */ 165 165 if (HT_MIN_BUCKETS < h->bucket_cnt) { … … 173 173 if (h->item_cnt == 0) 174 174 return; 175 175 176 176 for (size_t idx = 0; idx < h->bucket_cnt; ++idx) { 177 177 list_foreach_safe(h->bucket[idx], cur, next) { 178 178 assert(cur); 179 179 ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link); 180 180 181 181 list_remove(cur); 182 182 h->op->remove_callback(cur_link); 183 183 } 184 184 } 185 185 186 186 h->item_cnt = 0; 187 187 } … … 197 197 assert(h && h->bucket); 198 198 assert(!h->apply_ongoing); 199 199 200 200 size_t idx = h->op->hash(item) % h->bucket_cnt; 201 201 202 202 list_append(&item->link, &h->bucket[idx]); 203 203 ++h->item_cnt; … … 220 220 assert(h->op && h->op->hash && h->op->equal); 221 221 assert(!h->apply_ongoing); 222 222 223 223 size_t idx = h->op->hash(item) % h->bucket_cnt; 224 224 225 225 /* Check for duplicates. */ 226 226 list_foreach(h->bucket[idx], link, ht_link_t, cur_link) { … … 232 232 return false; 233 233 } 234 234 235 235 list_append(&item->link, &h->bucket[idx]); 236 236 ++h->item_cnt; 237 237 grow_if_needed(h); 238 238 239 239 return true; 240 240 } … … 251 251 { 252 252 assert(h && h->bucket); 253 253 254 254 size_t idx = h->op->key_hash(key) % h->bucket_cnt; 255 255 … … 264 264 } 265 265 } 266 266 267 267 return NULL; 268 268 } … … 305 305 assert(h && h->bucket); 306 306 assert(!h->apply_ongoing); 307 307 308 308 size_t idx = h->op->key_hash(key) % h->bucket_cnt; 309 309 310 310 size_t removed = 0; 311 311 312 312 list_foreach_safe(h->bucket[idx], cur, next) { 313 313 ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link); 314 314 315 315 if (h->op->key_equal(key, cur_link)) { 316 316 ++removed; … … 322 322 h->item_cnt -= removed; 323 323 shrink_if_needed(h); 324 324 325 325 return removed; 326 326 } … … 352 352 assert(f); 353 353 assert(h && h->bucket); 354 354 355 355 if (h->item_cnt == 0) 356 356 return; 357 357 358 358 h->apply_ongoing = true; 359 359 360 360 for (size_t idx = 0; idx < h->bucket_cnt; ++idx) { 361 361 list_foreach_safe(h->bucket[idx], cur, next) { … … 371 371 out: 372 372 h->apply_ongoing = false; 373 373 374 374 shrink_if_needed(h); 375 375 grow_if_needed(h); … … 380 380 { 381 381 size_t rounded_size = HT_MIN_BUCKETS; 382 382 383 383 while (rounded_size < size) { 384 384 rounded_size = 2 * rounded_size + 1; 385 385 } 386 386 387 387 return rounded_size; 388 388 } … … 392 392 { 393 393 assert(pbuckets && HT_MIN_BUCKETS <= bucket_cnt); 394 394 395 395 list_t *buckets = malloc(bucket_cnt * sizeof(list_t), FRAME_ATOMIC); 396 396 if (!buckets) 397 397 return false; 398 398 399 399 for (size_t i = 0; i < bucket_cnt; i++) 400 400 list_initialize(&buckets[i]); … … 434 434 assert(h && h->bucket); 435 435 assert(HT_MIN_BUCKETS <= new_bucket_cnt); 436 436 437 437 /* We are traversing the table and resizing would mess up the buckets. */ 438 438 if (h->apply_ongoing) 439 439 return; 440 440 441 441 list_t *new_buckets; 442 442 … … 444 444 if (!alloc_table(new_bucket_cnt, &new_buckets)) 445 445 return; 446 446 447 447 if (0 < h->item_cnt) { 448 448 /* Rehash all the items to the new table. */ … … 457 457 } 458 458 } 459 459 460 460 free(h->bucket); 461 461 h->bucket = new_buckets;
Note:
See TracChangeset
for help on using the changeset viewer.