OpenTTD
smallvec_type.hpp
Go to the documentation of this file.
1 /* $Id: smallvec_type.hpp 27641 2016-09-04 12:50:22Z alberth $ */
2 
3 /*
4  * This file is part of OpenTTD.
5  * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
6  * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
7  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
8  */
9 
12 #ifndef SMALLVEC_TYPE_HPP
13 #define SMALLVEC_TYPE_HPP
14 
15 #include "alloc_func.hpp"
16 #include "mem_func.hpp"
17 
28 template <typename T, uint S>
29 class SmallVector {
30 protected:
31  T *data;
32  uint items;
33  uint capacity;
34 
35 public:
36  SmallVector() : data(NULL), items(0), capacity(0) { }
37 
42  SmallVector(const SmallVector &other) : data(NULL), items(0), capacity(0)
43  {
44  this->Assign(other);
45  }
46 
51  template <uint X>
52  SmallVector(const SmallVector<T, X> &other) : data(NULL), items(0), capacity(0)
53  {
54  this->Assign(other);
55  }
56 
62  {
63  this->Assign(other);
64  return *this;
65  }
66 
71  template <uint X>
73  {
74  this->Assign(other);
75  return *this;
76  }
77 
78  ~SmallVector()
79  {
80  free(this->data);
81  }
82 
86  template <uint X>
87  inline void Assign(const SmallVector<T, X> &other)
88  {
89  if ((const void *)&other == (void *)this) return;
90 
91  this->Clear();
92  if (other.Length() > 0) MemCpyT<T>(this->Append(other.Length()), other.Begin(), other.Length());
93  }
94 
98  inline void Clear()
99  {
100  /* In fact we just reset the item counter avoiding the need to
101  * probably reallocate the same amount of memory the list was
102  * previously using. */
103  this->items = 0;
104  }
105 
109  inline void Reset()
110  {
111  this->items = 0;
112  this->capacity = 0;
113  free(data);
114  data = NULL;
115  }
116 
120  inline void Compact()
121  {
122  uint capacity = Align(this->items, S);
123  if (capacity >= this->capacity) return;
124 
125  this->capacity = capacity;
126  this->data = ReallocT(this->data, this->capacity);
127  }
128 
134  inline T *Append(uint to_add = 1)
135  {
136  uint begin = this->items;
137  this->items += to_add;
138 
139  if (this->items > this->capacity) {
140  this->capacity = Align(this->items, S);
141  this->data = ReallocT(this->data, this->capacity);
142  }
143 
144  return &this->data[begin];
145  }
146 
151  inline void Resize(uint num_items)
152  {
153  this->items = num_items;
154 
155  if (this->items > this->capacity) {
156  this->capacity = Align(this->items, S);
157  this->data = ReallocT(this->data, this->capacity);
158  }
159  }
160 
167  inline const T *Find(const T &item) const
168  {
169  const T *pos = this->Begin();
170  const T *end = this->End();
171  while (pos != end && *pos != item) pos++;
172  return pos;
173  }
174 
181  inline T *Find(const T &item)
182  {
183  T *pos = this->Begin();
184  const T *end = this->End();
185  while (pos != end && *pos != item) pos++;
186  return pos;
187  }
188 
195  inline int FindIndex(const T &item) const
196  {
197  int index = 0;
198  const T *pos = this->Begin();
199  const T *end = this->End();
200  while (pos != end && *pos != item) {
201  pos++;
202  index++;
203  }
204  return pos == end ? -1 : index;
205  }
206 
213  inline bool Contains(const T &item) const
214  {
215  return this->Find(item) != this->End();
216  }
217 
223  inline void Erase(T *item)
224  {
225  assert(item >= this->Begin() && item < this->End());
226  *item = this->data[--this->items];
227  }
228 
234  void ErasePreservingOrder(uint pos, uint count = 1)
235  {
236  if (count == 0) return;
237  assert(pos < this->items);
238  assert(pos + count <= this->items);
239  this->items -= count;
240  uint to_move = this->items - pos;
241  if (to_move > 0) MemMoveT(this->data + pos, this->data + pos + count, to_move);
242  }
243 
250  inline bool Include(const T &item)
251  {
252  bool is_member = this->Contains(item);
253  if (!is_member) *this->Append() = item;
254  return is_member;
255  }
256 
262  inline uint Length() const
263  {
264  return this->items;
265  }
266 
272  inline const T *Begin() const
273  {
274  return this->data;
275  }
276 
282  inline T *Begin()
283  {
284  return this->data;
285  }
286 
292  inline const T *End() const
293  {
294  return &this->data[this->items];
295  }
296 
302  inline T *End()
303  {
304  return &this->data[this->items];
305  }
306 
313  inline const T *Get(uint index) const
314  {
315  /* Allow access to the 'first invalid' item */
316  assert(index <= this->items);
317  return &this->data[index];
318  }
319 
326  inline T *Get(uint index)
327  {
328  /* Allow access to the 'first invalid' item */
329  assert(index <= this->items);
330  return &this->data[index];
331  }
332 
339  inline const T &operator[](uint index) const
340  {
341  assert(index < this->items);
342  return this->data[index];
343  }
344 
351  inline T &operator[](uint index)
352  {
353  assert(index < this->items);
354  return this->data[index];
355  }
356 };
357 
358 
369 template <typename T, uint S>
370 class AutoFreeSmallVector : public SmallVector<T, S> {
371 public:
373  {
374  this->Clear();
375  }
376 
380  inline void Clear()
381  {
382  for (uint i = 0; i < this->items; i++) {
383  free(this->data[i]);
384  }
385 
386  this->items = 0;
387  }
388 };
389 
400 template <typename T, uint S>
401 class AutoDeleteSmallVector : public SmallVector<T, S> {
402 public:
404  {
405  this->Clear();
406  }
407 
411  inline void Clear()
412  {
413  for (uint i = 0; i < this->items; i++) {
414  delete this->data[i];
415  }
416 
417  this->items = 0;
418  }
419 };
420 
422 
423 #endif /* SMALLVEC_TYPE_HPP */
void ErasePreservingOrder(uint pos, uint count=1)
Remove items from the vector while preserving the order of other items.
void Reset()
Remove all items from the list and free allocated memory.
void Clear()
Remove all items from the list.
void Compact()
Compact the list down to the smallest block size boundary.
const T * Begin() const
Get the pointer to the first item (const)
Simple vector template class.
const T & operator[](uint index) const
Get item "number" (const)
const T * End() const
Get the pointer behind the last valid item (const)
T * Append(uint to_add=1)
Append an item and return it.
static void MemMoveT(T *destination, const T *source, size_t num=1)
Type-safe version of memmove().
Definition: mem_func.hpp:38
void Resize(uint num_items)
Set the size of the vector, effectively truncating items from the end or appending uninitialised ones...
SmallVector & operator=(const SmallVector< T, X > &other)
Generic assignment.
uint capacity
The available space for storing items.
uint Length() const
Get the number of items in the list.
static T Align(const T x, uint n)
Return the smallest multiple of n equal or greater than x.
Definition: math_func.hpp:97
bool Contains(const T &item) const
Tests whether a item is present in the vector.
Functions related to the allocation of memory.
SmallVector(const SmallVector &other)
Copy constructor.
Simple vector template class, with automatic delete.
T * data
The pointer to the first item.
static T * ReallocT(T *t_ptr, size_t num_elements)
Simplified reallocation function that allocates the specified number of elements of the given type...
Definition: alloc_func.hpp:113
void Assign(const SmallVector< T, X > &other)
Assign items from other vector.
const T * Find(const T &item) const
Search for the first occurrence of an item.
SmallVector(const SmallVector< T, X > &other)
Generic copy constructor.
AutoFreeSmallVector< char *, 4 > StringList
Type for a list of strings.
Simple vector template class, with automatic free.
void Clear()
Remove all items from the list.
int FindIndex(const T &item) const
Search for the first occurrence of an item.
bool Include(const T &item)
Tests whether a item is present in the vector, and appends it to the end if not.
void Erase(T *item)
Removes given item from this vector.
void Clear()
Remove all items from the list.
static void free(const void *ptr)
Version of the standard free that accepts const pointers.
Definition: depend.cpp:114
const T * Get(uint index) const
Get the pointer to item "number" (const)
Functions related to memory operations.
SmallVector & operator=(const SmallVector &other)
Assignment.
uint items
The number of items stored.