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