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

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

base: work around an annoying GCC warning we very well know about.

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