1/* Copyright (C) 2011-2022 by The D Language Foundation, All Rights Reserved
2 * written by Walter Bright
3 * https://www.digitalmars.com
4 * Distributed under the Boost Software License, Version 1.0.
5 * https://www.boost.org/LICENSE_1_0.txt
6 * https://github.com/dlang/dmd/blob/master/src/dmd/root/array.h
7 */
8
9#pragma once
10
11#include "dsystem.h"
12#include "object.h"
13#include "rmem.h"
14
15template <typename TYPE>
16struct Array
17{
18    d_size_t length;
19
20  private:
21    DArray<TYPE> data;
22    #define SMALLARRAYCAP       1
23    TYPE smallarray[SMALLARRAYCAP];    // inline storage for small arrays
24
25    Array(const Array&);
26
27  public:
28    Array()
29    {
30        data.ptr = NULL;
31        length = 0;
32        data.length = 0;
33    }
34
35    ~Array()
36    {
37        if (data.ptr != &smallarray[0])
38            mem.xfree(data.ptr);
39    }
40
41    char *toChars() const
42    {
43        const char **buf = (const char **)mem.xmalloc(length * sizeof(const char *));
44        d_size_t len = 2;
45        for (d_size_t u = 0; u < length; u++)
46        {
47            buf[u] = ((RootObject *)data.ptr[u])->toChars();
48            len += strlen(buf[u]) + 1;
49        }
50        char *str = (char *)mem.xmalloc(len);
51
52        str[0] = '[';
53        char *p = str + 1;
54        for (d_size_t u = 0; u < length; u++)
55        {
56            if (u)
57                *p++ = ',';
58            len = strlen(buf[u]);
59            memcpy(p,buf[u],len);
60            p += len;
61        }
62        *p++ = ']';
63        *p = 0;
64        mem.xfree(buf);
65        return str;
66    }
67
68    void push(TYPE ptr)
69    {
70        reserve(1);
71        data.ptr[length++] = ptr;
72    }
73
74    void append(Array *a)
75    {
76        insert(length, a);
77    }
78
79    void reserve(d_size_t nentries)
80    {
81        //printf("Array::reserve: length = %d, data.length = %d, nentries = %d\n", (int)length, (int)data.length, (int)nentries);
82        if (data.length - length < nentries)
83        {
84            if (data.length == 0)
85            {
86                // Not properly initialized, someone memset it to zero
87                if (nentries <= SMALLARRAYCAP)
88                {
89                    data.length = SMALLARRAYCAP;
90                    data.ptr = SMALLARRAYCAP ? &smallarray[0] : NULL;
91                }
92                else
93                {
94                    data.length = nentries;
95                    data.ptr = (TYPE *)mem.xmalloc(data.length * sizeof(TYPE));
96                }
97            }
98            else if (data.length == SMALLARRAYCAP)
99            {
100                data.length = length + nentries;
101                data.ptr = (TYPE *)mem.xmalloc(data.length * sizeof(TYPE));
102                memcpy(data.ptr, &smallarray[0], length * sizeof(TYPE));
103            }
104            else
105            {
106                /* Increase size by 1.5x to avoid excessive memory fragmentation
107                 */
108                d_size_t increment = length / 2;
109                if (nentries > increment)       // if 1.5 is not enough
110                    increment = nentries;
111                data.length = length + increment;
112                data.ptr = (TYPE *)mem.xrealloc(data.ptr, data.length * sizeof(TYPE));
113            }
114        }
115    }
116
117    void remove(d_size_t i)
118    {
119        if (length - i - 1)
120            memmove(data.ptr + i, data.ptr + i + 1, (length - i - 1) * sizeof(TYPE));
121        length--;
122    }
123
124    void insert(d_size_t index, Array *a)
125    {
126        if (a)
127        {
128            d_size_t d = a->length;
129            reserve(d);
130            if (length != index)
131                memmove(data.ptr + index + d, data.ptr + index, (length - index) * sizeof(TYPE));
132            memcpy(data.ptr + index, a->data.ptr, d * sizeof(TYPE));
133            length += d;
134        }
135    }
136
137    void insert(d_size_t index, TYPE ptr)
138    {
139        reserve(1);
140        memmove(data.ptr + index + 1, data.ptr + index, (length - index) * sizeof(TYPE));
141        data.ptr[index] = ptr;
142        length++;
143    }
144
145    void setDim(d_size_t newdim)
146    {
147        if (length < newdim)
148        {
149            reserve(newdim - length);
150        }
151        length = newdim;
152    }
153
154    d_size_t find(TYPE ptr) const
155    {
156        for (d_size_t i = 0; i < length; i++)
157        {
158            if (data.ptr[i] == ptr)
159                return i;
160        }
161        return SIZE_MAX;
162    }
163
164    bool contains(TYPE ptr) const
165    {
166        return find(ptr) != SIZE_MAX;
167    }
168
169    TYPE& operator[] (d_size_t index)
170    {
171#ifdef DEBUG
172        assert(index < length);
173#endif
174        return data.ptr[index];
175    }
176
177    TYPE *tdata()
178    {
179        return data.ptr;
180    }
181
182    Array *copy()
183    {
184        Array *a = new Array();
185        a->setDim(length);
186        memcpy(a->data.ptr, data.ptr, length * sizeof(TYPE));
187        return a;
188    }
189
190    void shift(TYPE ptr)
191    {
192        reserve(1);
193        memmove(data.ptr + 1, data.ptr, length * sizeof(TYPE));
194        data.ptr[0] = ptr;
195        length++;
196    }
197
198    void zero()
199    {
200        memset(data.ptr, 0, length * sizeof(TYPE));
201    }
202
203    TYPE pop()
204    {
205        return data.ptr[--length];
206    }
207};
208