Lines Matching defs:htab
43 lookup (NAME *htab, HASHTYPE hval)
47 size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size);
51 hash = atomic_load_explicit(&htab->table[idx].hashval,
59 HASHTYPE second_hash = 1 + hval % (htab->size - 2);
64 idx = htab->size + idx - second_hash;
68 hash = atomic_load_explicit(&htab->table[idx].hashval,
78 insert_helper (NAME *htab, HASHTYPE hval, TYPE val)
82 size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size);
87 hash = atomic_load_explicit(&htab->table[idx].hashval,
94 atomic_compare_exchange_strong_explicit(&htab->table[idx].val_ptr,
102 atomic_store_explicit(&htab->table[idx].hashval, hval,
110 hash = atomic_load_explicit(&htab->table[idx].hashval,
120 HASHTYPE second_hash = 1 + hval % (htab->size - 2);
125 idx = htab->size + idx - second_hash;
129 hash = atomic_load_explicit(&htab->table[idx].hashval,
136 atomic_compare_exchange_strong_explicit(&htab->table[idx].val_ptr,
144 atomic_store_explicit(&htab->table[idx].hashval, hval,
152 hash = atomic_load_explicit(&htab->table[idx].hashval,
184 static void resize_helper(NAME *htab, int blocking)
186 size_t num_old_blocks = CEIL(htab->old_size, MOVE_BLOCK_SIZE);
187 size_t num_new_blocks = CEIL(htab->size, INITIALIZATION_BLOCK_SIZE);
192 while ((my_block = atomic_fetch_add_explicit(&htab->next_init_block, 1,
198 if (record_end > htab->size)
199 record_end = htab->size;
203 atomic_init(&htab->table[record_it].hashval, (uintptr_t) NULL);
204 atomic_init(&htab->table[record_it].val_ptr, (uintptr_t) NULL);
210 atomic_fetch_add_explicit(&htab->num_initialized_blocks,
212 while (atomic_load_explicit(&htab->num_initialized_blocks,
217 while ((my_block = atomic_fetch_add_explicit(&htab->next_move_block, 1,
223 if (record_end > htab->old_size)
224 record_end = htab->old_size;
229 &htab->old_table[record_it].val_ptr,
235 &htab->old_table[record_it].hashval,
239 insert_helper(htab, hashval, val_ptr);
245 atomic_fetch_add_explicit(&htab->num_moved_blocks, num_finished_blocks,
251 while (atomic_load_explicit(&htab->num_moved_blocks,
255 /* Called by the main thread holding the htab->resize_rwl lock to
259 resize_coordinator(NAME *htab)
261 htab->old_size = htab->size;
262 htab->old_table = htab->table;
264 htab->size = next_prime(htab->size * 2);
265 htab->table = malloc((1 + htab->size) * sizeof(htab->table[0]));
266 assert(htab->table);
269 atomic_fetch_xor_explicit(&htab->resizing_state,
273 resize_helper(htab, 1);
276 size_t resize_state = atomic_fetch_xor_explicit(&htab->resizing_state,
280 resize_state = atomic_load_explicit(&htab->resizing_state,
284 atomic_store_explicit(&htab->next_init_block, 0, memory_order_relaxed);
285 atomic_store_explicit(&htab->num_initialized_blocks, 0,
288 atomic_store_explicit(&htab->next_move_block, 0, memory_order_relaxed);
289 atomic_store_explicit(&htab->num_moved_blocks, 0, memory_order_relaxed);
291 free(htab->old_table);
294 atomic_fetch_xor_explicit(&htab->resizing_state, CLEANING ^ NO_RESIZING,
300 but notices it cannot get the htab->resize_rwl lock because another
304 resize_worker(NAME *htab)
306 size_t resize_state = atomic_load_explicit(&htab->resizing_state,
314 resize_state = atomic_fetch_add_explicit(&htab->resizing_state,
319 atomic_fetch_sub_explicit(&htab->resizing_state, STATE_INCREMENT,
326 resize_state = atomic_load_explicit(&htab->resizing_state,
333 atomic_fetch_sub_explicit(&htab->resizing_state, STATE_INCREMENT,
338 resize_helper(htab, 0);
341 atomic_fetch_sub_explicit(&htab->resizing_state, STATE_INCREMENT,
350 INIT(NAME) (NAME *htab, size_t init_size)
356 htab->size = init_size;
357 atomic_init(&htab->filled, 0);
358 atomic_init(&htab->resizing_state, 0);
360 atomic_init(&htab->next_init_block, 0);
361 atomic_init(&htab->num_initialized_blocks, 0);
363 atomic_init(&htab->next_move_block, 0);
364 atomic_init(&htab->num_moved_blocks, 0);
366 pthread_rwlock_init(&htab->resize_rwl, NULL);
368 htab->table = malloc ((init_size + 1) * sizeof (htab->table[0]));
369 if (htab->table == NULL)
374 atomic_init(&htab->table[i].hashval, (uintptr_t) NULL);
375 atomic_init(&htab->table[i].val_ptr, (uintptr_t) NULL);
386 FREE(NAME) (NAME *htab)
388 pthread_rwlock_destroy(&htab->resize_rwl);
389 free (htab->table);
398 INSERT(NAME) (NAME *htab, HASHTYPE hval, TYPE data)
406 while (pthread_rwlock_tryrdlock(&htab->resize_rwl) != 0)
407 resize_worker(htab);
412 filled = atomic_fetch_add_explicit(&htab->filled, 1,
418 filled = atomic_load_explicit(&htab->filled,
423 if (100 * filled > 90 * htab->size)
427 size_t resizing_state = atomic_load_explicit(&htab->resizing_state,
430 atomic_compare_exchange_strong_explicit(&htab->resizing_state,
437 pthread_rwlock_unlock(&htab->resize_rwl);
439 pthread_rwlock_wrlock(&htab->resize_rwl);
440 resize_coordinator(htab);
441 pthread_rwlock_unlock(&htab->resize_rwl);
447 pthread_rwlock_unlock(&htab->resize_rwl);
448 resize_worker(htab);
458 int ret_val = insert_helper(htab, hval, data);
460 atomic_fetch_sub_explicit(&htab->filled, 1, memory_order_relaxed);
461 pthread_rwlock_unlock(&htab->resize_rwl);
471 FIND(NAME) (NAME *htab, HASHTYPE hval)
475 while (pthread_rwlock_tryrdlock(&htab->resize_rwl) != 0)
476 resize_worker(htab);
482 idx = lookup(htab, hval);
486 pthread_rwlock_unlock(&htab->resize_rwl);
491 TYPE ret_val = (TYPE) atomic_load_explicit(&htab->table[idx].val_ptr,
494 pthread_rwlock_unlock(&htab->resize_rwl);