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
環境に合わせてnoexcept 又は同等の定義がされます。
bool operator[](const unsigned int idx) const noexcept
値が集合に含まれているかどうかをテストします。
#define NLIB_FINAL
利用可能であればfinalが定義されます。そうでない場合は空文字列です。
Rank/Select操作つきのビットデータを保持するデータ構造です。
bool TurnOn(unsigned int idx) noexcept
集合に32bit符号なし整数を追加します。
int Select0(unsigned int nth) const noexcept
nth 番目の0ビットの場所を返します。nth は0から開始します。
bool Unset(unsigned int idx) noexcept
集合から32bit符号なし整数を取り除きます。
const BIT * GetBitVector() const noexcept
ビットデータへのポインタを返します。
bool Set(unsigned int idx, bool value) noexcept
ビットデータのビットを設定します。
int Select1(unsigned int nth) const noexcept
nth 番目の1ビットの場所を返します。nth は0から開始します。
bool Has(unsigned int idx) const noexcept
値が集合に含まれているかどうかをテストします。
unsigned int GetBitVectorSize() const noexcept
ビットデータのサイズを返します。
void Init(BIT *bitmap) noexcept
ビットデータへのポインタを設定します。
unsigned int Rank0(unsigned int idx) const noexcept
Rank操作を行います。
void Reset() noexcept
オブジェクトをコンストラクタが呼ばれた直後の状態にします。
unsigned int Rank1(unsigned int idx) const noexcept
Rank操作を行います。
Rank/Select操作つきのビットデータを保持するデータ構造です。
bool Set(unsigned int idx) noexcept
集合に32bit符号なし整数を追加します。
Rank/Select操作つきのビットデータを保持するデータ構造です。