nlib
SmartBitmap.h
Go to the documentation of this file.
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 wordCount, const uint32_t* bv, uint32_t* lv_a,
14  uint8_t* lv_b) NLIB_NOEXCEPT;
15 NLIB_VIS_PUBLIC void BuildRankDictionary(unsigned int wordCount, const uint64_t* bv, uint32_t* lv_a,
16  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:
49  // cppcheck-suppress uninitMemberVar
51  unsigned int GetBitVectorSize() const NLIB_NOEXCEPT { return N; }
52  const BIT* GetBitVector() const NLIB_NOEXCEPT { return This()->m_Bitmap; }
53  bool Has(unsigned int idx) const NLIB_NOEXCEPT {
54  NLIB_ASSERT(This()->m_Bitmap);
55  if (m_IsDirty) this->Build();
56  if (idx >= N) return false;
57  unsigned int blk = idx / BLK_SIZE;
58  unsigned int ofs = idx % BLK_SIZE;
59  return 0 != (This()->m_Bitmap[blk] & (static_cast<BIT>(1) << ofs));
60  }
61  bool operator[](const unsigned int idx) const NLIB_NOEXCEPT { return this->Has(idx); }
62  unsigned int Rank1(unsigned int idx) const NLIB_NOEXCEPT {
63  if (m_IsDirty) this->Build();
64  unsigned int pos = idx < N ? idx : N - 1;
65  return detail::CalcRank1(pos, This()->m_Bitmap, m_LvA, m_LvB);
66  }
67  unsigned int Rank0(unsigned int idx) const NLIB_NOEXCEPT {
68  unsigned int rank1 = this->Rank1(idx);
69  return idx + 1 - rank1;
70  }
71  int Select1(unsigned int nth) const NLIB_NOEXCEPT {
72  NLIB_ASSERT(This()->m_Bitmap);
73  if (nth >= this->Rank1(N - 1)) return -1;
74  return detail::CalcSelect1(nth, N, This()->m_Bitmap, m_LvA, m_LvB);
75  }
76  int Select0(unsigned int nth) const NLIB_NOEXCEPT {
77  NLIB_ASSERT(This()->m_Bitmap);
78  if (nth >= this->Rank0(N - 1)) return -1;
79  return detail::CalcSelect0(nth, N, This()->m_Bitmap, m_LvA, m_LvB);
80  }
81  bool Set(unsigned int idx) NLIB_NOEXCEPT {
82  NLIB_ASSERT(This()->m_Bitmap);
83  if (idx >= N) return false;
84  unsigned int blk = idx / BLK_SIZE;
85  unsigned int ofs = idx % BLK_SIZE;
86  if (!(This()->m_Bitmap[blk] & (static_cast<BIT>(1) << ofs))) {
87  This()->m_Bitmap[blk] |= static_cast<BIT>(1) << ofs;
88  m_IsDirty = true;
89  }
90  return true;
91  }
92  bool TurnOn(unsigned int idx) NLIB_NOEXCEPT { return this->Set(idx); }
93  bool Unset(unsigned int idx) NLIB_NOEXCEPT {
94  NLIB_ASSERT(This()->m_Bitmap);
95  if (idx >= N) return false;
96  unsigned int blk = idx / BLK_SIZE;
97  unsigned int ofs = idx % BLK_SIZE;
98  if (This()->m_Bitmap[blk] & (static_cast<BIT>(1) << ofs)) {
99  This()->m_Bitmap[blk] &= ~(static_cast<BIT>(1) << ofs);
100  m_IsDirty = true;
101  }
102  return true;
103  }
104  bool Set(unsigned int idx, bool value) NLIB_NOEXCEPT {
105  return value ? this->Set(idx) : this->Unset(idx);
106  }
108  NLIB_ASSERT(This()->m_Bitmap);
109  this->ResetBase();
110  // cast is for armcc
111  nlib_memset(reinterpret_cast<void*>(&This()->m_Bitmap[0]),
112  0,
113  static_cast<size_t>(WORD_COUNT * sizeof(This()->m_Bitmap[0])));
114  }
115 
116  protected:
117  void ResetBase() NLIB_NOEXCEPT {
118  m_IsDirty = true;
119  // cast is for armcc
120  nlib_memset(reinterpret_cast<void*>(&m_LvA[0]),
121  0,
122  static_cast<size_t>(LV_A_COUNT * sizeof(m_LvA[0])));
123  nlib_memset(reinterpret_cast<void*>(&m_LvB[0]),
124  0,
125  static_cast<size_t>(LV_B_COUNT * sizeof(m_LvB[0])));
126  }
127 
128  private:
129  Derived* This() NLIB_NOEXCEPT { return static_cast<Derived*>(this); }
130  const Derived* This() const NLIB_NOEXCEPT { return static_cast<const Derived*>(this); }
131  void Build() const NLIB_NOEXCEPT {
132  detail::BuildRankDictionary(WORD_COUNT, This()->m_Bitmap, m_LvA, m_LvB);
133  m_IsDirty = false;
134  }
135  mutable bool m_IsDirty;
136  mutable uint32_t m_LvA[LV_A_COUNT];
137  mutable uint8_t m_LvB[LV_B_COUNT];
138 };
139 
140 #ifdef NLIB_64BIT
141 template <size_t N, class BIT = uint64_t>
142 #else
143 template <size_t N, class BIT = uint32_t>
144 #endif
145 class SmartBitmap NLIB_FINAL : public SmartBitmapCrtp<N, SmartBitmap<N, BIT>, BIT> {
147 
148  public:
149  // cppcheck-suppress uninitMemberVar
150  SmartBitmap() NLIB_NOEXCEPT { this->Reset(); }
151 
152  private:
153  BIT m_Bitmap[CrtpBase::WORD_COUNT];
154  friend class SmartBitmapCrtp<N, SmartBitmap<N, BIT>, BIT>;
155 };
156 
157 #ifdef NLIB_64BIT
158 template <size_t N, class BIT = uint64_t>
159 #else
160 template <size_t N, class BIT = uint32_t>
161 #endif
162 class SmartBitmapPtr NLIB_FINAL : public SmartBitmapCrtp<N, SmartBitmapPtr<N, BIT>, BIT> {
164 
165  public: // suppress doxygen warnings
167  enum { ARRAY_SIZE = CrtpBase::WORD_COUNT };
168  // cppcheck-suppress uninitMemberVar
170  void Init(BIT* bitmap) NLIB_NOEXCEPT {
171  this->ResetBase();
172  m_Bitmap = bitmap;
173  }
174 
175  private:
176  BIT* m_Bitmap;
177  friend class SmartBitmapCrtp<N, SmartBitmapPtr<N, BIT>, BIT>;
178 };
179 
180 NLIB_NAMESPACE_END
181 
182 #endif // INCLUDE_NN_NLIB_SMARTBITMAP_H_
#define NLIB_NOEXCEPT
Defines noexcept geared to the environment, or the equivalent.
Definition: Platform.h:2151
bool operator[](const unsigned int idx) const noexcept
Tests to determine whether a particular value is contained in the set.
Definition: SmartBitmap.h:61
#define NLIB_FINAL
Defines final if it is available for use. If not, holds an empty string.
The data structure holding bit data operated on by Rank and Select.
Definition: SmartBitmap.h:39
bool TurnOn(unsigned int idx) noexcept
Adds a 32-bit unsigned integer to the set.
Definition: SmartBitmap.h:92
int Select0(unsigned int nth) const noexcept
Returns the position of the nth 0 bit. nth starts from 0.
Definition: SmartBitmap.h:76
bool Unset(unsigned int idx) noexcept
Removes a 32-bit unsigned integer from the set.
Definition: SmartBitmap.h:93
const BIT * GetBitVector() const noexcept
Returns the pointer to the bit data.
Definition: SmartBitmap.h:52
bool Set(unsigned int idx, bool value) noexcept
Sets bits in the bit data.
Definition: SmartBitmap.h:104
int Select1(unsigned int nth) const noexcept
Returns the position of the nth 1 bit. nth starts from 0.
Definition: SmartBitmap.h:71
bool Has(unsigned int idx) const noexcept
Tests to determine whether a particular value is contained in the set.
Definition: SmartBitmap.h:53
errno_t nlib_memset(void *buf, int ch, size_t n)
Makes a function call corresponding to memset(buf, ch, n).
Definition: Platform.h:2117
unsigned int GetBitVectorSize() const noexcept
Returns the size of the bit data.
Definition: SmartBitmap.h:51
void Init(BIT *bitmap) noexcept
Sets a pointer to the bit data.
Definition: SmartBitmap.h:170
A file that contains the configuration information for each development environment.
unsigned int Rank0(unsigned int idx) const noexcept
Performs a Rank operation.
Definition: SmartBitmap.h:67
#define NLIB_VIS_PUBLIC
Symbols for functions and classes are made available outside of the library.
Definition: Platform_unix.h:51
void Reset() noexcept
Returns the object to the state immediately after the constructor is called.
Definition: SmartBitmap.h:107
unsigned int Rank1(unsigned int idx) const noexcept
Performs a Rank operation.
Definition: SmartBitmap.h:62
The data structure holding bit data operated on by Rank and Select.
Definition: SmartBitmap.h:162
bool Set(unsigned int idx) noexcept
Adds a 32-bit unsigned integer to the set.
Definition: SmartBitmap.h:81
The data structure holding bit data operated on by Rank and Select.
Definition: SmartBitmap.h:145