libobjc/sarray.c

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