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