err.no Git - sope/blob - gnustep-objc/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 <string.h>
  31 #include "assert.h"
  32 #include "objc-api.h"
  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 const char* __objc_sparse2_id = "2 level sparse indices";
  42
  43 #ifdef __alpha__
  44 const void *memcpy (void*, const void*, size_t);
  45 #endif
  46
  47 static void sarray_free_garbage(void *vp);
  48
  49 /* sparse array 2 */
  50
  51 #if BUCKET_SIZE == 32
  52 static struct sbucket empty_bucket_32 = {
  53   { NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  54     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  55     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  56     NULL, NULL }, /* elements */
  57   { -1 }
  58 };
  59 #elif BUCKET_SIZE == 64
  60 static struct sbucket empty_bucket_64 = {
  61   { NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  62     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  63     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  64     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  65     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  66     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  67     NULL, NULL, NULL, NULL }, /* elements */
  68   { -1 }
  69 };
  70 #elif BUCKET_SIZE == 256
  71 static struct sbucket empty_bucket_256 = {
  72   { NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  73     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  74     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  75     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  76     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  77     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  78     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  79     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  80     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  81     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  82     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  83     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  84     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  85     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  86     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  87     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  88     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  89     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  90     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  91     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  92     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  93     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  94     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  95     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  96     NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  97     NULL, NULL, NULL, NULL, NULL, NULL }, /* elements */
  98   { -1 }
  99 };
 100 #endif
 101
 102 struct sarray *sarray_new (int size)
 103 {
 104   struct sarray  *arr;
 105   size_t         num_indices = ((size - 1) / BUCKET_SIZE) + 1;
 106   struct sbucket **new_buckets;
 107   int            counter;
 108
 109   assert(size > 0);
 110
 111   /* Allocate core array */
 112   arr = (struct sarray*)OBJC_MALLOC_UNCOLLECTABLE(sizeof(struct sarray));
 113   arr->version.version = 0;
 114
 115   /* Initialize members */
 116   arr->capacity = num_indices * BUCKET_SIZE;
 117   new_buckets = (struct sbucket **)
 118     OBJC_MALLOC_UNCOLLECTABLE(sizeof(struct sbucket *) * num_indices);
 119
 120   narrays  += 1;
 121   idxsize  += num_indices;
 122
 123 #if BUCKET_SIZE == 32 || BUCKET_SIZE == 64 ||BUCKET_SIZE == 256
 124 #  if BUCKET_SIZE == 32
 125     arr->empty_bucket = &empty_bucket_32;
 126 #  elif BUCKET_SIZE == 64
 127     arr->empty_bucket = &empty_bucket_64;
 128 #  elif BUCKET_SIZE == 256
 129     arr->empty_bucket = &empty_bucket_256;
 130 #  endif
 131 #else
 132   arr->empty_bucket =
 133     (struct sbucket *)OBJC_MALLOC_UNCOLLECTABLE(sizeof(struct sbucket));
 134   arr->empty_bucket->version.version = 0;
 135 #endif
 136
 137   nbuckets += 1;
 138
 139   arr->ref_count = 1;
 140   arr->is_copy_of = (struct sarray*)0;
 141
 142   for (counter = 0; counter < num_indices; counter++)
 143     new_buckets[counter] = arr->empty_bucket;
 144
 145   arr->buckets = new_buckets;
 146
 147   return arr;
 148 }
 149
 150 /* Reallocate the sparse array to hold `newsize' entries
 151    Note: We really allocate and then free.  We have to do this to ensure that
 152    any concurrent readers notice the update. */
 153 void sarray_realloc(struct sarray* array, int newsize)
 154 {
 155   size_t old_max_index = (array->capacity-1)/BUCKET_SIZE;
 156   size_t new_max_index = ((newsize-1)/BUCKET_SIZE);
 157   size_t rounded_size = (new_max_index+1)*BUCKET_SIZE;
 158
 159   struct sbucket ** new_buckets;
 160   struct sbucket ** old_buckets;
 161
 162   int counter;
 163
 164   assert(newsize > 0);
 165
 166   /* The size is the same, just ignore the request */
 167   if(rounded_size <= array->capacity)
 168     return;
 169
 170   assert(array->ref_count == 1);        /* stop if lazy copied... */
 171
 172   /* We are asked to extend the array -- allocate new bucket table, */
 173   /* and insert empty_bucket in newly allocated places. */
 174   if(rounded_size > array->capacity) {
 175       new_max_index += 4;
 176       rounded_size = (new_max_index+1)*BUCKET_SIZE;
 177
 178       /* update capacity */
 179       array->capacity = rounded_size;
 180
 181       old_buckets = array->buckets;
 182       new_buckets = (struct sbucket**)
 183         OBJC_MALLOC_UNCOLLECTABLE((new_max_index + 1) * sizeof(struct sbucket*));
 184
 185       /* copy buckets below old_max_index (they are still valid) */
 186       for(counter = 0; counter <= old_max_index; counter++ )
 187         new_buckets[counter] = old_buckets[counter];
 188
 189       /* reset entries above old_max_index to empty_bucket */
 190       for(counter = old_max_index+1; counter <= new_max_index; counter++)
 191         new_buckets[counter] = array->empty_bucket;
 192
 193       array->buckets = new_buckets;
 194       sarray_free_garbage(old_buckets);
 195
 196       idxsize += (new_max_index-old_max_index);
 197       return;
 198     }
 199 }
 200
 201 /* Free a sparse array allocated with sarray_new */
 202 void sarray_free(struct sarray *array)
 203 {
 204   size_t old_max_bucket_index;
 205   struct sbucket **old_buckets;
 206   register int   counter;
 207
 208   if (array == NULL)
 209     return;
 210
 211   old_max_bucket_index = (array->capacity - 1) / BUCKET_SIZE;
 212
 213   assert(array->ref_count != 0);        /* Freed multiple times!!! */
 214
 215   (array->ref_count)--;
 216   if(array->ref_count > 0)      /* There exists copies of me */
 217     return;
 218
 219   old_buckets = array->buckets;
 220
 221   /* Free all entries that do not point to empty_bucket */
 222   for(counter = 0; counter <= old_max_bucket_index; counter++ ) {
 223     register struct sbucket *bkt = array->buckets[counter];
 224
 225     if ((bkt == NULL) || (bkt == array->empty_bucket))
 226       continue;
 227
 228     if (bkt->version.version == array->version.version) {
 229       /*
 230         only if bucket belongs to this array
 231         (only written records in lazy copies)
 232       */
 233       sarray_free_garbage(bkt); bkt = NULL;
 234       nbuckets -= 1;
 235     }
 236   }
 237
 238   /* free empty_bucket */
 239   if(array->empty_bucket->version.version == array->version.version) {
 240     sarray_free_garbage(array->empty_bucket);
 241     nbuckets -= 1;
 242   }
 243   idxsize -= (old_max_bucket_index + 1);
 244   narrays -= 1;
 245
 246   /* free bucket table */
 247   sarray_free_garbage(array->buckets);
 248
 249   /* release lazy copy */
 250   if (array->is_copy_of) {
 251     assert(array->is_copy_of != array);
 252     assert(array->is_copy_of->version.version < array->version.version);
 253
 254     sarray_free(array->is_copy_of);
 255     array->is_copy_of = NULL;
 256   }
 257
 258   /* free array */
 259   sarray_free_garbage(array);
 260 }
 261
 262 /* This is a lazy copy.  Only the core of the structure is actually */
 263 /* copied.   */
 264
 265 struct sarray *sarray_lazy_copy(struct sarray* oarr)
 266 {
 267   struct sarray* arr;
 268   size_t num_indices = ((oarr->capacity-1)/BUCKET_SIZE)+1;
 269   struct sbucket ** new_buckets;
 270
 271   /* Allocate core array */
 272   arr = (struct sarray *)OBJC_MALLOC_UNCOLLECTABLE(sizeof(struct sarray));
 273   assert(arr != oarr);
 274   arr->version.version =  oarr->version.version + 1;
 275   arr->empty_bucket    =  oarr->empty_bucket;
 276   arr->ref_count       =  1;
 277   oarr->ref_count      += 1;
 278   arr->is_copy_of      =  oarr;
 279   arr->capacity        =  oarr->capacity;
 280
 281   /* Copy bucket table */
 282   new_buckets = (struct sbucket**)
 283     OBJC_MALLOC_UNCOLLECTABLE(sizeof(struct sbucket *) * num_indices);
 284   memcpy(new_buckets, oarr->buckets, sizeof(struct sbucket*)*num_indices);
 285   arr->buckets = new_buckets;
 286   idxsize += num_indices;
 287   narrays += 1;
 288
 289   return arr;
 290 }
 291
 292 void sarray_at_put(struct sarray *array, sidx index, void *element) {
 293   return sarray_at_put_safe(array, index, element);
 294 }
 295
 296 void
 297 sarray_at_put_safe(struct sarray *array, sidx index, void *element)
 298 {
 299   register unsigned int idx;
 300   struct sbucket** the_bucket;
 301   struct sbucket*  new_bucket;
 302   size_t boffset;
 303   size_t eoffset;
 304   boffset = index / BUCKET_SIZE;
 305   eoffset = index % BUCKET_SIZE;
 306
 307   idx = index;
 308
 309 #ifdef __WIN32__
 310   if (array == NULL)
 311     abort();
 312 #endif
 313
 314   if (idx >= array->capacity)
 315     sarray_realloc(array, (idx + 1));
 316
 317   assert(idx < array->capacity); /* Range check */
 318
 319   the_bucket = &(array->buckets[boffset]);
 320
 321   if ((*the_bucket)->elems[eoffset] == element)
 322     return;             /* great! we just avoided a lazy copy */
 323
 324   /* next, perform lazy allocation/copy of the bucket if needed */
 325
 326   if ((*the_bucket) == array->empty_bucket) {
 327
 328     /* The bucket was previously empty (or something like that), */
 329     /* allocate a new.  This is the effect of `lazy' allocation */
 330     new_bucket =
 331       (struct sbucket*)OBJC_MALLOC_UNCOLLECTABLE(sizeof(struct sbucket));
 332
 333     memcpy((void *) new_bucket, (const void*)array->empty_bucket,
 334            sizeof(struct sbucket));
 335     new_bucket->version.version = array->version.version;
 336     *the_bucket = new_bucket;                   /* Prepared for install. */
 337
 338     nbuckets += 1;
 339
 340   } else if ((*the_bucket)->version.version != array->version.version) {
 341
 342     /* Perform lazy copy. */
 343     struct sbucket* old_bucket = *the_bucket;
 344
 345     new_bucket =
 346       (struct sbucket*)OBJC_MALLOC_UNCOLLECTABLE(sizeof(struct sbucket));
 347
 348     memcpy( new_bucket, old_bucket, sizeof(struct sbucket));
 349     new_bucket->version.version = array->version.version;
 350     *the_bucket = new_bucket;                   /* Prepared for install. */
 351
 352     nbuckets += 1;
 353
 354   }
 355   (*the_bucket)->elems[eoffset] = element;
 356 }
 357
 358 /* This function removes any structures left over from free operations
 359    that were not safe in a multi-threaded environment. */
 360 void sarray_remove_garbage(void) {
 361   void **vp;
 362   void *np;
 363
 364   RUNTIME_LOCK;
 365
 366   vp = first_free_data;
 367   first_free_data = NULL;
 368
 369   while (vp) {
 370     np = *vp;
 371 #if OBJC_WITH_GC
 372     GC_FREE(vp);
 373 #else
 374     free(vp);
 375 #endif
 376     vp = np;
 377   }
 378
 379   RUNTIME_UNLOCK;
 380 }
 381
 382 /* Free a block of dynamically allocated memory.  If we are in multi-threaded
 383    mode, it is ok to free it.  If not, we add it to the garbage heap to be
 384    freed later. */
 385
 386 static void sarray_free_garbage(void *vp) {
 387   RUNTIME_LOCK;
 388
 389   if (__objc_runtime_threads_alive == 1) {
 390 #if OBJC_WITH_GC
 391     GC_FREE(vp);
 392 #else
 393     free(vp);
 394 #endif
 395     if (first_free_data)
 396       sarray_remove_garbage();
 397   }
 398   else {
 399     *(void **)vp = first_free_data;
 400     first_free_data = vp;
 401   }
 402
 403   RUNTIME_UNLOCK;
 404 }