VirtualBox

source: vbox/trunk/include/iprt/cpp/list.h@ 62409

Last change on this file since 62409 was 57944, checked in by vboxsync, 9 years ago

iprt: More doxygen corrections.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 30.0 KB
Line 
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 */
109template <bool G>
110class RTCListGuard;
111
112/**
113 * The default guard which does nothing.
114 */
115template <>
116class RTCListGuard<false>
117{
118public:
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 */
131template <typename T1, typename T2>
132class RTCListHelper
133{
134public:
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 */
157template <typename T1>
158class RTCListHelper<T1, T1*>
159{
160public:
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 */
189template <class T, typename ITYPE, bool MT>
190class 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
204public:
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
794protected:
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
906template <class T, typename ITYPE, bool MT>
907const 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 */
914template <class T, typename ITYPE = typename RTCIf<(sizeof(T) > sizeof(void*)), T*, T>::result>
915class RTCList : public RTCListBase<T, ITYPE, false>
916{
917 /* Traits */
918 typedef RTCListBase<T, ITYPE, false> BASE;
919
920public:
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 */
945template <>
946class RTCList<uint64_t>: public RTCListBase<uint64_t, uint64_t, false>
947{
948 /* Traits */
949 typedef RTCListBase<uint64_t, uint64_t, false> BASE;
950
951public:
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 */
973template <>
974class RTCList<int64_t>: public RTCListBase<int64_t, int64_t, false>
975{
976 /* Traits */
977 typedef RTCListBase<int64_t, int64_t, false> BASE;
978
979public:
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
Note: See TracBrowser for help on using the repository browser.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette