nlib
SmartBitmap.h
[詳解]
1 
2 /*--------------------------------------------------------------------------------*
3  Project: CrossRoad
4  Copyright (C)Nintendo All rights reserved.
5 
6  These coded instructions, statements, and computer programs contain proprietary
7  information of Nintendo and/or its licensed developers and are protected by
8  national and international copyright laws. They may not be disclosed to third
9  parties or copied or duplicated in any form, in whole or in part, without the
10  prior written consent of Nintendo.
11 
12  The content herein is highly confidential and should be handled accordingly.
13  *--------------------------------------------------------------------------------*/
14 
15 #pragma once
16 #ifndef INCLUDE_NN_NLIB_SMARTBITMAP_H_
17 #define INCLUDE_NN_NLIB_SMARTBITMAP_H_
18 
19 #include <string.h>
20 
21 #include "nn/nlib/Config.h"
22 
23 NLIB_NAMESPACE_BEGIN
24 namespace detail {
25 
26 NLIB_VIS_PUBLIC void BuildRankDictionary(unsigned int word_count, const uint32_t* bv,
27  uint32_t* lv_a, uint8_t* lv_b) NLIB_NOEXCEPT;
28 NLIB_VIS_PUBLIC void BuildRankDictionary(unsigned int word_count, const uint64_t* bv,
29  uint32_t* lv_a, uint8_t* lv_b) NLIB_NOEXCEPT;
30 
31 NLIB_VIS_PUBLIC unsigned int CalcRank1(unsigned int pos, const uint32_t* bv, const uint32_t* lv_a,
32  const uint8_t* lv_b) NLIB_NOEXCEPT;
33 NLIB_VIS_PUBLIC unsigned int CalcRank1(unsigned int pos, const uint64_t* bv, const uint32_t* lv_a,
34  const uint8_t* lv_b) NLIB_NOEXCEPT;
35 
36 NLIB_VIS_PUBLIC int SelectPos(uint32_t r, size_t p) NLIB_NOEXCEPT;
37 NLIB_VIS_PUBLIC int SelectPos(uint64_t r, size_t p) NLIB_NOEXCEPT;
38 
39 NLIB_VIS_PUBLIC int CalcSelect1(unsigned int nth, unsigned int size, const uint32_t* bv,
40  const uint32_t* lv_a, const uint8_t* lv_b) NLIB_NOEXCEPT;
41 NLIB_VIS_PUBLIC int CalcSelect1(unsigned int nth, unsigned int size, const uint64_t* bv,
42  const uint32_t* lv_a, const uint8_t* lv_b) NLIB_NOEXCEPT;
43 
44 NLIB_VIS_PUBLIC int CalcSelect0(unsigned int nth, unsigned int size, const uint32_t* bv,
45  const uint32_t* lv_a, const uint8_t* lv_b) NLIB_NOEXCEPT;
46 NLIB_VIS_PUBLIC int CalcSelect0(unsigned int nth, unsigned int size, const uint64_t* bv,
47  const uint32_t* lv_a, const uint8_t* lv_b) NLIB_NOEXCEPT;
48 
49 } // namespace detail
50 
51 template <size_t N, class Derived, class BIT>
53  protected:
54  enum {
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
63  };
64 
65  public:
67  unsigned int GetBitVectorSize() const NLIB_NOEXCEPT { return N; }
68  const BIT* GetBitVector() const NLIB_NOEXCEPT { return This()->bitmap_; }
69  bool Has(unsigned int idx) const NLIB_NOEXCEPT {
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));
76  }
77  bool operator[](const unsigned int idx) const NLIB_NOEXCEPT { return this->Has(idx); }
78  unsigned int Rank1(unsigned int idx) const NLIB_NOEXCEPT {
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_);
82  }
83  unsigned int Rank0(unsigned int idx) const NLIB_NOEXCEPT {
84  unsigned int rank1 = this->Rank1(idx);
85  return idx + 1 - rank1;
86  }
87  int Select1(unsigned int nth) const NLIB_NOEXCEPT {
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_);
91  }
92  int Select0(unsigned int nth) const NLIB_NOEXCEPT {
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_);
96  }
97  bool Set(unsigned int idx) NLIB_NOEXCEPT {
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;
104  is_dirty_ = true;
105  }
106  return true;
107  }
108  bool TurnOn(unsigned int idx) NLIB_NOEXCEPT { return this->Set(idx); }
109  bool Unset(unsigned int idx) NLIB_NOEXCEPT {
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);
116  is_dirty_ = true;
117  }
118  return true;
119  }
120  bool Set(unsigned int idx, bool value) NLIB_NOEXCEPT {
121  return value ? this->Set(idx) : this->Unset(idx);
122  }
124  NLIB_ASSERT(This()->bitmap_);
125  this->ResetBase();
126  // cast is for armcc
127  nlib_memset(reinterpret_cast<void*>(&This()->bitmap_[0]),
128  0,
129  static_cast<size_t>(kWordCount * sizeof(This()->bitmap_[0])));
130  }
131 
132  protected:
133  void ResetBase() NLIB_NOEXCEPT {
134  is_dirty_ = true;
135  // cast is for armcc
136  nlib_memset(reinterpret_cast<void*>(&lv_a_[0]),
137  0,
138  static_cast<size_t>(kLvACount * sizeof(lv_a_[0])));
139  nlib_memset(reinterpret_cast<void*>(&lv_b_[0]),
140  0,
141  static_cast<size_t>(kLvBCount * sizeof(lv_b_[0])));
142  }
143 
144  private:
145  Derived* This() NLIB_NOEXCEPT { return static_cast<Derived*>(this); }
146  const Derived* This() const NLIB_NOEXCEPT { return static_cast<const Derived*>(this); }
147  void Build() const NLIB_NOEXCEPT {
148  detail::BuildRankDictionary(kWordCount, This()->bitmap_, lv_a_, lv_b_);
149  is_dirty_ = false;
150  }
151  mutable bool is_dirty_;
152  mutable uint32_t lv_a_[kLvACount];
153  mutable uint8_t lv_b_[kLvBCount];
154 };
155 
156 #ifdef NLIB_64BIT
157 template <size_t N, class BIT = uint64_t>
158 #else
159 template <size_t N, class BIT = uint32_t>
160 #endif
161 class SmartBitmap NLIB_FINAL : public SmartBitmapCrtp<N, SmartBitmap<N, BIT>, BIT> {
163 
164  public:
165  SmartBitmap() NLIB_NOEXCEPT { this->Reset(); }
166 
167  private:
168  BIT bitmap_[CrtpBase::kWordCount];
169  friend class SmartBitmapCrtp<N, SmartBitmap<N, BIT>, BIT>;
170 };
171 
172 #ifdef NLIB_64BIT
173 template <size_t N, class BIT = uint64_t>
174 #else
175 template <size_t N, class BIT = uint32_t>
176 #endif
177 class SmartBitmapPtr NLIB_FINAL : public SmartBitmapCrtp<N, SmartBitmapPtr<N, BIT>, BIT> {
179 
180  public: // suppress doxygen warnings
182  enum {
183  kArraySize = CrtpBase::kWordCount,
184  ARRAY_SIZE = kArraySize
185  };
187  void Init(BIT* bitmap) NLIB_NOEXCEPT {
188  this->ResetBase();
189  bitmap_ = bitmap;
190  }
191 
192  private:
193  BIT* bitmap_;
194  friend class SmartBitmapCrtp<N, SmartBitmapPtr<N, BIT>, BIT>;
195 };
196 
197 NLIB_NAMESPACE_END
198 
199 #endif // INCLUDE_NN_NLIB_SMARTBITMAP_H_
int Select1(unsigned int nth) const noexcept
nth 番目の1ビットの場所を返します。nth は0から開始します。
Definition: SmartBitmap.h:87
static errno_t nlib_memset(void *buf, int ch, size_t n)
内部でmemset(buf, ch, n)相当の関数を呼び出します。
Definition: Platform.h:2389
Rank/Select操作つきのビットデータを保持するデータ構造です。
Definition: SmartBitmap.h:52
bool TurnOn(unsigned int idx) noexcept
集合に32bit符号なし整数を追加します。
Definition: SmartBitmap.h:108
const BIT * GetBitVector() const noexcept
ビットデータへのポインタを返します。
Definition: SmartBitmap.h:68
#define NLIB_VIS_PUBLIC
関数やクラス等のシンボルをライブラリの外部に公開します。
Definition: Platform_unix.h:89
bool Unset(unsigned int idx) noexcept
集合から32bit符号なし整数を取り除きます。
Definition: SmartBitmap.h:109
bool Set(unsigned int idx, bool value) noexcept
ビットデータのビットを設定します。
Definition: SmartBitmap.h:120
void Init(BIT *bitmap) noexcept
ビットデータへのポインタを設定します。
Definition: SmartBitmap.h:187
bool operator[](const unsigned int idx) const noexcept
値が集合に含まれているかどうかをテストします。
Definition: SmartBitmap.h:77
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
Definition: Config.h:99
開発環境別の設定が書かれるファイルです。
int Select0(unsigned int nth) const noexcept
nth 番目の0ビットの場所を返します。nth は0から開始します。
Definition: SmartBitmap.h:92
unsigned int Rank0(unsigned int idx) const noexcept
Rank操作を行います。
Definition: SmartBitmap.h:83
unsigned int GetBitVectorSize() const noexcept
ビットデータのサイズを返します。
Definition: SmartBitmap.h:67
void Reset() noexcept
オブジェクトをコンストラクタが呼ばれた直後の状態にします。
Definition: SmartBitmap.h:123
#define NLIB_FINAL
利用可能であればfinalが定義されます。そうでない場合は空文字列です。
Definition: Config.h:229
Rank/Select操作つきのビットデータを保持するデータ構造です。
Definition: SmartBitmap.h:177
bool Set(unsigned int idx) noexcept
集合に32bit符号なし整数を追加します。
Definition: SmartBitmap.h:97
Rank/Select操作つきのビットデータを保持するデータ構造です。
Definition: SmartBitmap.h:161
bool Has(unsigned int idx) const noexcept
値が集合に含まれているかどうかをテストします。
Definition: SmartBitmap.h:69
unsigned int Rank1(unsigned int idx) const noexcept
Rank操作を行います。
Definition: SmartBitmap.h:78