|
1
|
1 #pragma once
|
|
|
2
|
|
|
3 #include <utility> // std::forward
|
|
|
4
|
|
|
5 #include "alloc.h"
|
|
|
6
|
|
|
7 namespace pfc {
|
|
|
8
|
|
|
9 template<typename t_item, template<typename> class t_alloc = alloc_standard> class array_t;
|
|
|
10
|
|
|
11
|
|
|
12 //! Special simplififed version of array class that avoids stepping on landmines with classes without public copy operators/constructors.
|
|
|
13 template<typename _t_item>
|
|
|
14 class array_staticsize_t {
|
|
|
15 public: typedef _t_item t_item;
|
|
|
16 private: typedef array_staticsize_t<t_item> t_self;
|
|
|
17 public:
|
|
|
18 array_staticsize_t() : m_array(NULL), m_size(0) {}
|
|
|
19 array_staticsize_t(t_size p_size) : m_array(new t_item[p_size]), m_size(p_size) {}
|
|
|
20 ~array_staticsize_t() {release_();}
|
|
|
21
|
|
|
22 //! Copy constructor nonfunctional when data type is not copyable.
|
|
|
23 array_staticsize_t(const t_self & p_source) : m_size(0), m_array(NULL) {
|
|
|
24 *this = p_source;
|
|
|
25 }
|
|
|
26 array_staticsize_t(t_self && p_source) {
|
|
|
27 move_(p_source);
|
|
|
28 }
|
|
|
29
|
|
|
30 //! Copy operator nonfunctional when data type is not copyable.
|
|
|
31 const t_self & operator=(const t_self & p_source) {
|
|
|
32 release_();
|
|
|
33
|
|
|
34 const t_size newsize = p_source.get_size();
|
|
|
35 if (newsize > 0) {
|
|
|
36 m_array = new t_item[newsize];
|
|
|
37 m_size = newsize;
|
|
|
38 for(t_size n = 0; n < newsize; n++) m_array[n] = p_source[n];
|
|
|
39 }
|
|
|
40 return *this;
|
|
|
41 }
|
|
|
42
|
|
|
43 //! Move operator.
|
|
|
44 const t_self & operator=(t_self && p_source) {
|
|
|
45 release_();
|
|
|
46 move_(p_source);
|
|
|
47 return *this;
|
|
|
48 }
|
|
|
49
|
|
|
50 void set_size_discard(t_size p_size) {
|
|
|
51 release_();
|
|
|
52 if (p_size > 0) {
|
|
|
53 m_array = new t_item[p_size];
|
|
|
54 m_size = p_size;
|
|
|
55 }
|
|
|
56 }
|
|
|
57 template<typename t_source>
|
|
|
58 void set_data_fromptr(const t_source * p_buffer,t_size p_count) {
|
|
|
59 if (p_count == m_size) {
|
|
|
60 pfc::copy_array_loop_t(*this,p_buffer,p_count);
|
|
|
61 } else {
|
|
|
62 t_item * arr = new t_item[p_count];
|
|
|
63 try {
|
|
|
64 pfc::copy_array_loop_t(arr, p_buffer, p_count);
|
|
|
65 } catch(...) { delete[] arr; throw; }
|
|
|
66 delete[] m_array;
|
|
|
67 m_array = arr;
|
|
|
68 m_size = p_count;
|
|
|
69 }
|
|
|
70 }
|
|
|
71
|
|
|
72 template<typename t_source>
|
|
|
73 void assign(t_source const * items, size_t count) {
|
|
|
74 set_data_fromptr( items, count );
|
|
|
75 }
|
|
|
76
|
|
|
77
|
|
|
78 t_size get_size() const {return m_size;}
|
|
|
79 t_size size() const {return m_size;} // std compat
|
|
|
80 const t_item * get_ptr() const {return m_array;}
|
|
|
81 t_item * get_ptr() {return m_array;}
|
|
|
82
|
|
|
83 const t_item & operator[](t_size p_index) const {PFC_ASSERT(p_index < get_size());return m_array[p_index];}
|
|
|
84 t_item & operator[](t_size p_index) {PFC_ASSERT(p_index < get_size());return m_array[p_index];}
|
|
|
85
|
|
|
86 template<typename t_source> bool is_owned(const t_source & p_item) {return pfc::is_pointer_in_range(get_ptr(),get_size(),&p_item);}
|
|
|
87
|
|
|
88 template<typename t_out> void enumerate(t_out & out) const { for(t_size walk = 0; walk < m_size; ++walk) out(m_array[walk]); }
|
|
|
89
|
|
|
90 // Modern for loop support
|
|
|
91 t_item* begin() { return get_ptr(); }
|
|
|
92 t_item* end() { return get_ptr() + get_size(); }
|
|
|
93 const t_item* begin() const { return get_ptr(); }
|
|
|
94 const t_item* end() const { return get_ptr() + get_size(); }
|
|
|
95
|
|
|
96 private:
|
|
|
97 void release_() {
|
|
|
98 m_size = 0;
|
|
|
99 delete[] pfc::replace_null_t(m_array);
|
|
|
100 }
|
|
|
101 void move_(t_self & from) {
|
|
|
102 m_size = from.m_size;
|
|
|
103 m_array = from.m_array;
|
|
|
104 from.m_size = 0;
|
|
|
105 from.m_array = NULL;
|
|
|
106 }
|
|
|
107 t_item * m_array;
|
|
|
108 t_size m_size;
|
|
|
109 };
|
|
|
110
|
|
|
111 template<typename t_to,typename t_from>
|
|
|
112 void copy_array_t(t_to & p_to,const t_from & p_from) {
|
|
|
113 const t_size size = array_size_t(p_from);
|
|
|
114 if (p_to.has_owned_items(p_from)) {//avoid landmines with actual array data overlapping, or p_from being same as p_to
|
|
|
115 array_staticsize_t<typename t_to::t_item> temp;
|
|
|
116 temp.set_size_discard(size);
|
|
|
117 pfc::copy_array_loop_t(temp,p_from,size);
|
|
|
118 p_to.set_size(size);
|
|
|
119 pfc::copy_array_loop_t(p_to,temp,size);
|
|
|
120 } else {
|
|
|
121 p_to.set_size(size);
|
|
|
122 pfc::copy_array_loop_t(p_to,p_from,size);
|
|
|
123 }
|
|
|
124 }
|
|
|
125
|
|
|
126 template<typename t_array,typename t_value>
|
|
|
127 void fill_array_t(t_array & p_array,const t_value & p_value) {
|
|
|
128 const t_size size = array_size_t(p_array);
|
|
|
129 for(t_size n=0;n<size;n++) p_array[n] = p_value;
|
|
|
130 }
|
|
|
131
|
|
|
132 template<typename _t_item, template<typename> class t_alloc> class array_t {
|
|
|
133 public: typedef _t_item t_item;
|
|
|
134 private: typedef array_t<t_item,t_alloc> t_self;
|
|
|
135 public:
|
|
|
136 array_t() {}
|
|
|
137 array_t(const t_self & p_source) {copy_array_t(*this,p_source);}
|
|
|
138 template<typename t_source> array_t(const t_source & p_source) {copy_array_t(*this,p_source);}
|
|
|
139 const t_self & operator=(const t_self & p_source) {copy_array_t(*this,p_source); return *this;}
|
|
|
140 template<typename t_source> const t_self & operator=(const t_source & p_source) {copy_array_t(*this,p_source); return *this;}
|
|
|
141
|
|
|
142 array_t(t_self && p_source) {move_from(p_source);}
|
|
|
143 const t_self & operator=(t_self && p_source) {move_from(p_source); return *this;}
|
|
|
144
|
|
|
145 void set_size(t_size p_size) {m_alloc.set_size(p_size);}
|
|
|
146 void resize( size_t s ) { set_size(s); } // std compat
|
|
|
147
|
|
|
148 template<typename fill_t>
|
|
|
149 void set_size_fill(size_t p_size, fill_t const & filler) {
|
|
|
150 size_t before = get_size();
|
|
|
151 set_size( p_size );
|
|
|
152 for(size_t w = before; w < p_size; ++w) this->get_ptr()[w] = filler;
|
|
|
153 }
|
|
|
154
|
|
|
155 void set_size_in_range(size_t minSize, size_t maxSize) {
|
|
|
156 if (minSize >= maxSize) { set_size( minSize); return; }
|
|
|
157 size_t walk = maxSize;
|
|
|
158 for(;;) {
|
|
|
159 try {
|
|
|
160 set_size(walk);
|
|
|
161 return;
|
|
|
162 } catch(std::bad_alloc const &) {
|
|
|
163 if (walk <= minSize) throw;
|
|
|
164 // go on
|
|
|
165 }
|
|
|
166 walk >>= 1;
|
|
|
167 if (walk < minSize) walk = minSize;
|
|
|
168 }
|
|
|
169 }
|
|
|
170 void set_size_discard(t_size p_size) {m_alloc.set_size(p_size);}
|
|
|
171 void set_count(t_size p_count) {m_alloc.set_size(p_count);}
|
|
|
172 t_size get_size() const {return m_alloc.get_size();}
|
|
|
173 size_t size() const {return m_alloc.get_size();} // std compat
|
|
|
174 t_size get_count() const {return m_alloc.get_size();}
|
|
|
175 void force_reset() {m_alloc.force_reset();}
|
|
|
176
|
|
|
177 const t_item & operator[](t_size p_index) const {PFC_ASSERT(p_index < get_size());return m_alloc[p_index];}
|
|
|
178 t_item & operator[](t_size p_index) {PFC_ASSERT(p_index < get_size());return m_alloc[p_index];}
|
|
|
179
|
|
|
180 //! Warning: buffer pointer must not point to buffer allocated by this array (fixme).
|
|
|
181 template<typename t_source>
|
|
|
182 void set_data_fromptr(const t_source * p_buffer,t_size p_count) {
|
|
|
183 set_size(p_count);
|
|
|
184 pfc::copy_array_loop_t(*this,p_buffer,p_count);
|
|
|
185 }
|
|
|
186
|
|
|
187 template<typename t_array>
|
|
|
188 void append(const t_array & p_source) {
|
|
|
189 if (has_owned_items(p_source)) append(array_t<t_item>(p_source));
|
|
|
190 else {
|
|
|
191 const t_size source_size = array_size_t(p_source);
|
|
|
192 const t_size base = get_size();
|
|
|
193 increase_size(source_size);
|
|
|
194 for(t_size n=0;n<source_size;n++) m_alloc[base+n] = p_source[n];
|
|
|
195 }
|
|
|
196 }
|
|
|
197
|
|
|
198 template<typename t_insert>
|
|
|
199 void insert_multi(const t_insert & value, t_size base, t_size count) {
|
|
|
200 const t_size oldSize = get_size();
|
|
|
201 if (base > oldSize) base = oldSize;
|
|
|
202 increase_size(count);
|
|
|
203 pfc::memmove_t(get_ptr() + base + count, get_ptr() + base, oldSize - base);
|
|
|
204 pfc::fill_ptr_t(get_ptr() + base, count, value);
|
|
|
205 }
|
|
|
206 template<typename t_append> void append_multi(const t_append & value, t_size count) {insert_multi(value,~0,count);}
|
|
|
207
|
|
|
208 //! Warning: buffer pointer must not point to buffer allocated by this array (fixme).
|
|
|
209 template<typename t_append>
|
|
|
210 void append_fromptr(const t_append * p_buffer,t_size p_count) {
|
|
|
211 PFC_ASSERT( !is_owned(&p_buffer[0]) );
|
|
|
212 t_size base = get_size();
|
|
|
213 increase_size(p_count);
|
|
|
214 for(t_size n=0;n<p_count;n++) m_alloc[base+n] = p_buffer[n];
|
|
|
215 }
|
|
|
216
|
|
|
217 void increase_size(t_size p_delta) {
|
|
|
218 t_size new_size = get_size() + p_delta;
|
|
|
219 if (new_size < p_delta) throw std::bad_alloc();
|
|
|
220 set_size(new_size);
|
|
|
221 }
|
|
|
222
|
|
|
223 template<typename item_t>
|
|
|
224 void add_item( item_t && item ) {
|
|
|
225 const t_size base = get_size();
|
|
|
226 increase_size(1);
|
|
|
227 m_alloc[base] = std::forward<item_t>( item );
|
|
|
228 }
|
|
|
229 template<typename item_t>
|
|
|
230 void append_single_val( item_t && item ) {
|
|
|
231 const t_size base = get_size();
|
|
|
232 increase_size(1);
|
|
|
233 m_alloc[base] = std::forward<item_t>( item );
|
|
|
234 }
|
|
|
235
|
|
|
236 template<typename t_append>
|
|
|
237 void append_single(const t_append & p_item) {
|
|
|
238 if (is_owned(p_item)) append_single(t_append(p_item));
|
|
|
239 else {
|
|
|
240 const t_size base = get_size();
|
|
|
241 increase_size(1);
|
|
|
242 m_alloc[base] = p_item;
|
|
|
243 }
|
|
|
244 }
|
|
|
245
|
|
|
246 template<typename t_filler>
|
|
|
247 void fill(const t_filler & p_filler) {
|
|
|
248 const t_size max = get_size();
|
|
|
249 for(t_size n=0;n<max;n++) m_alloc[n] = p_filler;
|
|
|
250 }
|
|
|
251
|
|
|
252 void fill_null() {
|
|
|
253 const t_size max = get_size();
|
|
|
254 for(t_size n=0;n<max;n++) m_alloc[n] = 0;
|
|
|
255 }
|
|
|
256
|
|
|
257 void grow_size(t_size p_size) {
|
|
|
258 if (p_size > get_size()) set_size(p_size);
|
|
|
259 }
|
|
|
260
|
|
|
261 //not supported by some allocs
|
|
|
262 const t_item * get_ptr() const {return m_alloc.get_ptr();}
|
|
|
263 t_item * get_ptr() {return m_alloc.get_ptr();}
|
|
|
264
|
|
|
265 void prealloc(t_size p_size) {m_alloc.prealloc(p_size);}
|
|
|
266
|
|
|
267 template<typename t_array>
|
|
|
268 bool has_owned_items(const t_array & p_source) {
|
|
|
269 if (array_size_t(p_source) == 0) return false;
|
|
|
270
|
|
|
271 //how the hell would we properly check if any of source items is owned by us, in case source array implements some weird mixing of references of items from different sources?
|
|
|
272 //the most obvious way means evil bottleneck here (whether it matters or not from caller's point of view which does something O(n) already is another question)
|
|
|
273 //at least this will work fine with all standard classes which don't crossreference anyhow and always use own storage
|
|
|
274 //perhaps we'll traitify this someday later
|
|
|
275 return is_owned(p_source[0]);
|
|
|
276 }
|
|
|
277
|
|
|
278 template<typename t_source>
|
|
|
279 bool is_owned(const t_source & p_item) {
|
|
|
280 return m_alloc.is_ptr_owned(&p_item);
|
|
|
281 }
|
|
|
282
|
|
|
283 template<typename t_item>
|
|
|
284 void set_single(const t_item & p_item) {
|
|
|
285 set_size(1);
|
|
|
286 (*this)[0] = p_item;
|
|
|
287 }
|
|
|
288
|
|
|
289 template<typename t_callback> void enumerate(t_callback & p_callback) const { for(t_size n = 0; n < get_size(); n++ ) { p_callback((*this)[n]); } }
|
|
|
290
|
|
|
291 void move_from(t_self & other) {
|
|
|
292 m_alloc.move_from(other.m_alloc);
|
|
|
293 }
|
|
|
294
|
|
|
295 // Modern for loop support
|
|
|
296 t_item* begin() { return get_ptr(); }
|
|
|
297 t_item* end() { return get_ptr() + get_size(); }
|
|
|
298 const t_item* begin() const { return get_ptr(); }
|
|
|
299 const t_item* end() const { return get_ptr() + get_size(); }
|
|
|
300 private:
|
|
|
301 t_alloc<t_item> m_alloc;
|
|
|
302 };
|
|
|
303
|
|
|
304 template<typename t_item,t_size p_width,template<typename> class t_alloc = alloc_standard >
|
|
|
305 class array_hybrid_t : public array_t<t_item, pfc::alloc_hybrid<p_width,t_alloc>::template alloc >
|
|
|
306 {};
|
|
|
307
|
|
|
308
|
|
|
309 template<typename t_item> class traits_t<array_staticsize_t<t_item> > : public traits_default_movable {};
|
|
|
310 template<typename t_item,template<typename> class t_alloc> class traits_t<array_t<t_item,t_alloc> > : public pfc::traits_t<t_alloc<t_item> > {};
|
|
|
311
|
|
|
312
|
|
|
313 template<typename t_comparator = comparator_default>
|
|
|
314 class comparator_array {
|
|
|
315 public:
|
|
|
316 template<typename t_array1, typename t_array2>
|
|
|
317 static int compare(const t_array1 & p_array1, const t_array2 & p_array2) {
|
|
|
318 t_size walk = 0;
|
|
|
319 for(;;) {
|
|
|
320 if (walk >= p_array1.get_size() && walk >= p_array2.get_size()) return 0;
|
|
|
321 else if (walk >= p_array1.get_size()) return -1;
|
|
|
322 else if (walk >= p_array2.get_size()) return 1;
|
|
|
323 else {
|
|
|
324 int state = t_comparator::compare(p_array1[walk],p_array2[walk]);
|
|
|
325 if (state != 0) return state;
|
|
|
326 }
|
|
|
327 ++walk;
|
|
|
328 }
|
|
|
329 }
|
|
|
330 };
|
|
|
331
|
|
|
332 template<typename t_a1, typename t_a2>
|
|
|
333 static bool array_equals(const t_a1 & arr1, const t_a2 & arr2) {
|
|
|
334 const t_size s = array_size_t(arr1);
|
|
|
335 if (s != array_size_t(arr2)) return false;
|
|
|
336 for(t_size walk = 0; walk < s; ++walk) {
|
|
|
337 if (arr1[walk] != arr2[walk]) return false;
|
|
|
338 }
|
|
|
339 return true;
|
|
|
340 }
|
|
|
341
|
|
|
342
|
|
|
343
|
|
|
344 template<typename t_item, template<typename> class t_alloc = alloc_standard> class array_2d_t {
|
|
|
345 public:
|
|
|
346 array_2d_t() : m_d1(), m_d2() {}
|
|
|
347 void set_size(t_size d1, t_size d2) {
|
|
|
348 m_content.set_size(pfc::mul_safe_t<std::bad_alloc>(d1, d2));
|
|
|
349 m_d1 = d1; m_d2 = d2;
|
|
|
350 }
|
|
|
351 t_size get_dim1() const {return m_d1;}
|
|
|
352 t_size get_dim2() const {return m_d2;}
|
|
|
353
|
|
|
354 t_item & at(t_size i1, t_size i2) {
|
|
|
355 return * _transformPtr(m_content.get_ptr(), i1, i2);
|
|
|
356 }
|
|
|
357 const t_item & at(t_size i1, t_size i2) const {
|
|
|
358 return * _transformPtr(m_content.get_ptr(), i1, i2);
|
|
|
359 }
|
|
|
360 template<typename t_filler> void fill(const t_filler & p_filler) {m_content.fill(p_filler);}
|
|
|
361 void fill_null() {m_content.fill_null();}
|
|
|
362
|
|
|
363 t_item * rowPtr(t_size i1) {return _transformPtr(m_content.get_ptr(), i1, 0);}
|
|
|
364 const t_item * rowPtr(t_size i1) const {return _transformPtr(m_content.get_ptr(), i1, 0);}
|
|
|
365
|
|
|
366 const t_item * operator[](t_size i1) const {return rowPtr(i1);}
|
|
|
367 t_item * operator[](t_size i1) {return rowPtr(i1);}
|
|
|
368 private:
|
|
|
369 template<typename t_ptr> t_ptr _transformPtr(t_ptr ptr, t_size i1, t_size i2) const {
|
|
|
370 PFC_ASSERT( i1 < m_d1 ); PFC_ASSERT( i2 < m_d2 );
|
|
|
371 return ptr + i1 * m_d2 + i2;
|
|
|
372 }
|
|
|
373 pfc::array_t<t_item, t_alloc> m_content;
|
|
|
374 t_size m_d1, m_d2;
|
|
|
375 };
|
|
|
376
|
|
|
377 }
|
|
|
378
|
