Roc Toolkit internal modules
Roc Toolkit: real-time audio streaming
hashmap_impl.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2020 Roc Streaming authors
3 *
4 * This Source Code Form is subject to the terms of the Mozilla Public
5 * License, v. 2.0. If a copy of the MPL was not distributed with this
6 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
7 */
8
9//! @file roc_core/hashmap_impl.h
10//! @brief Intrusive hash table implementation file.
11
12#ifndef ROC_CORE_HASHMAP_IMPL_H_
13#define ROC_CORE_HASHMAP_IMPL_H_
14
16#include "roc_core/attributes.h"
18#include "roc_core/hashsum.h"
19#include "roc_core/iarena.h"
23#include "roc_core/panic.h"
24#include "roc_core/stddefs.h"
25
26namespace roc {
27namespace core {
28
29//! Intrusive hash table internal implementation.
31public:
32 enum {
33 // rehash happens when n_elements >= n_buckets * LoadFactorNum / LoadFactorDen
34 LoadFactorNum = 13,
35 LoadFactorDen = 2,
36 };
37
38 //! Bucket container.
39 struct Bucket {
40 //! Pointer to head node.
42 };
43
44 //! Callback function pointer type for key equality check.
46 const void* key);
47
48 //! Initialize empty hashmap.
49 HashmapImpl(void* preallocated_data, size_t num_embedded_buckets, IArena* arena);
50
51 //! Deinitialize.
53
54 //! Get maximum number of nodes that can be added to hashmap before
55 //! grow() should be called.
56 size_t capacity() const;
57
58 //! Get number of nodes added to hashmap.
59 size_t size() const;
60
61 //! Check if node belongs to hashmap.
62 bool contains(const HashmapNode::HashmapNodeData* node) const;
63
64 //! Find node in the hashmap.
66 find_node(hashsum_t hash, const void* key, key_equals_callback callback) const;
67
68 //! Get first node in hashmap.
70
71 //! Get last node in hashmap.
73
74 //! Get hashmap node next to given one.
76
77 //! Insert node into hashmap.
79 hashsum_t hash,
80 const void* key,
81 key_equals_callback callback);
82
83 //! Remove node from hashmap.
84 void remove(HashmapNode::HashmapNodeData* node, bool skip_rehash);
85
86 //! Grow hashtable capacity.
88
89private:
90 HashmapNode::HashmapNodeData* find_in_bucket_(const Bucket& bucket,
91 hashsum_t hash,
92 const void* key,
93 key_equals_callback callback) const;
94
95 size_t buckets_capacity_(size_t n_buckets) const;
96
97 bool realloc_buckets_(size_t n_buckets);
98 void dealloc_buckets_();
99
100 bool member_of_bucket_array_(Bucket* buckets,
101 size_t n_buckets,
102 const HashmapNode::HashmapNodeData* node) const;
103
104 Bucket& select_bucket_(hashsum_t hash) const;
105 void bucket_insert_(Bucket& bucket, HashmapNode::HashmapNodeData* node);
106 void bucket_remove_(HashmapNode::HashmapNodeData* node);
107 void all_list_insert_(HashmapNode::HashmapNodeData* node);
108 void all_list_remove_(HashmapNode::HashmapNodeData* node);
109 void proceed_rehash_(bool in_insert);
110 void migrate_node_(HashmapNode::HashmapNodeData* node);
111 size_t get_next_bucket_size_(size_t current_count);
112
113 void* preallocated_data_;
114 size_t num_preallocated_buckets_;
115
116 Bucket* curr_buckets_;
117 size_t n_curr_buckets_;
118
119 Bucket* prev_buckets_;
120 size_t n_prev_buckets_;
121
122 size_t size_;
123
124 size_t rehash_pos_;
125 size_t rehash_remain_nodes_;
126
127 // head of list of all nodes
129
130 IArena* arena_;
131};
132
133} // namespace core
134} // namespace roc
135
136#endif // ROC_CORE_HASHMAP_IMPL_H_
Aligned storage.
Compiler attributes.
#define ROC_ATTR_NODISCARD
Emit warning if function result is not checked.
Definition: attributes.h:31
Intrusive hash table internal implementation.
Definition: hashmap_impl.h:30
bool insert(HashmapNode::HashmapNodeData *node, hashsum_t hash, const void *key, key_equals_callback callback)
Insert node into hashmap.
size_t size() const
Get number of nodes added to hashmap.
void remove(HashmapNode::HashmapNodeData *node, bool skip_rehash)
Remove node from hashmap.
HashmapImpl(void *preallocated_data, size_t num_embedded_buckets, IArena *arena)
Initialize empty hashmap.
HashmapNode::HashmapNodeData * front() const
Get first node in hashmap.
ROC_ATTR_NODISCARD bool grow()
Grow hashtable capacity.
HashmapNode::HashmapNodeData * nextof(HashmapNode::HashmapNodeData *node) const
Get hashmap node next to given one.
HashmapNode::HashmapNodeData * find_node(hashsum_t hash, const void *key, key_equals_callback callback) const
Find node in the hashmap.
bool contains(const HashmapNode::HashmapNodeData *node) const
Check if node belongs to hashmap.
~HashmapImpl()
Deinitialize.
HashmapNode::HashmapNodeData * back() const
Get last node in hashmap.
bool(* key_equals_callback)(HashmapNode::HashmapNodeData *node, const void *key)
Callback function pointer type for key equality check.
Definition: hashmap_impl.h:45
size_t capacity() const
Get maximum number of nodes that can be added to hashmap before grow() should be called.
Memory arena interface.
Definition: iarena.h:23
Hashmap node.
Hash sum.
Memory arena interface.
Helper macros.
size_t hashsum_t
Hash type.
Definition: hashsum.h:21
Root namespace.
Non-copyable object.
Ownership policies.
Panic.
Commonly used types and functions.
HashmapNode::HashmapNodeData * head
Pointer to head node.
Definition: hashmap_impl.h:41