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 #include "BitSet.h"
10
create(unsigned size)11 void BitSet::create(unsigned size)
12 {
13 const unsigned newArraySize = (size + NUM_BITS_PER_ELT - 1) / NUM_BITS_PER_ELT;
14 const unsigned oldArraySize = (m_Size + NUM_BITS_PER_ELT - 1) / NUM_BITS_PER_ELT;
15 const unsigned numBitsLeft = size % NUM_BITS_PER_ELT;
16
17 if (size == 0)
18 {
19 free(m_BitSetArray);
20 m_Size = 0;
21 return;
22 }
23
24 if (newArraySize == oldArraySize)
25 {
26 // same array size, zero out the unused bits if necessary
27 m_Size = size;
28 if (newArraySize && numBitsLeft != 0)
29 {
30 m_BitSetArray[ newArraySize - 1 ] &= BIT(numBitsLeft) - 1;
31 }
32 }
33 else
34 {
35 BITSET_ARRAY_TYPE* ptr = (BITSET_ARRAY_TYPE*) malloc(newArraySize * sizeof(BITSET_ARRAY_TYPE));
36
37 if (ptr)
38 {
39 if (m_BitSetArray)
40 {
41 if (newArraySize > oldArraySize)
42 {
43 // copy entire old array over, set uninitialized bits to zero
44 memcpy_s(ptr, newArraySize * sizeof(BITSET_ARRAY_TYPE), m_BitSetArray, oldArraySize * sizeof(BITSET_ARRAY_TYPE));
45 memset(ptr + oldArraySize, 0,
46 (newArraySize - oldArraySize) * sizeof(BITSET_ARRAY_TYPE));
47 }
48 else
49 {
50 // copy old array up to the size of new array, zero out the unused bits
51 memcpy_s(ptr, newArraySize * sizeof(BITSET_ARRAY_TYPE), m_BitSetArray, newArraySize * sizeof(BITSET_ARRAY_TYPE));
52 if (numBitsLeft != 0)
53 {
54 ptr[ newArraySize - 1 ] &= BIT(numBitsLeft) - 1;
55 }
56 }
57 }
58 else
59 {
60 memset(ptr, 0, newArraySize * sizeof(BITSET_ARRAY_TYPE));
61 }
62
63 free(m_BitSetArray);
64
65 m_BitSetArray = ptr;
66 m_Size = size;
67 }
68 else
69 {
70 assert(0);
71 }
72 }
73 }
74
setAll(void)75 void BitSet::setAll(void)
76 {
77 if (m_BitSetArray)
78 {
79 unsigned index = m_Size / NUM_BITS_PER_ELT;
80 std::fill_n(m_BitSetArray, index, ~(BITSET_ARRAY_TYPE) 0);
81
82 // do the leftover bits, make sure we don't change the values of the unused bits,
83 // so isEmpty() can be implemented faster
84 int numBitsLeft = m_Size % NUM_BITS_PER_ELT;
85 if (numBitsLeft)
86 {
87 m_BitSetArray[index] = BIT(numBitsLeft) - 1;
88 }
89 }
90 }
91
invert(void)92 void BitSet::invert(void)
93 {
94 if (m_BitSetArray)
95 {
96 unsigned index;
97 for (index = 0; index < m_Size / NUM_BITS_PER_ELT; index++)
98 {
99 m_BitSetArray[index] = ~m_BitSetArray[index];
100 }
101
102 // do the leftover bits
103 int numBitsLeft = m_Size % NUM_BITS_PER_ELT;
104 if (numBitsLeft)
105 {
106 m_BitSetArray[index] = ~m_BitSetArray[index] & (BIT(numBitsLeft) - 1);
107 }
108 }
109 }
110
111 template <typename T>
vector_and(T * __restrict__ p1,const T * const p2,unsigned n)112 void vector_and(T *__restrict__ p1, const T *const p2, unsigned n)
113 {
114 for (unsigned i = 0; i < n; ++i)
115 {
116 p1[i] &= p2[i];
117 }
118 }
119
120 template <typename T>
vector_or(T * __restrict__ p1,const T * const p2,unsigned n)121 void vector_or(T *__restrict__ p1, const T *const p2, unsigned n)
122 {
123 for (unsigned i = 0; i < n; ++i)
124 {
125 p1[i] |= p2[i];
126 }
127 }
128
129 template <typename T>
vector_minus(T * __restrict__ p1,const T * const p2,unsigned n)130 void vector_minus(T *__restrict__ p1, const T *const p2, unsigned n)
131 {
132 for (unsigned i = 0; i < n; ++i)
133 {
134 p1[i] &= ~p2[i];
135 }
136 }
137
operator |=(const BitSet & other)138 BitSet& BitSet::operator|=(const BitSet& other)
139 {
140 unsigned size = other.m_Size;
141
142 //grow the set to the size of the other set if necessary
143 if (m_Size < other.m_Size)
144 {
145 create(other.m_Size);
146 size = m_Size;
147 }
148
149 unsigned arraySize = (size + NUM_BITS_PER_ELT - 1) / NUM_BITS_PER_ELT;
150 vector_or(m_BitSetArray, other.m_BitSetArray, arraySize);
151
152 return *this;
153 }
154
operator -=(const BitSet & other)155 BitSet& BitSet::operator-= (const BitSet &other)
156 {
157 // do not grow the set for subtract
158 unsigned size = m_Size < other.m_Size ? m_Size : other.m_Size;
159 unsigned arraySize = (size + NUM_BITS_PER_ELT - 1) / NUM_BITS_PER_ELT;
160 vector_minus(m_BitSetArray, other.m_BitSetArray, arraySize);
161 return *this;
162 }
163
operator &=(const BitSet & other)164 BitSet& BitSet::operator&= (const BitSet &other)
165 {
166 // do not grow the set for and
167 unsigned size = m_Size < other.m_Size ? m_Size : other.m_Size;
168 unsigned arraySize = (size + NUM_BITS_PER_ELT - 1) / NUM_BITS_PER_ELT;
169 vector_and(m_BitSetArray, other.m_BitSetArray, arraySize);
170
171 //zero out the leftover bits if there are any
172 unsigned myArraySize = (m_Size + NUM_BITS_PER_ELT - 1) / NUM_BITS_PER_ELT;
173 for (unsigned i = arraySize; i < myArraySize; i++)
174 {
175 m_BitSetArray[ i ] = 0;
176 }
177
178 return *this;
179 }
180
181 // Create a bitmask with the N right-most bits set to 1, and all other bits set
182 // to 0.
maskTrailingOnes(unsigned n)183 static BITSET_ARRAY_TYPE maskTrailingOnes(unsigned n)
184 {
185 assert(n <= NUM_BITS_PER_ELT);
186 return n == 0 ? 0 : (BITSET_ARRAY_TYPE(-1) >> (NUM_BITS_PER_ELT - n));
187 }
188
189 // Create a bitmask with the N right-most bits set to 0, and all other bits set
190 // to 1.
maskTrailingZeros(unsigned n)191 static BITSET_ARRAY_TYPE maskTrailingZeros(unsigned n)
192 {
193 return ~maskTrailingOnes(n);
194 }
195
196 // TODO: Use c++20 bit manipulation utility functions.
countTrailingZeros(BITSET_ARRAY_TYPE val)197 static unsigned countTrailingZeros(BITSET_ARRAY_TYPE val)
198 {
199 assert(val != 0);
200 unsigned count = 0;
201 while ((val & 1) == 0)
202 {
203 val >>= 1;
204 ++count;
205 }
206 return count;
207 }
208
countLeadingZeros(BITSET_ARRAY_TYPE val)209 static unsigned countLeadingZeros(BITSET_ARRAY_TYPE val)
210 {
211 assert(val != 0);
212 unsigned count = 0;
213 while ((val & (1 << (NUM_BITS_PER_ELT - 1))) == 0)
214 {
215 val <<= 1;
216 ++count;
217 }
218 return count;
219 }
220
findFirstIn(unsigned begin,unsigned end) const221 int BitSet::findFirstIn(unsigned begin, unsigned end) const
222 {
223 assert(begin <= end && end <= m_Size);
224 if (begin == end)
225 return -1;
226
227 unsigned firstElt = begin / NUM_BITS_PER_ELT;
228 unsigned lastElt = (end - 1) / NUM_BITS_PER_ELT;
229
230 for (unsigned i = firstElt; i <= lastElt; ++i)
231 {
232 auto elt = getElt(i);
233
234 if (i == firstElt)
235 {
236 unsigned firstBit = begin % NUM_BITS_PER_ELT;
237 elt &= maskTrailingZeros(firstBit);
238 }
239
240 if (i == lastElt)
241 {
242 unsigned lastBit = (end - 1) % NUM_BITS_PER_ELT;
243 elt &= maskTrailingOnes(lastBit + 1);
244 }
245
246 if (elt != 0)
247 return i * NUM_BITS_PER_ELT + countTrailingZeros(elt);
248 }
249
250 return -1;
251 }
252
findLastIn(unsigned begin,unsigned end) const253 int BitSet::findLastIn(unsigned begin, unsigned end) const
254 {
255 assert(begin <= end && end <= m_Size);
256 if (begin == end)
257 return -1;
258
259 unsigned lastElt = (end - 1) / NUM_BITS_PER_ELT;
260 unsigned firstElt = begin / NUM_BITS_PER_ELT;
261
262 for (unsigned i = lastElt + 1; i >= firstElt + 1; --i)
263 {
264 unsigned currentElt = i - 1;
265 auto elt = getElt(currentElt);
266
267 if (currentElt == lastElt)
268 {
269 unsigned lastBit = (end - 1) % NUM_BITS_PER_ELT;
270 elt &= maskTrailingOnes(lastBit + 1);
271 }
272
273 if (currentElt == firstElt)
274 {
275 unsigned firstBit = begin % NUM_BITS_PER_ELT;
276 elt &= maskTrailingZeros(firstBit);
277 }
278
279 if (elt != 0)
280 return (currentElt + 1) * NUM_BITS_PER_ELT - countLeadingZeros(elt) - 1;
281 }
282
283 return -1;
284 }
285