nlib
SmartBitmap.h
Go to the documentation of this file.
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(static_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(static_cast<void*>(&lv_a_[0]),
137  0,
138  static_cast<size_t>(kLvACount * sizeof(lv_a_[0])));
139  nlib_memset(static_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
Returns the position of the nth 1 bit. nth starts from 0.
Definition: SmartBitmap.h:87
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:2469
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:108
const BIT * GetBitVector() const noexcept
Returns the pointer to the bit data.
Definition: SmartBitmap.h:68
#define NLIB_VIS_PUBLIC
Symbols for functions and classes are made available outside of the library.
Definition: Platform_unix.h:89
bool Unset(unsigned int idx) noexcept
Removes a 32-bit unsigned integer from the set.
Definition: SmartBitmap.h:109
bool Set(unsigned int idx, bool value) noexcept
Sets bits in the bit data.
Definition: SmartBitmap.h:120
void Init(BIT *bitmap) noexcept
Sets a pointer to the bit data.
Definition: SmartBitmap.h:187
bool operator[](const unsigned int idx) const noexcept
Tests to determine whether a particular value is contained in the set.
Definition: SmartBitmap.h:77
#define NLIB_NOEXCEPT
Defines noexcept geared to the environment, or the equivalent.
Definition: Config.h:105
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:92
unsigned int Rank0(unsigned int idx) const noexcept
Performs a Rank operation.
Definition: SmartBitmap.h:83
unsigned int GetBitVectorSize() const noexcept
Returns the size of the bit data.
Definition: SmartBitmap.h:67
void Reset() noexcept
Returns the object to the state immediately after the constructor is called.
Definition: SmartBitmap.h:123
#define NLIB_FINAL
Defines final if it is available for use. If not, holds an empty string.
Definition: Config.h:245
The data structure holding bit data operated on by Rank and Select.
Definition: SmartBitmap.h:177
bool Set(unsigned int idx) noexcept
Adds a 32-bit unsigned integer to the set.
Definition: SmartBitmap.h:97
The data structure holding bit data operated on by Rank and Select.
Definition: SmartBitmap.h:161
bool Has(unsigned int idx) const noexcept
Tests to determine whether a particular value is contained in the set.
Definition: SmartBitmap.h:69
unsigned int Rank1(unsigned int idx) const noexcept
Performs a Rank operation.
Definition: SmartBitmap.h:78