gcc/objc/sarray.c

   1 /* Sparse Arrays for Objective C dispatch tables
   2    Copyright (C) 1993 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, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  19
  20 /* As a special exception, if you link this library with files
  21    compiled with GCC to produce an executable, this does not cause
  22    the resulting executable to be covered by the GNU General Public License.
  23    This exception does not however invalidate any other reasons why
  24    the executable file might be covered by the GNU General Public License.  */
  25
  26 #include "objc/sarray.h"
  27 #include <stdio.h>
  28 #include "assert.h"
  29
  30 int nbuckets = 0;
  31 int nindices = 0;
  32 int narrays = 0;
  33 int idxsize = 0;
  34
  35 #ifdef OBJC_SPARSE2
  36 const char* __objc_sparse2_id = "2 level sparse indices";
  37 #endif
  38
  39 #ifdef OBJC_SPARSE3
  40 const char* __objc_sparse3_id = "3 level sparse indices";
  41 #endif
  42
  43 void
  44 sarray_at_put(struct sarray* array, sidx index, void* element)
  45 {
  46 #ifdef OBJC_SPARSE3
  47   struct sindex** the_index;
  48 #endif
  49   struct sbucket** the_bucket;
  50 #ifdef OBJC_SPARSE3
  51   size_t ioffset;
  52 #endif
  53   size_t boffset;
  54   size_t eoffset;
  55 #ifdef PRECOMPUTE_SELECTORS
  56   union sofftype xx;
  57   xx.idx = index;
  58 #ifdef OBJC_SPARSE3
  59   ioffset = xx.off.ioffset;
  60 #endif
  61   boffset = xx.off.boffset;
  62   eoffset = xx.off.eoffset;
  63 #else /* not PRECOMPUTE_SELECTORS */
  64 #ifdef OBJC_SPARSE3
  65   ioffset = index/INDEX_CAPACITY;
  66   boffset = (index/BUCKET_SIZE)%INDEX_SIZE;
  67   eoffset = index%BUCKET_SIZE;
  68 #else
  69   boffset = index/BUCKET_SIZE;
  70   eoffset = index%BUCKET_SIZE;
  71 #endif
  72 #endif /* not PRECOMPUTE_SELECTORS */
  73
  74   assert(soffset_decode(index) < array->capacity); /* Range check */
  75
  76 #ifdef OBJC_SPARSE3
  77   the_index = &(array->indices[ioffset]);
  78   the_bucket = &((*the_index)->buckets[boffset]);
  79 #else
  80   the_bucket = &(array->buckets[boffset]);
  81 #endif
  82
  83   if ((*the_bucket)->elems[eoffset] == element)
  84     return;             /* great! we just avoided a lazy copy */
  85
  86 #ifdef OBJC_SPARSE3
  87
  88   /* First, perform lazy copy/allocation of index if needed */
  89
  90   if ((*the_index) == array->empty_index) {
  91
  92     /* The index was previously empty, allocate a new */
  93     *the_index = (struct sindex*)__objc_xmalloc(sizeof(struct sindex));
  94     memcpy(*the_index, array->empty_index, sizeof(struct sindex));
  95     (*the_index)->version = array->version;
  96     the_bucket = &((*the_index)->buckets[boffset]);
  97     nindices += 1;
  98
  99   } else if ((*the_index)->version != array->version) {
 100
 101     /* This index must be lazy copied */
 102     struct sindex* old_index = *the_index;
 103     *the_index = (struct sindex*)__objc_xmalloc(sizeof(struct sindex));
 104     memcpy( *the_index,old_index, sizeof(struct sindex));
 105     (*the_index)->version = array->version;
 106     the_bucket = &((*the_index)->buckets[boffset]);
 107     nindices += 1;
 108
 109   }
 110
 111 #endif /* OBJC_SPARSE3 */
 112
 113   /* next, perform lazy allocation/copy of the bucket if needed */
 114
 115   if ((*the_bucket) == array->empty_bucket) {
 116
 117     /* The bucket was previously empty (or something like that), */
 118     /* allocate a new.  This is the effect of `lazy' allocation */
 119     *the_bucket = (struct sbucket*)__objc_xmalloc(sizeof(struct sbucket));
 120     memcpy( *the_bucket,array->empty_bucket, sizeof(struct sbucket));
 121     (*the_bucket)->version = array->version;
 122     nbuckets += 1;
 123
 124   } else if ((*the_bucket)->version != array->version) {
 125
 126     /* Perform lazy copy. */
 127     struct sbucket* old_bucket = *the_bucket;
 128     *the_bucket = (struct sbucket*)__objc_xmalloc(sizeof(struct sbucket));
 129     memcpy( *the_bucket,old_bucket, sizeof(struct sbucket));
 130     (*the_bucket)->version = array->version;
 131     nbuckets += 1;
 132
 133   }
 134   (*the_bucket)->elems[eoffset] = element;
 135 }
 136
 137 void
 138 sarray_at_put_safe(struct sarray* array, sidx index, void* element)
 139 {
 140   if(soffset_decode(index) >= array->capacity)
 141     sarray_realloc(array, soffset_decode(index)+1);
 142   sarray_at_put(array, index, element);
 143 }
 144
 145 struct sarray*
 146 sarray_new (int size, void* default_element)
 147 {
 148 #ifdef OBJC_SPARSE3
 149   size_t num_indices = ((size-1)/(INDEX_CAPACITY))+1;
 150 #else /* OBJC_SPARSE2 */
 151   size_t num_indices = ((size-1)/BUCKET_SIZE)+1;
 152 #endif
 153   int counter;
 154   struct sarray* arr;
 155
 156   assert(size > 0);
 157
 158   /* Allocate core array */
 159   arr = (struct sarray*) __objc_xmalloc(sizeof(struct sarray));
 160   arr->version = 0;
 161   narrays  += 1;
 162
 163   /* Initialize members */
 164 #ifdef OBJC_SPARSE3
 165   arr->capacity = num_indices*INDEX_CAPACITY;
 166   arr->indices = (struct sindex**)
 167     __objc_xmalloc(sizeof(struct sindex*)*num_indices);
 168   idxsize  += num_indices;
 169
 170   arr->empty_index = (struct sindex*) __objc_xmalloc(sizeof(struct sindex));
 171   arr->empty_index->version = 0;
 172   nindices += 1;
 173
 174 #else /* OBJC_SPARSE2 */
 175   arr->capacity = num_indices*BUCKET_SIZE;
 176   arr->buckets = (struct sbucket**)
 177     __objc_xmalloc(sizeof(struct sbucket*)*num_indices);
 178   idxsize  += num_indices;
 179
 180 #endif
 181
 182   arr->empty_bucket = (struct sbucket*) __objc_xmalloc(sizeof(struct sbucket));
 183   arr->empty_bucket->version = 0;
 184   nbuckets += 1;
 185
 186   arr->ref_count = 1;
 187   arr->is_copy_of = (struct sarray*)0;
 188
 189   for (counter=0; counter<BUCKET_SIZE; counter++)
 190     arr->empty_bucket->elems[counter] = default_element;
 191
 192 #ifdef OBJC_SPARSE3
 193   for (counter=0; counter<INDEX_SIZE; counter++)
 194     arr->empty_index->buckets[counter] = arr->empty_bucket;
 195
 196   for (counter=0; counter<num_indices; counter++)
 197     arr->indices[counter] = arr->empty_index;
 198
 199 #else /* OBJC_SPARSE2 */
 200
 201   for (counter=0; counter<num_indices; counter++)
 202     arr->buckets[counter] = arr->empty_bucket;
 203
 204 #endif
 205
 206   return arr;
 207 }
 208 \f
 209
 210 /* Reallocate the sparse array to hold `newsize' entries */
 211
 212 void
 213 sarray_realloc(struct sarray* array, int newsize)
 214 {
 215 #ifdef OBJC_SPARSE3
 216   int old_max_index = (array->capacity-1)/INDEX_CAPACITY;
 217   int new_max_index = ((newsize-1)/INDEX_CAPACITY);
 218   int rounded_size = (new_max_index+1)*INDEX_CAPACITY;
 219
 220 #else /* OBJC_SPARSE2 */
 221   int old_max_index = (array->capacity-1)/BUCKET_SIZE;
 222   int new_max_index = ((newsize-1)/BUCKET_SIZE);
 223   int rounded_size = (new_max_index+1)*BUCKET_SIZE;
 224
 225 #endif
 226
 227   int counter;
 228
 229   assert(newsize > 0);
 230
 231   /* The size is the same, just ignore the request */
 232   if(rounded_size == array->capacity)
 233     return;
 234
 235   assert(array->ref_count == 1);        /* stop if lazy copied... */
 236
 237   if(rounded_size < array->capacity)
 238     {
 239       /* update capacity */
 240       array->capacity = rounded_size;
 241
 242       /* free buckets above new_max_index */
 243       for(counter = old_max_index; counter > new_max_index; counter-- ) {
 244 #ifdef OBJC_SPARSE3
 245         struct sindex* idx = array->indices[counter];
 246         if((idx != array->empty_index) && (idx->version == array->version)) {
 247           int c2;
 248           for(c2=0; c2<INDEX_SIZE; c2++) {
 249             struct sbucket* bkt = idx->buckets[c2];
 250             if((bkt != array->empty_bucket) && (bkt->version == array->version))
 251               {
 252                 free(bkt);
 253                 nbuckets -= 1;
 254               }
 255           }
 256           free(idx);
 257           nindices -= 1;
 258         }
 259 #else /* OBJC_SPARSE2 */
 260         struct sbucket* bkt = array->buckets[counter];
 261         if ((bkt != array->empty_bucket) && (bkt->version == array->version))
 262           {
 263             free(bkt);
 264             nbuckets -= 1;
 265           }
 266 #endif
 267       }
 268
 269 #ifdef OBJC_SPARSE3
 270       /* realloc to free the space above new_max_index */
 271       array->indices = (struct sindex**)
 272         __objc_xrealloc(array->indices,
 273                         (new_max_index+1)*sizeof(struct sindex*));
 274 #else /* OBJC_SPARSE2 */
 275       array->buckets = (struct sbucket**)
 276         __objc_xrealloc(array->buckets,
 277                         (new_max_index+1)*sizeof(struct sbucket*));
 278 #endif
 279       idxsize -= (old_max_index-new_max_index);
 280
 281       return;
 282     }
 283
 284   /* We are asked to extend the array -- reallocate the bucket table, */
 285   /* and insert empty_bucket in newly allocated places. */
 286   if(rounded_size > array->capacity)
 287     {
 288       /* update capacity */
 289       array->capacity = rounded_size;
 290
 291 #ifdef OBJC_SPARSE3
 292       /* realloc to make room in table above old_max_index */
 293       array->indices = (struct sindex**)
 294         __objc_xrealloc(array->indices,
 295                         (new_max_index+1)*sizeof(struct sindex*));
 296
 297       /* reset entries above old_max_index to empty_bucket */
 298       for(counter = old_max_index+1; counter <= new_max_index; counter++)
 299         array->indices[counter] = array->empty_index;
 300
 301 #else /* OBJC_SPARSE2 */
 302
 303       /* realloc to make room in table above old_max_index */
 304       array->buckets = (struct sbucket**)
 305         __objc_xrealloc(array->buckets,
 306                         (new_max_index+1)*sizeof(struct sbucket*));
 307
 308       /* reset entries above old_max_index to empty_bucket */
 309       for(counter = old_max_index+1; counter <= new_max_index; counter++)
 310         array->buckets[counter] = array->empty_bucket;
 311
 312 #endif
 313       idxsize += (new_max_index-old_max_index);
 314       return;
 315     }
 316 }
 317 \f
 318
 319 /* Free a sparse array allocated with sarray_new */
 320
 321 void
 322 sarray_free(struct sarray* array) {
 323 #ifdef OBJC_SPARSE3
 324   size_t old_max_index = (array->capacity-1)/INDEX_CAPACITY;
 325 #else
 326   size_t old_max_index = (array->capacity-1)/BUCKET_SIZE;
 327 #endif
 328   int counter = 0;
 329
 330   assert(array->ref_count != 0);        /* Freed multiple times!!! */
 331
 332   if(--(array->ref_count) != 0) /* There exists copies of me */
 333     return;
 334
 335   if((array->is_copy_of) && ((array->is_copy_of->ref_count - 1) == 0))
 336     sarray_free(array->is_copy_of);
 337
 338   /* Free all entries that do not point to empty_bucket */
 339   for(counter = 0; counter <= old_max_index; counter++ ) {
 340 #ifdef OBJC_SPARSE3
 341     struct sindex* idx = array->indices[counter];
 342     if((idx != array->empty_index) && (idx->version == array->version)) {
 343       int c2;
 344       for(c2=0; c2<INDEX_SIZE; c2++) {
 345         struct sbucket* bkt = idx->buckets[c2];
 346         if((bkt != array->empty_bucket) && (bkt->version == array->version))
 347           {
 348             free(bkt);
 349             nbuckets -= 1;
 350           }
 351       }
 352       free(idx);
 353       nindices -= 1;
 354     }
 355 #else /* OBJC_SPARSE2 */
 356     struct sbucket* bkt = array->buckets[counter];
 357     if ((bkt != array->empty_bucket) && (bkt->version == array->version))
 358       {
 359         free(bkt);
 360         nbuckets -= 1;
 361       }
 362 #endif
 363   }
 364
 365 #ifdef OBJC_SPARSE3
 366   /* free empty_index */
 367   if(array->empty_index->version == array->version) {
 368     free(array->empty_index);
 369     nindices -= 1;
 370   }
 371 #endif
 372
 373   /* free empty_bucket */
 374   if(array->empty_bucket->version == array->version) {
 375     free(array->empty_bucket);
 376     nbuckets -= 1;
 377   }
 378
 379 #ifdef OBJC_SPARSE3
 380   /* free bucket table */
 381   free(array->indices);
 382   idxsize -= (old_max_index+1);
 383
 384 #else
 385   /* free bucket table */
 386   free(array->buckets);
 387   idxsize -= (old_max_index+1);
 388
 389 #endif
 390
 391   /* free array */
 392   free(array);
 393   narrays -= 1;
 394 }
 395
 396 /* This is a lazy copy.  Only the core of the structure is actually */
 397 /* copied.   */
 398
 399 struct sarray*
 400 sarray_lazy_copy(struct sarray* oarr)
 401 {
 402 #ifdef OBJC_SPARSE3
 403   size_t num_indices = ((oarr->capacity-1)/INDEX_CAPACITY)+1;
 404 #else /* OBJC_SPARSE2 */
 405   size_t num_indices = ((oarr->capacity-1)/BUCKET_SIZE)+1;
 406 #endif
 407   struct sarray* arr;
 408
 409   /* Allocate core array */
 410   arr = (struct sarray*) __objc_xmalloc(sizeof(struct sarray));
 411   memcpy( arr,oarr, sizeof(struct sarray));
 412   arr->version = oarr->version + 1;
 413   arr->is_copy_of = oarr;
 414   oarr->ref_count += 1;
 415   arr->ref_count = 1;
 416
 417 #ifdef OBJC_SPARSE3
 418   /* Copy bucket table */
 419   arr->indices = (struct sindex**)
 420     __objc_xmalloc(sizeof(struct sindex*)*num_indices);
 421   memcpy( arr->indices,oarr->indices,
 422         sizeof(struct sindex*)*num_indices);
 423 #else
 424   /* Copy bucket table */
 425   arr->buckets = (struct sbucket**)
 426     __objc_xmalloc(sizeof(struct sbucket*)*num_indices);
 427   memcpy( arr->buckets,oarr->buckets,
 428         sizeof(struct sbucket*)*num_indices);
 429 #endif
 430
 431   idxsize += num_indices;
 432   narrays += 1;
 433
 434   return arr;
 435 }