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
66 NLIB_ASSERT(This()->bitmap_);
67 if (is_dirty_) this->Build();
68 if (idx >= N)
return false;
69 unsigned int blk = idx / kBlockSize;
70 unsigned int ofs = idx % kBlockSize;
71 return 0 != (This()->bitmap_[blk] & (
static_cast<BIT
>(1) << ofs));
75 if (is_dirty_) this->Build();
76 unsigned int pos = idx < N ? idx : N - 1;
77 return detail::CalcRank1(pos, This()->bitmap_, lv_a_, lv_b_);
80 unsigned int rank1 = this->Rank1(idx);
81 return idx + 1 - rank1;
84 NLIB_ASSERT(This()->bitmap_);
85 if (nth >= this->Rank1(N - 1))
return -1;
86 return detail::CalcSelect1(nth, N, This()->bitmap_, lv_a_, lv_b_);
89 NLIB_ASSERT(This()->bitmap_);
90 if (nth >= this->Rank0(N - 1))
return -1;
91 return detail::CalcSelect0(nth, N, This()->bitmap_, lv_a_, lv_b_);
94 NLIB_ASSERT(This()->bitmap_);
95 if (idx >= N)
return false;
96 unsigned int blk = idx / kBlockSize;
97 unsigned int ofs = idx % kBlockSize;
98 if (!(This()->bitmap_[blk] & (static_cast<BIT>(1) << ofs))) {
99 This()->bitmap_[blk] |=
static_cast<BIT
>(1) << ofs;
106 NLIB_ASSERT(This()->bitmap_);
107 if (idx >= N)
return false;
108 unsigned int blk = idx / kBlockSize;
109 unsigned int ofs = idx % kBlockSize;
110 if (This()->bitmap_[blk] & (static_cast<BIT>(1) << ofs)) {
111 This()->bitmap_[blk] &= ~(
static_cast<BIT
>(1) << ofs);
117 return value ? this->Set(idx) : this->Unset(idx);
120 NLIB_ASSERT(This()->bitmap_);
123 nlib_memset(static_cast<void*>(&This()->bitmap_[0]), 0,
124 static_cast<size_t>(kWordCount *
sizeof(This()->bitmap_[0])));
132 static_cast<size_t>(kLvACount *
sizeof(lv_a_[0])));
134 static_cast<size_t>(kLvBCount *
sizeof(lv_b_[0])));
138 Derived* This()
NLIB_NOEXCEPT {
return static_cast<Derived*
>(
this); }
139 const Derived* This() const
NLIB_NOEXCEPT {
return static_cast<const Derived*
>(
this); }
141 detail::BuildRankDictionary(kWordCount, This()->bitmap_, lv_a_, lv_b_);
144 mutable bool is_dirty_;
145 mutable uint32_t lv_a_[kLvACount];
146 mutable uint8_t lv_b_[kLvBCount];
150 template<
size_t N,
class BIT = u
int64_t>
152 template<
size_t N,
class BIT = u
int32_t>
161 BIT bitmap_[CrtpBase::kWordCount];
166 template<
size_t N,
class BIT = u
int64_t>
168 template<
size_t N,
class BIT = u
int32_t>
175 enum { kArraySize = CrtpBase::kWordCount };
189 #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.