gcc/d/dmd/root/array.h

   1 /* Copyright (C) 2011-2018 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 <assert.h>
  11 #include <stdio.h>
  12 #include <stdlib.h>
  13 #include <string.h>
  14
  15 #include "object.h"
  16 #include "rmem.h"
  17
  18 template <typename TYPE>
  19 struct Array
  20 {
  21     d_size_t dim;
  22     TYPE *data;
  23
  24   private:
  25     Array(const Array&);
  26
  27     d_size_t allocdim;
  28     #define SMALLARRAYCAP       1
  29     TYPE smallarray[SMALLARRAYCAP];    // inline storage for small arrays
  30
  31   public:
  32     Array()
  33     {
  34         data = SMALLARRAYCAP ? &smallarray[0] : NULL;
  35         dim = 0;
  36         allocdim = SMALLARRAYCAP;
  37     }
  38
  39     ~Array()
  40     {
  41         if (data != &smallarray[0])
  42             mem.xfree(data);
  43     }
  44
  45     char *toChars()
  46     {
  47         const char **buf = (const char **)mem.xmalloc(dim * sizeof(const char *));
  48         d_size_t len = 2;
  49         for (d_size_t u = 0; u < dim; u++)
  50         {
  51             buf[u] = ((RootObject *)data[u])->toChars();
  52             len += strlen(buf[u]) + 1;
  53         }
  54         char *str = (char *)mem.xmalloc(len);
  55
  56         str[0] = '[';
  57         char *p = str + 1;
  58         for (d_size_t u = 0; u < dim; u++)
  59         {
  60             if (u)
  61                 *p++ = ',';
  62             len = strlen(buf[u]);
  63             memcpy(p,buf[u],len);
  64             p += len;
  65         }
  66         *p++ = ']';
  67         *p = 0;
  68         mem.xfree(buf);
  69         return str;
  70     }
  71
  72     void reserve(d_size_t nentries)
  73     {
  74         //printf("Array::reserve: dim = %d, allocdim = %d, nentries = %d\n", (int)dim, (int)allocdim, (int)nentries);
  75         if (allocdim - dim < nentries)
  76         {
  77             if (allocdim == 0)
  78             {   // Not properly initialized, someone memset it to zero
  79                 if (nentries <= SMALLARRAYCAP)
  80                 {   allocdim = SMALLARRAYCAP;
  81                     data = SMALLARRAYCAP ? &smallarray[0] : NULL;
  82                 }
  83                 else
  84                 {   allocdim = nentries;
  85                     data = (TYPE *)mem.xmalloc(allocdim * sizeof(*data));
  86                 }
  87             }
  88             else if (allocdim == SMALLARRAYCAP)
  89             {
  90                 allocdim = dim + nentries;
  91                 data = (TYPE *)mem.xmalloc(allocdim * sizeof(*data));
  92                 memcpy(data, &smallarray[0], dim * sizeof(*data));
  93             }
  94             else
  95             {
  96                 /* Increase size by 1.5x to avoid excessive memory fragmentation
  97                  */
  98                 d_size_t increment = dim / 2;
  99                 if (nentries > increment)       // if 1.5 is not enough
 100                     increment = nentries;
 101                 allocdim = dim + increment;
 102                 data = (TYPE *)mem.xrealloc(data, allocdim * sizeof(*data));
 103             }
 104         }
 105     }
 106
 107     void setDim(d_size_t newdim)
 108     {
 109         if (dim < newdim)
 110         {
 111             reserve(newdim - dim);
 112         }
 113         dim = newdim;
 114     }
 115
 116     TYPE pop()
 117     {
 118         return data[--dim];
 119     }
 120
 121     void shift(TYPE ptr)
 122     {
 123         reserve(1);
 124         memmove(data + 1, data, dim * sizeof(*data));
 125         data[0] = ptr;
 126         dim++;
 127     }
 128
 129     void remove(d_size_t i)
 130     {
 131         if (dim - i - 1)
 132             memmove(data + i, data + i + 1, (dim - i - 1) * sizeof(data[0]));
 133         dim--;
 134     }
 135
 136     void zero()
 137     {
 138         memset(data,0,dim * sizeof(data[0]));
 139     }
 140
 141     void sort()
 142     {
 143         struct ArraySort
 144         {
 145             static int
 146     #if _WIN32
 147               __cdecl
 148     #endif
 149             Array_sort_compare(const void *x, const void *y)
 150             {
 151                 RootObject *ox = *(RootObject **)const_cast<void *>(x);
 152                 RootObject *oy = *(RootObject **)const_cast<void *>(y);
 153
 154                 return ox->compare(oy);
 155             }
 156         };
 157
 158         if (dim)
 159         {
 160             qsort(data, dim, sizeof(RootObject *), &ArraySort::Array_sort_compare);
 161         }
 162     }
 163
 164     TYPE *tdata()
 165     {
 166         return data;
 167     }
 168
 169     TYPE& operator[] (d_size_t index)
 170     {
 171         return data[index];
 172     }
 173
 174     void insert(d_size_t index, TYPE v)
 175     {
 176         reserve(1);
 177         memmove(data + index + 1, data + index, (dim - index) * sizeof(*data));
 178         data[index] = v;
 179         dim++;
 180     }
 181
 182     void insert(d_size_t index, Array *a)
 183     {
 184         if (a)
 185         {
 186             d_size_t d = a->dim;
 187             reserve(d);
 188             if (dim != index)
 189                 memmove(data + index + d, data + index, (dim - index) * sizeof(*data));
 190             memcpy(data + index, a->data, d * sizeof(*data));
 191             dim += d;
 192         }
 193     }
 194
 195     void append(Array *a)
 196     {
 197         insert(dim, a);
 198     }
 199
 200     void push(TYPE a)
 201     {
 202         reserve(1);
 203         data[dim++] = a;
 204     }
 205
 206     Array *copy()
 207     {
 208         Array *a = new Array();
 209         a->setDim(dim);
 210         memcpy(a->data, data, dim * sizeof(*data));
 211         return a;
 212     }
 213 };
 214
 215 struct BitArray
 216 {
 217     BitArray()
 218       : len(0)
 219       , ptr(NULL)
 220     {}
 221
 222     ~BitArray()
 223     {
 224         mem.xfree(ptr);
 225     }
 226
 227     d_size_t len;
 228     d_size_t *ptr;
 229
 230 private:
 231     BitArray(const BitArray&);
 232 };