* xmalloc.c (xmalloc): Fix spelling error.
[official-gcc.git] / libobjc / sarray.c
blobf5ace10bf092f4ee699e0cb0ea575e6d9ca26092
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)
9 any later version.
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. */
27 #include "sarray.h"
28 #include "runtime.h"
29 #include <stdio.h>
30 #include "assert.h"
32 int nbuckets = 0; /* !T:MUTEX */
33 int nindices = 0; /* !T:MUTEX */
34 int narrays = 0; /* !T:MUTEX */
35 int idxsize = 0; /* !T:MUTEX */
37 static void * first_free_data = NULL; /* !T:MUTEX */
39 #ifdef OBJC_SPARSE2
40 const char* __objc_sparse2_id = "2 level sparse indices";
41 #endif
43 #ifdef OBJC_SPARSE3
44 const char* __objc_sparse3_id = "3 level sparse indices";
45 #endif
47 #ifdef __alpha__
48 const void *memcpy (void*, const void*, size_t);
49 #endif
51 /* This function removes any structures left over from free operations
52 that were not safe in a multi-threaded environment. */
53 void
54 sarray_remove_garbage(void)
56 void **vp;
57 void *np;
59 objc_mutex_lock(__objc_runtime_mutex);
61 vp = first_free_data;
62 first_free_data = NULL;
64 while (vp) {
65 np = *vp;
66 objc_free(vp);
67 vp = np;
70 objc_mutex_unlock(__objc_runtime_mutex);
73 /* Free a block of dynamically allocated memory. If we are in multi-threaded
74 mode, it is ok to free it. If not, we add it to the garbage heap to be
75 freed later. */
77 static void
78 sarray_free_garbage(void *vp)
80 objc_mutex_lock(__objc_runtime_mutex);
82 if (__objc_runtime_threads_alive == 1) {
83 objc_free(vp);
84 if (first_free_data)
85 sarray_remove_garbage();
87 else {
88 *(void **)vp = first_free_data;
89 first_free_data = vp;
92 objc_mutex_unlock(__objc_runtime_mutex);
95 /* sarray_at_put : copies data in such a way as to be thread reader safe. */
96 void
97 sarray_at_put(struct sarray* array, sidx index, void* element)
99 #ifdef OBJC_SPARSE3
100 struct sindex** the_index;
101 struct sindex* new_index;
102 #endif
103 struct sbucket** the_bucket;
104 struct sbucket* new_bucket;
105 #ifdef OBJC_SPARSE3
106 size_t ioffset;
107 #endif
108 size_t boffset;
109 size_t eoffset;
110 #ifdef PRECOMPUTE_SELECTORS
111 union sofftype xx;
112 xx.idx = index;
113 #ifdef OBJC_SPARSE3
114 ioffset = xx.off.ioffset;
115 #endif
116 boffset = xx.off.boffset;
117 eoffset = xx.off.eoffset;
118 #else /* not PRECOMPUTE_SELECTORS */
119 #ifdef OBJC_SPARSE3
120 ioffset = index/INDEX_CAPACITY;
121 boffset = (index/BUCKET_SIZE)%INDEX_SIZE;
122 eoffset = index%BUCKET_SIZE;
123 #else
124 boffset = index/BUCKET_SIZE;
125 eoffset = index%BUCKET_SIZE;
126 #endif
127 #endif /* not PRECOMPUTE_SELECTORS */
129 assert(soffset_decode(index) < array->capacity); /* Range check */
131 #ifdef OBJC_SPARSE3
132 the_index = &(array->indices[ioffset]);
133 the_bucket = &((*the_index)->buckets[boffset]);
134 #else
135 the_bucket = &(array->buckets[boffset]);
136 #endif
138 if ((*the_bucket)->elems[eoffset] == element)
139 return; /* great! we just avoided a lazy copy */
141 #ifdef OBJC_SPARSE3
143 /* First, perform lazy copy/allocation of index if needed */
145 if ((*the_index) == array->empty_index) {
147 /* The index was previously empty, allocate a new */
148 new_index = (struct sindex*)objc_malloc(sizeof(struct sindex));
149 memcpy(new_index, array->empty_index, sizeof(struct sindex));
150 new_index->version.version = array->version.version;
151 *the_index = new_index; /* Prepared for install. */
152 the_bucket = &((*the_index)->buckets[boffset]);
154 nindices += 1;
155 } else if ((*the_index)->version.version != array->version.version) {
157 /* This index must be lazy copied */
158 struct sindex* old_index = *the_index;
159 new_index = (struct sindex*)objc_malloc(sizeof(struct sindex));
160 memcpy( new_index, old_index, sizeof(struct sindex));
161 new_index->version.version = array->version.version;
162 *the_index = new_index; /* Prepared for install. */
163 the_bucket = &((*the_index)->buckets[boffset]);
165 nindices += 1;
168 #endif /* OBJC_SPARSE3 */
170 /* next, perform lazy allocation/copy of the bucket if needed */
172 if ((*the_bucket) == array->empty_bucket) {
174 /* The bucket was previously empty (or something like that), */
175 /* allocate a new. This is the effect of `lazy' allocation */
176 new_bucket = (struct sbucket*)objc_malloc(sizeof(struct sbucket));
177 memcpy((void *) new_bucket, (const void*)array->empty_bucket,
178 sizeof(struct sbucket));
179 new_bucket->version.version = array->version.version;
180 *the_bucket = new_bucket; /* Prepared for install. */
182 nbuckets += 1;
184 } else if ((*the_bucket)->version.version != array->version.version) {
186 /* Perform lazy copy. */
187 struct sbucket* old_bucket = *the_bucket;
188 new_bucket = (struct sbucket*)objc_malloc(sizeof(struct sbucket));
189 memcpy( new_bucket, old_bucket, sizeof(struct sbucket));
190 new_bucket->version.version = array->version.version;
191 *the_bucket = new_bucket; /* Prepared for install. */
193 nbuckets += 1;
196 (*the_bucket)->elems[eoffset] = element;
199 void
200 sarray_at_put_safe(struct sarray* array, sidx index, void* element)
202 if(soffset_decode(index) >= array->capacity)
203 sarray_realloc(array, soffset_decode(index)+1);
204 sarray_at_put(array, index, element);
207 struct sarray*
208 sarray_new (int size, void* default_element)
210 struct sarray* arr;
211 #ifdef OBJC_SPARSE3
212 size_t num_indices = ((size-1)/(INDEX_CAPACITY))+1;
213 struct sindex ** new_indices;
214 #else /* OBJC_SPARSE2 */
215 size_t num_indices = ((size-1)/BUCKET_SIZE)+1;
216 struct sbucket ** new_buckets;
217 #endif
218 int counter;
220 assert(size > 0);
222 /* Allocate core array */
223 arr = (struct sarray*) objc_malloc(sizeof(struct sarray));
224 arr->version.version = 0;
226 /* Initialize members */
227 #ifdef OBJC_SPARSE3
228 arr->capacity = num_indices*INDEX_CAPACITY;
229 new_indices = (struct sindex**)
230 objc_malloc(sizeof(struct sindex*)*num_indices);
232 arr->empty_index = (struct sindex*) objc_malloc(sizeof(struct sindex));
233 arr->empty_index->version.version = 0;
235 narrays += 1;
236 idxsize += num_indices;
237 nindices += 1;
239 #else /* OBJC_SPARSE2 */
240 arr->capacity = num_indices*BUCKET_SIZE;
241 new_buckets = (struct sbucket**)
242 objc_malloc(sizeof(struct sbucket*)*num_indices);
244 narrays += 1;
245 idxsize += num_indices;
247 #endif
249 arr->empty_bucket = (struct sbucket*) objc_malloc(sizeof(struct sbucket));
250 arr->empty_bucket->version.version = 0;
252 nbuckets += 1;
254 arr->ref_count = 1;
255 arr->is_copy_of = (struct sarray*)0;
257 for (counter=0; counter<BUCKET_SIZE; counter++)
258 arr->empty_bucket->elems[counter] = default_element;
260 #ifdef OBJC_SPARSE3
261 for (counter=0; counter<INDEX_SIZE; counter++)
262 arr->empty_index->buckets[counter] = arr->empty_bucket;
264 for (counter=0; counter<num_indices; counter++)
265 new_indices[counter] = arr->empty_index;
267 #else /* OBJC_SPARSE2 */
269 for (counter=0; counter<num_indices; counter++)
270 new_buckets[counter] = arr->empty_bucket;
272 #endif
274 #ifdef OBJC_SPARSE3
275 arr->indices = new_indices;
276 #else /* OBJC_SPARSE2 */
277 arr->buckets = new_buckets;
278 #endif
280 return arr;
284 /* Reallocate the sparse array to hold `newsize' entries
285 Note: We really allocate and then free. We have to do this to ensure that
286 any concurrent readers notice the update. */
288 void
289 sarray_realloc(struct sarray* array, int newsize)
291 #ifdef OBJC_SPARSE3
292 size_t old_max_index = (array->capacity-1)/INDEX_CAPACITY;
293 size_t new_max_index = ((newsize-1)/INDEX_CAPACITY);
294 size_t rounded_size = (new_max_index+1)*INDEX_CAPACITY;
296 struct sindex ** new_indices;
297 struct sindex ** old_indices;
299 #else /* OBJC_SPARSE2 */
300 size_t old_max_index = (array->capacity-1)/BUCKET_SIZE;
301 size_t new_max_index = ((newsize-1)/BUCKET_SIZE);
302 size_t rounded_size = (new_max_index+1)*BUCKET_SIZE;
304 struct sbucket ** new_buckets;
305 struct sbucket ** old_buckets;
307 #endif
309 int counter;
311 assert(newsize > 0);
313 /* The size is the same, just ignore the request */
314 if(rounded_size <= array->capacity)
315 return;
317 assert(array->ref_count == 1); /* stop if lazy copied... */
319 /* We are asked to extend the array -- allocate new bucket table, */
320 /* and insert empty_bucket in newly allocated places. */
321 if(rounded_size > array->capacity)
324 #ifdef OBJC_SPARSE3
325 new_max_index += 4;
326 rounded_size = (new_max_index+1)*INDEX_CAPACITY;
328 #else /* OBJC_SPARSE2 */
329 new_max_index += 4;
330 rounded_size = (new_max_index+1)*BUCKET_SIZE;
331 #endif
333 /* update capacity */
334 array->capacity = rounded_size;
336 #ifdef OBJC_SPARSE3
337 /* alloc to force re-read by any concurrent readers. */
338 old_indices = array->indices;
339 new_indices = (struct sindex**)
340 objc_malloc((new_max_index+1)*sizeof(struct sindex*));
341 #else /* OBJC_SPARSE2 */
342 old_buckets = array->buckets;
343 new_buckets = (struct sbucket**)
344 objc_malloc((new_max_index+1)*sizeof(struct sbucket*));
345 #endif
347 /* copy buckets below old_max_index (they are still valid) */
348 for(counter = 0; counter <= old_max_index; counter++ ) {
349 #ifdef OBJC_SPARSE3
350 new_indices[counter] = old_indices[counter];
351 #else /* OBJC_SPARSE2 */
352 new_buckets[counter] = old_buckets[counter];
353 #endif
356 #ifdef OBJC_SPARSE3
357 /* reset entries above old_max_index to empty_bucket */
358 for(counter = old_max_index+1; counter <= new_max_index; counter++)
359 new_indices[counter] = array->empty_index;
360 #else /* OBJC_SPARSE2 */
361 /* reset entries above old_max_index to empty_bucket */
362 for(counter = old_max_index+1; counter <= new_max_index; counter++)
363 new_buckets[counter] = array->empty_bucket;
364 #endif
366 #ifdef OBJC_SPARSE3
367 /* install the new indices */
368 array->indices = new_indices;
369 #else /* OBJC_SPARSE2 */
370 array->buckets = new_buckets;
371 #endif
373 #ifdef OBJC_SPARSE3
374 /* free the old indices */
375 sarray_free_garbage(old_indices);
376 #else /* OBJC_SPARSE2 */
377 sarray_free_garbage(old_buckets);
378 #endif
380 idxsize += (new_max_index-old_max_index);
381 return;
386 /* Free a sparse array allocated with sarray_new */
388 void
389 sarray_free(struct sarray* array) {
391 #ifdef OBJC_SPARSE3
392 size_t old_max_index = (array->capacity-1)/INDEX_CAPACITY;
393 struct sindex ** old_indices;
394 #else
395 size_t old_max_index = (array->capacity-1)/BUCKET_SIZE;
396 struct sbucket ** old_buckets;
397 #endif
398 int counter = 0;
400 assert(array->ref_count != 0); /* Freed multiple times!!! */
402 if(--(array->ref_count) != 0) /* There exists copies of me */
403 return;
405 #ifdef OBJC_SPARSE3
406 old_indices = array->indices;
407 #else
408 old_buckets = array->buckets;
409 #endif
411 if((array->is_copy_of) && ((array->is_copy_of->ref_count - 1) == 0))
412 sarray_free(array->is_copy_of);
414 /* Free all entries that do not point to empty_bucket */
415 for(counter = 0; counter <= old_max_index; counter++ ) {
416 #ifdef OBJC_SPARSE3
417 struct sindex* idx = old_indices[counter];
418 if((idx != array->empty_index) &&
419 (idx->version.version == array->version.version)) {
420 int c2;
421 for(c2=0; c2<INDEX_SIZE; c2++) {
422 struct sbucket* bkt = idx->buckets[c2];
423 if((bkt != array->empty_bucket) &&
424 (bkt->version.version == array->version.version))
426 sarray_free_garbage(bkt);
427 nbuckets -= 1;
430 sarray_free_garbage(idx);
431 nindices -= 1;
433 #else /* OBJC_SPARSE2 */
434 struct sbucket* bkt = array->buckets[counter];
435 if ((bkt != array->empty_bucket) &&
436 (bkt->version.version == array->version.version))
438 sarray_free_garbage(bkt);
439 nbuckets -= 1;
441 #endif
444 #ifdef OBJC_SPARSE3
445 /* free empty_index */
446 if(array->empty_index->version.version == array->version.version) {
447 sarray_free_garbage(array->empty_index);
448 nindices -= 1;
450 #endif
452 /* free empty_bucket */
453 if(array->empty_bucket->version.version == array->version.version) {
454 sarray_free_garbage(array->empty_bucket);
455 nbuckets -= 1;
457 idxsize -= (old_max_index+1);
458 narrays -= 1;
460 #ifdef OBJC_SPARSE3
461 /* free bucket table */
462 sarray_free_garbage(array->indices);
464 #else
465 /* free bucket table */
466 sarray_free_garbage(array->buckets);
468 #endif
470 /* free array */
471 sarray_free_garbage(array);
474 /* This is a lazy copy. Only the core of the structure is actually */
475 /* copied. */
477 struct sarray*
478 sarray_lazy_copy(struct sarray* oarr)
480 struct sarray* arr;
482 #ifdef OBJC_SPARSE3
483 size_t num_indices = ((oarr->capacity-1)/INDEX_CAPACITY)+1;
484 struct sindex ** new_indices;
485 #else /* OBJC_SPARSE2 */
486 size_t num_indices = ((oarr->capacity-1)/BUCKET_SIZE)+1;
487 struct sbucket ** new_buckets;
488 #endif
490 /* Allocate core array */
491 arr = (struct sarray*) objc_malloc(sizeof(struct sarray)); /* !!! */
492 arr->version.version = oarr->version.version + 1;
493 #ifdef OBJC_SPARSE3
494 arr->empty_index = oarr->empty_index;
495 #endif
496 arr->empty_bucket = oarr->empty_bucket;
497 arr->ref_count = 1;
498 oarr->ref_count += 1;
499 arr->is_copy_of = oarr;
500 arr->capacity = oarr->capacity;
502 #ifdef OBJC_SPARSE3
503 /* Copy bucket table */
504 new_indices = (struct sindex**)
505 objc_malloc(sizeof(struct sindex*)*num_indices);
506 memcpy( new_indices,oarr->indices,
507 sizeof(struct sindex*)*num_indices);
508 arr->indices = new_indices;
509 #else
510 /* Copy bucket table */
511 new_buckets = (struct sbucket**)
512 objc_malloc(sizeof(struct sbucket*)*num_indices);
513 memcpy( new_buckets,oarr->buckets,
514 sizeof(struct sbucket*)*num_indices);
515 arr->buckets = new_buckets;
516 #endif
518 idxsize += num_indices;
519 narrays += 1;
521 return arr;