3 #ifndef INCLUDE_NN_NLIB_SMARTBITMAP_H_ 4 #define INCLUDE_NN_NLIB_SMARTBITMAP_H_ 13 NLIB_VIS_PUBLIC void BuildRankDictionary(
unsigned int word_count,
const uint32_t* bv,
15 NLIB_VIS_PUBLIC void BuildRankDictionary(
unsigned int word_count,
const uint64_t* bv,
18 NLIB_VIS_PUBLIC unsigned int CalcRank1(
unsigned int pos,
const uint32_t* bv,
const uint32_t* lv_a,
20 NLIB_VIS_PUBLIC unsigned int CalcRank1(
unsigned int pos,
const uint64_t* bv,
const uint32_t* lv_a,
26 NLIB_VIS_PUBLIC int CalcSelect1(
unsigned int nth,
unsigned int size,
const uint32_t* bv,
28 NLIB_VIS_PUBLIC int CalcSelect1(
unsigned int nth,
unsigned int size,
const uint64_t* bv,
31 NLIB_VIS_PUBLIC int CalcSelect0(
unsigned int nth,
unsigned int size,
const uint32_t* bv,
33 NLIB_VIS_PUBLIC int CalcSelect0(
unsigned int nth,
unsigned int size,
const uint64_t* bv,
38 template <
size_t N,
class Derived,
class BIT>
42 BLK_SIZE = 8 *
sizeof(BIT),
43 WORD_COUNT = (N + BLK_SIZE - 1) / BLK_SIZE,
44 LV_A_COUNT = (N + 256 - 1) / 256,
45 LV_B_COUNT = ((N + BLK_SIZE - 1) / BLK_SIZE + 3) & ~0x3
53 NLIB_ASSERT(This()->bitmap_);
54 if (is_dirty_) this->Build();
55 if (idx >= N)
return false;
56 unsigned int blk = idx / BLK_SIZE;
57 unsigned int ofs = idx % BLK_SIZE;
58 return 0 != (This()->bitmap_[blk] & (
static_cast<BIT
>(1) << ofs));
62 if (is_dirty_) this->Build();
63 unsigned int pos = idx < N ? idx : N - 1;
64 return detail::CalcRank1(pos, This()->bitmap_, lv_a_, lv_b_);
67 unsigned int rank1 = this->Rank1(idx);
68 return idx + 1 - rank1;
71 NLIB_ASSERT(This()->bitmap_);
72 if (nth >= this->Rank1(N - 1))
return -1;
73 return detail::CalcSelect1(nth, N, This()->bitmap_, lv_a_, lv_b_);
76 NLIB_ASSERT(This()->bitmap_);
77 if (nth >= this->Rank0(N - 1))
return -1;
78 return detail::CalcSelect0(nth, N, This()->bitmap_, lv_a_, lv_b_);
81 NLIB_ASSERT(This()->bitmap_);
82 if (idx >= N)
return false;
83 unsigned int blk = idx / BLK_SIZE;
84 unsigned int ofs = idx % BLK_SIZE;
85 if (!(This()->bitmap_[blk] & (static_cast<BIT>(1) << ofs))) {
86 This()->bitmap_[blk] |=
static_cast<BIT
>(1) << ofs;
93 NLIB_ASSERT(This()->bitmap_);
94 if (idx >= N)
return false;
95 unsigned int blk = idx / BLK_SIZE;
96 unsigned int ofs = idx % BLK_SIZE;
97 if (This()->bitmap_[blk] & (static_cast<BIT>(1) << ofs)) {
98 This()->bitmap_[blk] &= ~(
static_cast<BIT
>(1) << ofs);
104 return value ? this->Set(idx) : this->Unset(idx);
107 NLIB_ASSERT(This()->bitmap_);
110 nlib_memset(reinterpret_cast<void*>(&This()->bitmap_[0]),
112 static_cast<size_t>(WORD_COUNT *
sizeof(This()->bitmap_[0])));
121 static_cast<size_t>(LV_A_COUNT *
sizeof(lv_a_[0])));
124 static_cast<size_t>(LV_B_COUNT *
sizeof(lv_b_[0])));
128 Derived* This()
NLIB_NOEXCEPT {
return static_cast<Derived*
>(
this); }
129 const Derived* This()
const NLIB_NOEXCEPT {
return static_cast<const Derived*
>(
this); }
131 detail::BuildRankDictionary(WORD_COUNT, This()->bitmap_, lv_a_, lv_b_);
134 mutable bool is_dirty_;
135 mutable uint32_t lv_a_[LV_A_COUNT];
136 mutable uint8_t lv_b_[LV_B_COUNT];
140 template <
size_t N,
class BIT = u
int64_t>
142 template <
size_t N,
class BIT = u
int32_t>
151 BIT bitmap_[CrtpBase::WORD_COUNT];
156 template <
size_t N,
class BIT = u
int64_t>
158 template <
size_t N,
class BIT = u
int32_t>
165 enum { ARRAY_SIZE = CrtpBase::WORD_COUNT };
179 #endif // INCLUDE_NN_NLIB_SMARTBITMAP_H_ int Select1(unsigned int nth) const noexcept
Returns the position of the nth 1 bit. nth starts from 0.
The data structure holding bit data operated on by Rank and Select.
bool TurnOn(unsigned int idx) noexcept
Adds a 32-bit unsigned integer to the set.
const BIT * GetBitVector() const noexcept
Returns the pointer to the bit data.
bool Unset(unsigned int idx) noexcept
Removes a 32-bit unsigned integer from the set.
bool Set(unsigned int idx, bool value) noexcept
Sets bits in the bit data.
void Init(BIT *bitmap) noexcept
Sets a pointer to the bit data.
bool operator[](const unsigned int idx) const noexcept
Tests to determine whether a particular value is contained in the set.
#define NLIB_NOEXCEPT
Defines noexcept geared to the environment, or the equivalent.
A file that contains the configuration information for each development environment.
int Select0(unsigned int nth) const noexcept
Returns the position of the nth 0 bit. nth starts from 0.
unsigned int Rank0(unsigned int idx) const noexcept
Performs a Rank operation.
unsigned int GetBitVectorSize() const noexcept
Returns the size of the bit data.
void Reset() noexcept
Returns the object to the state immediately after the constructor is called.
#define NLIB_FINAL
Defines final if it is available for use. If not, holds an empty string.
The data structure holding bit data operated on by Rank and Select.
bool Set(unsigned int idx) noexcept
Adds a 32-bit unsigned integer to the set.
The data structure holding bit data operated on by Rank and Select.
bool Has(unsigned int idx) const noexcept
Tests to determine whether a particular value is contained in the set.
unsigned int Rank1(unsigned int idx) const noexcept
Performs a Rank operation.