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