hash_map.inl - Engine C API Reference

hash_map.inl
  1. namespace stingray_plugin_foundation {
  4. template <class K, class D, class H, class E>
  5. HashMap<K,D,H,E>::HashMap(Allocator &a) : _data(), _used(0), _buckets(0),
  6.     _spill_unused(0), _spill_freelist(END_OF_FREELIST), _allocator(a)
  7. {
  8. }
  10. template <class K, class D, class H, class E>
  11. HashMap<K,D,H,E>::HashMap(unsigned buckets, unsigned spill, Allocator &a) :
  12.     _data(), _used(0), _buckets(buckets), _spill_unused(spill), _spill_freelist(END_OF_FREELIST)
  13.     , _allocator(a)
  14. {
  15.     allocate_data(buckets + spill);
  16.     for (unsigned i=0; i<_data.size; ++i)
  17.         _data.marker[i] = UNUSED;
  18. }
  20. template <class K, class D, class H, class E>
  21. HashMap<K,D,H,E>::HashMap(const HashMap<K,D,H,E> &o) :
  22.     _hash(o._hash), _equal(o._equal),
  23.     _data(), _used(o._used), _buckets(o._buckets),
  24.     _spill_unused(o._spill_unused), _spill_freelist(o._spill_freelist),
  25.     _allocator(o._allocator)
  26. {
  27.     allocate_data(o._data.size);
  28.     for (unsigned i = 0; i < _data.size; ++i) {
  29.         if (o._data.marker[i] != UNUSED && (o._data.marker[i] & 0x80000000) == 0) {
  30.             construct(_data.value[i]);
  31.             _data.value[i] = o._data.value[i];
  32.         }
  33.         _data.marker[i] = o._data.marker[i];
  34.     }
  35. }
  37. template <class K, class D, class H, class E>
  38. void HashMap<K,D,H,E>::operator=(const HashMap<K,D,H,E> &o)
  39. {
  40.     if (this == &o)
  41.         return;
  42.     clear();
  43.     _hash = o._hash;
  44.     _equal = o._equal;
  45.     _allocator.deallocate(_data.marker);
  46.     _data.marker = nullptr;
  47.     allocate_data(o._data.size);
  48.     for (unsigned i = 0; i < _data.size; ++i) {
  49.         if (o._data.marker[i] != UNUSED && (o._data.marker[i] & 0x80000000) == 0) {
  50.             construct(_data.value[i]);
  51.             _data.value[i] = o._data.value[i];
  52.         }
  53.         _data.marker[i] = o._data.marker[i];
  54.     }
  55.     _used = o._used;
  56.     _buckets = o._buckets;
  57.     _spill_unused = o._spill_unused;
  58.     _spill_freelist = o._spill_freelist;
  59. }
  61. template <class K, class D, class H, class E>
  62. HashMap<K, D, H, E>::~HashMap()
  63. {
  64.     clear();
  65.     _allocator.deallocate(_data.marker);
  66. }
  68. template <class K, class D, class H, class E>
  69. void HashMap<K,D,H,E>::swap(HashMap<K,D,H,E> &o)
  70. {
  71.     XENSURE(&_allocator == &o._allocator);
  72.     std::swap(_hash, o._hash);
  73.     std::swap(_equal, o._equal);
  74.     std::swap(_data.size, o._data.size);
  75.     std::swap(_data.marker, o._data.marker);
  76.     std::swap(_data.value, o._data.value);
  77.     std::swap(_used, o._used);
  78.     std::swap(_buckets, o._buckets);
  79.     std::swap(_spill_unused, o._spill_unused);
  80.     std::swap(_spill_freelist, o._spill_freelist);
  81. }
  83. template <class K, class D, class H, class E>
  84. typename HashMap<K,D,H,E>::iterator HashMap<K,D,H,E>::begin()
  85. {
  86.     return iterator(*this, 0);
  87. }
  89. template <class K, class D, class H, class E>
  90. typename HashMap<K,D,H,E>::iterator HashMap<K,D,H,E>::end()
  91. {
  92.     return iterator(*this, num_buckets());
  93. }
  95. template <class K, class D, class H, class E>
  96. typename HashMap<K,D,H,E>::const_iterator HashMap<K,D,H,E>::begin() const
  97. {
  98.     return const_iterator(*this, 0);
  99. }
  101. template <class K, class D, class H, class E>
  102. typename HashMap<K,D,H,E>::const_iterator HashMap<K,D,H,E>::end() const
  103. {
  104.     return const_iterator(*this, num_buckets());
  105. }
  107. template <class K, class D, class H, class E> template <class KEY_EQ>
  108. typename HashMap<K,D,H,E>::const_iterator HashMap<K,D,H,E>::find(const KEY_EQ &k) const{
  109.     auto i = find_or_fail(k);
  110.     return (i == END_OF_LIST) ? end() : const_iterator(*this, i);
  111. }
  113. template <class K, class D, class H, class E> template <class KEY_EQ>
  114. typename HashMap<K,D,H,E>::iterator HashMap<K,D,H,E>::find(const KEY_EQ &k){
  115.     auto i = find_or_fail(k);
  116.     return (i == END_OF_LIST) ? end() : iterator(*this, i);
  117. }
  119. template <class K, class D, class H, class E>
  120. Allocator & HashMap<K,D,H,E>::allocator() const
  121. {
  122.     return _allocator;
  123. }
  125. template <class K, class D, class H, class E>
  126. unsigned HashMap<K,D,H,E>::size() const
  127. {
  128.     return _used;
  129. }
  131. template <class K, class D, class H, class E>
  132. bool HashMap<K,D,H,E>::empty() const
  133. {
  134.     return _used == 0;
  135. }
  137. template <class K, class D, class H, class E> template <class KEY_EQ>
  138. bool HashMap<K,D,H,E>::has(const KEY_EQ &k) const
  139. {
  140.     return find_or_fail(k) != END_OF_LIST;
  141. }
  143. template <class K, class D, class H, class E> template <class KEY_EQ>
  144. typename HashMap<K,D,H,E>::data_type &HashMap<K,D,H,E>::operator[](const KEY_EQ &k)
  145. {
  146.     if (full()) {
  147.         unsigned i = find_or_fail(k);
  148.         if (i != END_OF_LIST)
  149.             return _data.value[i].second;
  150.         grow();
  151.     }
  152.     return _data.value[find_or_make(k)].second;
  153. }
  155. template <class K, class D, class H, class E> template <class KEY_EQ>
  156. typename HashMap<K, D, H, E>::value_type &HashMap<K, D, H, E>::get_pair(const KEY_EQ &k)
  157. {
  158.     if (full()) {
  159.         unsigned i = find_or_fail(k);
  160.         if (i != END_OF_LIST)
  161.             return _data.value[i];
  162.         grow();
  163.     }
  164.     return _data.value[find_or_make(k)];
  165. }
  167. template <class K, class D, class H, class E> template <class KEY_EQ>
  168. const typename HashMap<K,D,H,E>::data_type &HashMap<K,D,H,E>::operator[](const KEY_EQ &k) const
  169. {
  170.     unsigned i = find_or_fail(k);
  171.     XASSERT(i != END_OF_LIST, "key not in map");
  172.     return _data.value[i].second;
  173. }
  175. template <class K, class D, class H, class E> template <class KEY_EQ>
  176. typename HashMap<K,D,H,E>::data_type &HashMap<K,D,H,E>::get(const KEY_EQ &k, data_type &def)
  177. {
  178.     unsigned i = find_or_fail(k);
  179.     if (i == END_OF_LIST)
  180.         return def;
  181.     else
  182.         return _data.value[i].second;
  183. }
  185. template <class K, class D, class H, class E> template <class KEY_EQ>
  186. const typename HashMap<K,D,H,E>::data_type &HashMap<K,D,H,E>::get(const KEY_EQ &k, const data_type &def) const
  187. {
  188.     unsigned i = find_or_fail(k);
  189.     if (i == END_OF_LIST)
  190.         return def;
  191.     else
  192.         return _data.value[i].second;
  193. }
  195. template <class K, class D, class H, class E>
  196. void HashMap<K,D,H,E>::clear()
  197. {
  198.     _used = 0;
  199.     _spill_freelist = END_OF_FREELIST;
  200.     _spill_unused = _data.size - _buckets;
  201.     for (unsigned i=0; i<_data.size; ++i) {
  202.         if (bucket_valid(i))
  203.             destruct(_data.value[i]);
  204.         _data.marker[i] = UNUSED;
  205.     }
  206. }
  208. template <class K, class D, class H, class E> template <class KEY_EQ, class DATA_EQ>
  209. void HashMap<K,D,H,E>::insert(const KEY_EQ &k, const DATA_EQ &v)
  210. {
  211.     (*this)[k] = v;
  212. }
  214. template <class K, class D, class H, class E> template <class KEY_EQ>
  215. void HashMap<K,D,H,E>::erase(const KEY_EQ &k)
  216. {
  217.     find_and_erase(k);
  218. }
  220. template <class K, class D, class H, class E>
  221. void HashMap<K,D,H,E>::rehash(unsigned new_buckets)
  222. {
  223.     XENSURE(new_buckets >= _used);
  224.     clear_freelist();
  225.     unsigned spill = int(new_buckets * 0.37f + 1);
  226.     unsigned old_size = _data.size;
  227.     if (_data.size == 0) {
  228.         allocate_data(new_buckets + spill);
  229.         _buckets = new_buckets;
  230.         _spill_unused = spill;
  231.         for (unsigned i = 0; i<_data.size; ++i)
  232.             _data.marker[i] = UNUSED;
  233.         return;
  234.     }
  235.     this_type new_hash(new_buckets, spill, _allocator);
  236.     for (unsigned o=0; o<old_size; ++o) {
  237.         if (_data.marker[o] == UNUSED) {
  238.             continue;
  239.         }
  240.         // Find/allocate entry
  241.         auto &k = _data.value[o].first;
  242.         auto &d = _data.value[o].second;
  243.         unsigned i = new_hash.hash(k);
  244.         if (new_hash._data.marker[i] == UNUSED) {
  245.             new_hash._data.marker[i] = END_OF_LIST;
  246.             ++new_hash._used;
  247.         }
  248.         else {
  249.             // Walk the hash chain until the end and add a new entry
  250.             while (new_hash._data.marker[i] != END_OF_LIST)
  251.                 i = new_hash._data.marker[i];
  253.             unsigned j = new_hash.allocate_spill();
  254.             new_hash._data.marker[i] = j;
  255.             i = j;
  256.             new_hash._data.marker[i] = END_OF_LIST;
  257.         }
  258.         memmove(&new_hash._data.value[i].first, &k, sizeof(K));
  259.         memmove(&new_hash._data.value[i].second, &d, sizeof(D));
  260.         _data.marker[o] = UNUSED;
  261.     }
  262.     swap(new_hash);
  263. }
  265. template <class K, class D, class H, class E>
  266. void HashMap<K,D,H,E>::reserve(unsigned items)
  267. {
  268.     unsigned buckets = int(items * 1.37f);
  269.     if (buckets < 26)
  270.         buckets = 26;
  271.     rehash(buckets);
  272. }
  274. template <class K, class D, class H, class E>
  275. unsigned HashMap<K,D,H,E>::num_buckets() const
  276. {
  277.     return _data.size;
  278. }
  280. template <class K, class D, class H, class E>
  281. bool HashMap<K,D,H,E>::bucket_valid(unsigned i) const
  282. {
  283.     return (_data.marker[i] & 0x80000000) == 0;
  284. }
  286. template <class K, class D, class H, class E>
  287. typename HashMap<K,D,H,E>::value_type &HashMap<K,D,H,E>::bucket_value(unsigned i)
  288. {
  289.     return _data.value[i];
  290. }
  292. template <class K, class D, class H, class E>
  293. const typename HashMap<K,D,H,E>::value_type &HashMap<K,D,H,E>::bucket_value(unsigned i) const
  294. {
  295.     return _data.value[i];
  296. }
  298. // Searches for `k` in the map. Returns the index of the entry if found and
  299. // END_OF_LIST if not found.
  300. template <class K, class D, class H, class E> template <class KEY_EQ>
  301. unsigned HashMap<K,D,H,E>::find_or_fail(const KEY_EQ &k) const
  302. {
  303.     // Is hash empty?
  304.     if (empty())
  305.         return END_OF_LIST;
  307.     unsigned i = hash(k);
  309.     // Is primary slot unused?
  310.     if (_data.marker[i] == UNUSED)
  311.         return END_OF_LIST;
  313.     // Walk the hash chain until key matches or end is reached.
  314.     while (true) {
  315.         if (i == END_OF_LIST || _equal(k, _data.value[i].first))
  316.             return i;
  317.         i = _data.marker[i];
  318.     }
  319. }
  321. // Searches for `k` in the map. Returns the index if it is found. If it is
  322. // not found a new hash slot is create for `k` and its index is returned.
  323. template <class K, class D, class H, class E> template <class KEY_EQ>
  324. unsigned HashMap<K,D,H,E>::find_or_make(const KEY_EQ &k)
  325. {
  326.     unsigned i = hash(k);
  328.     // Is primary slot unused?
  329.     if (_data.marker[i] == UNUSED) {
  330.         ++_used;
  331.         construct(_data.value[i]);
  332.         _data.value[i].first = k;
  333.         _data.marker[i] = END_OF_LIST;
  334.         return i;
  335.     }
  337.     while (true) {
  338.         // Walk the hash chain until found
  339.         if (_equal(k, _data.value[i].first) )
  340.             return i;
  342.         // Or until end of hash chain, in which case we add a new entry
  343.         // to the end.
  344.         if (_data.marker[i] == END_OF_LIST) {
  345.             unsigned j = allocate_spill();
  346.             _data.marker[i] = j;
  347.             i = j;
  348.             construct(_data.value[i]);
  349.             _data.value[i].first = k;
  350.             _data.marker[i] = END_OF_LIST;
  351.             return i;
  352.         }
  354.         i = _data.marker[i];
  355.     }
  356. }
  358. // Searches for `k` in the map. If it is found, it is erased.
  359. template <class K, class D, class H, class E> template <class KEY_EQ>
  360. void HashMap<K,D,H,E>::find_and_erase(const KEY_EQ &k)
  361. {
  362.     // early out to avoid division by zero in hash method if the map is empty.
  363.     if (_buckets == 0)
  364.         return;
  366.     unsigned i = hash(k);
  368.     // Is primary slot unused?
  369.     if (_data.marker[i] == UNUSED)
  370.         return;
  372.     // Did the primary slot match?
  373.     if (_equal(k, _data.value[i].first)) {
  374.         // If there is no chain, just return the primary value
  375.         if (_data.marker[i] == END_OF_LIST) {
  376.             _data.marker[i] = UNUSED;
  377.             destruct(_data.value[i]);
  378.             --_used;
  379.         // If there is a chain, bring in the first value from the
  380.         // chain and mark it as free in the spillover region.
  381.         } else {
  382.             unsigned del = _data.marker[i];
  383.             _data.marker[i] = _data.marker[del];
  384.             _data.value[i] = _data.value[del];
  385.             destruct(_data.value[del]);
  386.             free_spill(del);
  387.         }
  388.         return;
  389.     }
  391.     // If not, search the hash chain for a match
  392.     unsigned prev = i;
  393.     while (true) {
  394.         // If there is a match remove that value from the chain and
  395.         // mark it as free in the spillover region.
  396.         if (_equal(k, _data.value[i].first) ) {
  397.             _data.marker[prev] = _data.marker[i];
  398.             destruct(_data.value[i]);
  399.             free_spill(i);
  400.             return;
  401.         }
  403.         // If end of chain was reached without finding the key just return
  404.         if (_data.marker[i] == END_OF_LIST)
  405.             return;
  407.         prev = i;
  408.         i = _data.marker[i];
  409.     }
  410. }
  412. template <class K, class D, class H, class E>
  413. bool HashMap<K,D,H,E>::full() const
  414. {
  415.     // Hash map is full when spillover region is full
  416.     return _spill_unused == 0 && _spill_freelist == END_OF_FREELIST;
  417. }
  419. template <class K, class D, class H, class E>
  420. void HashMap<K,D,H,E>::grow()
  421. {
  422.     do {
  423.         unsigned new_buckets = _buckets * 2 + 1;
  424.         if (new_buckets < 19)
  425.             new_buckets = 19;
  426.         rehash(new_buckets);
  427.     } while (full());
  428. }
  430. template <class K, class D, class H, class E> template <class KEY_EQ>
  431. unsigned HashMap<K,D,H,E>::hash(const KEY_EQ &k) const
  432. {
  433.     XENSURE(_buckets > 0);
  435.     return _hash(k) % _buckets;
  436. }
  438. // Allocate a slot in the spillover region and return it.
  439. template <class K, class D, class H, class E>
  440. unsigned HashMap<K,D,H,E>::allocate_spill()
  441. {
  442.     ++_used;
  444.     // If there spillover free list is non-empty, use its
  445.     // first item.
  446.     if (_spill_freelist != END_OF_FREELIST) {
  447.         unsigned i = _spill_freelist & 0x7fffffff;
  448.         _spill_freelist = _data.marker[i];
  449.         return i;
  450.     }
  452.     // Return the first unused item from the spillover region.
  453.     XENSURE(_spill_unused > 0);
  454.     unsigned i = _data.size - _spill_unused;
  455.     --_spill_unused;
  456.     _data.marker[i] = UNUSED;
  457.     return i;
  458. }
  460. template <class K, class D, class H, class E>
  461. void HashMap<K,D,H,E>::free_spill(unsigned i)
  462. {
  463.     // Free a spillover item by inserting it in the freelist.
  464.     --_used;
  465.     _data.marker[i] = _spill_freelist;
  466.     _spill_freelist = i | 0x80000000;
  467. }
  469. // Clears the spillover freelist (marks all items as unused).
  470. template <class K, class D, class H, class E>
  471. void HashMap<K,D,H,E>::clear_freelist()
  472. {
  473.     while (_spill_freelist != END_OF_FREELIST) {
  474.         unsigned i = _spill_freelist & 0x7fffffff;
  475.         _spill_freelist = _data.marker[i];
  476.         _data.marker[i] = UNUSED;
  477.     }
  478. }
  480. template <class K, class D, class H, class E>
  481. void HashMap<K, D, H, E>::allocate_data(unsigned count)
  482. {
  483.     XASSERT(_data.marker == nullptr, "Data must be deallocated/cleared before allocating new data");
  484.     if (count == 0) {
  485.         _data = Data();
  486.         return;
  487.     }
  489.     auto marker_size = (((sizeof(unsigned) * count) + sizeof(void*) - 1) / sizeof(void*)) * sizeof(void*);
  490.     auto value_size = sizeof(value_type) * count;
  491.     auto data_size = marker_size + value_size;
  492.     _data.marker = (unsigned*)_allocator.allocate(data_size);
  493.     _data.value = (value_type*)&(((char*)_data.marker)[marker_size]);
  494.     _data.size = count;
  495. }
  497. template<class K, class D, class H, class E>
  498. template <class STREAM> void HashMap<K,D,H,E>::serialize(STREAM &stream)
  499. {
  500.     unsigned n = size();
  501.     stream & n;
  502.     if (stream.is_output()) {
  503.         iterator it(this->begin());
  504.         iterator end(this->end());
  505.         for (; it != end; ++it)
  506.             stream & (*it);
  507.     } else {
  508.         reserve(n);
  509.         for (unsigned i=0; i<n; ++i) {
  510.             value_type v(_allocator);
  511.             stream & v;
  512.             insert(v.first, v.second);
  513.         }
  514.     }
  516. }
  518. } // namespace stingray_plugin_foundation
Please send us your comment about this page