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