Return to sarray.c CVS log

Up to [Apple XNU] / GNUtools / cc / objc

Annotation of GNUtools/cc/objc/sarray.c, revision 1.1

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

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.