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