OpenTTD
smallvec_type.hpp
Go to the documentation of this file.
1 /* $Id$ */
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 
166  inline T *Insert(T *item)
167  {
168  assert(item >= this->Begin() && item <= this->End());
169 
170  size_t to_move = this->End() - item;
171  size_t start = item - this->Begin();
172 
173  this->Append();
174  if (to_move > 0) MemMoveT(this->Begin() + start + 1, this->Begin() + start, to_move);
175  return this->Begin() + start;
176  }
177 
184  inline const T *Find(const T &item) const
185  {
186  const T *pos = this->Begin();
187  const T *end = this->End();
188  while (pos != end && *pos != item) pos++;
189  return pos;
190  }
191 
198  inline T *Find(const T &item)
199  {
200  T *pos = this->Begin();
201  const T *end = this->End();
202  while (pos != end && *pos != item) pos++;
203  return pos;
204  }
205 
212  inline int FindIndex(const T &item) const
213  {
214  int index = 0;
215  const T *pos = this->Begin();
216  const T *end = this->End();
217  while (pos != end && *pos != item) {
218  pos++;
219  index++;
220  }
221  return pos == end ? -1 : index;
222  }
223 
230  inline bool Contains(const T &item) const
231  {
232  return this->Find(item) != this->End();
233  }
234 
240  inline void Erase(T *item)
241  {
242  assert(item >= this->Begin() && item < this->End());
243  *item = this->data[--this->items];
244  }
245 
251  void ErasePreservingOrder(uint pos, uint count = 1)
252  {
253  ErasePreservingOrder(this->data + pos, count);
254  }
255 
261  inline void ErasePreservingOrder(T *item, uint count = 1)
262  {
263  if (count == 0) return;
264  assert(item >= this->Begin());
265  assert(item + count <= this->End());
266 
267  this->items -= count;
268  ptrdiff_t to_move = this->End() - item;
269  if (to_move > 0) MemMoveT(item, item + count, to_move);
270  }
271 
278  inline bool Include(const T &item)
279  {
280  bool is_member = this->Contains(item);
281  if (!is_member) *this->Append() = item;
282  return is_member;
283  }
284 
290  inline uint Length() const
291  {
292  return this->items;
293  }
294 
300  inline const T *Begin() const
301  {
302  return this->data;
303  }
304 
310  inline T *Begin()
311  {
312  return this->data;
313  }
314 
320  inline const T *End() const
321  {
322  return &this->data[this->items];
323  }
324 
330  inline T *End()
331  {
332  return &this->data[this->items];
333  }
334 
341  inline const T *Get(uint index) const
342  {
343  /* Allow access to the 'first invalid' item */
344  assert(index <= this->items);
345  return &this->data[index];
346  }
347 
354  inline T *Get(uint index)
355  {
356  /* Allow access to the 'first invalid' item */
357  assert(index <= this->items);
358  return &this->data[index];
359  }
360 
367  inline const T &operator[](uint index) const
368  {
369  assert(index < this->items);
370  return this->data[index];
371  }
372 
379  inline T &operator[](uint index)
380  {
381  assert(index < this->items);
382  return this->data[index];
383  }
384 };
385 
386 
397 template <typename T, uint S>
398 class AutoFreeSmallVector : public SmallVector<T, S> {
399 public:
401  {
402  this->Clear();
403  }
404 
408  inline void Clear()
409  {
410  for (uint i = 0; i < this->items; i++) {
411  free(this->data[i]);
412  }
413 
414  this->items = 0;
415  }
416 };
417 
428 template <typename T, uint S>
429 class AutoDeleteSmallVector : public SmallVector<T, S> {
430 public:
432  {
433  this->Clear();
434  }
435 
439  inline void Clear()
440  {
441  for (uint i = 0; i < this->items; i++) {
442  delete this->data[i];
443  }
444 
445  this->items = 0;
446  }
447 };
448 
450 
451 #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.
void ErasePreservingOrder(T *item, uint count=1)
Remove items from the vector while preserving the order of other items.
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)
T * Insert(T *item)
Insert a new item at a specific position into the vector, moving all following items.
Functions related to memory operations.
SmallVector & operator=(const SmallVector &other)
Assignment.
uint items
The number of items stored.