nlib
SmartBitmap.h
Go to the documentation of this file.
1 
2 /*---------------------------------------------------------------------------*
3 
4  Project: CrossRoad
5  Copyright (C)2012-2016 Nintendo. All rights reserved.
6 
7  These coded instructions, statements, and computer programs contain
8  proprietary information of Nintendo of America Inc. and/or Nintendo
9  Company Ltd., and are protected by Federal copyright law. They may
10  not be disclosed to third parties or copied or duplicated in any form,
11  in whole or in part, without the prior written consent of Nintendo.
12 
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  BLK_SIZE = 8 * sizeof(BIT),
56  WORD_COUNT = (N + BLK_SIZE - 1) / BLK_SIZE,
57  LV_A_COUNT = (N + 256 - 1) / 256,
58  LV_B_COUNT = ((N + BLK_SIZE - 1) / BLK_SIZE + 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 / BLK_SIZE;
70  unsigned int ofs = idx % BLK_SIZE;
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 / BLK_SIZE;
97  unsigned int ofs = idx % BLK_SIZE;
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 / BLK_SIZE;
109  unsigned int ofs = idx % BLK_SIZE;
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(reinterpret_cast<void*>(&This()->bitmap_[0]),
124  0,
125  static_cast<size_t>(WORD_COUNT * sizeof(This()->bitmap_[0])));
126  }
127 
128  protected:
129  void ResetBase() NLIB_NOEXCEPT {
130  is_dirty_ = true;
131  // cast is for armcc
132  nlib_memset(reinterpret_cast<void*>(&lv_a_[0]),
133  0,
134  static_cast<size_t>(LV_A_COUNT * sizeof(lv_a_[0])));
135  nlib_memset(reinterpret_cast<void*>(&lv_b_[0]),
136  0,
137  static_cast<size_t>(LV_B_COUNT * sizeof(lv_b_[0])));
138  }
139 
140  private:
141  Derived* This() NLIB_NOEXCEPT { return static_cast<Derived*>(this); }
142  const Derived* This() const NLIB_NOEXCEPT { return static_cast<const Derived*>(this); }
143  void Build() const NLIB_NOEXCEPT {
144  detail::BuildRankDictionary(WORD_COUNT, This()->bitmap_, lv_a_, lv_b_);
145  is_dirty_ = false;
146  }
147  mutable bool is_dirty_;
148  mutable uint32_t lv_a_[LV_A_COUNT];
149  mutable uint8_t lv_b_[LV_B_COUNT];
150 };
151 
152 #ifdef NLIB_64BIT
153 template <size_t N, class BIT = uint64_t>
154 #else
155 template <size_t N, class BIT = uint32_t>
156 #endif
157 class SmartBitmap NLIB_FINAL : public SmartBitmapCrtp<N, SmartBitmap<N, BIT>, BIT> {
159 
160  public:
161  SmartBitmap() NLIB_NOEXCEPT { this->Reset(); }
162 
163  private:
164  BIT bitmap_[CrtpBase::WORD_COUNT];
165  friend class SmartBitmapCrtp<N, SmartBitmap<N, BIT>, BIT>;
166 };
167 
168 #ifdef NLIB_64BIT
169 template <size_t N, class BIT = uint64_t>
170 #else
171 template <size_t N, class BIT = uint32_t>
172 #endif
173 class SmartBitmapPtr NLIB_FINAL : public SmartBitmapCrtp<N, SmartBitmapPtr<N, BIT>, BIT> {
175 
176  public: // suppress doxygen warnings
178  enum { ARRAY_SIZE = CrtpBase::WORD_COUNT };
180  void Init(BIT* bitmap) NLIB_NOEXCEPT {
181  this->ResetBase();
182  bitmap_ = bitmap;
183  }
184 
185  private:
186  BIT* bitmap_;
187  friend class SmartBitmapCrtp<N, SmartBitmapPtr<N, BIT>, BIT>;
188 };
189 
190 NLIB_NAMESPACE_END
191 
192 #endif // INCLUDE_NN_NLIB_SMARTBITMAP_H_
int Select1(unsigned int nth) const noexcept
Returns the position of the nth 1 bit. nth starts from 0.
Definition: SmartBitmap.h:83
static errno_t nlib_memset(void *buf, int ch, size_t n)
Makes a function call corresponding to memset(buf, ch, n).
Definition: Platform.h:3283
The data structure holding bit data operated on by Rank and Select.
Definition: SmartBitmap.h:52
bool TurnOn(unsigned int idx) noexcept
Adds a 32-bit unsigned integer to the set.
Definition: SmartBitmap.h:104
const BIT * GetBitVector() const noexcept
Returns the pointer to the bit data.
Definition: SmartBitmap.h:64
#define NLIB_VIS_PUBLIC
Symbols for functions and classes are made available outside of the library.
Definition: Platform_unix.h:87
bool Unset(unsigned int idx) noexcept
Removes a 32-bit unsigned integer from the set.
Definition: SmartBitmap.h:105
bool Set(unsigned int idx, bool value) noexcept
Sets bits in the bit data.
Definition: SmartBitmap.h:116
void Init(BIT *bitmap) noexcept
Sets a pointer to the bit data.
Definition: SmartBitmap.h:180
bool operator[](const unsigned int idx) const noexcept
Tests to determine whether a particular value is contained in the set.
Definition: SmartBitmap.h:73
#define NLIB_NOEXCEPT
Defines noexcept geared to the environment, or the equivalent.
Definition: Config.h:99
A file that contains the configuration information for each development environment.
int Select0(unsigned int nth) const noexcept
Returns the position of the nth 0 bit. nth starts from 0.
Definition: SmartBitmap.h:88
unsigned int Rank0(unsigned int idx) const noexcept
Performs a Rank operation.
Definition: SmartBitmap.h:79
unsigned int GetBitVectorSize() const noexcept
Returns the size of the bit data.
Definition: SmartBitmap.h:63
void Reset() noexcept
Returns the object to the state immediately after the constructor is called.
Definition: SmartBitmap.h:119
#define NLIB_FINAL
Defines final if it is available for use. If not, holds an empty string.
Definition: Config.h:224
The data structure holding bit data operated on by Rank and Select.
Definition: SmartBitmap.h:173
bool Set(unsigned int idx) noexcept
Adds a 32-bit unsigned integer to the set.
Definition: SmartBitmap.h:93
The data structure holding bit data operated on by Rank and Select.
Definition: SmartBitmap.h:157
bool Has(unsigned int idx) const noexcept
Tests to determine whether a particular value is contained in the set.
Definition: SmartBitmap.h:65
unsigned int Rank1(unsigned int idx) const noexcept
Performs a Rank operation.
Definition: SmartBitmap.h:74