Roc Toolkit internal modules
Roc Toolkit: real-time audio streaming
Loading...
Searching...
No Matches
hashmap.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.h
10//! @brief Intrusive hash table.
11
12#ifndef ROC_CORE_HASHMAP_H_
13#define ROC_CORE_HASHMAP_H_
14
16#include "roc_core/attributes.h"
19#include "roc_core/hashsum.h"
20#include "roc_core/iarena.h"
24#include "roc_core/panic.h"
25#include "roc_core/stddefs.h"
26
27namespace roc {
28namespace core {
29
30//! Intrusive hash table.
31//!
32//! Characteristics:
33//! 1) Intrusive. Hash table nodes are stored directly in elements. No allocations
34//! are needed to insert a node. Arena is used only to allocate an array
35//! of buckets.
36//! 2) Collision-chaining. Implemented as an array of buckets, where a bucket is
37//! the head of a doubly-linked lists of bucket elements.
38//! 3) Controllable allocations. Allocations and deallocations are performed only
39//! when the hash table is explicitly growed. All other operations don't touch
40//! arena.
41//! 4) Zero allocations for small hash tables. A fixed number of buckets can be
42//! embedded directly into hash table object.
43//! 5) Incremental rehashing. After hash table growth, rehashing is performed
44//! incrementally when inserting and removing elements. The slower hash table
45//! size growth is, the less overhead rehashing adds to each operation.
46//! 6) Allows to iterate elements in insertion order. Implements safe iteration with
47//! regards to element insertion and deletion. Elements deleted during iteration
48//! won't be visited. Elements inserted during iteration will be visited.
49//!
50//! Incremental rehashing technique is inspired by Go's map implementation, though
51//! there are differences. Load factor value is taken from it as well.
52//! Prime numbers for sizes are from https://planetmath.org/goodhashtableprimes.
53//!
54//! @tparam T defines object type, it should inherit HashmapNode and additionally
55//! implement three methods:
56//!
57//! @code
58//! // get object key
59//! Key key() const;
60//!
61//! // compute key hash
62//! static core::hashsum_t key_hash(Key key);
63//!
64//! // compare two keys for equality
65//! static bool key_equal(Key key1, Key key2);
66//! @endcode
67//!
68//! "Key" can be any type. Hashmap doesn't use it directly. It is never stored and
69//! is always accessed via the three methods above. The hash is computed for a key
70//! only once when an object is inserted into hash table.
71//!
72//! @tparam EmbeddedCapacity defines the capacity embedded directly into Hashmap.
73//! It is used instead of dynamic memory while the number of elements is smaller
74//! than this capacity. The actual object size occupied to provide the requested
75//! capacity is implementation defined.
76//!
77//! @tparam OwnershipPolicy defines ownership policy which is used to acquire an element
78//! ownership when it's added to the hashmap and release ownership when it's removed
79//! from the hashmap.
80template <class T,
81 size_t EmbeddedCapacity = 0,
82 template <class TT> class OwnershipPolicy = RefCountedOwnership>
83class Hashmap : public NonCopyable<> {
84public:
85 //! Pointer type.
86 //! @remarks
87 //! either raw or smart pointer depending on the ownership policy.
89
90 //! Initialize empty hashmap without arena.
91 //! @remarks
92 //! Hashmap capacity will be limited to the embedded capacity.
94 : impl_(embedded_buckets_.memory(), NumEmbeddedBuckets, NULL) {
95 }
96
97 //! Initialize empty hashmap with arena.
98 //! @remarks
99 //! Hashmap capacity may grow using arena.
100 explicit Hashmap(IArena& arena)
101 : impl_(embedded_buckets_.memory(), NumEmbeddedBuckets, &arena) {
102 }
103
104 //! Release ownership of all elements.
106 HashmapNode::HashmapNodeData* node = impl_.front();
107
108 while (node != NULL) {
109 impl_.remove(node, true);
110 T* elem = container_of_(node);
112 node = impl_.front();
113 }
114 }
115
116 //! Get maximum number of elements that can be added to hashmap before
117 //! grow() should be called.
118 size_t capacity() const {
119 return impl_.capacity();
120 }
121
122 //! Get number of elements added to hashmap.
123 size_t size() const {
124 return impl_.size();
125 }
126
127 //! Check if size is zero.
128 bool is_empty() const {
129 return size() == 0;
130 }
131
132 //! Check if element belongs to hashmap.
133 //!
134 //! @note
135 //! - has O(1) complexity
136 //! - doesn't compute key hashes
137 bool contains(const T& element) const {
138 const HashmapNode::HashmapNodeData* node = element.hashmap_node_data();
139 return impl_.contains(node);
140 }
141
142 //! Find element in the hashmap by key.
143 //!
144 //! @returns
145 //! Pointer to the element with given key or NULL if it's not found.
146 //!
147 //! @note
148 //! - has O(1) complexity in average and O(n) in the worst case
149 //! - computes key hash
150 //!
151 //! @note
152 //! The worst case is achieved when the hash function produces many collisions.
153 template <class Key> Pointer find(const Key& key) const {
154 const hashsum_t hash = T::key_hash(key);
156 hash, (const void*)&key,
158 if (!node) {
159 return NULL;
160 }
161 return container_of_(node);
162 }
163
164 //! Get first element in hashmap.
165 //! Elements are ordered by insertion.
166 //! @returns
167 //! first element or NULL if hashmap is empty.
168 Pointer front() const {
169 HashmapNode::HashmapNodeData* node = impl_.front();
170 if (!node) {
171 return NULL;
172 }
173 return container_of_(node);
174 }
175
176 //! Get last element in hashmap.
177 //! Elements are ordered by insertion.
178 //! @returns
179 //! last element or NULL if hashmap is empty.
180 Pointer back() const {
181 HashmapNode::HashmapNodeData* node = impl_.back();
182 if (!node) {
183 return NULL;
184 }
185 return container_of_(node);
186 }
187
188 //! Get hashmap element next to given one.
189 //! Elements are ordered by insertion.
190 //!
191 //! @returns
192 //! hashmap element following @p element if @p element is not
193 //! last, or NULL otherwise.
194 //!
195 //! @pre
196 //! @p element should be member of this hashmap.
198 HashmapNode::HashmapNodeData* node = element.hashmap_node_data();
200 if (!next_node) {
201 return NULL;
202 }
203 return container_of_(next_node);
204 }
205
206 //! Insert element into hashmap.
207 //!
208 //! @remarks
209 //! - acquires ownership of @p element
210 //!
211 //! @returns
212 //! false if the allocation failed
213 //!
214 //! @pre
215 //! - @p element should not be member of any hashmap
216 //! - hashmap shouldn't have an element with the same key
217 //!
218 //! @note
219 //! - has O(1) complexity in average and O(n) in the worst case
220 //! - computes key hash
221 //! - doesn't make allocations or deallocations
222 //! - proceedes lazy rehashing
223 //!
224 //! @note
225 //! Insertion speed is higher when insert to remove ratio is close to one or lower,
226 //! and slows down when it becomes higher than one. The slow down is caused by
227 //! the incremental rehashing algorithm.
229 HashmapNode::HashmapNodeData* node = element.hashmap_node_data();
230 if (!insert_(element.key(), node)) {
231 return false;
232 }
234 return true;
235 }
236
237 //! Remove element from hashmap.
238 //!
239 //! @remarks
240 //! - releases ownership of @p element
241 //!
242 //! @pre
243 //! @p element should be member of this hashmap.
244 //!
245 //! @note
246 //! - has O(1) complexity
247 //! - doesn't compute key hash
248 //! - doesn't make allocations or deallocations
249 //! - proceedes lazy rehashing
250 void remove(T& element) {
251 HashmapNode::HashmapNodeData* node = element.hashmap_node_data();
252 impl_.remove(node, false);
254 }
255
256 //! Grow hashtable capacity.
257 //!
258 //! @remarks
259 //! Check if hash table is full (size is equal to capacity), and if so, increase
260 //! hash table capacity and initiate incremental rehashing. Rehashing will be
261 //! performed during subsequent insertions and removals.
262 //!
263 //! @returns
264 //! - true if no growth needed or growth succeeded
265 //! - false if allocation failed
266 //!
267 //! @note
268 //! - has O(1) complexity
269 //! - doesn't computes key hashes
270 //! - makes allocations and deallocations
271 //! - doesn't proceed lazy rehashing
273 return impl_.grow();
274 }
275
276private:
277 enum {
278 // how much buckets are embeded directly into Hashmap object
279 NumEmbeddedBuckets = ((int)(EmbeddedCapacity == 0 ? 0
280 : EmbeddedCapacity <= 16 ? 16
282 * HashmapImpl::LoadFactorDen
283 + HashmapImpl::LoadFactorNum - 1)
284 / HashmapImpl::LoadFactorNum * 2
285 };
286
287 static T* container_of_(HashmapNode::HashmapNodeData* data) {
288 return static_cast<T*>(data->container_of());
289 }
290
291 template <class Key>
292 static bool key_equal_(HashmapNode::HashmapNodeData* node, const void* key) {
293 T* elem = container_of_(node);
294 const Key& key_ref = *(const Key*)key;
295 return T::key_equal(elem->key(), key_ref);
296 }
297
298 template <class Key>
299 bool insert_(const Key& key, HashmapNode::HashmapNodeData* node) {
300 const hashsum_t hash = T::key_hash(key);
301 return impl_.insert(
302 node, hash, (const void*)&key,
303 &Hashmap<T, EmbeddedCapacity, OwnershipPolicy>::key_equal_<Key>);
304 }
305
306 AlignedStorage<NumEmbeddedBuckets * sizeof(HashmapImpl::Bucket)> embedded_buckets_;
307
308 HashmapImpl impl_;
309};
310
311} // namespace core
312} // namespace roc
313
314#endif // ROC_CORE_HASHMAP_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.
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.
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.
HashmapNode::HashmapNodeData * back() const
Get last node in hashmap.
size_t capacity() const
Get maximum number of nodes that can be added to hashmap before grow() should be called.
Intrusive hash table.
Definition hashmap.h:83
Pointer back() const
Get last element in hashmap. Elements are ordered by insertion.
Definition hashmap.h:180
Hashmap()
Initialize empty hashmap without arena.
Definition hashmap.h:93
size_t size() const
Get number of elements added to hashmap.
Definition hashmap.h:123
~Hashmap()
Release ownership of all elements.
Definition hashmap.h:105
ROC_ATTR_NODISCARD bool grow()
Grow hashtable capacity.
Definition hashmap.h:272
Hashmap(IArena &arena)
Initialize empty hashmap with arena.
Definition hashmap.h:100
void remove(T &element)
Remove element from hashmap.
Definition hashmap.h:250
bool contains(const T &element) const
Check if element belongs to hashmap.
Definition hashmap.h:137
OwnershipPolicy< T >::Pointer Pointer
Pointer type.
Definition hashmap.h:88
bool is_empty() const
Check if size is zero.
Definition hashmap.h:128
Pointer front() const
Get first element in hashmap. Elements are ordered by insertion.
Definition hashmap.h:168
ROC_ATTR_NODISCARD bool insert(T &element)
Insert element into hashmap.
Definition hashmap.h:228
size_t capacity() const
Get maximum number of elements that can be added to hashmap before grow() should be called.
Definition hashmap.h:118
Pointer nextof(T &element) const
Get hashmap element next to given one. Elements are ordered by insertion.
Definition hashmap.h:197
Pointer find(const Key &key) const
Find element in the hashmap by key.
Definition hashmap.h:153
Memory arena interface.
Definition iarena.h:23
Base class for non-copyable objects.
Definition noncopyable.h:23
Shared ownership intrusive pointer.
Definition shared_ptr.h:32
Intrusive hash table implementation file.
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 * container_of()
Get HashmapNode object that contains this HashmapData object.