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