1 | /** @file
|
---|
2 | * IPRT - Generic List Class.
|
---|
3 | */
|
---|
4 |
|
---|
5 | /*
|
---|
6 | * Copyright (C) 2011-2015 Oracle Corporation
|
---|
7 | *
|
---|
8 | * This file is part of VirtualBox Open Source Edition (OSE), as
|
---|
9 | * available from http://www.virtualbox.org. This file is free software;
|
---|
10 | * you can redistribute it and/or modify it under the terms of the GNU
|
---|
11 | * General Public License (GPL) as published by the Free Software
|
---|
12 | * Foundation, in version 2 as it comes in the "COPYING" file of the
|
---|
13 | * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
|
---|
14 | * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
|
---|
15 | *
|
---|
16 | * The contents of this file may alternatively be used under the terms
|
---|
17 | * of the Common Development and Distribution License Version 1.0
|
---|
18 | * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
|
---|
19 | * VirtualBox OSE distribution, in which case the provisions of the
|
---|
20 | * CDDL are applicable instead of those of the GPL.
|
---|
21 | *
|
---|
22 | * You may elect to license modified versions of this file under the
|
---|
23 | * terms and conditions of either the GPL or the CDDL or both.
|
---|
24 | */
|
---|
25 |
|
---|
26 | #ifndef ___iprt_cpp_list_h
|
---|
27 | #define ___iprt_cpp_list_h
|
---|
28 |
|
---|
29 | #include <iprt/cpp/meta.h>
|
---|
30 | #include <iprt/mem.h>
|
---|
31 | #include <iprt/string.h> /* for memcpy */
|
---|
32 | #include <iprt/assert.h>
|
---|
33 |
|
---|
34 | #include <new> /* For std::bad_alloc */
|
---|
35 |
|
---|
36 | /** @defgroup grp_rt_cpp_list C++ List support
|
---|
37 | * @ingroup grp_rt_cpp
|
---|
38 | *
|
---|
39 | * @brief Generic C++ list class support.
|
---|
40 | *
|
---|
41 | * This list classes manage any amount of data in a fast and easy to use way.
|
---|
42 | * They have no dependencies on STL, only on generic memory management methods
|
---|
43 | * of IRPT. This allows list handling in situations where the use of STL
|
---|
44 | * container classes is forbidden.
|
---|
45 | *
|
---|
46 | * Not all of the functionality of STL container classes is implemented. There
|
---|
47 | * are no iterators or any other high level access/modifier methods (e.g.
|
---|
48 | * std::algorithms).
|
---|
49 | *
|
---|
50 | * The implementation is array based which allows fast access to the items.
|
---|
51 | * Appending items is usually also fast, cause the internal array is
|
---|
52 | * preallocated. To minimize the memory overhead, native types (that is
|
---|
53 | * everything smaller then the size of void*) are directly saved in the array.
|
---|
54 | * If bigger types are used (e.g. RTCString) the internal array is an array of
|
---|
55 | * pointers to the objects.
|
---|
56 | *
|
---|
57 | * The size of the internal array will usually not shrink, but grow
|
---|
58 | * automatically. Only certain methods, like RTCList::clear or the "=" operator
|
---|
59 | * will reset any previously allocated memory. You can call
|
---|
60 | * RTCList::setCapacity for manual adjustment. If the size of an new list will
|
---|
61 | * be known, calling the constructor with the necessary capacity will speed up
|
---|
62 | * the insertion of the new items.
|
---|
63 | *
|
---|
64 | * For the full public interface these list classes offer see RTCListBase.
|
---|
65 | *
|
---|
66 | * There are some requirements for the types used which follow:
|
---|
67 | * -# They need a default and a copy constructor.
|
---|
68 | * -# Some methods (e.g. RTCList::contains) need an equal operator.
|
---|
69 | * -# If the type is some complex class (that is, having a constructor which
|
---|
70 | * allocates members on the heap) it has to be greater than sizeof(void*) to
|
---|
71 | * be used correctly. If this is not the case you can manually overwrite the
|
---|
72 | * list behavior. Just add T* as a second parameter to the list template if
|
---|
73 | * your class is called T. Another possibility is to specialize the list for
|
---|
74 | * your target class. See below for more information.
|
---|
75 | *
|
---|
76 | * The native types like int, bool, ptr, ..., are meeting this criteria, so
|
---|
77 | * they are save to use.
|
---|
78 | *
|
---|
79 | * Please note that the return type of some of the getter methods are slightly
|
---|
80 | * different depending on the list type. Native types return the item by value,
|
---|
81 | * items with a size greater than sizeof(void*) by reference. As native types
|
---|
82 | * saved directly in the internal array, returning a reference to them (and
|
---|
83 | * saving them in a reference as well) would make them invalid (or pointing to
|
---|
84 | * a wrong item) when the list is changed in the meanwhile. Returning a
|
---|
85 | * reference for bigger types isn't problematic and makes sure we get out the
|
---|
86 | * best speed of the list. The one exception to this rule is the index
|
---|
87 | * operator[]. This operator always return a reference to make it possible to
|
---|
88 | * use it as a lvalue. Its your responsibility to make sure the list isn't
|
---|
89 | * changed when using the value as reference returned by this operator.
|
---|
90 | *
|
---|
91 | * The list class is reentrant. For a thread-safe variant see RTCMTList.
|
---|
92 | *
|
---|
93 | * Implementation details:
|
---|
94 | * It is possible to specialize any type. This might be necessary to get the
|
---|
95 | * best speed out of the list. Examples are the 64-bit types, which use the
|
---|
96 | * native (no pointers) implementation even on a 32-bit host. Consult the
|
---|
97 | * source code for more details.
|
---|
98 | *
|
---|
99 | * Current specialized implementations:
|
---|
100 | * - int64_t: RTCList<int64_t>
|
---|
101 | * - uint64_t: RTCList<uint64_t>
|
---|
102 | *
|
---|
103 | * @{
|
---|
104 | */
|
---|
105 |
|
---|
106 | /**
|
---|
107 | * The guard definition.
|
---|
108 | */
|
---|
109 | template <bool G>
|
---|
110 | class RTCListGuard;
|
---|
111 |
|
---|
112 | /**
|
---|
113 | * The default guard which does nothing.
|
---|
114 | */
|
---|
115 | template <>
|
---|
116 | class RTCListGuard<false>
|
---|
117 | {
|
---|
118 | public:
|
---|
119 | inline void enterRead() const {}
|
---|
120 | inline void leaveRead() const {}
|
---|
121 | inline void enterWrite() {}
|
---|
122 | inline void leaveWrite() {}
|
---|
123 |
|
---|
124 | /* Define our own new and delete. */
|
---|
125 | RTMEMEF_NEW_AND_DELETE_OPERATORS();
|
---|
126 | };
|
---|
127 |
|
---|
128 | /**
|
---|
129 | * General helper template for managing native values in RTCListBase.
|
---|
130 | */
|
---|
131 | template <typename T1, typename T2>
|
---|
132 | class RTCListHelper
|
---|
133 | {
|
---|
134 | public:
|
---|
135 | static inline void set(T2 *p, size_t i, const T1 &v) { p[i] = v; }
|
---|
136 | static inline T1 & at(T2 *p, size_t i) { return p[i]; }
|
---|
137 | static inline size_t find(T2 *p, const T1 &v, size_t cElements)
|
---|
138 | {
|
---|
139 | size_t i = cElements;
|
---|
140 | while (i-- > 0)
|
---|
141 | if (p[i] == v)
|
---|
142 | return i;
|
---|
143 | return cElements;
|
---|
144 | }
|
---|
145 | static inline void copyTo(T2 *p, T2 *const p1 , size_t iTo, size_t cSize)
|
---|
146 | {
|
---|
147 | if (cSize > 0)
|
---|
148 | memcpy(&p[iTo], &p1[0], sizeof(T1) * cSize);
|
---|
149 | }
|
---|
150 | static inline void erase(T2 * /* p */, size_t /* i */) { /* Nothing to do here. */ }
|
---|
151 | static inline void eraseRange(T2 * /* p */, size_t /* cFrom */, size_t /* cSize */) { /* Nothing to do here. */ }
|
---|
152 | };
|
---|
153 |
|
---|
154 | /**
|
---|
155 | * Specialized helper template for managing pointer values in RTCListBase.
|
---|
156 | */
|
---|
157 | template <typename T1>
|
---|
158 | class RTCListHelper<T1, T1*>
|
---|
159 | {
|
---|
160 | public:
|
---|
161 | static inline void set(T1 **p, size_t i, const T1 &v) { p[i] = new T1(v); }
|
---|
162 | static inline T1 & at(T1 **p, size_t i) { return *p[i]; }
|
---|
163 | static inline size_t find(T1 **p, const T1 &v, size_t cElements)
|
---|
164 | {
|
---|
165 | size_t i = cElements;
|
---|
166 | while (i-- > 0)
|
---|
167 | if (*p[i] == v)
|
---|
168 | return i;
|
---|
169 | return cElements;
|
---|
170 | }
|
---|
171 | static inline void copyTo(T1 **p, T1 **const p1 , size_t iTo, size_t cSize)
|
---|
172 | {
|
---|
173 | for (size_t i = 0; i < cSize; ++i)
|
---|
174 | p[iTo + i] = new T1(*p1[i]);
|
---|
175 | }
|
---|
176 | static inline void erase(T1 **p, size_t i) { delete p[i]; }
|
---|
177 | static inline void eraseRange(T1 **p, size_t iFrom, size_t cItems)
|
---|
178 | {
|
---|
179 | while (cItems-- > 0)
|
---|
180 | delete p[iFrom++];
|
---|
181 | }
|
---|
182 | };
|
---|
183 |
|
---|
184 | /**
|
---|
185 | * This is the base class for all other list classes. It implements the
|
---|
186 | * necessary list functionality in a type independent way and offers the public
|
---|
187 | * list interface to the user.
|
---|
188 | */
|
---|
189 | template <class T, typename ITYPE, bool MT>
|
---|
190 | class RTCListBase
|
---|
191 | {
|
---|
192 | /** @name Traits.
|
---|
193 | *
|
---|
194 | * Defines the return type of most of the getter methods. If the internal
|
---|
195 | * used type is a pointer, we return a reference. If not we return by
|
---|
196 | * value.
|
---|
197 | *
|
---|
198 | * @{
|
---|
199 | */
|
---|
200 | typedef typename RTCIfPtr<ITYPE, T&, T>::result GET_RTYPE;
|
---|
201 | typedef typename RTCIfPtr<ITYPE, const T&, T>::result GET_CRTYPE;
|
---|
202 | /** @} */
|
---|
203 |
|
---|
204 | public:
|
---|
205 | /**
|
---|
206 | * Creates a new list.
|
---|
207 | *
|
---|
208 | * This preallocates @a cCapacity elements within the list.
|
---|
209 | *
|
---|
210 | * @param cCapacity The initial capacity the list has.
|
---|
211 | * @throws std::bad_alloc
|
---|
212 | */
|
---|
213 | RTCListBase(size_t cCapacity = kDefaultCapacity)
|
---|
214 | : m_pArray(0)
|
---|
215 | , m_cElements(0)
|
---|
216 | , m_cCapacity(0)
|
---|
217 | {
|
---|
218 | if (cCapacity > 0)
|
---|
219 | growArray(cCapacity);
|
---|
220 | }
|
---|
221 |
|
---|
222 | /**
|
---|
223 | * Creates a copy of another list.
|
---|
224 | *
|
---|
225 | * The other list will be fully copied and the capacity will be the same as
|
---|
226 | * the size of the other list.
|
---|
227 | *
|
---|
228 | * @param other The list to copy.
|
---|
229 | * @throws std::bad_alloc
|
---|
230 | */
|
---|
231 | RTCListBase(const RTCListBase<T, ITYPE, MT>& other)
|
---|
232 | : m_pArray(0)
|
---|
233 | , m_cElements(0)
|
---|
234 | , m_cCapacity(0)
|
---|
235 | {
|
---|
236 | other.m_guard.enterRead();
|
---|
237 |
|
---|
238 | size_t const cElementsOther = other.m_cElements;
|
---|
239 | resizeArrayNoErase(cElementsOther);
|
---|
240 | RTCListHelper<T, ITYPE>::copyTo(m_pArray, other.m_pArray, 0, cElementsOther);
|
---|
241 | m_cElements = cElementsOther;
|
---|
242 |
|
---|
243 | other.m_guard.leaveRead();
|
---|
244 | }
|
---|
245 |
|
---|
246 | /**
|
---|
247 | * Destructor.
|
---|
248 | */
|
---|
249 | ~RTCListBase()
|
---|
250 | {
|
---|
251 | RTCListHelper<T, ITYPE>::eraseRange(m_pArray, 0, m_cElements);
|
---|
252 | if (m_pArray)
|
---|
253 | {
|
---|
254 | RTMemFree(m_pArray);
|
---|
255 | m_pArray = NULL;
|
---|
256 | }
|
---|
257 | m_cElements = m_cCapacity = 0;
|
---|
258 | }
|
---|
259 |
|
---|
260 | /**
|
---|
261 | * Sets a new capacity within the list.
|
---|
262 | *
|
---|
263 | * If the new capacity is bigger than the old size, it will be simply
|
---|
264 | * preallocated more space for the new items. If the new capacity is
|
---|
265 | * smaller than the previous size, items at the end of the list will be
|
---|
266 | * deleted.
|
---|
267 | *
|
---|
268 | * @param cCapacity The new capacity within the list.
|
---|
269 | * @throws std::bad_alloc
|
---|
270 | */
|
---|
271 | void setCapacity(size_t cCapacity)
|
---|
272 | {
|
---|
273 | m_guard.enterWrite();
|
---|
274 | resizeArray(cCapacity);
|
---|
275 | m_guard.leaveWrite();
|
---|
276 | }
|
---|
277 |
|
---|
278 | /**
|
---|
279 | * Return the current capacity of the list.
|
---|
280 | *
|
---|
281 | * @return The actual capacity.
|
---|
282 | */
|
---|
283 | size_t capacity() const
|
---|
284 | {
|
---|
285 | m_guard.enterRead();
|
---|
286 | size_t cRet = m_cCapacity;
|
---|
287 | m_guard.leaveRead();
|
---|
288 | return cRet;
|
---|
289 | }
|
---|
290 |
|
---|
291 | /**
|
---|
292 | * Check if an list contains any items.
|
---|
293 | *
|
---|
294 | * @return True if there is more than zero items, false otherwise.
|
---|
295 | */
|
---|
296 | bool isEmpty() const
|
---|
297 | {
|
---|
298 | m_guard.enterRead();
|
---|
299 | bool fEmpty = m_cElements == 0;
|
---|
300 | m_guard.leaveRead();
|
---|
301 | return fEmpty;
|
---|
302 | }
|
---|
303 |
|
---|
304 | /**
|
---|
305 | * Return the current count of elements within the list.
|
---|
306 | *
|
---|
307 | * @return The current element count.
|
---|
308 | */
|
---|
309 | size_t size() const
|
---|
310 | {
|
---|
311 | m_guard.enterRead();
|
---|
312 | size_t cRet = m_cElements;
|
---|
313 | m_guard.leaveRead();
|
---|
314 | return cRet;
|
---|
315 | }
|
---|
316 |
|
---|
317 | /**
|
---|
318 | * Inserts an item to the list at position @a i.
|
---|
319 | *
|
---|
320 | * @param i The position of the new item. The must be within or at the
|
---|
321 | * exact end of the list. Indexes specified beyond the end of
|
---|
322 | * the list will be changed to an append() operation and strict
|
---|
323 | * builds will raise an assert.
|
---|
324 | * @param val The new item.
|
---|
325 | * @return a reference to this list.
|
---|
326 | * @throws std::bad_alloc
|
---|
327 | */
|
---|
328 | RTCListBase<T, ITYPE, MT> &insert(size_t i, const T &val)
|
---|
329 | {
|
---|
330 | m_guard.enterWrite();
|
---|
331 |
|
---|
332 | AssertMsgStmt(i <= m_cElements, ("i=%zu m_cElements=%zu\n", i, m_cElements), i = m_cElements);
|
---|
333 |
|
---|
334 | if (m_cElements == m_cCapacity)
|
---|
335 | growArray(m_cCapacity + kDefaultCapacity);
|
---|
336 |
|
---|
337 | memmove(&m_pArray[i + 1], &m_pArray[i], (m_cElements - i) * sizeof(ITYPE));
|
---|
338 | RTCListHelper<T, ITYPE>::set(m_pArray, i, val);
|
---|
339 | ++m_cElements;
|
---|
340 |
|
---|
341 | m_guard.leaveWrite();
|
---|
342 | return *this;
|
---|
343 | }
|
---|
344 |
|
---|
345 | /**
|
---|
346 | * Inserts a list to the list at position @a i.
|
---|
347 | *
|
---|
348 | * @param i The position of the new item. The must be within or at the
|
---|
349 | * exact end of the list. Indexes specified beyond the end of
|
---|
350 | * the list will be changed to an append() operation and strict
|
---|
351 | * builds will raise an assert.
|
---|
352 | * @param other The other list. This MUST not be the same as the destination
|
---|
353 | * list, will assert and return without doing anything if this
|
---|
354 | * happens.
|
---|
355 | * @return a reference to this list.
|
---|
356 | * @throws std::bad_alloc
|
---|
357 | */
|
---|
358 | RTCListBase<T, ITYPE, MT> &insert(size_t i, const RTCListBase<T, ITYPE, MT> &other)
|
---|
359 | {
|
---|
360 | AssertReturn(this != &other, *this);
|
---|
361 |
|
---|
362 | other.m_guard.enterRead();
|
---|
363 | m_guard.enterWrite();
|
---|
364 |
|
---|
365 | AssertMsgStmt(i <= m_cElements, ("i=%zu m_cElements=%zu\n", i, m_cElements), i = m_cElements);
|
---|
366 |
|
---|
367 | size_t cElementsOther = other.m_cElements;
|
---|
368 | if (RT_LIKELY(cElementsOther > 0))
|
---|
369 | {
|
---|
370 | if (m_cCapacity - m_cElements < cElementsOther)
|
---|
371 | growArray(m_cCapacity + (cElementsOther - (m_cCapacity - m_cElements)));
|
---|
372 | if (i < m_cElements)
|
---|
373 | memmove(&m_pArray[i + cElementsOther], &m_pArray[i], (m_cElements - i) * sizeof(ITYPE));
|
---|
374 |
|
---|
375 | RTCListHelper<T, ITYPE>::copyTo(&m_pArray[i], other.m_pArray, 0, cElementsOther);
|
---|
376 | m_cElements += cElementsOther;
|
---|
377 | }
|
---|
378 |
|
---|
379 | m_guard.leaveWrite();
|
---|
380 | other.m_guard.leaveRead();
|
---|
381 | return *this;
|
---|
382 | }
|
---|
383 |
|
---|
384 | /**
|
---|
385 | * Prepend an item to the list.
|
---|
386 | *
|
---|
387 | * @param val The new item.
|
---|
388 | * @return a reference to this list.
|
---|
389 | * @throws std::bad_alloc
|
---|
390 | */
|
---|
391 | RTCListBase<T, ITYPE, MT> &prepend(const T &val)
|
---|
392 | {
|
---|
393 | return insert(0, val);
|
---|
394 | }
|
---|
395 |
|
---|
396 | /**
|
---|
397 | * Prepend a list of type T to the list.
|
---|
398 | *
|
---|
399 | * @param other The list to prepend.
|
---|
400 | * @return a reference to this list.
|
---|
401 | * @throws std::bad_alloc
|
---|
402 | */
|
---|
403 | RTCListBase<T, ITYPE, MT> &prepend(const RTCListBase<T, ITYPE, MT> &other)
|
---|
404 | {
|
---|
405 | return insert(0, other);
|
---|
406 | }
|
---|
407 |
|
---|
408 | /**
|
---|
409 | * Append an item to the list.
|
---|
410 | *
|
---|
411 | * @param val The new item.
|
---|
412 | * @return a reference to this list.
|
---|
413 | * @throws std::bad_alloc
|
---|
414 | */
|
---|
415 | RTCListBase<T, ITYPE, MT> &append(const T &val)
|
---|
416 | {
|
---|
417 | m_guard.enterWrite();
|
---|
418 | if (m_cElements == m_cCapacity)
|
---|
419 | growArray(m_cCapacity + kDefaultCapacity);
|
---|
420 | RTCListHelper<T, ITYPE>::set(m_pArray, m_cElements, val);
|
---|
421 | ++m_cElements;
|
---|
422 | m_guard.leaveWrite();
|
---|
423 |
|
---|
424 | return *this;
|
---|
425 | }
|
---|
426 |
|
---|
427 | /**
|
---|
428 | * Append a list of type T to the list.
|
---|
429 | *
|
---|
430 | * @param other The list to append. Must not be the same as the destination
|
---|
431 | * list, will assert and return without doing anything.
|
---|
432 | * @return a reference to this list.
|
---|
433 | * @throws std::bad_alloc
|
---|
434 | */
|
---|
435 | RTCListBase<T, ITYPE, MT> &append(const RTCListBase<T, ITYPE, MT> &other)
|
---|
436 | {
|
---|
437 | AssertReturn(this != &other, *this);
|
---|
438 |
|
---|
439 | other.m_guard.enterRead();
|
---|
440 | m_guard.enterWrite();
|
---|
441 |
|
---|
442 | insert(m_cElements, other);
|
---|
443 |
|
---|
444 | m_guard.leaveWrite();
|
---|
445 | other.m_guard.leaveRead();
|
---|
446 | return *this;
|
---|
447 | }
|
---|
448 |
|
---|
449 | /**
|
---|
450 | * Copy the items of the other list into this list.
|
---|
451 | *
|
---|
452 | * All previous items of this list are deleted.
|
---|
453 | *
|
---|
454 | * @param other The list to copy.
|
---|
455 | * @return a reference to this list.
|
---|
456 | */
|
---|
457 | RTCListBase<T, ITYPE, MT> &operator=(const RTCListBase<T, ITYPE, MT>& other)
|
---|
458 | {
|
---|
459 | /* Prevent self assignment */
|
---|
460 | if (RT_LIKELY(this != &other))
|
---|
461 | {
|
---|
462 |
|
---|
463 | other.m_guard.enterRead();
|
---|
464 | m_guard.enterWrite();
|
---|
465 |
|
---|
466 | /* Delete all items. */
|
---|
467 | RTCListHelper<T, ITYPE>::eraseRange(m_pArray, 0, m_cElements);
|
---|
468 |
|
---|
469 | /* Need we to realloc memory. */
|
---|
470 | if (other.m_cElements != m_cCapacity)
|
---|
471 | resizeArrayNoErase(other.m_cElements);
|
---|
472 | m_cElements = other.m_cElements;
|
---|
473 |
|
---|
474 | /* Copy new items. */
|
---|
475 | RTCListHelper<T, ITYPE>::copyTo(m_pArray, other.m_pArray, 0, other.m_cElements);
|
---|
476 |
|
---|
477 | m_guard.leaveWrite();
|
---|
478 | other.m_guard.leaveRead();
|
---|
479 | }
|
---|
480 | return *this;
|
---|
481 | }
|
---|
482 |
|
---|
483 | /**
|
---|
484 | * Replace an item in the list.
|
---|
485 | *
|
---|
486 | * @param i The position of the item to replace. If this is out of range,
|
---|
487 | * the request will be ignored, strict builds will assert.
|
---|
488 | * @param val The new value.
|
---|
489 | * @return a reference to this list.
|
---|
490 | */
|
---|
491 | RTCListBase<T, ITYPE, MT> &replace(size_t i, const T &val)
|
---|
492 | {
|
---|
493 | m_guard.enterWrite();
|
---|
494 |
|
---|
495 | if (i < m_cElements)
|
---|
496 | {
|
---|
497 | RTCListHelper<T, ITYPE>::erase(m_pArray, i);
|
---|
498 | RTCListHelper<T, ITYPE>::set(m_pArray, i, val);
|
---|
499 | }
|
---|
500 | else
|
---|
501 | AssertMsgFailed(("i=%zu m_cElements=%zu\n", i, m_cElements));
|
---|
502 |
|
---|
503 | m_guard.leaveWrite();
|
---|
504 | return *this;
|
---|
505 | }
|
---|
506 |
|
---|
507 | /**
|
---|
508 | * Return the first item as constant object.
|
---|
509 | *
|
---|
510 | * @return A reference or pointer to the first item.
|
---|
511 | *
|
---|
512 | * @note No boundary checks are done. Make sure there is at least one
|
---|
513 | * element.
|
---|
514 | */
|
---|
515 | GET_CRTYPE first() const
|
---|
516 | {
|
---|
517 | m_guard.enterRead();
|
---|
518 | Assert(m_cElements > 0);
|
---|
519 | GET_CRTYPE res = RTCListHelper<T, ITYPE>::at(m_pArray, 0);
|
---|
520 | m_guard.leaveRead();
|
---|
521 | return res;
|
---|
522 | }
|
---|
523 |
|
---|
524 | /**
|
---|
525 | * Return the first item.
|
---|
526 | *
|
---|
527 | * @return A reference or pointer to the first item.
|
---|
528 | *
|
---|
529 | * @note No boundary checks are done. Make sure there is at least one
|
---|
530 | * element.
|
---|
531 | */
|
---|
532 | GET_RTYPE first()
|
---|
533 | {
|
---|
534 | m_guard.enterRead();
|
---|
535 | Assert(m_cElements > 0);
|
---|
536 | GET_RTYPE res = RTCListHelper<T, ITYPE>::at(m_pArray, 0);
|
---|
537 | m_guard.leaveRead();
|
---|
538 | return res;
|
---|
539 | }
|
---|
540 |
|
---|
541 | /**
|
---|
542 | * Return the last item as constant object.
|
---|
543 | *
|
---|
544 | * @return A reference or pointer to the last item.
|
---|
545 | *
|
---|
546 | * @note No boundary checks are done. Make sure there is at least one
|
---|
547 | * element.
|
---|
548 | */
|
---|
549 | GET_CRTYPE last() const
|
---|
550 | {
|
---|
551 | m_guard.enterRead();
|
---|
552 | Assert(m_cElements > 0);
|
---|
553 | GET_CRTYPE res = RTCListHelper<T, ITYPE>::at(m_pArray, m_cElements - 1);
|
---|
554 | m_guard.leaveRead();
|
---|
555 | return res;
|
---|
556 | }
|
---|
557 |
|
---|
558 | /**
|
---|
559 | * Return the last item.
|
---|
560 | *
|
---|
561 | * @return A reference or pointer to the last item.
|
---|
562 | *
|
---|
563 | * @note No boundary checks are done. Make sure there is at least one
|
---|
564 | * element.
|
---|
565 | */
|
---|
566 | GET_RTYPE last()
|
---|
567 | {
|
---|
568 | m_guard.enterRead();
|
---|
569 | Assert(m_cElements > 0);
|
---|
570 | GET_RTYPE res = RTCListHelper<T, ITYPE>::at(m_pArray, m_cElements - 1);
|
---|
571 | m_guard.leaveRead();
|
---|
572 | return res;
|
---|
573 | }
|
---|
574 |
|
---|
575 | /**
|
---|
576 | * Return the item at position @a i as constant object.
|
---|
577 | *
|
---|
578 | * @param i The position of the item to return. This better not be out of
|
---|
579 | * bounds, however should it be the last element of the array
|
---|
580 | * will be return and strict builds will raise an assertion.
|
---|
581 | * Should the array be empty, a crash is very likely.
|
---|
582 | * @return The item at position @a i.
|
---|
583 | */
|
---|
584 | GET_CRTYPE at(size_t i) const
|
---|
585 | {
|
---|
586 | m_guard.enterRead();
|
---|
587 | AssertMsgStmt(i < m_cElements, ("i=%zu m_cElements=%zu\n", i, m_cElements), i = m_cElements - 1);
|
---|
588 | GET_CRTYPE res = RTCListHelper<T, ITYPE>::at(m_pArray, i);
|
---|
589 | m_guard.leaveRead();
|
---|
590 | return res;
|
---|
591 | }
|
---|
592 |
|
---|
593 | /**
|
---|
594 | * Return the item at position @a i.
|
---|
595 | *
|
---|
596 | * @param i The position of the item to return. This better not be out of
|
---|
597 | * bounds, however should it be the last element of the array
|
---|
598 | * will be return and strict builds will raise an assertion.
|
---|
599 | * Should the array be empty, a crash is very likely.
|
---|
600 | * @return The item at position @a i.
|
---|
601 | */
|
---|
602 | GET_RTYPE at(size_t i)
|
---|
603 | {
|
---|
604 | m_guard.enterRead();
|
---|
605 | AssertMsgStmt(i < m_cElements, ("i=%zu m_cElements=%zu\n", i, m_cElements), i = m_cElements - 1);
|
---|
606 | GET_RTYPE res = RTCListHelper<T, ITYPE>::at(m_pArray, i);
|
---|
607 | m_guard.leaveRead();
|
---|
608 | return res;
|
---|
609 | }
|
---|
610 |
|
---|
611 | /**
|
---|
612 | * Return the item at position @a i as mutable reference.
|
---|
613 | *
|
---|
614 | * @param i The position of the item to return. This better not be out of
|
---|
615 | * bounds, however should it be the last element of the array
|
---|
616 | * will be return and strict builds will raise an assertion.
|
---|
617 | * Should the array be empty, a crash is very likely.
|
---|
618 | * @return The item at position @a i.
|
---|
619 | */
|
---|
620 | T &operator[](size_t i)
|
---|
621 | {
|
---|
622 | m_guard.enterRead();
|
---|
623 | AssertMsgStmt(i < m_cElements, ("i=%zu m_cElements=%zu\n", i, m_cElements), i = m_cElements - 1);
|
---|
624 | T &res = RTCListHelper<T, ITYPE>::at(m_pArray, i);
|
---|
625 | m_guard.leaveRead();
|
---|
626 | return res;
|
---|
627 | }
|
---|
628 |
|
---|
629 | /**
|
---|
630 | * Return the item at position @a i or default value if out of range.
|
---|
631 | *
|
---|
632 | * @param i The position of the item to return.
|
---|
633 | * @return The item at position @a i or default value.
|
---|
634 | */
|
---|
635 | T value(size_t i) const
|
---|
636 | {
|
---|
637 | m_guard.enterRead();
|
---|
638 | if (RT_LIKELY(i < m_cElements))
|
---|
639 | {
|
---|
640 | T res = RTCListHelper<T, ITYPE>::at(m_pArray, i);
|
---|
641 | m_guard.leaveRead();
|
---|
642 | return res;
|
---|
643 | }
|
---|
644 | m_guard.leaveRead();
|
---|
645 | return T();
|
---|
646 | }
|
---|
647 |
|
---|
648 | /**
|
---|
649 | * Return the item at position @a i, or @a defaultVal if out of range.
|
---|
650 | *
|
---|
651 | * @param i The position of the item to return.
|
---|
652 | * @param defaultVal The value to return in case @a i is invalid.
|
---|
653 | * @return The item at position @a i or @a defaultVal.
|
---|
654 | */
|
---|
655 | T value(size_t i, const T &defaultVal) const
|
---|
656 | {
|
---|
657 | m_guard.enterRead();
|
---|
658 | if (RT_LIKELY(i < m_cElements))
|
---|
659 | {
|
---|
660 | T res = RTCListHelper<T, ITYPE>::at(m_pArray, i);
|
---|
661 | m_guard.leaveRead();
|
---|
662 | return res;
|
---|
663 | }
|
---|
664 | m_guard.leaveRead();
|
---|
665 | return defaultVal;
|
---|
666 | }
|
---|
667 |
|
---|
668 | /**
|
---|
669 | * Check if @a val is contained in the array.
|
---|
670 | *
|
---|
671 | * @param val The value to check for.
|
---|
672 | * @return true if it is found, false otherwise.
|
---|
673 | */
|
---|
674 | bool contains(const T &val) const
|
---|
675 | {
|
---|
676 | m_guard.enterRead();
|
---|
677 | bool fRc = RTCListHelper<T, ITYPE>::find(m_pArray, val, m_cElements) < m_cElements;
|
---|
678 | m_guard.leaveRead();
|
---|
679 | return fRc;
|
---|
680 | }
|
---|
681 |
|
---|
682 | /**
|
---|
683 | * Remove the first item.
|
---|
684 | *
|
---|
685 | * @note You should make sure the list isn't empty. Strict builds will assert.
|
---|
686 | * The other builds will quietly ignore the request.
|
---|
687 | */
|
---|
688 | void removeFirst()
|
---|
689 | {
|
---|
690 | removeAt(0);
|
---|
691 | }
|
---|
692 |
|
---|
693 | /**
|
---|
694 | * Remove the last item.
|
---|
695 | *
|
---|
696 | * @note You should make sure the list isn't empty. Strict builds will assert.
|
---|
697 | * The other builds will quietly ignore the request.
|
---|
698 | */
|
---|
699 | void removeLast()
|
---|
700 | {
|
---|
701 | m_guard.enterWrite();
|
---|
702 | removeAtLocked(m_cElements - 1);
|
---|
703 | m_guard.leaveWrite();
|
---|
704 | }
|
---|
705 |
|
---|
706 | /**
|
---|
707 | * Remove the item at position @a i.
|
---|
708 | *
|
---|
709 | * @param i The position of the item to remove. Out of bounds values will
|
---|
710 | * be ignored and an assertion will be raised in strict builds.
|
---|
711 | */
|
---|
712 | void removeAt(size_t i)
|
---|
713 | {
|
---|
714 | m_guard.enterWrite();
|
---|
715 | removeAtLocked(i);
|
---|
716 | m_guard.leaveWrite();
|
---|
717 | }
|
---|
718 |
|
---|
719 | /**
|
---|
720 | * Remove a range of items from the list.
|
---|
721 | *
|
---|
722 | * @param iStart The start position of the items to remove.
|
---|
723 | * @param iEnd The end position of the items to remove (excluded).
|
---|
724 | */
|
---|
725 | void removeRange(size_t iStart, size_t iEnd)
|
---|
726 | {
|
---|
727 | AssertReturnVoid(iStart <= iEnd);
|
---|
728 | m_guard.enterWrite();
|
---|
729 |
|
---|
730 | AssertMsgStmt(iEnd <= m_cElements, ("iEnd=%zu m_cElements=%zu\n", iEnd, m_cElements), iEnd = m_cElements);
|
---|
731 | AssertMsgStmt(iStart < m_cElements, ("iStart=%zu m_cElements=%zu\n", iStart, m_cElements), iStart = m_cElements);
|
---|
732 | size_t const cElements = iEnd - iStart;
|
---|
733 | if (cElements > 0)
|
---|
734 | {
|
---|
735 | Assert(iStart < m_cElements);
|
---|
736 | RTCListHelper<T, ITYPE>::eraseRange(m_pArray, iStart, cElements);
|
---|
737 | if (m_cElements > iEnd)
|
---|
738 | memmove(&m_pArray[iStart], &m_pArray[iEnd], (m_cElements - iEnd) * sizeof(ITYPE));
|
---|
739 | m_cElements -= cElements;
|
---|
740 | }
|
---|
741 |
|
---|
742 | m_guard.leaveWrite();
|
---|
743 | }
|
---|
744 |
|
---|
745 | /**
|
---|
746 | * Delete all items in the list.
|
---|
747 | */
|
---|
748 | void clear()
|
---|
749 | {
|
---|
750 | m_guard.enterWrite();
|
---|
751 |
|
---|
752 | /* Values cleanup */
|
---|
753 | RTCListHelper<T, ITYPE>::eraseRange(m_pArray, 0, m_cElements);
|
---|
754 | if (m_cElements != kDefaultCapacity)
|
---|
755 | resizeArrayNoErase(kDefaultCapacity);
|
---|
756 | m_cElements = 0;
|
---|
757 |
|
---|
758 | m_guard.leaveWrite();
|
---|
759 | }
|
---|
760 |
|
---|
761 | /**
|
---|
762 | * Return the raw array.
|
---|
763 | *
|
---|
764 | * For native types this is a pointer to continuous memory of the items. For
|
---|
765 | * pointer types this is a continuous memory of pointers to the items.
|
---|
766 | *
|
---|
767 | * @warning If you change anything in the underlaying list, this memory
|
---|
768 | * will very likely become invalid. So take care when using this
|
---|
769 | * method and better try to avoid using it.
|
---|
770 | *
|
---|
771 | * @returns the raw memory.
|
---|
772 | */
|
---|
773 | ITYPE *raw() const
|
---|
774 | {
|
---|
775 | m_guard.enterRead();
|
---|
776 | ITYPE *pRet = m_pArray;
|
---|
777 | m_guard.leaveRead();
|
---|
778 | return pRet;
|
---|
779 | }
|
---|
780 |
|
---|
781 | RTCListBase<T, ITYPE, MT> &operator<<(const T &val)
|
---|
782 | {
|
---|
783 | return append(val);
|
---|
784 | }
|
---|
785 |
|
---|
786 | /* Define our own new and delete. */
|
---|
787 | RTMEMEF_NEW_AND_DELETE_OPERATORS();
|
---|
788 |
|
---|
789 | /**
|
---|
790 | * The default capacity of the list. This is also used as grow factor.
|
---|
791 | */
|
---|
792 | static const size_t kDefaultCapacity;
|
---|
793 |
|
---|
794 | protected:
|
---|
795 |
|
---|
796 | /**
|
---|
797 | * Generic resizes the array, surplus elements are erased.
|
---|
798 | *
|
---|
799 | * @param cElementsNew The new array size.
|
---|
800 | * @throws std::bad_alloc.
|
---|
801 | */
|
---|
802 | void resizeArray(size_t cElementsNew)
|
---|
803 | {
|
---|
804 | /* Same size? */
|
---|
805 | if (cElementsNew == m_cCapacity)
|
---|
806 | return;
|
---|
807 |
|
---|
808 | /* If we get smaller we have to delete some of the objects at the end
|
---|
809 | of the list. */
|
---|
810 | if ( cElementsNew < m_cElements
|
---|
811 | && m_pArray)
|
---|
812 | RTCListHelper<T, ITYPE>::eraseRange(m_pArray, cElementsNew, m_cElements - cElementsNew);
|
---|
813 |
|
---|
814 | resizeArrayNoErase(cElementsNew);
|
---|
815 | }
|
---|
816 |
|
---|
817 | /**
|
---|
818 | * Resizes the array without doing the erase() thing on surplus elements.
|
---|
819 | *
|
---|
820 | * @param cElementsNew The new array size.
|
---|
821 | * @throws std::bad_alloc.
|
---|
822 | */
|
---|
823 | void resizeArrayNoErase(size_t cElementsNew)
|
---|
824 | {
|
---|
825 | /* Same size? */
|
---|
826 | if (cElementsNew == m_cCapacity)
|
---|
827 | return;
|
---|
828 |
|
---|
829 | /* Resize the array. */
|
---|
830 | if (cElementsNew > 0)
|
---|
831 | {
|
---|
832 | void *pvNew = RTMemRealloc(m_pArray, sizeof(ITYPE) * cElementsNew);
|
---|
833 | if (!pvNew)
|
---|
834 | {
|
---|
835 | #ifdef RT_EXCEPTIONS_ENABLED
|
---|
836 | throw std::bad_alloc();
|
---|
837 | #endif
|
---|
838 | return;
|
---|
839 | }
|
---|
840 | m_pArray = static_cast<ITYPE*>(pvNew);
|
---|
841 | }
|
---|
842 | /* If we get zero we delete the array it self. */
|
---|
843 | else if (m_pArray)
|
---|
844 | {
|
---|
845 | RTMemFree(m_pArray);
|
---|
846 | m_pArray = NULL;
|
---|
847 | }
|
---|
848 |
|
---|
849 | m_cCapacity = cElementsNew;
|
---|
850 | if (m_cElements > cElementsNew)
|
---|
851 | m_cElements = cElementsNew;
|
---|
852 | }
|
---|
853 |
|
---|
854 | /**
|
---|
855 | * Special realloc method which require that the array will grow.
|
---|
856 | *
|
---|
857 | * @param cElementsNew The new array size.
|
---|
858 | * @throws std::bad_alloc.
|
---|
859 | * @note No boundary checks are done!
|
---|
860 | */
|
---|
861 | void growArray(size_t cElementsNew)
|
---|
862 | {
|
---|
863 | Assert(cElementsNew > m_cCapacity);
|
---|
864 | void *pvNew = RTMemRealloc(m_pArray, sizeof(ITYPE) * cElementsNew);
|
---|
865 | if (pvNew)
|
---|
866 | {
|
---|
867 | m_cCapacity = cElementsNew;
|
---|
868 | m_pArray = static_cast<ITYPE*>(pvNew);
|
---|
869 | }
|
---|
870 | else
|
---|
871 | {
|
---|
872 | #ifdef RT_EXCEPTIONS_ENABLED
|
---|
873 | throw std::bad_alloc();
|
---|
874 | #endif
|
---|
875 | }
|
---|
876 | }
|
---|
877 |
|
---|
878 | /**
|
---|
879 | * Remove the item at position @a i.
|
---|
880 | *
|
---|
881 | * @param i The position of the item to remove. Out of bounds values will
|
---|
882 | * be ignored and an assertion will be raised in strict builds.
|
---|
883 | * @remarks
|
---|
884 | */
|
---|
885 | void removeAtLocked(size_t i)
|
---|
886 | {
|
---|
887 | AssertMsgReturnVoid(i < m_cElements, ("i=%zu m_cElements=%zu\n", i, m_cElements));
|
---|
888 |
|
---|
889 | RTCListHelper<T, ITYPE>::erase(m_pArray, i);
|
---|
890 | if (i < m_cElements - 1)
|
---|
891 | memmove(&m_pArray[i], &m_pArray[i + 1], (m_cElements - i - 1) * sizeof(ITYPE));
|
---|
892 | --m_cElements;
|
---|
893 | }
|
---|
894 |
|
---|
895 |
|
---|
896 | /** The internal list array. */
|
---|
897 | ITYPE *m_pArray;
|
---|
898 | /** The current count of items in use. */
|
---|
899 | size_t m_cElements;
|
---|
900 | /** The current capacity of the internal array. */
|
---|
901 | size_t m_cCapacity;
|
---|
902 | /** The guard used to serialize the access to the items. */
|
---|
903 | RTCListGuard<MT> m_guard;
|
---|
904 | };
|
---|
905 |
|
---|
906 | template <class T, typename ITYPE, bool MT>
|
---|
907 | const size_t RTCListBase<T, ITYPE, MT>::kDefaultCapacity = 10;
|
---|
908 |
|
---|
909 | /**
|
---|
910 | * Template class which automatically determines the type of list to use.
|
---|
911 | *
|
---|
912 | * @see RTCListBase
|
---|
913 | */
|
---|
914 | template <class T, typename ITYPE = typename RTCIf<(sizeof(T) > sizeof(void*)), T*, T>::result>
|
---|
915 | class RTCList : public RTCListBase<T, ITYPE, false>
|
---|
916 | {
|
---|
917 | /* Traits */
|
---|
918 | typedef RTCListBase<T, ITYPE, false> BASE;
|
---|
919 |
|
---|
920 | public:
|
---|
921 | /**
|
---|
922 | * Creates a new list.
|
---|
923 | *
|
---|
924 | * This preallocates @a cCapacity elements within the list.
|
---|
925 | *
|
---|
926 | * @param cCapacity The initial capacity the list has.
|
---|
927 | * @throws std::bad_alloc
|
---|
928 | */
|
---|
929 | RTCList(size_t cCapacity = BASE::kDefaultCapacity)
|
---|
930 | : BASE(cCapacity) {}
|
---|
931 |
|
---|
932 | RTCList(const BASE &other)
|
---|
933 | : BASE(other) {}
|
---|
934 |
|
---|
935 | /* Define our own new and delete. */
|
---|
936 | RTMEMEF_NEW_AND_DELETE_OPERATORS();
|
---|
937 | };
|
---|
938 |
|
---|
939 | /**
|
---|
940 | * Specialized class for using the native type list for unsigned 64-bit
|
---|
941 | * values even on a 32-bit host.
|
---|
942 | *
|
---|
943 | * @see RTCListBase
|
---|
944 | */
|
---|
945 | template <>
|
---|
946 | class RTCList<uint64_t>: public RTCListBase<uint64_t, uint64_t, false>
|
---|
947 | {
|
---|
948 | /* Traits */
|
---|
949 | typedef RTCListBase<uint64_t, uint64_t, false> BASE;
|
---|
950 |
|
---|
951 | public:
|
---|
952 | /**
|
---|
953 | * Creates a new list.
|
---|
954 | *
|
---|
955 | * This preallocates @a cCapacity elements within the list.
|
---|
956 | *
|
---|
957 | * @param cCapacity The initial capacity the list has.
|
---|
958 | * @throws std::bad_alloc
|
---|
959 | */
|
---|
960 | RTCList(size_t cCapacity = BASE::kDefaultCapacity)
|
---|
961 | : BASE(cCapacity) {}
|
---|
962 |
|
---|
963 | /* Define our own new and delete. */
|
---|
964 | RTMEMEF_NEW_AND_DELETE_OPERATORS();
|
---|
965 | };
|
---|
966 |
|
---|
967 | /**
|
---|
968 | * Specialized class for using the native type list for signed 64-bit
|
---|
969 | * values even on a 32-bit host.
|
---|
970 | *
|
---|
971 | * @see RTCListBase
|
---|
972 | */
|
---|
973 | template <>
|
---|
974 | class RTCList<int64_t>: public RTCListBase<int64_t, int64_t, false>
|
---|
975 | {
|
---|
976 | /* Traits */
|
---|
977 | typedef RTCListBase<int64_t, int64_t, false> BASE;
|
---|
978 |
|
---|
979 | public:
|
---|
980 | /**
|
---|
981 | * Creates a new list.
|
---|
982 | *
|
---|
983 | * This preallocates @a cCapacity elements within the list.
|
---|
984 | *
|
---|
985 | * @param cCapacity The initial capacity the list has.
|
---|
986 | * @throws std::bad_alloc
|
---|
987 | */
|
---|
988 | RTCList(size_t cCapacity = BASE::kDefaultCapacity)
|
---|
989 | : BASE(cCapacity) {}
|
---|
990 |
|
---|
991 | /* Define our own new and delete. */
|
---|
992 | RTMEMEF_NEW_AND_DELETE_OPERATORS();
|
---|
993 | };
|
---|
994 |
|
---|
995 | /** @} */
|
---|
996 |
|
---|
997 | #endif /* !___iprt_cpp_list_h */
|
---|
998 |
|
---|