1/**
2 * Copyright 2021 Alibaba, Inc. and its affiliates. All Rights Reserved.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15
16 * \author Hechong.xyf
17 * \date Dec 2017
18 * \brief Interface of AiLego Utility Bitmap
19 */
20
21#ifndef __AILEGO_CONTAINER_BITMAP_H__
22#define __AILEGO_CONTAINER_BITMAP_H__
23
24#include <algorithm>
25#include <vector>
26#include <ailego/utility/bitset_helper.h>
27
28namespace ailego {
29
30/*! Fixed Bitset
31 */
32template <size_t N, typename = typename std::enable_if<N % 32 == 0>::type>
33class FixedBitset {
34 public:
35 enum { MAX_SIZE = N };
36
37 //! Constructor
38 FixedBitset(void) {
39 memset(array_, 0, sizeof(array_));
40 }
41
42 //! Constructor
43 FixedBitset(const FixedBitset &rhs) {
44 memcpy(array_, rhs.array_, sizeof(array_));
45 }
46
47 //! Destructor
48 ~FixedBitset(void) {}
49
50 //! Assignment
51 FixedBitset &operator=(const FixedBitset &rhs) {
52 memcpy(array_, rhs.array_, sizeof(array_));
53 return *this;
54 }
55
56 //! Retrieve data pointer
57 uint32_t *data(void) {
58 return reinterpret_cast<uint32_t *>(array_);
59 }
60
61 //! Retrieve data pointer
62 const uint32_t *data(void) const {
63 return reinterpret_cast<const uint32_t *>(array_);
64 }
65
66 //! Retrieve count of bits in set
67 constexpr size_t size(void) const {
68 return MAX_SIZE;
69 }
70
71 //！Clear the bitset
72 void clear(void) {
73 memset(array_, 0, sizeof(array_));
74 }
75
76 //! Test a bit in bitset
77 bool test(size_t num) const {
78 ailego_assert_with(N > num, "overflow argument");
79 return ((array_[num >> 5] & (1u << (num & 0x1f))) != 0);
80 }
81
82 //! Set a bit in bitset
83 void set(size_t num) {
84 ailego_assert_with(N > num, "overflow argument");
85 uint32_t mask = (1u << (num & 0x1f));
86 array_[num >> 5] |= mask;
87 }
88
89 //! Clear a bit in bitset
90 void reset(size_t num) {
91 ailego_assert_with(N > num, "overflow argument");
92 uint32_t mask = (1u << (num & 0x1f));
93 array_[num >> 5] &= ~mask;
94 }
95
96 //! Toggle a bit in bitset
97 void flip(size_t num) {
98 ailego_assert_with(N > num, "overflow argument");
99 uint32_t mask = (1u << (num & 0x1f));
100 array_[num >> 5] ^= mask;
101 }
102
103 //! Perform binary AND
104 void bitwise_and(const FixedBitset &rhs) {
105 BitsetHelper::BitwiseAnd(array_, rhs.array_, ((N + 0x1f) >> 5));
106 }
107
108 //! Perform binary AND NOT
109 void bitwise_andnot(const FixedBitset &rhs) {
110 BitsetHelper::BitwiseAndnot(array_, rhs.array_, ((N + 0x1f) >> 5));
111 }
112
113 //! Perform binary OR
114 void bitwise_or(const FixedBitset &rhs) {
115 BitsetHelper::BitwiseOr(array_, rhs.array_, ((N + 0x1f) >> 5));
116 }
117
118 //! Perform binary XOR
119 void bitwise_xor(const FixedBitset &rhs) {
120 BitsetHelper::BitwiseXor(array_, rhs.array_, ((N + 0x1f) >> 5));
121 }
122
123 //! Perform binary NOT
124 void bitwise_not(void) {
125 BitsetHelper::BitwiseNot(array_, ((N + 0x1f) >> 5));
126 }
127
128 //! Check if all bits are set to true
129 bool test_all(void) const {
130 return BitsetHelper::TestAll(array_, ((N + 0x1f) >> 5));
131 }
132
133 //! Check if any bits are set to true
134 bool test_any(void) const {
135 return BitsetHelper::TestAny(array_, ((N + 0x1f) >> 5));
136 }
137
138 //! Check if none of the bits are set to true
139 bool test_none(void) const {
140 return BitsetHelper::TestNone(array_, ((N + 0x1f) >> 5));
141 }
142
143 //! Compute the cardinality of a bitset
144 size_t cardinality(void) const {
145 return BitsetHelper::Cardinality(array_, ((N + 0x1f) >> 5));
146 }
147
148 //! Extract the bitset to an array
149 void extract(size_t base, std::vector<size_t> *out) const {
150 const uint32_t *iter = array_;
151 const uint32_t *last = array_ + ((N + 0x1f) >> 5);
152
153 for (; iter != last; ++iter) {
154 uint32_t w = *iter;
155
156 while (w != 0) {
157 uint32_t c = ailego_ctz32(w);
158 w &= ~(1u << c);
159 out->push_back(base + c);
160 }
161 base += 32u;
162 }
163 }
164
165 //! Extract the bitset to an array
166 void extract(std::vector<size_t> *out) const {
167 this->extract(0, out);
168 }
169
170 //! Compute the AND cardinality between two bitsets
171 static size_t BitwiseAndCardinality(const FixedBitset &lhs,
172 const FixedBitset &rhs) {
173 return BitsetHelper::BitwiseAndCardinality(lhs.array_, rhs.array_,
174 ((N + 0x1f) >> 5));
175 }
176
177 //! Compute the ANDNOT cardinality between two bitsets
178 static size_t BitwiseAndnotCardinality(const FixedBitset &lhs,
179 const FixedBitset &rhs) {
180 return BitsetHelper::BitwiseAndnotCardinality(lhs.array_, rhs.array_,
181 ((N + 0x1f) >> 5));
182 }
183
184 //! Compute the XOR cardinality between two bitsets
185 static size_t BitwiseXorCardinality(const FixedBitset &lhs,
186 const FixedBitset &rhs) {
187 return BitsetHelper::BitwiseXorCardinality(lhs.array_, rhs.array_,
188 ((N + 0x1f) >> 5));
189 }
190
191 //! Compute the OR cardinality between two bitsets
192 static size_t BitwiseOrCardinality(const FixedBitset &lhs,
193 const FixedBitset &rhs) {
194 return BitsetHelper::BitwiseOrCardinality(lhs.array_, rhs.array_,
195 ((N + 0x1f) >> 5));
196 }
197
198 //! Convert a array pointer to bitset pointer
199 static FixedBitset *Cast(uint32_t *arr) {
200 return reinterpret_cast<FixedBitset<N> *>(arr);
201 }
202
203 //! Convert a array pointer to bitset pointer
204 static const FixedBitset *Cast(const uint32_t *arr) {
205 return reinterpret_cast<const FixedBitset<N> *>(arr);
206 }
207
208 //! Convert a array pointer to bitset pointer
209 static FixedBitset *Cast(uint64_t *arr) {
210 return reinterpret_cast<FixedBitset<N> *>(arr);
211 }
212
213 //! Convert a array pointer to bitset pointer
214 static const FixedBitset *Cast(const uint64_t *arr) {
215 return reinterpret_cast<const FixedBitset<N> *>(arr);
216 }
217
218 private:
219 uint32_t array_[(N + 0x1f) >> 5];
220};
221
222/*! Fixed Bitset (Special)
223 */
224template <>
225class FixedBitset<0> {
226 public:
227 enum { MAX_SIZE = 0 };
228
229 //! Retrieve max size of bitset
230 constexpr size_t size(void) const {
231 return MAX_SIZE;
232 }
233};
234
235/*! Bitset
236 */
237class Bitset {
238 public:
239 //! Constructor
240 Bitset(void) : array_() {}
241
242 //! Constructor
243 Bitset(size_t bits) : array_((bits + 0x1f) >> 5) {}
244
245 //! Constructor
246 Bitset(const Bitset &rhs) : array_(rhs.array_) {}
247
248 //! Constructor
249 Bitset(Bitset &&rhs) : array_(std::move(rhs.array_)) {}
250
251 //! Destructor
252 ~Bitset(void) {}
253
254 //! Assignment
255 Bitset &operator=(const Bitset &rhs) {
256 array_ = rhs.array_;
257 return *this;
258 }
259
260 //! Assignment
261 Bitset &operator=(Bitset &&rhs) {
262 array_ = std::move(rhs.array_);
263 return *this;
264 }
265
266 //! Retrieve data pointer
267 uint32_t *data(void) {
268 return array_.data();
269 }
270
271 //! Retrieve data pointer
272 const uint32_t *data(void) const {
273 return array_.data();
274 }
275
276 //! Retrieve count of bits in set
277 size_t size(void) const {
278 return (array_.size() << 5);
279 }
280
281 //! Resize the bitset
282 void resize(size_t bits) {
283 array_.resize((bits + 0x1f) >> 5);
284 }
285
286 //！Clear the bitset
287 void clear(void) {
288 array_.clear();
289 }
290
291 //! Test a bit in bitset
292 bool test(size_t num) const {
293 ailego_assert_with(this->size() > num, "overflow argument");
294 return ((array_[num >> 5] & (1u << (num & 0x1f))) != 0);
295 }
296
297 //! Set a bit in bitset
298 void set(size_t num) {
299 ailego_assert_with(this->size() > num, "overflow argument");
300 uint32_t mask = (1u << (num & 0x1f));
301 array_[num >> 5] |= mask;
302 }
303
304 //! Clear a bit in bitset
305 void reset(size_t num) {
306 ailego_assert_with(this->size() > num, "overflow argument");
307 uint32_t mask = (1u << (num & 0x1f));
308 array_[num >> 5] &= ~mask;
309 }
310
311 //! Toggle a bit in bitset
312 void flip(size_t num) {
313 ailego_assert_with(this->size() > num, "overflow argument");
314 uint32_t mask = (1u << (num & 0x1f));
315 array_[num >> 5] ^= mask;
316 }
317
318 //! Perform binary AND
319 void bitwise_and(const Bitset &rhs) {
320 BitsetHelper::BitwiseAnd(array_.data(), rhs.array_.data(),
321 std::min(array_.size(), rhs.array_.size()));
322 }
323
324 //! Perform binary AND NOT
325 void bitwise_andnot(const Bitset &rhs) {
326 BitsetHelper::BitwiseAndnot(array_.data(), rhs.array_.data(),
327 std::min(array_.size(), rhs.array_.size()));
328 }
329
330 //! Perform binary OR
331 void bitwise_or(const Bitset &rhs) {
332 BitsetHelper::BitwiseOr(array_.data(), rhs.array_.data(),
333 std::min(array_.size(), rhs.array_.size()));
334 }
335
336 //! Perform binary XOR
337 void bitwise_xor(const Bitset &rhs) {
338 BitsetHelper::BitwiseXor(array_.data(), rhs.array_.data(),
339 std::min(array_.size(), rhs.array_.size()));
340 }
341
342 //! Perform binary NOT
343 void bitwise_not(void) {
344 BitsetHelper::BitwiseNot(array_.data(), array_.size());
345 }
346
347 //! Check if all bits are set to true
348 bool test_all(void) const {
349 return BitsetHelper::TestAll(array_.data(), array_.size());
350 }
351
352 //! Check if any bits are set to true
353 bool test_any(void) const {
354 return BitsetHelper::TestAny(array_.data(), array_.size());
355 }
356
357 //! Check if none of the bits are set to true
358 bool test_none(void) const {
359 return BitsetHelper::TestNone(array_.data(), array_.size());
360 }
361
362 //! Compute the cardinality of a bitset
363 size_t cardinality(void) const {
364 return BitsetHelper::Cardinality(array_.data(), array_.size());
365 }
366
367 //! Extract the bitset to an array
368 void extract(size_t base, std::vector<size_t> *out) const {
369 const uint32_t *iter = array_.data();
370 const uint32_t *last = array_.data() + array_.size();
371
372 for (; iter != last; ++iter) {
373 uint32_t w = *iter;
374
375 while (w != 0) {
376 uint32_t c = ailego_ctz32(w);
377 w &= ~(1u << c);
378 out->push_back(base + c);
379 }
380 base += 32u;
381 }
382 }
383
384 //! Extract the bitset to an array
385 void extract(std::vector<size_t> *out) const {
386 this->extract(0, out);
387 }
388
389 //! Compute the AND cardinality between two bitsets
390 static size_t BitwiseAndCardinality(const Bitset &lhs, const Bitset &rhs);
391
392 //! Compute the ANDNOT cardinality between two bitsets
393 static size_t BitwiseAndnotCardinality(const Bitset &lhs, const Bitset &rhs);
394
395 //! Compute the XOR cardinality between two bitsets
396 static size_t BitwiseXorCardinality(const Bitset &lhs, const Bitset &rhs);
397
398 //! Compute the OR cardinality between two bitsets
399 static size_t BitwiseOrCardinality(const Bitset &lhs, const Bitset &rhs);
400
401 private:
402 std::vector<uint32_t> array_;
403};
404
405/*! Bitmap
406 */
407class Bitmap {
408 public:
409 typedef FixedBitset<65536u> Bucket;
410
411 //! Constructor
412 Bitmap(void) : array_() {}
413
414 //! Constructor
415 Bitmap(const Bitmap &rhs) {
416 this->copy(rhs);
417 }
418
419 //! Destructor
420 ~Bitmap(void) {
421 this->clear();
422 }
423
424 //! Assignment
425 Bitmap &operator=(const Bitmap &rhs) {
426 this->copy(rhs);
427 return *this;
428 }
429
430 //! Retrieve bucket size of bitmap
431 size_t bucket_size(void) const {
432 return array_.size();
433 }
434
435 //！Clear the bitmap
436 void clear(void);
437
438 //! Remove the none buckets
439 void shrink_to_fit(void);
440
441 //! Test a bit in bitmap
442 bool test(size_t num) const;
443
444 //! Set a bit in bitmap
445 void set(size_t num);
446
447 //! Reset a bit in bitmap
448 void reset(size_t num);
449
450 //! Toggle a bit in bitmap
451 void flip(size_t num);
452
453 //! Perform binary AND
454 void bitwise_and(const Bitmap &rhs);
455
456 //! Perform binary AND NOT
457 void bitwise_andnot(const Bitmap &rhs);
458
459 //! Perform binary OR
460 void bitwise_or(const Bitmap &rhs);
461
462 //! Perform binary XOR
463 void bitwise_xor(const Bitmap &rhs);
464
465 //! Perform binary NOT (It will expand the whole map)
466 void bitwise_not(void);
467
468 //! Check if all bits are set to true
469 bool test_all(void) const;
470
471 //! Check if any bits are set to true
472 bool test_any(void) const;
473
474 //! Check if none of the bits are set to true
475 bool test_none(void) const;
476
477 //! Compute the cardinality of a bitmap
478 size_t cardinality(void) const;
479
480 //! Extract the bitmap to an array
481 void extract(size_t base, std::vector<size_t> *out) const;
482
483 //! Extract the bitmap to an array
484 void extract(std::vector<size_t> *out) const {
485 this->extract(0, out);
486 }
487
488 //! Compute the AND cardinality between two bitmaps
489 static size_t BitwiseAndCardinality(const Bitmap &lhs, const Bitmap &rhs);
490
491 //! Compute the ANDNOT cardinality between two bitmaps
492 static size_t BitwiseAndnotCardinality(const Bitmap &lhs, const Bitmap &rhs);
493
494 //! Compute the XOR cardinality between two bitmaps
495 static size_t BitwiseXorCardinality(const Bitmap &lhs, const Bitmap &rhs);
496
497 //! Compute the OR cardinality between two bitmaps
498 static size_t BitwiseOrCardinality(const Bitmap &lhs, const Bitmap &rhs);
499
500 protected:
501 //! Copy the content from another bitmap
502 void copy(const Bitmap &rhs);
503
504 private:
505 std::vector<Bucket *> array_;
506};
507
508} // namespace ailego
509
510#endif // __AILEGO_CONTAINER_BITMAP_H__
511