nlib
SmartBitmap.h
[詳解]
1 
2 #pragma once
3 #ifndef INCLUDE_NN_NLIB_SMARTBITMAP_H_
4 #define INCLUDE_NN_NLIB_SMARTBITMAP_H_
5 
6 #include <string.h>
7 
8 #include "nn/nlib/Config.h"
9 
10 NLIB_NAMESPACE_BEGIN
11 namespace detail {
12 
13 NLIB_VIS_PUBLIC void BuildRankDictionary(unsigned int word_count, const uint32_t* bv,
14  uint32_t* lv_a, uint8_t* lv_b) NLIB_NOEXCEPT;
15 NLIB_VIS_PUBLIC void BuildRankDictionary(unsigned int word_count, const uint64_t* bv,
16  uint32_t* lv_a, uint8_t* lv_b) NLIB_NOEXCEPT;
17 
18 NLIB_VIS_PUBLIC unsigned int CalcRank1(unsigned int pos, const uint32_t* bv, const uint32_t* lv_a,
19  const uint8_t* lv_b) NLIB_NOEXCEPT;
20 NLIB_VIS_PUBLIC unsigned int CalcRank1(unsigned int pos, const uint64_t* bv, const uint32_t* lv_a,
21  const uint8_t* lv_b) NLIB_NOEXCEPT;
22 
23 NLIB_VIS_PUBLIC int SelectPos(uint32_t r, size_t p) NLIB_NOEXCEPT;
24 NLIB_VIS_PUBLIC int SelectPos(uint64_t r, size_t p) NLIB_NOEXCEPT;
25 
26 NLIB_VIS_PUBLIC int CalcSelect1(unsigned int nth, unsigned int size, const uint32_t* bv,
27  const uint32_t* lv_a, const uint8_t* lv_b) NLIB_NOEXCEPT;
28 NLIB_VIS_PUBLIC int CalcSelect1(unsigned int nth, unsigned int size, const uint64_t* bv,
29  const uint32_t* lv_a, const uint8_t* lv_b) NLIB_NOEXCEPT;
30 
31 NLIB_VIS_PUBLIC int CalcSelect0(unsigned int nth, unsigned int size, const uint32_t* bv,
32  const uint32_t* lv_a, const uint8_t* lv_b) NLIB_NOEXCEPT;
33 NLIB_VIS_PUBLIC int CalcSelect0(unsigned int nth, unsigned int size, const uint64_t* bv,
34  const uint32_t* lv_a, const uint8_t* lv_b) NLIB_NOEXCEPT;
35 
36 } // namespace detail
37 
38 template <size_t N, class Derived, class BIT>
40  protected:
41  enum {
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
46  };
47 
48  public:
50  unsigned int GetBitVectorSize() const NLIB_NOEXCEPT { return N; }
51  const BIT* GetBitVector() const NLIB_NOEXCEPT { return This()->bitmap_; }
52  bool Has(unsigned int idx) const NLIB_NOEXCEPT {
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));
59  }
60  bool operator[](const unsigned int idx) const NLIB_NOEXCEPT { return this->Has(idx); }
61  unsigned int Rank1(unsigned int idx) const NLIB_NOEXCEPT {
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_);
65  }
66  unsigned int Rank0(unsigned int idx) const NLIB_NOEXCEPT {
67  unsigned int rank1 = this->Rank1(idx);
68  return idx + 1 - rank1;
69  }
70  int Select1(unsigned int nth) const NLIB_NOEXCEPT {
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_);
74  }
75  int Select0(unsigned int nth) const NLIB_NOEXCEPT {
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_);
79  }
80  bool Set(unsigned int idx) NLIB_NOEXCEPT {
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;
87  is_dirty_ = true;
88  }
89  return true;
90  }
91  bool TurnOn(unsigned int idx) NLIB_NOEXCEPT { return this->Set(idx); }
92  bool Unset(unsigned int idx) NLIB_NOEXCEPT {
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);
99  is_dirty_ = true;
100  }
101  return true;
102  }
103  bool Set(unsigned int idx, bool value) NLIB_NOEXCEPT {
104  return value ? this->Set(idx) : this->Unset(idx);
105  }
107  NLIB_ASSERT(This()->bitmap_);
108  this->ResetBase();
109  // cast is for armcc
110  nlib_memset(reinterpret_cast<void*>(&This()->bitmap_[0]),
111  0,
112  static_cast<size_t>(WORD_COUNT * sizeof(This()->bitmap_[0])));
113  }
114 
115  protected:
116  void ResetBase() NLIB_NOEXCEPT {
117  is_dirty_ = true;
118  // cast is for armcc
119  nlib_memset(reinterpret_cast<void*>(&lv_a_[0]),
120  0,
121  static_cast<size_t>(LV_A_COUNT * sizeof(lv_a_[0])));
122  nlib_memset(reinterpret_cast<void*>(&lv_b_[0]),
123  0,
124  static_cast<size_t>(LV_B_COUNT * sizeof(lv_b_[0])));
125  }
126 
127  private:
128  Derived* This() NLIB_NOEXCEPT { return static_cast<Derived*>(this); }
129  const Derived* This() const NLIB_NOEXCEPT { return static_cast<const Derived*>(this); }
130  void Build() const NLIB_NOEXCEPT {
131  detail::BuildRankDictionary(WORD_COUNT, This()->bitmap_, lv_a_, lv_b_);
132  is_dirty_ = false;
133  }
134  mutable bool is_dirty_;
135  mutable uint32_t lv_a_[LV_A_COUNT];
136  mutable uint8_t lv_b_[LV_B_COUNT];
137 };
138 
139 #ifdef NLIB_64BIT
140 template <size_t N, class BIT = uint64_t>
141 #else
142 template <size_t N, class BIT = uint32_t>
143 #endif
144 class SmartBitmap NLIB_FINAL : public SmartBitmapCrtp<N, SmartBitmap<N, BIT>, BIT> {
146 
147  public:
148  SmartBitmap() NLIB_NOEXCEPT { this->Reset(); }
149 
150  private:
151  BIT bitmap_[CrtpBase::WORD_COUNT];
152  friend class SmartBitmapCrtp<N, SmartBitmap<N, BIT>, BIT>;
153 };
154 
155 #ifdef NLIB_64BIT
156 template <size_t N, class BIT = uint64_t>
157 #else
158 template <size_t N, class BIT = uint32_t>
159 #endif
160 class SmartBitmapPtr NLIB_FINAL : public SmartBitmapCrtp<N, SmartBitmapPtr<N, BIT>, BIT> {
162 
163  public: // suppress doxygen warnings
165  enum { ARRAY_SIZE = CrtpBase::WORD_COUNT };
167  void Init(BIT* bitmap) NLIB_NOEXCEPT {
168  this->ResetBase();
169  bitmap_ = bitmap;
170  }
171 
172  private:
173  BIT* bitmap_;
174  friend class SmartBitmapCrtp<N, SmartBitmapPtr<N, BIT>, BIT>;
175 };
176 
177 NLIB_NAMESPACE_END
178 
179 #endif // INCLUDE_NN_NLIB_SMARTBITMAP_H_
int Select1(unsigned int nth) const noexcept
nth 番目の1ビットの場所を返します。nth は0から開始します。
Definition: SmartBitmap.h:70
static errno_t nlib_memset(void *buf, int ch, size_t n)
内部でmemset(buf, ch, n)相当の関数を呼び出します。
Definition: Platform.h:3202
Rank/Select操作つきのビットデータを保持するデータ構造です。
Definition: SmartBitmap.h:39
bool TurnOn(unsigned int idx) noexcept
集合に32bit符号なし整数を追加します。
Definition: SmartBitmap.h:91
const BIT * GetBitVector() const noexcept
ビットデータへのポインタを返します。
Definition: SmartBitmap.h:51
#define NLIB_VIS_PUBLIC
関数やクラス等のシンボルをライブラリの外部に公開します。
Definition: Platform_unix.h:61
bool Unset(unsigned int idx) noexcept
集合から32bit符号なし整数を取り除きます。
Definition: SmartBitmap.h:92
bool Set(unsigned int idx, bool value) noexcept
ビットデータのビットを設定します。
Definition: SmartBitmap.h:103
void Init(BIT *bitmap) noexcept
ビットデータへのポインタを設定します。
Definition: SmartBitmap.h:167
bool operator[](const unsigned int idx) const noexcept
値が集合に含まれているかどうかをテストします。
Definition: SmartBitmap.h:60
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
Definition: Config.h:86
開発環境別の設定が書かれるファイルです。
int Select0(unsigned int nth) const noexcept
nth 番目の0ビットの場所を返します。nth は0から開始します。
Definition: SmartBitmap.h:75
unsigned int Rank0(unsigned int idx) const noexcept
Rank操作を行います。
Definition: SmartBitmap.h:66
unsigned int GetBitVectorSize() const noexcept
ビットデータのサイズを返します。
Definition: SmartBitmap.h:50
void Reset() noexcept
オブジェクトをコンストラクタが呼ばれた直後の状態にします。
Definition: SmartBitmap.h:106
#define NLIB_FINAL
利用可能であればfinalが定義されます。そうでない場合は空文字列です。
Definition: Config.h:211
Rank/Select操作つきのビットデータを保持するデータ構造です。
Definition: SmartBitmap.h:160
bool Set(unsigned int idx) noexcept
集合に32bit符号なし整数を追加します。
Definition: SmartBitmap.h:80
Rank/Select操作つきのビットデータを保持するデータ構造です。
Definition: SmartBitmap.h:144
bool Has(unsigned int idx) const noexcept
値が集合に含まれているかどうかをテストします。
Definition: SmartBitmap.h:52
unsigned int Rank1(unsigned int idx) const noexcept
Rank操作を行います。
Definition: SmartBitmap.h:61