1 |
schoenebeck |
2630 |
/* |
2 |
schoenebeck |
3557 |
* Copyright (c) 2014 - 2019 Christian Schoenebeck |
3 |
schoenebeck |
2630 |
* |
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 |
schoenebeck |
3557 |
ConstCapacityArray(ssize_t capacity) : |
45 |
schoenebeck |
2630 |
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 |
schoenebeck |
3557 |
inline size_t size() const { |
67 |
schoenebeck |
2630 |
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 |
schoenebeck |
3557 |
inline size_t capacity() const { |
80 |
schoenebeck |
2630 |
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 |
schoenebeck |
3557 |
inline void remove(size_t index, size_t count = 1) { |
119 |
schoenebeck |
2630 |
if (index >= m_size || index + count > m_size) |
120 |
|
|
return; |
121 |
|
|
// don't use memmove() here! Since it is not RT safe with all libc |
122 |
|
|
// implementations and on all architectures |
123 |
schoenebeck |
3557 |
for (size_t i = 0; i < count; ++i) |
124 |
schoenebeck |
2630 |
m_data[index + i] = m_data[index + i + count]; |
125 |
|
|
m_size -= count; |
126 |
|
|
} |
127 |
|
|
|
128 |
|
|
/** |
129 |
|
|
* Returns true in case there is an element with given @a value in this |
130 |
|
|
* array |
131 |
|
|
* |
132 |
|
|
* @param value - value to be searched for |
133 |
|
|
*/ |
134 |
|
|
bool contains(const T& value) const { |
135 |
schoenebeck |
3557 |
for (size_t i = 0; i < m_size; ++i) |
136 |
schoenebeck |
2630 |
if (m_data[i] == value) return true; |
137 |
|
|
return false; |
138 |
|
|
} |
139 |
|
|
|
140 |
|
|
/** |
141 |
|
|
* Searches the array for an element with given index, if found it |
142 |
|
|
* returns the element's index, if no such element was found an invalid |
143 |
|
|
* index will be returned instead. |
144 |
|
|
* |
145 |
|
|
* @param value - value to be searched for |
146 |
|
|
* @returns index of found element |
147 |
|
|
*/ |
148 |
schoenebeck |
3557 |
size_t find(const T& value) const { |
149 |
|
|
for (size_t i = 0; i < m_size; ++i) |
150 |
schoenebeck |
2630 |
if (m_data[i] == value) return i; |
151 |
|
|
return -1; |
152 |
|
|
} |
153 |
|
|
|
154 |
|
|
/** |
155 |
|
|
* Remove all elements from the array. Size of array will be zero after |
156 |
|
|
* this call. |
157 |
|
|
* |
158 |
|
|
* Access time is always constant with Theta(1). |
159 |
|
|
* |
160 |
|
|
* This method is guaranteed to be real-time safe. |
161 |
|
|
*/ |
162 |
|
|
inline void clear() { |
163 |
|
|
m_size = 0; |
164 |
|
|
} |
165 |
|
|
|
166 |
|
|
/** |
167 |
|
|
* Access element at position @a index (for read/write access). |
168 |
|
|
* |
169 |
|
|
* Access time is always constant with Theta(1). |
170 |
|
|
* |
171 |
|
|
* This method is guaranteed to be real-time safe. |
172 |
|
|
* |
173 |
|
|
* @param index - position of array to access |
174 |
|
|
*/ |
175 |
schoenebeck |
3557 |
inline T& operator[](size_t index) { |
176 |
schoenebeck |
2630 |
return m_data[index]; |
177 |
|
|
} |
178 |
|
|
|
179 |
|
|
/** |
180 |
|
|
* Access element at position @a index (for read only access). |
181 |
|
|
* |
182 |
|
|
* Access time is always constant with Theta(1). |
183 |
|
|
* |
184 |
|
|
* This method is guaranteed to be real-time safe. |
185 |
|
|
* |
186 |
|
|
* @param index - position of array to access |
187 |
|
|
*/ |
188 |
schoenebeck |
3557 |
inline const T& operator[](size_t index) const { |
189 |
schoenebeck |
2630 |
return m_data[index]; |
190 |
|
|
} |
191 |
|
|
|
192 |
|
|
private: |
193 |
|
|
T* __restrict const m_data; |
194 |
schoenebeck |
3557 |
ssize_t m_capacity; |
195 |
|
|
ssize_t m_size; |
196 |
schoenebeck |
2630 |
}; |
197 |
|
|
|
198 |
|
|
} // namespace LinuxSampler |
199 |
|
|
|
200 |
|
|
#endif // LS_CONSTCAPACITYARRAY_H |