source: trunk/src/lol/base/array.h @ 2261

Last change on this file since 2261 was 2261, checked in by sam, 7 years ago

base: fix header guard names.

  • Property svn:keywords set to Id
File size: 16.2 KB
Line 
1//
2// Lol Engine
3//
4// Copyright: (c) 2010-2013 Sam Hocevar <sam@hocevar.net>
5//   This program is free software; you can redistribute it and/or
6//   modify it under the terms of the Do What The Fuck You Want To
7//   Public License, Version 2, as published by Sam Hocevar. See
8//   http://www.wtfpl.net/ for more details.
9//
10
11//
12// The Array class
13// ---------------
14// A very simple Array class not unlike the std::vector, with some nice
15// additional features, eg. Array<int,float> for automatic arrays of structs.
16//
17
18#if !defined __LOL_BASE_ARRAY_H__
19#define __LOL_BASE_ARRAY_H__
20
21#include <new>
22#include <stdint.h>
23
24namespace lol
25{
26
27/*
28 * The base array type.
29 *
30 * Contains an m_data memory array of Elements, of which only the first
31 * m_count are allocated. The rest is uninitialised memory.
32 */
33
34template<typename T, typename ARRAY> class ArrayBase
35{
36public:
37    typedef T Element;
38
39    inline ArrayBase() : m_data(0), m_count(0), m_reserved(0)
40    {
41    }
42
43    inline ~ArrayBase()
44    {
45        for (int i = 0; i < m_count; i++)
46            m_data[i].~Element();
47        delete[] reinterpret_cast<uint8_t *>(m_data);
48    }
49
50    ArrayBase(ArrayBase const& that) : m_data(0), m_count(0), m_reserved(0)
51    {
52        /* Reserve the exact number of values instead of what the other
53         * array had reserved. Just a method for not wasting too much. */
54        Reserve(that.m_count);
55        for (int i = 0; i < that.m_count; i++)
56            new(&m_data[i]) Element(that[i]);
57        m_count = that.m_count;
58    }
59
60    ArrayBase& operator=(ArrayBase const& that)
61    {
62        if ((uintptr_t)this != (uintptr_t)&that)
63        {
64            /* FIXME: there is an opportunity for optimisation here if we
65             * find a way to ask Reserve not to create new elements, since
66             * we're going to overwrite them anyway. */
67            if (m_reserved < that.m_count)
68            {
69                /* If not enough space, reserve memory, overwrite the first
70                 * elements, then use placement new directly for the
71                 * remaining elements. */
72                Reserve(that.m_count);
73                for (int i = 0; i < m_count && i < that.m_count; i++)
74                    m_data[i] = Element(that[i]);
75                for (int i = m_count; i < that.m_count; i++)
76                    new(&m_data[i]) Element(that[i]);
77            }
78            else
79            {
80                /* If enough space, overwrite the common elements, then
81                 * use placement new for the elements in the other array
82                 * that we do not have, and finally destroy the remaining
83                 * elements. */
84                for (int i = 0; i < m_count && i < that.m_count; i++)
85                    m_data[i] = Element(that[i]);
86                for (int i = m_count; i < that.m_count; i++)
87                    new(&m_data[i]) Element(that[i]);
88                for (int i = that.m_count; i < m_count; i++)
89                    m_data[i].~Element();
90            }
91            m_count = that.m_count;
92        }
93        return *this;
94    }
95
96    ArrayBase& operator+=(ARRAY const &that)
97    {
98        int todo = that.m_count;
99        Reserve(m_count + that.m_count);
100        for (int i = 0; i < todo; i++)
101            *this << that[i];
102        return *this;
103    }
104
105    ARRAY operator+(ARRAY const &that) const
106    {
107        /* FIXME: upon return, this makes a copy of the temporary object;
108         * use either C++11 move semantics, or add a special flag to the
109         * object indicating we're a temporary about to be destroyed */
110        ARRAY ret;
111        ret.Reserve(m_count + that.m_count);
112        for (int i = 0; i < m_count; i++)
113            ret << (*this)[i];
114        for (int i = 0; i < that.m_count; i++)
115            ret << that[i];
116        return ret;
117    }
118
119    inline Element& operator[](int n)
120    {
121        return m_data[n];
122    }
123
124    inline Element const& operator[](int n) const
125    {
126        return m_data[n];
127    }
128
129    inline Element& Last()
130    {
131        return m_data[m_count - 1];
132    }
133
134    inline Element const& Last() const
135    {
136        return m_data[m_count - 1];
137    }
138
139    inline ArrayBase& operator<<(T const &x)
140    {
141        if (m_count >= m_reserved)
142        {
143            T tmp = x;
144            Reserve(m_count * 13 / 8 + 8);
145            new (&m_data[m_count++]) Element(tmp);
146        }
147        else
148        {
149            new (&m_data[m_count++]) Element(x);
150        }
151        return *this;
152    }
153
154    inline void Push(T const &x)
155    {
156        *this << x;
157    }
158
159    inline void Pop()
160    {
161        Remove(m_count - 1, 1);
162    }
163
164    void Remove(int pos, int todelete = 1)
165    {
166        for (int i = pos; i + todelete < m_count; i++)
167            m_data[i] = m_data[i + todelete];
168        for (int i = m_count - todelete; i < m_count; i++)
169            m_data[i].~Element();
170        m_count -= todelete;
171    }
172
173    void Resize(int count, Element e = Element())
174    {
175        Reserve(count);
176
177        /* Too many elements? Remove them. */
178        for (int i = count; i < m_count; ++i)
179            m_data[i].~Element();
180
181        /* Not enough elements? Add some. */
182        for (int i = m_count; i < count; ++i)
183            new(&m_data[i]) Element(e);
184
185        m_count = count;
186    }
187
188    inline void Empty()
189    {
190        Remove(0, m_count);
191    }
192
193    void Reserve(int toreserve)
194    {
195        if (toreserve <= (int)m_reserved)
196            return;
197
198        /* This cast is not very nice, because we kill any alignment
199         * information we could have. But until C++ gives us the proper
200         * tools to deal with it, we assume new uint8_t[] returns properly
201         * aligned data. */
202        Element *tmp = reinterpret_cast<Element *>(reinterpret_cast<uintptr_t>
203                               (new uint8_t[sizeof(Element) * toreserve]));
204        for (int i = 0; i < m_count; i++)
205        {
206            new(&tmp[i]) Element(m_data[i]);
207            m_data[i].~Element();
208        }
209        if (m_data)
210            delete[] reinterpret_cast<uint8_t *>(m_data);
211        m_data = tmp;
212        m_reserved = toreserve;
213    }
214
215    inline int Count() const { return m_count; }
216    inline int Bytes() const { return m_count * sizeof(Element); }
217
218protected:
219    Element *m_data;
220    int m_count, m_reserved;
221};
222
223/*
224 * Element types
225 */
226
227template<typename T1, typename T2, typename T3 = void, typename T4 = void,
228         typename T5 = void, typename T6 = void, typename T7 = void,
229         typename T8 = void>
230class ArrayElement
231{
232public:
233    T1 m1; T2 m2; T3 m3; T4 m4; T5 m5; T6 m6; T7 m7; T8 m8;
234};
235
236template<typename T1, typename T2, typename T3, typename T4, typename T5,
237         typename T6, typename T7>
238class ArrayElement<T1, T2, T3, T4, T5, T6, T7, void>
239{
240public:
241    T1 m1; T2 m2; T3 m3; T4 m4; T5 m5; T6 m6; T7 m7;
242};
243
244template<typename T1, typename T2, typename T3, typename T4, typename T5,
245         typename T6>
246class ArrayElement<T1, T2, T3, T4, T5, T6, void, void>
247{
248public:
249    T1 m1; T2 m2; T3 m3; T4 m4; T5 m5; T6 m6;
250};
251
252template<typename T1, typename T2, typename T3, typename T4, typename T5>
253class ArrayElement<T1, T2, T3, T4, T5, void, void, void>
254{
255public:
256    T1 m1; T2 m2; T3 m3; T4 m4; T5 m5;
257};
258
259template<typename T1, typename T2, typename T3, typename T4>
260class ArrayElement<T1, T2, T3, T4, void, void, void, void>
261{
262public:
263    T1 m1; T2 m2; T3 m3; T4 m4;
264};
265
266template<typename T1, typename T2, typename T3>
267class ArrayElement<T1, T2, T3, void, void, void, void, void>
268{
269public:
270    T1 m1; T2 m2; T3 m3;
271};
272
273template<typename T1, typename T2>
274class ArrayElement<T1, T2, void, void, void, void, void, void>
275{
276public:
277    T1 m1; T2 m2;
278};
279
280/*
281 * Array specialisations implementing specific setters
282 */
283
284template<typename T1, typename T2 = void, typename T3 = void,
285         typename T4 = void, typename T5 = void, typename T6 = void,
286         typename T7 = void, typename T8 = void>
287class Array : public ArrayBase<ArrayElement<T1, T2, T3, T4, T5, T6, T7, T8>,
288                               Array<T1, T2, T3, T4, T5, T6, T7, T8> >
289{
290public:
291    inline void Push(T1 const &m1, T2 const &m2, T3 const &m3, T4 const &m4,
292                     T5 const &m5, T6 const &m6, T7 const &m7, T8 const &m8)
293    {
294        if (this->m_count >= this->m_reserved)
295        {
296            T1 tmp1 = m1; T2 tmp2 = m2; T3 tmp3 = m3; T4 tmp4 = m4;
297            T5 tmp5 = m5; T6 tmp6 = m6; T7 tmp7 = m7; T8 tmp8 = m8;
298            this->Reserve(this->m_count * 13 / 8 + 8);
299            new (&this->m_data[this->m_count].m1) T1(tmp1);
300            new (&this->m_data[this->m_count].m2) T2(tmp2);
301            new (&this->m_data[this->m_count].m3) T3(tmp3);
302            new (&this->m_data[this->m_count].m4) T4(tmp4);
303            new (&this->m_data[this->m_count].m5) T5(tmp5);
304            new (&this->m_data[this->m_count].m6) T6(tmp6);
305            new (&this->m_data[this->m_count].m7) T7(tmp7);
306            new (&this->m_data[this->m_count].m8) T8(tmp8);
307        }
308        else
309        {
310            new (&this->m_data[this->m_count].m1) T1(m1);
311            new (&this->m_data[this->m_count].m2) T2(m2);
312            new (&this->m_data[this->m_count].m3) T3(m3);
313            new (&this->m_data[this->m_count].m4) T4(m4);
314            new (&this->m_data[this->m_count].m5) T5(m5);
315            new (&this->m_data[this->m_count].m6) T6(m6);
316            new (&this->m_data[this->m_count].m7) T7(m7);
317            new (&this->m_data[this->m_count].m8) T8(m8);
318        }
319        ++this->m_count;
320    }
321};
322
323template<typename T1, typename T2, typename T3, typename T4, typename T5,
324         typename T6, typename T7>
325class Array<T1, T2, T3, T4, T5, T6, T7, void>
326  : public ArrayBase<ArrayElement<T1, T2, T3, T4, T5, T6, T7, void>,
327                     Array<T1, T2, T3, T4, T5, T6, T7> >
328{
329public:
330    inline void Push(T1 const &m1, T2 const &m2, T3 const &m3, T4 const &m4,
331                     T5 const &m5, T6 const &m6, T7 const &m7)
332    {
333        if (this->m_count >= this->m_reserved)
334        {
335            T1 tmp1 = m1; T2 tmp2 = m2; T3 tmp3 = m3; T4 tmp4 = m4;
336            T5 tmp5 = m5; T6 tmp6 = m6; T7 tmp7 = m7;
337            this->Reserve(this->m_count * 13 / 8 + 8);
338            new (&this->m_data[this->m_count].m1) T1(tmp1);
339            new (&this->m_data[this->m_count].m2) T2(tmp2);
340            new (&this->m_data[this->m_count].m3) T3(tmp3);
341            new (&this->m_data[this->m_count].m4) T4(tmp4);
342            new (&this->m_data[this->m_count].m5) T5(tmp5);
343            new (&this->m_data[this->m_count].m6) T6(tmp6);
344            new (&this->m_data[this->m_count].m7) T7(tmp7);
345        }
346        else
347        {
348            new (&this->m_data[this->m_count].m1) T1(m1);
349            new (&this->m_data[this->m_count].m2) T2(m2);
350            new (&this->m_data[this->m_count].m3) T3(m3);
351            new (&this->m_data[this->m_count].m4) T4(m4);
352            new (&this->m_data[this->m_count].m5) T5(m5);
353            new (&this->m_data[this->m_count].m6) T6(m6);
354            new (&this->m_data[this->m_count].m7) T7(m7);
355        }
356        ++this->m_count;
357    }
358};
359
360template<typename T1, typename T2, typename T3, typename T4, typename T5,
361         typename T6>
362class Array<T1, T2, T3, T4, T5, T6, void, void>
363  : public ArrayBase<ArrayElement<T1, T2, T3, T4, T5, T6, void, void>,
364                     Array<T1, T2, T3, T4, T5, T6> >
365{
366public:
367    inline void Push(T1 const &m1, T2 const &m2, T3 const &m3, T4 const &m4,
368                     T5 const &m5, T6 const &m6)
369    {
370        if (this->m_count >= this->m_reserved)
371        {
372            T1 tmp1 = m1; T2 tmp2 = m2; T3 tmp3 = m3; T4 tmp4 = m4;
373            T5 tmp5 = m5; T6 tmp6 = m6;
374            this->Reserve(this->m_count * 13 / 8 + 8);
375            new (&this->m_data[this->m_count].m1) T1(tmp1);
376            new (&this->m_data[this->m_count].m2) T2(tmp2);
377            new (&this->m_data[this->m_count].m3) T3(tmp3);
378            new (&this->m_data[this->m_count].m4) T4(tmp4);
379            new (&this->m_data[this->m_count].m5) T5(tmp5);
380            new (&this->m_data[this->m_count].m6) T6(tmp6);
381        }
382        else
383        {
384            new (&this->m_data[this->m_count].m1) T1(m1);
385            new (&this->m_data[this->m_count].m2) T2(m2);
386            new (&this->m_data[this->m_count].m3) T3(m3);
387            new (&this->m_data[this->m_count].m4) T4(m4);
388            new (&this->m_data[this->m_count].m5) T5(m5);
389            new (&this->m_data[this->m_count].m6) T6(m6);
390        }
391        ++this->m_count;
392    }
393};
394
395template<typename T1, typename T2, typename T3, typename T4, typename T5>
396class Array<T1, T2, T3, T4, T5, void, void, void>
397  : public ArrayBase<ArrayElement<T1, T2, T3, T4, T5, void, void, void>,
398                     Array<T1, T2, T3, T4, T5> >
399{
400public:
401    inline void Push(T1 const &m1, T2 const &m2, T3 const &m3, T4 const &m4,
402                     T5 const &m5)
403    {
404        if (this->m_count >= this->m_reserved)
405        {
406            T1 tmp1 = m1; T2 tmp2 = m2; T3 tmp3 = m3; T4 tmp4 = m4;
407            T5 tmp5 = m5;
408            this->Reserve(this->m_count * 13 / 8 + 8);
409            new (&this->m_data[this->m_count].m1) T1(tmp1);
410            new (&this->m_data[this->m_count].m2) T2(tmp2);
411            new (&this->m_data[this->m_count].m3) T3(tmp3);
412            new (&this->m_data[this->m_count].m4) T4(tmp4);
413            new (&this->m_data[this->m_count].m5) T5(tmp5);
414        }
415        else
416        {
417            new (&this->m_data[this->m_count].m1) T1(m1);
418            new (&this->m_data[this->m_count].m2) T2(m2);
419            new (&this->m_data[this->m_count].m3) T3(m3);
420            new (&this->m_data[this->m_count].m4) T4(m4);
421            new (&this->m_data[this->m_count].m5) T5(m5);
422        }
423        ++this->m_count;
424    }
425};
426
427template<typename T1, typename T2, typename T3, typename T4>
428class Array<T1, T2, T3, T4, void, void, void, void>
429  : public ArrayBase<ArrayElement<T1, T2, T3, T4, void, void, void, void>,
430                     Array<T1, T2, T3, T4> >
431{
432public:
433    inline void Push(T1 const &m1, T2 const &m2, T3 const &m3, T4 const &m4)
434    {
435        if (this->m_count >= this->m_reserved)
436        {
437            T1 tmp1 = m1; T2 tmp2 = m2; T3 tmp3 = m3; T4 tmp4 = m4;
438            this->Reserve(this->m_count * 13 / 8 + 8);
439            new (&this->m_data[this->m_count].m1) T1(tmp1);
440            new (&this->m_data[this->m_count].m2) T2(tmp2);
441            new (&this->m_data[this->m_count].m3) T3(tmp3);
442            new (&this->m_data[this->m_count].m4) T4(tmp4);
443        }
444        else
445        {
446            new (&this->m_data[this->m_count].m1) T1(m1);
447            new (&this->m_data[this->m_count].m2) T2(m2);
448            new (&this->m_data[this->m_count].m3) T3(m3);
449            new (&this->m_data[this->m_count].m4) T4(m4);
450        }
451        ++this->m_count;
452    }
453};
454
455template<typename T1, typename T2, typename T3>
456class Array<T1, T2, T3, void, void, void, void, void>
457  : public ArrayBase<ArrayElement<T1, T2, T3, void, void, void, void, void>,
458                     Array<T1, T2, T3> >
459{
460public:
461    inline void Push(T1 const &m1, T2 const &m2, T3 const &m3)
462    {
463        if (this->m_count >= this->m_reserved)
464        {
465            T1 tmp1 = m1; T2 tmp2 = m2; T3 tmp3 = m3;
466            this->Reserve(this->m_count * 13 / 8 + 8);
467            new (&this->m_data[this->m_count].m1) T1(tmp1);
468            new (&this->m_data[this->m_count].m2) T2(tmp2);
469            new (&this->m_data[this->m_count].m3) T3(tmp3);
470        }
471        else
472        {
473            new (&this->m_data[this->m_count].m1) T1(m1);
474            new (&this->m_data[this->m_count].m2) T2(m2);
475            new (&this->m_data[this->m_count].m3) T3(m3);
476        }
477        ++this->m_count;
478    }
479};
480
481template<typename T1, typename T2>
482class Array<T1, T2, void, void, void, void, void, void>
483  : public ArrayBase<ArrayElement<T1, T2, void, void, void, void, void, void>,
484                     Array<T1, T2> >
485{
486public:
487    inline void Push(T1 const &m1, T2 const &m2)
488    {
489        if (this->m_count >= this->m_reserved)
490        {
491            T1 tmp1 = m1; T2 tmp2 = m2;
492            this->Reserve(this->m_count * 13 / 8 + 8);
493            new (&this->m_data[this->m_count].m1) T1(tmp1);
494            new (&this->m_data[this->m_count].m2) T2(tmp2);
495        }
496        else
497        {
498            new (&this->m_data[this->m_count].m1) T1(m1);
499            new (&this->m_data[this->m_count].m2) T2(m2);
500        }
501        ++this->m_count;
502    }
503};
504
505template<typename T>
506class Array<T, void, void, void, void, void, void, void>
507  : public ArrayBase<T,
508                     Array<T> >
509{
510};
511
512} /* namespace lol */
513
514#endif // __LOL_BASE_ARRAY_H__
515
Note: See TracBrowser for help on using the repository browser.