]>
Commit | Line | Data |
---|---|---|
54d533d3 | 1 | /* Sparse Arrays for Objective C dispatch tables |
f1717362 | 2 | Copyright (C) 1993-2016 Free Software Foundation, Inc. |
54d533d3 | 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 | ||
ec7829f5 | 29 | #define OBJC_SPARSE2 /* 2-level sparse array. */ |
30 | /* #define OBJC_SPARSE3 */ /* 3-level sparse array. */ | |
54d533d3 | 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 | ||
54d533d3 | 42 | extern int nbuckets; /* for stats */ |
43 | extern int nindices; | |
44 | extern int narrays; | |
45 | extern int idxsize; | |
46 | ||
ec7829f5 | 47 | /* An unsigned integer of same size as a pointer. */ |
48 | #define SIZET_BITS (sizeof (size_t) * 8) | |
54d533d3 | 49 | |
ec7829f5 | 50 | #if defined (__sparc__) || defined (OBJC_SPARSE2) |
54d533d3 | 51 | #define PRECOMPUTE_SELECTORS |
52 | #endif | |
53 | ||
54 | #ifdef OBJC_SPARSE3 | |
55 | ||
ec7829f5 | 56 | /* Buckets are 8 words each. */ |
54d533d3 | 57 | #define BUCKET_BITS 3 |
ec7829f5 | 58 | #define BUCKET_SIZE (1 << BUCKET_BITS) |
59 | #define BUCKET_MASK (BUCKET_SIZE - 1) | |
54d533d3 | 60 | |
ec7829f5 | 61 | /* Indices are 16 words each. */ |
54d533d3 | 62 | #define INDEX_BITS 4 |
ec7829f5 | 63 | #define INDEX_SIZE (1 << INDEX_BITS) |
64 | #define INDEX_MASK (INDEX_SIZE - 1) | |
54d533d3 | 65 | |
ec7829f5 | 66 | #define INDEX_CAPACITY (BUCKET_SIZE * INDEX_SIZE) |
54d533d3 | 67 | |
68 | #else /* OBJC_SPARSE2 */ | |
69 | ||
ec7829f5 | 70 | /* Buckets are 32 words each. */ |
54d533d3 | 71 | #define BUCKET_BITS 5 |
ec7829f5 | 72 | #define BUCKET_SIZE (1 << BUCKET_BITS) |
73 | #define BUCKET_MASK (BUCKET_SIZE - 1) | |
54d533d3 | 74 | |
75 | #endif /* OBJC_SPARSE2 */ | |
76 | ||
77 | typedef size_t sidx; | |
78 | ||
79 | #ifdef PRECOMPUTE_SELECTORS | |
80 | ||
ec7829f5 | 81 | struct soffset |
82 | { | |
54d533d3 | 83 | #ifdef OBJC_SPARSE3 |
ec7829f5 | 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; | |
54d533d3 | 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 | |
ec7829f5 | 94 | unsigned int boffset : SIZET_BITS / 2; |
95 | unsigned int eoffset : SIZET_BITS / 2; | |
54d533d3 | 96 | #endif |
97 | #endif /* OBJC_SPARSE2 */ | |
98 | }; | |
99 | ||
ec7829f5 | 100 | union sofftype |
101 | { | |
54d533d3 | 102 | struct soffset off; |
103 | sidx idx; | |
104 | }; | |
105 | ||
106 | #endif /* not PRECOMPUTE_SELECTORS */ | |
107 | ||
ec7829f5 | 108 | union sversion |
109 | { | |
54d533d3 | 110 | int version; |
111 | void *next_free; | |
112 | }; | |
113 | ||
ec7829f5 | 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; | |
54d533d3 | 121 | }; |
122 | ||
123 | #ifdef OBJC_SPARSE3 | |
124 | ||
ec7829f5 | 125 | struct sindex |
126 | { | |
54d533d3 | 127 | struct sbucket* buckets[INDEX_SIZE]; |
ec7829f5 | 128 | |
129 | /* Used for copy-on-write. */ | |
130 | union sversion version; | |
54d533d3 | 131 | }; |
132 | ||
133 | #endif /* OBJC_SPARSE3 */ | |
134 | ||
ec7829f5 | 135 | struct sarray |
136 | { | |
54d533d3 | 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; | |
ec7829f5 | 144 | |
145 | /* Used for copy-on-write. */ | |
146 | union sversion version; | |
147 | ||
54d533d3 | 148 | short ref_count; |
149 | struct sarray* is_copy_of; | |
150 | size_t capacity; | |
151 | }; | |
152 | ||
ec7829f5 | 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); | |
54d533d3 | 159 | |
ec7829f5 | 160 | struct sarray* sarray_hard_copy (struct sarray*); /* ... like the name ? */ |
161 | void sarray_remove_garbage (void); | |
54d533d3 | 162 | \f |
163 | ||
164 | #ifdef PRECOMPUTE_SELECTORS | |
ec7829f5 | 165 | /* Transform soffset values to ints and vice versa. */ |
54d533d3 | 166 | static inline unsigned int |
ec7829f5 | 167 | soffset_decode (sidx indx) |
54d533d3 | 168 | { |
169 | union sofftype x; | |
170 | x.idx = indx; | |
171 | #ifdef OBJC_SPARSE3 | |
172 | return x.off.eoffset | |
ec7829f5 | 173 | + (x.off.boffset * BUCKET_SIZE) |
174 | + (x.off.ioffset * INDEX_CAPACITY); | |
54d533d3 | 175 | #else /* OBJC_SPARSE2 */ |
ec7829f5 | 176 | return x.off.eoffset + (x.off.boffset * BUCKET_SIZE); |
54d533d3 | 177 | #endif /* OBJC_SPARSE2 */ |
178 | } | |
179 | ||
180 | static inline sidx | |
ec7829f5 | 181 | soffset_encode (size_t offset) |
54d533d3 | 182 | { |
183 | union sofftype x; | |
ec7829f5 | 184 | x.off.eoffset = offset % BUCKET_SIZE; |
54d533d3 | 185 | #ifdef OBJC_SPARSE3 |
ec7829f5 | 186 | x.off.boffset = (offset / BUCKET_SIZE) % INDEX_SIZE; |
187 | x.off.ioffset = offset / INDEX_CAPACITY; | |
54d533d3 | 188 | #else /* OBJC_SPARSE2 */ |
ec7829f5 | 189 | x.off.boffset = offset / BUCKET_SIZE; |
54d533d3 | 190 | #endif |
191 | return (sidx)x.idx; | |
192 | } | |
193 | ||
194 | #else /* not PRECOMPUTE_SELECTORS */ | |
195 | ||
196 | static inline size_t | |
ec7829f5 | 197 | soffset_decode (sidx indx) |
54d533d3 | 198 | { |
199 | return indx; | |
200 | } | |
201 | ||
202 | static inline sidx | |
ec7829f5 | 203 | soffset_encode (size_t offset) |
54d533d3 | 204 | { |
205 | return offset; | |
206 | } | |
207 | #endif /* not PRECOMPUTE_SELECTORS */ | |
208 | ||
ec7829f5 | 209 | /* Get element from the Sparse array `array' at offset `indx'. */ |
210 | static inline void* sarray_get (struct sarray* array, sidx indx) | |
54d533d3 | 211 | { |
212 | #ifdef PRECOMPUTE_SELECTORS | |
213 | union sofftype x; | |
214 | x.idx = indx; | |
215 | #ifdef OBJC_SPARSE3 | |
ec7829f5 | 216 | return array-> |
217 | indices[x.off.ioffset]-> | |
218 | buckets[x.off.boffset]-> | |
219 | elems[x.off.eoffset]; | |
54d533d3 | 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-> | |
ec7829f5 | 226 | indices[indx / INDEX_CAPACITY]-> |
227 | buckets[(indx / BUCKET_SIZE) % INDEX_SIZE]-> | |
228 | elems[indx % BUCKET_SIZE]; | |
54d533d3 | 229 | #else /* OBJC_SPARSE2 */ |
ec7829f5 | 230 | return array->buckets[indx / BUCKET_SIZE]->elems[indx % BUCKET_SIZE]; |
54d533d3 | 231 | #endif /* not OBJC_SPARSE3 */ |
232 | #endif /* not PRECOMPUTE_SELECTORS */ | |
233 | } | |
234 | ||
ec7829f5 | 235 | static inline void* sarray_get_safe (struct sarray* array, sidx indx) |
54d533d3 | 236 | { |
ec7829f5 | 237 | if (soffset_decode (indx) < array->capacity) |
238 | return sarray_get (array, indx); | |
54d533d3 | 239 | else |
240 | return (array->empty_bucket->elems[0]); | |
241 | } | |
242 | ||
54d533d3 | 243 | #endif /* __sarray_INCLUDE_GNU */ |