3 #ifndef INCLUDE_NN_NLIB_SMARTBITMAP_H_
4 #define INCLUDE_NN_NLIB_SMARTBITMAP_H_
13 NLIB_VIS_PUBLIC void BuildRankDictionary(
unsigned int wordCount,
const uint32_t* bv, uint32_t* lv_a,
15 NLIB_VIS_PUBLIC void BuildRankDictionary(
unsigned int wordCount,
const uint64_t* bv, uint32_t* lv_a,
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
54 NLIB_ASSERT(This()->m_Bitmap);
55 if (m_IsDirty) this->Build();
56 if (idx >= N)
return false;
57 unsigned int blk = idx / BLK_SIZE;
58 unsigned int ofs = idx % BLK_SIZE;
59 return 0 != (This()->m_Bitmap[blk] & (
static_cast<BIT
>(1) << ofs));
63 if (m_IsDirty) this->Build();
64 unsigned int pos = idx < N ? idx : N - 1;
65 return detail::CalcRank1(pos, This()->m_Bitmap, m_LvA, m_LvB);
68 unsigned int rank1 = this->Rank1(idx);
69 return idx + 1 - rank1;
72 NLIB_ASSERT(This()->m_Bitmap);
73 if (nth >= this->Rank1(N - 1))
return -1;
74 return detail::CalcSelect1(nth, N, This()->m_Bitmap, m_LvA, m_LvB);
77 NLIB_ASSERT(This()->m_Bitmap);
78 if (nth >= this->Rank0(N - 1))
return -1;
79 return detail::CalcSelect0(nth, N, This()->m_Bitmap, m_LvA, m_LvB);
82 NLIB_ASSERT(This()->m_Bitmap);
83 if (idx >= N)
return false;
84 unsigned int blk = idx / BLK_SIZE;
85 unsigned int ofs = idx % BLK_SIZE;
86 if (!(This()->m_Bitmap[blk] & (static_cast<BIT>(1) << ofs))) {
87 This()->m_Bitmap[blk] |=
static_cast<BIT
>(1) << ofs;
94 NLIB_ASSERT(This()->m_Bitmap);
95 if (idx >= N)
return false;
96 unsigned int blk = idx / BLK_SIZE;
97 unsigned int ofs = idx % BLK_SIZE;
98 if (This()->m_Bitmap[blk] & (static_cast<BIT>(1) << ofs)) {
99 This()->m_Bitmap[blk] &= ~(
static_cast<BIT
>(1) << ofs);
105 return value ? this->Set(idx) : this->Unset(idx);
108 NLIB_ASSERT(This()->m_Bitmap);
111 nlib_memset(reinterpret_cast<void*>(&This()->m_Bitmap[0]),
113 static_cast<size_t>(WORD_COUNT *
sizeof(This()->m_Bitmap[0])));
122 static_cast<size_t>(LV_A_COUNT *
sizeof(m_LvA[0])));
125 static_cast<size_t>(LV_B_COUNT *
sizeof(m_LvB[0])));
129 Derived* This()
NLIB_NOEXCEPT {
return static_cast<Derived*
>(
this); }
130 const Derived* This() const
NLIB_NOEXCEPT {
return static_cast<const Derived*
>(
this); }
132 detail::BuildRankDictionary(WORD_COUNT, This()->m_Bitmap, m_LvA, m_LvB);
135 mutable bool m_IsDirty;
136 mutable uint32_t m_LvA[LV_A_COUNT];
137 mutable uint8_t m_LvB[LV_B_COUNT];
141 template <
size_t N,
class BIT = u
int64_t>
143 template <
size_t N,
class BIT = u
int32_t>
153 BIT m_Bitmap[CrtpBase::WORD_COUNT];
158 template <
size_t N,
class BIT = u
int64_t>
160 template <
size_t N,
class BIT = u
int32_t>
167 enum { ARRAY_SIZE = CrtpBase::WORD_COUNT };
182 #endif // INCLUDE_NN_NLIB_SMARTBITMAP_H_
#define NLIB_NOEXCEPT
Defines noexcept geared to the environment, or the equivalent.
bool operator[](const unsigned int idx) const noexcept
Tests to determine whether a particular value is contained in the set.
#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 TurnOn(unsigned int idx) noexcept
Adds a 32-bit unsigned integer to the set.
int Select0(unsigned int nth) const noexcept
Returns the position of the nth 0 bit. nth starts from 0.
bool Unset(unsigned int idx) noexcept
Removes a 32-bit unsigned integer from the set.
const BIT * GetBitVector() const noexcept
Returns the pointer to the bit data.
bool Set(unsigned int idx, bool value) noexcept
Sets bits in the bit data.
int Select1(unsigned int nth) const noexcept
Returns the position of the nth 1 bit. nth starts from 0.
bool Has(unsigned int idx) const noexcept
Tests to determine whether a particular value is contained in the set.
unsigned int GetBitVectorSize() const noexcept
Returns the size of the bit data.
void Init(BIT *bitmap) noexcept
Sets a pointer to the bit data.
A file that contains the configuration information for each development environment.
unsigned int Rank0(unsigned int idx) const noexcept
Performs a Rank operation.
void Reset() noexcept
Returns the object to the state immediately after the constructor is called.
unsigned int Rank1(unsigned int idx) const noexcept
Performs a Rank operation.
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.