1/* Sparse Arrays for Objective C dispatch tables 2 Copyright (C) 1993-2022 Free Software Foundation, Inc. 3 Contributed by Kresten Krab Thorup. 4 5This file is part of GCC. 6 7GCC 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 3, or (at your option) 10any later version. 11 12GCC 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 17Under Section 7 of GPL version 3, you are granted additional 18permissions described in the GCC Runtime Library Exception, version 193.1, as published by the Free Software Foundation. 20 21You should have received a copy of the GNU General Public License and 22a copy of the GCC Runtime Library Exception along with this program; 23see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24<http://www.gnu.org/licenses/>. */ 25 26#ifndef __sarray_INCLUDE_GNU 27#define __sarray_INCLUDE_GNU 28 29#define OBJC_SPARSE2 /* 2-level sparse array. */ 30/* #define OBJC_SPARSE3 */ /* 3-level sparse array. */ 31 32#ifdef OBJC_SPARSE2 33extern const char* __objc_sparse2_id; 34#endif 35 36#ifdef OBJC_SPARSE3 37extern const char* __objc_sparse3_id; 38#endif 39 40#include <stddef.h> 41 42extern int nbuckets; /* for stats */ 43extern int nindices; 44extern int narrays; 45extern int idxsize; 46 47/* An unsigned integer of same size as a pointer. */ 48#define SIZET_BITS (sizeof (size_t) * 8) 49 50#if defined (__sparc__) || defined (OBJC_SPARSE2) 51#define PRECOMPUTE_SELECTORS 52#endif 53 54#ifdef OBJC_SPARSE3 55 56/* Buckets are 8 words each. */ 57#define BUCKET_BITS 3 58#define BUCKET_SIZE (1 << BUCKET_BITS) 59#define BUCKET_MASK (BUCKET_SIZE - 1) 60 61/* Indices are 16 words each. */ 62#define INDEX_BITS 4 63#define INDEX_SIZE (1 << INDEX_BITS) 64#define INDEX_MASK (INDEX_SIZE - 1) 65 66#define INDEX_CAPACITY (BUCKET_SIZE * INDEX_SIZE) 67 68#else /* OBJC_SPARSE2 */ 69 70/* Buckets are 32 words each. */ 71#define BUCKET_BITS 5 72#define BUCKET_SIZE (1 << BUCKET_BITS) 73#define BUCKET_MASK (BUCKET_SIZE - 1) 74 75#endif /* OBJC_SPARSE2 */ 76 77typedef size_t sidx; 78 79#ifdef PRECOMPUTE_SELECTORS 80 81struct soffset 82{ 83#ifdef OBJC_SPARSE3 84 unsigned int unused : SIZET_BITS / 4; 85 unsigned int eoffset : SIZET_BITS / 4; 86 unsigned int boffset : SIZET_BITS / 4; 87 unsigned int ioffset : SIZET_BITS / 4; 88#else /* OBJC_SPARSE2 */ 89#ifdef __sparc__ 90 unsigned long boffset : (SIZET_BITS - 2) - BUCKET_BITS; 91 unsigned int eoffset : BUCKET_BITS; 92 unsigned int unused : 2; 93#else 94 unsigned int boffset : SIZET_BITS / 2; 95 unsigned int eoffset : SIZET_BITS / 2; 96#endif 97#endif /* OBJC_SPARSE2 */ 98}; 99 100union sofftype 101{ 102 struct soffset off; 103 sidx idx; 104}; 105 106#endif /* not PRECOMPUTE_SELECTORS */ 107 108union sversion 109{ 110 int version; 111 void *next_free; 112}; 113 114struct sbucket 115{ 116 /* Elements stored in array. */ 117 void* elems[BUCKET_SIZE]; 118 119 /* Used for copy-on-write. */ 120 union sversion version; 121}; 122 123#ifdef OBJC_SPARSE3 124 125struct sindex 126{ 127 struct sbucket* buckets[INDEX_SIZE]; 128 129 /* Used for copy-on-write. */ 130 union sversion version; 131}; 132 133#endif /* OBJC_SPARSE3 */ 134 135struct sarray 136{ 137#ifdef OBJC_SPARSE3 138 struct sindex** indices; 139 struct sindex* empty_index; 140#else /* OBJC_SPARSE2 */ 141 struct sbucket** buckets; 142#endif /* OBJC_SPARSE2 */ 143 struct sbucket* empty_bucket; 144 145 /* Used for copy-on-write. */ 146 union sversion version; 147 148 short ref_count; 149 struct sarray* is_copy_of; 150 size_t capacity; 151}; 152 153struct sarray* sarray_new (int, void* default_element); 154void sarray_free (struct sarray*); 155struct sarray* sarray_lazy_copy (struct sarray*); 156void sarray_realloc (struct sarray*, int new_size); 157void sarray_at_put (struct sarray*, sidx indx, void* elem); 158void sarray_at_put_safe (struct sarray*, sidx indx, void* elem); 159 160struct sarray* sarray_hard_copy (struct sarray*); /* ... like the name ? */ 161void sarray_remove_garbage (void); 162 163 164#ifdef PRECOMPUTE_SELECTORS 165/* Transform soffset values to ints and vice versa. */ 166static inline unsigned int 167soffset_decode (sidx indx) 168{ 169 union sofftype x; 170 x.idx = indx; 171#ifdef OBJC_SPARSE3 172 return x.off.eoffset 173 + (x.off.boffset * BUCKET_SIZE) 174 + (x.off.ioffset * INDEX_CAPACITY); 175#else /* OBJC_SPARSE2 */ 176 return x.off.eoffset + (x.off.boffset * BUCKET_SIZE); 177#endif /* OBJC_SPARSE2 */ 178} 179 180static inline sidx 181soffset_encode (size_t offset) 182{ 183 union sofftype x; 184 x.off.eoffset = offset % BUCKET_SIZE; 185#ifdef OBJC_SPARSE3 186 x.off.boffset = (offset / BUCKET_SIZE) % INDEX_SIZE; 187 x.off.ioffset = offset / INDEX_CAPACITY; 188#else /* OBJC_SPARSE2 */ 189 x.off.boffset = offset / BUCKET_SIZE; 190#endif 191 return (sidx)x.idx; 192} 193 194#else /* not PRECOMPUTE_SELECTORS */ 195 196static inline size_t 197soffset_decode (sidx indx) 198{ 199 return indx; 200} 201 202static inline sidx 203soffset_encode (size_t offset) 204{ 205 return offset; 206} 207#endif /* not PRECOMPUTE_SELECTORS */ 208 209/* Get element from the Sparse array `array' at offset `indx'. */ 210static inline void* sarray_get (struct sarray* array, sidx indx) 211{ 212#ifdef PRECOMPUTE_SELECTORS 213 union sofftype x; 214 x.idx = indx; 215#ifdef OBJC_SPARSE3 216 return array-> 217 indices[x.off.ioffset]-> 218 buckets[x.off.boffset]-> 219 elems[x.off.eoffset]; 220#else /* OBJC_SPARSE2 */ 221 return array->buckets[x.off.boffset]->elems[x.off.eoffset]; 222#endif /* OBJC_SPARSE2 */ 223#else /* not PRECOMPUTE_SELECTORS */ 224#ifdef OBJC_SPARSE3 225 return array-> 226 indices[indx / INDEX_CAPACITY]-> 227 buckets[(indx / BUCKET_SIZE) % INDEX_SIZE]-> 228 elems[indx % BUCKET_SIZE]; 229#else /* OBJC_SPARSE2 */ 230 return array->buckets[indx / BUCKET_SIZE]->elems[indx % BUCKET_SIZE]; 231#endif /* not OBJC_SPARSE3 */ 232#endif /* not PRECOMPUTE_SELECTORS */ 233} 234 235static inline void* sarray_get_safe (struct sarray* array, sidx indx) 236{ 237 if (soffset_decode (indx) < array->capacity) 238 return sarray_get (array, indx); 239 else 240 return (array->empty_bucket->elems[0]); 241} 242 243#endif /* __sarray_INCLUDE_GNU */ 244