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     {
  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
  73    multi-threaded mode, it is ok to free it.  If not, we add it to the
  74    garbage heap to be freed later. */
  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     {
  82       objc_free (vp);
  83       if (first_free_data)
  84         sarray_remove_garbage ();
  85     }
  86   else
  87     {
  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
  96    safe.  */
  97 void
  98 sarray_at_put (struct sarray *array, sidx index, void *element)
  99 {
 100 #ifdef OBJC_SPARSE3
 101   struct sindex **the_index;
 102   struct sindex *new_index;
 103 #endif
 104   struct sbucket **the_bucket;
 105   struct sbucket *new_bucket;
 106 #ifdef OBJC_SPARSE3
 107   size_t ioffset;
 108 #endif
 109   size_t boffset;
 110   size_t eoffset;
 111 #ifdef PRECOMPUTE_SELECTORS
 112   union sofftype xx;
 113   xx.idx = index;
 114 #ifdef OBJC_SPARSE3
 115   ioffset = xx.off.ioffset;
 116 #endif
 117   boffset = xx.off.boffset;
 118   eoffset = xx.off.eoffset;
 119 #else /* not PRECOMPUTE_SELECTORS */
 120 #ifdef OBJC_SPARSE3
 121   ioffset = index/INDEX_CAPACITY;
 122   boffset = (index/BUCKET_SIZE)%INDEX_SIZE;
 123   eoffset = index%BUCKET_SIZE;
 124 #else
 125   boffset = index/BUCKET_SIZE;
 126   eoffset = index%BUCKET_SIZE;
 127 #endif
 128 #endif /* not PRECOMPUTE_SELECTORS */
 129
 130   assert (soffset_decode (index) < array->capacity); /* Range check */
 131
 132 #ifdef OBJC_SPARSE3
 133   the_index = &(array->indices[ioffset]);
 134   the_bucket = &((*the_index)->buckets[boffset]);
 135 #else
 136   the_bucket = &(array->buckets[boffset]);
 137 #endif
 138
 139   if ((*the_bucket)->elems[eoffset] == element)
 140     return;             /* Great! we just avoided a lazy copy.  */
 141
 142 #ifdef OBJC_SPARSE3
 143
 144   /* First, perform lazy copy/allocation of index if needed.  */
 145
 146   if ((*the_index) == array->empty_index)
 147     {
 148       /* The index was previously empty, allocate a new.  */
 149       new_index = (struct sindex *) objc_malloc (sizeof (struct sindex));
 150       memcpy (new_index, array->empty_index, sizeof (struct sindex));
 151       new_index->version.version = array->version.version;
 152       *the_index = new_index;                     /* Prepared for install. */
 153       the_bucket = &((*the_index)->buckets[boffset]);
 154
 155       nindices += 1;
 156     }
 157   else if ((*the_index)->version.version != array->version.version)
 158     {
 159       /* This index must be lazy copied.  */
 160       struct sindex *old_index = *the_index;
 161       new_index = (struct sindex *) objc_malloc (sizeof (struct sindex));
 162       memcpy (new_index, old_index, sizeof (struct sindex));
 163       new_index->version.version = array->version.version;
 164       *the_index = new_index;                     /* Prepared for install. */
 165       the_bucket = &((*the_index)->buckets[boffset]);
 166
 167       nindices += 1;
 168     }
 169
 170 #endif /* OBJC_SPARSE3 */
 171
 172   /* Next, perform lazy allocation/copy of the bucket if needed.  */
 173   if ((*the_bucket) == array->empty_bucket)
 174     {
 175       /* The bucket was previously empty (or something like that),
 176          allocate a new.  This is the effect of `lazy' allocation.  */
 177       new_bucket = (struct sbucket *) objc_malloc (sizeof (struct sbucket));
 178       memcpy ((void *) new_bucket, (const void *) array->empty_bucket,
 179               sizeof (struct sbucket));
 180       new_bucket->version.version = array->version.version;
 181       *the_bucket = new_bucket;                   /* Prepared for install. */
 182
 183       nbuckets += 1;
 184
 185     }
 186   else if ((*the_bucket)->version.version != array->version.version)
 187     {
 188       /* Perform lazy copy.  */
 189       struct sbucket *old_bucket = *the_bucket;
 190       new_bucket = (struct sbucket *) objc_malloc (sizeof (struct sbucket));
 191       memcpy (new_bucket, old_bucket, sizeof (struct sbucket));
 192       new_bucket->version.version = array->version.version;
 193       *the_bucket = new_bucket;                   /* Prepared for install. */
 194
 195       nbuckets += 1;
 196     }
 197   (*the_bucket)->elems[eoffset] = element;
 198 }
 199
 200 void
 201 sarray_at_put_safe (struct sarray *array, sidx index, void *element)
 202 {
 203   if (soffset_decode (index) >= array->capacity)
 204     sarray_realloc (array, soffset_decode (index) + 1);
 205   sarray_at_put (array, index, element);
 206 }
 207
 208 struct sarray *
 209 sarray_new (int size, void *default_element)
 210 {
 211   struct sarray *arr;
 212 #ifdef OBJC_SPARSE3
 213   size_t num_indices = ((size - 1)/(INDEX_CAPACITY)) + 1;
 214   struct sindex **new_indices;
 215 #else /* OBJC_SPARSE2 */
 216   size_t num_indices = ((size - 1)/BUCKET_SIZE) + 1;
 217   struct sbucket **new_buckets;
 218 #endif
 219   size_t counter;
 220
 221   assert (size > 0);
 222
 223   /* Allocate core array.  */
 224   arr = (struct sarray *) objc_malloc (sizeof (struct sarray));
 225   arr->version.version = 0;
 226
 227   /* Initialize members.  */
 228 #ifdef OBJC_SPARSE3
 229   arr->capacity = num_indices*INDEX_CAPACITY;
 230   new_indices = (struct sindex **)
 231     objc_malloc (sizeof (struct sindex *) * num_indices);
 232
 233   arr->empty_index = (struct sindex *) objc_malloc (sizeof (struct sindex));
 234   arr->empty_index->version.version = 0;
 235
 236   narrays  += 1;
 237   idxsize  += num_indices;
 238   nindices += 1;
 239
 240 #else /* OBJC_SPARSE2 */
 241   arr->capacity = num_indices*BUCKET_SIZE;
 242   new_buckets = (struct sbucket **)
 243     objc_malloc (sizeof (struct sbucket *) * num_indices);
 244
 245   narrays  += 1;
 246   idxsize  += num_indices;
 247
 248 #endif
 249
 250   arr->empty_bucket = (struct sbucket *) objc_malloc (sizeof (struct sbucket));
 251   arr->empty_bucket->version.version = 0;
 252
 253   nbuckets += 1;
 254
 255   arr->ref_count = 1;
 256   arr->is_copy_of = (struct sarray *) 0;
 257
 258   for (counter = 0; counter < BUCKET_SIZE; counter++)
 259     arr->empty_bucket->elems[counter] = default_element;
 260
 261 #ifdef OBJC_SPARSE3
 262   for (counter = 0; counter < INDEX_SIZE; counter++)
 263     arr->empty_index->buckets[counter] = arr->empty_bucket;
 264
 265   for (counter = 0; counter < num_indices; counter++)
 266     new_indices[counter] = arr->empty_index;
 267
 268 #else /* OBJC_SPARSE2 */
 269
 270   for (counter = 0; counter < num_indices; counter++)
 271     new_buckets[counter] = arr->empty_bucket;
 272
 273 #endif
 274
 275 #ifdef OBJC_SPARSE3
 276   arr->indices = new_indices;
 277 #else /* OBJC_SPARSE2 */
 278   arr->buckets = new_buckets;
 279 #endif
 280
 281   return arr;
 282 }
 283 \f
 284
 285 /* Reallocate the sparse array to hold `newsize' entries Note: We
 286    really allocate and then free.  We have to do this to ensure that
 287    any concurrent readers notice the update.  */
 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 #ifdef OBJC_SPARSE3
 324       new_max_index += 4;
 325       rounded_size = (new_max_index + 1) * INDEX_CAPACITY;
 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         {
 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 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     {
 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         {
 416           int c2;
 417           for (c2 = 0; c2 < INDEX_SIZE; c2++)
 418             {
 419               struct sbucket *bkt = idx->buckets[c2];
 420               if ((bkt != array->empty_bucket)
 421                   && (bkt->version.version == array->version.version))
 422                 {
 423                   sarray_free_garbage (bkt);
 424                   nbuckets -= 1;
 425                 }
 426             }
 427           sarray_free_garbage (idx);
 428           nindices -= 1;
 429         }
 430 #else /* OBJC_SPARSE2 */
 431       struct sbucket *bkt = old_buckets[counter];
 432       if ((bkt != array->empty_bucket)
 433           && (bkt->version.version == array->version.version))
 434         {
 435           sarray_free_garbage (bkt);
 436           nbuckets -= 1;
 437         }
 438 #endif
 439     }
 440
 441 #ifdef OBJC_SPARSE3
 442   /* Free empty_index.  */
 443   if (array->empty_index->version.version == array->version.version)
 444     {
 445       sarray_free_garbage (array->empty_index);
 446       nindices -= 1;
 447     }
 448 #endif
 449
 450   /* Free empty_bucket.  */
 451   if (array->empty_bucket->version.version == array->version.version)
 452     {
 453       sarray_free_garbage (array->empty_bucket);
 454       nbuckets -= 1;
 455     }
 456   idxsize -= (old_max_index + 1);
 457   narrays -= 1;
 458
 459 #ifdef OBJC_SPARSE3
 460   /* Free bucket table.  */
 461   sarray_free_garbage (array->indices);
 462 #else
 463   /* Free bucket table.  */
 464   sarray_free_garbage (array->buckets);
 465 #endif
 466
 467   /* If this is a copy of another array, we free it (which might just
 468      decrement its reference count so it will be freed when no longer
 469      in use).  */
 470   if (array->is_copy_of)
 471     sarray_free (array->is_copy_of);
 472
 473   /* Free array.  */
 474   sarray_free_garbage (array);
 475 }
 476
 477 /* This is a lazy copy.  Only the core of the structure is actually
 478    copied.  */
 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 }