libobjc/objc/deprecated/sarray.h

   1 /* Sparse Arrays for Objective C dispatch tables
   2    Copyright (C) 1993, 1995, 1996, 2004, 2009 Free Software Foundation, Inc.
   3    Contributed by Kresten Krab Thorup.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 Under Section 7 of GPL version 3, you are granted additional
  18 permissions described in the GCC Runtime Library Exception, version
  19 3.1, as published by the Free Software Foundation.
  20
  21 You should have received a copy of the GNU General Public License and
  22 a copy of the GCC Runtime Library Exception along with this program;
  23 see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  24 <http://www.gnu.org/licenses/>.  */
  25
  26
  27 #ifndef __sarray_INCLUDE_GNU
  28 #define __sarray_INCLUDE_GNU
  29
  30 #define OBJC_SPARSE2            /* 2-level sparse array */
  31 /* #define OBJC_SPARSE3 */      /* 3-level sparse array */
  32
  33 #ifdef OBJC_SPARSE2
  34 extern const char* __objc_sparse2_id;
  35 #endif
  36
  37 #ifdef OBJC_SPARSE3
  38 extern const char* __objc_sparse3_id;
  39 #endif
  40
  41 #include <stddef.h>
  42
  43 #ifdef __cplusplus
  44 extern "C" {
  45 #endif /* __cplusplus */
  46
  47 extern int nbuckets;            /* for stats */
  48 extern int nindices;
  49 extern int narrays;
  50 extern int idxsize;
  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 long 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 union sversion {
 112   int   version;
 113   void *next_free;
 114 };
 115
 116 struct sbucket {
 117   void* elems[BUCKET_SIZE];     /* elements stored in array */
 118   union sversion        version;                /* used for copy-on-write */
 119 };
 120
 121 #ifdef OBJC_SPARSE3
 122
 123 struct sindex {
 124   struct sbucket* buckets[INDEX_SIZE];
 125   union sversion        version;                /* used for copy-on-write */
 126 };
 127
 128 #endif /* OBJC_SPARSE3 */
 129
 130 struct sarray {
 131 #ifdef OBJC_SPARSE3
 132   struct sindex** indices;
 133   struct sindex* empty_index;
 134 #else /* OBJC_SPARSE2 */
 135   struct sbucket** buckets;
 136 #endif  /* OBJC_SPARSE2 */
 137   struct sbucket* empty_bucket;
 138   union sversion        version;                /* used for copy-on-write */
 139   short ref_count;
 140   struct sarray* is_copy_of;
 141   size_t capacity;
 142 };
 143
 144 struct sarray* sarray_new(int, void* default_element);
 145 void sarray_free(struct sarray*);
 146 struct sarray* sarray_lazy_copy(struct sarray*);
 147 void sarray_realloc(struct sarray*, int new_size);
 148 void sarray_at_put(struct sarray*, sidx indx, void* elem);
 149 void sarray_at_put_safe(struct sarray*, sidx indx, void* elem);
 150
 151 struct sarray* sarray_hard_copy(struct sarray*); /* ... like the name? */
 152 void sarray_remove_garbage(void);
 153 \f
 154
 155 #ifdef PRECOMPUTE_SELECTORS
 156 /* Transform soffset values to ints and vica verca */
 157 static inline unsigned int
 158 soffset_decode(sidx indx)
 159 {
 160   union sofftype x;
 161   x.idx = indx;
 162 #ifdef OBJC_SPARSE3
 163   return x.off.eoffset
 164     + (x.off.boffset*BUCKET_SIZE)
 165       + (x.off.ioffset*INDEX_CAPACITY);
 166 #else /* OBJC_SPARSE2 */
 167   return x.off.eoffset + (x.off.boffset*BUCKET_SIZE);
 168 #endif /* OBJC_SPARSE2 */
 169 }
 170
 171 static inline sidx
 172 soffset_encode(size_t offset)
 173 {
 174   union sofftype x;
 175   x.off.eoffset = offset%BUCKET_SIZE;
 176 #ifdef OBJC_SPARSE3
 177   x.off.boffset = (offset/BUCKET_SIZE)%INDEX_SIZE;
 178   x.off.ioffset = offset/INDEX_CAPACITY;
 179 #else /* OBJC_SPARSE2 */
 180   x.off.boffset = offset/BUCKET_SIZE;
 181 #endif
 182   return (sidx)x.idx;
 183 }
 184
 185 #else /* not PRECOMPUTE_SELECTORS */
 186
 187 static inline size_t
 188 soffset_decode(sidx indx)
 189 {
 190   return indx;
 191 }
 192
 193 static inline sidx
 194 soffset_encode(size_t offset)
 195 {
 196   return offset;
 197 }
 198 #endif /* not PRECOMPUTE_SELECTORS */
 199
 200 /* Get element from the Sparse array `array' at offset `indx' */
 201
 202 static inline void* sarray_get(struct sarray* array, sidx indx)
 203 {
 204 #ifdef PRECOMPUTE_SELECTORS
 205   union sofftype x;
 206   x.idx = indx;
 207 #ifdef OBJC_SPARSE3
 208   return
 209     array->
 210       indices[x.off.ioffset]->
 211         buckets[x.off.boffset]->
 212           elems[x.off.eoffset];
 213 #else /* OBJC_SPARSE2 */
 214   return array->buckets[x.off.boffset]->elems[x.off.eoffset];
 215 #endif /* OBJC_SPARSE2 */
 216 #else /* not PRECOMPUTE_SELECTORS */
 217 #ifdef OBJC_SPARSE3
 218   return array->
 219     indices[indx/INDEX_CAPACITY]->
 220       buckets[(indx/BUCKET_SIZE)%INDEX_SIZE]->
 221         elems[indx%BUCKET_SIZE];
 222 #else /* OBJC_SPARSE2 */
 223   return array->buckets[indx/BUCKET_SIZE]->elems[indx%BUCKET_SIZE];
 224 #endif /* not OBJC_SPARSE3 */
 225 #endif /* not PRECOMPUTE_SELECTORS */
 226 }
 227
 228 static inline void* sarray_get_safe(struct sarray* array, sidx indx)
 229 {
 230   if(soffset_decode(indx) < array->capacity)
 231     return sarray_get(array, indx);
 232   else
 233     return (array->empty_bucket->elems[0]);
 234 }
 235
 236 #ifdef __cplusplus
 237 }
 238 #endif /* __cplusplus */
 239
 240 #endif /* __sarray_INCLUDE_GNU */