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
28 #include "vogl_core.h"
29 #include "vogl_sparse_bit_array.h"
33 // TODO: This is for the sparse_array class.
34 uint g_sparse_vector_test_counters[2];
36 sparse_bit_array::sparse_bit_array()
37 : m_num_groups(0), m_ppGroups(NULL)
41 sparse_bit_array::sparse_bit_array(uint size)
42 : m_num_groups(0), m_ppGroups(NULL)
47 sparse_bit_array::sparse_bit_array(sparse_bit_array &other)
49 m_num_groups = other.m_num_groups;
50 m_ppGroups = (uint32 **)vogl_malloc(m_num_groups * sizeof(uint32 *));
51 VOGL_VERIFY(m_ppGroups);
53 for (uint i = 0; i < m_num_groups; i++)
55 if (other.m_ppGroups[i])
57 m_ppGroups[i] = alloc_group(false);
58 memcpy(m_ppGroups[i], other.m_ppGroups[i], cBytesPerGroup);
65 sparse_bit_array::~sparse_bit_array()
70 sparse_bit_array &sparse_bit_array::operator=(sparse_bit_array &other)
75 if (m_num_groups != other.m_num_groups)
79 m_num_groups = other.m_num_groups;
80 m_ppGroups = (uint32 **)vogl_calloc(m_num_groups, sizeof(uint32 *));
81 VOGL_VERIFY(m_ppGroups);
84 for (uint i = 0; i < m_num_groups; i++)
86 if (other.m_ppGroups[i])
89 m_ppGroups[i] = alloc_group(false);
90 memcpy(m_ppGroups[i], other.m_ppGroups[i], cBytesPerGroup);
92 else if (m_ppGroups[i])
94 free_group(m_ppGroups[i]);
102 void sparse_bit_array::clear()
107 for (uint i = 0; i < m_num_groups; i++)
108 free_group(m_ppGroups[i]);
110 vogl_free(m_ppGroups);
116 void sparse_bit_array::swap(sparse_bit_array &other)
118 utils::swap(m_ppGroups, other.m_ppGroups);
119 utils::swap(m_num_groups, other.m_num_groups);
122 void sparse_bit_array::optimize()
124 for (uint i = 0; i < m_num_groups; i++)
126 uint32 *s = m_ppGroups[i];
130 for (j = 0; j < cDWORDsPerGroup; j++)
133 if (j == cDWORDsPerGroup)
136 m_ppGroups[i] = NULL;
142 void sparse_bit_array::set_bit_range(uint index, uint num)
144 VOGL_ASSERT((index + num) <= (m_num_groups << cBitsPerGroupShift));
154 while ((index & cBitsPerGroupMask) || (num <= cBitsPerGroup))
156 uint group_index = index >> cBitsPerGroupShift;
157 VOGL_ASSERT(group_index < m_num_groups);
159 uint32 *pGroup = m_ppGroups[group_index];
162 pGroup = alloc_group(true);
163 m_ppGroups[group_index] = pGroup;
166 const uint group_bit_ofs = index & cBitsPerGroupMask;
168 const uint dword_bit_ofs = group_bit_ofs & 31;
169 const uint max_bits_to_set = 32 - dword_bit_ofs;
171 const uint bits_to_set = math::minimum(max_bits_to_set, num);
172 const uint32 msk = (0xFFFFFFFFU >> (32 - bits_to_set));
174 pGroup[group_bit_ofs >> 5] |= (msk << dword_bit_ofs);
180 index += bits_to_set;
183 while (num >= cBitsPerGroup)
185 uint group_index = index >> cBitsPerGroupShift;
186 VOGL_ASSERT(group_index < m_num_groups);
188 uint32 *pGroup = m_ppGroups[group_index];
191 pGroup = alloc_group(true);
192 m_ppGroups[group_index] = pGroup;
195 memset(pGroup, 0xFF, sizeof(uint32) * cDWORDsPerGroup);
197 num -= cBitsPerGroup;
198 index += cBitsPerGroup;
203 uint group_index = index >> cBitsPerGroupShift;
204 VOGL_ASSERT(group_index < m_num_groups);
206 uint32 *pGroup = m_ppGroups[group_index];
209 pGroup = alloc_group(true);
210 m_ppGroups[group_index] = pGroup;
213 uint group_bit_ofs = index & cBitsPerGroupMask;
215 uint bits_to_set = math::minimum(32U, num);
216 uint32 msk = (0xFFFFFFFFU >> (32 - bits_to_set));
218 pGroup[group_bit_ofs >> 5] |= (msk << (group_bit_ofs & 31));
221 index += bits_to_set;
225 void sparse_bit_array::clear_all_bits()
227 for (uint i = 0; i < m_num_groups; i++)
229 uint32 *pGroup = m_ppGroups[i];
231 memset(pGroup, 0, sizeof(uint32) * cDWORDsPerGroup);
235 void sparse_bit_array::clear_bit_range(uint index, uint num)
237 VOGL_ASSERT((index + num) <= (m_num_groups << cBitsPerGroupShift));
247 while ((index & cBitsPerGroupMask) || (num <= cBitsPerGroup))
249 uint group_index = index >> cBitsPerGroupShift;
250 VOGL_ASSERT(group_index < m_num_groups);
252 const uint group_bit_ofs = index & cBitsPerGroupMask;
254 const uint dword_bit_ofs = group_bit_ofs & 31;
255 const uint max_bits_to_set = 32 - dword_bit_ofs;
257 const uint bits_to_set = math::minimum(max_bits_to_set, num);
259 uint32 *pGroup = m_ppGroups[group_index];
262 const uint32 msk = (0xFFFFFFFFU >> (32 - bits_to_set));
264 pGroup[group_bit_ofs >> 5] &= (~(msk << dword_bit_ofs));
271 index += bits_to_set;
274 while (num >= cBitsPerGroup)
276 uint group_index = index >> cBitsPerGroupShift;
277 VOGL_ASSERT(group_index < m_num_groups);
279 uint32 *pGroup = m_ppGroups[group_index];
283 m_ppGroups[group_index] = NULL;
286 num -= cBitsPerGroup;
287 index += cBitsPerGroup;
292 uint group_index = index >> cBitsPerGroupShift;
293 VOGL_ASSERT(group_index < m_num_groups);
295 uint bits_to_set = math::minimum(32u, num);
297 uint32 *pGroup = m_ppGroups[group_index];
300 uint group_bit_ofs = index & cBitsPerGroupMask;
302 uint32 msk = (0xFFFFFFFFU >> (32 - bits_to_set));
304 pGroup[group_bit_ofs >> 5] &= (~(msk << (group_bit_ofs & 31)));
308 index += bits_to_set;
312 void sparse_bit_array::resize(uint size)
314 uint num_groups = (size + cBitsPerGroup - 1) >> cBitsPerGroupShift;
315 if (num_groups == m_num_groups)
324 sparse_bit_array temp;
327 m_num_groups = num_groups;
328 m_ppGroups = (uint32 **)vogl_calloc(m_num_groups, sizeof(uint32 *));
329 VOGL_VERIFY(m_ppGroups);
331 uint n = math::minimum(temp.m_num_groups, m_num_groups);
332 for (uint i = 0; i < n; i++)
334 uint32 *p = temp.m_ppGroups[i];
337 m_ppGroups[i] = temp.m_ppGroups[i];
338 temp.m_ppGroups[i] = NULL;
343 sparse_bit_array &sparse_bit_array::operator&=(const sparse_bit_array &other)
348 VOGL_VERIFY(other.m_num_groups == m_num_groups);
350 for (uint i = 0; i < m_num_groups; i++)
352 uint32 *d = m_ppGroups[i];
355 uint32 *s = other.m_ppGroups[i];
360 m_ppGroups[i] = NULL;
365 for (uint j = 0; j < cDWORDsPerGroup; j++)
367 uint32 c = d[j] & s[j];
374 m_ppGroups[i] = NULL;
382 sparse_bit_array &sparse_bit_array::operator|=(const sparse_bit_array &other)
387 VOGL_VERIFY(other.m_num_groups == m_num_groups);
389 for (uint i = 0; i < m_num_groups; i++)
391 uint32 *s = other.m_ppGroups[i];
395 uint32 *d = m_ppGroups[i];
398 d = alloc_group(true);
400 memcpy(d, s, cBytesPerGroup);
405 for (uint j = 0; j < cDWORDsPerGroup; j++)
407 uint32 c = d[j] | s[j];
414 m_ppGroups[i] = NULL;
422 sparse_bit_array &sparse_bit_array::and_not(const sparse_bit_array &other)
427 VOGL_VERIFY(other.m_num_groups == m_num_groups);
429 for (uint i = 0; i < m_num_groups; i++)
431 uint32 *d = m_ppGroups[i];
434 uint32 *s = other.m_ppGroups[i];
439 for (uint j = 0; j < cDWORDsPerGroup; j++)
441 uint32 c = d[j] & (~s[j]);
448 m_ppGroups[i] = NULL;
455 int sparse_bit_array::find_first_set_bit(uint index, uint num) const
457 VOGL_ASSERT((index + num) <= (m_num_groups << cBitsPerGroupShift));
462 while ((index & cBitsPerGroupMask) || (num <= cBitsPerGroup))
464 uint group_index = index >> cBitsPerGroupShift;
465 VOGL_ASSERT(group_index < m_num_groups);
467 const uint group_bit_ofs = index & cBitsPerGroupMask;
468 const uint dword_bit_ofs = group_bit_ofs & 31;
470 const uint max_bits_to_examine = 32 - dword_bit_ofs;
471 const uint bits_to_examine = math::minimum(max_bits_to_examine, num);
473 uint32 *pGroup = m_ppGroups[group_index];
476 const uint32 msk = (0xFFFFFFFFU >> (32 - bits_to_examine));
478 uint bits = pGroup[group_bit_ofs >> 5] & (msk << dword_bit_ofs);
481 uint num_trailing_zeros = math::count_trailing_zero_bits(bits);
482 int set_index = num_trailing_zeros + (index & ~31);
483 VOGL_ASSERT(get_bit(set_index));
488 num -= bits_to_examine;
492 index += bits_to_examine;
495 while (num >= cBitsPerGroup)
497 uint group_index = index >> cBitsPerGroupShift;
498 VOGL_ASSERT(group_index < m_num_groups);
500 uint32 *pGroup = m_ppGroups[group_index];
503 for (uint i = 0; i < cDWORDsPerGroup; i++)
505 uint32 bits = pGroup[i];
508 uint num_trailing_zeros = math::count_trailing_zero_bits(bits);
510 int set_index = num_trailing_zeros + index + (i << 5);
511 VOGL_ASSERT(get_bit(set_index));
517 num -= cBitsPerGroup;
518 index += cBitsPerGroup;
523 uint group_index = index >> cBitsPerGroupShift;
524 VOGL_ASSERT(group_index < m_num_groups);
526 uint bits_to_examine = math::minimum(32U, num);
528 uint32 *pGroup = m_ppGroups[group_index];
531 uint group_bit_ofs = index & cBitsPerGroupMask;
533 uint32 msk = (0xFFFFFFFFU >> (32 - bits_to_examine));
535 uint32 bits = pGroup[group_bit_ofs >> 5] & (msk << (group_bit_ofs & 31));
538 uint num_trailing_zeros = math::count_trailing_zero_bits(bits);
540 int set_index = num_trailing_zeros + (index & ~31);
541 VOGL_ASSERT(get_bit(set_index));
546 num -= bits_to_examine;
547 index += bits_to_examine;