1 /* Copyright (C) 2011-2021 by The D Language Foundation, All Rights Reserved
2  * written by Walter Bright
3  * http://www.digitalmars.com
4  * Distributed under the Boost Software License, Version 1.0.
5  * http://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 
15 template <typename TYPE>
16 struct 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:
ArrayArray28     Array()
29     {
30         data.ptr = NULL;
31         length = 0;
32         data.length = 0;
33     }
34 
~ArrayArray35     ~Array()
36     {
37         if (data.ptr != &smallarray[0])
38             mem.xfree(data.ptr);
39     }
40 
toCharsArray41     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 
pushArray68     void push(TYPE ptr)
69     {
70         reserve(1);
71         data.ptr[length++] = ptr;
72     }
73 
appendArray74     void append(Array *a)
75     {
76         insert(length, a);
77     }
78 
reserveArray79     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 
removeArray117     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 
insertArray124     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 
insertArray137     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 
setDimArray145     void setDim(d_size_t newdim)
146     {
147         if (length < newdim)
148         {
149             reserve(newdim - length);
150         }
151         length = newdim;
152     }
153 
findArray154     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 
containsArray164     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 
tdataArray177     TYPE *tdata()
178     {
179         return data.ptr;
180     }
181 
copyArray182     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 
shiftArray190     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 
zeroArray198     void zero()
199     {
200         memset(data.ptr, 0, length * sizeof(TYPE));
201     }
202 
popArray203     TYPE pop()
204     {
205         return data.ptr[--length];
206     }
207 };
208 
209