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  };
60 
61  public:
63  unsigned int GetBitVectorSize() const NLIB_NOEXCEPT { return N; }
64  const BIT* GetBitVector() const NLIB_NOEXCEPT { return This()->bitmap_; }
65  bool Has(unsigned int idx) const NLIB_NOEXCEPT {
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));
72  }
73  bool operator[](const unsigned int idx) const NLIB_NOEXCEPT { return this->Has(idx); }
74  unsigned int Rank1(unsigned int idx) const NLIB_NOEXCEPT {
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_);
78  }
79  unsigned int Rank0(unsigned int idx) const NLIB_NOEXCEPT {
80  unsigned int rank1 = this->Rank1(idx);
81  return idx + 1 - rank1;
82  }
83  int Select1(unsigned int nth) const NLIB_NOEXCEPT {
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_);
87  }
88  int Select0(unsigned int nth) const NLIB_NOEXCEPT {
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_);
92  }
93  bool Set(unsigned int idx) NLIB_NOEXCEPT {
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;
100  is_dirty_ = true;
101  }
102  return true;
103  }
104  bool TurnOn(unsigned int idx) NLIB_NOEXCEPT { return this->Set(idx); }
105  bool Unset(unsigned int idx) NLIB_NOEXCEPT {
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);
112  is_dirty_ = true;
113  }
114  return true;
115  }
116  bool Set(unsigned int idx, bool value) NLIB_NOEXCEPT {
117  return value ? this->Set(idx) : this->Unset(idx);
118  }
120  NLIB_ASSERT(This()->bitmap_);
121  this->ResetBase();
122  // cast is for armcc
123  nlib_memset(static_cast<void*>(&This()->bitmap_[0]), 0,
124  static_cast<size_t>(kWordCount * sizeof(This()->bitmap_[0])));
125  }
126 
127  protected:
128  void ResetBase() NLIB_NOEXCEPT {
129  is_dirty_ = true;
130  // cast is for armcc
131  nlib_memset(static_cast<void*>(&lv_a_[0]), 0,
132  static_cast<size_t>(kLvACount * sizeof(lv_a_[0])));
133  nlib_memset(static_cast<void*>(&lv_b_[0]), 0,
134  static_cast<size_t>(kLvBCount * sizeof(lv_b_[0])));
135  }
136 
137  private:
138  Derived* This() NLIB_NOEXCEPT { return static_cast<Derived*>(this); }
139  const Derived* This() const NLIB_NOEXCEPT { return static_cast<const Derived*>(this); }
140  void Build() const NLIB_NOEXCEPT {
141  detail::BuildRankDictionary(kWordCount, This()->bitmap_, lv_a_, lv_b_);
142  is_dirty_ = false;
143  }
144  mutable bool is_dirty_;
145  mutable uint32_t lv_a_[kLvACount];
146  mutable uint8_t lv_b_[kLvBCount];
147 };
148 
149 #ifdef NLIB_64BIT
150 template<size_t N, class BIT = uint64_t>
151 #else
152 template<size_t N, class BIT = uint32_t>
153 #endif
154 class SmartBitmap NLIB_FINAL : public SmartBitmapCrtp<N, SmartBitmap<N, BIT>, BIT> {
156 
157  public:
158  SmartBitmap() NLIB_NOEXCEPT { this->Reset(); }
159 
160  private:
161  BIT bitmap_[CrtpBase::kWordCount];
162  friend class SmartBitmapCrtp<N, SmartBitmap<N, BIT>, BIT>;
163 };
164 
165 #ifdef NLIB_64BIT
166 template<size_t N, class BIT = uint64_t>
167 #else
168 template<size_t N, class BIT = uint32_t>
169 #endif
170 class SmartBitmapPtr NLIB_FINAL : public SmartBitmapCrtp<N, SmartBitmapPtr<N, BIT>, BIT> {
172 
173  public: // suppress doxygen warnings
175  enum { kArraySize = CrtpBase::kWordCount };
177  void Init(BIT* bitmap) NLIB_NOEXCEPT {
178  this->ResetBase();
179  bitmap_ = bitmap;
180  }
181 
182  private:
183  BIT* bitmap_;
184  friend class SmartBitmapCrtp<N, SmartBitmapPtr<N, BIT>, BIT>;
185 };
186 
187 NLIB_NAMESPACE_END
188 
189 #endif // INCLUDE_NN_NLIB_SMARTBITMAP_H_
int Select1(unsigned int nth) const noexcept
nth 番目の1ビットの場所を返します。nth は0から開始します。
Definition: SmartBitmap.h:83
static errno_t nlib_memset(void *buf, int ch, size_t n)
内部でmemset(buf, ch, n)相当の関数を呼び出します。
Definition: Platform.h:2544
Rank/Select操作つきのビットデータを保持するデータ構造です。
Definition: SmartBitmap.h:52
bool TurnOn(unsigned int idx) noexcept
集合に32bit符号なし整数を追加します。
Definition: SmartBitmap.h:104
const BIT * GetBitVector() const noexcept
ビットデータへのポインタを返します。
Definition: SmartBitmap.h:64
#define NLIB_VIS_PUBLIC
関数やクラス等のシンボルをライブラリの外部に公開します。
Definition: Platform_unix.h:87
bool Unset(unsigned int idx) noexcept
集合から32bit符号なし整数を取り除きます。
Definition: SmartBitmap.h:105
bool Set(unsigned int idx, bool value) noexcept
ビットデータのビットを設定します。
Definition: SmartBitmap.h:116
void Init(BIT *bitmap) noexcept
ビットデータへのポインタを設定します。
Definition: SmartBitmap.h:177
bool operator[](const unsigned int idx) const noexcept
値が集合に含まれているかどうかをテストします。
Definition: SmartBitmap.h:73
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
Definition: Config.h:109
開発環境別の設定が書かれるファイルです。
int Select0(unsigned int nth) const noexcept
nth 番目の0ビットの場所を返します。nth は0から開始します。
Definition: SmartBitmap.h:88
unsigned int Rank0(unsigned int idx) const noexcept
Rank操作を行います。
Definition: SmartBitmap.h:79
unsigned int GetBitVectorSize() const noexcept
ビットデータのサイズを返します。
Definition: SmartBitmap.h:63
void Reset() noexcept
オブジェクトをコンストラクタが呼ばれた直後の状態にします。
Definition: SmartBitmap.h:119
#define NLIB_FINAL
利用可能であればfinalが定義されます。そうでない場合は空文字列です。
Definition: Config.h:250
Rank/Select操作つきのビットデータを保持するデータ構造です。
Definition: SmartBitmap.h:170
bool Set(unsigned int idx) noexcept
集合に32bit符号なし整数を追加します。
Definition: SmartBitmap.h:93
Rank/Select操作つきのビットデータを保持するデータ構造です。
Definition: SmartBitmap.h:154
bool Has(unsigned int idx) const noexcept
値が集合に含まれているかどうかをテストします。
Definition: SmartBitmap.h:65
unsigned int Rank1(unsigned int idx) const noexcept
Rank操作を行います。
Definition: SmartBitmap.h:74