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 "dcompat.h"
13 #include "object.h"
14 #include "rmem.h"
15 
16 template <typename TYPE>
17 struct Array
18 {
19     size_t length;
20 
21   private:
22     DArray<TYPE> data;
23     #define SMALLARRAYCAP       1
24     TYPE smallarray[SMALLARRAYCAP];    // inline storage for small arrays
25 
26     Array(const Array&);
27 
28   public:
ArrayArray29     Array()
30     {
31         data.ptr = NULL;
32         length = 0;
33         data.length = 0;
34     }
35 
~ArrayArray36     ~Array()
37     {
38         if (data.ptr != &smallarray[0])
39             mem.xfree(data.ptr);
40     }
41 
toCharsArray42     char *toChars() const
43     {
44         const char **buf = (const char **)mem.xmalloc(length * sizeof(const char *));
45         size_t len = 2;
46         for (size_t u = 0; u < length; u++)
47         {
48             buf[u] = ((RootObject *)data.ptr[u])->toChars();
49             len += strlen(buf[u]) + 1;
50         }
51         char *str = (char *)mem.xmalloc(len);
52 
53         str[0] = '[';
54         char *p = str + 1;
55         for (size_t u = 0; u < length; u++)
56         {
57             if (u)
58                 *p++ = ',';
59             len = strlen(buf[u]);
60             memcpy(p,buf[u],len);
61             p += len;
62         }
63         *p++ = ']';
64         *p = 0;
65         mem.xfree(buf);
66         return str;
67     }
68 
pushArray69     void push(TYPE ptr)
70     {
71         reserve(1);
72         data.ptr[length++] = ptr;
73     }
74 
appendArray75     void append(Array *a)
76     {
77         insert(length, a);
78     }
79 
reserveArray80     void reserve(size_t nentries)
81     {
82         //printf("Array::reserve: length = %d, data.length = %d, nentries = %d\n", (int)length, (int)data.length, (int)nentries);
83         if (data.length - length < nentries)
84         {
85             if (data.length == 0)
86             {
87                 // Not properly initialized, someone memset it to zero
88                 if (nentries <= SMALLARRAYCAP)
89                 {
90                     data.length = SMALLARRAYCAP;
91                     data.ptr = SMALLARRAYCAP ? &smallarray[0] : NULL;
92                 }
93                 else
94                 {
95                     data.length = nentries;
96                     data.ptr = (TYPE *)mem.xmalloc(data.length * sizeof(TYPE));
97                 }
98             }
99             else if (data.length == SMALLARRAYCAP)
100             {
101                 data.length = length + nentries;
102                 data.ptr = (TYPE *)mem.xmalloc(data.length * sizeof(TYPE));
103                 memcpy(data.ptr, &smallarray[0], length * sizeof(TYPE));
104             }
105             else
106             {
107                 /* Increase size by 1.5x to avoid excessive memory fragmentation
108                  */
109                 size_t increment = length / 2;
110                 if (nentries > increment)       // if 1.5 is not enough
111                     increment = nentries;
112                 data.length = length + increment;
113                 data.ptr = (TYPE *)mem.xrealloc(data.ptr, data.length * sizeof(TYPE));
114             }
115         }
116     }
117 
removeArray118     void remove(size_t i)
119     {
120         if (length - i - 1)
121             memmove(data.ptr + i, data.ptr + i + 1, (length - i - 1) * sizeof(TYPE));
122         length--;
123     }
124 
insertArray125     void insert(size_t index, Array *a)
126     {
127         if (a)
128         {
129             size_t d = a->length;
130             reserve(d);
131             if (length != index)
132                 memmove(data.ptr + index + d, data.ptr + index, (length - index) * sizeof(TYPE));
133             memcpy(data.ptr + index, a->data.ptr, d * sizeof(TYPE));
134             length += d;
135         }
136     }
137 
insertArray138     void insert(size_t index, TYPE ptr)
139     {
140         reserve(1);
141         memmove(data.ptr + index + 1, data.ptr + index, (length - index) * sizeof(TYPE));
142         data.ptr[index] = ptr;
143         length++;
144     }
145 
setDimArray146     void setDim(size_t newdim)
147     {
148         if (length < newdim)
149         {
150             reserve(newdim - length);
151         }
152         length = newdim;
153     }
154 
findArray155     size_t find(TYPE ptr) const
156     {
157         for (size_t i = 0; i < length; i++)
158         {
159             if (data.ptr[i] == ptr)
160                 return i;
161         }
162         return SIZE_MAX;
163     }
164 
containsArray165     bool contains(TYPE ptr) const
166     {
167         return find(ptr) != SIZE_MAX;
168     }
169 
170     TYPE& operator[] (size_t index)
171     {
172 #ifdef DEBUG
173         assert(index < length);
174 #endif
175         return data.ptr[index];
176     }
177 
tdataArray178     TYPE *tdata()
179     {
180         return data.ptr;
181     }
182 
copyArray183     Array *copy()
184     {
185         Array *a = new Array();
186         a->setDim(length);
187         memcpy(a->data.ptr, data.ptr, length * sizeof(TYPE));
188         return a;
189     }
190 
shiftArray191     void shift(TYPE ptr)
192     {
193         reserve(1);
194         memmove(data.ptr + 1, data.ptr, length * sizeof(TYPE));
195         data.ptr[0] = ptr;
196         length++;
197     }
198 
zeroArray199     void zero()
200     {
201         memset(data.ptr, 0, length * sizeof(TYPE));
202     }
203 
popArray204     TYPE pop()
205     {
206         return data.ptr[--length];
207     }
208 
sortArray209     void sort()
210     {
211         struct ArraySort
212         {
213             static int
214     #if _WIN32
215               __cdecl
216     #endif
217             Array_sort_compare(const void *x, const void *y)
218             {
219                 RootObject *ox = *(RootObject **)const_cast<void *>(x);
220                 RootObject *oy = *(RootObject **)const_cast<void *>(y);
221 
222                 return ox->compare(oy);
223             }
224         };
225 
226         if (length)
227         {
228             qsort(data.ptr, length, sizeof(RootObject *), &ArraySort::Array_sort_compare);
229         }
230     }
231 };
232 
233