Home | History | Annotate | Line # | Download | only in root 
      1 /* Copyright (C) 2011-2022 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 };
    208