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;
46  NLIB_CEXPR ReallocVec() NLIB_NOEXCEPT : vec_(nullptr),
47  cur_(0),
48  size_(0),
49  realloc_(::nlib_realloc) {}
50  NLIB_CEXPR explicit ReallocVec(ReallocFunc func) NLIB_NOEXCEPT NLIB_NONNULL;
52  if (vec_) {
53  realloc_(vec_, 0);
54  }
55  NLIB_STATIC_ASSERT(IsPod<T>::value);
56  }
57 #ifdef __cpp_rvalue_references
58  ReallocVec(ReallocVec&& rhs) NLIB_NOEXCEPT : vec_(rhs.vec_),
59  cur_(rhs.cur_),
60  size_(rhs.size_),
61  realloc_(rhs.realloc_) {
62  rhs.vec_ = nullptr;
63  rhs.cur_ = 0;
64  rhs.size_ = 0;
65  rhs.realloc_ = ::nlib_realloc;
66  }
68  vec_ = rhs.vec_;
69  cur_ = rhs.cur_;
70  size_ = rhs.size_;
71  realloc_ = rhs.realloc_;
72  rhs.vec_ = nullptr;
73  rhs.cur_ = 0;
74  rhs.size_ = 0;
75  rhs.realloc_ = ::nlib_realloc;
76  return *this;
77  }
78 #endif
79  ReallocVec(ReallocVec& rhs, move_tag) NLIB_NOEXCEPT : vec_(rhs.vec_),
80  cur_(rhs.cur_),
81  size_(rhs.size_),
82  realloc_(rhs.realloc_) {
83  rhs.vec_ = nullptr;
84  rhs.cur_ = 0;
85  rhs.size_ = 0;
86  rhs.realloc_ = ::nlib_realloc;
87  }
88  ReallocVec& assign(ReallocVec& rhs, move_tag) NLIB_NOEXCEPT {
89  vec_ = rhs.vec_;
90  cur_ = rhs.cur_;
91  size_ = rhs.size_;
92  realloc_ = rhs.realloc_;
93  rhs.vec_ = nullptr;
94  rhs.cur_ = 0;
95  rhs.size_ = 0;
96  rhs.realloc_ = ::nlib_realloc;
97  return *this;
98  }
99  ReallocFunc GetRealloc() const NLIB_NOEXCEPT { return realloc_; }
100  bool push_back(const T& v) NLIB_NOEXCEPT {
101  if (cur_ == size_) {
102  size_t newsize = (size_ == 0) ? 1 : size_ * 2;
103  if (newsize < size_) return false;
104  if (!this->Expand(newsize)) return false;
105  }
106  vec_[cur_++] = v;
107  return true;
108  }
110  if (cur_ == 0) return false;
111  --cur_;
112  return true;
113  }
114  T& operator[](size_t idx) { return vec_[idx]; }
115  const T& operator[](size_t idx) const { return vec_[idx]; }
116  T& front() {
117  NLIB_ASSERT(!this->empty());
118  return *begin();
119  }
120  const T& front() const {
121  NLIB_ASSERT(!this->empty());
122  return *begin();
123  }
124  T& back() {
125  NLIB_ASSERT(!this->empty());
126  return *(begin() + cur_ - 1);
127  }
128  const T& back() const {
129  NLIB_ASSERT(!this->empty());
130  return *(begin() + cur_ - 1);
131  }
132 
133  iterator begin() NLIB_NOEXCEPT { return vec_; }
134  const_iterator begin() const NLIB_NOEXCEPT { return vec_; }
135  const_iterator cbegin() const NLIB_NOEXCEPT { return vec_; }
136  iterator end() NLIB_NOEXCEPT { return begin() + cur_; }
137  const_iterator end() const NLIB_NOEXCEPT { return begin() + cur_; }
138  const_iterator cend() const NLIB_NOEXCEPT { return begin() + cur_; }
145  size_t size() const NLIB_NOEXCEPT { return cur_; }
146  size_t capacity() const NLIB_NOEXCEPT { return size_; }
147  bool empty() const NLIB_NOEXCEPT { return cur_ == 0; }
148  bool reserve(size_t n) NLIB_NOEXCEPT { return (n > size_) ? this->Expand(n) : true; }
149  bool resize(size_t n) NLIB_NOEXCEPT {
150  if (!this->reserve(n)) return false;
151  cur_ = n;
152  return true;
153  }
154  void clear() NLIB_NOEXCEPT { cur_ = 0; }
156  if (cur_ != size_) {
157  if (cur_ > 0) {
158  this->Expand(cur_);
159  } else {
160  realloc_(vec_, 0);
161  vec_ = nullptr;
162  size_ = 0;
163  }
164  }
165  }
166  iterator insert(iterator pos, const T& val) {
167  ptrdiff_t idx = pos - begin();
168  if (!this->push_back(val)) return nullptr;
169  std::rotate(begin() + idx, &back(), end());
170  return begin() + idx;
171  }
172 
173  private:
174  bool Expand(size_t new_size) NLIB_NOEXCEPT;
175 
176  T* vec_;
177  size_t cur_;
178  size_t size_;
179  ReallocFunc realloc_;
181 };
182 
183 template<class T>
184 inline NLIB_CEXPR ReallocVec<T>::ReallocVec(ReallocFunc func) NLIB_NOEXCEPT : vec_(nullptr),
185  cur_(0),
186  size_(0),
187  realloc_(func) {}
188 
189 template<class T>
190 bool ReallocVec<T>::Expand(size_t new_size) NLIB_NOEXCEPT {
191  T* ptr = vec_;
192  void* new_ptr = realloc_(ptr, new_size * sizeof(T));
193  if (!new_ptr) return false;
194  vec_ = static_cast<T*>(new_ptr);
195  size_ = new_size;
196  return true;
197 }
198 
199 template<class T>
201  public:
203  ReallocQueue() NLIB_NOEXCEPT : front_idx_(0) {}
204  explicit ReallocQueue(ReallocFunc func) NLIB_NOEXCEPT : front_idx_(0),
205  front_vec_(func),
206  back_vec_(func) {}
208 #ifdef __cpp_rvalue_references
209  ReallocQueue(ReallocQueue&& rhs) NLIB_NOEXCEPT : front_idx_(rhs.front_idx_),
210  front_vec_(std::move(rhs.front_vec_)),
211  back_vec_(std::move(rhs.back_vec_)) {
212  rhs.front_idx_ = 0;
213  }
215  front_idx_ = rhs.front_idx_;
216  rhs.front_idx_ = 0;
217  front_vec_ = std::move(rhs.front_vec_);
218  back_vec_ = std::move(rhs.back_vec_);
219  return *this;
220  }
221 #endif
223  : front_idx_(rhs.front_idx_),
224  front_vec_(rhs.front_vec_, move_tag()),
225  back_vec_(rhs.back_vec_, move_tag()) {
226  rhs.front_idx_ = 0;
227  }
228  ReallocQueue& assign(ReallocQueue& rhs, move_tag) NLIB_NOEXCEPT {
229  front_idx_ = rhs.front_idx_;
230  rhs.front_idx_ = 0;
231  front_vec_.assign(rhs.front_vec_, move_tag());
232  back_vec_.assign(rhs.back_vec_, move_tag());
233  return *this;
234  }
235  ReallocFunc GetRealloc() const NLIB_NOEXCEPT { return front_vec_.GetRealloc(); }
236  size_t size() const NLIB_NOEXCEPT { return front_vec_.size() - front_idx_ + back_vec_.size(); }
237  bool empty() const NLIB_NOEXCEPT {
238  return front_idx_ == front_vec_.size() && back_vec_.empty();
239  }
240  bool push(const T& val) NLIB_NOEXCEPT { return back_vec_.push_back(val); }
242  if (front_idx_ == front_vec_.size()) {
243  using std::swap;
244  if (back_vec_.empty()) return false;
245  front_vec_.clear();
246  swap(front_vec_, back_vec_);
247  front_idx_ = 0;
248  }
249  ++front_idx_;
250  return true;
251  }
252  T& front() {
253  if (front_idx_ == front_vec_.size()) {
254  using std::swap;
255  NLIB_ASSERT(!back_vec_.empty());
256  front_vec_.clear();
257  swap(front_vec_, back_vec_);
258  front_idx_ = 0;
259  }
260  return front_vec_[front_idx_];
261  }
262  bool pop(T* v) NLIB_NOEXCEPT {
263  if (front_idx_ == front_vec_.size()) {
264  using std::swap;
265  if (back_vec_.empty()) return false;
266  front_vec_.clear();
267  swap(front_vec_, back_vec_);
268  front_idx_ = 0;
269  }
270  if (v) *v = front_vec_[front_idx_];
271  ++front_idx_;
272  return true;
273  }
274 
275  private:
276  size_t front_idx_;
277  ReallocVec<T> front_vec_;
278  ReallocVec<T> back_vec_;
280 };
281 
283  typedef ReallocVec<char*> VecType;
284  typedef VecType::ReallocFunc ReallocFunc;
285 
286  public:
288  explicit ReallocCstringVec(ReallocFunc func) NLIB_NOEXCEPT : vec_(func) {}
289  ~ReallocCstringVec() NLIB_NOEXCEPT { this->clear(); }
290 #ifdef __cpp_rvalue_references
291 #ifdef NLIB_CXX11_DEFAULTED_AND_DELETED_FUNCTIONS
292  ReallocCstringVec(ReallocCstringVec&& rhs) = default;
293  ReallocCstringVec& operator=(ReallocCstringVec&& rhs) = default;
294 #else
295  ReallocCstringVec(ReallocCstringVec&& rhs) NLIB_NOEXCEPT : vec_(std::move(rhs.vec_)) {}
296  ReallocCstringVec& operator=(ReallocCstringVec&& rhs) NLIB_NOEXCEPT {
297  vec_ = std::move(rhs.vec_);
298  return *this;
299  }
300 #endif
301 #endif
302  ReallocCstringVec(ReallocCstringVec& rhs, move_tag) NLIB_NOEXCEPT : vec_(rhs.vec_, move_tag()) {
303  }
304  ReallocCstringVec& assign(ReallocCstringVec& rhs, move_tag) NLIB_NOEXCEPT {
305  vec_.assign(rhs.vec_, move_tag());
306  return *this;
307  }
308  ReallocFunc GetRealloc() const NLIB_NOEXCEPT { return vec_.GetRealloc(); }
309  bool push_back(const char* str) NLIB_NOEXCEPT {
310  return this->push_back(str, str + nlib_strlen(str));
311  }
312  bool push_back(const char* startchar_ptr, const char* endchar_ptr) NLIB_NOEXCEPT {
313  size_t n = endchar_ptr - startchar_ptr;
314  char* p = static_cast<char*>(vec_.GetRealloc()(nullptr, n + 1));
315  if (!p) return false;
316  nlib_memcpy(p, n, startchar_ptr, n);
317  p[n] = '\0';
318  return vec_.push_back(p);
319  }
321  if (vec_.empty()) return false;
322  vec_.GetRealloc()(vec_.back(), 0);
323  vec_.pop_back();
324  return true;
325  }
326  char* operator[](size_t idx) NLIB_NOEXCEPT { return vec_[idx]; }
327  const char* operator[](size_t idx) const NLIB_NOEXCEPT { return vec_[idx]; }
328  char* front() NLIB_NOEXCEPT { return vec_.front(); }
329  const char* front() const NLIB_NOEXCEPT { return vec_.front(); }
330  char* back() NLIB_NOEXCEPT { return vec_.back(); }
331  const char* back() const NLIB_NOEXCEPT { return vec_.back(); }
332  size_t size() const NLIB_NOEXCEPT { return vec_.size(); }
333  size_t capacity() const NLIB_NOEXCEPT { return vec_.capacity(); }
334  bool empty() const NLIB_NOEXCEPT { return vec_.empty(); }
335  bool reserve(size_t n) NLIB_NOEXCEPT { return vec_.reserve(n); }
337  VecType::iterator it = vec_.begin();
338  VecType::iterator end = vec_.end();
339  for (; it != end; ++it) {
340  vec_.GetRealloc()(*it, 0);
341  }
342  vec_.clear();
343  }
344 
345  private:
346  VecType vec_;
348 };
349 
350 NLIB_NAMESPACE_END
351 
352 NLIB_DEFINE_STD_SWAP(NLIB_NS::ReallocCstringVec)
353 
354 NLIB_DEFINE_STD_SWAP_T_BEGIN2(nn, nlib)
355 NLIB_DEFINE_STD_SWAP_T1(AL, NLIB_NS::ReallocVec)
356 NLIB_DEFINE_STD_SWAP_T1(AL, NLIB_NS::ReallocQueue)
357 NLIB_DEFINE_STD_SWAP_T_END2(nn, nlib)
358 
359 #endif // INCLUDE_NN_NLIB_REALLOCVEC_H_
const T & front() const
The const decoration version of the above function.
Definition: ReallocVec.h:120
T * iterator
A 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:204
const_iterator end() const noexcept
Gets the read-only iterator pointing beyond the last element.
Definition: ReallocVec.h:137
ReallocVec< T >::ReallocFunc ReallocFunc
The type for functions corresponding to realloc.
Definition: ReallocVec.h:202
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:100
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:328
#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
ReallocVec & operator=(ReallocVec &&rhs) noexcept
Move assignment operator.
Definition: ReallocVec.h:67
bool pop_back() noexcept
Deletes a string from the end of the vector.
Definition: ReallocVec.h:320
size_t size() const noexcept
Returns the number of stored elements.
Definition: ReallocVec.h:145
const_iterator begin() const noexcept
Gets the read-only iterator pointing to the first element.
Definition: ReallocVec.h:134
The class for realloc-based implementations of C string vectors.
Definition: ReallocVec.h:282
Definition: Base64.h:25
bool empty() const noexcept
Determines whether the queue is empty.
Definition: ReallocVec.h:237
The class for realloc-based implementations of queues with POD-type elements.
Definition: ReallocVec.h:200
const char * front() const noexcept
The const decoration version of the above function.
Definition: ReallocVec.h:329
const char * back() const noexcept
The const decoration version of the above function.
Definition: ReallocVec.h:331
const T * const_pointer
Read-only pointer to an element.
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:335
iterator insert(iterator pos, const T &val)
Inserts an element in the position specified by pos.
Definition: ReallocVec.h:166
char * back() noexcept
Gets the last string.
Definition: ReallocVec.h:330
const_reverse_iterator crbegin() const noexcept
Gets the read-only reverse iterator pointing to the last element.
Definition: ReallocVec.h:143
bool pop() noexcept
Deletes the first element in the queue.
Definition: ReallocVec.h:241
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:135
const T & const_reference
Read-only reference to an element.
Definition: ReallocVec.h:39
ReallocFunc GetRealloc() const noexcept
Gets the specified realloc function.
Definition: ReallocVec.h:99
const T * const_iterator
Read-only random-access iterator.
Definition: ReallocVec.h:43
T & front()
Gets a reference to the first element.
Definition: ReallocVec.h:116
T & reference
A reference to an element.
Definition: ReallocVec.h:38
bool resize(size_t n) noexcept
Changes the number of elements.
Definition: ReallocVec.h:149
const_reverse_iterator rbegin() const noexcept
Gets the read-only reverse iterator pointing to the last element.
Definition: ReallocVec.h:140
bool reserve(size_t n) noexcept
Makes it possible to store as many as n elements without reallocating memory.
Definition: ReallocVec.h:148
T & back()
Gets a reference to the last element.
Definition: ReallocVec.h:124
bool pop(T *v) noexcept
Gets the first element in the queue and then deletes it.
Definition: ReallocVec.h:262
ReallocQueue(ReallocQueue &&rhs) noexcept
Instantiates the object (move constructor).
Definition: ReallocVec.h:209
bool pop_back() noexcept
Deletes an element from the end of the vector.
Definition: ReallocVec.h:109
An empty structure indicating that an argument to a function needs to be moved.
Definition: Config.h:270
ReallocQueue & operator=(ReallocQueue &&rhs) noexcept
Move assignment operator.
Definition: ReallocVec.h:214
bool empty() const noexcept
Determines whether the vector is empty.
Definition: ReallocVec.h:334
std::reverse_iterator< const_iterator > const_reverse_iterator
Read-only reverse iterator.
Definition: ReallocVec.h:45
ReallocFunc GetRealloc() const noexcept
Gets the specified realloc function.
Definition: ReallocVec.h:235
ReallocCstringVec() noexcept
Instantiates the object with default parameters (default constructor). Uses std::realloc.
Definition: ReallocVec.h:287
T & operator[](size_t idx)
Gets the nth element, where n is specified by idx.
Definition: ReallocVec.h:114
size_t size() const noexcept
Gets the size of the queue.
Definition: ReallocVec.h:236
reverse_iterator rend() noexcept
Gets the reverse iterator pointing ahead of the first element.
Definition: ReallocVec.h:141
bool push_back(const char *str) noexcept
Adds a C string to the end.
Definition: ReallocVec.h:309
const_reverse_iterator rend() const noexcept
Gets the read-only reverse iterator pointing ahead of the first element.
Definition: ReallocVec.h:142
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:288
size_t capacity() const noexcept
Gets the maximum number of elements that can be stored without expanding the vector.
Definition: ReallocVec.h:333
void clear() noexcept
Empties the vector. Note that the memory remains allocated.
Definition: ReallocVec.h:154
void clear() noexcept
Empties the vector.
Definition: ReallocVec.h:336
bool empty() const noexcept
Returns true if the number of stored elements is 0, or returns false otherwise.
Definition: ReallocVec.h:147
#define NLIB_NOEXCEPT
Defines noexcept geared to the environment, or the equivalent.
Definition: Config.h:109
size_t capacity() const noexcept
Gets the maximum number of elements that can be stored without reallocating memory.
Definition: ReallocVec.h:146
iterator end() noexcept
Gets the iterator pointing beyond the last element.
Definition: ReallocVec.h:136
const T & operator[](size_t idx) const
The const decoration version of the above function.
Definition: ReallocVec.h:115
#define NLIB_CEXPR
Defines constexpr if it is available for use. If not, holds an empty string.
Definition: Config.h:111
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:139
bool push(const T &val) noexcept
Adds an element to the queue.
Definition: ReallocVec.h:240
std::reverse_iterator< iterator > reverse_iterator
A reverse 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:312
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 reverse iterator pointing ahead of the first element.
Definition: ReallocVec.h:144
char * operator[](size_t idx) noexcept
Gets the nth string, where n is specified by idx.
Definition: ReallocVec.h:326
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:155
const char * operator[](size_t idx) const noexcept
The const decoration version of the above function.
Definition: ReallocVec.h:327
iterator begin() noexcept
Gets the iterator pointing to the first element.
Definition: ReallocVec.h:133
ReallocFunc GetRealloc() const noexcept
Gets the specified realloc function.
Definition: ReallocVec.h:308
#define NLIB_STATIC_ASSERT(exp)
Defines a static assertion. Uses static_assert if it is available for use.
Definition: Config.h:174
ReallocQueue() noexcept
Instantiates the object with default parameters (default constructor). Uses std::realloc.
Definition: ReallocVec.h:203
T * pointer
Pointer to the element.
Definition: ReallocVec.h:40
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:252
size_t size() const noexcept
Gets the size of the vector.
Definition: ReallocVec.h:332
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.
ReallocVec(ReallocVec &&rhs) noexcept
Instantiates the object (move constructor).
Definition: ReallocVec.h:58
const_iterator cend() const noexcept
Gets the read-only iterator pointing beyond the last element.
Definition: ReallocVec.h:138
const T & back() const
The const decoration version of the above function.
Definition: ReallocVec.h:128