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