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