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 **************************************************************************/
27 // File: vogl_sparse_vector.h
30 #include "vogl_core.h"
31 #include "vogl_rand.h"
32 #include "vogl_strutils.h"
37 template <typename T, uint Log2N>
38 class sparse_vector_traits
41 static inline void *alloc_space(uint size)
43 return vogl_malloc(size);
46 static inline void free_space(void *p)
51 static inline void construct_group(T *p)
53 scalar_type<T>::construct_array(p, 1U << Log2N);
56 static inline void destruct_group(T *p)
58 scalar_type<T>::destruct_array(p, 1U << Log2N);
61 static inline void construct_element(T *p)
63 scalar_type<T>::construct(p);
66 static inline void destruct_element(T *p)
68 scalar_type<T>::destruct(p);
71 static inline void copy_group(T *pDst, const T *pSrc)
73 for (uint j = 0; j < (1U << Log2N); j++)
78 template <typename T, uint Log2N, template <typename, uint> class Traits = sparse_vector_traits>
79 class sparse_vector : public Traits<T, Log2N>
82 typedef Traits<T, Log2N> base;
88 typedef vogl::vector<T *> group_ptr_vec;
90 inline sparse_vector()
91 : m_size(0), m_num_active_groups(0)
96 inline sparse_vector(uint size)
97 : m_size(0), m_num_active_groups(0)
104 inline sparse_vector(const sparse_vector &other)
105 : m_size(0), m_num_active_groups(0)
112 template <uint OtherLogN, template <typename, uint> class OtherTraits>
113 inline sparse_vector(const sparse_vector<T, OtherLogN, OtherTraits> &other)
114 : m_size(0), m_num_active_groups(0)
118 default_element() = other.default_element();
123 inline sparse_vector(const vogl::vector<T> &other)
124 : m_size(0), m_num_active_groups(0)
131 inline ~sparse_vector()
133 for (uint i = 0; (i < m_groups.size()) && m_num_active_groups; i++)
134 free_group(m_groups[i]);
139 // Get/set the default object returned by operator [] on non-present elements.
140 inline const T &default_element() const
142 return *reinterpret_cast<const T *>(m_default);
144 inline T &default_element()
146 return *reinterpret_cast<T *>(m_default);
149 inline bool assign(const sparse_vector &other)
154 if (!try_resize(other.size()))
157 for (uint i = 0; i < other.m_groups.size(); i++)
159 const T *p = other.m_groups[i];
167 q = alloc_group(true);
174 base::copy_group(q, p);
186 sparse_vector &operator=(const sparse_vector &other)
190 VOGL_FAIL("Out of memory");
196 template <uint OtherLogN, template <typename, uint> class OtherTraits>
197 inline bool assign(const sparse_vector<T, OtherLogN, OtherTraits> &other)
199 if ((void *)this == (void *)&other)
202 if (!try_resize(other.size()))
205 for (uint i = 0; i < other.size(); ++i)
206 if (other.is_present(i))
207 set(i, *other.get_ptr(i));
212 template <uint OtherLogN, template <typename, uint> class OtherTraits>
213 inline sparse_vector &operator=(const sparse_vector<T, OtherLogN, OtherTraits> &other)
217 VOGL_FAIL("Out of memory");
223 inline bool assign(const vogl::vector<T> &other, bool default_element_check)
225 if (!try_resize(other.size()))
228 if (default_element_check)
230 allocate_all_groups();
232 const T *pSrc = other.get_ptr();
233 const uint n = other.size();
234 for (uint i = 0; i < n; ++i)
235 m_groups[i >> Log2N][i & (N - 1)] = *pSrc++;
239 for (uint i = 0; i < other.size(); ++i)
240 if (other[i] != default_element())
247 inline bool operator=(const vogl::vector<T> &other)
249 if (!assign(other, true))
251 VOGL_FAIL("Out of memory");
256 bool operator==(const sparse_vector &other) const
261 if (m_size != other.m_size)
264 for (uint i = 0; i < m_size; i++)
265 if (!((*this)[i] == other[i]))
271 bool operator!=(const sparse_vector &other) const
273 return !(*this == other);
276 bool operator<(const sparse_vector &rhs) const
278 const uint min_size = math::minimum(m_size, rhs.m_size);
281 for (i = 0; i < min_size; i++)
282 if (!((*this)[i] == rhs[i]))
286 return (*this)[i] < rhs[i];
288 return m_size < rhs.m_size;
295 for (uint i = 0; (i < m_groups.size()) && m_num_active_groups; i++)
296 free_group(m_groups[i]);
303 VOGL_ASSERT(!m_num_active_groups);
306 bool get_vector(vogl::vector<T> &dst) const
308 if (!dst.try_resize(size()))
311 const T *const *ppGroups = m_groups.get_ptr();
312 const uint num_groups = m_groups.size();
313 for (uint group_iter = 0; group_iter < num_groups; ++group_iter)
315 const T *pGroup = ppGroups[group_iter];
319 const uint n = get_num_valid_elements_in_group(group_iter);
320 T *pDst = &dst[group_iter << Log2N];
322 for (uint i = 0; i < n; ++i)
329 bool try_resize(uint new_size)
331 if (m_size == new_size)
334 uint new_last_group_index = 0;
335 uint prev_num_valid_elements_in_new_last_group = 0;
336 bool shrinking = ((new_size) && (new_size < m_size));
339 new_last_group_index = (new_size - 1) >> Log2N;
340 prev_num_valid_elements_in_new_last_group = get_num_valid_elements_in_group(new_last_group_index);
341 VOGL_ASSERT(prev_num_valid_elements_in_new_last_group);
344 const uint new_num_groups = (new_size + N - 1) >> Log2N;
345 if (new_num_groups != m_groups.size())
347 for (uint i = new_num_groups; i < m_groups.size(); i++)
348 free_group(m_groups[i]);
350 if (!m_groups.try_resize(new_num_groups))
358 T *pLast_group = m_groups[new_last_group_index];
361 uint cur_num_valid_elements_in_new_last_group = get_num_valid_elements_in_group(new_last_group_index);
362 VOGL_ASSERT(cur_num_valid_elements_in_new_last_group);
364 if (cur_num_valid_elements_in_new_last_group < prev_num_valid_elements_in_new_last_group)
366 for (uint i = cur_num_valid_elements_in_new_last_group; i < prev_num_valid_elements_in_new_last_group; i++)
367 pLast_group[i] = default_element();
375 void resize(uint size)
377 if (!try_resize(size))
379 VOGL_FAIL("Out of memory");
383 inline uint size() const
387 inline bool is_empty() const
392 inline uint capacity() const
394 return m_groups.size() << Log2N;
396 inline uint actual_capacity() const
398 return m_num_active_groups << Log2N;
401 // Returns the default object if the element does not yet exist.
402 // at() will not force elements to be allocated if they don't exist, preventing accidents.
403 inline const T &at(uint i) const
405 VOGL_ASSERT(i < m_size);
406 const T *p = m_groups[i >> Log2N];
407 return p ? p[i & (N - 1)] : *reinterpret_cast<const T *>(m_default);
410 // Returns the default object if the element does not yet exist.
411 // operator [] is read only, i.e. will not force elements to be allocated if they don't exist, preventing accidents.
412 inline const T &operator[](uint i) const
417 class sparse_vector_object_accessor
419 sparse_vector &m_array;
423 inline sparse_vector_object_accessor(sparse_vector &array, uint index)
424 : m_array(array), m_index(index)
427 inline sparse_vector_object_accessor(const sparse_vector_object_accessor &other)
428 : m_array(other.m_array), m_index(other.m_index)
432 // Returns const ref to element, or the default element if it's not allocated.
433 inline operator const T &() const
435 return m_array.get_element(m_index);
438 // Taking the address always forces the element to be allocated.
439 inline T *operator&() const
441 T *p = m_array.get_ptr(m_index);
443 p = m_array.ensure_present(m_index);
447 // Assigns element, forcing it to be allocated if it doesn't exist.
448 inline T &operator=(const T &other) const
450 T *p = m_array.get_ptr(m_index);
452 p = m_array.ensure_present(m_index);
458 // Yes this is ugly, but it works around the fact that we can't overload operator "." in C++.
459 // So operator[] and at() are read-only (and never force elements to be allocated, preventing silly accidents), and operator () is read/write (it will write on operator =).
460 // I'm torn about this guy, it's probably too confusing vs. just calling get_or_create_element(), get_ptr(), etc.
461 inline const sparse_vector_object_accessor operator()(uint i)
463 VOGL_ASSERT(i < m_size);
464 return sparse_vector_object_accessor(*this, i);
467 // Returns a ref to the element (allocating it if necessary).
468 inline T &get_or_create_element(uint i)
470 VOGL_ASSERT(i < m_size);
472 T *p = m_groups[i >> Log2N];
474 return *ensure_present(i);
476 return p[i & (N - 1)];
479 // Returns NULL if element does not yet exist.
480 inline const T *get_ptr(uint i) const
482 VOGL_ASSERT(i < m_size);
483 const T *p = m_groups[i >> Log2N];
484 return p ? &p[i & (N - 1)] : NULL;
487 // Returns NULL if element does not yet exist.
488 inline T *get_ptr(uint i)
490 VOGL_ASSERT(i < m_size);
491 T *p = m_groups[i >> Log2N];
492 return p ? &p[i & (N - 1)] : NULL;
495 // Returns true if the element exists.
496 inline bool is_present(uint i) const
498 VOGL_ASSERT(i < m_size);
499 return m_groups[i >> Log2N] != NULL;
502 // Ensures element is allocated/present (enlarging the entire array if needed).
503 inline T *ensure_present(uint index)
505 const uint group_index = index >> Log2N;
506 if (group_index >= m_groups.size())
508 if (!try_resize(index + 1))
512 T *p = m_groups[group_index];
515 p = alloc_group(true);
519 m_groups[group_index] = p;
522 m_size = math::maximum(index + 1, m_size);
524 return p + (index & (N - 1));
527 inline bool set(uint index, const T &obj)
529 T *p = ensure_present(index);
538 inline void push_back(const T &obj)
540 if (!set(m_size, obj))
542 VOGL_FAIL("Out of memory");
546 inline bool try_push_back(const T &obj)
548 return set(m_size, obj);
551 inline T *enlarge(uint n)
553 uint orig_size = m_size;
554 for (uint i = 0; i < n; i++)
556 if (!ensure_present(m_size))
558 VOGL_FAIL("Out of memory");
561 return get_ptr(orig_size);
564 inline void pop_back()
571 // Sets range [start, start + num) to the default object, freeing any groups that it can
572 inline void invalidate_range(uint start, uint num)
577 if ((start + num) > m_size)
583 const uint num_to_skip = math::minimum(math::get_align_up_value_delta(start, N), num);
585 for (uint i = 0; i < num_to_skip; i++)
587 if (is_present(start + i))
588 set(start + i, default_element());
591 start += num_to_skip;
594 const uint first_group_to_free = start >> Log2N;
595 const uint num_groups_to_free = num >> Log2N;
597 free_groups(first_group_to_free, num_groups_to_free);
599 const uint total_elements_freed = num_groups_to_free << Log2N;
600 start += total_elements_freed;
601 num -= total_elements_freed;
603 for (uint i = 0; i < num; i++)
605 if (is_present(start + i))
606 set(start + i, default_element());
610 inline void invalidate_all()
612 for (uint i = 0; i < m_groups.size(); i++)
623 inline void swap(sparse_vector &other)
625 utils::swap(m_size, other.m_size);
626 m_groups.swap(other.m_groups);
627 utils::swap(m_num_active_groups, other.m_num_active_groups);
630 inline bool set_all(const T &val)
635 const bool is_default = (val == default_element());
637 for (uint group_iter = 0; group_iter < m_groups.size(); ++group_iter)
639 const T *pGroup = m_groups[group_iter];
645 pGroup = alloc_group(true);
649 m_groups[group_iter] = pGroup;
652 const uint n = get_num_valid_elements_in_group(group_iter);
653 for (uint i = 0; i < n; i++)
660 inline int find(const T &key) const
663 return cInvalidIndex;
665 const bool is_default = (key == default_element());
667 for (uint group_iter = 0; group_iter < m_groups.size(); ++group_iter)
669 const T *pGroup = m_groups[group_iter];
673 return group_iter << Log2N;
677 const uint n = get_num_valid_elements_in_group(group_iter);
678 for (uint i = 0; i < n; i++)
679 if (pGroup[i] == key)
680 return (group_iter << Log2N) + i;
683 return cInvalidIndex;
686 inline uint allocate_all_groups()
688 if (m_num_active_groups == m_groups.size())
691 uint num_groups_allocated = 0;
693 for (uint group_iter = 0; group_iter < m_groups.size(); ++group_iter)
695 T *pGroup = m_groups[group_iter];
699 m_groups[group_iter] = alloc_group();
700 num_groups_allocated++;
703 return num_groups_allocated;
706 inline uint optimize_groups()
708 if (!m_num_active_groups)
711 uint num_groups_freed = 0;
713 for (uint group_iter = 0; group_iter < m_groups.size(); ++group_iter)
715 T *pGroup = m_groups[group_iter];
719 const uint n = get_num_valid_elements_in_group(group_iter);
722 for (i = 0; i < n; i++)
723 if (!(pGroup[i] == default_element()))
729 m_groups[group_iter] = NULL;
735 return num_groups_freed;
738 inline bool check() const
740 if (m_groups.size() != ((m_size + (N - 1)) >> Log2N))
743 vogl::vector<T *> group_ptrs;
744 uint total_active_groups = 0;
745 for (uint group_iter = 0; group_iter < m_groups.size(); ++group_iter)
747 T *pGroup = m_groups[group_iter];
748 if (reinterpret_cast<intptr_t>(pGroup) & (VOGL_MIN_ALLOC_ALIGNMENT - 1))
753 total_active_groups++;
754 group_ptrs.push_back(pGroup);
758 if (total_active_groups != m_num_active_groups)
763 if (group_ptrs.size() != total_active_groups)
769 for (uint i = 0; i < (m_groups.size() - 1); i++)
771 uint n = get_num_valid_elements_in_group(i);
777 uint num_valid_in_last_group = get_num_valid_elements_in_group(m_groups.size() - 1);
778 t += num_valid_in_last_group;
782 if (!num_valid_in_last_group)
784 if (num_valid_in_last_group > N)
787 const T *pLast_group = m_groups.back();
790 for (uint i = num_valid_in_last_group; i < N; i++)
792 if (!(pLast_group[i] == default_element()))
801 inline void copy_element(uint dst_index, uint src_index)
803 if (!is_present(src_index))
805 if (is_present(dst_index))
806 set(dst_index, default_element());
810 set(dst_index, *get_ptr(src_index));
814 inline void erase(uint start, uint n)
816 VOGL_ASSERT((start + n) <= m_size);
817 if ((start + n) > m_size)
823 const uint orig_num_groups = m_groups.size();
825 uint num_to_move = m_size - (start + n);
826 uint dst_index = start;
827 uint src_index = start + n;
829 while ((num_to_move) && ((dst_index & (N - 1)) != 0))
831 copy_element(dst_index, src_index);
840 // dst_index must be aligned to the beginning of a group here.
841 VOGL_ASSERT((dst_index & (N - 1)) == 0);
843 const uint move_gap_size = src_index - dst_index;
845 // If the move gap is >= the group size, then we can just free all the groups in the middle of the move gap that are overridden (and bulk erase the group ptrs array).
846 if (move_gap_size >= N)
848 uint first_full_group, num_full_groups;
849 get_full_group_range(dst_index, math::minimum(num_to_move, move_gap_size), first_full_group, num_full_groups);
853 const uint total_elements_to_free = num_full_groups << Log2N;
855 VOGL_ASSERT(total_elements_to_free <= num_to_move);
856 VOGL_ASSERT(dst_index <= (first_full_group << Log2N));
857 VOGL_ASSERT(src_index >= total_elements_to_free);
859 free_groups(first_full_group, num_full_groups);
861 m_groups.erase(first_full_group, num_full_groups);
862 m_groups.resize(orig_num_groups);
864 //VOGL_ASSERT(check());
866 src_index -= total_elements_to_free;
872 if (!is_present(src_index))
874 if ((src_index & (N - 1)) == 0)
876 uint num_not_present = math::minimum<uint>(num_to_move, N);
878 // We know up to the next N src elements are not present, so there's no need to check them.
879 VOGL_ASSERT(!is_present(src_index + num_not_present - 1));
881 src_index += num_not_present;
882 num_to_move -= num_not_present;
884 while (num_not_present)
886 if (is_present(dst_index))
887 set(dst_index, default_element());
895 if (is_present(dst_index))
896 set(dst_index, default_element());
900 set(dst_index, *get_ptr(src_index));
912 inline void insert(uint index, const T *p, uint n, bool check_for_default_elements_while_copying = true)
914 VOGL_ASSERT(index <= m_size);
918 const uint orig_size = m_size;
921 uint num_to_copy = orig_size - index;
923 uint src_index = orig_size - 1;
924 uint dst_index = src_index + n;
928 copy_element(dst_index, src_index);
937 if (check_for_default_elements_while_copying)
941 if (!(*p == default_element()))
953 set(dst_index++, *p++);
959 inline void insert(uint index, const T &obj)
961 insert(index, &obj, 1);
964 inline void push_front(const T &obj)
969 sparse_vector &append(const sparse_vector &other)
971 VOGL_ASSERT(this != &other);
974 insert(m_size, &other[0], other.m_size);
978 sparse_vector &append(const T *p, uint n)
980 insert(m_size, p, n);
984 // low-level element group access
985 inline uint get_num_groups() const
987 return m_groups.size();
989 inline uint get_num_active_groups() const
991 return m_num_active_groups;
993 inline uint get_group_size() const
998 inline bool is_last_group(uint group_index) const
1000 return (static_cast<int>(group_index) == (static_cast<int>(m_groups.size()) - 1));
1003 inline uint get_group_index(uint element_index)
1005 return element_index >> Log2N;
1007 inline uint get_group_offset(uint element_index)
1009 return element_index & (N - 1);
1012 inline const T *get_group_ptr(uint group_index) const
1014 return m_groups[group_index];
1016 inline T *get_group_ptr(uint group_index)
1018 return m_groups[group_index];
1021 const group_ptr_vec &get_group_ptr_vec() const
1025 group_ptr_vec &get_group_ptr_vec()
1030 inline bool is_group_present(uint group_index) const
1032 return get_group_ptr(group_index) != NULL;
1035 inline uint get_num_valid_elements_in_group(uint group_index) const
1037 VOGL_ASSERT(group_index < m_groups.size());
1039 if (!m_groups.size())
1043 if (static_cast<int>(group_index) == (static_cast<int>(m_groups.size()) - 1))
1044 n = m_size & (N - 1);
1046 return n ? n : static_cast<uint>(N);
1051 uint m_num_active_groups;
1053 group_ptr_vec m_groups;
1055 uint64_t m_default[(sizeof(T) + sizeof(uint64_t) - 1) / sizeof(uint64_t)];
1057 inline T *alloc_group(bool nofail = false)
1059 T *p = static_cast<T *>(base::alloc_space(N * sizeof(T)));
1066 VOGL_FAIL("Out of memory");
1069 base::construct_group(p);
1071 m_num_active_groups++;
1076 inline void free_group(T *p)
1080 VOGL_ASSERT(m_num_active_groups);
1081 m_num_active_groups--;
1083 base::destruct_group(p);
1085 base::free_space(p);
1089 inline void free_groups(uint first_group_to_free, uint num_groups_to_free)
1091 for (uint i = 0; i < num_groups_to_free; i++)
1093 T *p = m_groups[first_group_to_free + i];
1097 m_groups[first_group_to_free + i] = NULL;
1102 // assumes [start, start + num) is a valid group range
1103 inline void get_full_group_range(uint start, uint num, uint &first_full_group, uint &num_full_groups)
1105 const uint num_to_skip = math::minimum(math::get_align_up_value_delta(start, N), num);
1107 start += num_to_skip;
1110 first_full_group = start >> Log2N;
1111 num_full_groups = num >> Log2N;
1114 inline void init_default()
1116 base::construct_element(reinterpret_cast<T *>(m_default));
1119 inline void deinit_default()
1121 base::destruct_element(reinterpret_cast<T *>(m_default));
1125 extern uint g_sparse_vector_test_counters[2];
1127 template <uint counter>
1128 class sparse_vector_test_obj
1131 sparse_vector_test_obj()
1133 g_sparse_vector_test_counters[counter]++;
1136 sparse_vector_test_obj(const sparse_vector_test_obj &)
1138 g_sparse_vector_test_counters[counter]--;
1141 ~sparse_vector_test_obj()
1143 VOGL_ASSERT(g_sparse_vector_test_counters[counter]);
1144 g_sparse_vector_test_counters[counter]--;
1147 bool operator==(const sparse_vector_test_obj &other) const
1149 return this == &other;
1153 inline bool sparse_vector_test(uint seed = 15)
1155 uint num_failures = 0;
1159 #define VOGL_SPARSE_VECTOR_CHECK(x) \
1165 vogl_debug_break_if_debugging(); \
1170 for (uint t = 0; t < 10; t++)
1173 printf("std::vector: ");
1174 timed_scope stopwatch;
1176 std::vector<dynamic_string> t1;
1177 //t1.reserve(100000);
1178 for (uint i = 0; i < 100000; i++)
1181 vogl_sprintf_s(buf, sizeof(buf), "%u", i);
1188 printf("std::vector with reserve: ");
1189 timed_scope stopwatch;
1191 std::vector<dynamic_string> t1;
1193 for (uint i = 0; i < 100000; i++)
1196 vogl_sprintf_s(buf, sizeof(buf), "%u", i);
1203 printf("vogl::vector: ");
1204 timed_scope stopwatch;
1206 vogl::vector<dynamic_string> t1;
1207 //t1.reserve(100000);
1208 for (uint i = 0; i < 100000; i++)
1211 vogl_sprintf_s(buf, sizeof(buf), "%u", i);
1218 printf("vogl::vector with reserve: ");
1219 timed_scope stopwatch;
1221 vogl::vector<dynamic_string> t1;
1223 for (uint i = 0; i < 100000; i++)
1226 vogl_sprintf_s(buf, sizeof(buf), "%u", i);
1232 #define SPARSE_VECTOR_PUSH_BACK_TEST(x) \
1234 printf("vogl::sparse_vector %u, group size %u bytes: ", x, (1U << x) * (uint)sizeof(dynamic_string)); \
1235 timed_scope stopwatch; \
1237 sparse_vector<dynamic_string, x> t2; \
1238 for (uint i = 0; i < 100000; i++) \
1241 vogl_sprintf_s(buf, sizeof(buf), "%u", i); \
1242 t2.push_back(buf); \
1247 SPARSE_VECTOR_PUSH_BACK_TEST(0);
1248 SPARSE_VECTOR_PUSH_BACK_TEST(1);
1249 SPARSE_VECTOR_PUSH_BACK_TEST(2);
1250 SPARSE_VECTOR_PUSH_BACK_TEST(3);
1251 SPARSE_VECTOR_PUSH_BACK_TEST(4);
1252 SPARSE_VECTOR_PUSH_BACK_TEST(5);
1253 SPARSE_VECTOR_PUSH_BACK_TEST(6);
1254 SPARSE_VECTOR_PUSH_BACK_TEST(7);
1255 SPARSE_VECTOR_PUSH_BACK_TEST(8);
1256 SPARSE_VECTOR_PUSH_BACK_TEST(9);
1257 SPARSE_VECTOR_PUSH_BACK_TEST(10);
1258 SPARSE_VECTOR_PUSH_BACK_TEST(11);
1259 SPARSE_VECTOR_PUSH_BACK_TEST(12);
1260 SPARSE_VECTOR_PUSH_BACK_TEST(13);
1261 SPARSE_VECTOR_PUSH_BACK_TEST(14);
1262 #undef SPARSE_VECTOR_PUSH_BACK_TEST
1266 sparse_vector<uint, 2> a1;
1268 VOGL_SPARSE_VECTOR_CHECK(a1.check());
1270 for (uint i = 0; i < 16; i++)
1273 const uint *q = &a1[0];
1274 VOGL_NOTE_UNUSED(q);
1276 VOGL_NOTE_UNUSED(p);
1277 const uint &x1 = a1[0];
1278 VOGL_NOTE_UNUSED(x1);
1279 uint &x2 = a1.get_or_create_element(0);
1280 VOGL_NOTE_UNUSED(x2);
1282 for (uint i = 0; i < 16; i++)
1285 VOGL_SPARSE_VECTOR_CHECK(a1.check());
1287 VOGL_SPARSE_VECTOR_CHECK(a1.size() == 16);
1288 VOGL_SPARSE_VECTOR_CHECK(a1.get_num_active_groups() == 4);
1290 for (uint i = 0; i < 16; i++)
1291 VOGL_SPARSE_VECTOR_CHECK(a1[i] == i);
1293 const sparse_vector<uint, 2> a1_const(a1);
1294 for (uint i = 0; i < 16; i++)
1295 VOGL_SPARSE_VECTOR_CHECK(a1_const[i] == i);
1296 for (uint i = 0; i < 16; i++)
1297 VOGL_SPARSE_VECTOR_CHECK(a1_const.at(i) == i);
1299 a1.invalidate_range(1, 9);
1300 VOGL_SPARSE_VECTOR_CHECK(a1.get_num_active_groups() == 3);
1301 VOGL_SPARSE_VECTOR_CHECK(a1.check());
1303 for (uint i = 0; i < 16; i++)
1305 if ((i >= 1) && (i <= 9))
1306 VOGL_SPARSE_VECTOR_CHECK(a1[i] == a1.default_element());
1308 VOGL_SPARSE_VECTOR_CHECK(a1[i] == i);
1311 a1.invalidate_all();
1312 VOGL_SPARSE_VECTOR_CHECK(a1.get_num_active_groups() == 0);
1313 VOGL_SPARSE_VECTOR_CHECK(a1.check());
1315 for (uint i = 0; i < 16; i++)
1316 VOGL_SPARSE_VECTOR_CHECK(a1[i] == a1.default_element());
1320 sparse_vector<uint, 0> a1;
1322 VOGL_SPARSE_VECTOR_CHECK(a1.check());
1324 for (uint i = 0; i < 16; i++)
1327 const uint *q = &a1[0];
1328 VOGL_NOTE_UNUSED(q);
1330 VOGL_NOTE_UNUSED(p);
1331 const uint &x1 = a1[0];
1332 VOGL_NOTE_UNUSED(x1);
1333 uint &x2 = a1.get_or_create_element(0);
1334 VOGL_NOTE_UNUSED(x2);
1336 for (uint i = 0; i < 16; i++)
1339 VOGL_SPARSE_VECTOR_CHECK(a1.check());
1341 VOGL_SPARSE_VECTOR_CHECK(a1.size() == 16);
1342 VOGL_SPARSE_VECTOR_CHECK(a1.get_num_active_groups() == 16);
1344 for (uint i = 0; i < 16; i++)
1345 VOGL_SPARSE_VECTOR_CHECK(a1[i] == i);
1347 const sparse_vector<uint, 0> a1_const(a1);
1348 for (uint i = 0; i < 16; i++)
1349 VOGL_SPARSE_VECTOR_CHECK(a1_const[i] == i);
1350 for (uint i = 0; i < 16; i++)
1351 VOGL_SPARSE_VECTOR_CHECK(a1_const.at(i) == i);
1353 a1.invalidate_range(1, 9);
1354 VOGL_SPARSE_VECTOR_CHECK(a1.get_num_active_groups() == 7);
1355 VOGL_SPARSE_VECTOR_CHECK(a1.check());
1357 for (uint i = 0; i < 16; i++)
1359 if ((i >= 1) && (i <= 9))
1360 VOGL_SPARSE_VECTOR_CHECK(a1[i] == a1.default_element());
1362 VOGL_SPARSE_VECTOR_CHECK(a1[i] == i);
1365 a1.invalidate_all();
1366 VOGL_SPARSE_VECTOR_CHECK(a1.get_num_active_groups() == 0);
1367 VOGL_SPARSE_VECTOR_CHECK(a1.check());
1369 for (uint i = 0; i < 16; i++)
1370 VOGL_SPARSE_VECTOR_CHECK(a1[i] == a1.default_element());
1374 sparse_vector<sparse_vector_test_obj<0>, 2> blah;
1376 VOGL_SPARSE_VECTOR_CHECK(g_sparse_vector_test_counters[0] == 1);
1379 for (uint i = 0; i < 16; i++)
1380 blah.set(i, sparse_vector_test_obj<0>());
1382 VOGL_SPARSE_VECTOR_CHECK(g_sparse_vector_test_counters[0] == 17);
1386 VOGL_SPARSE_VECTOR_CHECK(g_sparse_vector_test_counters[0] == 13);
1388 for (uint i = 4; i < 8; i++)
1389 blah.set(i, blah.default_element());
1390 blah.optimize_groups();
1391 VOGL_SPARSE_VECTOR_CHECK(g_sparse_vector_test_counters[0] == 13);
1393 blah.insert(4, sparse_vector_test_obj<0>());
1394 VOGL_SPARSE_VECTOR_CHECK(g_sparse_vector_test_counters[0] == 17); // 17, because the sparse_vector had to add a new group to the end and groups are always fully constructed
1398 VOGL_SPARSE_VECTOR_CHECK(g_sparse_vector_test_counters[0] == 1);
1401 blah.allocate_all_groups();
1403 VOGL_SPARSE_VECTOR_CHECK(g_sparse_vector_test_counters[0] == 257);
1405 blah.erase(0, blah.size());
1407 VOGL_SPARSE_VECTOR_CHECK(g_sparse_vector_test_counters[0] == 1);
1410 for (uint iter = 0; iter < 10000; iter++)
1412 uint n = r.irand_inclusive(0, 100000);
1413 uint j = r.irand_inclusive(0, math::clamp<uint>(n / 30, 1, n));
1415 vogl::vector<uint> a1(n);
1416 sparse_vector<uint, 6> a2;
1417 sparse_vector<uint, 6> a4;
1419 VOGL_SPARSE_VECTOR_CHECK(a2.check());
1421 for (uint m = 0; m < j; m++)
1423 uint pos = r.irand(0, n);
1428 VOGL_SPARSE_VECTOR_CHECK(a2.check());
1432 VOGL_SPARSE_VECTOR_CHECK(a2.check());
1434 a2.optimize_groups();
1436 VOGL_SPARSE_VECTOR_CHECK(a2.check());
1438 a2.allocate_all_groups();
1440 VOGL_SPARSE_VECTOR_CHECK(a2.check());
1442 a2.optimize_groups();
1444 VOGL_SPARSE_VECTOR_CHECK(a2.check());
1450 sparse_vector<uint, 8> k5(k4);
1451 VOGL_SPARSE_VECTOR_CHECK(k5 == a4);
1453 k5.assign(k4, true);
1454 VOGL_SPARSE_VECTOR_CHECK(k5 == a4);
1456 sparse_vector<uint, 6> a3(a2);
1458 VOGL_SPARSE_VECTOR_CHECK(a2 == a3);
1459 VOGL_SPARSE_VECTOR_CHECK(!(a2 < a3));
1460 VOGL_SPARSE_VECTOR_CHECK(!(a3 < a2));
1462 for (uint m = 0; m < n; m++)
1464 VOGL_SPARSE_VECTOR_CHECK(a1[m] == a2[m]);
1467 for (uint m = 0; m < n; m++)
1469 VOGL_SPARSE_VECTOR_CHECK(a1[a1.size() - 1] == a2[a2.size() - 1]);
1475 VOGL_SPARSE_VECTOR_CHECK(a2.check());
1477 a3.allocate_all_groups();
1480 VOGL_SPARSE_VECTOR_CHECK(a2 == a3);
1481 VOGL_SPARSE_VECTOR_CHECK(!(a2 < a3));
1482 VOGL_SPARSE_VECTOR_CHECK(!(a3 < a2));
1484 VOGL_SPARSE_VECTOR_CHECK(a3.check());
1488 VOGL_SPARSE_VECTOR_CHECK(a2.check());
1490 a2.optimize_groups();
1492 VOGL_SPARSE_VECTOR_CHECK(a2.check());
1495 vogl::vector<uint> shadow(a4.size());
1496 for (uint i = 0; i < a4.size(); i++)
1499 for (uint m = 0; m < a4.size(); m++)
1501 VOGL_SPARSE_VECTOR_CHECK(a4[m] == shadow[m]);
1504 vogl::vector<uint> vals;
1507 uint k = r.irand(0, math::minimum<uint>(16, n / 4));
1508 while ((k) && (a4.size()))
1510 uint s = r.irand(0, a4.size());
1511 uint l = r.irand_inclusive(1, a4.size() - s);
1521 for (uint i = 0; i < l; i++)
1522 vals[i] = r.urand32();
1524 shadow.insert(s, vals.get_ptr(), l);
1525 a4.insert(s, vals.get_ptr(), l);
1528 VOGL_SPARSE_VECTOR_CHECK(a4.check());
1529 VOGL_SPARSE_VECTOR_CHECK(shadow.size() == a4.size());
1531 for (uint m = 0; m < a4.size(); m++)
1533 VOGL_SPARSE_VECTOR_CHECK(a4[m] == shadow[m]);
1541 sparse_vector<uint, 0> a5(a4.size());
1544 vogl::vector<uint> shadow(a5.size());
1545 for (uint i = 0; i < a5.size(); i++)
1548 for (uint m = 0; m < a5.size(); m++)
1550 VOGL_SPARSE_VECTOR_CHECK(a5[m] == shadow[m]);
1553 vogl::vector<uint> vals;
1556 uint k = r.irand(0, math::minimum<uint>(16, n / 4));
1557 while ((k) && (a5.size()))
1559 uint s = r.irand(0, a5.size());
1560 uint l = r.irand_inclusive(1, a5.size() - s);
1570 for (uint i = 0; i < l; i++)
1571 vals[i] = r.urand32();
1573 shadow.insert(s, vals.get_ptr(), l);
1574 a5.insert(s, vals.get_ptr(), l);
1577 VOGL_SPARSE_VECTOR_CHECK(a5.check());
1578 VOGL_SPARSE_VECTOR_CHECK(shadow.size() == a5.size());
1580 for (uint m = 0; m < a5.size(); m++)
1582 VOGL_SPARSE_VECTOR_CHECK(a5[m] == shadow[m]);
1590 sparse_vector<uint *, 2> z1;
1594 VOGL_SPARSE_VECTOR_CHECK(*z1[0] == 5);
1596 sparse_vector<uint *, 4> z2(z1);
1597 sparse_vector<uint *, 4> z3;
1601 sparse_vector<dynamic_string, 4> j1;
1602 j1.push_back("blah");
1603 const sparse_vector<dynamic_string, 4> &j2 = j1;
1605 j1(0) = dynamic_string("cool");
1609 if ((iter & 255) == 0)
1610 printf("%u\n", iter);
1613 #undef VOGL_SPARSE_VECTOR_CHECK
1615 return !num_failures;