libobjc/sarray.c

   1 /* Sparse Arrays for Objective C dispatch tables
   2    Copyright (C) 1993, 1995, 1996, 2002 Free Software Foundation, Inc.
   3
   4 This file is part of GNU CC.
   5
   6 GNU CC 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 GNU CC 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 GNU CC; 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 "sarray.h"
  28 #include "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   if ((array->is_copy_of) && ((array->is_copy_of->ref_count - 1) == 0))
 407     sarray_free (array->is_copy_of);
 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 = array->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   /* free array */
 466   sarray_free_garbage (array);
 467 }
 468
 469 /* This is a lazy copy.  Only the core of the structure is actually */
 470 /* copied.   */
 471
 472 struct sarray *
 473 sarray_lazy_copy (struct sarray *oarr)
 474 {
 475   struct sarray *arr;
 476
 477 #ifdef OBJC_SPARSE3
 478   size_t num_indices = ((oarr->capacity - 1)/INDEX_CAPACITY) + 1;
 479   struct sindex **new_indices;
 480 #else /* OBJC_SPARSE2 */
 481   size_t num_indices = ((oarr->capacity - 1)/BUCKET_SIZE) + 1;
 482   struct sbucket **new_buckets;
 483 #endif
 484
 485   /* Allocate core array */
 486   arr = (struct sarray *) objc_malloc (sizeof (struct sarray)); /* !!! */
 487   arr->version.version = oarr->version.version + 1;
 488 #ifdef OBJC_SPARSE3
 489   arr->empty_index = oarr->empty_index;
 490 #endif
 491   arr->empty_bucket = oarr->empty_bucket;
 492   arr->ref_count = 1;
 493   oarr->ref_count += 1;
 494   arr->is_copy_of = oarr;
 495   arr->capacity = oarr->capacity;
 496
 497 #ifdef OBJC_SPARSE3
 498   /* Copy bucket table */
 499   new_indices = (struct sindex **)
 500     objc_malloc (sizeof (struct sindex *) * num_indices);
 501   memcpy (new_indices, oarr->indices, sizeof (struct sindex *) * num_indices);
 502   arr->indices = new_indices;
 503 #else
 504   /* Copy bucket table */
 505   new_buckets = (struct sbucket **)
 506     objc_malloc (sizeof (struct sbucket *) * num_indices);
 507   memcpy (new_buckets, oarr->buckets, sizeof (struct sbucket *) * num_indices);
 508   arr->buckets = new_buckets;
 509 #endif
 510
 511   idxsize += num_indices;
 512   narrays += 1;
 513
 514   return arr;
 515 }