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