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 "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: ArrayArray28 Array() 29 { 30 data.ptr = NULL; 31 length = 0; 32 data.length = 0; 33 } 34 ~ArrayArray35 ~Array() 36 { 37 if (data.ptr != &smallarray[0]) 38 mem.xfree(data.ptr); 39 } 40 toCharsArray41 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 pushArray68 void push(TYPE ptr) 69 { 70 reserve(1); 71 data.ptr[length++] = ptr; 72 } 73 appendArray74 void append(Array *a) 75 { 76 insert(length, a); 77 } 78 reserveArray79 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 removeArray117 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 insertArray124 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 insertArray137 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 setDimArray145 void setDim(d_size_t newdim) 146 { 147 if (length < newdim) 148 { 149 reserve(newdim - length); 150 } 151 length = newdim; 152 } 153 findArray154 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 containsArray164 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 tdataArray177 TYPE *tdata() 178 { 179 return data.ptr; 180 } 181 copyArray182 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 shiftArray190 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 zeroArray198 void zero() 199 { 200 memset(data.ptr, 0, length * sizeof(TYPE)); 201 } 202 popArray203 TYPE pop() 204 { 205 return data.ptr[--length]; 206 } 207 }; 208 209