12 #ifndef ROC_CORE_HASHMAP_H_
13 #define ROC_CORE_HASHMAP_H_
81 size_t EmbeddedCapacity = 0,
82 template <
class TT>
class OwnershipPolicy = RefCountedOwnership>
88 typedef typename OwnershipPolicy<T>::Pointer
Pointer;
94 : impl_(embedded_buckets_.memory(), NumEmbeddedBuckets, NULL) {
101 : impl_(embedded_buckets_.memory(), NumEmbeddedBuckets, &arena) {
108 while (node != NULL) {
110 T* elem = container_of_(node);
111 OwnershipPolicy<T>::release(*elem);
112 node = impl_.
front();
156 hash, (
const void*)&key,
161 return container_of_(node);
173 return container_of_(node);
185 return container_of_(node);
203 return container_of_(next_node);
230 if (!insert_(element.key(), node)) {
233 OwnershipPolicy<T>::acquire(element);
252 impl_.
remove(node,
false);
253 OwnershipPolicy<T>::release(element);
279 NumEmbeddedBuckets = ((int)(EmbeddedCapacity == 0 ? 0
280 : EmbeddedCapacity <= 16 ? 16
282 * HashmapImpl::LoadFactorDen
283 + HashmapImpl::LoadFactorNum - 1)
284 / HashmapImpl::LoadFactorNum * 2
287 static T* container_of_(HashmapNode::HashmapNodeData* data) {
288 return static_cast<T*
>(data->container_of());
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);
299 bool insert_(
const Key& key, HashmapNode::HashmapNodeData* node) {
302 node, hash, (
const void*)&key,
303 &Hashmap<T, EmbeddedCapacity, OwnershipPolicy>::key_equal_<Key>);
306 AlignedStorage<NumEmbeddedBuckets *
sizeof(HashmapImpl::Bucket)> embedded_buckets_;
#define ROC_ATTR_NODISCARD
Emit warning if function result is not checked.
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 * 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.
ROC_ATTR_NODISCARD bool grow()
Grow hashtable capacity.
bool contains(const HashmapNode::HashmapNodeData *node) const
Check if node belongs to hashmap.
HashmapNode::HashmapNodeData * front() const
Get first node in 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.
Pointer back() const
Get last element in hashmap. Elements are ordered by insertion.
Hashmap()
Initialize empty hashmap without arena.
size_t size() const
Get number of elements added to hashmap.
~Hashmap()
Release ownership of all elements.
ROC_ATTR_NODISCARD bool grow()
Grow hashtable capacity.
Hashmap(IArena &arena)
Initialize empty hashmap with arena.
void remove(T &element)
Remove element from hashmap.
bool contains(const T &element) const
Check if element belongs to hashmap.
OwnershipPolicy< T >::Pointer Pointer
Pointer type.
bool is_empty() const
Check if size is zero.
Pointer front() const
Get first element in hashmap. Elements are ordered by insertion.
ROC_ATTR_NODISCARD bool insert(T &element)
Insert element into hashmap.
size_t capacity() const
Get maximum number of elements that can be added to hashmap before grow() should be called.
Pointer nextof(T &element) const
Get hashmap element next to given one. Elements are ordered by insertion.
Pointer find(const Key &key) const
Find element in the hashmap by key.
Base class for non-copyable objects.
Intrusive hash table implementation file.
size_t hashsum_t
Hash type.
Commonly used types and functions.