mono/metadata/sgen-dynarray.h

   1 /**
   2  * \file
   3  * Copyright 2016 Xamarin, Inc.
   4  *
   5  * Licensed under the MIT license. See LICENSE file in the project root for full license information.
   6  */
   7
   8  // Growable array implementation used by sgen-new-bridge and sgen-tarjan-bridge.
   9
  10 typedef struct {
  11         int size;
  12         int capacity;           /* if negative, data points to another DynArray's data */
  13         char *data;
  14 } DynArray;
  15
  16 /*Specializations*/
  17
  18 // IntArray supports an optimization (in sgen-new-bridge.c): If capacity is less than 0 it is a "copy" and does not own its buffer.
  19 typedef struct {
  20         DynArray array;
  21 } DynIntArray;
  22
  23 // PtrArray supports an optimization: If size is equal to 1 it is a "singleton" and data points to the single held item, not to a buffer.
  24 typedef struct {
  25         DynArray array;
  26 } DynPtrArray;
  27
  28 typedef struct {
  29         DynArray array;
  30 } DynSCCArray;
  31
  32 static void
  33 dyn_array_init (DynArray *da)
  34 {
  35         da->size = 0;
  36         da->capacity = 0;
  37         da->data = NULL;
  38 }
  39
  40 static void
  41 dyn_array_uninit (DynArray *da, int elem_size)
  42 {
  43         if (da->capacity < 0) {
  44                 dyn_array_init (da);
  45                 return;
  46         }
  47
  48         if (da->capacity == 0)
  49                 return;
  50
  51         sgen_free_internal_dynamic (da->data, elem_size * da->capacity, INTERNAL_MEM_BRIDGE_DATA);
  52         da->data = NULL;
  53 }
  54
  55 static void
  56 dyn_array_empty (DynArray *da)
  57 {
  58         if (da->capacity < 0)
  59                 dyn_array_init (da);
  60         else
  61                 da->size = 0;
  62 }
  63
  64 static char *
  65 dyn_array_ensure_capacity_internal (DynArray *da, int capacity, int elem_size)
  66 {
  67         if (da->capacity <= 0)
  68                 da->capacity = 2;
  69         while (capacity > da->capacity)
  70                 da->capacity *= 2;
  71
  72         return (char *)sgen_alloc_internal_dynamic (elem_size * da->capacity, INTERNAL_MEM_BRIDGE_DATA, TRUE);
  73 }
  74
  75 static void
  76 dyn_array_ensure_capacity (DynArray *da, int capacity, int elem_size)
  77 {
  78         int old_capacity = da->capacity;
  79         char *new_data;
  80
  81         g_assert (capacity > 0);
  82
  83         if (capacity <= old_capacity)
  84                 return;
  85
  86         new_data = dyn_array_ensure_capacity_internal (da, capacity, elem_size);
  87         memcpy (new_data, da->data, elem_size * da->size);
  88         if (old_capacity > 0)
  89                 sgen_free_internal_dynamic (da->data, elem_size * old_capacity, INTERNAL_MEM_BRIDGE_DATA);
  90         da->data = new_data;
  91 }
  92
  93 static gboolean
  94 dyn_array_is_copy (DynArray *da)
  95 {
  96         return da->capacity < 0;
  97 }
  98
  99 static void
 100 dyn_array_ensure_independent (DynArray *da, int elem_size)
 101 {
 102         if (!dyn_array_is_copy (da))
 103                 return;
 104         dyn_array_ensure_capacity (da, da->size, elem_size);
 105         g_assert (da->capacity > 0);
 106 }
 107
 108 static void*
 109 dyn_array_add (DynArray *da, int elem_size)
 110 {
 111         void *p;
 112
 113         dyn_array_ensure_capacity (da, da->size + 1, elem_size);
 114
 115         p = da->data + da->size * elem_size;
 116         ++da->size;
 117         return p;
 118 }
 119
 120 static void
 121 dyn_array_copy (DynArray *dst, DynArray *src, int elem_size)
 122 {
 123         dyn_array_uninit (dst, elem_size);
 124
 125         if (src->size == 0)
 126                 return;
 127
 128         dst->size = src->size;
 129         dst->capacity = -1;
 130         dst->data = src->data;
 131 }
 132
 133 /* int */
 134 static void
 135 dyn_array_int_init (DynIntArray *da)
 136 {
 137         dyn_array_init (&da->array);
 138 }
 139
 140 static void
 141 dyn_array_int_uninit (DynIntArray *da)
 142 {
 143         dyn_array_uninit (&da->array, sizeof (int));
 144 }
 145
 146 static int
 147 dyn_array_int_size (DynIntArray *da)
 148 {
 149         return da->array.size;
 150 }
 151
 152 #ifdef NEW_XREFS
 153 static void
 154 dyn_array_int_empty (DynIntArray *da)
 155 {
 156         dyn_array_empty (&da->array);
 157 }
 158 #endif
 159
 160 static void
 161 dyn_array_int_add (DynIntArray *da, int x)
 162 {
 163         int *p = (int *)dyn_array_add (&da->array, sizeof (int));
 164         *p = x;
 165 }
 166
 167 static int
 168 dyn_array_int_get (DynIntArray *da, int x)
 169 {
 170         return ((int*)da->array.data)[x];
 171 }
 172
 173 #ifdef NEW_XREFS
 174 static void
 175 dyn_array_int_set (DynIntArray *da, int idx, int val)
 176 {
 177         ((int*)da->array.data)[idx] = val;
 178 }
 179 #endif
 180
 181 static void
 182 dyn_array_int_ensure_independent (DynIntArray *da)
 183 {
 184         dyn_array_ensure_independent (&da->array, sizeof (int));
 185 }
 186
 187 static void
 188 dyn_array_int_copy (DynIntArray *dst, DynIntArray *src)
 189 {
 190         dyn_array_copy (&dst->array, &src->array, sizeof (int));
 191 }
 192
 193 static gboolean
 194 dyn_array_int_is_copy (DynIntArray *da)
 195 {
 196         return dyn_array_is_copy (&da->array);
 197 }
 198
 199 /* ptr */
 200
 201 static void
 202 dyn_array_ptr_init (DynPtrArray *da)
 203 {
 204         dyn_array_init (&da->array);
 205 }
 206
 207 static void
 208 dyn_array_ptr_uninit (DynPtrArray *da)
 209 {
 210 #ifdef OPTIMIZATION_SINGLETON_DYN_ARRAY
 211         if (da->array.capacity == 1)
 212                 dyn_array_ptr_init (da);
 213         else
 214 #endif
 215                 dyn_array_uninit (&da->array, sizeof (void*));
 216 }
 217
 218 static int
 219 dyn_array_ptr_size (DynPtrArray *da)
 220 {
 221         return da->array.size;
 222 }
 223
 224 static void
 225 dyn_array_ptr_empty (DynPtrArray *da)
 226 {
 227 #ifdef OPTIMIZATION_SINGLETON_DYN_ARRAY
 228         if (da->array.capacity == 1)
 229                 dyn_array_ptr_init (da);
 230         else
 231 #endif
 232                 dyn_array_empty (&da->array);
 233 }
 234
 235 static void*
 236 dyn_array_ptr_get (DynPtrArray *da, int x)
 237 {
 238 #ifdef OPTIMIZATION_SINGLETON_DYN_ARRAY
 239         if (da->array.capacity == 1) {
 240                 g_assert (x == 0);
 241                 return da->array.data;
 242         }
 243 #endif
 244         return ((void**)da->array.data)[x];
 245 }
 246
 247 static void
 248 dyn_array_ptr_set (DynPtrArray *da, int x, void *ptr)
 249 {
 250 #ifdef OPTIMIZATION_SINGLETON_DYN_ARRAY
 251         if (da->array.capacity == 1) {
 252                 g_assert (x == 0);
 253                 da->array.data = ptr;
 254         } else
 255 #endif
 256         {
 257                 ((void**)da->array.data)[x] = ptr;
 258         }
 259 }
 260
 261 static void
 262 dyn_array_ptr_add (DynPtrArray *da, void *ptr)
 263 {
 264         void **p;
 265
 266 #ifdef OPTIMIZATION_SINGLETON_DYN_ARRAY
 267         if (da->array.capacity == 0) {
 268                 da->array.capacity = 1;
 269                 da->array.size = 1;
 270                 p = (void**)&da->array.data;
 271         } else if (da->array.capacity == 1) {
 272                 void *ptr0 = da->array.data;
 273                 void **p0;
 274                 dyn_array_init (&da->array);
 275                 p0 = (void **)dyn_array_add (&da->array, sizeof (void*));
 276                 *p0 = ptr0;
 277                 p = (void **)dyn_array_add (&da->array, sizeof (void*));
 278         } else
 279 #endif
 280         {
 281                 p = (void **)dyn_array_add (&da->array, sizeof (void*));
 282         }
 283         *p = ptr;
 284 }
 285
 286 #define dyn_array_ptr_push dyn_array_ptr_add
 287
 288 static void*
 289 dyn_array_ptr_pop (DynPtrArray *da)
 290 {
 291         int size = da->array.size;
 292         void *p;
 293         g_assert (size > 0);
 294 #ifdef OPTIMIZATION_SINGLETON_DYN_ARRAY
 295         if (da->array.capacity == 1) {
 296                 p = dyn_array_ptr_get (da, 0);
 297                 dyn_array_init (&da->array);
 298         } else
 299 #endif
 300         {
 301                 g_assert (da->array.capacity > 1);
 302                 dyn_array_ensure_independent (&da->array, sizeof (void*));
 303                 p = dyn_array_ptr_get (da, size - 1);
 304                 --da->array.size;
 305         }
 306         return p;
 307 }
 308
 309 static void
 310 dyn_array_ptr_ensure_capacity (DynPtrArray *da, int capacity)
 311 {
 312 #ifdef OPTIMIZATION_SINGLETON_DYN_ARRAY
 313         if (capacity == 1 && da->array.capacity < 1) {
 314                 da->array.capacity = 1;
 315         } else if (da->array.capacity == 1) // TODO size==1
 316         {
 317                 if (capacity > 1)
 318                 {
 319                         void *ptr = dyn_array_ptr_get (da, 0);
 320                         da->array.data = dyn_array_ensure_capacity_internal(&da->array, capacity, sizeof (void*));
 321                         dyn_array_ptr_set (da, 0, ptr);
 322                 }
 323         }
 324 #endif
 325         {
 326                 dyn_array_ensure_capacity (&da->array, capacity, sizeof (void*));
 327         }
 328 }
 329
 330 static void
 331 dyn_array_ptr_set_all (DynPtrArray *dst, DynPtrArray *src)
 332 {
 333         const int copysize = src->array.size;
 334         if (copysize > 0) {
 335                 dyn_array_ptr_ensure_capacity (dst, copysize);
 336
 337 #ifdef OPTIMIZATION_SINGLETON_DYN_ARRAY
 338                 if (copysize == 1) {
 339                         dyn_array_ptr_set (dst, 0, dyn_array_ptr_get (src, 0));
 340                 } else
 341 #endif
 342                 {
 343                         memcpy (dst->array.data, src->array.data, copysize * sizeof (void*));
 344                 }
 345         }
 346         dst->array.size = src->array.size;
 347 }