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

   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 #pragma once
  29
  30 #include "vogl_core.h"
  31
  32 namespace vogl
  33 {
  34     class sparse_bit_array
  35     {
  36     public:
  37         sparse_bit_array();
  38         sparse_bit_array(uint size);
  39         sparse_bit_array(sparse_bit_array &other);
  40         ~sparse_bit_array();
  41
  42         sparse_bit_array &operator=(sparse_bit_array &other);
  43
  44         void clear();
  45
  46         inline uint get_size()
  47         {
  48             return (m_num_groups << cBitsPerGroupShift);
  49         }
  50
  51         void resize(uint size);
  52
  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);
  56
  57         void swap(sparse_bit_array &other);
  58
  59         void optimize();
  60
  61         void set_bit_range(uint index, uint num);
  62         void clear_bit_range(uint index, uint num);
  63
  64         void clear_all_bits();
  65
  66         inline void set_bit(uint index)
  67         {
  68             uint group_index = index >> cBitsPerGroupShift;
  69             VOGL_ASSERT(group_index < m_num_groups);
  70
  71             uint32 *pGroup = m_ppGroups[group_index];
  72             if (!pGroup)
  73             {
  74                 pGroup = alloc_group(true);
  75                 m_ppGroups[group_index] = pGroup;
  76             }
  77
  78             uint bit_ofs = index & (cBitsPerGroup - 1);
  79
  80             pGroup[bit_ofs >> 5] |= (1U << (bit_ofs & 31));
  81         }
  82
  83         inline void clear_bit(uint index)
  84         {
  85             uint group_index = index >> cBitsPerGroupShift;
  86             VOGL_ASSERT(group_index < m_num_groups);
  87
  88             uint32 *pGroup = m_ppGroups[group_index];
  89             if (!pGroup)
  90             {
  91                 pGroup = alloc_group(true);
  92                 m_ppGroups[group_index] = pGroup;
  93             }
  94
  95             uint bit_ofs = index & (cBitsPerGroup - 1);
  96
  97             pGroup[bit_ofs >> 5] &= (~(1U << (bit_ofs & 31)));
  98         }
  99
 100         inline void set(uint index, bool value)
 101         {
 102             uint group_index = index >> cBitsPerGroupShift;
 103             VOGL_ASSERT(group_index < m_num_groups);
 104
 105             uint32 *pGroup = m_ppGroups[group_index];
 106             if (!pGroup)
 107             {
 108                 pGroup = alloc_group(true);
 109                 m_ppGroups[group_index] = pGroup;
 110             }
 111
 112             uint bit_ofs = index & (cBitsPerGroup - 1);
 113
 114             uint bit = (1U << (bit_ofs & 31));
 115
 116             uint c = pGroup[bit_ofs >> 5];
 117             uint mask = (uint)(-(int)value);
 118
 119             pGroup[bit_ofs >> 5] = (c & ~bit) | (mask & bit);
 120         }
 121
 122         inline bool get_bit(uint index) const
 123         {
 124             uint group_index = index >> cBitsPerGroupShift;
 125             VOGL_ASSERT(group_index < m_num_groups);
 126
 127             uint32 *pGroup = m_ppGroups[group_index];
 128             if (!pGroup)
 129                 return 0;
 130
 131             uint bit_ofs = index & (cBitsPerGroup - 1);
 132
 133             uint bit = (1U << (bit_ofs & 31));
 134
 135             return (pGroup[bit_ofs >> 5] & bit) != 0;
 136         }
 137
 138         inline bool operator[](uint index) const
 139         {
 140             return get_bit(index);
 141         }
 142
 143         inline uint32 get_uint32(uint index) const
 144         {
 145             uint group_index = index >> cBitsPerGroupShift;
 146             VOGL_ASSERT(group_index < m_num_groups);
 147
 148             uint32 *pGroup = m_ppGroups[group_index];
 149             if (!pGroup)
 150                 return 0;
 151
 152             uint bit_ofs = index & (cBitsPerGroup - 1);
 153
 154             return pGroup[bit_ofs >> 5];
 155         }
 156
 157         inline void set_uint32(uint index, uint32 value) const
 158         {
 159             uint group_index = index >> cBitsPerGroupShift;
 160             VOGL_ASSERT(group_index < m_num_groups);
 161
 162             uint32 *pGroup = m_ppGroups[group_index];
 163             if (!pGroup)
 164             {
 165                 pGroup = alloc_group(true);
 166                 m_ppGroups[group_index] = pGroup;
 167             }
 168
 169             uint bit_ofs = index & (cBitsPerGroup - 1);
 170
 171             pGroup[bit_ofs >> 5] = value;
 172         }
 173
 174         int find_first_set_bit(uint index, uint num) const;
 175
 176         enum
 177         {
 178             cDWORDsPerGroupShift = 4U,
 179             cDWORDsPerGroup = 1U << cDWORDsPerGroupShift,
 180             cBitsPerGroupShift = cDWORDsPerGroupShift + 5,
 181             cBitsPerGroup = 1U << cBitsPerGroupShift,
 182             cBitsPerGroupMask = cBitsPerGroup - 1U,
 183             cBytesPerGroup = cDWORDsPerGroup * sizeof(uint32)
 184         };
 185
 186         uint get_num_groups() const
 187         {
 188             return m_num_groups;
 189         }
 190         uint32 **get_groups()
 191         {
 192             return m_ppGroups;
 193         }
 194
 195     private:
 196         uint m_num_groups;
 197         uint32 **m_ppGroups;
 198
 199         static inline uint32 *alloc_group(bool clear)
 200         {
 201             uint32 *p = (uint32 *)vogl_malloc(cBytesPerGroup);
 202             VOGL_VERIFY(p);
 203             if (clear)
 204                 memset(p, 0, cBytesPerGroup);
 205             return p;
 206         }
 207
 208         static inline void free_group(void *p)
 209         {
 210             if (p)
 211                 vogl_free(p);
 212         }
 213     };
 214
 215 } // namespace vogl