1 /* Copyright (C) 2011-2023 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
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:
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 };