git.cworth.org Git - vogl/blob - src/voglcore/vogl_sparse_bit_array.cpp

   1 /**************************************************************************
   2  *
   3  * Copyright 2013-2014 RAD Game Tools and Valve Software
   4  * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
   5  * All Rights Reserved.
   6  *
   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:
  13  *
  14  * The above copyright notice and this permission notice shall be included in
  15  * all copies or substantial portions of the Software.
  16  *
  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
  23  * THE SOFTWARE.
  24  *
  25  **************************************************************************/
  26
  27 // File: vogl_sparse_bit_array.h
  28 #include "vogl_core.h"
  29 #include "vogl_sparse_bit_array.h"
  30
  31 namespace vogl
  32 {
  33     // TODO: This is for the sparse_array class.
  34     uint g_sparse_vector_test_counters[2];
  35
  36     sparse_bit_array::sparse_bit_array()
  37         : m_num_groups(0), m_ppGroups(NULL)
  38     {
  39     }
  40
  41     sparse_bit_array::sparse_bit_array(uint size)
  42         : m_num_groups(0), m_ppGroups(NULL)
  43     {
  44         resize(size);
  45     }
  46
  47     sparse_bit_array::sparse_bit_array(sparse_bit_array &other)
  48     {
  49         m_num_groups = other.m_num_groups;
  50         m_ppGroups = (uint32 **)vogl_malloc(m_num_groups * sizeof(uint32 *));
  51         VOGL_VERIFY(m_ppGroups);
  52
  53         for (uint i = 0; i < m_num_groups; i++)
  54         {
  55             if (other.m_ppGroups[i])
  56             {
  57                 m_ppGroups[i] = alloc_group(false);
  58                 memcpy(m_ppGroups[i], other.m_ppGroups[i], cBytesPerGroup);
  59             }
  60             else
  61                 m_ppGroups[i] = NULL;
  62         }
  63     }
  64
  65     sparse_bit_array::~sparse_bit_array()
  66     {
  67         clear();
  68     }
  69
  70     sparse_bit_array &sparse_bit_array::operator=(sparse_bit_array &other)
  71     {
  72         if (this == &other)
  73             return *this;
  74
  75         if (m_num_groups != other.m_num_groups)
  76         {
  77             clear();
  78
  79             m_num_groups = other.m_num_groups;
  80             m_ppGroups = (uint32 **)vogl_calloc(m_num_groups, sizeof(uint32 *));
  81             VOGL_VERIFY(m_ppGroups);
  82         }
  83
  84         for (uint i = 0; i < m_num_groups; i++)
  85         {
  86             if (other.m_ppGroups[i])
  87             {
  88                 if (!m_ppGroups[i])
  89                     m_ppGroups[i] = alloc_group(false);
  90                 memcpy(m_ppGroups[i], other.m_ppGroups[i], cBytesPerGroup);
  91             }
  92             else if (m_ppGroups[i])
  93             {
  94                 free_group(m_ppGroups[i]);
  95                 m_ppGroups[i] = NULL;
  96             }
  97         }
  98
  99         return *this;
 100     }
 101
 102     void sparse_bit_array::clear()
 103     {
 104         if (!m_num_groups)
 105             return;
 106
 107         for (uint i = 0; i < m_num_groups; i++)
 108             free_group(m_ppGroups[i]);
 109
 110         vogl_free(m_ppGroups);
 111         m_ppGroups = NULL;
 112
 113         m_num_groups = 0;
 114     }
 115
 116     void sparse_bit_array::swap(sparse_bit_array &other)
 117     {
 118         utils::swap(m_ppGroups, other.m_ppGroups);
 119         utils::swap(m_num_groups, other.m_num_groups);
 120     }
 121
 122     void sparse_bit_array::optimize()
 123     {
 124         for (uint i = 0; i < m_num_groups; i++)
 125         {
 126             uint32 *s = m_ppGroups[i];
 127             if (s)
 128             {
 129                 uint j;
 130                 for (j = 0; j < cDWORDsPerGroup; j++)
 131                     if (s[j])
 132                         break;
 133                 if (j == cDWORDsPerGroup)
 134                 {
 135                     free_group(s);
 136                     m_ppGroups[i] = NULL;
 137                 }
 138             }
 139         }
 140     }
 141
 142     void sparse_bit_array::set_bit_range(uint index, uint num)
 143     {
 144         VOGL_ASSERT((index + num) <= (m_num_groups << cBitsPerGroupShift));
 145
 146         if (!num)
 147             return;
 148         else if (num == 1)
 149         {
 150             set_bit(index);
 151             return;
 152         }
 153
 154         while ((index & cBitsPerGroupMask) || (num <= cBitsPerGroup))
 155         {
 156             uint group_index = index >> cBitsPerGroupShift;
 157             VOGL_ASSERT(group_index < m_num_groups);
 158
 159             uint32 *pGroup = m_ppGroups[group_index];
 160             if (!pGroup)
 161             {
 162                 pGroup = alloc_group(true);
 163                 m_ppGroups[group_index] = pGroup;
 164             }
 165
 166             const uint group_bit_ofs = index & cBitsPerGroupMask;
 167
 168             const uint dword_bit_ofs = group_bit_ofs & 31;
 169             const uint max_bits_to_set = 32 - dword_bit_ofs;
 170
 171             const uint bits_to_set = math::minimum(max_bits_to_set, num);
 172             const uint32 msk = (0xFFFFFFFFU >> (32 - bits_to_set));
 173
 174             pGroup[group_bit_ofs >> 5] |= (msk << dword_bit_ofs);
 175
 176             num -= bits_to_set;
 177             if (!num)
 178                 return;
 179
 180             index += bits_to_set;
 181         }
 182
 183         while (num >= cBitsPerGroup)
 184         {
 185             uint group_index = index >> cBitsPerGroupShift;
 186             VOGL_ASSERT(group_index < m_num_groups);
 187
 188             uint32 *pGroup = m_ppGroups[group_index];
 189             if (!pGroup)
 190             {
 191                 pGroup = alloc_group(true);
 192                 m_ppGroups[group_index] = pGroup;
 193             }
 194
 195             memset(pGroup, 0xFF, sizeof(uint32) * cDWORDsPerGroup);
 196
 197             num -= cBitsPerGroup;
 198             index += cBitsPerGroup;
 199         }
 200
 201         while (num)
 202         {
 203             uint group_index = index >> cBitsPerGroupShift;
 204             VOGL_ASSERT(group_index < m_num_groups);
 205
 206             uint32 *pGroup = m_ppGroups[group_index];
 207             if (!pGroup)
 208             {
 209                 pGroup = alloc_group(true);
 210                 m_ppGroups[group_index] = pGroup;
 211             }
 212
 213             uint group_bit_ofs = index & cBitsPerGroupMask;
 214
 215             uint bits_to_set = math::minimum(32U, num);
 216             uint32 msk = (0xFFFFFFFFU >> (32 - bits_to_set));
 217
 218             pGroup[group_bit_ofs >> 5] |= (msk << (group_bit_ofs & 31));
 219
 220             num -= bits_to_set;
 221             index += bits_to_set;
 222         }
 223     }
 224
 225     void sparse_bit_array::clear_all_bits()
 226     {
 227         for (uint i = 0; i < m_num_groups; i++)
 228         {
 229             uint32 *pGroup = m_ppGroups[i];
 230             if (pGroup)
 231                 memset(pGroup, 0, sizeof(uint32) * cDWORDsPerGroup);
 232         }
 233     }
 234
 235     void sparse_bit_array::clear_bit_range(uint index, uint num)
 236     {
 237         VOGL_ASSERT((index + num) <= (m_num_groups << cBitsPerGroupShift));
 238
 239         if (!num)
 240             return;
 241         else if (num == 1)
 242         {
 243             clear_bit(index);
 244             return;
 245         }
 246
 247         while ((index & cBitsPerGroupMask) || (num <= cBitsPerGroup))
 248         {
 249             uint group_index = index >> cBitsPerGroupShift;
 250             VOGL_ASSERT(group_index < m_num_groups);
 251
 252             const uint group_bit_ofs = index & cBitsPerGroupMask;
 253
 254             const uint dword_bit_ofs = group_bit_ofs & 31;
 255             const uint max_bits_to_set = 32 - dword_bit_ofs;
 256
 257             const uint bits_to_set = math::minimum(max_bits_to_set, num);
 258
 259             uint32 *pGroup = m_ppGroups[group_index];
 260             if (pGroup)
 261             {
 262                 const uint32 msk = (0xFFFFFFFFU >> (32 - bits_to_set));
 263
 264                 pGroup[group_bit_ofs >> 5] &= (~(msk << dword_bit_ofs));
 265             }
 266
 267             num -= bits_to_set;
 268             if (!num)
 269                 return;
 270
 271             index += bits_to_set;
 272         }
 273
 274         while (num >= cBitsPerGroup)
 275         {
 276             uint group_index = index >> cBitsPerGroupShift;
 277             VOGL_ASSERT(group_index < m_num_groups);
 278
 279             uint32 *pGroup = m_ppGroups[group_index];
 280             if (pGroup)
 281             {
 282                 free_group(pGroup);
 283                 m_ppGroups[group_index] = NULL;
 284             }
 285
 286             num -= cBitsPerGroup;
 287             index += cBitsPerGroup;
 288         }
 289
 290         while (num)
 291         {
 292             uint group_index = index >> cBitsPerGroupShift;
 293             VOGL_ASSERT(group_index < m_num_groups);
 294
 295             uint bits_to_set = math::minimum(32u, num);
 296
 297             uint32 *pGroup = m_ppGroups[group_index];
 298             if (pGroup)
 299             {
 300                 uint group_bit_ofs = index & cBitsPerGroupMask;
 301
 302                 uint32 msk = (0xFFFFFFFFU >> (32 - bits_to_set));
 303
 304                 pGroup[group_bit_ofs >> 5] &= (~(msk << (group_bit_ofs & 31)));
 305             }
 306
 307             num -= bits_to_set;
 308             index += bits_to_set;
 309         }
 310     }
 311
 312     void sparse_bit_array::resize(uint size)
 313     {
 314         uint num_groups = (size + cBitsPerGroup - 1) >> cBitsPerGroupShift;
 315         if (num_groups == m_num_groups)
 316             return;
 317
 318         if (!num_groups)
 319         {
 320             clear();
 321             return;
 322         }
 323
 324         sparse_bit_array temp;
 325         temp.swap(*this);
 326
 327         m_num_groups = num_groups;
 328         m_ppGroups = (uint32 **)vogl_calloc(m_num_groups, sizeof(uint32 *));
 329         VOGL_VERIFY(m_ppGroups);
 330
 331         uint n = math::minimum(temp.m_num_groups, m_num_groups);
 332         for (uint i = 0; i < n; i++)
 333         {
 334             uint32 *p = temp.m_ppGroups[i];
 335             if (p)
 336             {
 337                 m_ppGroups[i] = temp.m_ppGroups[i];
 338                 temp.m_ppGroups[i] = NULL;
 339             }
 340         }
 341     }
 342
 343     sparse_bit_array &sparse_bit_array::operator&=(const sparse_bit_array &other)
 344     {
 345         if (this == &other)
 346             return *this;
 347
 348         VOGL_VERIFY(other.m_num_groups == m_num_groups);
 349
 350         for (uint i = 0; i < m_num_groups; i++)
 351         {
 352             uint32 *d = m_ppGroups[i];
 353             if (!d)
 354                 continue;
 355             uint32 *s = other.m_ppGroups[i];
 356
 357             if (!s)
 358             {
 359                 free_group(d);
 360                 m_ppGroups[i] = NULL;
 361             }
 362             else
 363             {
 364                 uint32 oc = 0;
 365                 for (uint j = 0; j < cDWORDsPerGroup; j++)
 366                 {
 367                     uint32 c = d[j] & s[j];
 368                     d[j] = c;
 369                     oc |= c;
 370                 }
 371                 if (!oc)
 372                 {
 373                     free_group(d);
 374                     m_ppGroups[i] = NULL;
 375                 }
 376             }
 377         }
 378
 379         return *this;
 380     }
 381
 382     sparse_bit_array &sparse_bit_array::operator|=(const sparse_bit_array &other)
 383     {
 384         if (this == &other)
 385             return *this;
 386
 387         VOGL_VERIFY(other.m_num_groups == m_num_groups);
 388
 389         for (uint i = 0; i < m_num_groups; i++)
 390         {
 391             uint32 *s = other.m_ppGroups[i];
 392             if (!s)
 393                 continue;
 394
 395             uint32 *d = m_ppGroups[i];
 396             if (!d)
 397             {
 398                 d = alloc_group(true);
 399                 m_ppGroups[i] = d;
 400                 memcpy(d, s, cBytesPerGroup);
 401             }
 402             else
 403             {
 404                 uint32 oc = 0;
 405                 for (uint j = 0; j < cDWORDsPerGroup; j++)
 406                 {
 407                     uint32 c = d[j] | s[j];
 408                     d[j] = c;
 409                     oc |= c;
 410                 }
 411                 if (!oc)
 412                 {
 413                     free_group(d);
 414                     m_ppGroups[i] = NULL;
 415                 }
 416             }
 417         }
 418
 419         return *this;
 420     }
 421
 422     sparse_bit_array &sparse_bit_array::and_not(const sparse_bit_array &other)
 423     {
 424         if (this == &other)
 425             return *this;
 426
 427         VOGL_VERIFY(other.m_num_groups == m_num_groups);
 428
 429         for (uint i = 0; i < m_num_groups; i++)
 430         {
 431             uint32 *d = m_ppGroups[i];
 432             if (!d)
 433                 continue;
 434             uint32 *s = other.m_ppGroups[i];
 435             if (!s)
 436                 continue;
 437
 438             uint32 oc = 0;
 439             for (uint j = 0; j < cDWORDsPerGroup; j++)
 440             {
 441                 uint32 c = d[j] & (~s[j]);
 442                 d[j] = c;
 443                 oc |= c;
 444             }
 445             if (!oc)
 446             {
 447                 free_group(d);
 448                 m_ppGroups[i] = NULL;
 449             }
 450         }
 451
 452         return *this;
 453     }
 454
 455     int sparse_bit_array::find_first_set_bit(uint index, uint num) const
 456     {
 457         VOGL_ASSERT((index + num) <= (m_num_groups << cBitsPerGroupShift));
 458
 459         if (!num)
 460             return -1;
 461
 462         while ((index & cBitsPerGroupMask) || (num <= cBitsPerGroup))
 463         {
 464             uint group_index = index >> cBitsPerGroupShift;
 465             VOGL_ASSERT(group_index < m_num_groups);
 466
 467             const uint group_bit_ofs = index & cBitsPerGroupMask;
 468             const uint dword_bit_ofs = group_bit_ofs & 31;
 469
 470             const uint max_bits_to_examine = 32 - dword_bit_ofs;
 471             const uint bits_to_examine = math::minimum(max_bits_to_examine, num);
 472
 473             uint32 *pGroup = m_ppGroups[group_index];
 474             if (pGroup)
 475             {
 476                 const uint32 msk = (0xFFFFFFFFU >> (32 - bits_to_examine));
 477
 478                 uint bits = pGroup[group_bit_ofs >> 5] & (msk << dword_bit_ofs);
 479                 if (bits)
 480                 {
 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));
 484                     return set_index;
 485                 }
 486             }
 487
 488             num -= bits_to_examine;
 489             if (!num)
 490                 return -1;
 491
 492             index += bits_to_examine;
 493         }
 494
 495         while (num >= cBitsPerGroup)
 496         {
 497             uint group_index = index >> cBitsPerGroupShift;
 498             VOGL_ASSERT(group_index < m_num_groups);
 499
 500             uint32 *pGroup = m_ppGroups[group_index];
 501             if (pGroup)
 502             {
 503                 for (uint i = 0; i < cDWORDsPerGroup; i++)
 504                 {
 505                     uint32 bits = pGroup[i];
 506                     if (bits)
 507                     {
 508                         uint num_trailing_zeros = math::count_trailing_zero_bits(bits);
 509
 510                         int set_index = num_trailing_zeros + index + (i << 5);
 511                         VOGL_ASSERT(get_bit(set_index));
 512                         return set_index;
 513                     }
 514                 }
 515             }
 516
 517             num -= cBitsPerGroup;
 518             index += cBitsPerGroup;
 519         }
 520
 521         while (num)
 522         {
 523             uint group_index = index >> cBitsPerGroupShift;
 524             VOGL_ASSERT(group_index < m_num_groups);
 525
 526             uint bits_to_examine = math::minimum(32U, num);
 527
 528             uint32 *pGroup = m_ppGroups[group_index];
 529             if (pGroup)
 530             {
 531                 uint group_bit_ofs = index & cBitsPerGroupMask;
 532
 533                 uint32 msk = (0xFFFFFFFFU >> (32 - bits_to_examine));
 534
 535                 uint32 bits = pGroup[group_bit_ofs >> 5] & (msk << (group_bit_ofs & 31));
 536                 if (bits)
 537                 {
 538                     uint num_trailing_zeros = math::count_trailing_zero_bits(bits);
 539
 540                     int set_index = num_trailing_zeros + (index & ~31);
 541                     VOGL_ASSERT(get_bit(set_index));
 542                     return set_index;
 543                 }
 544             }
 545
 546             num -= bits_to_examine;
 547             index += bits_to_examine;
 548         }
 549
 550         return -1;
 551     }
 552
 553 } // namespace vogl