Roc Toolkit internal modules
Roc Toolkit: real-time audio streaming
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//! Small chunks can be stored directly in Array object, without extra allocation.
30//! Array can be resized only by explicitly calling resize(), grow(), or grow_exp().
31//! Elements are copied during resize and old copies are destroyed.
32//!
33//! @tparam T defines array element type. It should have copy constructor and
34//! destructor.
35//!
36//! @tparam EmbeddedCapacity defines the size of the fixed-size array embedded
37//! directly into Array object; it is used instead of dynamic memory if
38//! the array size is small enough.
39template <class T, size_t EmbeddedCapacity = 0> class Array : public NonCopyable<> {
40public:
41 //! Initialize empty array without arena.
42 //! @remarks
43 //! Array capacity will be limited to the embedded capacity.
45 : data_(NULL)
46 , size_(0)
47 , max_size_(0)
48 , arena_(NULL) {
49 }
50
51 //! Initialize empty array with arena.
52 //! @remarks
53 //! Array capacity may grow using arena.
54 explicit Array(IArena& arena)
55 : data_(NULL)
56 , size_(0)
57 , max_size_(0)
58 , arena_(&arena) {
59 }
60
61 ~Array() {
62 clear();
63
64 if (data_) {
65 deallocate_(data_);
66 }
67 }
68
69 //! Get maximum number of elements.
70 //! If array has arena, capacity can be grown.
71 size_t capacity() const {
72 return max_size_;
73 }
74
75 //! Get number of elements.
76 size_t size() const {
77 return size_;
78 }
79
80 //! Check if size is zero.
81 bool is_empty() const {
82 return size_ == 0;
83 }
84
85 //! Get pointer to first element.
86 //! @remarks
87 //! Returns null if the array is empty.
88 T* data() {
89 if (size_) {
90 return data_;
91 } else {
92 return NULL;
93 }
94 }
95
96 //! Get pointer to first element.
97 //! @remarks
98 //! Returns null if the array is empty.
99 const T* data() const {
100 if (size_) {
101 return data_;
102 } else {
103 return NULL;
104 }
105 }
106
107 //! Get element at given position.
108 T& operator[](size_t index) {
109 if (index >= size_) {
110 roc_panic("array: subscript out of range: index=%lu size=%lu",
111 (unsigned long)index, (unsigned long)size_);
112 }
113 return data_[index];
114 }
115
116 //! Get element at given position.
117 const T& operator[](size_t index) const {
118 if (index >= size_) {
119 roc_panic("array: subscript out of range: index=%lu size=%lu",
120 (unsigned long)index, (unsigned long)size_);
121 }
122 return data_[index];
123 }
124
125 //! Append element to array.
126 //! @returns
127 //! false if the allocation failed
128 ROC_ATTR_NODISCARD bool push_back(const T& value) {
129 if (!grow_exp(size() + 1)) {
130 return false;
131 }
132
133 new (data_ + size_) T(value);
134 size_++;
135
136 return true;
137 }
138
139 //! Set array size.
140 //! @remarks
141 //! Calls grow() to ensure that there is enough space in array.
142 //! @returns
143 //! false if the allocation failed
144 ROC_ATTR_NODISCARD bool resize(size_t sz) {
145 // Move objects to a new memory region if necessary.
146 if (!grow(sz)) {
147 return false;
148 }
149
150 // Construct new objects if size increased.
151 for (size_t n = size_; n < sz; n++) {
152 new (data_ + n) T();
153 }
154
155 // Destruct old objects (in reverse order) if size decreased.
156 for (size_t n = size_; n > sz; n--) {
157 data_[n - 1].~T();
158 }
159
160 size_ = sz;
161
162 return true;
163 }
164
165 //! Set array size to zero.
166 //! @remarks
167 //! Never fails.
168 void clear() {
169 (void)resize(0);
170 }
171
172 //! Increase array capacity.
173 //! @remarks
174 //! If @p max_sz is greater than the current capacity, a larger memory
175 //! region is allocated and the array elements are copied there.
176 //! @returns
177 //! false if the allocation failed
178 ROC_ATTR_NODISCARD bool grow(size_t max_sz) {
179 if (max_sz <= max_size_) {
180 return true;
181 }
182
183 T* new_data = allocate_(max_sz);
184 if (!new_data) {
185 roc_log(LogError, "array: can't allocate memory: old_size=%lu new_size=%lu",
186 (unsigned long)max_size_, (unsigned long)max_sz);
187 return false;
188 }
189
190 if (new_data != data_) {
191 // Copy old objects to new memory.
192 for (size_t n = 0; n < size_; n++) {
193 new (new_data + n) T(data_[n]);
194 }
195
196 // Destruct objects in old memory (in reverse order).
197 for (size_t n = size_; n > 0; n--) {
198 data_[n - 1].~T();
199 }
200
201 // Free old memory.
202 if (data_) {
203 deallocate_(data_);
204 }
205
206 data_ = new_data;
207 }
208
209 max_size_ = max_sz;
210 return true;
211 }
212
213 //! Increase array capacity exponentially.
214 //! @remarks
215 //! If @p min_size is greater than the current capacity, a larger memory
216 //! region is allocated and the array elements are copied there.
217 //! The size growth will follow the sequence: 0, 2, 4, 8, 16, ... until
218 //! it reaches some threshold, and then starts growing linearly.
219 //! @returns
220 //! false if the allocation failed
221 ROC_ATTR_NODISCARD bool grow_exp(size_t min_size) {
222 if (min_size <= max_size_) {
223 return true;
224 }
225
226 size_t new_max_size_ = max_size_;
227
228 if (max_size_ < 1024) {
229 while (min_size > new_max_size_) {
230 new_max_size_ = (new_max_size_ == 0) ? 2 : new_max_size_ * 2;
231 }
232 } else {
233 while (min_size > new_max_size_) {
234 new_max_size_ += new_max_size_ / 4;
235 }
236 }
237
238 return grow(new_max_size_);
239 }
240
241private:
242 T* allocate_(size_t n_elems) {
243 if (n_elems <= EmbeddedCapacity) {
244 return (T*)embedded_data_.memory();
245 } else if (arena_) {
246 return (T*)arena_->allocate(n_elems * sizeof(T));
247 } else {
248 return NULL;
249 }
250 }
251
252 void deallocate_(T* data) {
253 if ((void*)data != (void*)embedded_data_.memory()) {
254 roc_panic_if(!arena_);
255 arena_->deallocate(data);
256 }
257 }
258
259 T* data_;
260 size_t size_;
261 size_t max_size_;
262
263 IArena* arena_;
264
265 AlignedStorage<EmbeddedCapacity * sizeof(T)> embedded_data_;
266};
267
268} // namespace core
269} // namespace roc
270
271#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:39
ROC_ATTR_NODISCARD bool grow_exp(size_t min_size)
Increase array capacity exponentially.
Definition: array.h:221
T * data()
Get pointer to first element.
Definition: array.h:88
Array()
Initialize empty array without arena.
Definition: array.h:44
void clear()
Set array size to zero.
Definition: array.h:168
const T * data() const
Get pointer to first element.
Definition: array.h:99
ROC_ATTR_NODISCARD bool push_back(const T &value)
Append element to array.
Definition: array.h:128
Array(IArena &arena)
Initialize empty array with arena.
Definition: array.h:54
ROC_ATTR_NODISCARD bool resize(size_t sz)
Set array size.
Definition: array.h:144
ROC_ATTR_NODISCARD bool grow(size_t max_sz)
Increase array capacity.
Definition: array.h:178
bool is_empty() const
Check if size is zero.
Definition: array.h:81
size_t capacity() const
Get maximum number of elements. If array has arena, capacity can be grown.
Definition: array.h:71
const T & operator[](size_t index) const
Get element at given position.
Definition: array.h:117
T & operator[](size_t index)
Get element at given position.
Definition: array.h:108
size_t size() const
Get number of elements.
Definition: array.h:76
Memory arena interface.
Definition: iarena.h:23
virtual void * allocate(size_t size)=0
Allocate memory.
virtual void deallocate(void *)=0
Deallocate previously allocated memory.
Base class for non-copyable objects.
Definition: noncopyable.h:23
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(x)
Panic if condition is true.
Definition: panic.h:26
#define roc_panic(...)
Print error message and terminate program gracefully.
Definition: panic.h:50
Commonly used types and functions.