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

Last change on this file since 2780 was 2780, checked in by sam, 6 years ago

base: Array::Pop() returns the popped element.

  • Property svn:keywords set to Id
File size: 16.8 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 <lol/base/assert.h>
22
23#include <new>
24#include <stdint.h>
25
26namespace lol
27{
28
29/*
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.
34 */
35
36template<typename T, typename ARRAY> class ArrayBase
37{
38public:
39    typedef T Element;
40
41    inline ArrayBase() : m_data(0), m_count(0), m_reserved(0)
42    {
43    }
44
45    inline ~ArrayBase()
46    {
47        for (int i = 0; i < m_count; i++)
48            m_data[i].~Element();
49        delete[] reinterpret_cast<uint8_t *>(m_data);
50    }
51
52    ArrayBase(ArrayBase const& that) : m_data(0), m_count(0), m_reserved(0)
53    {
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]);
59        m_count = that.m_count;
60    }
61
62    ArrayBase& operator=(ArrayBase const& that)
63    {
64        if ((uintptr_t)this != (uintptr_t)&that)
65        {
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. */
69            if (m_reserved < that.m_count)
70            {
71                /* If not enough space, reserve memory, overwrite the first
72                 * elements, then use placement new directly for the
73                 * remaining elements. */
74                Reserve(that.m_count);
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++)
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        }
95        return *this;
96    }
97
98    ArrayBase& operator+=(ArrayBase const &that)
99    {
100        int todo = that.m_count;
101        Reserve(m_count + that.m_count);
102        for (int i = 0; i < todo; i++)
103            new(&m_data[m_count + i]) Element(that[i]);
104        m_count += todo;
105        return *this;
106    }
107
108    ARRAY operator+(ARRAY const &that) const
109    {
110        ARRAY ret;
111        ret.Reserve(m_count + that.m_count);
112        ret += *this;
113        ret += that;
114        return ret;
115    }
116
117    inline Element& operator[](int n)
118    {
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);
122        ASSERT((unsigned)n < (unsigned)m_count || (!n && !m_count));
123        return m_data[n];
124    }
125
126    inline Element const& operator[](int n) const
127    {
128        ASSERT(n >= 0);
129        ASSERT(n < m_count || (!n && !m_count));
130        return m_data[n];
131    }
132
133    inline Element& Last()
134    {
135        ASSERT(m_count > 0);
136        return m_data[m_count - 1];
137    }
138
139    inline Element const& Last() const
140    {
141        ASSERT(m_count > 0);
142        return m_data[m_count - 1];
143    }
144
145    inline ArrayBase& operator<<(T const &x)
146    {
147        if (m_count >= m_reserved)
148        {
149            T tmp = x;
150            Reserve(m_count * 13 / 8 + 8);
151            new (&m_data[m_count++]) Element(tmp);
152        }
153        else
154        {
155            new (&m_data[m_count++]) Element(x);
156        }
157        return *this;
158    }
159
160    inline void Push(T const &x)
161    {
162        *this << x;
163    }
164
165    inline T Pop()
166    {
167        ASSERT(m_count > 0);
168        Element tmp = Last();
169        Remove(m_count - 1, 1);
170        return tmp;
171    }
172
173    void Swap(int pos1, int pos2)
174    {
175        ASSERT(pos1 >= 0);
176        ASSERT(pos2 >= 0);
177        ASSERT(pos1 < m_count);
178        ASSERT(pos2 < m_count);
179
180        if (pos1 != pos2)
181        {
182            Element tmp = (*this)[pos1];
183            (*this)[pos1] = (*this)[pos2];
184            (*this)[pos2] = tmp;
185        }
186    }
187
188    void Remove(int pos, int todelete = 1)
189    {
190        ASSERT(pos >= 0);
191        ASSERT(todelete >= 0);
192        ASSERT(pos + todelete <= m_count);
193        for (int i = pos; i + todelete < m_count; i++)
194            m_data[i] = m_data[i + todelete];
195        for (int i = m_count - todelete; i < m_count; i++)
196            m_data[i].~Element();
197        m_count -= todelete;
198    }
199
200    void Resize(int count, Element e = Element())
201    {
202        ASSERT(count > 0);
203        Reserve(count);
204
205        /* Too many elements? Remove them. */
206        for (int i = count; i < m_count; ++i)
207            m_data[i].~Element();
208
209        /* Not enough elements? Add some. */
210        for (int i = m_count; i < count; ++i)
211            new(&m_data[i]) Element(e);
212
213        m_count = count;
214    }
215
216    inline void Empty()
217    {
218        Remove(0, m_count);
219    }
220
221    void Reserve(int toreserve)
222    {
223        if (toreserve <= (int)m_reserved)
224            return;
225
226        /* This cast is not very nice, because we kill any alignment
227         * information we could have. But until C++ gives us the proper
228         * tools to deal with it, we assume new uint8_t[] returns properly
229         * aligned data. */
230        Element *tmp = reinterpret_cast<Element *>(reinterpret_cast<uintptr_t>
231                               (new uint8_t[sizeof(Element) * toreserve]));
232        for (int i = 0; i < m_count; i++)
233        {
234            new(&tmp[i]) Element(m_data[i]);
235            m_data[i].~Element();
236        }
237        if (m_data)
238            delete[] reinterpret_cast<uint8_t *>(m_data);
239        m_data = tmp;
240        m_reserved = toreserve;
241    }
242
243    inline int Count() const { return m_count; }
244    inline int Bytes() const { return m_count * sizeof(Element); }
245
246protected:
247    Element *m_data;
248    int m_count, m_reserved;
249};
250
251/*
252 * Element types
253 */
254
255template<typename T1, typename T2, typename T3 = void, typename T4 = void,
256         typename T5 = void, typename T6 = void, typename T7 = void,
257         typename T8 = void>
258class ArrayElement
259{
260public:
261    T1 m1; T2 m2; T3 m3; T4 m4; T5 m5; T6 m6; T7 m7; T8 m8;
262};
263
264template<typename T1, typename T2, typename T3, typename T4, typename T5,
265         typename T6, typename T7>
266class ArrayElement<T1, T2, T3, T4, T5, T6, T7, void>
267{
268public:
269    T1 m1; T2 m2; T3 m3; T4 m4; T5 m5; T6 m6; T7 m7;
270};
271
272template<typename T1, typename T2, typename T3, typename T4, typename T5,
273         typename T6>
274class ArrayElement<T1, T2, T3, T4, T5, T6, void, void>
275{
276public:
277    T1 m1; T2 m2; T3 m3; T4 m4; T5 m5; T6 m6;
278};
279
280template<typename T1, typename T2, typename T3, typename T4, typename T5>
281class ArrayElement<T1, T2, T3, T4, T5, void, void, void>
282{
283public:
284    T1 m1; T2 m2; T3 m3; T4 m4; T5 m5;
285};
286
287template<typename T1, typename T2, typename T3, typename T4>
288class ArrayElement<T1, T2, T3, T4, void, void, void, void>
289{
290public:
291    T1 m1; T2 m2; T3 m3; T4 m4;
292};
293
294template<typename T1, typename T2, typename T3>
295class ArrayElement<T1, T2, T3, void, void, void, void, void>
296{
297public:
298    T1 m1; T2 m2; T3 m3;
299};
300
301template<typename T1, typename T2>
302class ArrayElement<T1, T2, void, void, void, void, void, void>
303{
304public:
305    T1 m1; T2 m2;
306};
307
308/*
309 * Array specialisations implementing specific setters
310 */
311
312template<typename T1, typename T2 = void, typename T3 = void,
313         typename T4 = void, typename T5 = void, typename T6 = void,
314         typename T7 = void, typename T8 = void>
315class Array : public ArrayBase<ArrayElement<T1, T2, T3, T4, T5, T6, T7, T8>,
316                               Array<T1, T2, T3, T4, T5, T6, T7, T8> >
317{
318public:
319    inline void Push(T1 const &m1, T2 const &m2, T3 const &m3, T4 const &m4,
320                     T5 const &m5, T6 const &m6, T7 const &m7, T8 const &m8)
321    {
322        if (this->m_count >= this->m_reserved)
323        {
324            T1 tmp1 = m1; T2 tmp2 = m2; T3 tmp3 = m3; T4 tmp4 = m4;
325            T5 tmp5 = m5; T6 tmp6 = m6; T7 tmp7 = m7; T8 tmp8 = m8;
326            this->Reserve(this->m_count * 13 / 8 + 8);
327            new (&this->m_data[this->m_count].m1) T1(tmp1);
328            new (&this->m_data[this->m_count].m2) T2(tmp2);
329            new (&this->m_data[this->m_count].m3) T3(tmp3);
330            new (&this->m_data[this->m_count].m4) T4(tmp4);
331            new (&this->m_data[this->m_count].m5) T5(tmp5);
332            new (&this->m_data[this->m_count].m6) T6(tmp6);
333            new (&this->m_data[this->m_count].m7) T7(tmp7);
334            new (&this->m_data[this->m_count].m8) T8(tmp8);
335        }
336        else
337        {
338            new (&this->m_data[this->m_count].m1) T1(m1);
339            new (&this->m_data[this->m_count].m2) T2(m2);
340            new (&this->m_data[this->m_count].m3) T3(m3);
341            new (&this->m_data[this->m_count].m4) T4(m4);
342            new (&this->m_data[this->m_count].m5) T5(m5);
343            new (&this->m_data[this->m_count].m6) T6(m6);
344            new (&this->m_data[this->m_count].m7) T7(m7);
345            new (&this->m_data[this->m_count].m8) T8(m8);
346        }
347        ++this->m_count;
348    }
349};
350
351template<typename T1, typename T2, typename T3, typename T4, typename T5,
352         typename T6, typename T7>
353class Array<T1, T2, T3, T4, T5, T6, T7, void>
354  : public ArrayBase<ArrayElement<T1, T2, T3, T4, T5, T6, T7, void>,
355                     Array<T1, T2, T3, T4, T5, T6, T7> >
356{
357public:
358    inline void Push(T1 const &m1, T2 const &m2, T3 const &m3, T4 const &m4,
359                     T5 const &m5, T6 const &m6, T7 const &m7)
360    {
361        if (this->m_count >= this->m_reserved)
362        {
363            T1 tmp1 = m1; T2 tmp2 = m2; T3 tmp3 = m3; T4 tmp4 = m4;
364            T5 tmp5 = m5; T6 tmp6 = m6; T7 tmp7 = m7;
365            this->Reserve(this->m_count * 13 / 8 + 8);
366            new (&this->m_data[this->m_count].m1) T1(tmp1);
367            new (&this->m_data[this->m_count].m2) T2(tmp2);
368            new (&this->m_data[this->m_count].m3) T3(tmp3);
369            new (&this->m_data[this->m_count].m4) T4(tmp4);
370            new (&this->m_data[this->m_count].m5) T5(tmp5);
371            new (&this->m_data[this->m_count].m6) T6(tmp6);
372            new (&this->m_data[this->m_count].m7) T7(tmp7);
373        }
374        else
375        {
376            new (&this->m_data[this->m_count].m1) T1(m1);
377            new (&this->m_data[this->m_count].m2) T2(m2);
378            new (&this->m_data[this->m_count].m3) T3(m3);
379            new (&this->m_data[this->m_count].m4) T4(m4);
380            new (&this->m_data[this->m_count].m5) T5(m5);
381            new (&this->m_data[this->m_count].m6) T6(m6);
382            new (&this->m_data[this->m_count].m7) T7(m7);
383        }
384        ++this->m_count;
385    }
386};
387
388template<typename T1, typename T2, typename T3, typename T4, typename T5,
389         typename T6>
390class Array<T1, T2, T3, T4, T5, T6, void, void>
391  : public ArrayBase<ArrayElement<T1, T2, T3, T4, T5, T6, void, void>,
392                     Array<T1, T2, T3, T4, T5, T6> >
393{
394public:
395    inline void Push(T1 const &m1, T2 const &m2, T3 const &m3, T4 const &m4,
396                     T5 const &m5, T6 const &m6)
397    {
398        if (this->m_count >= this->m_reserved)
399        {
400            T1 tmp1 = m1; T2 tmp2 = m2; T3 tmp3 = m3; T4 tmp4 = m4;
401            T5 tmp5 = m5; T6 tmp6 = m6;
402            this->Reserve(this->m_count * 13 / 8 + 8);
403            new (&this->m_data[this->m_count].m1) T1(tmp1);
404            new (&this->m_data[this->m_count].m2) T2(tmp2);
405            new (&this->m_data[this->m_count].m3) T3(tmp3);
406            new (&this->m_data[this->m_count].m4) T4(tmp4);
407            new (&this->m_data[this->m_count].m5) T5(tmp5);
408            new (&this->m_data[this->m_count].m6) T6(tmp6);
409        }
410        else
411        {
412            new (&this->m_data[this->m_count].m1) T1(m1);
413            new (&this->m_data[this->m_count].m2) T2(m2);
414            new (&this->m_data[this->m_count].m3) T3(m3);
415            new (&this->m_data[this->m_count].m4) T4(m4);
416            new (&this->m_data[this->m_count].m5) T5(m5);
417            new (&this->m_data[this->m_count].m6) T6(m6);
418        }
419        ++this->m_count;
420    }
421};
422
423template<typename T1, typename T2, typename T3, typename T4, typename T5>
424class Array<T1, T2, T3, T4, T5, void, void, void>
425  : public ArrayBase<ArrayElement<T1, T2, T3, T4, T5, void, void, void>,
426                     Array<T1, T2, T3, T4, T5> >
427{
428public:
429    inline void Push(T1 const &m1, T2 const &m2, T3 const &m3, T4 const &m4,
430                     T5 const &m5)
431    {
432        if (this->m_count >= this->m_reserved)
433        {
434            T1 tmp1 = m1; T2 tmp2 = m2; T3 tmp3 = m3; T4 tmp4 = m4;
435            T5 tmp5 = m5;
436            this->Reserve(this->m_count * 13 / 8 + 8);
437            new (&this->m_data[this->m_count].m1) T1(tmp1);
438            new (&this->m_data[this->m_count].m2) T2(tmp2);
439            new (&this->m_data[this->m_count].m3) T3(tmp3);
440            new (&this->m_data[this->m_count].m4) T4(tmp4);
441            new (&this->m_data[this->m_count].m5) T5(tmp5);
442        }
443        else
444        {
445            new (&this->m_data[this->m_count].m1) T1(m1);
446            new (&this->m_data[this->m_count].m2) T2(m2);
447            new (&this->m_data[this->m_count].m3) T3(m3);
448            new (&this->m_data[this->m_count].m4) T4(m4);
449            new (&this->m_data[this->m_count].m5) T5(m5);
450        }
451        ++this->m_count;
452    }
453};
454
455template<typename T1, typename T2, typename T3, typename T4>
456class Array<T1, T2, T3, T4, void, void, void, void>
457  : public ArrayBase<ArrayElement<T1, T2, T3, T4, void, void, void, void>,
458                     Array<T1, T2, T3, T4> >
459{
460public:
461    inline void Push(T1 const &m1, T2 const &m2, T3 const &m3, T4 const &m4)
462    {
463        if (this->m_count >= this->m_reserved)
464        {
465            T1 tmp1 = m1; T2 tmp2 = m2; T3 tmp3 = m3; T4 tmp4 = m4;
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            new (&this->m_data[this->m_count].m4) T4(tmp4);
471        }
472        else
473        {
474            new (&this->m_data[this->m_count].m1) T1(m1);
475            new (&this->m_data[this->m_count].m2) T2(m2);
476            new (&this->m_data[this->m_count].m3) T3(m3);
477            new (&this->m_data[this->m_count].m4) T4(m4);
478        }
479        ++this->m_count;
480    }
481};
482
483template<typename T1, typename T2, typename T3>
484class Array<T1, T2, T3, void, void, void, void, void>
485  : public ArrayBase<ArrayElement<T1, T2, T3, void, void, void, void, void>,
486                     Array<T1, T2, T3> >
487{
488public:
489    inline void Push(T1 const &m1, T2 const &m2, T3 const &m3)
490    {
491        if (this->m_count >= this->m_reserved)
492        {
493            T1 tmp1 = m1; T2 tmp2 = m2; T3 tmp3 = m3;
494            this->Reserve(this->m_count * 13 / 8 + 8);
495            new (&this->m_data[this->m_count].m1) T1(tmp1);
496            new (&this->m_data[this->m_count].m2) T2(tmp2);
497            new (&this->m_data[this->m_count].m3) T3(tmp3);
498        }
499        else
500        {
501            new (&this->m_data[this->m_count].m1) T1(m1);
502            new (&this->m_data[this->m_count].m2) T2(m2);
503            new (&this->m_data[this->m_count].m3) T3(m3);
504        }
505        ++this->m_count;
506    }
507};
508
509template<typename T1, typename T2>
510class Array<T1, T2, void, void, void, void, void, void>
511  : public ArrayBase<ArrayElement<T1, T2, void, void, void, void, void, void>,
512                     Array<T1, T2> >
513{
514public:
515    inline void Push(T1 const &m1, T2 const &m2)
516    {
517        if (this->m_count >= this->m_reserved)
518        {
519            T1 tmp1 = m1; T2 tmp2 = m2;
520            this->Reserve(this->m_count * 13 / 8 + 8);
521            new (&this->m_data[this->m_count].m1) T1(tmp1);
522            new (&this->m_data[this->m_count].m2) T2(tmp2);
523        }
524        else
525        {
526            new (&this->m_data[this->m_count].m1) T1(m1);
527            new (&this->m_data[this->m_count].m2) T2(m2);
528        }
529        ++this->m_count;
530    }
531};
532
533template<typename T>
534class Array<T, void, void, void, void, void, void, void>
535  : public ArrayBase<T,
536                     Array<T> >
537{
538};
539
540} /* namespace lol */
541
542#endif // __LOL_BASE_ARRAY_H__
543
Note: See TracBrowser for help on using the repository browser.