Roc Toolkit internal modules
Roc Toolkit: real-time audio streaming
Loading...
Searching...
No Matches
array.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2015 Roc Streaming authors
3 *
4 * This Source Code Form is subject to the terms of the Mozilla Public
5 * License, v. 2.0. If a copy of the MPL was not distributed with this
6 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
7 */
8
9//! @file roc_core/array.h
10//! @brief Dynamic array.
11
12#ifndef ROC_CORE_ARRAY_H_
13#define ROC_CORE_ARRAY_H_
14
16#include "roc_core/attributes.h"
17#include "roc_core/iarena.h"
18#include "roc_core/log.h"
20#include "roc_core/panic.h"
21#include "roc_core/stddefs.h"
22
23namespace roc {
24namespace core {
25
26//! Dynamic array.
27//!
28//! Elements are stored continuously in a memory chunk allocated using IArena,
29//! or directly in Array object when number of elements is small.
30//!
31//! Array supports resizing and inserting and removing elements in the end with
32//! amortized O(1) complexity.
33//!
34//! @tparam T defines array element type. It should have default constructor,
35//! copy constructor, and assignment operator.
36//!
37//! @tparam EmbeddedCapacity defines number of elements in the fixed-size chunk
38//! embedded directly into Array object; it is used instead of dynamic memory if
39//! the array size is small enough.
40template <class T, size_t EmbeddedCapacity = 0> class Array : public NonCopyable<> {
41public:
42 //! Initialize empty array with arena.
43 //! @remarks
44 //! Array capacity may grow using arena.
45 explicit Array(IArena& arena)
46 : data_(NULL)
47 , size_(0)
48 , capacity_(0)
49 , arena_(arena) {
50 }
51
52 ~Array() {
53 clear();
54
55 if (data_) {
56 deallocate_(data_);
57 }
58 }
59
60 //! Get maximum number of elements that can be added without reallocation.
61 size_t capacity() const {
62 return capacity_;
63 }
64
65 //! Get number of elements.
66 size_t size() const {
67 return size_;
68 }
69
70 //! Check if size is zero.
71 bool is_empty() const {
72 return size_ == 0;
73 }
74
75 //! Get pointer to first element.
76 //! @remarks
77 //! Returns null if the array is empty.
78 T* data() {
79 if (size_ == 0) {
80 roc_panic("array: is empty");
81 }
82 return data_;
83 }
84
85 //! Get pointer to first element.
86 //! @remarks
87 //! Returns null if the array is empty.
88 const T* data() const {
89 if (size_ == 0) {
90 roc_panic("array: is empty");
91 }
92 return data_;
93 }
94
95 //! Get element at given position.
96 //! @pre
97 //! Panics if index is out of bounds.
98 T& operator[](size_t index) {
99 roc_panic_if_msg(index >= size_,
100 "array: subscript out of range: index=%lu size=%lu",
101 (unsigned long)index, (unsigned long)size_);
102
103 return data_[index];
104 }
105
106 //! Get element at given position.
107 //! @pre
108 //! Panics if index is out of bounds.
109 const T& operator[](size_t index) const {
110 roc_panic_if_msg(index >= size_,
111 "array: subscript out of range: index=%lu size=%lu",
112 (unsigned long)index, (unsigned long)size_);
113
114 return data_[index];
115 }
116
117 //! Get reference to first element.
118 T& front() {
119 if (size_ == 0) {
120 roc_panic("array: is empty");
121 }
122 return data_[0];
123 }
124
125 //! Get const reference to first element.
126 const T& front() const {
127 if (size_ == 0) {
128 roc_panic("array: is empty");
129 }
130 return data_[0];
131 }
132
133 //! Get reference to last element.
134 T& back() {
135 if (size_ == 0) {
136 roc_panic("array: is empty");
137 }
138 return data_[size_ - 1];
139 }
140
141 //! Get const reference to last element.
142 const T& back() const {
143 if (size_ == 0) {
144 roc_panic("array: is empty");
145 }
146 return data_[size_ - 1];
147 }
148
149 //! Append element to array.
150 //! @returns
151 //! false if the allocation failed.
152 //! @note
153 //! has amortized O(1) complexity, O(n) in worst case.
154 ROC_ATTR_NODISCARD bool push_back(const T& value) {
155 if (!grow_exp(size_ + 1)) {
156 return false;
157 }
158
159 new (data_ + size_) T(value);
160 size_++;
161
162 return true;
163 }
164
165 //! Remove last element from the array.
166 //! @pre
167 //! Panics if array is empty.
168 void pop_back() {
169 if (size_ == 0) {
170 roc_panic("array: array is empty");
171 }
172
173 // Destruct object
174 data_[size_ - 1].~T();
175 size_--;
176 }
177
178 //! Set array size.
179 //! @remarks
180 //! Calls grow() to ensure that there is enough space in array.
181 //! @returns
182 //! false if the allocation failed
184 // Move objects to a new memory region if necessary.
185 if (!grow(new_size)) {
186 return false;
187 }
188
189 // Construct new objects if size increased.
190 for (size_t n = size_; n < new_size; n++) {
191 new (data_ + n) T();
192 }
193
194 // Destruct old objects (in reversed order) if size decreased.
195 for (size_t n = size_; n > new_size; n--) {
196 data_[n - 1].~T();
197 }
198
199 size_ = new_size;
200
201 return true;
202 }
203
204 //! Set array size to zero.
205 //! @remarks
206 //! Never fails.
207 void clear() {
208 (void)resize(0);
209 }
210
211 //! Increase array capacity.
212 //! @remarks
213 //! If @p min_capacity is greater than the current capacity, a larger memory
214 //! region is allocated and the array elements are copied there.
215 //! @returns
216 //! false if the allocation failed.
218 if (min_capacity <= capacity_) {
219 return true;
220 }
221
222 T* new_data = allocate_(min_capacity);
223 if (!new_data) {
224 return false;
225 }
226
227 if (new_data != data_) {
228 // Copy old objects to new memory.
229 for (size_t n = 0; n < size_; n++) {
230 new (new_data + n) T(data_[n]);
231 }
232
233 // Destruct objects in old memory (in reversed order).
234 for (size_t n = size_; n > 0; n--) {
235 data_[n - 1].~T();
236 }
237
238 // Free old memory.
239 if (data_) {
240 deallocate_(data_);
241 }
242
243 data_ = new_data;
244 }
245
246 capacity_ = min_capacity;
247 return true;
248 }
249
250 //! Increase array capacity exponentially.
251 //! @remarks
252 //! If @p min_capacity is greater than the current capacity, a larger memory
253 //! region is allocated and the array elements are copied there.
254 //! The size growth will follow the sequence: 0, 2, 4, 8, 16, ... until
255 //! it reaches some threshold, and then starts growing linearly.
256 //! @returns
257 //! false if the allocation failed.
259 if (min_capacity <= capacity_) {
260 return true;
261 }
262
263 const size_t new_capacity = next_capacity_(min_capacity);
264
265 return grow(new_capacity);
266 }
267
268private:
269 T* allocate_(size_t n_elems) {
270 T* data = NULL;
271
272 if (n_elems <= EmbeddedCapacity) {
273 data = (T*)embedded_data_.memory();
274 } else {
275 data = (T*)arena_.allocate(n_elems * sizeof(T));
276 }
277
278 if (!data) {
280 "array: can't allocate memory:"
281 " current_cap=%lu requested_cap=%lu embedded_cap=%lu",
282 (unsigned long)capacity_, (unsigned long)n_elems,
283 (unsigned long)EmbeddedCapacity);
284 }
285
286 return data;
287 }
288
289 void deallocate_(T* data) {
290 if ((void*)data != (void*)embedded_data_.memory()) {
291 arena_.deallocate(data);
292 }
293 }
294
295 size_t next_capacity_(size_t min_size) const {
296 size_t new_capacity = capacity_;
297
298 if (capacity_ < 1024) {
299 while (min_size > new_capacity) {
300 new_capacity = (new_capacity == 0) ? 2 : new_capacity * 2;
301 }
302 } else {
303 while (min_size > new_capacity) {
304 new_capacity += new_capacity / 4;
305 }
306 }
307
308 return new_capacity;
309 }
310
311 T* data_;
312 size_t size_;
313 size_t capacity_;
314
315 IArena& arena_;
316
317 AlignedStorage<EmbeddedCapacity * sizeof(T)> embedded_data_;
318};
319
320} // namespace core
321} // namespace roc
322
323#endif // ROC_CORE_ARRAY_H_
Aligned storage.
Compiler attributes.
#define ROC_ATTR_NODISCARD
Emit warning if function result is not checked.
Definition attributes.h:31
Dynamic array.
Definition array.h:40
bool grow(size_t min_capacity)
Increase array capacity.
Definition array.h:217
T & front()
Get reference to first element.
Definition array.h:118
T * data()
Get pointer to first element.
Definition array.h:78
const T & front() const
Get const reference to first element.
Definition array.h:126
void pop_back()
Remove last element from the array.
Definition array.h:168
void clear()
Set array size to zero.
Definition array.h:207
const T * data() const
Get pointer to first element.
Definition array.h:88
T & back()
Get reference to last element.
Definition array.h:134
Array(IArena &arena)
Initialize empty array with arena.
Definition array.h:45
bool grow_exp(size_t min_capacity)
Increase array capacity exponentially.
Definition array.h:258
bool is_empty() const
Check if size is zero.
Definition array.h:71
bool resize(size_t new_size)
Set array size.
Definition array.h:183
const T & back() const
Get const reference to last element.
Definition array.h:142
size_t capacity() const
Get maximum number of elements that can be added without reallocation.
Definition array.h:61
const T & operator[](size_t index) const
Get element at given position.
Definition array.h:109
bool push_back(const T &value)
Append element to array.
Definition array.h:154
T & operator[](size_t index)
Get element at given position.
Definition array.h:98
size_t size() const
Get number of elements.
Definition array.h:66
Memory arena interface.
Definition iarena.h:23
virtual void deallocate(void *ptr)=0
Deallocate previously allocated memory.
virtual void * allocate(size_t size)=0
Allocate memory.
Base class for non-copyable objects.
Definition noncopyable.h:23
Shared ownership intrusive pointer.
Definition shared_ptr.h:32
Memory arena interface.
Logging.
#define roc_log(level,...)
Print message to log.
Definition log.h:31
Root namespace.
@ LogError
Error message.
Definition log.h:45
Non-copyable object.
Panic.
#define roc_panic_if_msg(x,...)
Panic if condition is true, printing custom message.
Definition panic.h:40
#define roc_panic(...)
Print error message and terminate program gracefully.
Definition panic.h:50
Commonly used types and functions.