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