1 /* Sparse Arrays for Objective C dispatch tables
2 Copyright (C) 1993, 1995, 1996 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
21 /* As a special exception, if you link this library with files
22 compiled with GCC to produce an executable, this does not cause
23 the resulting executable to be covered by the GNU General Public License.
24 This exception does not however invalidate any other reasons why
25 the executable file might be covered by the GNU General Public License. */
34 int nbuckets = 0; /* !T:MUTEX */
35 int nindices = 0; /* !T:MUTEX */
36 int narrays = 0; /* !T:MUTEX */
37 int idxsize = 0; /* !T:MUTEX */
39 static void *first_free_data = NULL; /* !T:MUTEX */
41 const char* __objc_sparse2_id = "2 level sparse indices";
44 const void *memcpy (void*, const void*, size_t);
47 static void sarray_free_garbage(void *vp);
52 static struct sbucket empty_bucket_32 = {
53 { NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
54 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
55 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
56 NULL, NULL }, /* elements */
59 #elif BUCKET_SIZE == 64
60 static struct sbucket empty_bucket_64 = {
61 { NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
62 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
63 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
64 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
65 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
66 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
67 NULL, NULL, NULL, NULL }, /* elements */
70 #elif BUCKET_SIZE == 256
71 static struct sbucket empty_bucket_256 = {
72 { NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
73 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
74 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
75 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
76 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
77 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
78 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
79 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
80 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
81 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
82 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
83 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
84 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
85 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
86 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
87 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
88 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
89 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
90 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
91 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
92 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
93 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
94 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
95 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
96 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
97 NULL, NULL, NULL, NULL, NULL, NULL }, /* elements */
102 struct sarray *sarray_new (int size)
105 size_t num_indices = ((size - 1) / BUCKET_SIZE) + 1;
106 struct sbucket **new_buckets;
111 /* Allocate core array */
112 arr = (struct sarray*)OBJC_MALLOC_UNCOLLECTABLE(sizeof(struct sarray));
113 arr->version.version = 0;
115 /* Initialize members */
116 arr->capacity = num_indices * BUCKET_SIZE;
117 new_buckets = (struct sbucket **)
118 OBJC_MALLOC_UNCOLLECTABLE(sizeof(struct sbucket *) * num_indices);
121 idxsize += num_indices;
123 #if BUCKET_SIZE == 32 || BUCKET_SIZE == 64 ||BUCKET_SIZE == 256
124 # if BUCKET_SIZE == 32
125 arr->empty_bucket = &empty_bucket_32;
126 # elif BUCKET_SIZE == 64
127 arr->empty_bucket = &empty_bucket_64;
128 # elif BUCKET_SIZE == 256
129 arr->empty_bucket = &empty_bucket_256;
133 (struct sbucket *)OBJC_MALLOC_UNCOLLECTABLE(sizeof(struct sbucket));
134 arr->empty_bucket->version.version = 0;
140 arr->is_copy_of = (struct sarray*)0;
142 for (counter = 0; counter < num_indices; counter++)
143 new_buckets[counter] = arr->empty_bucket;
145 arr->buckets = new_buckets;
150 /* Reallocate the sparse array to hold `newsize' entries
151 Note: We really allocate and then free. We have to do this to ensure that
152 any concurrent readers notice the update. */
153 void sarray_realloc(struct sarray* array, int newsize)
155 size_t old_max_index = (array->capacity-1)/BUCKET_SIZE;
156 size_t new_max_index = ((newsize-1)/BUCKET_SIZE);
157 size_t rounded_size = (new_max_index+1)*BUCKET_SIZE;
159 struct sbucket ** new_buckets;
160 struct sbucket ** old_buckets;
166 /* The size is the same, just ignore the request */
167 if(rounded_size <= array->capacity)
170 assert(array->ref_count == 1); /* stop if lazy copied... */
172 /* We are asked to extend the array -- allocate new bucket table, */
173 /* and insert empty_bucket in newly allocated places. */
174 if(rounded_size > array->capacity) {
176 rounded_size = (new_max_index+1)*BUCKET_SIZE;
178 /* update capacity */
179 array->capacity = rounded_size;
181 old_buckets = array->buckets;
182 new_buckets = (struct sbucket**)
183 OBJC_MALLOC_UNCOLLECTABLE((new_max_index + 1) * sizeof(struct sbucket*));
185 /* copy buckets below old_max_index (they are still valid) */
186 for(counter = 0; counter <= old_max_index; counter++ )
187 new_buckets[counter] = old_buckets[counter];
189 /* reset entries above old_max_index to empty_bucket */
190 for(counter = old_max_index+1; counter <= new_max_index; counter++)
191 new_buckets[counter] = array->empty_bucket;
193 array->buckets = new_buckets;
194 sarray_free_garbage(old_buckets);
196 idxsize += (new_max_index-old_max_index);
201 /* Free a sparse array allocated with sarray_new */
202 void sarray_free(struct sarray *array)
204 size_t old_max_bucket_index;
205 struct sbucket **old_buckets;
206 register int counter;
211 old_max_bucket_index = (array->capacity - 1) / BUCKET_SIZE;
213 assert(array->ref_count != 0); /* Freed multiple times!!! */
215 (array->ref_count)--;
216 if(array->ref_count > 0) /* There exists copies of me */
219 old_buckets = array->buckets;
221 /* Free all entries that do not point to empty_bucket */
222 for(counter = 0; counter <= old_max_bucket_index; counter++ ) {
223 register struct sbucket *bkt = array->buckets[counter];
225 if ((bkt == NULL) || (bkt == array->empty_bucket))
228 if (bkt->version.version == array->version.version) {
230 only if bucket belongs to this array
231 (only written records in lazy copies)
233 sarray_free_garbage(bkt); bkt = NULL;
238 /* free empty_bucket */
239 if(array->empty_bucket->version.version == array->version.version) {
240 sarray_free_garbage(array->empty_bucket);
243 idxsize -= (old_max_bucket_index + 1);
246 /* free bucket table */
247 sarray_free_garbage(array->buckets);
249 /* release lazy copy */
250 if (array->is_copy_of) {
251 assert(array->is_copy_of != array);
252 assert(array->is_copy_of->version.version < array->version.version);
254 sarray_free(array->is_copy_of);
255 array->is_copy_of = NULL;
259 sarray_free_garbage(array);
262 /* This is a lazy copy. Only the core of the structure is actually */
265 struct sarray *sarray_lazy_copy(struct sarray* oarr)
268 size_t num_indices = ((oarr->capacity-1)/BUCKET_SIZE)+1;
269 struct sbucket ** new_buckets;
271 /* Allocate core array */
272 arr = (struct sarray *)OBJC_MALLOC_UNCOLLECTABLE(sizeof(struct sarray));
274 arr->version.version = oarr->version.version + 1;
275 arr->empty_bucket = oarr->empty_bucket;
277 oarr->ref_count += 1;
278 arr->is_copy_of = oarr;
279 arr->capacity = oarr->capacity;
281 /* Copy bucket table */
282 new_buckets = (struct sbucket**)
283 OBJC_MALLOC_UNCOLLECTABLE(sizeof(struct sbucket *) * num_indices);
284 memcpy(new_buckets, oarr->buckets, sizeof(struct sbucket*)*num_indices);
285 arr->buckets = new_buckets;
286 idxsize += num_indices;
292 void sarray_at_put(struct sarray *array, sidx index, void *element) {
293 return sarray_at_put_safe(array, index, element);
297 sarray_at_put_safe(struct sarray *array, sidx index, void *element)
299 register unsigned int idx;
300 struct sbucket** the_bucket;
301 struct sbucket* new_bucket;
304 boffset = index / BUCKET_SIZE;
305 eoffset = index % BUCKET_SIZE;
314 if (idx >= array->capacity)
315 sarray_realloc(array, (idx + 1));
317 assert(idx < array->capacity); /* Range check */
319 the_bucket = &(array->buckets[boffset]);
321 if ((*the_bucket)->elems[eoffset] == element)
322 return; /* great! we just avoided a lazy copy */
324 /* next, perform lazy allocation/copy of the bucket if needed */
326 if ((*the_bucket) == array->empty_bucket) {
328 /* The bucket was previously empty (or something like that), */
329 /* allocate a new. This is the effect of `lazy' allocation */
331 (struct sbucket*)OBJC_MALLOC_UNCOLLECTABLE(sizeof(struct sbucket));
333 memcpy((void *) new_bucket, (const void*)array->empty_bucket,
334 sizeof(struct sbucket));
335 new_bucket->version.version = array->version.version;
336 *the_bucket = new_bucket; /* Prepared for install. */
340 } else if ((*the_bucket)->version.version != array->version.version) {
342 /* Perform lazy copy. */
343 struct sbucket* old_bucket = *the_bucket;
346 (struct sbucket*)OBJC_MALLOC_UNCOLLECTABLE(sizeof(struct sbucket));
348 memcpy( new_bucket, old_bucket, sizeof(struct sbucket));
349 new_bucket->version.version = array->version.version;
350 *the_bucket = new_bucket; /* Prepared for install. */
355 (*the_bucket)->elems[eoffset] = element;
358 /* This function removes any structures left over from free operations
359 that were not safe in a multi-threaded environment. */
360 void sarray_remove_garbage(void) {
366 vp = first_free_data;
367 first_free_data = NULL;
382 /* Free a block of dynamically allocated memory. If we are in multi-threaded
383 mode, it is ok to free it. If not, we add it to the garbage heap to be
386 static void sarray_free_garbage(void *vp) {
389 if (__objc_runtime_threads_alive == 1) {
396 sarray_remove_garbage();
399 *(void **)vp = first_free_data;
400 first_free_data = vp;