135 #define MAX_COUNT_PER_PARTITION(hash_table)				\  argument
136 	(BUCKETS_PER_PARTITION(hash_table->size_log2) / 2 + \
137 	 BUCKETS_PER_PARTITION(hash_table->size_log2) / 4)
157 #define BUCKET_FOR_HASH(hash_table, hash)								\  argument
158 	(hash_table->buckets[												\
160 									   hash_table->size_log2)])
162 static void delete_item(dshash_table *hash_table,
164 static void resize(dshash_table *hash_table, size_t new_size);
165 static inline void ensure_valid_bucket_pointers(dshash_table *hash_table);
166 static inline dshash_table_item *find_in_bucket(dshash_table *hash_table,
169 static void insert_item_into_bucket(dshash_table *hash_table,
173 static dshash_table_item *insert_into_bucket(dshash_table *hash_table,
176 static bool delete_key_from_bucket(dshash_table *hash_table,
179 static bool delete_item_from_bucket(dshash_table *hash_table,
182 static inline dshash_hash hash_key(dshash_table *hash_table, const void *key);
183 static inline bool equal_keys(dshash_table *hash_table,
186 #define PARTITION_LOCK(hash_table, i)			\  argument
187 	(&(hash_table)->control->partitions[(i)].lock)
198 	dshash_table *hash_table;  in dshash_create()  local
202 	hash_table = palloc(sizeof(dshash_table));  in dshash_create()
208 	hash_table->area = area;  in dshash_create()
209 	hash_table->params = *params;  in dshash_create()
210 	hash_table->arg = arg;  in dshash_create()
211 	hash_table->control = dsa_get_address(area, control);  in dshash_create()
212 	hash_table->control->handle = control;  in dshash_create()
213 	hash_table->control->magic = DSHASH_MAGIC;  in dshash_create()
214 	hash_table->control->lwlock_tranche_id = params->tranche_id;  in dshash_create()
218 		dshash_partition *partitions = hash_table->control->partitions;  in dshash_create()
219 		int			tranche_id = hash_table->control->lwlock_tranche_id;  in dshash_create()
229 	hash_table->find_locked = false;  in dshash_create()
230 	hash_table->find_exclusively_locked = false;  in dshash_create()
236 	hash_table->control->size_log2 = DSHASH_NUM_PARTITIONS_LOG2;  in dshash_create()
237 	hash_table->control->buckets =  in dshash_create()
241 	if (!DsaPointerIsValid(hash_table->control->buckets))  in dshash_create()
250 	hash_table->buckets = dsa_get_address(area,  in dshash_create()
251 										  hash_table->control->buckets);  in dshash_create()
252 	hash_table->size_log2 = hash_table->control->size_log2;  in dshash_create()
254 	return hash_table;  in dshash_create()
266 	dshash_table *hash_table;  in dshash_attach()  local
270 	hash_table = palloc(sizeof(dshash_table));  in dshash_attach()
276 	hash_table->area = area;  in dshash_attach()
277 	hash_table->params = *params;  in dshash_attach()
278 	hash_table->arg = arg;  in dshash_attach()
279 	hash_table->control = dsa_get_address(area, control);  in dshash_attach()
280 	hash_table->find_locked = false;  in dshash_attach()
281 	hash_table->find_exclusively_locked = false;  in dshash_attach()
282 	Assert(hash_table->control->magic == DSHASH_MAGIC);  in dshash_attach()
289 	hash_table->buckets = NULL;  in dshash_attach()
290 	hash_table->size_log2 = 0;  in dshash_attach()
292 	return hash_table;  in dshash_attach()
302 dshash_detach(dshash_table *hash_table)  in dshash_detach()  argument
304 	Assert(!hash_table->find_locked);  in dshash_detach()
307 	pfree(hash_table);  in dshash_detach()
318 dshash_destroy(dshash_table *hash_table)  in dshash_destroy()  argument
323 	Assert(hash_table->control->magic == DSHASH_MAGIC);  in dshash_destroy()
324 	ensure_valid_bucket_pointers(hash_table);  in dshash_destroy()
327 	size = ((size_t) 1) << hash_table->size_log2;  in dshash_destroy()
330 		dsa_pointer item_pointer = hash_table->buckets[i];  in dshash_destroy()
337 			item = dsa_get_address(hash_table->area, item_pointer);  in dshash_destroy()
339 			dsa_free(hash_table->area, item_pointer);  in dshash_destroy()
348 	hash_table->control->magic = 0;  in dshash_destroy()
351 	dsa_free(hash_table->area, hash_table->control->buckets);  in dshash_destroy()
352 	dsa_free(hash_table->area, hash_table->control->handle);  in dshash_destroy()
354 	pfree(hash_table);  in dshash_destroy()
362 dshash_get_hash_table_handle(dshash_table *hash_table)  in dshash_get_hash_table_handle()  argument
364 	Assert(hash_table->control->magic == DSHASH_MAGIC);  in dshash_get_hash_table_handle()
366 	return hash_table->control->handle;  in dshash_get_hash_table_handle()
385 dshash_find(dshash_table *hash_table, const void *key, bool exclusive)  in dshash_find()  argument
391 	hash = hash_key(hash_table, key);  in dshash_find()
394 	Assert(hash_table->control->magic == DSHASH_MAGIC);  in dshash_find()
395 	Assert(!hash_table->find_locked);  in dshash_find()
397 	LWLockAcquire(PARTITION_LOCK(hash_table, partition),  in dshash_find()
399 	ensure_valid_bucket_pointers(hash_table);  in dshash_find()
402 	item = find_in_bucket(hash_table, key, BUCKET_FOR_HASH(hash_table, hash));  in dshash_find()
407 		LWLockRelease(PARTITION_LOCK(hash_table, partition));  in dshash_find()
413 		hash_table->find_locked = true;  in dshash_find()
414 		hash_table->find_exclusively_locked = exclusive;  in dshash_find()
430 dshash_find_or_insert(dshash_table *hash_table,  in dshash_find_or_insert()  argument
439 	hash = hash_key(hash_table, key);  in dshash_find_or_insert()
441 	partition = &hash_table->control->partitions[partition_index];  in dshash_find_or_insert()
443 	Assert(hash_table->control->magic == DSHASH_MAGIC);  in dshash_find_or_insert()
444 	Assert(!hash_table->find_locked);  in dshash_find_or_insert()
447 	LWLockAcquire(PARTITION_LOCK(hash_table, partition_index),  in dshash_find_or_insert()
449 	ensure_valid_bucket_pointers(hash_table);  in dshash_find_or_insert()
452 	item = find_in_bucket(hash_table, key, BUCKET_FOR_HASH(hash_table, hash));  in dshash_find_or_insert()
461 		if (partition->count > MAX_COUNT_PER_PARTITION(hash_table))  in dshash_find_or_insert()
474 			LWLockRelease(PARTITION_LOCK(hash_table, partition_index));  in dshash_find_or_insert()
475 			resize(hash_table, hash_table->size_log2 + 1);  in dshash_find_or_insert()
481 		item = insert_into_bucket(hash_table, key,  in dshash_find_or_insert()
482 								  &BUCKET_FOR_HASH(hash_table, hash));  in dshash_find_or_insert()
489 	hash_table->find_locked = true;  in dshash_find_or_insert()
490 	hash_table->find_exclusively_locked = true;  in dshash_find_or_insert()
502 dshash_delete_key(dshash_table *hash_table, const void *key)  in dshash_delete_key()  argument
508 	Assert(hash_table->control->magic == DSHASH_MAGIC);  in dshash_delete_key()
509 	Assert(!hash_table->find_locked);  in dshash_delete_key()
511 	hash = hash_key(hash_table, key);  in dshash_delete_key()
514 	LWLockAcquire(PARTITION_LOCK(hash_table, partition), LW_EXCLUSIVE);  in dshash_delete_key()
515 	ensure_valid_bucket_pointers(hash_table);  in dshash_delete_key()
517 	if (delete_key_from_bucket(hash_table, key,  in dshash_delete_key()
518 							   &BUCKET_FOR_HASH(hash_table, hash)))  in dshash_delete_key()
520 		Assert(hash_table->control->partitions[partition].count > 0);  in dshash_delete_key()
522 		--hash_table->control->partitions[partition].count;  in dshash_delete_key()
527 	LWLockRelease(PARTITION_LOCK(hash_table, partition));  in dshash_delete_key()
540 dshash_delete_entry(dshash_table *hash_table, void *entry)  in dshash_delete_entry()  argument
545 	Assert(hash_table->control->magic == DSHASH_MAGIC);  in dshash_delete_entry()
546 	Assert(hash_table->find_locked);  in dshash_delete_entry()
547 	Assert(hash_table->find_exclusively_locked);  in dshash_delete_entry()
548 	Assert(LWLockHeldByMeInMode(PARTITION_LOCK(hash_table, partition),  in dshash_delete_entry()
551 	delete_item(hash_table, item);  in dshash_delete_entry()
552 	hash_table->find_locked = false;  in dshash_delete_entry()
553 	hash_table->find_exclusively_locked = false;  in dshash_delete_entry()
554 	LWLockRelease(PARTITION_LOCK(hash_table, partition));  in dshash_delete_entry()
561 dshash_release_lock(dshash_table *hash_table, void *entry)  in dshash_release_lock()  argument
566 	Assert(hash_table->control->magic == DSHASH_MAGIC);  in dshash_release_lock()
567 	Assert(hash_table->find_locked);  in dshash_release_lock()
568 	Assert(LWLockHeldByMeInMode(PARTITION_LOCK(hash_table, partition_index),  in dshash_release_lock()
569 								hash_table->find_exclusively_locked  in dshash_release_lock()
572 	hash_table->find_locked = false;  in dshash_release_lock()
573 	hash_table->find_exclusively_locked = false;  in dshash_release_lock()
574 	LWLockRelease(PARTITION_LOCK(hash_table, partition_index));  in dshash_release_lock()
600 dshash_dump(dshash_table *hash_table)  in dshash_dump()  argument
605 	Assert(hash_table->control->magic == DSHASH_MAGIC);  in dshash_dump()
606 	Assert(!hash_table->find_locked);  in dshash_dump()
610 		Assert(!LWLockHeldByMe(PARTITION_LOCK(hash_table, i)));  in dshash_dump()
611 		LWLockAcquire(PARTITION_LOCK(hash_table, i), LW_SHARED);  in dshash_dump()
614 	ensure_valid_bucket_pointers(hash_table);  in dshash_dump()
617 			"hash table size = %zu\n", (size_t) 1 << hash_table->size_log2);  in dshash_dump()
620 		dshash_partition *partition = &hash_table->control->partitions[i];  in dshash_dump()
621 		size_t		begin = BUCKET_INDEX_FOR_PARTITION(i, hash_table->size_log2);  in dshash_dump()
622 		size_t		end = BUCKET_INDEX_FOR_PARTITION(i + 1, hash_table->size_log2);  in dshash_dump()
631 			dsa_pointer bucket = hash_table->buckets[j];  in dshash_dump()
637 				item = dsa_get_address(hash_table->area, bucket);  in dshash_dump()
647 		LWLockRelease(PARTITION_LOCK(hash_table, i));  in dshash_dump()
654 delete_item(dshash_table *hash_table, dshash_table_item *item)  in delete_item()  argument
659 	Assert(LWLockHeldByMe(PARTITION_LOCK(hash_table, partition)));  in delete_item()
661 	if (delete_item_from_bucket(hash_table, item,  in delete_item()
662 								&BUCKET_FOR_HASH(hash_table, hash)))  in delete_item()
664 		Assert(hash_table->control->partitions[partition].count > 0);  in delete_item()
665 		--hash_table->control->partitions[partition].count;  in delete_item()
680 resize(dshash_table *hash_table, size_t new_size_log2)  in resize()  argument
695 		Assert(!LWLockHeldByMe(PARTITION_LOCK(hash_table, i)));  in resize()
697 		LWLockAcquire(PARTITION_LOCK(hash_table, i), LW_EXCLUSIVE);  in resize()
698 		if (i == 0 && hash_table->control->size_log2 >= new_size_log2)  in resize()
704 			LWLockRelease(PARTITION_LOCK(hash_table, 0));  in resize()
709 	Assert(new_size_log2 == hash_table->control->size_log2 + 1);  in resize()
712 	new_buckets_shared = dsa_allocate0(hash_table->area,  in resize()
714 	new_buckets = dsa_get_address(hash_table->area, new_buckets_shared);  in resize()
720 	size = ((size_t) 1) << hash_table->control->size_log2;  in resize()
723 		dsa_pointer item_pointer = hash_table->buckets[i];  in resize()
730 			item = dsa_get_address(hash_table->area, item_pointer);  in resize()
732 			insert_item_into_bucket(hash_table, item_pointer, item,  in resize()
740 	old_buckets = hash_table->control->buckets;  in resize()
741 	hash_table->control->buckets = new_buckets_shared;  in resize()
742 	hash_table->control->size_log2 = new_size_log2;  in resize()
743 	hash_table->buckets = new_buckets;  in resize()
744 	dsa_free(hash_table->area, old_buckets);  in resize()
748 		LWLockRelease(PARTITION_LOCK(hash_table, i));  in resize()
757 ensure_valid_bucket_pointers(dshash_table *hash_table)  in ensure_valid_bucket_pointers()  argument
759 	if (hash_table->size_log2 != hash_table->control->size_log2)  in ensure_valid_bucket_pointers()
761 		hash_table->buckets = dsa_get_address(hash_table->area,  in ensure_valid_bucket_pointers()
762 											  hash_table->control->buckets);  in ensure_valid_bucket_pointers()
763 		hash_table->size_log2 = hash_table->control->size_log2;  in ensure_valid_bucket_pointers()
771 find_in_bucket(dshash_table *hash_table, const void *key,  in find_in_bucket()  argument
778 		item = dsa_get_address(hash_table->area, item_pointer);  in find_in_bucket()
779 		if (equal_keys(hash_table, key, ENTRY_FROM_ITEM(item)))  in find_in_bucket()
790 insert_item_into_bucket(dshash_table *hash_table,  in insert_item_into_bucket()  argument
795 	Assert(item == dsa_get_address(hash_table->area, item_pointer));  in insert_item_into_bucket()
806 insert_into_bucket(dshash_table *hash_table,  in insert_into_bucket()  argument
813 	item_pointer = dsa_allocate(hash_table->area,  in insert_into_bucket()
814 								hash_table->params.entry_size +  in insert_into_bucket()
816 	item = dsa_get_address(hash_table->area, item_pointer);  in insert_into_bucket()
817 	memcpy(ENTRY_FROM_ITEM(item), key, hash_table->params.key_size);  in insert_into_bucket()
818 	insert_item_into_bucket(hash_table, item_pointer, item, bucket);  in insert_into_bucket()
826 delete_key_from_bucket(dshash_table *hash_table,  in delete_key_from_bucket()  argument
834 		item = dsa_get_address(hash_table->area, *bucket_head);  in delete_key_from_bucket()
836 		if (equal_keys(hash_table, key, ENTRY_FROM_ITEM(item)))  in delete_key_from_bucket()
841 			dsa_free(hash_table->area, *bucket_head);  in delete_key_from_bucket()
855 delete_item_from_bucket(dshash_table *hash_table,  in delete_item_from_bucket()  argument
863 		bucket_item = dsa_get_address(hash_table->area, *bucket_head);  in delete_item_from_bucket()
870 			dsa_free(hash_table->area, *bucket_head);  in delete_item_from_bucket()
883 hash_key(dshash_table *hash_table, const void *key)  in hash_key()  argument
885 	return hash_table->params.hash_function(key,  in hash_key()
886 											hash_table->params.key_size,  in hash_key()
887 											hash_table->arg);  in hash_key()
894 equal_keys(dshash_table *hash_table, const void *a, const void *b)  in equal_keys()  argument
896 	return hash_table->params.compare_function(a, b,  in equal_keys()
897 											   hash_table->params.key_size,  in equal_keys()
898 											   hash_table->arg) == 0;  in equal_keys()