• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright (c) 2023 Huawei Device Co., Ltd.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at
6  *
7  *     http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 
16 #ifndef MEMPOOL_INCLUDE_MAPLE_SPARSE_BITVECTOR_H
17 #define MEMPOOL_INCLUDE_MAPLE_SPARSE_BITVECTOR_H
18 #include <climits>
19 #include <iterator>
20 #include <list>
21 #include <iostream>
22 #include <bitset>
23 #include <set>
24 #include "mempool_allocator.h"
25 
26 namespace maple {
27 template <unsigned bitVectorSize = 64>
28 struct MapleSparseBitVectorElement {
29     using BitWord = unsigned long long;
30     enum { kBitWordSize = sizeof(BitWord) * CHAR_BIT, kBitWordNum = (bitVectorSize + kBitWordSize - 1) / kBitWordSize };
31 
MapleSparseBitVectorElementMapleSparseBitVectorElement32     explicit MapleSparseBitVectorElement(unsigned idx) : index(idx), bitVector {0} {}
33 
GetWordMapleSparseBitVectorElement34     BitWord GetWord(unsigned idx) const
35     {
36         return bitVector[idx];
37     }
38 
GetIndexMapleSparseBitVectorElement39     unsigned GetIndex() const
40     {
41         return index;
42     }
43 
SetMapleSparseBitVectorElement44     void Set(unsigned idx)
45     {
46         bitVector[idx / kBitWordSize] |= 1ULL << (idx % kBitWordSize);
47     }
48 
ResetMapleSparseBitVectorElement49     void Reset(unsigned idx)
50     {
51         bitVector[idx / kBitWordSize] &= ~(1ULL << (idx % kBitWordSize));
52     }
53 
TestMapleSparseBitVectorElement54     bool Test(unsigned idx) const
55     {
56         return bitVector[idx / kBitWordSize] & (1ULL << (idx % kBitWordSize));
57     }
58 
EmptyMapleSparseBitVectorElement59     bool Empty() const
60     {
61         for (unsigned i = 0; i < kBitWordNum; i++) {
62             if (bitVector[i]) {
63                 return false;
64             }
65         }
66         return true;
67     }
68 
ConvertToSetMapleSparseBitVectorElement69     void ConvertToSet(MapleSet<uint32> &res, unsigned base) const
70     {
71         for (unsigned i = 0; i < kBitWordNum; i++) {
72             BitWord tmp = bitVector[i];
73             unsigned bitPos = 0;
74             while (tmp != 0) {
75                 unsigned trailingZeroNum = static_cast<unsigned>(__builtin_ctzll(tmp));
76                 bitPos += trailingZeroNum;
77                 tmp >>= trailingZeroNum;
78                 DEBUG_ASSERT(tmp > 0, "tmp should not be zero; tmp should end with 1 in binary after shifting");
79                 tmp -= 1;
80                 res.insert(base + bitPos + i * kBitWordSize);
81             }
82         }
83     }
84 
ConvertToSetMapleSparseBitVectorElement85     void ConvertToSet(std::set<uint32> &res, unsigned base) const
86     {
87         for (unsigned i = 0; i < kBitWordNum; i++) {
88             BitWord tmp = bitVector[i];
89             unsigned bitPos = 0;
90             while (tmp != 0) {
91                 unsigned trailingZeroNum = static_cast<unsigned>(__builtin_ctzll(tmp));
92                 bitPos += trailingZeroNum;
93                 tmp >>= trailingZeroNum;
94                 tmp -= 1;
95                 res.insert(base + bitPos + i * kBitWordSize);
96             }
97         }
98     }
99 
AndMapleSparseBitVectorElement100     bool And(const MapleSparseBitVectorElement &rhs, bool &becameZero)
101     {
102         bool changed = false;
103         bool allzero = true;
104         becameZero = false;
105         for (unsigned i = 0; i < kBitWordNum; i++) {
106             BitWord oldBitWord = bitVector[i];
107             bitVector[i] &= rhs.bitVector[i];
108             changed = changed || (oldBitWord != bitVector[i]);
109             if (bitVector[i] != 0) {
110                 allzero = false;
111             }
112         }
113         becameZero = allzero;
114         return changed;
115     }
116 
OrMapleSparseBitVectorElement117     bool Or(const MapleSparseBitVectorElement &rhs)
118     {
119         bool changed = false;
120         for (unsigned i = 0; i < kBitWordNum; i++) {
121             BitWord oldBitWord = bitVector[i];
122             bitVector[i] |= rhs.bitVector[i];
123             changed = changed || (oldBitWord != bitVector[i]);
124         }
125         return changed;
126     }
127 
DiffMapleSparseBitVectorElement128     bool Diff(const MapleSparseBitVectorElement &rhs, bool &becameZero)
129     {
130         bool changed = false;
131         bool allzero = true;
132         becameZero = false;
133         for (unsigned i = 0; i < kBitWordNum; i++) {
134             BitWord oldBitWord = bitVector[i];
135             bitVector[i] &= ~rhs.bitVector[i];
136             changed = changed || (oldBitWord != bitVector[i]);
137             if (bitVector[i] != 0) {
138                 allzero = false;
139             }
140         }
141         becameZero = allzero;
142         return changed;
143     }
144 
145     bool operator==(const MapleSparseBitVectorElement &rhs) const
146     {
147         if (index != rhs.GetIndex()) {
148             return false;
149         }
150         for (unsigned i = 0; i < kBitWordNum; i++) {
151             if (bitVector[i] != rhs.bitVector[i]) {
152                 return false;
153             }
154         }
155         return true;
156     }
157 
158     bool operator!=(const MapleSparseBitVectorElement &rhs) const
159     {
160         return !(*this == rhs);
161     }
162 
163 private:
164     unsigned index;
165     BitWord bitVector[kBitWordNum];
166 };
167 
168 template <unsigned bitVectorSize = 64>
169 class MapleSparseBitVector {
170     using ElementList = MapleList<MapleSparseBitVectorElement<bitVectorSize>>;
171     using ElementListIterator = typename ElementList::iterator;
172     using ElementListConstIterator = typename ElementList::const_iterator;
173     using BitWord = unsigned long long;
174 
175 public:
MapleSparseBitVector(const MapleAllocator & alloc)176     explicit MapleSparseBitVector(const MapleAllocator &alloc)
177         : allocator(alloc), elementList(allocator.Adapter()), currIter(elementList.begin())
178     {
179     }
180 
MapleSparseBitVector(const MapleSparseBitVector & rhs,const MapleAllocator & alloc)181     explicit MapleSparseBitVector(const MapleSparseBitVector &rhs, const MapleAllocator &alloc)
182         : allocator(alloc), elementList(rhs.elementList, allocator.Adapter()), currIter(elementList.begin())
183     {
184     }
185 
MapleSparseBitVector(const MapleSparseBitVector & rhs)186     MapleSparseBitVector(const MapleSparseBitVector &rhs)
187         : allocator(rhs.allocator), elementList(rhs.elementList, allocator.Adapter()), currIter(elementList.begin())
188     {
189     }
190 
Set(unsigned bitNO)191     void Set(unsigned bitNO)
192     {
193         unsigned idx = bitNO / bitVectorSize;
194         ElementListIterator iter;
195         if (elementList.empty()) {
196             iter = elementList.emplace(elementList.end(), idx);
197         } else {
198             iter = LowerBoundFor(idx);
199             if (iter == elementList.end() || iter->GetIndex() != idx) {
200                 if (iter != elementList.end() && iter->GetIndex() < idx) {
201                     ++iter;
202                 }
203                 iter = elementList.emplace(iter, idx);
204             }
205         }
206         currIter = iter;
207         iter->Set(bitNO % bitVectorSize);
208     }
209 
Reset(unsigned bitNO)210     void Reset(unsigned bitNO)
211     {
212         if (elementList.empty()) {
213             return;
214         }
215         unsigned idx = bitNO / bitVectorSize;
216         ElementListIterator iter = LowerBoundFor(idx);
217         if (iter == elementList.end() || iter->GetIndex() != idx) {
218             return;
219         }
220         iter->Reset(bitNO % bitVectorSize);
221         if (iter->Empty()) {
222             ++currIter;
223             elementList.erase(iter);
224         }
225     }
226 
Test(unsigned bitNO)227     bool Test(unsigned bitNO) const
228     {
229         if (elementList.empty()) {
230             return false;
231         }
232         unsigned idx = bitNO / bitVectorSize;
233         ElementListConstIterator iter = LowerBoundForConst(idx);
234         if (iter == elementList.end() || iter->GetIndex() != idx) {
235             return false;
236         }
237         return (iter->Test(bitNO % bitVectorSize));
238     }
239 
240     MapleSparseBitVector &operator=(const MapleSparseBitVector &rhs)
241     {
242         if (this == &rhs) {
243             return *this;
244         }
245         allocator = rhs.allocator;
246         elementList = rhs.elementList;
247         currIter = elementList.begin();
248         return *this;
249     }
250 
251     bool operator&=(const MapleSparseBitVector &rhs)
252     {
253         if (this == &rhs) {
254             return false;
255         }
256 
257         bool changed = false;
258         ElementListIterator iter1 = elementList.begin();
259         ElementListConstIterator iter2 = rhs.elementList.begin();
260 
261         if (elementList.empty() || rhs.elementList.empty()) {
262             return false;
263         }
264 
265         while (iter2 != rhs.elementList.end()) {
266             if (iter1 == elementList.end()) {
267                 currIter = elementList.begin();
268                 return changed;
269             }
270 
271             if (iter1->GetIndex() > iter2->GetIndex()) {
272                 ++iter2;
273             } else if (iter1->GetIndex() == iter2->GetIndex()) {
274                 bool becameZero;
275                 changed = iter1->And(*iter2, becameZero) || changed;
276                 if (becameZero) {
277                     ElementListIterator iterTmp = iter1;
278                     ++iter1;
279                     elementList.erase(iterTmp);
280                 } else {
281                     ++iter1;
282                 }
283                 ++iter2;
284             } else {
285                 ElementListIterator iterTmp = iter1;
286                 ++iter1;
287                 elementList.erase(iterTmp);
288                 changed = true;
289             }
290         }
291         if (iter1 != elementList.end()) {
292             elementList.erase(iter1, elementList.end());
293             changed = true;
294         }
295         currIter = elementList.begin();
296         return changed;
297     }
298 
299     bool operator|=(const MapleSparseBitVector &rhs)
300     {
301         if (this == &rhs) {
302             return false;
303         }
304 
305         bool changed = false;
306         ElementListIterator iter1 = elementList.begin();
307         ElementListConstIterator iter2 = rhs.elementList.begin();
308 
309         if (rhs.elementList.empty()) {
310             return false;
311         }
312 
313         while (iter2 != rhs.elementList.end()) {
314             if (iter1 == elementList.end() || iter1->GetIndex() > iter2->GetIndex()) {
315                 elementList.insert(iter1, *iter2);
316                 ++iter2;
317                 changed = true;
318             } else if (iter1->GetIndex() == iter2->GetIndex()) {
319                 changed = iter1->Or(*iter2) || changed;
320                 ++iter1;
321                 ++iter2;
322             } else {
323                 ++iter1;
324             }
325         }
326         currIter = elementList.begin();
327         return changed;
328     }
329 
Clear()330     void Clear()
331     {
332         elementList.clear();
333         currIter = elementList.begin();
334     }
335 
336     bool operator==(const MapleSparseBitVector &rhs) const
337     {
338         ElementListConstIterator iter1 = elementList.begin();
339         ElementListConstIterator iter2 = rhs.elementList.begin();
340         for (; iter1 != elementList.end() && iter2 != rhs.elementList.end(); ++iter1, ++iter2) {
341             if (*iter1 != *iter2) {
342                 return false;
343             }
344         }
345         return iter1 == elementList.end() && iter2 == rhs.elementList.end();
346     }
347 
348     bool operator!=(const MapleSparseBitVector &rhs) const
349     {
350         return !(*this == rhs);
351     }
352 
Empty()353     bool Empty() const
354     {
355         if (elementList.empty()) {
356             return true;
357         }
358         ElementListConstIterator iter1 = elementList.begin();
359         for (; iter1 != elementList.end(); ++iter1) {
360             if (!iter1->Empty()) {
361                 return false;
362             }
363         }
364         return true;
365     }
366 
Diff(const MapleSparseBitVector & rhs)367     bool Diff(const MapleSparseBitVector &rhs)
368     {
369         if (this == &rhs) {
370             if (!Empty()) {
371                 Clear();
372                 return true;
373             }
374             return false;
375         }
376 
377         bool changed = false;
378         ElementListIterator iter1 = elementList.begin();
379         ElementListConstIterator iter2 = rhs.elementList.begin();
380 
381         if (elementList.empty() || rhs.elementList.empty()) {
382             return false;
383         }
384 
385         while (iter2 != rhs.elementList.end()) {
386             if (iter1 == elementList.end()) {
387                 currIter = elementList.begin();
388                 return changed;
389             }
390 
391             if (iter1->GetIndex() > iter2->GetIndex()) {
392                 ++iter2;
393             } else if (iter1->GetIndex() == iter2->GetIndex()) {
394                 bool becameZero;
395                 changed = iter1->Diff(*iter2, becameZero) || changed;
396                 if (becameZero) {
397                     ElementListIterator iterTmp = iter1;
398                     ++iter1;
399                     elementList.erase(iterTmp);
400                 } else {
401                     ++iter1;
402                 }
403                 ++iter2;
404             } else {
405                 ++iter1;
406             }
407         }
408         currIter = elementList.begin();
409         return changed;
410     }
411 
ConvertToSet(MapleSet<uint32> & res)412     void ConvertToSet(MapleSet<uint32> &res) const
413     {
414         for (auto &element : elementList) {
415             unsigned pos = bitVectorSize * element.GetIndex();
416             element.ConvertToSet(res, pos);
417         }
418     }
419 
ConvertToSet(std::set<uint32> & res)420     void ConvertToSet(std::set<uint32> &res) const
421     {
422         for (auto &element : elementList) {
423             unsigned pos = bitVectorSize * element.GetIndex();
424             element.ConvertToSet(res, pos);
425         }
426     }
427 
428 private:
LowerBoundForImpl(unsigned idx)429     ElementListIterator LowerBoundForImpl(unsigned idx) const
430     {
431         ElementListIterator begin = const_cast<MapleSparseBitVector *>(this)->elementList.begin();
432         ElementListIterator end = const_cast<MapleSparseBitVector *>(this)->elementList.end();
433 
434         if (elementList.empty()) {
435             currIter = begin;
436             return currIter;
437         }
438 
439         if (currIter == end) {
440             --currIter;
441         }
442 
443         ElementListIterator iter = currIter;
444         if (iter->GetIndex() == idx) {
445             return iter;
446         } else if (iter->GetIndex() > idx) {
447             while (iter != begin && iter->GetIndex() > idx) {
448                 --iter;
449             }
450         } else {
451             while (iter != end && iter->GetIndex() < idx) {
452                 ++iter;
453             }
454         }
455         currIter = iter;
456         return iter;
457     }
458 
LowerBoundForConst(unsigned idx)459     ElementListConstIterator LowerBoundForConst(unsigned idx) const
460     {
461         return LowerBoundForImpl(idx);
462     }
463 
LowerBoundFor(unsigned idx)464     ElementListIterator LowerBoundFor(unsigned idx)
465     {
466         return LowerBoundForImpl(idx);
467     }
468 
469     MapleAllocator allocator;
470     ElementList elementList;
471     mutable ElementListIterator currIter;
472 };
473 }  // namespace maple
474 #endif /* MAPLEBE_INCLUDE_CG_SPARSE_BITVECTOR_H */
475