|
111
|
1 /* Sparse Arrays for Objective C dispatch tables
|
|
145
|
2 Copyright (C) 1993-2020 Free Software Foundation, Inc.
|
|
111
|
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 #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
|
|
|
33 extern const char* __objc_sparse2_id;
|
|
|
34 #endif
|
|
|
35
|
|
|
36 #ifdef OBJC_SPARSE3
|
|
|
37 extern const char* __objc_sparse3_id;
|
|
|
38 #endif
|
|
|
39
|
|
|
40 #include <stddef.h>
|
|
|
41
|
|
|
42 extern int nbuckets; /* for stats */
|
|
|
43 extern int nindices;
|
|
|
44 extern int narrays;
|
|
|
45 extern 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
|
|
|
77 typedef size_t sidx;
|
|
|
78
|
|
|
79 #ifdef PRECOMPUTE_SELECTORS
|
|
|
80
|
|
|
81 struct 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
|
|
|
100 union sofftype
|
|
|
101 {
|
|
|
102 struct soffset off;
|
|
|
103 sidx idx;
|
|
|
104 };
|
|
|
105
|
|
|
106 #endif /* not PRECOMPUTE_SELECTORS */
|
|
|
107
|
|
|
108 union sversion
|
|
|
109 {
|
|
|
110 int version;
|
|
|
111 void *next_free;
|
|
|
112 };
|
|
|
113
|
|
|
114 struct 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
|
|
|
125 struct 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
|
|
|
135 struct 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
|
|
|
153 struct sarray* sarray_new (int, void* default_element);
|
|
|
154 void sarray_free (struct sarray*);
|
|
|
155 struct sarray* sarray_lazy_copy (struct sarray*);
|
|
|
156 void sarray_realloc (struct sarray*, int new_size);
|
|
|
157 void sarray_at_put (struct sarray*, sidx indx, void* elem);
|
|
|
158 void sarray_at_put_safe (struct sarray*, sidx indx, void* elem);
|
|
|
159
|
|
|
160 struct sarray* sarray_hard_copy (struct sarray*); /* ... like the name ? */
|
|
|
161 void sarray_remove_garbage (void);
|
|
|
162
|
|
|
163
|
|
|
164 #ifdef PRECOMPUTE_SELECTORS
|
|
|
165 /* Transform soffset values to ints and vice versa. */
|
|
|
166 static inline unsigned int
|
|
|
167 soffset_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
|
|
|
180 static inline sidx
|
|
|
181 soffset_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
|
|
|
196 static inline size_t
|
|
|
197 soffset_decode (sidx indx)
|
|
|
198 {
|
|
|
199 return indx;
|
|
|
200 }
|
|
|
201
|
|
|
202 static inline sidx
|
|
|
203 soffset_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'. */
|
|
|
210 static 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
|
|
|
235 static 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 */
|
