gcc/d/dmd/root/array.h

   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 };