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