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