nlib
ReallocVec.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_REALLOCVEC_H_
17 #define INCLUDE_NN_NLIB_REALLOCVEC_H_
18 
19 #include <stdlib.h>
20 #include <string.h>
21 #include <algorithm>
22 #include <iterator>
23 #include <utility>
24 
25 #include "nn/nlib/Config.h"
26 #include "nn/nlib/UniquePtr.h"
27 #include "nn/nlib/TypeTraits.h"
28 
29 NLIB_NAMESPACE_BEGIN
30 
31 template <class T>
32 class ReallocVec {
33  public:
34  typedef void* (*ReallocFunc)(void*, size_t) NLIB_NOEXCEPT_FUNCPTR;
35  typedef T value_type;
36  typedef size_t size_type;
37  typedef ptrdiff_t difference_type;
38  typedef T& reference;
39  typedef const T& const_reference;
40  typedef T* pointer;
41  typedef const T* const_pointer;
42  typedef T* iterator;
43  typedef const T* const_iterator;
44  typedef std::reverse_iterator<iterator> reverse_iterator;
45  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
47  : vec_(nullptr), cur_(0), size_(0), realloc_(::nlib_realloc) {}
48  NLIB_CEXPR explicit ReallocVec(ReallocFunc func) NLIB_NOEXCEPT NLIB_NONNULL;
50  if (vec_) {
51  realloc_(vec_, 0);
52  }
53  NLIB_STATIC_ASSERT(IsPod<T>::value);
54  }
55 #ifdef __cpp_rvalue_references
57  : vec_(rhs.vec_), cur_(rhs.cur_), size_(rhs.size_), realloc_(rhs.realloc_) {
58  rhs.vec_ = nullptr;
59  rhs.cur_ = 0;
60  rhs.size_ = 0;
61  rhs.realloc_ = ::nlib_realloc;
62  }
63  ReallocVec& operator=(ReallocVec&& rhs) NLIB_NOEXCEPT {
64  vec_ = rhs.vec_;
65  cur_ = rhs.cur_;
66  size_ = rhs.size_;
67  realloc_ = rhs.realloc_;
68  rhs.vec_ = nullptr;
69  rhs.cur_ = 0;
70  rhs.size_ = 0;
71  rhs.realloc_ = ::nlib_realloc;
72  return *this;
73  }
74 #endif
76  : vec_(rhs.vec_), cur_(rhs.cur_), size_(rhs.size_), realloc_(rhs.realloc_) {
77  rhs.vec_ = nullptr;
78  rhs.cur_ = 0;
79  rhs.size_ = 0;
80  rhs.realloc_ = ::nlib_realloc;
81  }
82  ReallocVec& assign(ReallocVec& rhs, move_tag) NLIB_NOEXCEPT { // NOLINT
83  vec_ = rhs.vec_;
84  cur_ = rhs.cur_;
85  size_ = rhs.size_;
86  realloc_ = rhs.realloc_;
87  rhs.vec_ = nullptr;
88  rhs.cur_ = 0;
89  rhs.size_ = 0;
90  rhs.realloc_ = ::nlib_realloc;
91  return *this;
92  }
94  using std::swap;
95  swap(vec_, rhs.vec_);
96  swap(cur_, rhs.cur_);
97  swap(size_, rhs.size_);
98  swap(realloc_, rhs.realloc_);
99  }
100  ReallocFunc GetRealloc() const NLIB_NOEXCEPT { return realloc_; }
101  bool push_back(const T& v) NLIB_NOEXCEPT {
102  if (cur_ == size_) {
103  size_t newsize = (size_ == 0) ? 1 : size_ * 2;
104  if (newsize < size_) return false;
105  if (!this->Expand(newsize)) return false;
106  }
107  vec_[cur_++] = v;
108  return true;
109  }
111  if (cur_ == 0) return false;
112  --cur_;
113  return true;
114  }
115  T& operator[](size_t idx) { return vec_[idx]; }
116  const T& operator[](size_t idx) const { return vec_[idx]; }
117  T& front() { return *begin(); }
118  const T& front() const { return *begin(); }
119  T& back() { return *(begin() + cur_ - 1); }
120  const T& back() const { return *(begin() + cur_ - 1); }
121 
122  iterator begin() NLIB_NOEXCEPT { return vec_; }
123  const_iterator begin() const NLIB_NOEXCEPT { return vec_; }
124  const_iterator cbegin() const NLIB_NOEXCEPT { return vec_; }
125  iterator end() NLIB_NOEXCEPT { return begin() + cur_; }
126  const_iterator end() const NLIB_NOEXCEPT { return begin() + cur_; }
127  const_iterator cend() const NLIB_NOEXCEPT { return begin() + cur_; }
128  reverse_iterator rbegin() NLIB_NOEXCEPT { return reverse_iterator(end()); }
129  const_reverse_iterator rbegin() const NLIB_NOEXCEPT {
130  return const_reverse_iterator(end());
131  }
132  reverse_iterator rend() NLIB_NOEXCEPT { return reverse_iterator(begin()); }
133  const_reverse_iterator rend() const NLIB_NOEXCEPT {
134  return const_reverse_iterator(begin());
135  }
136  const_reverse_iterator crbegin() const NLIB_NOEXCEPT {
137  return const_reverse_iterator(end());
138  }
139  const_reverse_iterator crend() const NLIB_NOEXCEPT {
140  return const_reverse_iterator(begin());
141  }
142  size_t size() const NLIB_NOEXCEPT { return cur_; }
143  size_t capacity() const NLIB_NOEXCEPT { return size_; }
144  bool empty() const NLIB_NOEXCEPT { return cur_ == 0; }
145  bool reserve(size_t n) NLIB_NOEXCEPT {
146  return (n > size_) ? this->Expand(n) : true;
147  }
148  bool resize(size_t n) NLIB_NOEXCEPT {
149  if (!this->reserve(n)) return false;
150  cur_ = n;
151  return true;
152  }
153  void clear() NLIB_NOEXCEPT { cur_ = 0; }
155  if (cur_ != size_) {
156  if (cur_ > 0) {
157  this->Expand(cur_);
158  } else {
159  realloc_(vec_, 0);
160  vec_ = nullptr;
161  size_ = 0;
162  }
163  }
164  }
165  iterator insert(iterator pos, const T& val) {
166  ptrdiff_t idx = pos - begin();
167  if (!this->push_back(val)) return nullptr;
168  std::rotate(begin() + idx, &back(), end());
169  return begin() + idx;
170  }
171 
172  private:
173  bool Expand(size_t new_size) NLIB_NOEXCEPT;
174 
175  T* vec_;
176  size_t cur_;
177  size_t size_;
178  ReallocFunc realloc_;
180 };
181 
182 template <class T>
183 inline NLIB_CEXPR ReallocVec<T>::ReallocVec(ReallocFunc func) NLIB_NOEXCEPT : vec_(nullptr),
184  cur_(0),
185  size_(0),
186  realloc_(func) {}
187 
188 template <class T>
189 bool ReallocVec<T>::Expand(size_t new_size) NLIB_NOEXCEPT {
190  T* ptr = vec_;
191  void* new_ptr = realloc_(ptr, new_size * sizeof(T));
192  if (!new_ptr) return false;
193  vec_ = static_cast<T*>(new_ptr);
194  size_ = new_size;
195  return true;
196 }
197 
198 template <class T>
200  public:
202  ReallocQueue() NLIB_NOEXCEPT : front_idx_(0) {}
203  explicit ReallocQueue(ReallocFunc func) NLIB_NOEXCEPT
204  : front_idx_(0), front_vec_(func), back_vec_(func) {}
206 #ifdef __cpp_rvalue_references
208  : front_idx_(rhs.front_idx_), front_vec_(std::move(rhs.front_vec_)),
209  back_vec_(std::move(rhs.back_vec_)) {
210  rhs.front_idx_ = 0;
211  }
212  ReallocQueue& operator=(ReallocQueue&& rhs) NLIB_NOEXCEPT {
213  front_idx_ = rhs.front_idx_;
214  rhs.front_idx_ = 0;
215  front_vec_ = std::move(rhs.front_vec_);
216  back_vec_ = std::move(rhs.back_vec_);
217  return *this;
218  }
219 #endif
221  : front_idx_(rhs.front_idx_),
222  front_vec_(rhs.front_vec_, move_tag()),
223  back_vec_(rhs.back_vec_, move_tag()) {
224  rhs.front_idx_ = 0;
225  }
226  ReallocQueue& assign(ReallocQueue& rhs, move_tag) NLIB_NOEXCEPT { // NOLINT
227  front_idx_ = rhs.front_idx_;
228  rhs.front_idx_ = 0;
229  front_vec_.assign(rhs.front_vec_, move_tag());
230  back_vec_.assign(rhs.back_vec_, move_tag());
231  return *this;
232  }
234  using std::swap;
235  swap(front_idx_, rhs.front_idx_);
236  swap(front_vec_, rhs.front_vec_);
237  swap(back_vec_, rhs.back_vec_);
238  }
239  ReallocFunc GetRealloc() const NLIB_NOEXCEPT {
240  return front_vec_.GetRealloc();
241  }
242  size_t size() const NLIB_NOEXCEPT {
243  return front_vec_.size() - front_idx_ + back_vec_.size();
244  }
245  bool empty() const NLIB_NOEXCEPT {
246  return front_idx_ == front_vec_.size() && back_vec_.empty();
247  }
248  bool push(const T& val) NLIB_NOEXCEPT { return back_vec_.push_back(val); }
250  if (front_idx_ == front_vec_.size()) {
251  using std::swap;
252  if (back_vec_.empty()) return false;
253  front_vec_.clear();
254  swap(front_vec_, back_vec_);
255  front_idx_ = 0;
256  }
257  ++front_idx_;
258  return true;
259  }
260  T& front() {
261  if (front_idx_ == front_vec_.size()) {
262  using std::swap;
263  NLIB_ASSERT(!back_vec_.empty());
264  front_vec_.clear();
265  swap(front_vec_, back_vec_);
266  front_idx_ = 0;
267  }
268  return front_vec_[front_idx_];
269  }
270  bool pop(T* v) NLIB_NOEXCEPT {
271  if (front_idx_ == front_vec_.size()) {
272  using std::swap;
273  if (back_vec_.empty()) return false;
274  front_vec_.clear();
275  swap(front_vec_, back_vec_);
276  front_idx_ = 0;
277  }
278  if (v) *v = front_vec_[front_idx_];
279  ++front_idx_;
280  return true;
281  }
282 
283  private:
284  size_t front_idx_;
285  ReallocVec<T> front_vec_;
286  ReallocVec<T> back_vec_;
288 };
289 
291  typedef ReallocVec<char*> VecType;
292  typedef VecType::ReallocFunc ReallocFunc;
293 
294  public:
296  explicit ReallocCstringVec(ReallocFunc func) NLIB_NOEXCEPT : vec_(func) {}
297  ~ReallocCstringVec() NLIB_NOEXCEPT { this->clear(); }
298 #ifdef __cpp_rvalue_references
299 #ifdef NLIB_CXX11_DEFAULTED_AND_DELETED_FUNCTIONS
300  ReallocCstringVec(ReallocCstringVec&& rhs) = default;
301  ReallocCstringVec& operator=(ReallocCstringVec&& rhs) = default;
302 #else
303  ReallocCstringVec(ReallocCstringVec&& rhs) NLIB_NOEXCEPT : vec_(std::move(rhs.vec_)) {}
305  vec_ = std::move(rhs.vec_);
306  return *this;
307  }
308 #endif
309 #endif
311  : vec_(rhs.vec_, move_tag()) {}
312  ReallocCstringVec& assign(ReallocCstringVec& rhs, move_tag) NLIB_NOEXCEPT { // NOLINT
313  vec_.assign(rhs.vec_, move_tag());
314  return *this;
315  }
317  using std::swap;
318  swap(vec_, rhs.vec_);
319  }
320  ReallocFunc GetRealloc() const NLIB_NOEXCEPT { return vec_.GetRealloc(); }
321  bool push_back(const char* str) NLIB_NOEXCEPT {
322  return this->push_back(str, str + nlib_strlen(str));
323  }
324  bool push_back(const char* startchar_ptr,
325  const char* endchar_ptr) NLIB_NOEXCEPT {
326  size_t n = endchar_ptr - startchar_ptr;
327  char* p = static_cast<char*>(vec_.GetRealloc()(nullptr, n + 1));
328  if (!p) return false;
329  nlib_memcpy(p, n, startchar_ptr, n);
330  p[n] = '\0';
331  if (!vec_.push_back(p)) return false;
332  return true;
333  }
335  if (vec_.empty()) return false;
336  vec_.GetRealloc()(vec_.back(), 0);
337  vec_.pop_back();
338  return true;
339  }
340  char* operator[](size_t idx)NLIB_NOEXCEPT { return vec_[idx]; }
341  const char* operator[](size_t idx) const NLIB_NOEXCEPT {
342  return vec_[idx];
343  }
344  char* front() NLIB_NOEXCEPT { return vec_.front(); }
345  const char* front() const NLIB_NOEXCEPT { return vec_.front(); }
346  char* back() NLIB_NOEXCEPT { return vec_.back(); }
347  const char* back() const NLIB_NOEXCEPT { return vec_.back(); }
348  size_t size() const NLIB_NOEXCEPT { return vec_.size(); }
349  size_t capacity() const NLIB_NOEXCEPT { return vec_.capacity(); }
350  bool empty() const NLIB_NOEXCEPT { return vec_.empty(); }
351  bool reserve(size_t n) NLIB_NOEXCEPT { return vec_.reserve(n); }
352  void clear() NLIB_NOEXCEPT {
353  VecType::iterator it = vec_.begin();
354  VecType::iterator end = vec_.end();
355  for (; it != end; ++it) {
356  vec_.GetRealloc()(*it, 0);
357  }
358  vec_.clear();
359  }
360 
361  private:
362  VecType vec_;
364 };
365 
366 NLIB_NAMESPACE_END
367 
368 NLIB_DEFINE_STD_SWAP(NLIB_NS::ReallocCstringVec)
369 
370 NLIB_DEFINE_STD_SWAP_T_BEGIN2(nn, nlib) // NOLINT
371 NLIB_DEFINE_STD_SWAP_T1(AL, NLIB_NS::ReallocVec) // NOLINT
372 NLIB_DEFINE_STD_SWAP_T1(AL, NLIB_NS::ReallocQueue) // NOLINT
373 NLIB_DEFINE_STD_SWAP_T_END2(nn, nlib) // NOLINT
374 
375 #endif // INCLUDE_NN_NLIB_REALLOCVEC_H_
const T & front() const
See front.
Definition: ReallocVec.h:118
T * iterator
Random-access iterator.
Definition: ReallocVec.h:42
ReallocQueue(ReallocFunc func) noexcept
Enables the user to specify the realloc function with the constructor.
Definition: ReallocVec.h:203
const_iterator end() const noexcept
See end.
Definition: ReallocVec.h:126
ReallocVec< T >::ReallocFunc ReallocFunc
The type for functions corresponding to realloc.
Definition: ReallocVec.h:201
T value_type
Element type T.
Definition: ReallocVec.h:35
bool push_back(const T &v) noexcept
Adds an element to the vector.
Definition: ReallocVec.h:101
Substitute definitions for the C++11 standard header type_traits. These substitute definitions are us...
size_t size_type
Unsigned integer type (size_t).
Definition: ReallocVec.h:36
char * front() noexcept
Gets the first string.
Definition: ReallocVec.h:344
#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 pop_back() noexcept
Deletes a string from the end of the vector.
Definition: ReallocVec.h:334
size_t size() const noexcept
Gets the size of the vector.
Definition: ReallocVec.h:142
const_iterator begin() const noexcept
See begin.
Definition: ReallocVec.h:123
The class for realloc-based implementations of C string vectors.
Definition: ReallocVec.h:290
Definition: Base64.h:25
bool empty() const noexcept
Determines whether the queue is empty.
Definition: ReallocVec.h:245
The class for realloc-based implementations of queues with POD-type elements.
Definition: ReallocVec.h:199
const T * const_pointer
const T*.
Definition: ReallocVec.h:41
bool reserve(size_t n) noexcept
Makes it possible to store as many as n elements without expanding the vector.
Definition: ReallocVec.h:351
iterator insert(iterator pos, const T &val)
Inserts an element in the position specified by pos.
Definition: ReallocVec.h:165
char * back() noexcept
Gets the last string.
Definition: ReallocVec.h:346
const_reverse_iterator crbegin() const noexcept
Gets the read-only reverse iterator pointing to the last element.
Definition: ReallocVec.h:136
bool pop() noexcept
Deletes the first element in the queue.
Definition: ReallocVec.h:249
Defines that class that is corresponding to std::unique_ptr.
const_iterator cbegin() const noexcept
Gets the read-only iterator pointing to the first element.
Definition: ReallocVec.h:124
const T & const_reference
const T&.
Definition: ReallocVec.h:39
#define NLIB_DEPRECATED
Indicates that a function or something has been deprecated.
Definition: Config.h:109
ReallocFunc GetRealloc() const noexcept
Gets the specified realloc function.
Definition: ReallocVec.h:100
const T * const_iterator
Read-only random-access iterator.
Definition: ReallocVec.h:43
T & front()
Gets the first element.
Definition: ReallocVec.h:117
void swap(ReallocCstringVec &rhs) noexcept
Swaps vectors.
Definition: ReallocVec.h:316
bool resize(size_t n) noexcept
Changes the number of elements.
Definition: ReallocVec.h:148
const_reverse_iterator rbegin() const noexcept
See rbegin.
Definition: ReallocVec.h:129
bool reserve(size_t n) noexcept
Makes it possible to store as many as n elements without reallocating memory.
Definition: ReallocVec.h:145
T & back()
Gets the last element.
Definition: ReallocVec.h:119
bool pop(T *v) noexcept
Gets the first element in the queue and then deletes it.
Definition: ReallocVec.h:270
bool pop_back() noexcept
Deletes an element from the end of the vector.
Definition: ReallocVec.h:110
void swap(ReallocQueue &rhs) noexcept
Swaps queues.
Definition: ReallocVec.h:233
An empty structure indicating that an argument to a function needs to be moved.
Definition: Config.h:265
bool empty() const noexcept
Determines whether the vector is empty.
Definition: ReallocVec.h:350
std::reverse_iterator< const_iterator > const_reverse_iterator
std::reverse_iterator<const_iterator>
Definition: ReallocVec.h:45
ReallocFunc GetRealloc() const noexcept
Gets the specified realloc function.
Definition: ReallocVec.h:239
ReallocCstringVec() noexcept
Uses std::realloc with the default constructor.
Definition: ReallocVec.h:295
T & operator[](size_t idx)
Gets the nth element, where n is specified by idx.
Definition: ReallocVec.h:115
size_t size() const noexcept
Gets the size of the queue.
Definition: ReallocVec.h:242
reverse_iterator rend() noexcept
Gets the reverse iterator pointing ahead of the first element.
Definition: ReallocVec.h:132
bool push_back(const char *str) noexcept
Adds a C string to the end.
Definition: ReallocVec.h:321
const_reverse_iterator rend() const noexcept
See rend.
Definition: ReallocVec.h:133
static errno_t nlib_memcpy(void *s1, size_t s1max, const void *s2, size_t n)
An implementation corresponding to N1078 memcpy_s.
Definition: Platform.h:2437
constexpr ReallocVec() noexcept
Uses std::realloc with the default constructor.
Definition: ReallocVec.h:46
ReallocCstringVec(ReallocFunc func) noexcept
Enables the user to specify the realloc function with the constructor.
Definition: ReallocVec.h:296
size_t capacity() const noexcept
Gets the maximum number of elements that can be stored without expanding the vector.
Definition: ReallocVec.h:349
void clear() noexcept
Empties the vector. Note that the memory remains allocated.
Definition: ReallocVec.h:153
bool empty() const noexcept
Determines whether the vector is empty.
Definition: ReallocVec.h:144
#define NLIB_NOEXCEPT
Defines noexcept geared to the environment, or the equivalent.
Definition: Config.h:105
size_t capacity() const noexcept
Gets the maximum number of elements that can be stored without reallocating memory.
Definition: ReallocVec.h:143
iterator end() noexcept
Gets the iterator pointing beyond the last element.
Definition: ReallocVec.h:125
const T & operator[](size_t idx) const
See operator[](size_t idx) =.
Definition: ReallocVec.h:116
#define NLIB_CEXPR
Defines constexpr if it is available for use. If not, holds an empty string.
Definition: Config.h:107
A file that contains the configuration information for each development environment.
reverse_iterator rbegin() noexcept
Gets the reverse iterator pointing to the last element.
Definition: ReallocVec.h:128
bool push(const T &val) noexcept
Adds an element to the queue.
Definition: ReallocVec.h:248
std::reverse_iterator< iterator > reverse_iterator
std::reverse_iterator<iterator>
Definition: ReallocVec.h:44
bool push_back(const char *startchar_ptr, const char *endchar_ptr) noexcept
Adds a (sub)string to the end.
Definition: ReallocVec.h:324
void * nlib_realloc(void *ptr, size_t size)
A weak function that calls the C standard function realloc. nlib calls realloc via this function...
const_reverse_iterator crend() const noexcept
Gets the read-only iterator pointing ahead of the first element.
Definition: ReallocVec.h:139
char * operator[](size_t idx) noexcept
Gets the nth string, where n is specified by idx.
Definition: ReallocVec.h:340
size_t nlib_strlen(const char *s)
Internally calls strlen(). In some cases, it may operate as an independent implementation.
void shrink_to_fit() noexcept
Adjusts the size of allocated memory to exactly fit the current number of elements.
Definition: ReallocVec.h:154
iterator begin() noexcept
Gets the iterator pointing to the first element.
Definition: ReallocVec.h:122
ReallocFunc GetRealloc() const noexcept
Gets the specified realloc function.
Definition: ReallocVec.h:320
#define NLIB_STATIC_ASSERT(exp)
Defines a static assertion. Uses static_assert if it is available for use.
Definition: Config.h:170
ReallocQueue() noexcept
Uses std::realloc with the default constructor.
Definition: ReallocVec.h:202
ptrdiff_t difference_type
Signed integer type (ptrdiff_t).
Definition: ReallocVec.h:37
T & front()
Gets the first element in the queue.
Definition: ReallocVec.h:260
size_t size() const noexcept
Gets the size of the vector.
Definition: ReallocVec.h:348
The class for realloc-based implementations of vectors with POD-type elements.
Definition: ReallocVec.h:32
#define NLIB_NONNULL
Indicates that you cannot specify NULL for all arguments.
const_iterator cend() const noexcept
Gets the read-only iterator pointing beyond the last element.
Definition: ReallocVec.h:127
void swap(ReallocVec &rhs) noexcept
Swaps vectors.
Definition: ReallocVec.h:93
const T & back() const
See back.
Definition: ReallocVec.h:120