• 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                 tmp -= 1;
79                 res.insert(base + bitPos + i * kBitWordSize);
80             }
81         }
82     }
83 
ConvertToSetMapleSparseBitVectorElement84     void ConvertToSet(std::set<uint32> &res, unsigned base) const
85     {
86         for (unsigned i = 0; i < kBitWordNum; i++) {
87             BitWord tmp = bitVector[i];
88             unsigned bitPos = 0;
89             while (tmp != 0) {
90                 unsigned trailingZeroNum = static_cast<unsigned>(__builtin_ctzll(tmp));
91                 bitPos += trailingZeroNum;
92                 tmp >>= trailingZeroNum;
93                 tmp -= 1;
94                 res.insert(base + bitPos + i * kBitWordSize);
95             }
96         }
97     }
98 
AndMapleSparseBitVectorElement99     bool And(const MapleSparseBitVectorElement &rhs, bool &becameZero)
100     {
101         bool changed = false;
102         bool allzero = true;
103         becameZero = false;
104         for (unsigned i = 0; i < kBitWordNum; i++) {
105             BitWord oldBitWord = bitVector[i];
106             bitVector[i] &= rhs.bitVector[i];
107             changed = changed || (oldBitWord != bitVector[i]);
108             if (bitVector[i] != 0) {
109                 allzero = false;
110             }
111         }
112         becameZero = allzero;
113         return changed;
114     }
115 
OrMapleSparseBitVectorElement116     bool Or(const MapleSparseBitVectorElement &rhs)
117     {
118         bool changed = false;
119         for (unsigned i = 0; i < kBitWordNum; i++) {
120             BitWord oldBitWord = bitVector[i];
121             bitVector[i] |= rhs.bitVector[i];
122             changed = changed || (oldBitWord != bitVector[i]);
123         }
124         return changed;
125     }
126 
DiffMapleSparseBitVectorElement127     bool Diff(const MapleSparseBitVectorElement &rhs, bool &becameZero)
128     {
129         bool changed = false;
130         bool allzero = true;
131         becameZero = false;
132         for (unsigned i = 0; i < kBitWordNum; i++) {
133             BitWord oldBitWord = bitVector[i];
134             bitVector[i] &= ~rhs.bitVector[i];
135             changed = changed || (oldBitWord != bitVector[i]);
136             if (bitVector[i] != 0) {
137                 allzero = false;
138             }
139         }
140         becameZero = allzero;
141         return changed;
142     }
143 
144     bool operator==(const MapleSparseBitVectorElement &rhs) const
145     {
146         if (index != rhs.GetIndex()) {
147             return false;
148         }
149         for (unsigned i = 0; i < kBitWordNum; i++) {
150             if (bitVector[i] != rhs.bitVector[i]) {
151                 return false;
152             }
153         }
154         return true;
155     }
156 
157     bool operator!=(const MapleSparseBitVectorElement &rhs) const
158     {
159         return !(*this == rhs);
160     }
161 
162 private:
163     unsigned index;
164     BitWord bitVector[kBitWordNum];
165 };
166 
167 template <unsigned bitVectorSize = 64>
168 class MapleSparseBitVector {
169     using ElementList = MapleList<MapleSparseBitVectorElement<bitVectorSize>>;
170     using ElementListIterator = typename ElementList::iterator;
171     using ElementListConstIterator = typename ElementList::const_iterator;
172     using BitWord = unsigned long long;
173 
174 public:
MapleSparseBitVector(const MapleAllocator & alloc)175     explicit MapleSparseBitVector(const MapleAllocator &alloc)
176         : allocator(alloc), elementList(allocator.Adapter()), currIter(elementList.begin())
177     {
178     }
179 
MapleSparseBitVector(const MapleSparseBitVector & rhs,const MapleAllocator & alloc)180     explicit MapleSparseBitVector(const MapleSparseBitVector &rhs, const MapleAllocator &alloc)
181         : allocator(alloc), elementList(rhs.elementList, allocator.Adapter()), currIter(elementList.begin())
182     {
183     }
184 
MapleSparseBitVector(const MapleSparseBitVector & rhs)185     MapleSparseBitVector(const MapleSparseBitVector &rhs)
186         : allocator(rhs.allocator), elementList(rhs.elementList, allocator.Adapter()), currIter(elementList.begin())
187     {
188     }
189 
Set(unsigned bitNO)190     void Set(unsigned bitNO)
191     {
192         unsigned idx = bitNO / bitVectorSize;
193         ElementListIterator iter;
194         if (elementList.empty()) {
195             iter = elementList.emplace(elementList.end(), idx);
196         } else {
197             iter = LowerBoundFor(idx);
198             if (iter == elementList.end() || iter->GetIndex() != idx) {
199                 if (iter != elementList.end() && iter->GetIndex() < idx) {
200                     ++iter;
201                 }
202                 iter = elementList.emplace(iter, idx);
203             }
204         }
205         currIter = iter;
206         iter->Set(bitNO % bitVectorSize);
207     }
208 
Reset(unsigned bitNO)209     void Reset(unsigned bitNO)
210     {
211         if (elementList.empty()) {
212             return;
213         }
214         unsigned idx = bitNO / bitVectorSize;
215         ElementListIterator iter = LowerBoundFor(idx);
216         if (iter == elementList.end() || iter->GetIndex() != idx) {
217             return;
218         }
219         iter->Reset(bitNO % bitVectorSize);
220         if (iter->Empty()) {
221             ++currIter;
222             elementList.erase(iter);
223         }
224     }
225 
Test(unsigned bitNO)226     bool Test(unsigned bitNO) const
227     {
228         if (elementList.empty()) {
229             return false;
230         }
231         unsigned idx = bitNO / bitVectorSize;
232         ElementListConstIterator iter = LowerBoundForConst(idx);
233         if (iter == elementList.end() || iter->GetIndex() != idx) {
234             return false;
235         }
236         return (iter->Test(bitNO % bitVectorSize));
237     }
238 
239     MapleSparseBitVector &operator=(const MapleSparseBitVector &rhs)
240     {
241         if (this == &rhs) {
242             return *this;
243         }
244         allocator = rhs.allocator;
245         elementList = rhs.elementList;
246         currIter = elementList.begin();
247         return *this;
248     }
249 
250     bool operator&=(const MapleSparseBitVector &rhs)
251     {
252         if (this == &rhs) {
253             return false;
254         }
255 
256         bool changed = false;
257         ElementListIterator iter1 = elementList.begin();
258         ElementListConstIterator iter2 = rhs.elementList.begin();
259 
260         if (elementList.empty() || rhs.elementList.empty()) {
261             return false;
262         }
263 
264         while (iter2 != rhs.elementList.end()) {
265             if (iter1 == elementList.end()) {
266                 currIter = elementList.begin();
267                 return changed;
268             }
269 
270             if (iter1->GetIndex() > iter2->GetIndex()) {
271                 ++iter2;
272             } else if (iter1->GetIndex() == iter2->GetIndex()) {
273                 bool becameZero;
274                 changed = iter1->And(*iter2, becameZero) || changed;
275                 if (becameZero) {
276                     ElementListIterator iterTmp = iter1;
277                     ++iter1;
278                     elementList.erase(iterTmp);
279                 } else {
280                     ++iter1;
281                 }
282                 ++iter2;
283             } else {
284                 ElementListIterator iterTmp = iter1;
285                 ++iter1;
286                 elementList.erase(iterTmp);
287                 changed = true;
288             }
289         }
290         if (iter1 != elementList.end()) {
291             elementList.erase(iter1, elementList.end());
292             changed = true;
293         }
294         currIter = elementList.begin();
295         return changed;
296     }
297 
298     bool operator|=(const MapleSparseBitVector &rhs)
299     {
300         if (this == &rhs) {
301             return false;
302         }
303 
304         bool changed = false;
305         ElementListIterator iter1 = elementList.begin();
306         ElementListConstIterator iter2 = rhs.elementList.begin();
307 
308         if (rhs.elementList.empty()) {
309             return false;
310         }
311 
312         while (iter2 != rhs.elementList.end()) {
313             if (iter1 == elementList.end() || iter1->GetIndex() > iter2->GetIndex()) {
314                 elementList.insert(iter1, *iter2);
315                 ++iter2;
316                 changed = true;
317             } else if (iter1->GetIndex() == iter2->GetIndex()) {
318                 changed = iter1->Or(*iter2) || changed;
319                 ++iter1;
320                 ++iter2;
321             } else {
322                 ++iter1;
323             }
324         }
325         currIter = elementList.begin();
326         return changed;
327     }
328 
Clear()329     void Clear()
330     {
331         elementList.clear();
332         currIter = elementList.begin();
333     }
334 
335     bool operator==(const MapleSparseBitVector &rhs) const
336     {
337         ElementListConstIterator iter1 = elementList.begin();
338         ElementListConstIterator iter2 = rhs.elementList.begin();
339         for (; iter1 != elementList.end() && iter2 != rhs.elementList.end(); ++iter1, ++iter2) {
340             if (*iter1 != *iter2) {
341                 return false;
342             }
343         }
344         return iter1 == elementList.end() && iter2 == rhs.elementList.end();
345     }
346 
347     bool operator!=(const MapleSparseBitVector &rhs) const
348     {
349         return !(*this == rhs);
350     }
351 
Empty()352     bool Empty() const
353     {
354         if (elementList.empty()) {
355             return true;
356         }
357         ElementListConstIterator iter1 = elementList.begin();
358         for (; iter1 != elementList.end(); ++iter1) {
359             if (!iter1->Empty()) {
360                 return false;
361             }
362         }
363         return true;
364     }
365 
Diff(const MapleSparseBitVector & rhs)366     bool Diff(const MapleSparseBitVector &rhs)
367     {
368         if (this == &rhs) {
369             if (!Empty()) {
370                 Clear();
371                 return true;
372             }
373             return false;
374         }
375 
376         bool changed = false;
377         ElementListIterator iter1 = elementList.begin();
378         ElementListConstIterator iter2 = rhs.elementList.begin();
379 
380         if (elementList.empty() || rhs.elementList.empty()) {
381             return false;
382         }
383 
384         while (iter2 != rhs.elementList.end()) {
385             if (iter1 == elementList.end()) {
386                 currIter = elementList.begin();
387                 return changed;
388             }
389 
390             if (iter1->GetIndex() > iter2->GetIndex()) {
391                 ++iter2;
392             } else if (iter1->GetIndex() == iter2->GetIndex()) {
393                 bool becameZero;
394                 changed = iter1->Diff(*iter2, becameZero) || changed;
395                 if (becameZero) {
396                     ElementListIterator iterTmp = iter1;
397                     ++iter1;
398                     elementList.erase(iterTmp);
399                 } else {
400                     ++iter1;
401                 }
402                 ++iter2;
403             } else {
404                 ++iter1;
405             }
406         }
407         currIter = elementList.begin();
408         return changed;
409     }
410 
ConvertToSet(MapleSet<uint32> & res)411     void ConvertToSet(MapleSet<uint32> &res) const
412     {
413         for (auto &element : elementList) {
414             unsigned pos = bitVectorSize * element.GetIndex();
415             element.ConvertToSet(res, pos);
416         }
417     }
418 
ConvertToSet(std::set<uint32> & res)419     void ConvertToSet(std::set<uint32> &res) const
420     {
421         for (auto &element : elementList) {
422             unsigned pos = bitVectorSize * element.GetIndex();
423             element.ConvertToSet(res, pos);
424         }
425     }
426 
427 private:
LowerBoundForImpl(unsigned idx)428     ElementListIterator LowerBoundForImpl(unsigned idx) const
429     {
430         ElementListIterator begin = const_cast<MapleSparseBitVector *>(this)->elementList.begin();
431         ElementListIterator end = const_cast<MapleSparseBitVector *>(this)->elementList.end();
432 
433         if (elementList.empty()) {
434             currIter = begin;
435             return currIter;
436         }
437 
438         if (currIter == end) {
439             --currIter;
440         }
441 
442         ElementListIterator iter = currIter;
443         if (iter->GetIndex() == idx) {
444             return iter;
445         } else if (iter->GetIndex() > idx) {
446             while (iter != begin && iter->GetIndex() > idx) {
447                 --iter;
448             }
449         } else {
450             while (iter != end && iter->GetIndex() < idx) {
451                 ++iter;
452             }
453         }
454         currIter = iter;
455         return iter;
456     }
457 
LowerBoundForConst(unsigned idx)458     ElementListConstIterator LowerBoundForConst(unsigned idx) const
459     {
460         return LowerBoundForImpl(idx);
461     }
462 
LowerBoundFor(unsigned idx)463     ElementListIterator LowerBoundFor(unsigned idx)
464     {
465         return LowerBoundForImpl(idx);
466     }
467 
468     MapleAllocator allocator;
469     ElementList elementList;
470     mutable ElementListIterator currIter;
471 };
472 }  // namespace maple
473 #endif /* MAPLEBE_INCLUDE_CG_SPARSE_BITVECTOR_H */
474