source: icXML/icXML-devel/src/icxmlc/Array.hpp @ 2720

Last change on this file since 2720 was 2720, checked in by cameron, 6 years ago

Initial check-in of icXML 0.8 source files

File size: 10.7 KB
Line 
1/*
2 *  Copyright © 2012 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icXML is a trademark of International Characters.
5 */
6
7/*
8 * @author Nigel Medforth, nigelm -at- interational-characters.com
9 * @version $Id: Array.hpp 207 2012-12-02 20:38:22Z robc $
10 *
11 */
12
13#ifndef ARRAY_HPP
14#define ARRAY_HPP
15
16#include <icxmlc/XMLBlockCopy.h>
17#include <simd-lib/bitblock.hpp>
18#include <string.h>
19#include <icxmlc/XMLConfig.hpp>
20
21#if defined(_MSC_VER)
22#include <malloc.h>
23#elif !defined(__APPLE__)
24#include <stdlib.h>
25#endif
26
27/// ---------------------------------------------------------------------------------------------- ///
28
29template<typename T>
30class Array
31{
32        public:
33
34                static void copy(const T * input, T * output, size_t count);
35
36                static int cmp(const T * a, const T * b, size_t count);
37
38                static void move(const T * input, T * output, size_t count);
39
40                static void memzero(T * ptr, size_t count);
41
42                static T * allocate(const size_t size);
43
44                static void deallocate(T * ptr);
45
46        protected:
47
48                Array() {}
49                virtual ~Array() = 0;
50};
51
52/** ----------------------------------------------------------------------------------------------------- **/
53
54template<typename T, size_t initialCapacity = 0, size_t padding = 0>
55class DynamicArray
56{
57                typedef T & ref_t;
58                typedef const T & const_ref_t;
59                typedef T * ptr_t;
60                typedef const T * const_ptr_t;
61
62                enum { DYNAMIC_ARRAY_PADDING = padding / sizeof(T) };
63
64        public:
65
66                DynamicArray()
67                : _array(_internalArray)
68                , _capacity(initialCapacity)
69                {
70                        // use a flag to avoid this? the internal array ought to be constructed
71                        // with a default 'constructor', which means it ought to be 0'd out.
72                        Array<T>::memzero(_internalArray, initialCapacity + DYNAMIC_ARRAY_PADDING);
73                }
74
75                DynamicArray(const size_t allocatedCapacity)
76                : _array(initialCapacity >= allocatedCapacity ? _internalArray : Array<T>::allocate(allocatedCapacity + DYNAMIC_ARRAY_PADDING))
77                , _capacity(initialCapacity >= allocatedCapacity ? initialCapacity : allocatedCapacity)
78                {
79                        // use a flag to avoid this? the internal array ought to be constructed
80                        // with a default 'constructor', which means it ought to be 0'd out.
81                        Array<T>::memzero(_array, _capacity + DYNAMIC_ARRAY_PADDING);
82                }
83
84                DynamicArray(T * array, const size_t capacity)
85                : _array(array)
86                , _capacity(capacity)
87                {
88
89                }
90
91                ~DynamicArray()
92                {
93                        deallocateArrayIfNecessary();
94                }
95
96                void init(const size_t capacity)
97                {
98                        _array = Array<T>::allocate(capacity + DYNAMIC_ARRAY_PADDING);
99                        _capacity = capacity;
100                        Array<T>::memzero(_array, _capacity + DYNAMIC_ARRAY_PADDING);
101                }
102
103                IDISA_ALWAYS_INLINE
104                void expand(const size_t size)
105                {
106                        expand(&_array[0], size);
107                }
108
109                IDISA_ALWAYS_INLINE
110                void resizeToFit(const size_t size);
111
112                IDISA_ALWAYS_INLINE
113                void resizeToFit(const size_t index, const size_t size);
114
115                IDISA_ALWAYS_INLINE
116                ref_t operator[](const size_t i)
117                {
118                        return _array[i];
119                }
120
121                IDISA_ALWAYS_INLINE
122                const_ref_t operator[](const size_t i) const
123                {
124                        return _array[i];
125                }
126
127                void clear();
128
129                size_t copy_to_front(const size_t from, const size_t to);
130
131                size_t copy_to_front(const size_t from, const size_t to, DynamicArray<T, initialCapacity, padding> & array);
132
133                size_t capacity() const { return _capacity; }
134
135                const T * limit() const { return &_array[_capacity]; }
136
137        private:
138
139                void expand(const_ptr_t const input, const size_t count);
140
141                IDISA_ALWAYS_INLINE
142                void deallocateArrayIfNecessary()
143                {
144                        if ((initialCapacity == 0) || unlikely(_array != _internalArray))
145                        {
146                                Array<T>::deallocate(_array);
147                                _array = _internalArray;
148                                _capacity = initialCapacity;
149                        }
150                }
151
152        private:
153
154
155
156                T                                                       _internalArray[initialCapacity == 0 ? 0 : initialCapacity + DYNAMIC_ARRAY_PADDING];
157                ptr_t                                           _array;
158                size_t                                          _capacity;
159
160};
161
162/// ---------------------------------------------------------------------------------------------- ///
163
164#define ARRAY_IMPL(retType) \
165        template<class T, size_t initialCapacity, size_t padding> \
166        IDISA_ALWAYS_INLINE \
167        retType \
168        DynamicArray<T, initialCapacity, padding>
169
170/// ---------------------------------------------------------------------------------------------- ///
171
172ARRAY_IMPL(void)::
173expand(const_ptr_t const input, size_t count)
174{
175        const size_t additionalCapacity = (initialCapacity == 0) ? 0 : capacity() - (count % initialCapacity);
176        const size_t newCapacity = max(capacity() * 2, count + additionalCapacity);
177
178        ptr_t newArray = Array<T>::allocate(newCapacity + DYNAMIC_ARRAY_PADDING);
179
180        if (unlikely(!newArray))
181        {
182                assert (!"DYNAMIC ARRAY: MEMORY ALLOCATION ERROR!");
183                throw;
184        }
185
186        const size_t size = min(count, capacity());
187
188        Array<T>::copy(input, newArray, size);
189        Array<T>::memzero(&newArray[size], newCapacity - size + DYNAMIC_ARRAY_PADDING);
190
191        deallocateArrayIfNecessary();
192
193        _array = newArray;
194        _capacity = newCapacity;
195}
196
197/// ---------------------------------------------------------------------------------------------- ///
198
199ARRAY_IMPL(void)::
200resizeToFit(const size_t size)
201{
202        resizeToFit(capacity(), size);
203}
204
205
206ARRAY_IMPL(void)::
207resizeToFit(const size_t index, const size_t size)
208{
209        const size_t additionalCapacity = (initialCapacity == 0) ? 0 : capacity() - (size % initialCapacity);
210        const size_t newCapacity = max(capacity() * 2, size + additionalCapacity);
211
212        ptr_t newArray = Array<T>::allocate(newCapacity + DYNAMIC_ARRAY_PADDING);
213
214        if (unlikely(!newArray))
215        {
216                assert (!"DYNAMIC ARRAY: MEMORY ALLOCATION ERROR!");
217                throw;
218        }
219
220        Array<T>::copy(_array, newArray, index);
221        Array<T>::memzero(&newArray[index], newCapacity - index + DYNAMIC_ARRAY_PADDING);
222
223        deallocateArrayIfNecessary();
224
225        _array = newArray;
226        _capacity = newCapacity;
227}
228
229/// ---------------------------------------------------------------------------------------------- ///
230
231ARRAY_IMPL(void)::
232clear()
233{
234        Array<T>::memzero(&_array[0], _capacity + DYNAMIC_ARRAY_PADDING);
235}
236
237/// ---------------------------------------------------------------------------------------------- ///
238
239ARRAY_IMPL(size_t)::
240copy_to_front(const size_t from, const size_t to)
241{
242        const size_t count = to - from;
243
244        if (count)
245        {
246                if (likely(count < (capacity() / 2)))
247                {
248                        // if we are copying less than half of the array, reuse the current buffer;
249                        Array<T>::move(&_array[from], &_array[0], count);
250                }
251                else
252                {
253                        // if we are copying at least half of the array, expand and copy the remaining
254                        // data into the new array.
255                        expand(&_array[from], count);
256                }
257        }
258        return count;
259
260}
261
262ARRAY_IMPL(size_t)::
263copy_to_front(const size_t from, const size_t to, DynamicArray<T, initialCapacity, padding> & array)
264{
265        const size_t count = to - from;
266
267        if (count)
268        {
269                if (likely(count < (array.capacity() / 2)))
270                {
271                        // if we are copying less than half of the array, reuse the current buffer;
272                        Array<T>::copy(&_array[from], &array._array[0], count);
273                }
274                else
275                {
276                        // if we are copying at least half of the array, expand and copy the remaining
277                        // data into the new array.
278                        array.expand(&_array[from], count);
279                }
280        }
281        return count;
282
283}
284
285
286#undef ARRAY_IMPL
287
288/** ----------------------------------------------------------------------------------------------------- **/
289
290template<typename T, size_t fixedCapacity>
291class FixedArray
292{
293                typedef T & ref_t;
294                typedef const T & const_ref_t;
295
296        public:
297
298                FixedArray()
299                {
300                        memset(_array, 0, fixedCapacity * sizeof(T));
301                }
302
303                ~FixedArray() { }
304
305                void expand(const size_t currentSize);
306
307                IDISA_ALWAYS_INLINE
308                ref_t operator[](const size_t i)
309                {
310                        return _array[i];
311                }
312
313                IDISA_ALWAYS_INLINE
314                const_ref_t operator[](const size_t i) const
315                {
316                        return _array[i];
317                }
318
319                size_t copy_to_front(const size_t from, const size_t to);
320
321                size_t capacity() const { return fixedCapacity; }
322
323        private:
324
325                T                               _array[fixedCapacity];
326};
327
328/// ---------------------------------------------------------------------------------------------- ///
329
330#define ARRAY_IMPL(retType) \
331        template<class T, size_t fixedCapacity> \
332        IDISA_ALWAYS_INLINE \
333        retType \
334        FixedArray<T, fixedCapacity>
335
336/// ---------------------------------------------------------------------------------------------- ///
337
338ARRAY_IMPL(size_t)::
339copy_to_front(const size_t from, const size_t to)
340{
341        const size_t count = to - from;
342
343        if (count)
344        {
345                Array<T>::copy(&_array[from], &_array[0], count);
346        }
347
348        return count;
349}
350
351#undef ARRAY_IMPL
352
353/// ---------------------------------------------------------------------------------------------- ///
354
355template<typename T>
356IDISA_ALWAYS_INLINE
357void Array<T>::copy(const T * input, T * output, size_t count)
358{
359        memcpy(output, input, count * sizeof(T));
360}
361
362template<>
363IDISA_ALWAYS_INLINE
364void Array<BitBlock>::copy(const BitBlock * input, BitBlock * output, size_t count)
365{
366        while (count--)
367        {
368                copy_aligned<1>(input++, output++);
369        }
370}
371
372/// ---------------------------------------------------------------------------------------------- ///
373
374template<typename T>
375IDISA_ALWAYS_INLINE
376void Array<T>::move(const T * input, T * output, size_t count)
377{
378        memmove(output, input, count * sizeof(T));
379}
380
381/// ---------------------------------------------------------------------------------------------- ///
382
383template<typename T>
384IDISA_ALWAYS_INLINE
385void Array<T>::memzero(T * ptr, size_t count)
386{
387        memset(ptr, 0, count * sizeof(T));
388}
389
390template<>
391IDISA_ALWAYS_INLINE
392void Array<BitBlock>::memzero(BitBlock * ptr, size_t count)
393{
394        while (count--)
395        {
396                *ptr++ = simd<1>::constant<0>();
397        }
398}
399
400/// ---------------------------------------------------------------------------------------------- ///
401
402template<typename T>
403IDISA_ALWAYS_INLINE
404int Array<T>::cmp(const T * a, const T * b, size_t count)
405{
406        return memcmp(a, b, count * sizeof(T));
407}
408
409/// ---------------------------------------------------------------------------------------------- ///
410
411template<typename T>
412IDISA_ALWAYS_INLINE
413T * Array<T>::allocate(const size_t size)
414{
415        return new T[size];
416}
417
418template<>
419IDISA_ALWAYS_INLINE
420BitBlock * Array<BitBlock>::allocate(const size_t size)
421{
422        #ifdef __APPLE__
423                #if BLOCK_SIZE == 128
424                        return new BitBlock [size];
425                #else
426                        #error "Array<BitBlock>::allocate(x) is not yet defined for Apple systems with a block size over 128."
427                #endif
428        #elif defined(_MSC_VER)
429                        return (BitBlock*)_aligned_malloc(size * sizeof(BitBlock), sizeof(BitBlock));
430        #else
431                        BitBlock * ptr;
432                        if (!posix_memalign(reinterpret_cast<void **>(&ptr), sizeof(BitBlock), size * sizeof(BitBlock)))
433                        {
434                                return ptr;
435                        }
436                        return NULL;
437        #endif
438}
439
440/// ---------------------------------------------------------------------------------------------- ///
441
442template<typename T>
443IDISA_ALWAYS_INLINE
444void Array<T>::deallocate(T * ptr)
445{
446        if (ptr) delete [] ptr;
447}
448
449template<>
450IDISA_ALWAYS_INLINE
451void Array<BitBlock>::deallocate(BitBlock * ptr)
452{
453        if (ptr)
454        {
455                #ifdef __APPLE__
456                        delete [] ptr;
457                #elif defined(_MSC_VER)
458                        _aligned_free(ptr);
459                #else
460                        free((void *)ptr);
461                #endif
462        }
463}
464
465template<class T>
466Array<T>::~Array() { }
467
468#endif // ARRAY_HPP
Note: See TracBrowser for help on using the repository browser.