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