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;
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
上記関数のconst修飾付き版です。
Definition: ReallocVec.h:120
T * iterator
ランダムアクセス反復子です。
Definition: ReallocVec.h:42
ReallocQueue(ReallocFunc func) noexcept
コンストラクタで、realloc関数をユーザーが指定できます。
Definition: ReallocVec.h:204
const_iterator end() const noexcept
末尾の次を指す読み取り専用反復子を取得します。
Definition: ReallocVec.h:137
ReallocVec< T >::ReallocFunc ReallocFunc
reallocに相当する関数の型です。
Definition: ReallocVec.h:202
T value_type
要素型 T
Definition: ReallocVec.h:35
bool push_back(const T &v) noexcept
ベクタに要素を追加します。
Definition: ReallocVec.h:100
C++11の標準ヘッダとなるtype_traitsの代用定義です。 コンパイラや標準ライブラリによってサポートされてい...
size_t size_type
符号なし整数型(size_t)
Definition: ReallocVec.h:36
char * front() noexcept
最初の文字列を取得します。
Definition: ReallocVec.h:328
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
TypeName で指定されたクラスのコピーコンストラクタと代入演算子を禁止します。
Definition: Config.h:183
ReallocVec & operator=(ReallocVec &&rhs) noexcept
ムーブ代入演算子です。
Definition: ReallocVec.h:67
bool pop_back() noexcept
ベクタの末尾から文字列を削除します。
Definition: ReallocVec.h:320
size_t size() const noexcept
格納されている要素数を返します。
Definition: ReallocVec.h:145
const_iterator begin() const noexcept
先頭要素を指す読み取り専用反復子を取得します。
Definition: ReallocVec.h:134
C文字列のベクタをreallocベースで実装しています。
Definition: ReallocVec.h:282
Definition: Base64.h:25
bool empty() const noexcept
キューが空かどうかを判定する
Definition: ReallocVec.h:237
PODを要素に持つキューをreallocベースで実装しています。
Definition: ReallocVec.h:200
const char * front() const noexcept
上記関数のconst修飾付き版です。
Definition: ReallocVec.h:329
const char * back() const noexcept
上記関数のconst修飾付き版です。
Definition: ReallocVec.h:331
const T * const_pointer
要素への読み取り専用ポインタです。
Definition: ReallocVec.h:41
bool reserve(size_t n) noexcept
n 個の要素までをベクタの拡張をせずに格納できるようにする。
Definition: ReallocVec.h:335
iterator insert(iterator pos, const T &val)
要素をposの場所に挿入します。
Definition: ReallocVec.h:166
char * back() noexcept
最後の文字列を取得します。
Definition: ReallocVec.h:330
const_reverse_iterator crbegin() const noexcept
末尾要素を指す読み取り専用逆反復子を取得します。
Definition: ReallocVec.h:143
bool pop() noexcept
キューの先頭要素を削除する。
Definition: ReallocVec.h:241
std::unique_ptrに相当するクラスが定義されています。
const_iterator cbegin() const noexcept
先頭要素を指す読み取り専用反復子を取得します。
Definition: ReallocVec.h:135
const T & const_reference
要素への読み取り専用参照です。
Definition: ReallocVec.h:39
ReallocFunc GetRealloc() const noexcept
指定したrealloc関数を取得します。
Definition: ReallocVec.h:99
const T * const_iterator
読み取り専用ランダムアクセス反復子です。
Definition: ReallocVec.h:43
T & front()
最初の要素への参照を取得します。
Definition: ReallocVec.h:116
T & reference
要素への参照です。
Definition: ReallocVec.h:38
bool resize(size_t n) noexcept
要素数を変更する
Definition: ReallocVec.h:149
const_reverse_iterator rbegin() const noexcept
末尾要素を指す読み取り専用逆反復子を取得します。
Definition: ReallocVec.h:140
bool reserve(size_t n) noexcept
n 個の要素までをメモリを最確保せずに格納できるようにする。
Definition: ReallocVec.h:148
T & back()
最後の要素への参照を取得します。
Definition: ReallocVec.h:124
bool pop(T *v) noexcept
キューの先頭要素を取得し、その後削除する。
Definition: ReallocVec.h:262
ReallocQueue(ReallocQueue &&rhs) noexcept
ムーブコンストラクタです。
Definition: ReallocVec.h:209
bool pop_back() noexcept
ベクタの末尾から要素を削除します。
Definition: ReallocVec.h:109
空の構造体で、関数の引数をムーブすべきことを示すために利用されます。
Definition: Config.h:270
ReallocQueue & operator=(ReallocQueue &&rhs) noexcept
ムーブ代入演算子です。
Definition: ReallocVec.h:214
bool empty() const noexcept
ベクタが空かどうかを判定する
Definition: ReallocVec.h:334
std::reverse_iterator< const_iterator > const_reverse_iterator
読み取り専用逆反復子です。
Definition: ReallocVec.h:45
ReallocFunc GetRealloc() const noexcept
指定したrealloc関数を取得します。
Definition: ReallocVec.h:235
ReallocCstringVec() noexcept
デフォルトコンストラクタです。 std::reallocを利用します。
Definition: ReallocVec.h:287
T & operator[](size_t idx)
idx 番目の要素を取得します。
Definition: ReallocVec.h:114
size_t size() const noexcept
キューのサイズを取得する
Definition: ReallocVec.h:236
reverse_iterator rend() noexcept
先頭の前を指す逆反復子を取得します。
Definition: ReallocVec.h:141
bool push_back(const char *str) noexcept
C文字列を末尾に追加します。
Definition: ReallocVec.h:309
const_reverse_iterator rend() const noexcept
先頭の前を指す読み取り専用逆反復子を取得します。
Definition: ReallocVec.h:142
constexpr ReallocVec() noexcept
デフォルトコンストラクタで、std::reallocを利用します。
Definition: ReallocVec.h:46
ReallocCstringVec(ReallocFunc func) noexcept
コンストラクタで、realloc関数をユーザーが指定できます。
Definition: ReallocVec.h:288
size_t capacity() const noexcept
ベクタの拡張をせずに格納できる最大の要素数を取得する
Definition: ReallocVec.h:333
void clear() noexcept
ベクタを空にします。メモリは確保されたままであることに注意してください。
Definition: ReallocVec.h:154
void clear() noexcept
ベクタを空にします。
Definition: ReallocVec.h:336
bool empty() const noexcept
格納されている要素数が0ならばtrue、それ以外ならfalseを返します。
Definition: ReallocVec.h:147
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
Definition: Config.h:109
size_t capacity() const noexcept
メモリを再確保せずに格納できる最大の要素数を取得する
Definition: ReallocVec.h:146
iterator end() noexcept
末尾の次を指す反復子を取得します。
Definition: ReallocVec.h:136
const T & operator[](size_t idx) const
上記関数のconst修飾付き版です。
Definition: ReallocVec.h:115
#define NLIB_CEXPR
利用可能であればconstexprが定義されます。そうでない場合は空文字列です。
Definition: Config.h:111
開発環境別の設定が書かれるファイルです。
reverse_iterator rbegin() noexcept
末尾要素を指す逆反復子を取得します。
Definition: ReallocVec.h:139
bool push(const T &val) noexcept
キューに要素を追加する。
Definition: ReallocVec.h:240
std::reverse_iterator< iterator > reverse_iterator
逆反復子です。
Definition: ReallocVec.h:44
bool push_back(const char *startchar_ptr, const char *endchar_ptr) noexcept
(部分)文字列を末尾に追加します。
Definition: ReallocVec.h:312
void * nlib_realloc(void *ptr, size_t size)
C標準関数のrealloc()を呼び出すweak関数です。nlibはこの関数を経由してrealloc()を呼び出します。 ...
const_reverse_iterator crend() const noexcept
先頭の前を指す読み取り専用逆反復子を取得します。
Definition: ReallocVec.h:144
char * operator[](size_t idx) noexcept
idx番目の文字列を取得します。
Definition: ReallocVec.h:326
size_t nlib_strlen(const char *s)
内部でstrlen()を呼び出します。独自の実装が動作する場合もあります。
void shrink_to_fit() noexcept
確保されたメモリを現在の要素数を丁度格納できるサイズにフィッティングします。
Definition: ReallocVec.h:155
const char * operator[](size_t idx) const noexcept
上記関数のconst修飾付き版です。
Definition: ReallocVec.h:327
iterator begin() noexcept
先頭要素を指す反復子を取得します。
Definition: ReallocVec.h:133
ReallocFunc GetRealloc() const noexcept
指定したrealloc関数を取得します。
Definition: ReallocVec.h:308
#define NLIB_STATIC_ASSERT(exp)
静的アサートが定義されます。利用可能であればstatic_assertを利用します。
Definition: Config.h:174
ReallocQueue() noexcept
デフォルトコンストラクタです。 std::reallocを利用します。
Definition: ReallocVec.h:203
T * pointer
要素へのポインタです。
Definition: ReallocVec.h:40
ptrdiff_t difference_type
符号つき整数型(ptrdiff_t)
Definition: ReallocVec.h:37
T & front()
キューの先頭要素を取得する。
Definition: ReallocVec.h:252
size_t size() const noexcept
ベクタのサイズを取得する
Definition: ReallocVec.h:332
PODを要素に持つベクタをreallocベースで実装しています。
Definition: ReallocVec.h:32
#define NLIB_NONNULL
全ての引数にNULLを指定することができないことを示します。
ReallocVec(ReallocVec &&rhs) noexcept
ムーブコンストラクタです。
Definition: ReallocVec.h:58
const_iterator cend() const noexcept
末尾の次を指す読み取り専用反復子を取得します。
Definition: ReallocVec.h:138
const T & back() const
上記関数のconst修飾付き版です。
Definition: ReallocVec.h:128