NXWidgets: tnxarray.hxx Source File

NXWidgets 1.19

tnxarray.hxx
Go to the documentation of this file.
1 /****************************************************************************
2 * NxWidgets/libnxwidgets/include/tnxarray.hxx
3 *
4 * Copyright (C) 2012 Gregory Nutt. All rights reserved.
5 * Author: Gregory Nutt <gnutt@nuttx.org>
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
16 * distribution.
17 * 3. Neither the name NuttX, NxWidgets, nor the names of its contributors
18 * me be used to endorse or promote products derived from this software
19 * without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
28 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
29 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32 * POSSIBILITY OF SUCH DAMAGE.
33 *
34 ****************************************************************************
35 *
36 * Portions of this package derive from Woopsi (http://woopsi.org/) and
37 * portions are original efforts. It is difficult to determine at this
38 * point what parts are original efforts and which parts derive from Woopsi.
39 * However, in any event, the work of Antony Dzeryn will be acknowledged
40 * in most NxWidget files. Thanks Antony!
41 *
42 * Copyright (c) 2007-2011, Antony Dzeryn
43 * All rights reserved.
44 *
45 * Redistribution and use in source and binary forms, with or without
46 * modification, are permitted provided that the following conditions are met:
47 *
48 * * Redistributions of source code must retain the above copyright
49 * notice, this list of conditions and the following disclaimer.
50 * * Redistributions in binary form must reproduce the above copyright
51 * notice, this list of conditions and the following disclaimer in the
52 * documentation and/or other materials provided with the distribution.
53 * * Neither the names "Woopsi", "Simian Zombie" nor the
54 * names of its contributors may be used to endorse or promote products
55 * derived from this software without specific prior written permission.
56 *
57 * THIS SOFTWARE IS PROVIDED BY Antony Dzeryn ``AS IS'' AND ANY
58 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
59 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
60 * DISCLAIMED. IN NO EVENT SHALL Antony Dzeryn BE LIABLE FOR ANY
61 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
62 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
63 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
64 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
65 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
66 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
67 *
68 ****************************************************************************/
69
70 #ifndef __INCLUDE_TNXARRAY_HXX
71 #define __INCLUDE_TNXARRAY_HXX
72
73 /****************************************************************************
74 * Included Files
75 ****************************************************************************/
76
77 #include <nuttx/config.h>
78
79 #include <stdint.h>
80 #include <stdbool.h>
81
82 #include "nxconfig.hxx"
83
84 /****************************************************************************
85 * Pre-Processor Definitions
86 ****************************************************************************/
87
88 /****************************************************************************
89 * Implementation Classes
90 ****************************************************************************/
91
92 #if defined(__cplusplus)
93
94 /**
95 * Class providing a dynamic array; that is, an array that will automatically
96 * grow to accommodate new data. It provides a fast way to randomly access
97 * a list of data. Essentially, it provides the most important functionality
98 * of the STL vector class without any of the overhead of including an STL
99 * class.
100 *
101 * If the data to be stored will store a lot of data that will predominantly
102 * be read sequentially, consider using the LinkedList class instead. Resizing
103 * the list is an expensive operation that will occur frequently when filling
104 * the array with large amounts of data. Adding new data to the linked list is
105 * very inexpensive.
106 */
107
108 template <class T>
109 class TNxArray
110 {
111 private:
112 T *m_data; /**< Internal array of data items */
113 int m_size; /**< Number of items in the array */
114 int m_reservedSize; /**< Total size of the array including unpopulated slots */
115
116 /**
117 * Re-allocate the array to this size;
118 */
119
120 void reallocate(const int newSize);
121
122 /**
123 * Resize the array if it is full.
124 */
125
126 void resize(void);
127
128 public:
129
130 /**
131 * Constructor. Creates an un-allocated array. The array will
132 * be allocated when items are added to it or when preallocate()
133 * is called.
134 */
135
136 inline TNxArray();
137
138 /**
139 * Constructor. Creates an allocated array.
140 *
141 *@param initialSize The initial size of the array.
142 */
143
144 inline TNxArray(int initialSize);
145
146 /**
147 * Destructor.
148 */
149
150 inline ~TNxArray();
151
152 /**
153 * Set the initial size of the array. Normally, the array is
154 * unallocated until the first data is pushed into the array.
155 * That works great for stacks and lists. But if you want a
156 * array of unitialized elements, then this method will
157 * preallocate the array for you.
158 *
159 * @return The size of the array.
160 */
161
162 void preallocate(void);
163
164 /**
165 * Get the size of the array.
166 *
167 * @return The size of the array.
168 */
169
170 inline const int size(void) const;
171
172 /**
173 * Add a value to the end of the array.
174 *
175 * @param value The value to add to the array.
176 */
177
178 void push_back(const T &value);
179
180 /**
181 * Insert a value into the array.
182 *
183 * @param index The index to insert into.
184 * @param value The value to insert.
185 */
186
187 void insert(const int index, const T &value);
188
189 /**
190 * Remove the last element from the array.
191 */
192
193 void pop_back(void);
194
195 /**
196 * Erase a single value at the specified index
197 */
198
199 void erase(const int index);
200
201 /**
202 * Get a value at the specified location. Does not perform bounds checking.
203 * @param index The index of the desired value.
204 * @return The value at the specified index.
205 */
206
207 inline T &at(const int index) const;
208
209 /**
210 * Check if the array has any data.
211 * @return True if the array is empty.
212 */
213
214 inline bool empty(void) const;
215
216 /**
217 * Remove all data.
218 */
219
220 void clear();
221
222 /**
223 * Overload the [] operator to allow array-style access.
224 * @param index The index to retrieve.
225 * @return The value at the specified index.
226 */
227
228 T& operator[](const int index) const;
229 };
230
231 template <class T>
232 TNxArray<T>::TNxArray()
233 {
234 // Don't allocate anything until the first data is added to
235 // the array
236
237 m_size = 0; // Number of data items in use
238 m_reservedSize = 0; // Number of data items allocated
239 m_data = (T *)0; // Allocated memory for data items
240 }
241
242 template <class T>
243 TNxArray<T>::TNxArray(int initialSize)
244 {
245 m_size = 0; // Number of data items in use
246 m_reservedSize = 0; // Number of data items allocated
247 m_data = (T *)0; // Allocated memory for data items
248 preallocate(initialSize); // Allocate the initial array
249 }
250
251 template <class T>
252 TNxArray<T>::~TNxArray()
253 {
254 if (m_data)
255 {
256 delete [] m_data;
257 }
258 }
259
260 template <class T>
261 const int TNxArray<T>::size(void) const
262 {
263 return m_size;
264 }
265
266 template <class T>
267 void TNxArray<T>::push_back(const T &value)
268 {
269 // Ensure the array is large enough to hold one more data item
270
271 resize();
272
273 // Add data to array
274
275 m_data[m_size] = value;
276
277 // Remember we've filled a slot
278
279 m_size++;
280 }
281
282 template <class T>
283 void TNxArray<T>::pop_back(void)
284 {
285 if (m_size >= 1)
286 {
287 // We can just reduce the used size of the array, as the value
288 // will get overwritten automatically
289
290 m_size--;
291 }
292 }
293
294 template <class T>
295 void TNxArray<T>::insert(const int index, const T &value)
296 {
297 // Bounds check
298
299 if ((index >= m_size) || (m_size == 0))
300 {
301 push_back(value);
302 return;
303 }
304
305 // Ensure the array is large enough to hold one more data item
306
307 resize();
308
309 // Shift all of the data back one place to make a space for the new data
310
311 for (int i = m_size; i > index; i--)
312 {
313 m_data[i] = m_data[i - 1];
314 }
315
316 // Add data to array
317
318 m_data[index] = value;
319
320 // Remember we've filled a slot
321
322 m_size++;
323 }
324
325 template <class T>
326 void TNxArray<T>::erase(const int index)
327 {
328 // Bounds check
329
330 if (index >= m_size)
331 {
332 return;
333 }
334
335 // Shift all of the data back one place and overwrite the value
336
337 for (int i = index; i < m_size - 1; i++)
338 {
339 m_data[i] = m_data[i + 1];
340 }
341
342 // Remember we've removed a slot
343
344 m_size--;
345 }
346
347 template <class T>
348 void TNxArray<T>::reallocate(const int newSize)
349 {
350 // Do we need to redim the array?
351
352 if (m_reservedSize < newSize)
353 {
354 // Create the new array
355
356 T *newData = new T[newSize];
357
358 // Copy old array contents to new the new array
359
360 for (int i = 0; i < m_reservedSize; i++)
361 {
362 newData[i] = m_data[i];
363 }
364
365 // Delete the old array (if there was one)
366
367 if (m_data)
368 {
369 delete [] m_data;
370 }
371
372 // Update values
373
374 m_data = newData;
375 m_reservedSize = newSize;
376 }
377 }
378
379 template <class T>
380 void TNxArray<T>::resize(void)
381 {
382 // Do we need to redim the array in order to add one more entry?
383
384 if (m_reservedSize == m_size)
385 {
386 // We have filled the array, so resize it
387
388 int newSize = m_reservedSize;
389 #if CONFIG_NXWIDGETS_TNXARRAY_INITIALSIZE != CONFIG_NXWIDGETS_TNXARRAY_SIZEINCREMENT
390 newSize += m_reservedSize ?
391 CONFIG_NXWIDGETS_TNXARRAY_SIZEINCREMENT :
392 CONFIG_NXWIDGETS_TNXARRAY_INITIALSIZE;
393 #else
394 newSize += CONFIG_NXWIDGETS_TNXARRAY_SIZEINCREMENT;
395 #endif
396
397 // Re-allocate the array
398
399 reallocate(newSize);
400 }
401 }
402
403 template <class T>
404 T& TNxArray<T>::at(const int index) const
405 {
406 // What if this is called with index > m_reservedSize? What if
407 // this is called before m_data is allocated? Don't do that!
408
409 return m_data[index];
410 }
411
412 template <class T>
413 bool TNxArray<T>::empty() const
414 {
415 return (m_size == 0);
416 }
417
418 template <class T>
419 T& TNxArray<T>::operator[](const int index) const
420 {
421 // What if this is called with index > m_reservedSize? What if
422 // this is called before m_data is allocated? Don't do that!
423
424 return m_data[index];
425 }
426
427 template <class T>
428 void TNxArray<T>::clear()
429 {
430 // All we need to do is reset the size value
431
432 m_size = 0;
433 }
434
435 #endif // __cplusplus
436
437 #endif // __INCLUDE_TNXARRAY_HXX
TNxArray::resize
void resize(void)
Definition: tnxarray.hxx:380
TNxArray::empty
bool empty(void) const
Definition: tnxarray.hxx:413
TNxArray::~TNxArray
~TNxArray()
Definition: tnxarray.hxx:252
TNxArray::TNxArray
TNxArray()
Definition: tnxarray.hxx:232
TNxArray::pop_back
void pop_back(void)
Definition: tnxarray.hxx:283
TNxArray::operator[]
T & operator[](const int index) const
Definition: tnxarray.hxx:419
TNxArray::erase
void erase(const int index)
Definition: tnxarray.hxx:326
nxconfig.hxx
TNxArray
Definition: tnxarray.hxx:109
TNxArray::clear
void clear()
Definition: tnxarray.hxx:428
TNxArray::push_back
void push_back(const T &value)
Definition: tnxarray.hxx:267
TNxArray::m_data
T * m_data
Definition: tnxarray.hxx:112
TNxArray::reallocate
void reallocate(const int newSize)
Definition: tnxarray.hxx:348
TNxArray::m_reservedSize
int m_reservedSize
Definition: tnxarray.hxx:114
TNxArray::preallocate
void preallocate(void)
TNxArray::size
const int size(void) const
Definition: tnxarray.hxx:261
TNxArray::at
T & at(const int index) const
Definition: tnxarray.hxx:404
TNxArray::insert
void insert(const int index, const T &value)
Definition: tnxarray.hxx:295
TNxArray::m_size
int m_size
Definition: tnxarray.hxx:113