nlib
Sbv.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_SUCCINCT_SBV_H_
17 #define INCLUDE_NN_NLIB_SUCCINCT_SBV_H_
18 
19 #include <string.h>
20 #include <utility>
21 
22 #include "nn/nlib/Config.h"
23 #include "nn/nlib/Swap.h"
24 #include "nn/nlib/SmartBitmap.h"
25 #include "nn/nlib/BinaryReader.h"
26 #include "nn/nlib/BinaryWriter.h"
27 #include "nn/nlib/TypeTraits.h"
28 
29 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
30 #undef NLIB_VIS_PUBLIC
31 #define NLIB_VIS_PUBLIC NLIB_WINEXPORT
32 #endif
33 
34 NLIB_NAMESPACE_BEGIN
35 namespace succinct {
36 
37 namespace detail {
38 static const unsigned int BLK_SIZE = 32;
39 } // namespace detail
40 
42  public:
43  typedef uint32_t IdxType;
44  Set() NLIB_NOEXCEPT : prv_(NULL) {}
45  ~Set() NLIB_NOEXCEPT;
46  NLIB_MOVE_MEMBER_HELPER_1(Set, prv_);
47  void swap(Set& rhs) NLIB_NOEXCEPT {
48  SetPrivate* tmp = rhs.prv_;
49  rhs.prv_ = prv_;
50  prv_ = tmp;
51  }
52  bool Init(uint32_t bv_size) NLIB_NOEXCEPT;
53  bool TurnOn(uint32_t idx) NLIB_NOEXCEPT;
54  bool TurnOff(uint32_t idx) NLIB_NOEXCEPT;
55  bool Build() NLIB_NOEXCEPT;
56  bool Has(uint32_t idx) const NLIB_NOEXCEPT;
57  uint32_t Rank1(uint32_t idx) const NLIB_NOEXCEPT;
58  uint32_t Rank0(uint32_t idx) const NLIB_NOEXCEPT {
59  uint32_t rank1 = this->Rank1(idx);
60  return idx + 1 - rank1;
61  }
62  int32_t Select1(uint32_t nth) const NLIB_NOEXCEPT;
63  int32_t Select0(uint32_t nth) const NLIB_NOEXCEPT;
64  size_t MemSize() const NLIB_NOEXCEPT;
65  uint32_t GetBitVectorSize() const NLIB_NOEXCEPT;
66  const uint32_t* GetBitVector() const NLIB_NOEXCEPT;
67  void Reset() NLIB_NOEXCEPT;
68  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT NLIB_NONNULL;
69  bool Import(BinaryReader* r) NLIB_NOEXCEPT NLIB_NONNULL;
70 
71  private:
72  struct SetPrivate;
73  mutable SetPrivate* prv_;
75 };
76 
78  public:
79  typedef uint32_t IdxType;
80  Sbv() NLIB_NOEXCEPT : prv_(NULL) {}
81  ~Sbv() NLIB_NOEXCEPT;
82  NLIB_MOVE_MEMBER_HELPER_2(Sbv, prv_, set_);
83  void swap(Sbv& rhs) NLIB_NOEXCEPT {
84  using std::swap;
85  set_.swap(rhs.set_);
86  SbvPrivate* tmp = rhs.prv_;
87  rhs.prv_ = prv_;
88  prv_ = tmp;
89  }
90  bool Init(uint32_t bv_size) NLIB_NOEXCEPT;
91  bool TurnOn(uint32_t idx) NLIB_NOEXCEPT { return set_.TurnOn(idx); }
92  bool TurnOff(uint32_t idx) NLIB_NOEXCEPT { return set_.TurnOff(idx); }
93  bool Build() NLIB_NOEXCEPT;
94  bool Has(uint32_t idx) const NLIB_NOEXCEPT { return set_.Has(idx); }
95  uint32_t Rank1(uint32_t idx) const NLIB_NOEXCEPT { return set_.Rank1(idx); }
96  uint32_t Rank0(uint32_t idx) const NLIB_NOEXCEPT { return set_.Rank0(idx); }
97  int32_t Select1(uint32_t nth) const NLIB_NOEXCEPT;
98  int32_t Select0(uint32_t nth) const NLIB_NOEXCEPT { return set_.Select0(nth); }
99  size_t MemSize() const NLIB_NOEXCEPT;
100  uint32_t GetBitVectorSize() const NLIB_NOEXCEPT { return set_.GetBitVectorSize(); }
101  const uint32_t* GetBitVector() const NLIB_NOEXCEPT { return set_.GetBitVector(); }
102  void Reset() NLIB_NOEXCEPT;
103  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
104  bool Import(BinaryReader* r) NLIB_NOEXCEPT;
105 
106  private:
107  struct SbvPrivate;
108  SbvPrivate* prv_;
109  Set set_;
111 };
112 
114  public:
115  // index is 64-bit and # of on-bits is 32-bit.
116  // In other words, rank is 64-bit index, and select is 32-bit index
117  typedef uint64_t IdxType;
118  SparseSet() NLIB_NOEXCEPT : bitvector_size_(0),
119  lowest_idx_(0xFFFFFFFF),
120  highest_idx_(0),
121  num_on_bits_(0),
122  width_(0),
123  blen_(0),
124  b_(NULL) {}
126 #ifdef NLIB_CXX11_RVALUE_REFERENCES
128  SparseSet& operator=(SparseSet&& rhs) NLIB_NOEXCEPT;
129 #endif
130  bool Init(uint64_t bv_size) NLIB_NOEXCEPT;
131  bool TurnOn(uint64_t idx) NLIB_NOEXCEPT;
132  bool Build() NLIB_NOEXCEPT;
133  bool Has(uint64_t idx, uint32_t* rank) const NLIB_NOEXCEPT {
134  // called after Build()
135  uint32_t rank1 = this->Rank1(idx);
136  if (rank) *rank = rank1;
137  if (rank1 == 0) return false;
138  int64_t select1 = this->Select1Ex(rank1 - 1);
139  NLIB_ASSERT(select1 >= 0);
140  // if (select1 < 0) return false; // not possible
141  return idx == static_cast<uint64_t>(select1);
142  }
143  bool Has(uint64_t idx) const NLIB_NOEXCEPT {
144  return this->Has(idx, NULL);
145  }
146  uint32_t Rank1(uint64_t idx) const NLIB_NOEXCEPT;
147  uint32_t Rank0(uint64_t idx) const NLIB_NOEXCEPT {
148  uint32_t rank1 = this->Rank1(idx);
149  return static_cast<uint32_t>(idx + 1 - rank1);
150  }
151  int32_t Select1(uint32_t nth) const NLIB_NOEXCEPT;
152  int64_t Select1Ex(uint32_t nth) const NLIB_NOEXCEPT;
153  size_t MemSize() const NLIB_NOEXCEPT;
154  uint64_t GetBitVectorSize() const NLIB_NOEXCEPT {
155  return bitvector_size_;
156  }
157  void Reset() NLIB_NOEXCEPT;
158  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
159  bool Import(BinaryReader* r) NLIB_NOEXCEPT;
160  void swap(SparseSet& rhs) NLIB_NOEXCEPT; // NOLINT
161 
162  private:
163  uint32_t GetBits(uint64_t pos, size_t num) const NLIB_NOEXCEPT {
164  NLIB_ASSERT(num <= 32);
165  uint64_t idx64 = pos / detail::BLK_SIZE;
166  NLIB_ASSERT(idx64 <= SIZE_MAX);
167  size_t idx = static_cast<size_t>(idx64);
168  size_t ofs = static_cast<size_t>(pos % detail::BLK_SIZE);
169  if (ofs + num > 32) {
170  uint64_t b = b_[idx + 1];
171  b <<= 32;
172  b += b_[idx];
173  return static_cast<uint32_t>((b >> ofs) & ((1 << num) - 1));
174  } else {
175  return (b_[idx] >> ofs) & ((1 << num) - 1);
176  }
177  }
178 
179  private:
180  uint64_t bitvector_size_;
181  uint64_t lowest_idx_;
182  uint64_t highest_idx_;
183  uint32_t num_on_bits_;
184  uint32_t width_;
185  uint32_t blen_;
186  uint32_t* b_;
187  Sbv sbv_; // Set sbv_;
189 };
190 
192  static const size_t UNIT_SIZE = 64;
193 
194  public:
196  : header_(NULL), data_(NULL), header_size_(0), header_capacity_(0),
197  data_size_(0), data_capacity_(0), workidx_(0) {}
200  CompressedArray& assign(CompressedArray &rhs, move_tag) NLIB_NOEXCEPT; // NOLINT
201 #ifdef NLIB_CXX11_RVALUE_REFERENCES
204 #endif
205  // NLIB_MOVE_MEMBER_HELPER_3(CompressedArray, header_, data_, workidx_);
206  void swap(CompressedArray& rhs) NLIB_NOEXCEPT;
207  bool PushBack(uint32_t x) NLIB_NOEXCEPT {
208  work_[workidx_++] = x;
209  if (workidx_ == UNIT_SIZE) return this->Build();
210  return true;
211  }
212  uint32_t operator[](size_t idx) const NLIB_NOEXCEPT;
213  size_t Size() const NLIB_NOEXCEPT {
214  return workidx_ + header_capacity_ * UNIT_SIZE / 2;
215  }
216  void Reset() NLIB_NOEXCEPT;
217  size_t MemSize() const NLIB_NOEXCEPT;
218  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT;
219  bool Import(BinaryReader* r) NLIB_NOEXCEPT;
220 
221  private:
222  bool Build() NLIB_NOEXCEPT;
223  // Header:
224  // baseidx: index of data_(lower 27bits)
225  // k: bit width of diff data(upper 5bits)
226  // base: base value(uint32_t)
227 
228  // Data:
229  // UNIT_SIZE * kbit: diff data
230  uint32_t* header_;
231  uint32_t* data_;
232  uint32_t header_size_;
233  uint32_t header_capacity_;
234  uint32_t data_size_;
235  uint32_t data_capacity_;
236  uint8_t workidx_;
237  uint32_t work_[UNIT_SIZE];
239 };
240 
242  typedef CompressedArray ArrayType;
243  typedef SparseSet SetType;
244 
245  public:
247  typedef std::pair<bool, uint32_t> FindType;
248  Map() NLIB_NOEXCEPT : set_(), value_() {}
250  NLIB_MOVE_MEMBER_HELPER_2(Map, set_, value_);
251  void swap(Map& rhs) NLIB_NOEXCEPT {
252  set_.swap(rhs.set_);
253  value_.swap(rhs.value_);
254  }
255  bool Init(IdxType bv_size) NLIB_NOEXCEPT {
256  if (value_.Size() != 0) return false;
257  return set_.Init(bv_size);
258  }
259  bool TurnOn(IdxType idx, uint32_t data) NLIB_NOEXCEPT {
260  if (!set_.TurnOn(idx)) return false;
261  value_.PushBack(data);
262  return true;
263  }
264  bool Build() NLIB_NOEXCEPT { return set_.Build(); }
265  FindType Find(IdxType idx) NLIB_NOEXCEPT {
266  if (set_.Has(idx))
267  return std::make_pair(true, value_[set_.Rank1(idx) - 1]);
268  else
269  return std::make_pair(false, 0);
270  }
271  const FindType Find(IdxType idx) const NLIB_NOEXCEPT {
272  if (set_.Has(idx))
273  return std::make_pair(true, value_[set_.Rank1(idx) - 1]);
274  else
275  return std::make_pair(false, 0);
276  }
277  size_t MemSize() const NLIB_NOEXCEPT {
278  size_t value_size = value_.MemSize();
279  size_t set_size = set_.MemSize();
280  return value_size + set_size;
281  }
282  const SetType& GetKeys() const NLIB_NOEXCEPT { return set_; }
283  const ArrayType& GetValues() const NLIB_NOEXCEPT { return value_; }
285  value_.Reset();
286  set_.Reset();
287  }
289  if (!value_.Export(w)) return false;
290  if (!set_.Export(w)) return false;
291  return true;
292  }
294  if (!value_.Import(r) || !set_.Import(r)) {
295  this->Reset();
296  return false;
297  }
298  return true;
299  }
300 
301  private:
302  SetType set_;
303  ArrayType value_;
305 };
306 
307 } // namespace succinct
308 NLIB_NAMESPACE_END
309 
310 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::Set)
311 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::Sbv)
312 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::SparseSet)
313 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::CompressedArray)
314 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::Map)
315 
316 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
317 #undef NLIB_VIS_PUBLIC
318 #define NLIB_VIS_PUBLIC NLIB_WINIMPORT
319 #endif
320 
321 #endif // INCLUDE_NN_NLIB_SUCCINCT_SBV_H_
uint32_t Rank1(uint32_t idx) const noexcept
Performs a Rank operation.
Definition: Sbv.h:95
bool TurnOff(uint32_t idx) noexcept
Removes a 32-bit unsigned integer from the set.
Definition: Sbv.h:92
Sbv() noexcept
Instantiates the object.
Definition: Sbv.h:80
Substitute definitions for the C++11 standard header type_traits. These substitute definitions are us...
uint32_t IdxType
typedef for the integer index type.
Definition: Sbv.h:79
size_t MemSize() const noexcept
Returns the amount of memory explicitly allocated by the class.
Definition: Sbv.h:277
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
Prohibits use of the copy constructor and assignment operator for the class specified by TypeName...
Definition: Config.h:163
bool TurnOn(uint32_t idx) noexcept
Adds a 32-bit unsigned integer to the set.
Definition: Sbv.h:91
Succinct data structure to hold a set of 32-bit unsigned integers for a Rank/Select operation...
Definition: Sbv.h:77
Defines the class for reading binary files from streams.
int32_t Select0(uint32_t nth) const noexcept
Returns the position of the nth 0 bit. nth starts from 0.
Definition: Sbv.h:98
FindType Find(IdxType idx) noexcept
Specifies a key and gets the value in the associative array.
Definition: Sbv.h:265
bool Has(uint64_t idx, uint32_t *rank) const noexcept
Tests to determine whether a particular value is contained in the set.
Definition: Sbv.h:133
void swap(Map &rhs) noexcept
Swaps the contents of an object.
Definition: Sbv.h:251
bool Init(IdxType bv_size) noexcept
Initializes an object.
Definition: Sbv.h:255
bool Has(uint32_t idx) const noexcept
Tests to determine whether a particular value is contained in the set.
Definition: Sbv.h:94
void swap(Set &rhs) noexcept
Swaps the contents of an object.
Definition: Sbv.h:47
uint32_t Rank0(uint64_t idx) const noexcept
Performs a Rank operation.
Definition: Sbv.h:147
Set() noexcept
Instantiates the object.
Definition: Sbv.h:44
void swap(Sbv &rhs) noexcept
Swaps the contents of an object.
Definition: Sbv.h:83
#define NLIB_VIS_PUBLIC
Symbols for functions and classes are made available outside of the library.
Definition: Platform_unix.h:89
const SetType & GetKeys() const noexcept
Gets the key set.
Definition: Sbv.h:282
bool Export(BinaryWriter *w) const noexcept
Writes the object to the file.
Definition: Sbv.h:288
CompressedArray() noexcept
Instantiates the object.
Definition: Sbv.h:195
const ArrayType & GetValues() const noexcept
Gets the set of values.
Definition: Sbv.h:283
uint32_t Rank0(uint32_t idx) const noexcept
Performs a Rank operation.
Definition: Sbv.h:58
Succinct data structure to hold a set of 32-bit unsigned integers for a Rank/Select operation...
Definition: Sbv.h:41
An empty structure indicating that an argument to a function needs to be moved.
Definition: Config.h:249
const uint32_t * GetBitVector() const noexcept
Returns the pointer to the bit vector.
Definition: Sbv.h:101
SparseSet() noexcept
Instantiates the object.
Definition: Sbv.h:118
uint64_t GetBitVectorSize() const noexcept
Returns the size of the bit vector.
Definition: Sbv.h:154
A compressed array of integers that allows appending additional data.
Definition: Sbv.h:191
bool TurnOn(IdxType idx, uint32_t data) noexcept
Adds a key and value.
Definition: Sbv.h:259
Succinct data structure to hold a nowhere dense set of 64-bit unsigned integers.
Definition: Sbv.h:113
SetType::IdxType IdxType
Integer index.
Definition: Sbv.h:246
Defines the class for writing binary files to streams.
#define NLIB_NOEXCEPT
Defines noexcept geared to the environment, or the equivalent.
Definition: Config.h:99
void Reset() noexcept
Returns the object to the state immediately after the constructor is called.
Definition: Sbv.h:284
bool Has(uint64_t idx) const noexcept
Tests to determine whether a particular value is contained in the set.
Definition: Sbv.h:143
A file that contains the configuration information for each development environment.
Defines the class for handing bit streams operated on by Rank and Select.
uint64_t IdxType
typedef for the integer index type.
Definition: Sbv.h:117
bool Build() noexcept
Builds an associative array.
Definition: Sbv.h:264
bool Import(BinaryReader *r) noexcept
Reads the written object.
Definition: Sbv.h:293
Map() noexcept
Instantiates the object.
Definition: Sbv.h:248
The class for writing binary to streams (to OutputStream).
Definition: BinaryWriter.h:26
A compact integer to integer read-only associative array.
Definition: Sbv.h:241
#define NLIB_FINAL
Defines final if it is available for use. If not, holds an empty string.
Definition: Config.h:229
const FindType Find(IdxType idx) const noexcept
Specifies a key and gets the value in the associative array.
Definition: Sbv.h:271
The class for reading binary from streams (from InputStream).
Definition: BinaryReader.h:26
uint32_t IdxType
typedef for the integer index type.
Definition: Sbv.h:43
uint32_t Rank0(uint32_t idx) const noexcept
Performs a Rank operation.
Definition: Sbv.h:96
size_t Size() const noexcept
Gets the array length.
Definition: Sbv.h:213
#define NLIB_NONNULL
Indicates that you cannot specify NULL for all arguments.
uint32_t GetBitVectorSize() const noexcept
Returns the size of the bit vector.
Definition: Sbv.h:100
bool PushBack(uint32_t x) noexcept
Adds data. Compresses data after it becomes 64 elements long.
Definition: Sbv.h:207
std::pair< bool, uint32_t > FindType
Pair of boolean value and integer. If the value is not found, the boolean value is false...
Definition: Sbv.h:247
~Map() noexcept
Destructor.
Definition: Sbv.h:249