mono/metadata/sgen-dynarray.h

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