libobjc/sarray.c

   1 /* Sparse Arrays for Objective C dispatch tables
   2    Copyright (C) 1993, 1995, 1996, 2002, 2004, 2009, 2010
   3    Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 Under Section 7 of GPL version 3, you are granted additional
  18 permissions described in the GCC Runtime Library Exception, version
  19 3.1, as published by the Free Software Foundation.
  20
  21 You should have received a copy of the GNU General Public License and
  22 a copy of the GCC Runtime Library Exception along with this program;
  23 see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  24 <http://www.gnu.org/licenses/>.  */
  25
  26 #include "objc-private/common.h"
  27 #include "objc-private/sarray.h"
  28 #include "objc/runtime.h" /* For objc_malloc */
  29 #include "objc/thr.h"     /* For objc_mutex_lock */
  30 #include "objc-private/module-abi-8.h"
  31 #include "objc-private/runtime.h"
  32 #include <stdio.h>
  33 #include <string.h> /* For memset */
  34 #include <assert.h> /* For assert */
  35
  36 int nbuckets = 0;                                       /* !T:MUTEX */
  37 int nindices = 0;                                       /* !T:MUTEX */
  38 int narrays = 0;                                        /* !T:MUTEX */
  39 int idxsize = 0;                                        /* !T:MUTEX */
  40
  41 static void *first_free_data = NULL;                    /* !T:MUTEX */
  42
  43 #ifdef OBJC_SPARSE2
  44 const char *__objc_sparse2_id = "2 level sparse indices";
  45 #endif
  46
  47 #ifdef OBJC_SPARSE3
  48 const char *__objc_sparse3_id = "3 level sparse indices";
  49 #endif
  50
  51 /* This function removes any structures left over from free operations
  52    that were not safe in a multi-threaded environment. */
  53 void
  54 sarray_remove_garbage (void)
  55 {
  56   void **vp;
  57   void *np;
  58
  59   objc_mutex_lock (__objc_runtime_mutex);
  60
  61   vp = first_free_data;
  62   first_free_data = NULL;
  63
  64   while (vp)
  65     {
  66       np = *vp;
  67       objc_free (vp);
  68       vp = np;
  69     }
  70
  71   objc_mutex_unlock (__objc_runtime_mutex);
  72 }
  73
  74 /* Free a block of dynamically allocated memory.  If we are in
  75    multi-threaded mode, it is ok to free it.  If not, we add it to the
  76    garbage heap to be freed later. */
  77 static void
  78 sarray_free_garbage (void *vp)
  79 {
  80   objc_mutex_lock (__objc_runtime_mutex);
  81
  82   if (__objc_runtime_threads_alive == 1)
  83     {
  84       objc_free (vp);
  85       if (first_free_data)
  86         sarray_remove_garbage ();
  87     }
  88   else
  89     {
  90       *(void **)vp = first_free_data;
  91       first_free_data = vp;
  92     }
  93
  94   objc_mutex_unlock (__objc_runtime_mutex);
  95 }
  96
  97 /* sarray_at_put copies data in such a way as to be thread reader
  98    safe.  */
  99 void
 100 sarray_at_put (struct sarray *array, sidx index, void *element)
 101 {
 102 #ifdef OBJC_SPARSE3
 103   struct sindex **the_index;
 104   struct sindex *new_index;
 105 #endif
 106   struct sbucket **the_bucket;
 107   struct sbucket *new_bucket;
 108 #ifdef OBJC_SPARSE3
 109   size_t ioffset;
 110 #endif
 111   size_t boffset;
 112   size_t eoffset;
 113 #ifdef PRECOMPUTE_SELECTORS
 114   union sofftype xx;
 115   xx.idx = index;
 116 #ifdef OBJC_SPARSE3
 117   ioffset = xx.off.ioffset;
 118 #endif
 119   boffset = xx.off.boffset;
 120   eoffset = xx.off.eoffset;
 121 #else /* not PRECOMPUTE_SELECTORS */
 122 #ifdef OBJC_SPARSE3
 123   ioffset = index/INDEX_CAPACITY;
 124   boffset = (index/BUCKET_SIZE)%INDEX_SIZE;
 125   eoffset = index%BUCKET_SIZE;
 126 #else
 127   boffset = index/BUCKET_SIZE;
 128   eoffset = index%BUCKET_SIZE;
 129 #endif
 130 #endif /* not PRECOMPUTE_SELECTORS */
 131
 132   assert (soffset_decode (index) < array->capacity); /* Range check */
 133
 134 #ifdef OBJC_SPARSE3
 135   the_index = &(array->indices[ioffset]);
 136   the_bucket = &((*the_index)->buckets[boffset]);
 137 #else
 138   the_bucket = &(array->buckets[boffset]);
 139 #endif
 140
 141   if ((*the_bucket)->elems[eoffset] == element)
 142     return;             /* Great! we just avoided a lazy copy.  */
 143
 144 #ifdef OBJC_SPARSE3
 145
 146   /* First, perform lazy copy/allocation of index if needed.  */
 147
 148   if ((*the_index) == array->empty_index)
 149     {
 150       /* The index was previously empty, allocate a new.  */
 151       new_index = (struct sindex *) objc_malloc (sizeof (struct sindex));
 152       memcpy (new_index, array->empty_index, sizeof (struct sindex));
 153       new_index->version.version = array->version.version;
 154       *the_index = new_index;                     /* Prepared for install. */
 155       the_bucket = &((*the_index)->buckets[boffset]);
 156
 157       nindices += 1;
 158     }
 159   else if ((*the_index)->version.version != array->version.version)
 160     {
 161       /* This index must be lazy copied.  */
 162       struct sindex *old_index = *the_index;
 163       new_index = (struct sindex *) objc_malloc (sizeof (struct sindex));
 164       memcpy (new_index, old_index, sizeof (struct sindex));
 165       new_index->version.version = array->version.version;
 166       *the_index = new_index;                     /* Prepared for install. */
 167       the_bucket = &((*the_index)->buckets[boffset]);
 168
 169       nindices += 1;
 170     }
 171
 172 #endif /* OBJC_SPARSE3 */
 173
 174   /* Next, perform lazy allocation/copy of the bucket if needed.  */
 175   if ((*the_bucket) == array->empty_bucket)
 176     {
 177       /* The bucket was previously empty (or something like that),
 178          allocate a new.  This is the effect of `lazy' allocation.  */
 179       new_bucket = (struct sbucket *) objc_malloc (sizeof (struct sbucket));
 180       memcpy ((void *) new_bucket, (const void *) array->empty_bucket,
 181               sizeof (struct sbucket));
 182       new_bucket->version.version = array->version.version;
 183       *the_bucket = new_bucket;                   /* Prepared for install. */
 184
 185       nbuckets += 1;
 186
 187     }
 188   else if ((*the_bucket)->version.version != array->version.version)
 189     {
 190       /* Perform lazy copy.  */
 191       struct sbucket *old_bucket = *the_bucket;
 192       new_bucket = (struct sbucket *) objc_malloc (sizeof (struct sbucket));
 193       memcpy (new_bucket, old_bucket, sizeof (struct sbucket));
 194       new_bucket->version.version = array->version.version;
 195       *the_bucket = new_bucket;                   /* Prepared for install. */
 196
 197       nbuckets += 1;
 198     }
 199   (*the_bucket)->elems[eoffset] = element;
 200 }
 201
 202 void
 203 sarray_at_put_safe (struct sarray *array, sidx index, void *element)
 204 {
 205   if (soffset_decode (index) >= array->capacity)
 206     sarray_realloc (array, soffset_decode (index) + 1);
 207   sarray_at_put (array, index, element);
 208 }
 209
 210 struct sarray *
 211 sarray_new (int size, void *default_element)
 212 {
 213   struct sarray *arr;
 214 #ifdef OBJC_SPARSE3
 215   size_t num_indices = ((size - 1)/(INDEX_CAPACITY)) + 1;
 216   struct sindex **new_indices;
 217 #else /* OBJC_SPARSE2 */
 218   size_t num_indices = ((size - 1)/BUCKET_SIZE) + 1;
 219   struct sbucket **new_buckets;
 220 #endif
 221   size_t counter;
 222
 223   assert (size > 0);
 224
 225   /* Allocate core array.  */
 226   arr = (struct sarray *) objc_malloc (sizeof (struct sarray));
 227   arr->version.version = 0;
 228
 229   /* Initialize members.  */
 230 #ifdef OBJC_SPARSE3
 231   arr->capacity = num_indices*INDEX_CAPACITY;
 232   new_indices = (struct sindex **)
 233     objc_malloc (sizeof (struct sindex *) * num_indices);
 234
 235   arr->empty_index = (struct sindex *) objc_malloc (sizeof (struct sindex));
 236   arr->empty_index->version.version = 0;
 237
 238   narrays  += 1;
 239   idxsize  += num_indices;
 240   nindices += 1;
 241
 242 #else /* OBJC_SPARSE2 */
 243   arr->capacity = num_indices*BUCKET_SIZE;
 244   new_buckets = (struct sbucket **)
 245     objc_malloc (sizeof (struct sbucket *) * num_indices);
 246
 247   narrays  += 1;
 248   idxsize  += num_indices;
 249
 250 #endif
 251
 252   arr->empty_bucket = (struct sbucket *) objc_malloc (sizeof (struct sbucket));
 253   arr->empty_bucket->version.version = 0;
 254
 255   nbuckets += 1;
 256
 257   arr->ref_count = 1;
 258   arr->is_copy_of = (struct sarray *) 0;
 259
 260   for (counter = 0; counter < BUCKET_SIZE; counter++)
 261     arr->empty_bucket->elems[counter] = default_element;
 262
 263 #ifdef OBJC_SPARSE3
 264   for (counter = 0; counter < INDEX_SIZE; counter++)
 265     arr->empty_index->buckets[counter] = arr->empty_bucket;
 266
 267   for (counter = 0; counter < num_indices; counter++)
 268     new_indices[counter] = arr->empty_index;
 269
 270 #else /* OBJC_SPARSE2 */
 271
 272   for (counter = 0; counter < num_indices; counter++)
 273     new_buckets[counter] = arr->empty_bucket;
 274
 275 #endif
 276
 277 #ifdef OBJC_SPARSE3
 278   arr->indices = new_indices;
 279 #else /* OBJC_SPARSE2 */
 280   arr->buckets = new_buckets;
 281 #endif
 282
 283   return arr;
 284 }
 285 \f
 286
 287 /* Reallocate the sparse array to hold `newsize' entries Note: We
 288    really allocate and then free.  We have to do this to ensure that
 289    any concurrent readers notice the update.  */
 290 void
 291 sarray_realloc (struct sarray *array, int newsize)
 292 {
 293 #ifdef OBJC_SPARSE3
 294   size_t old_max_index = (array->capacity - 1)/INDEX_CAPACITY;
 295   size_t new_max_index = ((newsize - 1)/INDEX_CAPACITY);
 296   size_t rounded_size = (new_max_index + 1) * INDEX_CAPACITY;
 297
 298   struct sindex **new_indices;
 299   struct sindex **old_indices;
 300
 301 #else /* OBJC_SPARSE2 */
 302   size_t old_max_index = (array->capacity - 1)/BUCKET_SIZE;
 303   size_t new_max_index = ((newsize - 1)/BUCKET_SIZE);
 304   size_t rounded_size = (new_max_index + 1) * BUCKET_SIZE;
 305
 306   struct sbucket **new_buckets;
 307   struct sbucket **old_buckets;
 308
 309 #endif
 310
 311   size_t counter;
 312
 313   assert (newsize > 0);
 314
 315   /* The size is the same, just ignore the request.  */
 316   if (rounded_size <= array->capacity)
 317     return;
 318
 319   assert (array->ref_count == 1);       /* stop if lazy copied... */
 320
 321   /* We are asked to extend the array -- allocate new bucket table,
 322      and insert empty_bucket in newly allocated places.  */
 323   if (rounded_size > array->capacity)
 324     {
 325 #ifdef OBJC_SPARSE3
 326       new_max_index += 4;
 327       rounded_size = (new_max_index + 1) * INDEX_CAPACITY;
 328 #else /* OBJC_SPARSE2 */
 329       new_max_index += 4;
 330       rounded_size = (new_max_index + 1) * BUCKET_SIZE;
 331 #endif
 332
 333       /* Update capacity.  */
 334       array->capacity = rounded_size;
 335
 336 #ifdef OBJC_SPARSE3
 337       /* Alloc to force re-read by any concurrent readers.  */
 338       old_indices = array->indices;
 339       new_indices = (struct sindex **)
 340         objc_malloc ((new_max_index + 1) * sizeof (struct sindex *));
 341 #else /* OBJC_SPARSE2 */
 342       old_buckets = array->buckets;
 343       new_buckets = (struct sbucket **)
 344         objc_malloc ((new_max_index + 1) * sizeof (struct sbucket *));
 345 #endif
 346
 347       /* Copy buckets below old_max_index (they are still valid).  */
 348       for (counter = 0; counter <= old_max_index; counter++ )
 349         {
 350 #ifdef OBJC_SPARSE3
 351           new_indices[counter] = old_indices[counter];
 352 #else /* OBJC_SPARSE2 */
 353           new_buckets[counter] = old_buckets[counter];
 354 #endif
 355         }
 356
 357 #ifdef OBJC_SPARSE3
 358       /* Reset entries above old_max_index to empty_bucket.  */
 359       for (counter = old_max_index + 1; counter <= new_max_index; counter++)
 360         new_indices[counter] = array->empty_index;
 361 #else /* OBJC_SPARSE2 */
 362       /* Reset entries above old_max_index to empty_bucket.  */
 363       for (counter = old_max_index + 1; counter <= new_max_index; counter++)
 364         new_buckets[counter] = array->empty_bucket;
 365 #endif
 366
 367 #ifdef OBJC_SPARSE3
 368       /* Install the new indices.  */
 369       array->indices = new_indices;
 370 #else /* OBJC_SPARSE2 */
 371       array->buckets = new_buckets;
 372 #endif
 373
 374 #ifdef OBJC_SPARSE3
 375       /* Free the old indices.  */
 376       sarray_free_garbage (old_indices);
 377 #else /* OBJC_SPARSE2 */
 378       sarray_free_garbage (old_buckets);
 379 #endif
 380
 381       idxsize += (new_max_index-old_max_index);
 382       return;
 383     }
 384 }
 385 \f
 386
 387 /* Free a sparse array allocated with sarray_new */
 388 void
 389 sarray_free (struct sarray *array) {
 390 #ifdef OBJC_SPARSE3
 391   size_t old_max_index = (array->capacity - 1)/INDEX_CAPACITY;
 392   struct sindex **old_indices;
 393 #else
 394   size_t old_max_index = (array->capacity - 1)/BUCKET_SIZE;
 395   struct sbucket **old_buckets;
 396 #endif
 397   size_t counter = 0;
 398
 399   assert (array->ref_count != 0);       /* Freed multiple times!!! */
 400
 401   if (--(array->ref_count) != 0)        /* There exists copies of me */
 402     return;
 403
 404 #ifdef OBJC_SPARSE3
 405   old_indices = array->indices;
 406 #else
 407   old_buckets = array->buckets;
 408 #endif
 409
 410   /* Free all entries that do not point to empty_bucket.  */
 411   for (counter = 0; counter <= old_max_index; counter++ )
 412     {
 413 #ifdef OBJC_SPARSE3
 414       struct sindex *idx = old_indices[counter];
 415       if ((idx != array->empty_index)
 416           && (idx->version.version == array->version.version))
 417         {
 418           int c2;
 419           for (c2 = 0; c2 < INDEX_SIZE; c2++)
 420             {
 421               struct sbucket *bkt = idx->buckets[c2];
 422               if ((bkt != array->empty_bucket)
 423                   && (bkt->version.version == array->version.version))
 424                 {
 425                   sarray_free_garbage (bkt);
 426                   nbuckets -= 1;
 427                 }
 428             }
 429           sarray_free_garbage (idx);
 430           nindices -= 1;
 431         }
 432 #else /* OBJC_SPARSE2 */
 433       struct sbucket *bkt = old_buckets[counter];
 434       if ((bkt != array->empty_bucket)
 435           && (bkt->version.version == array->version.version))
 436         {
 437           sarray_free_garbage (bkt);
 438           nbuckets -= 1;
 439         }
 440 #endif
 441     }
 442
 443 #ifdef OBJC_SPARSE3
 444   /* Free empty_index.  */
 445   if (array->empty_index->version.version == array->version.version)
 446     {
 447       sarray_free_garbage (array->empty_index);
 448       nindices -= 1;
 449     }
 450 #endif
 451
 452   /* Free empty_bucket.  */
 453   if (array->empty_bucket->version.version == array->version.version)
 454     {
 455       sarray_free_garbage (array->empty_bucket);
 456       nbuckets -= 1;
 457     }
 458   idxsize -= (old_max_index + 1);
 459   narrays -= 1;
 460
 461 #ifdef OBJC_SPARSE3
 462   /* Free bucket table.  */
 463   sarray_free_garbage (array->indices);
 464 #else
 465   /* Free bucket table.  */
 466   sarray_free_garbage (array->buckets);
 467 #endif
 468
 469   /* If this is a copy of another array, we free it (which might just
 470      decrement its reference count so it will be freed when no longer
 471      in use).  */
 472   if (array->is_copy_of)
 473     sarray_free (array->is_copy_of);
 474
 475   /* Free array.  */
 476   sarray_free_garbage (array);
 477 }
 478
 479 /* This is a lazy copy.  Only the core of the structure is actually
 480    copied.  */
 481 struct sarray *
 482 sarray_lazy_copy (struct sarray *oarr)
 483 {
 484   struct sarray *arr;
 485
 486 #ifdef OBJC_SPARSE3
 487   size_t num_indices = ((oarr->capacity - 1)/INDEX_CAPACITY) + 1;
 488   struct sindex **new_indices;
 489 #else /* OBJC_SPARSE2 */
 490   size_t num_indices = ((oarr->capacity - 1)/BUCKET_SIZE) + 1;
 491   struct sbucket **new_buckets;
 492 #endif
 493
 494   /* Allocate core array.  */
 495   arr = (struct sarray *) objc_malloc (sizeof (struct sarray)); /* !!! */
 496   arr->version.version = oarr->version.version + 1;
 497 #ifdef OBJC_SPARSE3
 498   arr->empty_index = oarr->empty_index;
 499 #endif
 500   arr->empty_bucket = oarr->empty_bucket;
 501   arr->ref_count = 1;
 502   oarr->ref_count += 1;
 503   arr->is_copy_of = oarr;
 504   arr->capacity = oarr->capacity;
 505
 506 #ifdef OBJC_SPARSE3
 507   /* Copy bucket table.  */
 508   new_indices = (struct sindex **)
 509     objc_malloc (sizeof (struct sindex *) * num_indices);
 510   memcpy (new_indices, oarr->indices, sizeof (struct sindex *) * num_indices);
 511   arr->indices = new_indices;
 512 #else
 513   /* Copy bucket table.  */
 514   new_buckets = (struct sbucket **)
 515     objc_malloc (sizeof (struct sbucket *) * num_indices);
 516   memcpy (new_buckets, oarr->buckets, sizeof (struct sbucket *) * num_indices);
 517   arr->buckets = new_buckets;
 518 #endif
 519
 520   idxsize += num_indices;
 521   narrays += 1;
 522
 523   return arr;
 524 }