/[svn]/linuxsampler/trunk/src/common/ConstCapacityArray.h
ViewVC logotype

Contents of /linuxsampler/trunk/src/common/ConstCapacityArray.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 3847 - (show annotations) (download) (as text)
Thu Jan 7 12:25:59 2021 UTC (8 weeks, 3 days ago) by schoenebeck
File MIME type: text/x-c++hdr
File size: 6896 byte(s)
ConstCapacityArray class: fix bug in remove() method

1 /*
2 * Copyright (c) 2014 - 2021 Christian Schoenebeck
3 *
4 * http://www.linuxsampler.org
5 *
6 * This file is part of LinuxSampler and released under the same terms.
7 * See README file for details.
8 */
9
10 #ifndef LS_CONSTCAPACITYARRAY_H
11 #define LS_CONSTCAPACITYARRAY_H
12
13 #include <stdlib.h>
14 #include <stdint.h>
15
16 namespace LinuxSampler {
17
18 /**
19 * Very simple container with array implementation which ensures a constant
20 * access time of Theta(1) on individual elements. Internally it uses a
21 * consecutive, dense C array (on heap) where its capacity is defined by the
22 * constructor of this class. That internal array will never be reallocated
23 * during the lifetime of a ConstCapacityArray object and thus C pointers to
24 * elements of this array remain always valid.
25 *
26 * This class has methods to add and remove elements from the array and
27 * "resizing" the array. All those operations are guaranteed to be real-time
28 * safe. When elements are removed from the array, members past the removed
29 * element(s) will be moved towards the array start, to always ensure that
30 * the array is kept dense (without any gaps).
31 */
32 template<typename T>
33 class ConstCapacityArray {
34 public:
35 /**
36 * Create a ConstCapacityArray with the given capacity. The initial
37 * size of the array will be zero. ConstCapacityArray's size can never
38 * grow larger than its capacity defined with the constructor here.
39 *
40 * This constructor <b>must not</b> be called in a real-time context!
41 *
42 * @param capacity - maximum size this object may ever grow
43 */
44 ConstCapacityArray(ssize_t capacity) :
45 m_data(new T[capacity]), m_capacity(capacity), m_size(0) {}
46
47 /**
48 * Destructor. Frees the internal array allocated by this object.
49 *
50 * This destructor <b>must not</b> be called in a real-time context!
51 */
52 ~ConstCapacityArray() {
53 if (m_data) delete [] m_data;
54 }
55
56 /**
57 * Amount of elements this array currently holds. The array's size may
58 * vary between 0 ... capacity() during its lifetime.
59 *
60 * Access time is always constant with Theta(1).
61 *
62 * This method is guaranteed to be real-time safe.
63 *
64 * @see capacity()
65 */
66 inline size_t size() const {
67 return m_size;
68 }
69
70 /**
71 * Maximum size this array may ever grow to in its lifetime.
72 *
73 * Access time is always constant with Theta(1).
74 *
75 * This method is guaranteed to be real-time safe.
76 *
77 * @see size()
78 */
79 inline size_t capacity() const {
80 return m_capacity;
81 }
82
83 /**
84 * Returns true if this array is empty.
85 *
86 * Access time is always constant with Theta(1).
87 *
88 * This method is guaranteed to be real-time safe.
89 */
90 inline bool empty() const {
91 return !m_size;
92 }
93
94 /**
95 * Add a new element to the end of the array. Size is incremented by
96 * one. You cannot add more elements than capacity() reflects.
97 *
98 * This method is guaranteed to be real-time safe.
99 *
100 * @param element - value to be added as new element
101 */
102 inline void append(const T& element) {
103 if (m_size == m_capacity) return; // max. size already exhausted
104 m_data[m_size++] = element;
105 }
106
107 /**
108 * Remove @a count elements from the array at position @a index.
109 * Elements past the removed element(s) will be moved towards the
110 * beginning of the array. So the array always remains dense (without
111 * gaps).
112 *
113 * This method is guaranteed to be real-time safe.
114 *
115 * @param index - position where element(s) shall be removed
116 * @param count - amount of elements to be removed
117 */
118 inline void remove(size_t index, size_t count = 1) {
119 if (index >= m_size)
120 return;
121 // special case: no elements behind the removed elements, so nothing
122 // to move
123 if (index + count >= m_size) {
124 m_size = index;
125 return;
126 }
127 // don't use memmove() here! Since it is not RT safe with all libc
128 // implementations and on all architectures
129 const size_t n = m_size - index - count;
130 for (size_t i = 0; i < n; ++i)
131 m_data[index + i] = m_data[index + i + count];
132 m_size -= count;
133 }
134
135 /**
136 * Returns true in case there is an element with given @a value in this
137 * array
138 *
139 * @param value - value to be searched for
140 */
141 bool contains(const T& value) const {
142 for (size_t i = 0; i < m_size; ++i)
143 if (m_data[i] == value) return true;
144 return false;
145 }
146
147 /**
148 * Searches the array for an element with given index, if found it
149 * returns the element's index, if no such element was found an invalid
150 * index will be returned instead.
151 *
152 * @param value - value to be searched for
153 * @returns index of found element
154 */
155 size_t find(const T& value) const {
156 for (size_t i = 0; i < m_size; ++i)
157 if (m_data[i] == value) return i;
158 return -1;
159 }
160
161 /**
162 * Remove all elements from the array. Size of array will be zero after
163 * this call.
164 *
165 * Access time is always constant with Theta(1).
166 *
167 * This method is guaranteed to be real-time safe.
168 */
169 inline void clear() {
170 m_size = 0;
171 }
172
173 /**
174 * Access element at position @a index (for read/write access).
175 *
176 * Access time is always constant with Theta(1).
177 *
178 * This method is guaranteed to be real-time safe.
179 *
180 * @param index - position of array to access
181 */
182 inline T& operator[](size_t index) {
183 return m_data[index];
184 }
185
186 /**
187 * Access element at position @a index (for read only access).
188 *
189 * Access time is always constant with Theta(1).
190 *
191 * This method is guaranteed to be real-time safe.
192 *
193 * @param index - position of array to access
194 */
195 inline const T& operator[](size_t index) const {
196 return m_data[index];
197 }
198
199 private:
200 T* __restrict const m_data;
201 ssize_t m_capacity;
202 ssize_t m_size;
203 };
204
205 } // namespace LinuxSampler
206
207 #endif // LS_CONSTCAPACITYARRAY_H

  ViewVC Help
Powered by ViewVC