libobjc/sarray.c

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