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_bit_array.h
30 #include "vogl_core.h"
34 class sparse_bit_array
38 sparse_bit_array(uint size);
39 sparse_bit_array(sparse_bit_array &other);
42 sparse_bit_array &operator=(sparse_bit_array &other);
46 inline uint get_size()
48 return (m_num_groups << cBitsPerGroupShift);
51 void resize(uint size);
53 sparse_bit_array &operator&=(const sparse_bit_array &other);
54 sparse_bit_array &operator|=(const sparse_bit_array &other);
55 sparse_bit_array &and_not(const sparse_bit_array &other);
57 void swap(sparse_bit_array &other);
61 void set_bit_range(uint index, uint num);
62 void clear_bit_range(uint index, uint num);
64 void clear_all_bits();
66 inline void set_bit(uint index)
68 uint group_index = index >> cBitsPerGroupShift;
69 VOGL_ASSERT(group_index < m_num_groups);
71 uint32 *pGroup = m_ppGroups[group_index];
74 pGroup = alloc_group(true);
75 m_ppGroups[group_index] = pGroup;
78 uint bit_ofs = index & (cBitsPerGroup - 1);
80 pGroup[bit_ofs >> 5] |= (1U << (bit_ofs & 31));
83 inline void clear_bit(uint index)
85 uint group_index = index >> cBitsPerGroupShift;
86 VOGL_ASSERT(group_index < m_num_groups);
88 uint32 *pGroup = m_ppGroups[group_index];
91 pGroup = alloc_group(true);
92 m_ppGroups[group_index] = pGroup;
95 uint bit_ofs = index & (cBitsPerGroup - 1);
97 pGroup[bit_ofs >> 5] &= (~(1U << (bit_ofs & 31)));
100 inline void set(uint index, bool value)
102 uint group_index = index >> cBitsPerGroupShift;
103 VOGL_ASSERT(group_index < m_num_groups);
105 uint32 *pGroup = m_ppGroups[group_index];
108 pGroup = alloc_group(true);
109 m_ppGroups[group_index] = pGroup;
112 uint bit_ofs = index & (cBitsPerGroup - 1);
114 uint bit = (1U << (bit_ofs & 31));
116 uint c = pGroup[bit_ofs >> 5];
117 uint mask = (uint)(-(int)value);
119 pGroup[bit_ofs >> 5] = (c & ~bit) | (mask & bit);
122 inline bool get_bit(uint index) const
124 uint group_index = index >> cBitsPerGroupShift;
125 VOGL_ASSERT(group_index < m_num_groups);
127 uint32 *pGroup = m_ppGroups[group_index];
131 uint bit_ofs = index & (cBitsPerGroup - 1);
133 uint bit = (1U << (bit_ofs & 31));
135 return (pGroup[bit_ofs >> 5] & bit) != 0;
138 inline bool operator[](uint index) const
140 return get_bit(index);
143 inline uint32 get_uint32(uint index) const
145 uint group_index = index >> cBitsPerGroupShift;
146 VOGL_ASSERT(group_index < m_num_groups);
148 uint32 *pGroup = m_ppGroups[group_index];
152 uint bit_ofs = index & (cBitsPerGroup - 1);
154 return pGroup[bit_ofs >> 5];
157 inline void set_uint32(uint index, uint32 value) const
159 uint group_index = index >> cBitsPerGroupShift;
160 VOGL_ASSERT(group_index < m_num_groups);
162 uint32 *pGroup = m_ppGroups[group_index];
165 pGroup = alloc_group(true);
166 m_ppGroups[group_index] = pGroup;
169 uint bit_ofs = index & (cBitsPerGroup - 1);
171 pGroup[bit_ofs >> 5] = value;
174 int find_first_set_bit(uint index, uint num) const;
178 cDWORDsPerGroupShift = 4U,
179 cDWORDsPerGroup = 1U << cDWORDsPerGroupShift,
180 cBitsPerGroupShift = cDWORDsPerGroupShift + 5,
181 cBitsPerGroup = 1U << cBitsPerGroupShift,
182 cBitsPerGroupMask = cBitsPerGroup - 1U,
183 cBytesPerGroup = cDWORDsPerGroup * sizeof(uint32)
186 uint get_num_groups() const
190 uint32 **get_groups()
199 static inline uint32 *alloc_group(bool clear)
201 uint32 *p = (uint32 *)vogl_malloc(cBytesPerGroup);
204 memset(p, 0, cBytesPerGroup);
208 static inline void free_group(void *p)