1 |
/* |
2 |
* Copyright (c) 2014 - 2019 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 || 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 |
for (size_t i = 0; i < count; ++i) |
124 |
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 |
for (size_t i = 0; i < m_size; ++i) |
136 |
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 |
size_t find(const T& value) const { |
149 |
for (size_t i = 0; i < m_size; ++i) |
150 |
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 |
inline T& operator[](size_t index) { |
176 |
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 |
inline const T& operator[](size_t index) const { |
189 |
return m_data[index]; |
190 |
} |
191 |
|
192 |
private: |
193 |
T* __restrict const m_data; |
194 |
ssize_t m_capacity; |
195 |
ssize_t m_size; |
196 |
}; |
197 |
|
198 |
} // namespace LinuxSampler |
199 |
|
200 |
#endif // LS_CONSTCAPACITYARRAY_H |