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