Commit | Line | Data |
---|---|---|
9bf86ebb PR |
1 | /* Sparse Arrays for Objective C dispatch tables |
2 | Copyright (C) 1993 Free Software Foundation, Inc. | |
3 | ||
4 | Author: Kresten Krab Thorup | |
5 | ||
6 | This file is part of GNU CC. | |
7 | ||
8 | GNU CC is free software; you can redistribute it and/or modify | |
9 | it under the terms of the GNU General Public License as published by | |
10 | the Free Software Foundation; either version 2, or (at your option) | |
11 | any later version. | |
12 | ||
13 | GNU CC is distributed in the hope that it will be useful, | |
14 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
16 | GNU General Public License for more details. | |
17 | ||
18 | You should have received a copy of the GNU General Public License | |
19 | along with GNU CC; see the file COPYING. If not, write to | |
20 | the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ | |
21 | ||
22 | /* As a special exception, if you link this library with files | |
23 | compiled with GCC to produce an executable, this does not cause | |
24 | the resulting executable to be covered by the GNU General Public License. | |
25 | This exception does not however invalidate any other reasons why | |
26 | the executable file might be covered by the GNU General Public License. */ | |
27 | ||
28 | #ifndef __sarray_INCLUDE_GNU | |
29 | #define __sarray_INCLUDE_GNU | |
30 | ||
31 | #define OBJC_SPARSE2 /* 2-level sparse array */ | |
32 | /* #define OBJC_SPARSE3 */ /* 3-level sparse array */ | |
33 | ||
34 | #ifdef OBJC_SPARSE2 | |
35 | extern const char* __objc_sparse2_id; | |
36 | #endif | |
37 | ||
38 | #ifdef OBJC_SPARSE3 | |
39 | extern const char* __objc_sparse3_id; | |
40 | #endif | |
41 | ||
42 | #ifdef IN_GCC | |
43 | #include "gstddef.h" | |
44 | #else | |
45 | #include "stddef.h" | |
46 | #endif | |
47 | ||
48 | extern int nbuckets; /* for stats */ | |
49 | extern int nindices; | |
50 | extern int narrays; | |
51 | extern int idxsize; | |
52 | ||
53 | #include <assert.h> | |
54 | ||
55 | /* An unsigned integer of same size as a pointer */ | |
56 | #define SIZET_BITS (sizeof(size_t)*8) | |
57 | ||
58 | #if defined(sparc) || defined(OBJC_SPARSE2) | |
59 | #define PRECOMPUTE_SELECTORS | |
60 | #endif | |
61 | ||
62 | #ifdef OBJC_SPARSE3 | |
63 | ||
64 | /* Buckets are 8 words each */ | |
65 | #define BUCKET_BITS 3 | |
66 | #define BUCKET_SIZE (1<<BUCKET_BITS) | |
67 | #define BUCKET_MASK (BUCKET_SIZE-1) | |
68 | ||
69 | /* Indices are 16 words each */ | |
70 | #define INDEX_BITS 4 | |
71 | #define INDEX_SIZE (1<<INDEX_BITS) | |
72 | #define INDEX_MASK (INDEX_SIZE-1) | |
73 | ||
74 | #define INDEX_CAPACITY (BUCKET_SIZE*INDEX_SIZE) | |
75 | ||
76 | #else /* OBJC_SPARSE2 */ | |
77 | ||
78 | /* Buckets are 32 words each */ | |
79 | #define BUCKET_BITS 5 | |
80 | #define BUCKET_SIZE (1<<BUCKET_BITS) | |
81 | #define BUCKET_MASK (BUCKET_SIZE-1) | |
82 | ||
83 | #endif /* OBJC_SPARSE2 */ | |
84 | ||
85 | typedef size_t sidx; | |
86 | ||
87 | #ifdef PRECOMPUTE_SELECTORS | |
88 | ||
89 | struct soffset { | |
90 | #ifdef OBJC_SPARSE3 | |
91 | unsigned int unused : SIZET_BITS/4; | |
92 | unsigned int eoffset : SIZET_BITS/4; | |
93 | unsigned int boffset : SIZET_BITS/4; | |
94 | unsigned int ioffset : SIZET_BITS/4; | |
95 | #else /* OBJC_SPARSE2 */ | |
96 | #ifdef sparc | |
97 | unsigned int boffset : (SIZET_BITS - 2) - BUCKET_BITS; | |
98 | unsigned int eoffset : BUCKET_BITS; | |
99 | unsigned int unused : 2; | |
100 | #else | |
101 | unsigned int boffset : SIZET_BITS/2; | |
102 | unsigned int eoffset : SIZET_BITS/2; | |
103 | #endif | |
104 | #endif /* OBJC_SPARSE2 */ | |
105 | }; | |
106 | ||
107 | union sofftype { | |
108 | struct soffset off; | |
109 | sidx idx; | |
110 | }; | |
111 | ||
112 | #endif /* not PRECOMPUTE_SELECTORS */ | |
113 | ||
114 | void * __objc_xrealloc (void *optr, size_t size); | |
115 | void * __objc_xmalloc (size_t size); | |
116 | ||
117 | struct sbucket { | |
118 | void* elems[BUCKET_SIZE]; /* elements stored in array */ | |
119 | short version; /* used for copy-on-write */ | |
120 | }; | |
121 | ||
122 | #ifdef OBJC_SPARSE3 | |
123 | ||
124 | struct sindex { | |
125 | struct sbucket* buckets[INDEX_SIZE]; | |
126 | short version; | |
127 | }; | |
128 | ||
129 | #endif /* OBJC_SPARSE3 */ | |
130 | ||
131 | struct sarray { | |
132 | #ifdef OBJC_SPARSE3 | |
133 | struct sindex** indices; | |
134 | struct sindex* empty_index; | |
135 | #else /* OBJC_SPARSE2 */ | |
136 | struct sbucket** buckets; | |
137 | #endif /* OBJC_SPARSE2 */ | |
138 | struct sbucket* empty_bucket; | |
139 | short version; | |
140 | short ref_count; | |
141 | struct sarray* is_copy_of; | |
142 | int capacity; | |
143 | }; | |
144 | ||
145 | struct sarray* sarray_new(int, void* default_element); | |
146 | void sarray_free(struct sarray*); | |
147 | struct sarray* sarray_lazy_copy(struct sarray*); | |
148 | struct sarray* sarray_hard_copy(struct sarray*); /* ... like the name? */ | |
149 | void sarray_realloc(struct sarray*, int new_size); | |
150 | void sarray_at_put(struct sarray*, sidx index, void* elem); | |
151 | void sarray_at_put_safe(struct sarray*, sidx index, void* elem); | |
152 | \f | |
153 | ||
154 | #ifdef PRECOMPUTE_SELECTORS | |
155 | /* Transform soffset values to ints and vica verca */ | |
156 | static inline unsigned int | |
157 | soffset_decode(sidx index) | |
158 | { | |
159 | union sofftype x; | |
160 | x.idx = index; | |
161 | #ifdef OBJC_SPARSE3 | |
162 | return x.off.eoffset | |
163 | + (x.off.boffset*BUCKET_SIZE) | |
164 | + (x.off.ioffset*INDEX_CAPACITY); | |
165 | #else /* OBJC_SPARSE2 */ | |
166 | return x.off.eoffset + (x.off.boffset*BUCKET_SIZE); | |
167 | #endif /* OBJC_SPARSE2 */ | |
168 | } | |
169 | ||
170 | static inline sidx | |
171 | soffset_encode(size_t offset) | |
172 | { | |
173 | union sofftype x; | |
174 | x.off.eoffset = offset%BUCKET_SIZE; | |
175 | #ifdef OBJC_SPARSE3 | |
176 | x.off.boffset = (offset/BUCKET_SIZE)%INDEX_SIZE; | |
177 | x.off.ioffset = offset/INDEX_CAPACITY; | |
178 | #else /* OBJC_SPARSE2 */ | |
179 | x.off.boffset = offset/BUCKET_SIZE; | |
180 | #endif | |
181 | return (sidx)x.idx; | |
182 | } | |
183 | ||
184 | #else /* not PRECOMPUTE_SELECTORS */ | |
185 | ||
186 | static inline size_t | |
187 | soffset_decode(sidx index) | |
188 | { | |
189 | return index; | |
190 | } | |
191 | ||
192 | static inline sidx | |
193 | soffset_encode(size_t offset) | |
194 | { | |
195 | return offset; | |
196 | } | |
197 | #endif /* not PRECOMPUTE_SELECTORS */ | |
198 | ||
199 | /* Get element from the Sparse array `array' at offset `index' */ | |
200 | ||
201 | static inline void* sarray_get(struct sarray* array, sidx index) | |
202 | { | |
203 | #ifdef PRECOMPUTE_SELECTORS | |
204 | union sofftype x; | |
205 | x.idx = index; | |
206 | #ifdef OBJC_SPARSE3 | |
207 | return | |
208 | array-> | |
209 | indices[x.off.ioffset]-> | |
210 | buckets[x.off.boffset]-> | |
211 | elems[x.off.eoffset]; | |
212 | #else /* OBJC_SPARSE2 */ | |
213 | return array->buckets[x.off.boffset]->elems[x.off.eoffset]; | |
214 | #endif /* OBJC_SPARSE2 */ | |
215 | #else /* not PRECOMPUTE_SELECTORS */ | |
216 | #ifdef OBJC_SPARSE3 | |
217 | return array-> | |
218 | indices[index/INDEX_CAPACITY]-> | |
219 | buckets[(index/BUCKET_SIZE)%INDEX_SIZE]-> | |
220 | elems[index%BUCKET_SIZE]; | |
221 | #else /* OBJC_SPARSE2 */ | |
222 | return array->buckets[index/BUCKET_SIZE]->elems[index%BUCKET_SIZE]; | |
223 | #endif /* not OBJC_SPARSE3 */ | |
224 | #endif /* not PRECOMPUTE_SELECTORS */ | |
225 | } | |
226 | ||
227 | static inline void* sarray_get_safe(struct sarray* array, sidx index) | |
228 | { | |
229 | if(soffset_decode(index) < array->capacity) | |
230 | return sarray_get(array, index); | |
231 | else | |
232 | return (array->empty_bucket->elems[0]); | |
233 | } | |
234 | ||
235 | #endif /* __sarray_INCLUDE_GNU */ |