Return to sarray.h CVS log

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

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

1.1     ! root        1: /* Sparse Arrays for Objective C dispatch tables
        !             2:    Copyright (C) 1993 Free Software Foundation, Inc.
        !             3: 
        !             4: Author: Kresten Krab Thorup
        !             5: 
        !             6: This file is part of GNU CC.
        !             7: 
        !             8: GNU CC is free software; you can redistribute it and/or modify
        !             9: it under the terms of the GNU General Public License as published by
        !            10: the Free Software Foundation; either version 2, or (at your option)
        !            11: any later version.
        !            12: 
        !            13: GNU CC is distributed in the hope that it will be useful,
        !            14: but WITHOUT ANY WARRANTY; without even the implied warranty of
        !            15: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
        !            16: GNU General Public License for more details.
        !            17: 
        !            18: You should have received a copy of the GNU General Public License
        !            19: along with GNU CC; see the file COPYING.  If not, write to
        !            20: the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
        !            21: 
        !            22: /* As a special exception, if you link this library with files
        !            23:    compiled with GCC to produce an executable, this does not cause
        !            24:    the resulting executable to be covered by the GNU General Public License.
        !            25:    This exception does not however invalidate any other reasons why
        !            26:    the executable file might be covered by the GNU General Public License.  */
        !            27: 
        !            28: #ifndef __sarray_INCLUDE_GNU
        !            29: #define __sarray_INCLUDE_GNU
        !            30: 
        !            31: #define OBJC_SPARSE2           /* 2-level sparse array */
        !            32: /* #define OBJC_SPARSE3 */      /* 3-level sparse array */
        !            33: 
        !            34: #ifdef OBJC_SPARSE2
        !            35: extern const char* __objc_sparse2_id;
        !            36: #endif
        !            37: 
        !            38: #ifdef OBJC_SPARSE3
        !            39: extern const char* __objc_sparse3_id;
        !            40: #endif
        !            41: 
        !            42: #ifdef IN_GCC
        !            43: #include "gstddef.h"
        !            44: #else
        !            45: #include "stddef.h"
        !            46: #endif
        !            47: 
        !            48: extern int nbuckets;           /* for stats */
        !            49: extern int nindices;
        !            50: extern int narrays;
        !            51: extern int idxsize;
        !            52: 
        !            53: #include <assert.h>
        !            54: 
        !            55: /* An unsigned integer of same size as a pointer */
        !            56: #define SIZET_BITS (sizeof(size_t)*8)
        !            57: 
        !            58: #if defined(sparc) || defined(OBJC_SPARSE2)
        !            59: #define PRECOMPUTE_SELECTORS
        !            60: #endif
        !            61: 
        !            62: #ifdef OBJC_SPARSE3
        !            63: 
        !            64: /* Buckets are 8 words each */
        !            65: #define BUCKET_BITS 3
        !            66: #define BUCKET_SIZE (1<<BUCKET_BITS)
        !            67: #define BUCKET_MASK (BUCKET_SIZE-1)
        !            68: 
        !            69: /* Indices are 16 words each */
        !            70: #define INDEX_BITS 4
        !            71: #define INDEX_SIZE (1<<INDEX_BITS)
        !            72: #define INDEX_MASK (INDEX_SIZE-1)
        !            73: 
        !            74: #define INDEX_CAPACITY (BUCKET_SIZE*INDEX_SIZE)
        !            75: 
        !            76: #else /* OBJC_SPARSE2 */
        !            77: 
        !            78: /* Buckets are 32 words each */
        !            79: #define BUCKET_BITS 5
        !            80: #define BUCKET_SIZE (1<<BUCKET_BITS)
        !            81: #define BUCKET_MASK (BUCKET_SIZE-1)
        !            82: 
        !            83: #endif /* OBJC_SPARSE2 */
        !            84: 
        !            85: typedef size_t sidx;
        !            86: 
        !            87: #ifdef PRECOMPUTE_SELECTORS
        !            88: 
        !            89: struct soffset {
        !            90: #ifdef OBJC_SPARSE3
        !            91:   unsigned int unused : SIZET_BITS/4;
        !            92:   unsigned int eoffset : SIZET_BITS/4;
        !            93:   unsigned int boffset : SIZET_BITS/4;
        !            94:   unsigned int ioffset : SIZET_BITS/4;
        !            95: #else /* OBJC_SPARSE2 */
        !            96: #ifdef sparc
        !            97:   unsigned int boffset : (SIZET_BITS - 2) - BUCKET_BITS;
        !            98:   unsigned int eoffset : BUCKET_BITS;
        !            99:   unsigned int unused  : 2;
        !           100: #else
        !           101:   unsigned int boffset : SIZET_BITS/2;
        !           102:   unsigned int eoffset : SIZET_BITS/2;
        !           103: #endif
        !           104: #endif /* OBJC_SPARSE2 */
        !           105: };
        !           106: 
        !           107: union sofftype {
        !           108:   struct soffset off;
        !           109:   sidx idx;
        !           110: };
        !           111: 
        !           112: #endif /* not PRECOMPUTE_SELECTORS */
        !           113: 
        !           114: void * __objc_xrealloc (void *optr, size_t size);
        !           115: void * __objc_xmalloc (size_t size);
        !           116: 
        !           117: struct sbucket {
        !           118:   void* elems[BUCKET_SIZE];    /* elements stored in array */
        !           119:   short version;                       /* used for copy-on-write */
        !           120: };
        !           121: 
        !           122: #ifdef OBJC_SPARSE3
        !           123: 
        !           124: struct sindex {
        !           125:   struct sbucket* buckets[INDEX_SIZE];
        !           126:   short version;
        !           127: };
        !           128: 
        !           129: #endif /* OBJC_SPARSE3 */
        !           130: 
        !           131: struct sarray {
        !           132: #ifdef OBJC_SPARSE3
        !           133:   struct sindex** indices;
        !           134:   struct sindex* empty_index;
        !           135: #else /* OBJC_SPARSE2 */
        !           136:   struct sbucket** buckets;
        !           137: #endif  /* OBJC_SPARSE2 */
        !           138:   struct sbucket* empty_bucket;
        !           139:   short version;
        !           140:   short ref_count;
        !           141:   struct sarray* is_copy_of;
        !           142:   int capacity;
        !           143: };
        !           144: 
        !           145: struct sarray* sarray_new(int, void* default_element);
        !           146: void sarray_free(struct sarray*);
        !           147: struct sarray* sarray_lazy_copy(struct sarray*);
        !           148: struct sarray* sarray_hard_copy(struct sarray*); /* ... like the name? */
        !           149: void sarray_realloc(struct sarray*, int new_size);
        !           150: void sarray_at_put(struct sarray*, sidx index, void* elem);
        !           151: void sarray_at_put_safe(struct sarray*, sidx index, void* elem);
        !           152: 
        !           153: 
        !           154: #ifdef PRECOMPUTE_SELECTORS
        !           155: /* Transform soffset values to ints and vica verca */
        !           156: static inline unsigned int
        !           157: soffset_decode(sidx index)
        !           158: {
        !           159:   union sofftype x;
        !           160:   x.idx = index;
        !           161: #ifdef OBJC_SPARSE3
        !           162:   return x.off.eoffset
        !           163:     + (x.off.boffset*BUCKET_SIZE)
        !           164:       + (x.off.ioffset*INDEX_CAPACITY);
        !           165: #else /* OBJC_SPARSE2 */
        !           166:   return x.off.eoffset + (x.off.boffset*BUCKET_SIZE);
        !           167: #endif /* OBJC_SPARSE2 */
        !           168: }
        !           169: 
        !           170: static inline sidx
        !           171: soffset_encode(size_t offset)
        !           172: {
        !           173:   union sofftype x;
        !           174:   x.off.eoffset = offset%BUCKET_SIZE;
        !           175: #ifdef OBJC_SPARSE3
        !           176:   x.off.boffset = (offset/BUCKET_SIZE)%INDEX_SIZE;
        !           177:   x.off.ioffset = offset/INDEX_CAPACITY;
        !           178: #else /* OBJC_SPARSE2 */
        !           179:   x.off.boffset = offset/BUCKET_SIZE;
        !           180: #endif
        !           181:   return (sidx)x.idx;
        !           182: }
        !           183: 
        !           184: #else /* not PRECOMPUTE_SELECTORS */
        !           185: 
        !           186: static inline size_t
        !           187: soffset_decode(sidx index)
        !           188: {
        !           189:   return index;
        !           190: }
        !           191: 
        !           192: static inline sidx
        !           193: soffset_encode(size_t offset)
        !           194: {
        !           195:   return offset;
        !           196: }
        !           197: #endif /* not PRECOMPUTE_SELECTORS */
        !           198: 
        !           199: /* Get element from the Sparse array `array' at offset `index' */
        !           200: 
        !           201: static inline void* sarray_get(struct sarray* array, sidx index)
        !           202: {
        !           203: #ifdef PRECOMPUTE_SELECTORS
        !           204:   union sofftype x;
        !           205:   x.idx = index;
        !           206: #ifdef OBJC_SPARSE3
        !           207:   return 
        !           208:     array->
        !           209:       indices[x.off.ioffset]->
        !           210:        buckets[x.off.boffset]->
        !           211:          elems[x.off.eoffset];
        !           212: #else /* OBJC_SPARSE2 */
        !           213:   return array->buckets[x.off.boffset]->elems[x.off.eoffset];
        !           214: #endif /* OBJC_SPARSE2 */
        !           215: #else /* not PRECOMPUTE_SELECTORS */
        !           216: #ifdef OBJC_SPARSE3
        !           217:   return array->
        !           218:     indices[index/INDEX_CAPACITY]->
        !           219:       buckets[(index/BUCKET_SIZE)%INDEX_SIZE]->
        !           220:        elems[index%BUCKET_SIZE];
        !           221: #else /* OBJC_SPARSE2 */
        !           222:   return array->buckets[index/BUCKET_SIZE]->elems[index%BUCKET_SIZE];
        !           223: #endif /* not OBJC_SPARSE3 */
        !           224: #endif /* not PRECOMPUTE_SELECTORS */
        !           225: }
        !           226: 
        !           227: static inline void* sarray_get_safe(struct sarray* array, sidx index)
        !           228: {
        !           229:   if(soffset_decode(index) < array->capacity)
        !           230:     return sarray_get(array, index);
        !           231:   else
        !           232:     return (array->empty_bucket->elems[0]);
        !           233: }
        !           234: 
        !           235: #endif /* __sarray_INCLUDE_GNU */

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