gcc/objc/sarray.h

   1 /* Sparse Arrays for Objective C dispatch tables
   2    Copyright (C) 1993, 1995 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, 59 Temple Place - Suite 330,
  21 Boston, MA 02111-1307, USA.  */
  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
  43 #include <stddef.h>
  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
  55 #if defined(__sparc__) || defined(OBJC_SPARSE2)
  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 */
  93 #ifdef __sparc__
  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;
 139   size_t capacity;
 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 \f
 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 */