![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to sarray.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [GCC 2.x] / gcc / objc|
Return to sarray.h CVS log | Up to [GCC 2.x] / gcc / objc |
1.1 root 1: /* Sparse Arrays for Objective C dispatch tables 1.1.1.3 ! root 2: Copyright (C) 1993, 1995 Free Software Foundation, Inc. 1.1 root 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 1.1.1.3 ! root 20: the Free Software Foundation, 59 Temple Place - Suite 330, ! 21: Boston, MA 02111-1307, USA. */ 1.1 root 22: 23: /* As a special exception, if you link this library with files 24: compiled with GCC to produce an executable, this does not cause 25: the resulting executable to be covered by the GNU General Public License. 26: This exception does not however invalidate any other reasons why 27: the executable file might be covered by the GNU General Public License. */ 28: 29: #ifndef __sarray_INCLUDE_GNU 30: #define __sarray_INCLUDE_GNU 31: 32: #define OBJC_SPARSE2 /* 2-level sparse array */ 33: /* #define OBJC_SPARSE3 */ /* 3-level sparse array */ 34: 35: #ifdef OBJC_SPARSE2 36: extern const char* __objc_sparse2_id; 37: #endif 38: 39: #ifdef OBJC_SPARSE3 40: extern const char* __objc_sparse3_id; 41: #endif 42: 1.1.1.2 root 43: #include <stddef.h> 1.1 root 44: 45: extern int nbuckets; /* for stats */ 46: extern int nindices; 47: extern int narrays; 48: extern int idxsize; 49: 50: #include <assert.h> 51: 52: /* An unsigned integer of same size as a pointer */ 53: #define SIZET_BITS (sizeof(size_t)*8) 54: 1.1.1.3 ! root 55: #if defined(__sparc__) || defined(OBJC_SPARSE2) 1.1 root 56: #define PRECOMPUTE_SELECTORS 57: #endif 58: 59: #ifdef OBJC_SPARSE3 60: 61: /* Buckets are 8 words each */ 62: #define BUCKET_BITS 3 63: #define BUCKET_SIZE (1<<BUCKET_BITS) 64: #define BUCKET_MASK (BUCKET_SIZE-1) 65: 66: /* Indices are 16 words each */ 67: #define INDEX_BITS 4 68: #define INDEX_SIZE (1<<INDEX_BITS) 69: #define INDEX_MASK (INDEX_SIZE-1) 70: 71: #define INDEX_CAPACITY (BUCKET_SIZE*INDEX_SIZE) 72: 73: #else /* OBJC_SPARSE2 */ 74: 75: /* Buckets are 32 words each */ 76: #define BUCKET_BITS 5 77: #define BUCKET_SIZE (1<<BUCKET_BITS) 78: #define BUCKET_MASK (BUCKET_SIZE-1) 79: 80: #endif /* OBJC_SPARSE2 */ 81: 82: typedef size_t sidx; 83: 84: #ifdef PRECOMPUTE_SELECTORS 85: 86: struct soffset { 87: #ifdef OBJC_SPARSE3 88: unsigned int unused : SIZET_BITS/4; 89: unsigned int eoffset : SIZET_BITS/4; 90: unsigned int boffset : SIZET_BITS/4; 91: unsigned int ioffset : SIZET_BITS/4; 92: #else /* OBJC_SPARSE2 */ 1.1.1.3 ! root 93: #ifdef __sparc__ 1.1 root 94: unsigned int boffset : (SIZET_BITS - 2) - BUCKET_BITS; 95: unsigned int eoffset : BUCKET_BITS; 96: unsigned int unused : 2; 97: #else 98: unsigned int boffset : SIZET_BITS/2; 99: unsigned int eoffset : SIZET_BITS/2; 100: #endif 101: #endif /* OBJC_SPARSE2 */ 102: }; 103: 104: union sofftype { 105: struct soffset off; 106: sidx idx; 107: }; 108: 109: #endif /* not PRECOMPUTE_SELECTORS */ 110: 111: void * __objc_xrealloc (void *optr, size_t size); 112: void * __objc_xmalloc (size_t size); 113: 114: struct sbucket { 115: void* elems[BUCKET_SIZE]; /* elements stored in array */ 116: short version; /* used for copy-on-write */ 117: }; 118: 119: #ifdef OBJC_SPARSE3 120: 121: struct sindex { 122: struct sbucket* buckets[INDEX_SIZE]; 123: short version; 124: }; 125: 126: #endif /* OBJC_SPARSE3 */ 127: 128: struct sarray { 129: #ifdef OBJC_SPARSE3 130: struct sindex** indices; 131: struct sindex* empty_index; 132: #else /* OBJC_SPARSE2 */ 133: struct sbucket** buckets; 134: #endif /* OBJC_SPARSE2 */ 135: struct sbucket* empty_bucket; 136: short version; 137: short ref_count; 138: struct sarray* is_copy_of; 1.1.1.3 ! root 139: size_t capacity; 1.1 root 140: }; 141: 142: struct sarray* sarray_new(int, void* default_element); 143: void sarray_free(struct sarray*); 144: struct sarray* sarray_lazy_copy(struct sarray*); 145: struct sarray* sarray_hard_copy(struct sarray*); /* ... like the name? */ 146: void sarray_realloc(struct sarray*, int new_size); 147: void sarray_at_put(struct sarray*, sidx index, void* elem); 148: void sarray_at_put_safe(struct sarray*, sidx index, void* elem); 149: 150: 151: #ifdef PRECOMPUTE_SELECTORS 152: /* Transform soffset values to ints and vica verca */ 153: static inline unsigned int 154: soffset_decode(sidx index) 155: { 156: union sofftype x; 157: x.idx = index; 158: #ifdef OBJC_SPARSE3 159: return x.off.eoffset 160: + (x.off.boffset*BUCKET_SIZE) 161: + (x.off.ioffset*INDEX_CAPACITY); 162: #else /* OBJC_SPARSE2 */ 163: return x.off.eoffset + (x.off.boffset*BUCKET_SIZE); 164: #endif /* OBJC_SPARSE2 */ 165: } 166: 167: static inline sidx 168: soffset_encode(size_t offset) 169: { 170: union sofftype x; 171: x.off.eoffset = offset%BUCKET_SIZE; 172: #ifdef OBJC_SPARSE3 173: x.off.boffset = (offset/BUCKET_SIZE)%INDEX_SIZE; 174: x.off.ioffset = offset/INDEX_CAPACITY; 175: #else /* OBJC_SPARSE2 */ 176: x.off.boffset = offset/BUCKET_SIZE; 177: #endif 178: return (sidx)x.idx; 179: } 180: 181: #else /* not PRECOMPUTE_SELECTORS */ 182: 183: static inline size_t 184: soffset_decode(sidx index) 185: { 186: return index; 187: } 188: 189: static inline sidx 190: soffset_encode(size_t offset) 191: { 192: return offset; 193: } 194: #endif /* not PRECOMPUTE_SELECTORS */ 195: 196: /* Get element from the Sparse array `array' at offset `index' */ 197: 198: static inline void* sarray_get(struct sarray* array, sidx index) 199: { 200: #ifdef PRECOMPUTE_SELECTORS 201: union sofftype x; 202: x.idx = index; 203: #ifdef OBJC_SPARSE3 204: return 205: array-> 206: indices[x.off.ioffset]-> 207: buckets[x.off.boffset]-> 208: elems[x.off.eoffset]; 209: #else /* OBJC_SPARSE2 */ 210: return array->buckets[x.off.boffset]->elems[x.off.eoffset]; 211: #endif /* OBJC_SPARSE2 */ 212: #else /* not PRECOMPUTE_SELECTORS */ 213: #ifdef OBJC_SPARSE3 214: return array-> 215: indices[index/INDEX_CAPACITY]-> 216: buckets[(index/BUCKET_SIZE)%INDEX_SIZE]-> 217: elems[index%BUCKET_SIZE]; 218: #else /* OBJC_SPARSE2 */ 219: return array->buckets[index/BUCKET_SIZE]->elems[index%BUCKET_SIZE]; 220: #endif /* not OBJC_SPARSE3 */ 221: #endif /* not PRECOMPUTE_SELECTORS */ 222: } 223: 224: static inline void* sarray_get_safe(struct sarray* array, sidx index) 225: { 226: if(soffset_decode(index) < array->capacity) 227: return sarray_get(array, index); 228: else 229: return (array->empty_bucket->elems[0]); 230: } 231: 232: #endif /* __sarray_INCLUDE_GNU */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.