1 /* Copyright (C) 2011-2019 by The D Language Foundation, All Rights Reserved
2  * http://www.digitalmars.com
3  * Distributed under the Boost Software License, Version 1.0.
4  * http://www.boost.org/LICENSE_1_0.txt
5  * https://github.com/dlang/dmd/blob/master/src/dmd/root/array.h
6  */
7 
8 #pragma once
9 
10 #include "dsystem.h"
11 #include "object.h"
12 #include "rmem.h"
13 
14 template <typename TYPE>
15 struct Array
16 {
17     d_size_t dim;
18     TYPE *data;
19 
20   private:
21     Array(const Array&);
22 
23     d_size_t allocdim;
24     #define SMALLARRAYCAP       1
25     TYPE smallarray[SMALLARRAYCAP];    // inline storage for small arrays
26 
27   public:
ArrayArray28     Array()
29     {
30         data = SMALLARRAYCAP ? &smallarray[0] : NULL;
31         dim = 0;
32         allocdim = SMALLARRAYCAP;
33     }
34 
~ArrayArray35     ~Array()
36     {
37         if (data != &smallarray[0])
38             mem.xfree(data);
39     }
40 
toCharsArray41     char *toChars()
42     {
43         const char **buf = (const char **)mem.xmalloc(dim * sizeof(const char *));
44         d_size_t len = 2;
45         for (d_size_t u = 0; u < dim; u++)
46         {
47             buf[u] = ((RootObject *)data[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 < dim; 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 
reserveArray68     void reserve(d_size_t nentries)
69     {
70         //printf("Array::reserve: dim = %d, allocdim = %d, nentries = %d\n", (int)dim, (int)allocdim, (int)nentries);
71         if (allocdim - dim < nentries)
72         {
73             if (allocdim == 0)
74             {   // Not properly initialized, someone memset it to zero
75                 if (nentries <= SMALLARRAYCAP)
76                 {   allocdim = SMALLARRAYCAP;
77                     data = SMALLARRAYCAP ? &smallarray[0] : NULL;
78                 }
79                 else
80                 {   allocdim = nentries;
81                     data = (TYPE *)mem.xmalloc(allocdim * sizeof(*data));
82                 }
83             }
84             else if (allocdim == SMALLARRAYCAP)
85             {
86                 allocdim = dim + nentries;
87                 data = (TYPE *)mem.xmalloc(allocdim * sizeof(*data));
88                 memcpy(data, &smallarray[0], dim * sizeof(*data));
89             }
90             else
91             {
92                 /* Increase size by 1.5x to avoid excessive memory fragmentation
93                  */
94                 d_size_t increment = dim / 2;
95                 if (nentries > increment)       // if 1.5 is not enough
96                     increment = nentries;
97                 allocdim = dim + increment;
98                 data = (TYPE *)mem.xrealloc(data, allocdim * sizeof(*data));
99             }
100         }
101     }
102 
setDimArray103     void setDim(d_size_t newdim)
104     {
105         if (dim < newdim)
106         {
107             reserve(newdim - dim);
108         }
109         dim = newdim;
110     }
111 
popArray112     TYPE pop()
113     {
114         return data[--dim];
115     }
116 
shiftArray117     void shift(TYPE ptr)
118     {
119         reserve(1);
120         memmove(data + 1, data, dim * sizeof(*data));
121         data[0] = ptr;
122         dim++;
123     }
124 
removeArray125     void remove(d_size_t i)
126     {
127         if (dim - i - 1)
128             memmove(data + i, data + i + 1, (dim - i - 1) * sizeof(data[0]));
129         dim--;
130     }
131 
zeroArray132     void zero()
133     {
134         memset(data,0,dim * sizeof(data[0]));
135     }
136 
sortArray137     void sort()
138     {
139         struct ArraySort
140         {
141             static int
142     #if _WIN32
143               __cdecl
144     #endif
145             Array_sort_compare(const void *x, const void *y)
146             {
147                 RootObject *ox = *(RootObject **)const_cast<void *>(x);
148                 RootObject *oy = *(RootObject **)const_cast<void *>(y);
149 
150                 return ox->compare(oy);
151             }
152         };
153 
154         if (dim)
155         {
156             qsort(data, dim, sizeof(RootObject *), &ArraySort::Array_sort_compare);
157         }
158     }
159 
tdataArray160     TYPE *tdata()
161     {
162         return data;
163     }
164 
165     TYPE& operator[] (d_size_t index)
166     {
167         return data[index];
168     }
169 
insertArray170     void insert(d_size_t index, TYPE v)
171     {
172         reserve(1);
173         memmove(data + index + 1, data + index, (dim - index) * sizeof(*data));
174         data[index] = v;
175         dim++;
176     }
177 
insertArray178     void insert(d_size_t index, Array *a)
179     {
180         if (a)
181         {
182             d_size_t d = a->dim;
183             reserve(d);
184             if (dim != index)
185                 memmove(data + index + d, data + index, (dim - index) * sizeof(*data));
186             memcpy(data + index, a->data, d * sizeof(*data));
187             dim += d;
188         }
189     }
190 
appendArray191     void append(Array *a)
192     {
193         insert(dim, a);
194     }
195 
pushArray196     void push(TYPE a)
197     {
198         reserve(1);
199         data[dim++] = a;
200     }
201 
copyArray202     Array *copy()
203     {
204         Array *a = new Array();
205         a->setDim(dim);
206         memcpy(a->data, data, dim * sizeof(*data));
207         return a;
208     }
209 };
210 
211 struct BitArray
212 {
BitArrayBitArray213     BitArray()
214       : len(0)
215       , ptr(NULL)
216     {}
217 
~BitArrayBitArray218     ~BitArray()
219     {
220         mem.xfree(ptr);
221     }
222 
223     d_size_t len;
224     d_size_t *ptr;
225 
226 private:
227     BitArray(const BitArray&);
228 };
229