nlib
ReallocVec.h
[詳解]
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
front()をご覧ください。
Definition: ReallocVec.h:118
T * iterator
ランダムアクセスイテレータ
Definition: ReallocVec.h:42
ReallocQueue(ReallocFunc func) noexcept
コンストラクタで、realloc関数をユーザーが指定できます。
Definition: ReallocVec.h:203
const_iterator end() const noexcept
end()を御覧ください。
Definition: ReallocVec.h:126
ReallocVec< T >::ReallocFunc ReallocFunc
reallocに相当する関数の型です。
Definition: ReallocVec.h:201
T value_type
要素型 T
Definition: ReallocVec.h:35
bool push_back(const T &v) noexcept
ベクタに要素を追加します。
Definition: ReallocVec.h:101
C++11の標準ヘッダとなるtype_traitsの代用定義です。 コンパイラや標準ライブラリによってサポートされてい...
size_t size_type
符号なし整数型(size_t)
Definition: ReallocVec.h:36
char * front() noexcept
最初の文字列を取得します。
Definition: ReallocVec.h:344
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
TypeName で指定されたクラスのコピーコンストラクタと代入演算子を禁止します。
Definition: Config.h:179
bool pop_back() noexcept
ベクタの末尾から文字列を削除します。
Definition: ReallocVec.h:334
size_t size() const noexcept
ベクタのサイズを取得する
Definition: ReallocVec.h:142
const_iterator begin() const noexcept
begin()を御覧ください。
Definition: ReallocVec.h:123
C文字列のベクタをreallocベースで実装しています。
Definition: ReallocVec.h:290
Definition: Base64.h:25
bool empty() const noexcept
キューが空かどうかを判定する
Definition: ReallocVec.h:245
PODを要素に持つキューをreallocベースで実装しています。
Definition: ReallocVec.h:199
const T * const_pointer
const T*
Definition: ReallocVec.h:41
bool reserve(size_t n) noexcept
n 個の要素までをベクタの拡張をせずに格納できるようにする。
Definition: ReallocVec.h:351
iterator insert(iterator pos, const T &val)
要素をposの場所に挿入します。
Definition: ReallocVec.h:165
char * back() noexcept
最後の文字列を取得します。
Definition: ReallocVec.h:346
const_reverse_iterator crbegin() const noexcept
末尾要素を指す読み取り専用逆イテレータを取得する。
Definition: ReallocVec.h:136
bool pop() noexcept
キューの先頭要素を削除する。
Definition: ReallocVec.h:249
std::unique_ptrに相当するクラスが定義されています。
const_iterator cbegin() const noexcept
先頭要素を指す読み取り専用イテレータを取得する。
Definition: ReallocVec.h:124
const T & const_reference
const T&
Definition: ReallocVec.h:39
#define NLIB_DEPRECATED
関数等がdeprecatedになったことを示します。
Definition: Config.h:109
ReallocFunc GetRealloc() const noexcept
指定したrealloc関数を取得します。
Definition: ReallocVec.h:100
const T * const_iterator
読み取り専用ランダムアクセスイテレータ
Definition: ReallocVec.h:43
T & front()
最初の要素を取得します。
Definition: ReallocVec.h:117
void swap(ReallocCstringVec &rhs) noexcept
ベクタを交換する
Definition: ReallocVec.h:316
bool resize(size_t n) noexcept
要素数を変更する
Definition: ReallocVec.h:148
const_reverse_iterator rbegin() const noexcept
rbegin()を御覧ください。
Definition: ReallocVec.h:129
bool reserve(size_t n) noexcept
n 個の要素までをメモリを最確保せずに格納できるようにする。
Definition: ReallocVec.h:145
T & back()
最後の要素を取得します。
Definition: ReallocVec.h:119
bool pop(T *v) noexcept
キューの先頭要素を取得し、その後削除する。
Definition: ReallocVec.h:270
bool pop_back() noexcept
ベクタの末尾から要素を削除します。
Definition: ReallocVec.h:110
void swap(ReallocQueue &rhs) noexcept
キューを交換する
Definition: ReallocVec.h:233
空の構造体で、関数の引数をムーブすべきことを示すために利用されます。
Definition: Config.h:265
bool empty() const noexcept
ベクタが空かどうかを判定する
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
指定したrealloc関数を取得します。
Definition: ReallocVec.h:239
ReallocCstringVec() noexcept
デフォルトコンストラクタで、std::reallocを利用します。
Definition: ReallocVec.h:295
T & operator[](size_t idx)
idx 番目の要素を取得します。
Definition: ReallocVec.h:115
size_t size() const noexcept
キューのサイズを取得する
Definition: ReallocVec.h:242
reverse_iterator rend() noexcept
先頭の前を指す逆イテレータを取得する。
Definition: ReallocVec.h:132
bool push_back(const char *str) noexcept
C文字列を末尾に追加します。
Definition: ReallocVec.h:321
const_reverse_iterator rend() const noexcept
rend()を御覧ください。
Definition: ReallocVec.h:133
static errno_t nlib_memcpy(void *s1, size_t s1max, const void *s2, size_t n)
N1078のmemcpy_sに相当する実装です。
Definition: Platform.h:2437
constexpr ReallocVec() noexcept
デフォルトコンストラクタで、std::reallocを利用します。
Definition: ReallocVec.h:46
ReallocCstringVec(ReallocFunc func) noexcept
コンストラクタで、realloc関数をユーザーが指定できます。
Definition: ReallocVec.h:296
size_t capacity() const noexcept
ベクタの拡張をせずに格納できる最大の要素数を取得する
Definition: ReallocVec.h:349
void clear() noexcept
ベクタを空にします。メモリは確保されたままであることに注意してください。
Definition: ReallocVec.h:153
bool empty() const noexcept
ベクタが空かどうかを判定する
Definition: ReallocVec.h:144
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
Definition: Config.h:105
size_t capacity() const noexcept
メモリを再確保せずに格納できる最大の要素数を取得する
Definition: ReallocVec.h:143
iterator end() noexcept
末尾の次を指すイテレータを取得する。
Definition: ReallocVec.h:125
const T & operator[](size_t idx) const
operator[](size_t idx) を御覧ください。
Definition: ReallocVec.h:116
#define NLIB_CEXPR
利用可能であればconstexprが定義されます。そうでない場合は空文字列です。
Definition: Config.h:107
開発環境別の設定が書かれるファイルです。
reverse_iterator rbegin() noexcept
末尾要素を指す逆イテレータを取得する。
Definition: ReallocVec.h:128
bool push(const T &val) noexcept
キューに要素を追加する。
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
(部分)文字列を末尾に追加します。
Definition: ReallocVec.h:324
void * nlib_realloc(void *ptr, size_t size)
C標準関数のrealloc()を呼び出すweak関数です。nlibはこの関数を経由してrealloc()を呼び出します。 ...
const_reverse_iterator crend() const noexcept
先頭の前を指す読み取り専用逆イテレータを取得する。
Definition: ReallocVec.h:139
char * operator[](size_t idx) noexcept
idx番目の文字列を取得します。
Definition: ReallocVec.h:340
size_t nlib_strlen(const char *s)
内部でstrlen()を呼び出します。独自の実装が動作する場合もあります。
void shrink_to_fit() noexcept
確保されたメモリを現在の要素数を丁度格納できるサイズにフィッティングします。
Definition: ReallocVec.h:154
iterator begin() noexcept
先頭要素を指すイテレータを取得する。
Definition: ReallocVec.h:122
ReallocFunc GetRealloc() const noexcept
指定したrealloc関数を取得します。
Definition: ReallocVec.h:320
#define NLIB_STATIC_ASSERT(exp)
静的アサートが定義されます。利用可能であればstatic_assertを利用します。
Definition: Config.h:170
ReallocQueue() noexcept
デフォルトコンストラクタで、std::reallocを利用します。
Definition: ReallocVec.h:202
ptrdiff_t difference_type
符号つき整数型(ptrdiff_t)
Definition: ReallocVec.h:37
T & front()
キューの先頭要素を取得する。
Definition: ReallocVec.h:260
size_t size() const noexcept
ベクタのサイズを取得する
Definition: ReallocVec.h:348
PODを要素に持つベクタをreallocベースで実装しています。
Definition: ReallocVec.h:32
#define NLIB_NONNULL
全ての引数にNULLを指定することができないことを示します。
const_iterator cend() const noexcept
末尾の次を指す読み取り専用イテレータを取得する。
Definition: ReallocVec.h:127
void swap(ReallocVec &rhs) noexcept
ベクタを交換する
Definition: ReallocVec.h:93
const T & back() const
back()を御覧ください。
Definition: ReallocVec.h:120