16 #ifndef INCLUDE_NN_NLIB_SMARTBITMAP_H_ 17 #define INCLUDE_NN_NLIB_SMARTBITMAP_H_ 26 NLIB_VIS_PUBLIC void BuildRankDictionary(
unsigned int word_count,
const uint32_t* bv,
28 NLIB_VIS_PUBLIC void BuildRankDictionary(
unsigned int word_count,
const uint64_t* bv,
31 NLIB_VIS_PUBLIC unsigned int CalcRank1(
unsigned int pos,
const uint32_t* bv,
const uint32_t* lv_a,
33 NLIB_VIS_PUBLIC unsigned int CalcRank1(
unsigned int pos,
const uint64_t* bv,
const uint32_t* lv_a,
39 NLIB_VIS_PUBLIC int CalcSelect1(
unsigned int nth,
unsigned int size,
const uint32_t* bv,
41 NLIB_VIS_PUBLIC int CalcSelect1(
unsigned int nth,
unsigned int size,
const uint64_t* bv,
44 NLIB_VIS_PUBLIC int CalcSelect0(
unsigned int nth,
unsigned int size,
const uint32_t* bv,
46 NLIB_VIS_PUBLIC int CalcSelect0(
unsigned int nth,
unsigned int size,
const uint64_t* bv,
51 template <
size_t N,
class Derived,
class BIT>
55 kBlockSize = 8 *
sizeof(BIT),
56 kWordCount = (N + kBlockSize - 1) / kBlockSize,
57 kLvACount = (N + 256 - 1) / 256,
58 kLvBCount = ((N + kBlockSize - 1) / kBlockSize + 3) & ~0x3,
59 BLK_SIZE = kBlockSize,
60 WORD_COUNT = kWordCount,
61 LV_A_COUNT = kLvACount,
62 LV_B_COUNT = kLvBCount
70 NLIB_ASSERT(This()->bitmap_);
71 if (is_dirty_) this->Build();
72 if (idx >= N)
return false;
73 unsigned int blk = idx / kBlockSize;
74 unsigned int ofs = idx % kBlockSize;
75 return 0 != (This()->bitmap_[blk] & (
static_cast<BIT
>(1) << ofs));
79 if (is_dirty_) this->Build();
80 unsigned int pos = idx < N ? idx : N - 1;
81 return detail::CalcRank1(pos, This()->bitmap_, lv_a_, lv_b_);
84 unsigned int rank1 = this->Rank1(idx);
85 return idx + 1 - rank1;
88 NLIB_ASSERT(This()->bitmap_);
89 if (nth >= this->Rank1(N - 1))
return -1;
90 return detail::CalcSelect1(nth, N, This()->bitmap_, lv_a_, lv_b_);
93 NLIB_ASSERT(This()->bitmap_);
94 if (nth >= this->Rank0(N - 1))
return -1;
95 return detail::CalcSelect0(nth, N, This()->bitmap_, lv_a_, lv_b_);
98 NLIB_ASSERT(This()->bitmap_);
99 if (idx >= N)
return false;
100 unsigned int blk = idx / kBlockSize;
101 unsigned int ofs = idx % kBlockSize;
102 if (!(This()->bitmap_[blk] & (static_cast<BIT>(1) << ofs))) {
103 This()->bitmap_[blk] |=
static_cast<BIT
>(1) << ofs;
110 NLIB_ASSERT(This()->bitmap_);
111 if (idx >= N)
return false;
112 unsigned int blk = idx / kBlockSize;
113 unsigned int ofs = idx % kBlockSize;
114 if (This()->bitmap_[blk] & (static_cast<BIT>(1) << ofs)) {
115 This()->bitmap_[blk] &= ~(
static_cast<BIT
>(1) << ofs);
121 return value ? this->Set(idx) : this->Unset(idx);
124 NLIB_ASSERT(This()->bitmap_);
127 nlib_memset(static_cast<void*>(&This()->bitmap_[0]),
129 static_cast<size_t>(kWordCount *
sizeof(This()->bitmap_[0])));
138 static_cast<size_t>(kLvACount *
sizeof(lv_a_[0])));
141 static_cast<size_t>(kLvBCount *
sizeof(lv_b_[0])));
145 Derived* This()
NLIB_NOEXCEPT {
return static_cast<Derived*
>(
this); }
146 const Derived* This()
const NLIB_NOEXCEPT {
return static_cast<const Derived*
>(
this); }
148 detail::BuildRankDictionary(kWordCount, This()->bitmap_, lv_a_, lv_b_);
151 mutable bool is_dirty_;
152 mutable uint32_t lv_a_[kLvACount];
153 mutable uint8_t lv_b_[kLvBCount];
157 template <
size_t N,
class BIT = u
int64_t>
159 template <
size_t N,
class BIT = u
int32_t>
168 BIT bitmap_[CrtpBase::kWordCount];
173 template <
size_t N,
class BIT = u
int64_t>
175 template <
size_t N,
class BIT = u
int32_t>
183 kArraySize = CrtpBase::kWordCount,
184 ARRAY_SIZE = kArraySize
199 #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.