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

Last change on this file since 2267 was 2267, checked in by sam, 8 years ago

base: tweak the asserts in the String class, add String::Sub() method
for substrings, and the corresponding unit tests.

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