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