1 #ifndef RDESTL_HASH_MAP_H 2 #define RDESTL_HASH_MAP_H 4 #include <stk_util/util/algorithm_rdestl.h> 5 #include <stk_util/util/allocator_rdestl.h> 6 #include <stk_util/util/functional_rdestl.h> 7 #include <stk_util/util/hash_rdestl.h> 8 #include <stk_util/util/pair_rdestl.h> 17 template<
typename TKey,
typename TValue,
18 class THashFunc = rde::hash<TKey>,
20 class TKeyEqualFunc = rde::equal_to<TKey>,
21 class TAllocator = rde::allocator>
25 typedef rde::pair<TKey, TValue> value_type;
30 static const hash_value_t kUnusedHash = 0xFFFFFFFF;
31 static const hash_value_t kDeletedHash = 0xFFFFFFFE;
33 node(): hash(kUnusedHash) {}
35 RDE_FORCEINLINE
bool is_unused()
const {
return hash == kUnusedHash; }
36 RDE_FORCEINLINE
bool is_deleted()
const {
return hash == kDeletedHash; }
37 RDE_FORCEINLINE
bool is_occupied()
const {
return hash < kDeletedHash; }
42 template<
typename TNodePtr,
typename TPtr,
typename TRef>
45 friend class hash_map;
47 typedef forward_iterator_tag iterator_category;
49 explicit node_iterator(TNodePtr node,
const hash_map* map)
53 template<
typename UNodePtr,
typename UPtr,
typename URef>
54 node_iterator(
const node_iterator<UNodePtr, UPtr, URef>& rhs)
59 TRef operator*()
const 61 RDE_ASSERT(m_node != 0);
64 TPtr operator->()
const 68 RDE_FORCEINLINE TNodePtr node()
const 73 node_iterator& operator++()
75 RDE_ASSERT(m_node != 0);
77 move_to_next_occupied_node();
80 node_iterator operator++(
int)
82 node_iterator
copy(*
this);
87 RDE_FORCEINLINE
bool operator==(
const node_iterator& rhs)
const 89 return rhs.m_node == m_node;
91 bool operator!=(
const node_iterator& rhs)
const 93 return !(rhs == *
this);
96 const hash_map* get_map()
const {
return m_map; }
98 void move_to_next_occupied_node()
101 TNodePtr nodeEnd = m_map->m_nodes + m_map->bucket_count();
102 for (; m_node < nodeEnd; ++m_node)
104 if (m_node->is_occupied())
109 const hash_map* m_map;
113 typedef TKey key_type;
114 typedef TValue mapped_type;
115 typedef TAllocator allocator_type;
116 typedef node_iterator<node*, value_type*, value_type&> iterator;
117 typedef node_iterator<const node*, const value_type*, const value_type&> const_iterator;
118 typedef int size_type;
119 static const size_type kNodeSize =
sizeof(node);
120 static const size_type kInitialCapacity = 64;
123 : m_nodes(&ms_emptyNode),
129 RDE_ASSERT((kInitialCapacity & (kInitialCapacity - 1)) == 0);
131 explicit hash_map(
const allocator_type& allocator)
132 : m_nodes(&ms_emptyNode),
137 m_allocator(allocator)
141 explicit hash_map(size_type initial_bucket_count,
142 const allocator_type& allocator = allocator_type())
143 : m_nodes(&ms_emptyNode),
148 m_allocator(allocator)
150 reserve(initial_bucket_count);
152 hash_map(size_type initial_bucket_count,
153 const THashFunc& hashFunc,
154 const allocator_type& allocator = allocator_type())
155 : m_nodes(&ms_emptyNode),
160 m_hashFunc(hashFunc),
161 m_allocator(allocator)
163 reserve(initial_bucket_count);
165 hash_map(
const hash_map& rhs,
const allocator_type& allocator = allocator_type())
166 : m_nodes(&ms_emptyNode),
171 m_allocator(allocator)
175 explicit hash_map(e_noinitialize)
186 iterator it(m_nodes,
this);
187 it.move_to_next_occupied_node();
190 const_iterator begin()
const 192 const_iterator it(m_nodes,
this);
193 it.move_to_next_occupied_node();
196 iterator end() {
return iterator(m_nodes + m_capacity,
this); }
197 const_iterator end()
const {
return const_iterator(m_nodes + m_capacity,
this); }
202 mapped_type& operator[](
const key_type& key)
205 node* n = find_for_insert(key, &hash);
206 if (n == 0 || !n->is_occupied())
208 return insert_at(value_type(key, TValue()), n, hash).first->second;
210 return n->data.second;
213 hash_map& operator=(
const hash_map& rhs)
215 RDE_ASSERT(invariant());
219 if (m_capacity < rhs.bucket_count())
222 m_nodes = allocate_nodes(rhs.bucket_count());
223 m_capacity = rhs.bucket_count();
224 m_capacityMask = m_capacity - 1;
226 rehash(m_capacity, m_nodes, rhs.m_capacity, rhs.m_nodes,
false);
228 m_numUsed = rhs.m_numUsed;
230 RDE_ASSERT(invariant());
233 void swap(hash_map& rhs)
237 RDE_ASSERT(invariant());
238 RDE_ASSERT(m_allocator == rhs.m_allocator);
239 rde::swap(m_nodes, rhs.m_nodes);
240 rde::swap(m_size, rhs.m_size);
241 rde::swap(m_capacity, rhs.m_capacity);
242 rde::swap(m_capacityMask, rhs.m_capacityMask);
243 rde::swap(m_numUsed, rhs.m_numUsed);
244 rde::swap(m_hashFunc, rhs.m_hashFunc);
245 rde::swap(m_keyEqualFunc, rhs.m_keyEqualFunc);
246 RDE_ASSERT(invariant());
250 rde::pair<iterator, bool>
insert(
const value_type& v)
252 typedef rde::pair<iterator, bool> ret_type_t;
253 RDE_ASSERT(invariant());
254 if (m_numUsed * TLoadFactor4 >= m_capacity * 4)
257 hash_value_t hash = 0XFFFFFFFF;
259 node* n = find_for_insert(v.first, &hash);
260 if (n->is_occupied())
262 RDE_ASSERT(hash == n->hash && m_keyEqualFunc(v.first, n->data.first));
263 return ret_type_t(iterator(n,
this),
false);
267 rde::copy_construct(&n->data, v);
270 RDE_ASSERT(invariant());
271 return ret_type_t(iterator(n,
this),
true);
274 size_type erase(
const key_type& key)
276 node* n = lookup(key);
277 if (n != (m_nodes + m_capacity) && n->is_occupied())
284 void erase(iterator it)
286 RDE_ASSERT(it.get_map() ==
this);
289 RDE_ASSERT(!empty());
290 erase_node(it.node());
293 void erase(iterator from, iterator to)
295 for (; from != to; ++from)
297 node* n = from.node();
298 if (n->is_occupied())
303 iterator
find(
const key_type& key)
305 node* n = lookup(key);
306 return iterator(n,
this);
308 const_iterator
find(
const key_type& key)
const 310 const node* n = lookup(key);
311 return const_iterator(n,
this);
316 node* endNode = m_nodes + m_capacity;
317 for (node* iter = m_nodes; iter != endNode; ++iter)
321 if (iter->is_occupied())
323 rde::destruct(&iter->data);
327 iter->hash = node::kUnusedHash;
336 void reserve(size_type min_size)
338 size_type newCapacity = (m_capacity == 0 ? kInitialCapacity : m_capacity);
339 while (newCapacity < min_size)
341 if (newCapacity > m_capacity)
345 size_type bucket_count()
const {
return m_capacity; }
346 size_type size()
const {
return m_size; }
347 size_type empty()
const {
return size() == 0; }
348 size_type nonempty_bucket_count()
const {
return m_numUsed; }
349 size_type used_memory()
const 351 return bucket_count() * kNodeSize;
354 const allocator_type& get_allocator()
const {
return m_allocator; }
355 void set_allocator(
const allocator_type& allocator)
357 m_allocator = allocator;
363 const int newCapacity = (m_capacity == 0 ? kInitialCapacity : m_capacity * 2);
366 void grow(
int new_capacity)
368 RDE_ASSERT((new_capacity & (new_capacity - 1)) == 0);
369 node* newNodes = allocate_nodes(new_capacity);
370 rehash(new_capacity, newNodes, m_capacity, m_nodes,
true);
371 if (m_nodes != &ms_emptyNode)
372 m_allocator.deallocate(m_nodes,
sizeof(node) * m_capacity);
373 m_capacity = new_capacity;
374 m_capacityMask = new_capacity - 1;
377 RDE_ASSERT(m_numUsed < m_capacity);
379 rde::pair<iterator, bool> insert_at(
const value_type& v, node* n,
382 RDE_ASSERT(invariant());
383 if (n == 0 || m_numUsed * TLoadFactor4 >= m_capacity * 4)
386 RDE_ASSERT(!n->is_occupied());
389 rde::copy_construct(&n->data, v);
392 RDE_ASSERT(invariant());
393 return rde::pair<iterator, bool>(iterator(n,
this),
true);
395 node* find_for_insert(
const key_type& key, hash_value_t* out_hash)
400 const hash_value_t hash = hash_func(key);
402 uint32 i = hash & m_capacityMask;
404 node* n = m_nodes + i;
405 if (n->hash == hash && m_keyEqualFunc(key, n->data.first))
413 RDE_ASSERT(m_numUsed < m_capacity);
414 while (!n->is_unused())
417 i = (i + numProbes) & m_capacityMask;
419 if (compare_key(n, key, hash))
421 if (n->is_deleted() && freeNode == 0)
424 return freeNode ? freeNode : n;
426 node* lookup(
const key_type& key)
const 428 const hash_value_t hash = hash_func(key);
429 uint32 i = hash & m_capacityMask;
430 node* n = m_nodes + i;
437 if (n->hash == hash && m_keyEqualFunc(key, n->data.first))
442 RDE_ASSERT(m_capacity == 0 || m_numUsed < m_capacity);
443 while (!n->is_unused())
446 i = (i + numProbes) & m_capacityMask;
449 if (compare_key(n, key, hash))
452 return m_nodes + m_capacity;
455 static void rehash(
int new_capacity, node* new_nodes,
456 int capacity,
const node* nodes,
bool destruct_original)
461 const node* it = nodes;
462 const node* itEnd = nodes + capacity;
463 const uint32 mask = new_capacity - 1;
466 if (it->is_occupied())
468 const hash_value_t hash = it->hash;
469 uint32 i = hash & mask;
471 node* n = new_nodes + i;
473 while (!n->is_unused())
476 i = (i + numProbes) & mask;
479 rde::copy_construct(&n->data, it->data);
481 if (destruct_original)
482 rde::destruct(&it->data);
488 node* allocate_nodes(
int n)
490 node* buckets =
static_cast<node*
>(m_allocator.allocate(n *
sizeof(node)));
491 node* iterBuckets(buckets);
492 node* end = iterBuckets + n;
493 for (; iterBuckets != end; ++iterBuckets)
494 iterBuckets->hash = node::kUnusedHash;
501 node* itEnd = it + m_capacity;
504 if (it && it->is_occupied())
505 rde::destruct(&it->data);
508 if (m_nodes != &ms_emptyNode)
509 m_allocator.deallocate(m_nodes,
sizeof(node) * m_capacity);
515 void erase_node(node* n)
517 RDE_ASSERT(!empty());
518 RDE_ASSERT(n->is_occupied());
519 rde::destruct(&n->data);
520 n->hash = node::kDeletedHash;
524 RDE_FORCEINLINE hash_value_t hash_func(
const key_type& key)
const 526 const hash_value_t h = m_hashFunc(key) & 0xFFFFFFFD;
530 bool invariant()
const 532 RDE_ASSERT((m_capacity & (m_capacity - 1)) == 0);
533 RDE_ASSERT(m_numUsed >= m_size);
537 RDE_FORCEINLINE
bool compare_key(
const node* n,
const key_type& key, hash_value_t hash,
538 int_to_type<false>)
const 540 return (n->hash == hash && m_keyEqualFunc(key, n->data.first));
542 RDE_FORCEINLINE
bool compare_key(
const node* n,
const key_type& key, hash_value_t,
543 int_to_type<true>)
const 545 return m_keyEqualFunc(key, n->data.first);
547 RDE_FORCEINLINE
bool compare_key(
const node* n,
const key_type& key, hash_value_t hash)
const 549 return compare_key(n, key, hash, int_to_type<has_cheap_compare<TKey>::value>());
555 uint32 m_capacityMask;
557 THashFunc m_hashFunc;
558 TKeyEqualFunc m_keyEqualFunc;
559 TAllocator m_allocator;
561 static node ms_emptyNode;
566 template<
typename TKey,
typename TValue,
571 typename hash_map<TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator>::node hash_map<TKey, TValue, THashFunc, TLoadFactor4, TKeyEqualFunc, TAllocator>::ms_emptyNode;
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result)
Part * find(const PartVector &parts, const std::string &name)
Find a part by name in a collection of parts.
bool insert(PartVector &v, Part &part)
Insert a part into a properly ordered collection of parts. Returns true if this is a new insertion...