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(reinterpret_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
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操作を行います。