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 
24 #include "nn/nlib/Config.h"
25 #include "nn/nlib/UniquePtr.h"
26 #include "nn/nlib/TypeTraits.h"
27 
28 NLIB_NAMESPACE_BEGIN
29 
30 template <class T>
31 class ReallocVec {
32  public:
33  typedef void* (*ReallocFunc)(void*, size_t) NLIB_NOEXCEPT_FUNCPTR;
34  typedef T value_type;
35  typedef size_t size_type;
36  typedef ptrdiff_t difference_type;
37  typedef T& reference;
38  typedef const T& const_reference;
39  typedef T* pointer;
40  typedef const T* const_pointer;
41  typedef T* iterator;
42  typedef const T* const_iterator;
43  typedef std::reverse_iterator<iterator> reverse_iterator;
44  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
46  cur_(0),
47  size_(0),
48  realloc_(::nlib_realloc) {}
49  NLIB_CEXPR explicit ReallocVec(ReallocFunc func) NLIB_NOEXCEPT NLIB_NONNULL;
51  if (vec_) {
52  realloc_(vec_, 0);
53  }
54  NLIB_STATIC_ASSERT(IsPod<T>::value);
55  }
56  NLIB_MOVE_MEMBER_HELPER_4(ReallocVec, vec_, cur_, size_, realloc_)
57 
58  ReallocFunc GetRealloc() const NLIB_NOEXCEPT { return realloc_; }
59  bool push_back(const T& v) NLIB_NOEXCEPT {
60  if (cur_ == size_) {
61  size_t newsize = (size_ == 0) ? 1 : size_ * 2;
62  if (newsize < size_) return false;
63  if (!this->Expand(newsize)) return false;
64  }
65  vec_[cur_++] = v;
66  return true;
67  }
69  if (cur_ == 0) return false;
70  --cur_;
71  return true;
72  }
73  T& operator[](size_t idx) { return vec_[idx]; }
74  const T& operator[](size_t idx) const { return vec_[idx]; }
75  T& front() { return *begin(); }
76  const T& front() const { return *begin(); }
77  T& back() { return *(begin() + cur_ - 1); }
78  const T& back() const { return *(begin() + cur_ - 1); }
79 
80  iterator begin() NLIB_NOEXCEPT { return vec_; }
81  const_iterator begin() const NLIB_NOEXCEPT { return vec_; }
82  const_iterator cbegin() const NLIB_NOEXCEPT { return vec_; }
83  iterator end() NLIB_NOEXCEPT { return begin() + cur_; }
84  const_iterator end() const NLIB_NOEXCEPT { return begin() + cur_; }
85  const_iterator cend() const NLIB_NOEXCEPT { return begin() + cur_; }
88  return const_reverse_iterator(end());
89  }
92  return const_reverse_iterator(begin());
93  }
95  return const_reverse_iterator(end());
96  }
98  return const_reverse_iterator(begin());
99  }
101  using std::swap;
102  swap(vec_, rhs.vec_);
103  swap(cur_, rhs.cur_);
104  swap(size_, rhs.size_);
105  swap(realloc_, rhs.realloc_);
106  }
107  size_t size() const NLIB_NOEXCEPT { return cur_; }
108  size_t capacity() const NLIB_NOEXCEPT { return size_; }
109  bool empty() const NLIB_NOEXCEPT { return cur_ == 0; }
110  bool reserve(size_t n) NLIB_NOEXCEPT {
111  return (n > size_) ? this->Expand(n) : true;
112  }
113  bool resize(size_t n) NLIB_NOEXCEPT {
114  if (!this->reserve(n)) return false;
115  cur_ = n;
116  return true;
117  }
118  void clear() NLIB_NOEXCEPT { cur_ = 0; }
120  if (cur_ != size_) {
121  if (cur_ > 0) {
122  this->Expand(cur_);
123  } else {
124  realloc_(vec_, 0);
125  vec_ = NULL;
126  size_ = 0;
127  }
128  }
129  }
130  iterator insert(iterator pos, const T& val) {
131  ptrdiff_t idx = pos - begin();
132  if (!this->push_back(val)) return NULL;
133  std::rotate(begin() + idx, &back(), end());
134  return begin() + idx;
135  }
136 
137  private:
138  bool Expand(size_t new_size) NLIB_NOEXCEPT;
139 
140  T* vec_;
141  size_t cur_;
142  size_t size_;
143  ReallocFunc realloc_;
145 };
146 
147 template <class T>
148 inline NLIB_CEXPR ReallocVec<T>::ReallocVec(ReallocFunc func) NLIB_NOEXCEPT : vec_(NULL),
149  cur_(0),
150  size_(0),
151  realloc_(func) {}
152 
153 template <class T>
154 bool ReallocVec<T>::Expand(size_t new_size) NLIB_NOEXCEPT {
155  T* ptr = vec_;
156  void* new_ptr = realloc_(ptr, new_size * sizeof(T));
157  if (!new_ptr) return false;
158  vec_ = reinterpret_cast<T*>(new_ptr);
159  size_ = new_size;
160  return true;
161 }
162 
163 template <class T>
165  public:
167  ReallocQueue() NLIB_NOEXCEPT : front_idx_(0) {}
168  explicit ReallocQueue(ReallocFunc func) NLIB_NOEXCEPT : front_idx_(0),
169  front_vec_(func),
170  back_vec_(func) {}
172  NLIB_MOVE_MEMBER_HELPER_3(ReallocQueue, front_idx_, front_vec_, back_vec_)
173  ReallocFunc GetRealloc() const NLIB_NOEXCEPT {
174  return front_vec_.GetRealloc();
175  }
176  size_t size() const NLIB_NOEXCEPT {
177  return front_vec_.size() - front_idx_ + back_vec_.size();
178  }
179  bool empty() const NLIB_NOEXCEPT {
180  return front_idx_ == front_vec_.size() && back_vec_.empty();
181  }
182  bool push(const T& val) NLIB_NOEXCEPT { return back_vec_.push_back(val); }
184  if (front_idx_ == front_vec_.size()) {
185  if (back_vec_.empty()) return false;
186  front_vec_.clear();
187  front_vec_.swap(back_vec_);
188  front_idx_ = 0;
189  }
190  ++front_idx_;
191  return true;
192  }
193  T& front() {
194  if (front_idx_ == front_vec_.size()) {
195  NLIB_ASSERT(!back_vec_.empty());
196  front_vec_.clear();
197  front_vec_.swap(back_vec_);
198  front_idx_ = 0;
199  }
200  return front_vec_[front_idx_];
201  }
202  bool pop(T* v) NLIB_NOEXCEPT {
203  if (front_idx_ == front_vec_.size()) {
204  if (back_vec_.empty()) return false;
205  front_vec_.clear();
206  front_vec_.swap(back_vec_);
207  front_idx_ = 0;
208  }
209  if (v) *v = front_vec_[front_idx_];
210  ++front_idx_;
211  return true;
212  }
214  using std::swap;
215  swap(front_idx_, rhs.front_idx_);
216  front_vec_.swap(rhs.front_vec_);
217  back_vec_.swap(rhs.back_vec_);
218  }
219 
220  private:
221  size_t front_idx_;
222  ReallocVec<T> front_vec_;
223  ReallocVec<T> back_vec_;
225 };
226 
228  typedef ReallocVec<char*> VecType;
229  typedef VecType::ReallocFunc ReallocFunc;
230 
231  public:
233  explicit ReallocCstringVec(ReallocFunc func) NLIB_NOEXCEPT : vec_(func) {}
234  ~ReallocCstringVec() NLIB_NOEXCEPT { this->clear(); }
235  NLIB_MOVE_MEMBER_HELPER_1(ReallocCstringVec, vec_)
236  ReallocFunc GetRealloc() const NLIB_NOEXCEPT { return vec_.GetRealloc(); }
237  bool push_back(const char* str) NLIB_NOEXCEPT {
238  return this->push_back(str, str + nlib_strlen(str));
239  }
240  bool push_back(const char* startchar_ptr,
241  const char* endchar_ptr) NLIB_NOEXCEPT {
242  size_t n = endchar_ptr - startchar_ptr;
243  char* p = reinterpret_cast<char*>(vec_.GetRealloc()(NULL, n + 1));
244  if (!p) return false;
245  nlib_memcpy(p, n, startchar_ptr, n);
246  p[n] = '\0';
247  if (!vec_.push_back(p)) return false;
248  return true;
249  }
251  if (vec_.empty()) return false;
252  vec_.GetRealloc()(vec_.back(), 0);
253  vec_.pop_back();
254  return true;
255  }
256  char* operator[](size_t idx)NLIB_NOEXCEPT { return vec_[idx]; }
257  const char* operator[](size_t idx) const NLIB_NOEXCEPT {
258  return vec_[idx];
259  }
260  char* front() NLIB_NOEXCEPT { return vec_.front(); }
261  const char* front() const NLIB_NOEXCEPT { return vec_.front(); }
262  char* back() NLIB_NOEXCEPT { return vec_.back(); }
263  const char* back() const NLIB_NOEXCEPT { return vec_.back(); }
264  void swap(ReallocCstringVec& rhs) NLIB_NOEXCEPT { vec_.swap(rhs.vec_); }
265  size_t size() const NLIB_NOEXCEPT { return vec_.size(); }
266  size_t capacity() const NLIB_NOEXCEPT { return vec_.capacity(); }
267  bool empty() const NLIB_NOEXCEPT { return vec_.empty(); }
268  bool reserve(size_t n) NLIB_NOEXCEPT { return vec_.reserve(n); }
269  void clear() NLIB_NOEXCEPT {
270  VecType::iterator it = vec_.begin();
271  VecType::iterator end = vec_.end();
272  for (; it != end; ++it) {
273  vec_.GetRealloc()(*it, 0);
274  }
275  vec_.clear();
276  }
277 
278  private:
279  VecType vec_;
281 };
282 
283 NLIB_NAMESPACE_END
284 
285 NLIB_DEFINE_STD_SWAP(NLIB_NS::ReallocCstringVec)
286 #ifndef NLIB_STD_SWAP_WORKAROUND
287 NLIB_NAMESPACE_BEGIN
288 #else
289 NLIB_DEFINE_STD_SWAP_T_BEGIN1(std) // NOLINT
290 #endif
291 
292 NLIB_DEFINE_STD_SWAP_T1(AL, NLIB_NS::ReallocVec) // NOLINT
293 NLIB_DEFINE_STD_SWAP_T1(AL, NLIB_NS::ReallocQueue) // NOLINT
294 
295 #ifndef NLIB_STD_SWAP_WORKAROUND
296 NLIB_NAMESPACE_END
297 #else
298 NLIB_DEFINE_STD_SWAP_T_END1(std) // NOLINT
299 #endif
300 
301 #endif // INCLUDE_NN_NLIB_REALLOCVEC_H_
const T & front() const
See front.
Definition: ReallocVec.h:76
T * iterator
Random-access iterator.
Definition: ReallocVec.h:41
ReallocQueue(ReallocFunc func) noexcept
Enables the user to specify the realloc function with the constructor.
Definition: ReallocVec.h:168
const_iterator end() const noexcept
See end.
Definition: ReallocVec.h:84
ReallocVec< T >::ReallocFunc ReallocFunc
The type for functions corresponding to realloc.
Definition: ReallocVec.h:166
T value_type
Element type T.
Definition: ReallocVec.h:34
bool push_back(const T &v) noexcept
Adds an element to the vector.
Definition: ReallocVec.h:59
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:35
char * front() noexcept
Gets the first string.
Definition: ReallocVec.h:260
#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 pop_back() noexcept
Deletes a string from the end of the vector.
Definition: ReallocVec.h:250
size_t size() const noexcept
Gets the size of the vector.
Definition: ReallocVec.h:107
const_iterator begin() const noexcept
See begin.
Definition: ReallocVec.h:81
The class for realloc-based implementations of C string vectors.
Definition: ReallocVec.h:227
bool empty() const noexcept
Determines whether the queue is empty.
Definition: ReallocVec.h:179
The class for realloc-based implementations of queues with POD-type elements.
Definition: ReallocVec.h:164
STL namespace.
const T * const_pointer
const T*.
Definition: ReallocVec.h:40
bool reserve(size_t n) noexcept
Makes it possible to store as many as n elements without expanding the vector.
Definition: ReallocVec.h:268
iterator insert(iterator pos, const T &val)
Inserts an element in the position specified by pos.
Definition: ReallocVec.h:130
char * back() noexcept
Gets the last string.
Definition: ReallocVec.h:262
const_reverse_iterator crbegin() const noexcept
Gets the read-only reverse iterator pointing to the last element.
Definition: ReallocVec.h:94
bool pop() noexcept
Deletes the first element in the queue.
Definition: ReallocVec.h:183
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:82
const T & const_reference
const T&.
Definition: ReallocVec.h:38
const T * const_iterator
Read-only random-access iterator.
Definition: ReallocVec.h:42
T & front()
Gets the first element.
Definition: ReallocVec.h:75
void swap(ReallocCstringVec &rhs) noexcept
Swaps vectors.
Definition: ReallocVec.h:264
bool resize(size_t n) noexcept
Changes the number of elements.
Definition: ReallocVec.h:113
const_reverse_iterator rbegin() const noexcept
See rbegin.
Definition: ReallocVec.h:87
bool reserve(size_t n) noexcept
Makes it possible to store as many as n elements without reallocating memory.
Definition: ReallocVec.h:110
T & back()
Gets the last element.
Definition: ReallocVec.h:77
bool pop(T *v) noexcept
Gets the first element in the queue and then deletes it.
Definition: ReallocVec.h:202
bool pop_back() noexcept
Deletes an element from the end of the vector.
Definition: ReallocVec.h:68
void swap(ReallocQueue &rhs) noexcept
Swaps queues.
Definition: ReallocVec.h:213
bool empty() const noexcept
Determines whether the vector is empty.
Definition: ReallocVec.h:267
std::reverse_iterator< const_iterator > const_reverse_iterator
std::reverse_iterator<const_iterator>
Definition: ReallocVec.h:44
ReallocCstringVec() noexcept
Uses std::realloc with the default constructor.
Definition: ReallocVec.h:232
T & operator[](size_t idx)
Gets the nth element, where n is specified by idx.
Definition: ReallocVec.h:73
size_t size() const noexcept
Gets the size of the queue.
Definition: ReallocVec.h:176
reverse_iterator rend() noexcept
Gets the reverse iterator pointing ahead of the first element.
Definition: ReallocVec.h:90
bool push_back(const char *str) noexcept
Adds a C string to the end.
Definition: ReallocVec.h:237
const_reverse_iterator rend() const noexcept
See rend.
Definition: ReallocVec.h:91
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:2357
constexpr ReallocVec() noexcept
Uses std::realloc with the default constructor.
Definition: ReallocVec.h:45
ReallocCstringVec(ReallocFunc func) noexcept
Enables the user to specify the realloc function with the constructor.
Definition: ReallocVec.h:233
size_t capacity() const noexcept
Gets the maximum number of elements that can be stored without expanding the vector.
Definition: ReallocVec.h:266
void clear() noexcept
Empties the vector. Note that the memory remains allocated.
Definition: ReallocVec.h:118
bool empty() const noexcept
Determines whether the vector is empty.
Definition: ReallocVec.h:109
#define NLIB_NOEXCEPT
Defines noexcept geared to the environment, or the equivalent.
Definition: Config.h:99
size_t capacity() const noexcept
Gets the maximum number of elements that can be stored without reallocating memory.
Definition: ReallocVec.h:108
iterator end() noexcept
Gets the iterator pointing beyond the last element.
Definition: ReallocVec.h:83
const T & operator[](size_t idx) const
See operator[](size_t idx) =.
Definition: ReallocVec.h:74
#define NLIB_CEXPR
Defines constexpr if it is available for use. If not, holds an empty string.
Definition: Config.h:93
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:86
bool push(const T &val) noexcept
Adds an element to the queue.
Definition: ReallocVec.h:182
std::reverse_iterator< iterator > reverse_iterator
std::reverse_iterator<iterator>
Definition: ReallocVec.h:43
bool push_back(const char *startchar_ptr, const char *endchar_ptr) noexcept
Adds a (sub)string to the end.
Definition: ReallocVec.h:240
NLIB_CHECK_RESULT 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:97
char * operator[](size_t idx) noexcept
Gets the nth string, where n is specified by idx.
Definition: ReallocVec.h:256
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:119
iterator begin() noexcept
Gets the iterator pointing to the first element.
Definition: ReallocVec.h:80
#define NLIB_STATIC_ASSERT(exp)
Defines a static assertion. Uses static_assert if it is available for use.
Definition: Config.h:154
ReallocQueue() noexcept
Uses std::realloc with the default constructor.
Definition: ReallocVec.h:167
ptrdiff_t difference_type
Signed integer type (ptrdiff_t).
Definition: ReallocVec.h:36
T & front()
Gets the first element in the queue.
Definition: ReallocVec.h:193
size_t size() const noexcept
Gets the size of the vector.
Definition: ReallocVec.h:265
The class for realloc-based implementations of vectors with POD-type elements.
Definition: ReallocVec.h:31
#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:85
void swap(ReallocVec &rhs) noexcept
Swaps vectors.
Definition: ReallocVec.h:100
const T & back() const
See back.
Definition: ReallocVec.h:78