1 /*========================== begin_copyright_notice ============================ 2 3 Copyright (C) 2017-2021 Intel Corporation 4 5 SPDX-License-Identifier: MIT 6 7 ============================= end_copyright_notice ===========================*/ 8 9 #ifndef _BITSET_H_ 10 #define _BITSET_H_ 11 12 #include "Mem_Manager.h" 13 #include <cstdlib> 14 #include <cstring> 15 16 // Array-based bitset implementation where each element occupies a single bit. 17 // Inside each array element, bits are stored and indexed from lsb to msb. 18 typedef unsigned int BITSET_ARRAY_TYPE; 19 #define BITS_PER_BYTE 8 20 #define BIT(x) (((BITSET_ARRAY_TYPE)1 ) << x) 21 #define NUM_BITS_PER_ELT ( sizeof(BITSET_ARRAY_TYPE) * BITS_PER_BYTE ) 22 23 class BitSet 24 { 25 public: BitSet()26 BitSet() : m_BitSetArray(nullptr), m_Size(0) {} BitSet(unsigned size,bool defaultValue)27 BitSet(unsigned size, bool defaultValue) 28 { 29 m_BitSetArray = NULL; 30 m_Size = 0; 31 32 create(size); 33 if (defaultValue) 34 { 35 setAll(); 36 } 37 } 38 BitSet(const BitSet & other)39 BitSet(const BitSet &other) : m_BitSetArray(nullptr), m_Size(0) 40 { 41 copy(other); 42 } 43 BitSet(BitSet && other)44 BitSet(BitSet && other) noexcept 45 { 46 m_BitSetArray = other.m_BitSetArray; 47 m_Size = other.m_Size; 48 other.m_BitSetArray = nullptr; 49 other.m_Size = 0; 50 } 51 ~BitSet()52 ~BitSet() { std::free(m_BitSetArray); } 53 resize(unsigned size)54 void resize(unsigned size) { create(size); } clear()55 void clear() 56 { 57 unsigned sizeInBytes = (m_Size + BITS_PER_BYTE - 1) / BITS_PER_BYTE; 58 std::memset(m_BitSetArray, 0, sizeInBytes); 59 } 60 61 void setAll(void); 62 void invert(void); 63 isEmpty()64 bool isEmpty() const 65 { 66 unsigned arraySize = (m_Size + NUM_BITS_PER_ELT - 1) / NUM_BITS_PER_ELT; 67 for (unsigned i = 0; i < arraySize; i++) 68 { 69 if (m_BitSetArray[i] != 0) 70 { 71 return false; 72 } 73 } 74 return true; 75 } 76 isAllset()77 bool isAllset() const 78 { 79 unsigned index; 80 unsigned bound = m_Size / NUM_BITS_PER_ELT; 81 82 for (index = 0; index < bound; index++) 83 { 84 if (~m_BitSetArray[index] != 0) 85 { 86 return false; 87 } 88 } 89 90 unsigned numBitsLeft = m_Size % NUM_BITS_PER_ELT; 91 for (unsigned bitIndex = 0; bitIndex < numBitsLeft; bitIndex++) 92 { 93 if ((m_BitSetArray[index] & BIT(bitIndex)) == 0) 94 { 95 return false; 96 } 97 } 98 99 return true; 100 } 101 102 isSet(unsigned index)103 bool isSet(unsigned index) const 104 { 105 if (index < m_Size) 106 { 107 unsigned arrayIndex = index / NUM_BITS_PER_ELT; 108 unsigned bitIndex = index % NUM_BITS_PER_ELT; 109 return (m_BitSetArray[arrayIndex] & BIT(bitIndex)) != 0; 110 } 111 return false; 112 } 113 isAllSet(unsigned startIndex,unsigned endIndex)114 bool isAllSet(unsigned startIndex, unsigned endIndex) const 115 { 116 MUST_BE_TRUE(startIndex <= endIndex, "Invalid bitSet Index"); 117 MUST_BE_TRUE(startIndex < m_Size, "Invalid bitSet Index"); 118 MUST_BE_TRUE(endIndex < m_Size, "Invalid bitSet Index"); 119 120 unsigned start = startIndex / NUM_BITS_PER_ELT; 121 unsigned end = endIndex / NUM_BITS_PER_ELT; 122 123 if (start == end) 124 { 125 for (unsigned i = startIndex; i <= endIndex; i++) 126 { 127 if (!isSet(i)) 128 { 129 return false; 130 } 131 } 132 return true; 133 } 134 135 unsigned index; 136 unsigned numBitsBefore = startIndex % NUM_BITS_PER_ELT; 137 if (numBitsBefore) 138 { 139 for (unsigned bitIndex = numBitsBefore; bitIndex < NUM_BITS_PER_ELT; bitIndex++) 140 { 141 if ((m_BitSetArray[start] & BIT(bitIndex)) == 0) 142 { 143 return false; 144 } 145 } 146 start++; 147 } 148 149 for (index = start; index < end; index++) 150 { 151 if (~m_BitSetArray[index] != 0) 152 { 153 return false; 154 } 155 } 156 157 unsigned numBitsLeft = endIndex % NUM_BITS_PER_ELT; 158 for (unsigned bitIndex = 0; bitIndex <= numBitsLeft; bitIndex++) 159 { 160 if ((m_BitSetArray[index] & BIT(bitIndex)) == 0) 161 { 162 return false; 163 } 164 } 165 166 return true; 167 } 168 isEmpty(unsigned startIndex,unsigned endIndex)169 bool isEmpty(unsigned startIndex, unsigned endIndex) const 170 { 171 MUST_BE_TRUE(startIndex <= endIndex, "Invalid bitSet Index"); 172 MUST_BE_TRUE(startIndex < m_Size, "Invalid bitSet Index"); 173 MUST_BE_TRUE(endIndex < m_Size, "Invalid bitSet Index"); 174 175 unsigned start = startIndex / NUM_BITS_PER_ELT; 176 unsigned end = endIndex / NUM_BITS_PER_ELT; 177 178 if (start == end) 179 { 180 for (unsigned i = startIndex; i <= endIndex; i++) 181 { 182 if (isSet(i)) 183 { 184 return false; 185 } 186 } 187 return true; 188 } 189 190 unsigned index; 191 unsigned numBitsBefore = startIndex % NUM_BITS_PER_ELT; 192 if (numBitsBefore) 193 { 194 for (unsigned bitIndex = numBitsBefore; bitIndex < NUM_BITS_PER_ELT; bitIndex++) 195 { 196 if ((m_BitSetArray[start] & BIT(bitIndex)) != 0) 197 { 198 return false; 199 } 200 } 201 start++; 202 } 203 204 for (index = start; index < end; index++) 205 { 206 if (m_BitSetArray[index] != 0) 207 { 208 return false; 209 } 210 } 211 212 unsigned numBitsLeft = endIndex % NUM_BITS_PER_ELT; 213 for (unsigned bitIndex = 0; bitIndex <= numBitsLeft; bitIndex++) 214 { 215 if ((m_BitSetArray[index] & BIT(bitIndex)) != 0) 216 { 217 return false; 218 } 219 } 220 221 return true; 222 } 223 getElt(unsigned eltIndex)224 BITSET_ARRAY_TYPE getElt(unsigned eltIndex) const 225 { 226 MUST_BE_TRUE(eltIndex < m_Size, "Invalid bitSet Index"); 227 return m_BitSetArray[eltIndex]; 228 } 229 setElt(unsigned eltIndex,BITSET_ARRAY_TYPE value)230 void setElt(unsigned eltIndex, BITSET_ARRAY_TYPE value) 231 { 232 unsigned bound = (eltIndex + 1) * NUM_BITS_PER_ELT; 233 if (bound > m_Size) 234 { 235 create(bound); 236 } 237 m_BitSetArray[eltIndex] |= value; 238 } 239 resetElt(unsigned eltIndex,BITSET_ARRAY_TYPE value)240 void resetElt(unsigned eltIndex, BITSET_ARRAY_TYPE value) 241 { 242 unsigned bound = (eltIndex + 1) * NUM_BITS_PER_ELT; 243 if (bound > m_Size) 244 { 245 create(bound); 246 } 247 m_BitSetArray[eltIndex] &= ~value; 248 } 249 set(unsigned index,bool value)250 void set(unsigned index, bool value) 251 { 252 // If the index is larger than the size of the BitSet then grow the BitSet 253 if (index >= m_Size) 254 { 255 create(index + 1); 256 } 257 258 unsigned arrayIndex = index / NUM_BITS_PER_ELT; 259 unsigned bitIndex = index % NUM_BITS_PER_ELT; 260 261 if (value) 262 { 263 m_BitSetArray[arrayIndex] |= BIT(bitIndex); 264 } 265 else 266 { 267 m_BitSetArray[arrayIndex] &= ~BIT(bitIndex); 268 } 269 } 270 set(unsigned startIndex,unsigned endIndex)271 void set(unsigned startIndex, unsigned endIndex) 272 { 273 for (unsigned i = startIndex; i <= endIndex; i++) 274 { 275 set(i, true); 276 } 277 } 278 getSize()279 unsigned getSize() const { return m_Size; } 280 281 bool operator==(const BitSet &other) const 282 { 283 if (m_Size == other.m_Size) 284 { 285 unsigned sizeInBytes = (m_Size + BITS_PER_BYTE - 1) / BITS_PER_BYTE; 286 return 0 == std::memcmp(m_BitSetArray, other.m_BitSetArray, sizeInBytes); 287 } 288 return false; 289 } 290 291 bool operator!=(const BitSet &other) const 292 { 293 if (m_Size == other.m_Size) 294 { 295 unsigned sizeInBytes = (m_Size + BITS_PER_BYTE - 1) / BITS_PER_BYTE; 296 return 0 != std::memcmp(m_BitSetArray, other.m_BitSetArray, sizeInBytes); 297 } 298 return true; 299 } 300 301 BitSet& operator= (const BitSet &other) 302 { 303 copy(other); 304 return *this; 305 } 306 307 BitSet& operator=(BitSet&& other) noexcept 308 { 309 if (m_BitSetArray) 310 { 311 std::free(m_BitSetArray); 312 } 313 m_BitSetArray = other.m_BitSetArray; 314 m_Size = other.m_Size; 315 other.m_BitSetArray = nullptr; 316 other.m_Size = 0; 317 318 return *this; 319 } 320 swap(BitSet & other)321 void swap(BitSet &other) 322 { 323 if (this != &other) 324 { 325 std::swap(m_Size, other.m_Size); 326 std::swap(m_BitSetArray, other.m_BitSetArray); 327 } 328 } 329 330 BitSet &operator|=(const BitSet &other); 331 BitSet &operator&=(const BitSet &other); 332 BitSet &operator-=(const BitSet &other); 333 new(size_t sz,vISA::Mem_Manager & m)334 void *operator new(size_t sz, vISA:: 335 Mem_Manager &m) { return m.alloc(sz); } 336 337 // Return the index of the first set bit in the range [begin, end). 338 // Return -1 if all bits in the range are unset. 339 int findFirstIn(unsigned begin, unsigned end) const; 340 // Return the index of the last set bit in the range [begin, end). 341 // Return -1 if all bits in the range are unset. 342 int findLastIn(unsigned begin, unsigned end) const; 343 344 protected: 345 BITSET_ARRAY_TYPE* m_BitSetArray; 346 unsigned m_Size; 347 348 void create(unsigned size); copy(const BitSet & other)349 void copy(const BitSet &other) 350 { 351 unsigned sizeInBytes = (other.m_Size + BITS_PER_BYTE - 1) / BITS_PER_BYTE; 352 if (this != &other) 353 { 354 if (m_Size == other.m_Size) 355 { 356 memcpy_s(m_BitSetArray, sizeInBytes, other.m_BitSetArray, sizeInBytes); 357 } 358 else 359 { 360 create(other.m_Size); 361 memcpy_s(m_BitSetArray, sizeInBytes, other.m_BitSetArray, sizeInBytes); 362 } 363 } 364 } 365 }; 366 367 #endif 368