libobjc/sarray.c

   1 /* Sparse Arrays for Objective C dispatch tables
   2    Copyright (C) 1993, 1995, 1996 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   int 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   int 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
 387 #ifdef OBJC_SPARSE3
 388   size_t old_max_index = (array->capacity-1)/INDEX_CAPACITY;
 389   struct sindex ** old_indices;
 390 #else
 391   size_t old_max_index = (array->capacity-1)/BUCKET_SIZE;
 392   struct sbucket ** old_buckets;
 393 #endif
 394   int counter = 0;
 395
 396   assert(array->ref_count != 0);        /* Freed multiple times!!! */
 397
 398   if(--(array->ref_count) != 0) /* There exists copies of me */
 399     return;
 400
 401 #ifdef OBJC_SPARSE3
 402   old_indices = array->indices;
 403 #else
 404   old_buckets = array->buckets;
 405 #endif
 406
 407   if((array->is_copy_of) && ((array->is_copy_of->ref_count - 1) == 0))
 408     sarray_free(array->is_copy_of);
 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 = array->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   /* free array */
 467   sarray_free_garbage(array);
 468 }
 469
 470 /* This is a lazy copy.  Only the core of the structure is actually */
 471 /* copied.   */
 472
 473 struct sarray*
 474 sarray_lazy_copy(struct sarray* oarr)
 475 {
 476   struct sarray* arr;
 477
 478 #ifdef OBJC_SPARSE3
 479   size_t num_indices = ((oarr->capacity-1)/INDEX_CAPACITY)+1;
 480   struct sindex ** new_indices;
 481 #else /* OBJC_SPARSE2 */
 482   size_t num_indices = ((oarr->capacity-1)/BUCKET_SIZE)+1;
 483   struct sbucket ** new_buckets;
 484 #endif
 485
 486   /* Allocate core array */
 487   arr = (struct sarray*) objc_malloc(sizeof(struct sarray)); /* !!! */
 488   arr->version.version = oarr->version.version + 1;
 489 #ifdef OBJC_SPARSE3
 490   arr->empty_index = oarr->empty_index;
 491 #endif
 492   arr->empty_bucket = oarr->empty_bucket;
 493   arr->ref_count = 1;
 494   oarr->ref_count += 1;
 495   arr->is_copy_of = oarr;
 496   arr->capacity = oarr->capacity;
 497
 498 #ifdef OBJC_SPARSE3
 499   /* Copy bucket table */
 500   new_indices = (struct sindex**)
 501     objc_malloc(sizeof(struct sindex*)*num_indices);
 502   memcpy( new_indices,oarr->indices,
 503         sizeof(struct sindex*)*num_indices);
 504   arr->indices = new_indices;
 505 #else
 506   /* Copy bucket table */
 507   new_buckets = (struct sbucket**)
 508     objc_malloc(sizeof(struct sbucket*)*num_indices);
 509   memcpy( new_buckets,oarr->buckets,
 510         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 }