12#ifndef ROC_CORE_HASHMAP_H_
13#define ROC_CORE_HASHMAP_H_
76 size_t EmbeddedCapacity = 0,
77 template <
class TT>
class OwnershipPolicy = RefCountedOwnership>
83 typedef typename OwnershipPolicy<T>::Pointer
Pointer;
93 , rehash_remain_nodes_(0)
94 , allocator_(allocator) {
95 if (EmbeddedCapacity != 0) {
96 if (!realloc_buckets_(NumEmbeddedBuckets)) {
97 roc_panic(
"hashmap: initialization failed");
104 release_bucket_array_(curr_buckets_, n_curr_buckets_);
105 release_bucket_array_(prev_buckets_, n_prev_buckets_);
113 return buckets_capacity_(n_curr_buckets_);
129 if (member_of_bucket_array_(curr_buckets_, n_curr_buckets_, node)) {
133 if (member_of_bucket_array_(prev_buckets_, n_prev_buckets_, node)) {
154 return find_node_(hash, key);
178 if (size_ >= buckets_capacity_(n_curr_buckets_)) {
180 "hashmap: attempt to insert into full hashmap before calling grow()");
185 if (node->
bucket != NULL) {
188 " attempt to insert an element which is already a member of %s hashmap",
189 contains(element) ?
"this" :
"another");
192 const hashsum_t hash = T::key_hash(element.key());
194 if (find_node_(hash, element.key())) {
195 roc_panic(
"hashmap: attempt to insert an element with duplicate key");
198 Bucket& bucket = select_bucket_(hash);
201 insert_node_(bucket, node);
203 proceed_rehash_(
true);
205 OwnershipPolicy<T>::acquire(element);
226 " attempt to remove an element which is not a member of %s hashmap",
227 node->
bucket == NULL ?
"any" :
"this");
232 proceed_rehash_(
false);
234 OwnershipPolicy<T>::release(element);
254 const size_t cap = buckets_capacity_(n_curr_buckets_);
258 size_t n_buckets = n_curr_buckets_;
260 n_buckets = get_prime_larger_than_(n_buckets);
261 }
while (size_ >= buckets_capacity_(n_buckets));
263 if (!realloc_buckets_(n_buckets)) {
267 const size_t new_cap = buckets_capacity_(n_curr_buckets_);
282 (EmbeddedCapacity * LoafFactorDen + LoafFactorNum - 1) / LoafFactorNum
286 HashmapNode::HashmapNodeData* head;
289 bool realloc_buckets_(
size_t n_buckets) {
296 if (n_buckets <= NumEmbeddedBuckets
297 && curr_buckets_ != (Bucket*)embedded_buckets_.
memory()) {
298 buckets = (Bucket*)embedded_buckets_.
memory();
300 buckets = (Bucket*)allocator_.
allocate(n_buckets *
sizeof(Bucket));
301 if (buckets == NULL) {
306 memset(buckets, 0, n_buckets *
sizeof(Bucket));
308 if (prev_buckets_ && prev_buckets_ != (Bucket*)embedded_buckets_.
memory()) {
310 prev_buckets_ = NULL;
314 prev_buckets_ = curr_buckets_;
315 n_prev_buckets_ = n_curr_buckets_;
318 rehash_remain_nodes_ = size_;
321 curr_buckets_ = buckets;
322 n_curr_buckets_ = n_buckets;
327 void dealloc_buckets_() {
328 if (curr_buckets_ && curr_buckets_ != (Bucket*)embedded_buckets_.
memory()) {
332 if (prev_buckets_ && prev_buckets_ != (Bucket*)embedded_buckets_.
memory()) {
337 bool member_of_bucket_array_(Bucket* buckets,
339 const HashmapNode::HashmapNodeData* node)
const {
340 if (n_buckets == 0) {
344 Bucket* node_bucket = (Bucket*)node->bucket;
346 return node_bucket >= buckets && node_bucket < buckets + n_buckets;
349 void release_bucket_array_(Bucket* buckets,
size_t n_buckets) {
350 if (n_buckets == 0) {
354 for (
size_t n = 0; n < n_buckets; n++) {
355 HashmapNode::HashmapNodeData* node = buckets[n].head;
358 T* elem =
static_cast<T*
>(node->container_of());
363 if (node == buckets[n].head) {
367 OwnershipPolicy<T>::release(*elem);
372 template <
class Key> T* find_node_(
hashsum_t hash,
const Key& key)
const {
373 if (n_curr_buckets_ != 0) {
374 T* elem = find_in_bucket_(curr_buckets_[hash % n_curr_buckets_], hash, key);
380 if (n_prev_buckets_ != 0) {
381 T* elem = find_in_bucket_(prev_buckets_[hash % n_prev_buckets_], hash, key);
391 T* find_in_bucket_(
const Bucket& bucket,
hashsum_t hash,
const Key& key)
const {
392 HashmapNode::HashmapNodeData* node = bucket.head;
396 if (node->hash == hash) {
397 T* elem =
static_cast<T*
>(node->container_of());
399 if (T::key_equal(elem->key(), key)) {
405 }
while (node != bucket.head);
411 size_t buckets_capacity_(
size_t n_buckets)
const {
412 return n_buckets * LoafFactorNum / LoafFactorDen;
415 Bucket& select_bucket_(
hashsum_t hash)
const {
418 return curr_buckets_[hash % n_curr_buckets_];
421 void insert_node_(Bucket& bucket, HashmapNode::HashmapNodeData* node) {
422 if (HashmapNode::HashmapNodeData* head = bucket.head) {
424 node->prev = head->prev;
426 head->prev->next = node;
435 node->bucket = (
void*)&bucket;
440 void remove_node_(HashmapNode::HashmapNodeData* node) {
441 Bucket& bucket = *(Bucket*)node->bucket;
443 if (bucket.head == node) {
444 if (node->next != node) {
445 bucket.head = node->next;
451 node->prev->next = node->next;
452 node->next->prev = node->prev;
454 if (member_of_bucket_array_(prev_buckets_, n_prev_buckets_, node)) {
456 rehash_remain_nodes_--;
464 void proceed_rehash_(
bool in_insert) {
465 if (rehash_remain_nodes_ == 0) {
469 size_t num_migrations = 1;
472 const size_t inserts_until_rehash =
473 buckets_capacity_(n_curr_buckets_) - size_;
475 if (inserts_until_rehash == 0) {
477 num_migrations = rehash_remain_nodes_;
480 num_migrations = (rehash_remain_nodes_ + inserts_until_rehash - 1)
481 / inserts_until_rehash;
488 Bucket& bucket = prev_buckets_[rehash_pos_];
490 if (bucket.head == NULL) {
493 if (rehash_pos_ == n_prev_buckets_) {
504 if (num_migrations == 0) {
508 migrate_node_(bucket.head);
513 void migrate_node_(HashmapNode::HashmapNodeData* node) {
516 Bucket& bucket = select_bucket_(node->hash);
518 insert_node_(bucket, node);
521 size_t get_prime_larger_than_(
size_t min) {
522 static const size_t primes[] = {
523 53, 97, 193, 389, 769, 1543, 3079,
524 6151, 12289, 24593, 49157, 98317, 196613, 393241,
525 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653,
526 100663319, 201326611, 402653189, 805306457, 1610612741
530 if (primes[n] > min) {
539 Bucket* curr_buckets_;
540 size_t n_curr_buckets_;
542 Bucket* prev_buckets_;
543 size_t n_prev_buckets_;
548 size_t rehash_remain_nodes_;
550 IAllocator& allocator_;
552 AlignedStorage<NumEmbeddedBuckets *
sizeof(Bucket)> embedded_buckets_;
const void * memory() const
Get storage memory.
size_t size() const
Get number of elements added to hashmap.
~Hashmap()
Release ownership of all elements.
void remove(T &element)
Remove element from hashmap.
Hashmap(IAllocator &allocator)
Initialize empty hashmap.
bool contains(const T &element) const
Check if element belongs to hashmap.
void insert(T &element)
Insert element into hashmap.
OwnershipPolicy< T >::Pointer Pointer
Pointer type.
size_t capacity() const
Get maximum number of elements that can be added to hashmap before grow() should be called.
Pointer find(const Key &key) const
Find element in the hashmap by key.
bool grow()
Grow hashtable capacity.
Memory allocator interface.
virtual void deallocate(void *)=0
Deallocate previously allocated memory.
virtual void * allocate(size_t size)=0
Allocate memory.
Base class for non-copyable objects.
Memory allocator interface.
#define ROC_ARRAY_SIZE(a)
Get number of elements in a static array.
size_t hashsum_t
Hash type.
#define roc_panic_if_not(x)
Panic if condition is false.
#define roc_panic_if(x)
Panic if condition is true.
#define roc_panic(...)
Print error message and terminate program gracefully.
Commonly used types and functions.
void * bucket
The bucket this node belongs to.
hashsum_t hash
Cached node hash.