gcc/objc/sarray.h

   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 #include <stddef.h>
  43
  44 extern int nbuckets;            /* for stats */
  45 extern int nindices;
  46 extern int narrays;
  47 extern int idxsize;
  48
  49 #include <assert.h>
  50
  51 #if defined(sparc) || defined(OBJC_SPARSE2)
  52 #define PRECOMPUTE_SELECTORS
  53 #endif
  54
  55 #ifdef OBJC_SPARSE3
  56
  57 /* Buckets are 8 words each */
  58 #define BUCKET_BITS 3
  59 #define BUCKET_SIZE (1<<BUCKET_BITS)
  60 #define BUCKET_MASK (BUCKET_SIZE-1)
  61
  62 /* Indices are 16 words each */
  63 #define INDEX_BITS 4
  64 #define INDEX_SIZE (1<<INDEX_BITS)
  65 #define INDEX_MASK (INDEX_SIZE-1)
  66
  67 #define INDEX_CAPACITY (BUCKET_SIZE*INDEX_SIZE)
  68
  69 #else /* OBJC_SPARSE2 */
  70
  71 /* Buckets are 32 words each */
  72 #define BUCKET_BITS 5
  73 #define BUCKET_SIZE (1<<BUCKET_BITS)
  74 #define BUCKET_MASK (BUCKET_SIZE-1)
  75
  76 #endif /* OBJC_SPARSE2 */
  77
  78 typedef unsigned int sidx;
  79
  80 #ifdef PRECOMPUTE_SELECTORS
  81
  82 struct soffset {
  83 #ifdef OBJC_SPARSE3
  84   unsigned char unused;
  85   unsigned char eoffset;
  86   unsigned char boffset;
  87   unsigned char ioffset;
  88 #else /* OBJC_SPARSE2 */
  89 #ifdef sparc
  90   unsigned int boffset : 30 - BUCKET_BITS;
  91   unsigned int eoffset : BUCKET_BITS;
  92   unsigned int unused  : 2;
  93 #else
  94   unsigned short boffset;
  95   unsigned short eoffset;
  96 #endif
  97 #endif /* OBJC_SPARSE2 */
  98 };
  99
 100 union sofftype {
 101   struct soffset off;
 102   sidx idx;
 103 };
 104
 105 #endif /* not PRECOMPUTE_SELECTORS */
 106
 107 void * __objc_xrealloc (void *optr, size_t size);
 108 void * __objc_xmalloc (size_t size);
 109
 110 struct sbucket {
 111   void* elems[BUCKET_SIZE];     /* elements stored in array */
 112   short version;                        /* used for copy-on-write */
 113 };
 114
 115 #ifdef OBJC_SPARSE3
 116
 117 struct sindex {
 118   struct sbucket* buckets[INDEX_SIZE];
 119   short version;
 120 };
 121
 122 #endif /* OBJC_SPARSE3 */
 123
 124 struct sarray {
 125 #ifdef OBJC_SPARSE3
 126   struct sindex** indices;
 127   struct sindex* empty_index;
 128 #else /* OBJC_SPARSE2 */
 129   struct sbucket** buckets;
 130 #endif  /* OBJC_SPARSE2 */
 131   struct sbucket* empty_bucket;
 132   short version;
 133   short ref_count;
 134   struct sarray* is_copy_of;
 135   int capacity;
 136 };
 137
 138 struct sarray* sarray_new(int, void* default_element);
 139 void sarray_free(struct sarray*);
 140 struct sarray* sarray_lazy_copy(struct sarray*);
 141 struct sarray* sarray_hard_copy(struct sarray*); /* ... like the name? */
 142 void sarray_realloc(struct sarray*, int new_size);
 143 void sarray_at_put(struct sarray*, sidx index, void* elem);
 144 void sarray_at_put_safe(struct sarray*, sidx index, void* elem);
 145 \f
 146
 147 #ifdef PRECOMPUTE_SELECTORS
 148 /* Transform soffset values to ints and vica verca */
 149 static inline unsigned int
 150 soffset_decode(sidx index)
 151 {
 152   union sofftype x;
 153   x.idx = index;
 154 #ifdef OBJC_SPARSE3
 155   return x.off.eoffset
 156     + (x.off.boffset*BUCKET_SIZE)
 157       + (x.off.ioffset*INDEX_CAPACITY);
 158 #else /* OBJC_SPARSE2 */
 159   return x.off.eoffset + (x.off.boffset*BUCKET_SIZE);
 160 #endif /* OBJC_SPARSE2 */
 161 }
 162
 163 static inline sidx
 164 soffset_encode(unsigned int offset)
 165 {
 166   union sofftype x;
 167   x.off.eoffset = offset%BUCKET_SIZE;
 168 #ifdef OBJC_SPARSE3
 169   x.off.boffset = (offset/BUCKET_SIZE)%INDEX_SIZE;
 170   x.off.ioffset = offset/INDEX_CAPACITY;
 171 #else /* OBJC_SPARSE2 */
 172   x.off.boffset = offset/BUCKET_SIZE;
 173 #endif
 174   return (sidx)x.idx;
 175 }
 176
 177 #else /* not PRECOMPUTE_SELECTORS */
 178
 179 static inline unsigned int
 180 soffset_decode(sidx index)
 181 {
 182   return index;
 183 }
 184
 185 static inline sidx
 186 soffset_encode(unsigned int offset)
 187 {
 188   return offset;
 189 }
 190 #endif /* not PRECOMPUTE_SELECTORS */
 191
 192 /* Get element from the Sparse array `array' at offset `index' */
 193
 194 static inline void* sarray_get(struct sarray* array, sidx index)
 195 {
 196 #ifdef PRECOMPUTE_SELECTORS
 197   union sofftype x;
 198   x.idx = index;
 199 #ifdef OBJC_SPARSE3
 200   return
 201     array->
 202       indices[x.off.ioffset]->
 203         buckets[x.off.boffset]->
 204           elems[x.off.eoffset];
 205 #else /* OBJC_SPARSE2 */
 206   return array->buckets[x.off.boffset]->elems[x.off.eoffset];
 207 #endif /* OBJC_SPARSE2 */
 208 #else /* not PRECOMPUTE_SELECTORS */
 209   return array->
 210     indices[index/INDEX_CAPACITY]->
 211       buckets[(index/BUCKET_SIZE)%INDEX_SIZE]->
 212         elems[index%BUCKET_SIZE];
 213 #endif /* not PRECOMPUTE_SELECTORS */
 214 }
 215
 216 static inline void* sarray_get_safe(struct sarray* array, sidx index)
 217 {
 218   if(soffset_decode(index) < array->capacity)
 219     return sarray_get(array, index);
 220   else
 221     return (array->empty_bucket->elems[0]);
 222 }
 223
 224 #endif /* __sarray_INCLUDE_GNU */