1 /**************************************************************************
3 * Copyright 2013-2014 RAD Game Tools and Valve Software
4 * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
7 * Permission is hereby granted, free of charge, to any person obtaining a copy
8 * of this software and associated documentation files (the "Software"), to deal
9 * in the Software without restriction, including without limitation the rights
10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11 * copies of the Software, and to permit persons to whom the Software is
12 * furnished to do so, subject to the following conditions:
14 * The above copyright notice and this permission notice shall be included in
15 * all copies or substantial portions of the Software.
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
25 **************************************************************************/
28 // See https://en.wikipedia.org/wiki/Skip_list
29 // Inspired by Qt4's QMap and http://www.keithschwarz.com/interesting/code/?dir=skiplist
32 // vogl::map is a associative container implemented using a skip-list.
33 // Its interface and performance is roughly similar to std::map, std::multi_map, std::set, and std::multi_set.
36 // insert/erase perf on int->int test containers using prob .25 vs. glibc x64 is a mixed bag:
37 // If the entire container fits into the CPU cache, this class is up to 20-50% faster.
38 // For large int->int containers, for random insertion/erases this class is 25-35% slower, but for forward/reverse insertion/erases it's around 2x faster.
41 // Always 1 malloc per vogl::map instance (for the heap node), allocated at construction time.
42 // 1 additional malloc per inserted object, objects never move, objects are always traversable in sorted order forwards or backwards in constant time per iteration.
43 // iterators remain valid after inserting/erasing.
44 // key is stored immediately before value in memory, followed by the element pointers.
45 // Sets (using an empty Value struct) aren't as efficient as they could be, because empty_struct is 1 byte which gets aligned up to 4 bytes.
46 // In debug builds each node has a 16-bit marker to detect bogus iterators/overruns/etc.
48 // Duplicate key behavior:
49 // - find() always finds the first key in a run of duplicate keys.
50 // - insert() never overwrites duplicate keys.
51 // - insert_multi() always inserts before the first key in a run of duplicate keys (i.e. duplicate keys are ordered by how recently they are inserted).
52 // - erase() by key always erases the first key in a run of duplicate keys
53 // - erase() by iterator may be slow within very large runs of duplicate keys.
55 // By default, the container will automatically nudge up the max pointer level as it grows, unless the fixed max level is enabled (not recommended).
56 // The max pointer level is never reduced, even after calling clear(). Use reset() instead if this is important.
57 // This implementation is hard coded to use a list level probability of 1/4. A max pointer level of 8 should be reasonable for 64k elements.
58 // Each container uses its own 32-bit PRNG with a constant seed.
60 // Item memory overhead: ~13 bytes avg overhead in 32-bit builds, ~26 bytes for 64-bit builds.
61 // Min overhead is sizeof(uint32)+sizeof(void*)*2 per element.
65 #include "vogl_core.h"
66 #include "vogl_rand.h"
67 #include "vogl_vector.h"
68 #include "vogl_console.h"
70 // If VOGL_MAP_USE_POINT_25_PROB is 1, the skip list uses prob = .25, otherwise it uses .5
71 #define VOGL_MAP_USE_POINT_25_PROB 1
77 cMapNodeHeadDebugMarker = 0xE138,
78 cMapListNodeItemDebugMarker = 0xE137,
79 cMapNodeFreeDebugMarker = 0xFEFE
82 template <typename Key, typename Value>
85 template <typename Key, typename Value, uint N>
88 #ifdef VOGL_ASSERTS_ENABLED
89 uint16 m_debug_marker;
92 // m_num_next_ptrs is not needed in a basic implementation, but it can simplify erasing (especially with multiple equal elements) and helps debugging.
93 uint8 m_num_next_ptrs;
95 map_node<Key, Value> *m_pPrev;
97 // m_pNext[] must be last
98 map_node<Key, Value> *m_pNext[N];
101 template <typename Key, typename Value>
102 struct map_node : std::pair<const Key, Value>
104 map_node_ptrs<Key, Value, 1> m_ptrs;
106 inline uint get_num_next_ptrs() const
108 return m_ptrs.m_num_next_ptrs;
110 inline void set_num_next_ptrs(uint n)
112 m_ptrs.m_num_next_ptrs = n;
115 inline void set_prev_ptr(map_node *pPrev)
117 m_ptrs.m_pPrev = pPrev;
119 inline map_node *get_prev_ptr() const
121 return m_ptrs.m_pPrev;
124 inline map_node *get_forward_ptr(uint index) const
126 VOGL_ASSERT(index < m_ptrs.m_num_next_ptrs);
127 return m_ptrs.m_pNext[index];
130 inline void set_forward_ptr(uint index, map_node *p)
132 VOGL_ASSERT(index < m_ptrs.m_num_next_ptrs);
133 m_ptrs.m_pNext[index] = p;
136 inline uint get_allocated_size() const
138 return sizeof(*this) + (get_num_next_ptrs() - 1) * sizeof(map_node *);
141 #ifdef VOGL_ASSERTS_ENABLED
142 inline uint16 get_debug_marker() const
144 return m_ptrs.m_debug_marker;
146 inline void set_debug_marker(uint16 val)
148 m_ptrs.m_debug_marker = val;
152 inline void check_item_debug_marker() const
154 VOGL_ASSERT(m_ptrs.m_debug_marker == cMapListNodeItemDebugMarker);
156 inline void check_head_debug_marker() const
158 VOGL_ASSERT(m_ptrs.m_debug_marker == cMapNodeHeadDebugMarker);
164 cMapMaxPossibleLevels = VOGL_MAP_USE_POINT_25_PROB ? 16 : 32
167 // Using default template options, Key must support operator <.
168 // If Key supports operator== and if operator< is complex, consider setting EqualComp to equal_to for a potential perf gain.
169 template <typename Key, typename Value = empty_type,
170 typename LessComp = less_than<Key>,
171 typename EqualComp = equal_to_using_less_than<Key>,
172 uint MaxLevels = cMapMaxPossibleLevels>
175 friend class iterator_base;
176 friend class iterator;
177 friend class const_iterator;
179 typedef map_node<const Key, Value> node_type;
182 typedef map<Key, Value, LessComp, EqualComp, MaxLevels> map_type;
183 typedef Key key_type;
184 typedef Value referent_type;
185 typedef std::pair<const Key, Value> value_type;
186 typedef LessComp less_comp_type;
187 typedef EqualComp equal_comp_type;
191 cMaxLevels = MaxLevels
194 template <typename DerivedType, typename Pointer, typename Reference>
200 template <typename DerivedType2, typename Pointer2, typename Reference2>
201 friend class iterator_base;
203 inline iterator_base()
208 inline iterator_base(node_type *pNode)
215 inline DerivedType operator++(int)
217 DerivedType result(static_cast<DerivedType &>(*this));
223 inline DerivedType &operator++()
225 VOGL_ASSERT(m_pNode);
227 m_pNode = m_pNode->get_forward_ptr(0);
228 return static_cast<DerivedType &>(*this);
232 inline DerivedType operator--(int)
234 DerivedType result(static_cast<DerivedType &>(*this));
240 inline DerivedType &operator--()
242 VOGL_ASSERT(m_pNode);
244 m_pNode = m_pNode->get_prev_ptr();
245 return static_cast<DerivedType &>(*this);
248 inline Reference operator*() const
250 VOGL_ASSERT(m_pNode);
251 VOGL_ASSERT(m_pNode->get_debug_marker() == cMapListNodeItemDebugMarker);
255 inline Pointer operator->() const
257 VOGL_ASSERT(m_pNode->get_debug_marker() == cMapListNodeItemDebugMarker);
261 template <typename DerivedType2, typename Pointer2, typename Reference2>
262 inline bool operator==(const iterator_base<DerivedType2, Pointer2, Reference2> &rhs) const
264 return (m_pNode == rhs.m_pNode);
267 template <typename DerivedType2, typename Pointer2, typename Reference2>
268 inline bool operator!=(const iterator_base<DerivedType2, Pointer2, Reference2> &rhs) const
270 return (m_pNode != rhs.m_pNode);
274 class iterator : public iterator_base<iterator, std::pair<const Key, Value> *, std::pair<const Key, Value> &>
277 friend class const_iterator;
279 inline iterator(node_type *pNode)
280 : iterator_base<iterator, std::pair<const Key, Value> *, std::pair<const Key, Value> &>(pNode)
290 class const_iterator : public iterator_base<const_iterator, const std::pair<const Key, Value> *, const std::pair<const Key, Value> &>
293 friend class iterator;
295 inline const_iterator(node_type *pNode)
296 : iterator_base<const_iterator, const std::pair<const Key, Value> *, const std::pair<const Key, Value> &>(pNode)
301 inline const_iterator()
305 inline const_iterator(iterator itr)
306 : iterator_base<const_iterator, const std::pair<const Key, Value> *, const std::pair<const Key, Value> &>(itr.m_pNode)
311 // max_level must be < MaxLevels (i.e. 15 or less with default template MaxLevels)
312 // By default the max level will automatically increase as the container grows, which leads to reasonable behavior in testing.
313 // You can fix the max level by calling set_fixed_map_level(), but use caution because if the level is too low perf will be dreadful.
322 // 6 is good enough for 1/(.25 ^ 6) = ~4k entries
330 // A decent max level ~= ceil(log(N)/log(2) * 0.5)
334 cDefaultMaxLevel = VOGL_MAP_USE_POINT_25_PROB ? 3 : 6
337 inline map(uint initial_max_level = cDefaultMaxLevel, const LessComp &less_than_obj = less_comp_type(), const EqualComp &equal_to_obj = equal_comp_type())
338 : m_total_allocated(0),
341 m_fixed_max_level(false),
342 m_is_key_less_than(less_than_obj),
343 m_is_key_equal_to(equal_to_obj)
345 init(initial_max_level);
348 inline map(const map &other)
349 : m_total_allocated(0),
352 m_rand(other.m_rand),
353 m_fixed_max_level(other.m_fixed_max_level),
354 m_is_key_less_than(other.m_is_key_less_than),
355 m_is_key_equal_to(other.m_is_key_equal_to)
360 inline map &operator=(const map &rhs)
367 m_is_key_less_than = rhs.m_is_key_less_than;
368 m_is_key_equal_to = rhs.m_is_key_equal_to;
369 m_fixed_max_level = rhs.m_fixed_max_level;
379 m_pHead->check_head_debug_marker();
381 node_type *pCur = m_pHead->get_forward_ptr(0);
382 while (pCur != m_pHead)
384 pCur->check_item_debug_marker();
385 node_type *pNext = pCur->get_forward_ptr(0);
390 #ifdef VOGL_ASSERTS_ENABLED
391 m_pHead->set_debug_marker(cMapNodeFreeDebugMarker);
397 // clear() wipes the container, but does not change the current max level
400 m_pHead->check_head_debug_marker();
402 node_type *pCur = m_pHead->get_forward_ptr(0);
403 while (pCur != m_pHead)
405 pCur->check_item_debug_marker();
407 node_type *pNext = pCur->get_forward_ptr(0);
412 VOGL_ASSERT(!m_total_allocated);
414 m_pHead->set_prev_ptr(m_pHead);
415 for (uint i = 0; i <= m_max_level; i++)
416 m_pHead->set_forward_ptr(i, m_pHead);
418 m_total_allocated = 0;
423 inline void reset(uint initial_max_level = cDefaultMaxLevel, const LessComp &less_than_obj = less_comp_type(), const EqualComp &equal_to_obj = equal_comp_type())
427 m_rand.set_default_seed();
428 m_fixed_max_level = false;
429 m_is_key_less_than = less_than_obj;
430 m_is_key_equal_to = equal_to_obj;
432 init(initial_max_level);
435 inline iterator begin()
437 m_pHead->check_head_debug_marker();
438 return iterator(m_pHead->get_forward_ptr(0));
440 inline const_iterator begin() const
442 m_pHead->check_head_debug_marker();
443 return const_iterator(m_pHead->get_forward_ptr(0));
446 inline iterator end()
448 m_pHead->check_head_debug_marker();
449 return iterator(m_pHead);
451 inline const_iterator end() const
453 m_pHead->check_head_debug_marker();
454 return const_iterator(m_pHead);
457 inline int size() const
462 inline bool is_empty() const
467 inline int64_t get_total_bytes_allocated() const
469 return m_total_allocated;
472 inline uint get_cur_list_level() const
476 inline uint get_cur_max_level() const
480 inline uint get_max_possible_level() const
482 return cMaxLevels - 1;
485 inline uint get_fixed_map_level() const
487 return m_fixed_max_level;
490 inline void set_fixed_map_level(uint level)
492 if (m_fixed_max_level)
495 m_fixed_max_level = true;
496 m_bump_max_level_size_thresh = cUINT32_MAX;
498 level = math::minimum<uint>(level, cMaxLevels - 1);
500 if (level > m_max_level)
503 m_pHead->set_num_next_ptrs(m_max_level + 1);
505 VOGL_ASSERT(m_pHead->get_forward_ptr(m_max_level) == m_pHead);
509 inline const EqualComp &get_equals() const
511 return m_is_key_equal_to;
514 inline EqualComp &get_equals()
516 return m_is_key_equal_to;
519 inline void set_equals(const EqualComp &equals)
521 m_is_key_equal_to = equals;
524 inline const LessComp &get_less() const
526 return m_is_key_less_than;
529 inline LessComp &get_less()
531 return m_is_key_less_than;
534 inline void set_less(const LessComp &less)
536 m_is_key_less_than = less;
539 inline void reserve(size_t)
544 // insert_result.first will always point to inserted key/value (or the already existing key/value).
545 // insert_result.second will be true if a new key/value was inserted, or false if the key already existed (in which case first will point to the already existing value).
546 typedef std::pair<iterator, bool> insert_result;
548 insert_result insert(const Key &key, const Value &value = Value())
550 return insert(key, value, false);
553 inline insert_result insert(const value_type &value)
555 return insert(value.first, value.second, false);
558 // insert_multi() allows items with duplicate keys.
559 insert_result insert_multi(const Key &key, const Value &value = Value())
561 return insert(key, value, true);
564 inline insert_result insert_multi(const value_type &value)
566 return insert(value.first, value.second, true);
569 inline Value &operator[](const Key &key)
571 return (insert(key).first)->second;
574 // Returns const ref to value if key is found, otherwise returns the default.
575 inline const Value &value(const Key &key, const Value &def = Value()) const
577 const_iterator it(find(key));
583 // iterator->first is the key, iterator->second is the value, or returns end() if the key cannot be found
584 inline const_iterator find(const Key &key) const
586 return find_const(key);
589 // iterator->first is the key, iterator->second is the value, or returns end() if the key cannot be found
590 inline iterator find(const Key &key)
592 const_iterator it(find_const(key));
593 return iterator(it.m_pNode);
596 // Return pointer to the value associated with key, or NULL if it doesn't exist.
597 inline Value *find_value(const Key &key)
599 node_type *p = find_prev_node(key);
601 p = p->get_forward_ptr(0);
602 if ((p != m_pHead) && (m_is_key_equal_to(p->first, key)))
608 // Return pointer to the value associated with key, or NULL if it doesn't exist.
609 inline const Value *find_value(const Key &key) const
611 node_type *p = find_prev_node(key);
613 p = p->get_forward_ptr(0);
614 if ((p != m_pHead) && (m_is_key_equal_to(p->first, key)))
620 // true if the key is found.
621 inline bool contains(const Key &key) const
623 m_pHead->check_head_debug_marker();
625 node_type *p = find_prev_node(key);
627 p = p->get_forward_ptr(0);
628 if ((p != m_pHead) && (m_is_key_equal_to(p->first, key)))
634 // Returns the # of items associated with the specified key.
635 inline uint count(const Key &key) const
637 m_pHead->check_head_debug_marker();
639 const_iterator it(find(key));
649 if (it->first != key)
657 // Erases the first item associated with the specified key. If there are multiple items with the same key, the most recently inserted will be erased.
658 bool erase(const Key &key)
660 VOGL_ASSERT((m_max_level < cMaxLevels) && (m_cur_level <= m_max_level));
661 m_pHead->check_head_debug_marker();
663 node_type *p = m_pHead;
665 node_type *ppPredecessors[cMaxLevels];
666 for (int i = m_cur_level; i >= 0; i--)
670 node_type *pNext = p->get_forward_ptr(i);
671 if ((pNext == m_pHead) || (!m_is_key_less_than(pNext->first, key)))
676 pNext = p->get_forward_ptr(i);
677 if ((pNext == m_pHead) || (!m_is_key_less_than(pNext->first, key)))
683 ppPredecessors[i] = p;
686 node_type *pPrev = p;
688 p = p->get_forward_ptr(0);
690 if ((p == m_pHead) || (!(m_is_key_equal_to(p->first, key))))
693 VOGL_ASSERT(m_size > 0);
695 node_type *pNext = p->get_forward_ptr(0);
697 VOGL_ASSERT(pPrev->get_forward_ptr(0) == p);
698 VOGL_ASSERT(pNext->get_prev_ptr() == p);
700 pPrev->set_forward_ptr(0, pNext);
701 pNext->set_prev_ptr(pPrev);
703 for (uint i = 1; i <= m_cur_level; i++)
705 if (ppPredecessors[i]->get_forward_ptr(i) != p)
708 ppPredecessors[i]->set_forward_ptr(i, p->get_forward_ptr(i));
711 // Be careful, key is a ref and it could be freed here!
714 while ((m_cur_level > 0) && (m_pHead->get_forward_ptr(m_cur_level) == m_pHead))
722 // This method erases a specific object from the container.
723 // It's more complex than erase() by key because there could be duplicate items.
724 void erase(const iterator &it)
726 VOGL_ASSERT((m_max_level < cMaxLevels) && (m_cur_level <= m_max_level));
727 m_pHead->check_head_debug_marker();
735 node_type *pNode_to_erase = it.m_pNode;
736 if (pNode_to_erase == m_pHead)
741 pNode_to_erase->check_item_debug_marker();
743 const int max_node_level = pNode_to_erase->get_num_next_ptrs() - 1;
744 if ((max_node_level < 0) || (max_node_level > m_cur_level))
750 if (max_node_level > 0)
752 const Key &key = it->first;
754 node_type *p = m_pHead;
756 node_type *ppPredecessors[cMaxLevels];
758 #ifdef VOGL_BUILD_DEBUG
759 ppPredecessors[0] = NULL;
761 for (int i = m_cur_level; i >= 1; i--)
765 node_type *pNext = p->get_forward_ptr(i);
766 if ((pNext == m_pHead) || (!m_is_key_less_than(pNext->first, key)))
771 pNext = p->get_forward_ptr(i);
772 if ((pNext == m_pHead) || (!m_is_key_less_than(pNext->first, key)))
778 ppPredecessors[i] = p;
781 for (int i = 1; i <= max_node_level; i++)
783 node_type *q = ppPredecessors[i];
785 while (q->get_forward_ptr(i) != pNode_to_erase)
787 q = q->get_forward_ptr(i);
789 if ((q == m_pHead) || (m_is_key_less_than(key, q->first)))
791 // Something is very wrong, because the node to delete MUST be in this level's list and we've now either reached the end or a key which is greater.
796 VOGL_ASSERT(m_is_key_equal_to(key, q->first));
799 q->set_forward_ptr(i, pNode_to_erase->get_forward_ptr(i));
803 node_type *pPrev = pNode_to_erase->get_prev_ptr();
804 node_type *pNext = pNode_to_erase->get_forward_ptr(0);
806 VOGL_ASSERT(pPrev->get_forward_ptr(0) == pNode_to_erase);
807 VOGL_ASSERT(pNext->get_prev_ptr() == pNode_to_erase);
809 pPrev->set_forward_ptr(0, pNext);
810 pNext->set_prev_ptr(pPrev);
812 free_node(pNode_to_erase);
814 while ((m_cur_level > 0) && (m_pHead->get_forward_ptr(m_cur_level) == m_pHead))
820 // Erases all items with the specified key.
821 // Returns the total number of erased keys.
822 inline uint erase_all(const Key &key)
824 m_pHead->check_head_debug_marker();
826 std::pair<iterator, iterator> it_range(equal_range(key));
828 // Use caution here - key could point into one of the items we're about to erase!
831 for (iterator it = it_range.first; it != it_range.second;)
833 iterator next_it(it);
845 // Returns an iterator pointing to the first item with key key in the map.
846 // If the map contains no item with key key, the function returns an iterator to the nearest item with a greater key.
847 inline const_iterator lower_bound(const Key &key) const
849 m_pHead->check_head_debug_marker();
851 node_type *pPrev = find_prev_node(key);
852 node_type *pNext = pPrev->get_forward_ptr(0);
853 return const_iterator(pNext);
856 inline iterator lower_bound(const Key &key)
858 m_pHead->check_head_debug_marker();
860 node_type *pPrev = find_prev_node(key);
861 node_type *pNext = pPrev->get_forward_ptr(0);
862 return iterator(pNext);
865 // Returns an iterator pointing to the item that immediately follows the last item with key key in the map.
866 // If the map contains no item with key key, the function returns an iterator to the nearest item with a greater key.
867 inline const_iterator upper_bound(const Key &key) const
869 m_pHead->check_head_debug_marker();
871 node_type *pPrev = find_prev_node(key);
872 node_type *pNext = pPrev->get_forward_ptr(0);
874 while (pNext != m_pHead)
876 if (!m_is_key_equal_to(pNext->first, key))
878 pNext = pNext->get_forward_ptr(0);
881 return const_iterator(pNext);
884 inline iterator upper_bound(const Key &key)
886 m_pHead->check_head_debug_marker();
888 node_type *pPrev = find_prev_node(key);
889 node_type *pNext = pPrev->get_forward_ptr(0);
891 while (pNext != m_pHead)
893 if (!m_is_key_equal_to(pNext->first, key))
895 pNext = pNext->get_forward_ptr(0);
898 return iterator(pNext);
901 // Returns a pair of iterators delimiting the range of values that are stored under key.
902 inline std::pair<iterator, iterator> equal_range(const Key &key)
904 m_pHead->check_head_debug_marker();
906 node_type *pPrev = find_prev_node(key);
907 node_type *pNext = pPrev->get_forward_ptr(0);
909 if ((pNext == m_pHead) || (!m_is_key_equal_to(pNext->first, key)))
910 return std::make_pair(end(), end());
912 iterator first_it(pNext);
916 pNext = pNext->get_forward_ptr(0);
917 if ((pNext == m_pHead) || (!m_is_key_equal_to(pNext->first, key)))
921 return std::make_pair(first_it, iterator(pNext));
924 inline std::pair<const_iterator, const_iterator> equal_range(const Key &key) const
926 m_pHead->check_head_debug_marker();
928 node_type *pPrev = find_prev_node(key);
929 node_type *pNext = pPrev->get_forward_ptr(0);
931 if ((pNext == m_pHead) || (!m_is_key_equal_to(pNext->first, key)))
932 return std::make_pair(end(), end());
934 const_iterator first_it(pNext);
938 pNext = pNext->get_forward_ptr(0);
939 if ((pNext == m_pHead) || (!m_is_key_equal_to(pNext->first, key)))
943 return std::make_pair(first_it, const_iterator(pNext));
946 // Appends all unique keys to the specified vector.
947 inline vogl::vector<Key> &get_unique_keys(vogl::vector<Key> &vec) const
949 m_pHead->check_head_debug_marker();
954 node_type *pCur = m_pHead->get_forward_ptr(0);
955 while (pCur != m_pHead)
957 const Key &cur_key = pCur->first;
958 vec.push_back(cur_key);
960 pCur = pCur->get_forward_ptr(0);
962 while ((pCur != m_pHead) && (pCur->first == cur_key))
963 pCur = pCur->get_forward_ptr(0);
969 // Appends all keys to the specified vector.
970 inline vogl::vector<Key> &get_keys(vogl::vector<Key> &vec) const
972 m_pHead->check_head_debug_marker();
977 vec.reserve(vec.size() + m_size);
979 node_type *pCur = m_pHead->get_forward_ptr(0);
980 while (pCur != m_pHead)
982 vec.push_back(pCur->first);
983 pCur = pCur->get_forward_ptr(0);
989 // Appends all values to the specified vector.
990 inline vogl::vector<Value> &get_values(vogl::vector<Value> &vec) const
992 m_pHead->check_head_debug_marker();
997 vec.reserve(vec.size() + m_size);
999 node_type *pCur = m_pHead->get_forward_ptr(0);
1000 while (pCur != m_pHead)
1002 vec.push_back(pCur->second);
1003 pCur = pCur->get_forward_ptr(0);
1009 // Appends all items with key to the specified vector.
1010 inline vogl::vector<Value> &get_values(const Key &key, vogl::vector<Value> &vec) const
1012 m_pHead->check_head_debug_marker();
1014 node_type *pPrev = find_prev_node(key);
1015 node_type *pNext = pPrev->get_forward_ptr(0);
1017 while ((pNext != m_pHead) && (m_is_key_equal_to(pNext->first, key)))
1019 vec.push_back(pNext->second);
1021 pNext = pNext->get_forward_ptr(0);
1027 // Inserts all items from the specified map to this map.
1028 inline map &unite_multi(const map &rhs)
1030 m_pHead->check_head_debug_marker();
1031 rhs.m_pHead->check_head_debug_marker();
1039 for (const_iterator it = rhs.begin(); it != rhs.end(); ++it)
1040 insert_multi(it->first, it->second);
1045 inline map &unite(const map &rhs)
1047 m_pHead->check_head_debug_marker();
1048 rhs.m_pHead->check_head_debug_marker();
1056 for (const_iterator it = rhs.begin(); it != rhs.end(); ++it)
1057 insert(it->first, it->second);
1062 // Fast swap of this container with another.
1063 inline void swap(map &other)
1065 m_pHead->check_head_debug_marker();
1066 other.m_pHead->check_head_debug_marker();
1068 std::swap(m_total_allocated, other.m_total_allocated);
1069 std::swap(m_is_key_less_than, other.m_is_key_less_than);
1070 std::swap(m_is_key_equal_to, other.m_is_key_equal_to);
1071 std::swap(m_rand, other.m_rand);
1072 std::swap(m_size, other.m_size);
1073 std::swap(m_bump_max_level_size_thresh, other.m_bump_max_level_size_thresh);
1074 std::swap(m_cur_level, other.m_cur_level);
1075 std::swap(m_max_level, other.m_max_level);
1076 std::swap(m_pHead, other.m_pHead);
1077 std::swap(m_fixed_max_level, other.m_fixed_max_level);
1080 // Compares this container's full contents to another.
1081 inline bool operator==(const map &rhs) const
1086 m_pHead->check_head_debug_marker();
1087 rhs.m_pHead->check_head_debug_marker();
1089 if (m_size != rhs.m_size)
1092 const_iterator lhs_it(begin());
1093 const_iterator rhs_it(rhs.begin());
1095 while (lhs_it != end())
1097 VOGL_ASSERT(rhs_it != rhs.end());
1099 if (*lhs_it != *rhs_it)
1109 inline bool operator!=(const map &rhs) const
1111 return !(*this == rhs);
1114 void print_debug_info()
1116 m_pHead->check_head_debug_marker();
1118 console::debug("map 0x%p: Size: %u elements, Max possible level: %u, Cur max level: %u, Cur level: %u\n",
1119 this, m_size, cMaxLevels - 1, m_max_level, m_cur_level);
1120 console::debug(" Bump max level size: %u\n", m_bump_max_level_size_thresh);
1121 console::debug(" Key size: %u bytes, Value size: %u bytes, KeyValue size: %u bytes, Min element size: %u bytes\n", (uint)sizeof(Key), (uint)sizeof(Value), (uint)sizeof(value_type), (uint)sizeof(node_type));
1122 console::debug(" Total allocated: %" PRIu64 " bytes, Avg allocated per element: %f bytes, Avg overhead: %f bytes\n", m_total_allocated,
1123 m_size ? m_total_allocated / (double)m_size : 0,
1124 m_size ? (m_total_allocated / (double)m_size) - sizeof(value_type) : 0);
1125 console::debug(" Max element size: %u bytes\n", (uint)(sizeof(node_type) + sizeof(void *) * m_max_level));
1127 for (uint level = 0; level <= m_max_level; level++)
1131 node_type *p = m_pHead->get_forward_ptr(level);
1133 int64_t total_size_at_this_level = 0;
1134 uint total_count_at_this_level = 0;
1136 while (p != m_pHead)
1138 p->check_item_debug_marker();
1140 if (p->get_num_next_ptrs() == (level + 1))
1142 total_size_at_this_level += p->get_allocated_size();
1143 total_count_at_this_level++;
1146 p = p->get_forward_ptr(level);
1150 float prob = VOGL_MAP_USE_POINT_25_PROB ? (1.0f / 4.0f) : (1.0f / 2.0f);
1151 console::debug(" Level %u: Total: %u (Expected: %f), At this level: %u (Expected: %f), Alloc bytes at this level: %" PRIi64 ", Avg alloc bytes at this level: %f\n",
1152 level, n, m_size * pow(prob, level),
1153 total_count_at_this_level, m_size * pow(prob, level) * ((level == m_max_level) ? 1.0f : (1.0f - prob)),
1154 total_size_at_this_level,
1155 total_count_at_this_level ? total_size_at_this_level / (double)total_count_at_this_level : 0);
1159 // Returns false if the container is invalid/corrupted.
1160 bool debug_check() const
1162 m_pHead->check_head_debug_marker();
1164 if (m_cur_level > m_max_level)
1169 if (m_size > m_bump_max_level_size_thresh)
1174 if (m_pHead->get_prev_ptr() != m_pHead)
1176 if (m_pHead->get_forward_ptr(0) != m_pHead)
1178 if (m_cur_level > 0)
1183 for (uint i = m_cur_level + 1; i <= m_max_level; i++)
1185 if (m_pHead->get_forward_ptr(i) != m_pHead)
1189 for (uint i = 0; i <= m_cur_level; i++)
1191 uint num_nodes_examined = 0;
1192 node_type *pCur = m_pHead;
1194 int64_t total_node_bytes = 0;
1198 if (!pCur->get_num_next_ptrs())
1201 if (pCur == m_pHead)
1203 pCur->check_head_debug_marker();
1205 if (pCur->get_num_next_ptrs() != (m_max_level + 1U))
1210 pCur->check_item_debug_marker();
1212 if (pCur->get_num_next_ptrs() > (m_cur_level + 1U))
1216 if (i >= pCur->get_num_next_ptrs())
1219 node_type *pNext = pCur->get_forward_ptr(i);
1229 if (pNext->get_prev_ptr() != pCur)
1233 if (pNext == m_pHead)
1238 total_node_bytes += sizeof(node_type) + sizeof(node_type *) * (pNext->get_num_next_ptrs() - 1);
1241 num_nodes_examined++;
1242 if (num_nodes_examined > m_size)
1245 if (pCur != m_pHead)
1247 if (m_is_key_less_than(pNext->first, pCur->first))
1253 node_type *q = pCur->get_forward_ptr(i - 1);
1260 q = q->get_forward_ptr(i - 1);
1267 if (!num_nodes_examined)
1272 if (num_nodes_examined != m_size)
1274 if (total_node_bytes != m_total_allocated)
1283 int64_t m_total_allocated;
1288 uint m_bump_max_level_size_thresh;
1295 bool m_fixed_max_level;
1297 less_comp_type m_is_key_less_than;
1298 equal_comp_type m_is_key_equal_to;
1300 inline void free_node(node_type *p)
1302 p->check_item_debug_marker();
1304 m_total_allocated -= (sizeof(node_type) + sizeof(node_type *) * (p->get_num_next_ptrs() - 1));
1305 VOGL_ASSERT(m_total_allocated >= 0);
1307 #ifdef VOGL_ASSERTS_ENABLED
1308 p->set_debug_marker(cMapNodeFreeDebugMarker);
1311 helpers::destruct(p);
1316 inline node_type *alloc_node(uint num_forward_ptrs, const Key &key, const Value &val)
1318 VOGL_ASSERT(num_forward_ptrs && (num_forward_ptrs < cMaxLevels));
1320 uint alloc_size = sizeof(node_type) + sizeof(node_type *) * (num_forward_ptrs - 1);
1321 m_total_allocated += alloc_size;
1323 node_type *p = static_cast<node_type *>(vogl_malloc(alloc_size));
1325 p->set_num_next_ptrs(num_forward_ptrs);
1327 #ifdef VOGL_ASSERTS_ENABLED
1328 p->set_debug_marker(cMapListNodeItemDebugMarker);
1331 helpers::construct(const_cast<Key *>(&p->first), key);
1332 helpers::construct(&p->second, val);
1337 void init(uint initial_max_level)
1339 VOGL_VERIFY(initial_max_level < cMaxLevels);
1340 VOGL_ASSERT(!m_size && !m_total_allocated);
1342 m_max_level = initial_max_level;
1345 m_bump_max_level_size_thresh = cUINT32_MAX;
1346 if (!m_fixed_max_level)
1348 #if VOGL_MAP_USE_POINT_25_PROB
1349 if (initial_max_level < 16)
1350 m_bump_max_level_size_thresh = 1U << (initial_max_level * 2U);
1352 if (initial_max_level < 32)
1353 m_bump_max_level_size_thresh = 1U << initial_max_level;
1359 m_pHead = static_cast<node_type *>(vogl_malloc(sizeof(node_type) + (cMaxLevels - 1) * sizeof(void *)));
1361 // Purposely clearing the whole thing, because we're not going to construct the Key/Value at the beginning (and if somebody screws up and accesses the head by accident, at least they get zero's instead of garbage).
1362 memset(m_pHead, 0, sizeof(node_type));
1364 #ifdef VOGL_ASSERTS_ENABLED
1365 m_pHead->set_debug_marker(cMapNodeHeadDebugMarker);
1370 m_pHead->check_head_debug_marker();
1373 VOGL_ASSERT(m_pHead->get_prev_ptr() == m_pHead);
1374 VOGL_ASSERT(m_pHead->get_num_next_ptrs() < cMaxLevels);
1375 for (uint i = 0; i < cMaxLevels; i++)
1377 VOGL_ASSERT(m_pHead->m_ptrs.m_pNext[i] == m_pHead);
1381 m_pHead->set_prev_ptr(m_pHead);
1383 m_pHead->set_num_next_ptrs(cMaxLevels);
1384 for (uint i = 0; i < cMaxLevels; i++)
1385 m_pHead->set_forward_ptr(i, m_pHead);
1387 m_pHead->set_num_next_ptrs(m_max_level + 1);
1390 void clone(const map &other)
1392 other.m_pHead->check_head_debug_marker();
1394 init(other.m_max_level);
1396 node_type *pCur = other.m_pHead->get_forward_ptr(0);
1397 while (pCur != other.m_pHead)
1399 pCur->check_item_debug_marker();
1401 insert_multi(*pCur);
1403 pCur = pCur->get_forward_ptr(0);
1407 // Returns the node previous to key. The next node will be the first instance of key, or the next greater key, or m_pHead.
1408 inline node_type *find_prev_node(const Key &key) const
1410 node_type *p = m_pHead;
1412 p->check_head_debug_marker();
1414 for (int i = m_cur_level; i >= 0; i--)
1418 node_type *pNext = p->get_forward_ptr(i);
1420 if (pNext == m_pHead)
1422 pNext->check_item_debug_marker();
1423 if (!m_is_key_less_than(pNext->first, key))
1428 pNext = p->get_forward_ptr(i);
1429 if (pNext == m_pHead)
1431 pNext->check_item_debug_marker();
1432 if (!m_is_key_less_than(pNext->first, key))
1437 pNext = p->get_forward_ptr(i);
1438 if (pNext == m_pHead)
1440 pNext->check_item_debug_marker();
1441 if (!m_is_key_less_than(pNext->first, key))
1451 inline const_iterator find_const(const Key &key) const
1453 node_type *p = find_prev_node(key);
1455 p = p->get_forward_ptr(0);
1456 if ((p != m_pHead) && (m_is_key_equal_to(p->first, key)))
1457 return const_iterator(p);
1462 // insert_result.first will always point to inserted key/value (or the already existing key/value).
1463 // insert_result.second will be true if a new key/value was inserted, or false if the key already existed (in which case first will point to the already existing value).
1464 insert_result insert(const Key &key, const Value &value, bool allow_dups)
1466 VOGL_ASSERT((m_max_level < cMaxLevels) && (m_cur_level <= m_max_level));
1467 m_pHead->check_head_debug_marker();
1469 node_type *p = m_pHead;
1471 node_type *ppPredecessors[cMaxLevels];
1472 for (int i = m_cur_level; i >= 0; i--)
1476 node_type *pNext = p->get_forward_ptr(i);
1477 if ((pNext == m_pHead) || (!m_is_key_less_than(pNext->first, key)))
1482 pNext = p->get_forward_ptr(i);
1483 if ((pNext == m_pHead) || (!m_is_key_less_than(pNext->first, key)))
1488 pNext = p->get_forward_ptr(i);
1489 if ((pNext == m_pHead) || (!m_is_key_less_than(pNext->first, key)))
1495 ppPredecessors[i] = p;
1500 p = p->get_forward_ptr(0);
1501 if ((p != m_pHead) && (m_is_key_equal_to(p->first, key)))
1502 return std::make_pair(iterator(p), false);
1505 if (m_size == cUINT32_MAX)
1508 return std::make_pair(begin(), false);
1511 uint rnd = m_rand.urand32();
1512 int new_level = math::count_leading_zero_bits(rnd);
1513 #if VOGL_MAP_USE_POINT_25_PROB
1516 new_level = math::minimum<uint>(new_level, m_max_level);
1518 if (new_level > m_cur_level)
1520 for (int i = m_cur_level + 1; i <= new_level; i++)
1521 ppPredecessors[i] = m_pHead;
1523 m_cur_level = new_level;
1526 node_type *pNew_node = alloc_node(new_level + 1, key, value);
1528 node_type *pPrev = ppPredecessors[0];
1529 node_type *pNext = pPrev->get_forward_ptr(0);
1531 VOGL_ASSERT(pNext->get_prev_ptr() == pPrev);
1533 pPrev->set_forward_ptr(0, pNew_node);
1534 pNext->set_prev_ptr(pNew_node);
1535 pNew_node->set_prev_ptr(pPrev);
1536 pNew_node->set_forward_ptr(0, pNext);
1538 for (int i = 1; i <= new_level; i++)
1540 pNew_node->set_forward_ptr(i, ppPredecessors[i]->get_forward_ptr(i));
1541 ppPredecessors[i]->set_forward_ptr(i, pNew_node);
1545 if ((m_size > m_bump_max_level_size_thresh) && (static_cast<int>(m_max_level) < (static_cast<int>(cMaxLevels) - 1)))
1549 m_pHead->set_num_next_ptrs(m_max_level + 1);
1550 VOGL_ASSERT(m_pHead->get_forward_ptr(m_max_level) == m_pHead);
1552 uint orig_thresh_size = m_bump_max_level_size_thresh;
1553 m_bump_max_level_size_thresh <<= (VOGL_MAP_USE_POINT_25_PROB ? 2U : 1U);
1554 if (m_bump_max_level_size_thresh < orig_thresh_size)
1555 m_bump_max_level_size_thresh = cUINT32_MAX;
1558 return std::make_pair(iterator(pNew_node), true);
1562 template <typename Key, typename Value, typename LessComp, typename EqualComp, uint MaxLevels>
1563 struct bitwise_movable<map<Key, Value, LessComp, EqualComp, MaxLevels> >
1571 template <typename Key, typename Value, typename LessComp, typename EqualComp, uint MaxLevels>
1572 inline void swap(map<Key, Value, LessComp, EqualComp, MaxLevels> &a, map<Key, Value, LessComp, EqualComp, MaxLevels> &b)
1578 void map_perf_test(uint Q = 20000);
1584 template <typename Key, typename Value, typename LessComp, typename EqualComp, uint MaxLevels>
1585 inline void swap(vogl::map<Key, Value, LessComp, EqualComp, MaxLevels> &a, vogl::map<Key, Value, LessComp, EqualComp, MaxLevels> &b)
1591 #endif // #ifndef VOGL_MAP_H