X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=libobjc%2Fsarray.c;h=b35772b3f53c2865d83680e00437d7bfbe5da08b;hb=c452f8c1edaeb90a2c6407ac83903d0d64411259;hp=7e40fba750f6b1e80044f48baccf5e2975d8da43;hpb=8a7d0ecc89848fa1b5bd4af83609f07ee93d11e3;p=pf3gnuchains%2Fgcc-fork.git diff --git a/libobjc/sarray.c b/libobjc/sarray.c index 7e40fba750f..b35772b3f53 100644 --- a/libobjc/sarray.c +++ b/libobjc/sarray.c @@ -1,22 +1,22 @@ /* Sparse Arrays for Objective C dispatch tables - Copyright (C) 1993, 1995, 1996 Free Software Foundation, Inc. + Copyright (C) 1993, 1995, 1996, 2002, 2004 Free Software Foundation, Inc. -This file is part of GNU CC. +This file is part of GCC. -GNU CC is free software; you can redistribute it and/or modify +GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) any later version. -GNU CC is distributed in the hope that it will be useful, +GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License -along with GNU CC; see the file COPYING. If not, write to -the Free Software Foundation, 59 Temple Place - Suite 330, -Boston, MA 02111-1307, USA. */ +along with GCC; see the file COPYING. If not, write to +the Free Software Foundation, 51 Franklin Street, Fifth Floor, +Boston, MA 02110-1301, USA. */ /* As a special exception, if you link this library with files compiled with GCC to produce an executable, this does not cause @@ -34,40 +34,36 @@ int nindices = 0; /* !T:MUTEX */ int narrays = 0; /* !T:MUTEX */ int idxsize = 0; /* !T:MUTEX */ -static void * first_free_data = NULL; /* !T:MUTEX */ +static void *first_free_data = NULL; /* !T:MUTEX */ #ifdef OBJC_SPARSE2 -const char* __objc_sparse2_id = "2 level sparse indices"; +const char *__objc_sparse2_id = "2 level sparse indices"; #endif #ifdef OBJC_SPARSE3 -const char* __objc_sparse3_id = "3 level sparse indices"; -#endif - -#ifdef __alpha__ -const void *memcpy (void*, const void*, size_t); +const char *__objc_sparse3_id = "3 level sparse indices"; #endif /* This function removes any structures left over from free operations that were not safe in a multi-threaded environment. */ void -sarray_remove_garbage(void) +sarray_remove_garbage (void) { void **vp; void *np; - objc_mutex_lock(__objc_runtime_mutex); + objc_mutex_lock (__objc_runtime_mutex); vp = first_free_data; first_free_data = NULL; while (vp) { np = *vp; - objc_free(vp); + objc_free (vp); vp = np; } - objc_mutex_unlock(__objc_runtime_mutex); + objc_mutex_unlock (__objc_runtime_mutex); } /* Free a block of dynamically allocated memory. If we are in multi-threaded @@ -75,33 +71,33 @@ sarray_remove_garbage(void) freed later. */ static void -sarray_free_garbage(void *vp) +sarray_free_garbage (void *vp) { - objc_mutex_lock(__objc_runtime_mutex); + objc_mutex_lock (__objc_runtime_mutex); if (__objc_runtime_threads_alive == 1) { - objc_free(vp); + objc_free (vp); if (first_free_data) - sarray_remove_garbage(); + sarray_remove_garbage (); } else { *(void **)vp = first_free_data; first_free_data = vp; } - objc_mutex_unlock(__objc_runtime_mutex); + objc_mutex_unlock (__objc_runtime_mutex); } /* sarray_at_put : copies data in such a way as to be thread reader safe. */ void -sarray_at_put(struct sarray* array, sidx index, void* element) +sarray_at_put (struct sarray *array, sidx index, void *element) { #ifdef OBJC_SPARSE3 - struct sindex** the_index; - struct sindex* new_index; + struct sindex **the_index; + struct sindex *new_index; #endif - struct sbucket** the_bucket; - struct sbucket* new_bucket; + struct sbucket **the_bucket; + struct sbucket *new_bucket; #ifdef OBJC_SPARSE3 size_t ioffset; #endif @@ -126,7 +122,7 @@ sarray_at_put(struct sarray* array, sidx index, void* element) #endif #endif /* not PRECOMPUTE_SELECTORS */ - assert(soffset_decode(index) < array->capacity); /* Range check */ + assert (soffset_decode (index) < array->capacity); /* Range check */ #ifdef OBJC_SPARSE3 the_index = &(array->indices[ioffset]); @@ -145,8 +141,8 @@ sarray_at_put(struct sarray* array, sidx index, void* element) if ((*the_index) == array->empty_index) { /* The index was previously empty, allocate a new */ - new_index = (struct sindex*)objc_malloc(sizeof(struct sindex)); - memcpy(new_index, array->empty_index, sizeof(struct sindex)); + new_index = (struct sindex *) objc_malloc (sizeof (struct sindex)); + memcpy (new_index, array->empty_index, sizeof (struct sindex)); new_index->version.version = array->version.version; *the_index = new_index; /* Prepared for install. */ the_bucket = &((*the_index)->buckets[boffset]); @@ -155,9 +151,9 @@ sarray_at_put(struct sarray* array, sidx index, void* element) } else if ((*the_index)->version.version != array->version.version) { /* This index must be lazy copied */ - struct sindex* old_index = *the_index; - new_index = (struct sindex*)objc_malloc(sizeof(struct sindex)); - memcpy( new_index, old_index, sizeof(struct sindex)); + struct sindex *old_index = *the_index; + new_index = (struct sindex *) objc_malloc (sizeof (struct sindex)); + memcpy (new_index, old_index, sizeof (struct sindex)); new_index->version.version = array->version.version; *the_index = new_index; /* Prepared for install. */ the_bucket = &((*the_index)->buckets[boffset]); @@ -173,9 +169,9 @@ sarray_at_put(struct sarray* array, sidx index, void* element) /* The bucket was previously empty (or something like that), */ /* allocate a new. This is the effect of `lazy' allocation */ - new_bucket = (struct sbucket*)objc_malloc(sizeof(struct sbucket)); - memcpy((void *) new_bucket, (const void*)array->empty_bucket, - sizeof(struct sbucket)); + new_bucket = (struct sbucket *) objc_malloc (sizeof (struct sbucket)); + memcpy ((void *) new_bucket, (const void *) array->empty_bucket, + sizeof (struct sbucket)); new_bucket->version.version = array->version.version; *the_bucket = new_bucket; /* Prepared for install. */ @@ -184,9 +180,9 @@ sarray_at_put(struct sarray* array, sidx index, void* element) } else if ((*the_bucket)->version.version != array->version.version) { /* Perform lazy copy. */ - struct sbucket* old_bucket = *the_bucket; - new_bucket = (struct sbucket*)objc_malloc(sizeof(struct sbucket)); - memcpy( new_bucket, old_bucket, sizeof(struct sbucket)); + struct sbucket *old_bucket = *the_bucket; + new_bucket = (struct sbucket *) objc_malloc (sizeof (struct sbucket)); + memcpy (new_bucket, old_bucket, sizeof (struct sbucket)); new_bucket->version.version = array->version.version; *the_bucket = new_bucket; /* Prepared for install. */ @@ -197,39 +193,39 @@ sarray_at_put(struct sarray* array, sidx index, void* element) } void -sarray_at_put_safe(struct sarray* array, sidx index, void* element) +sarray_at_put_safe (struct sarray *array, sidx index, void *element) { - if(soffset_decode(index) >= array->capacity) - sarray_realloc(array, soffset_decode(index)+1); - sarray_at_put(array, index, element); + if (soffset_decode (index) >= array->capacity) + sarray_realloc (array, soffset_decode (index) + 1); + sarray_at_put (array, index, element); } -struct sarray* -sarray_new (int size, void* default_element) +struct sarray * +sarray_new (int size, void *default_element) { - struct sarray* arr; + struct sarray *arr; #ifdef OBJC_SPARSE3 - size_t num_indices = ((size-1)/(INDEX_CAPACITY))+1; - struct sindex ** new_indices; + size_t num_indices = ((size - 1)/(INDEX_CAPACITY)) + 1; + struct sindex **new_indices; #else /* OBJC_SPARSE2 */ - size_t num_indices = ((size-1)/BUCKET_SIZE)+1; - struct sbucket ** new_buckets; + size_t num_indices = ((size - 1)/BUCKET_SIZE) + 1; + struct sbucket **new_buckets; #endif - int counter; + size_t counter; - assert(size > 0); + assert (size > 0); /* Allocate core array */ - arr = (struct sarray*) objc_malloc(sizeof(struct sarray)); + arr = (struct sarray *) objc_malloc (sizeof (struct sarray)); arr->version.version = 0; /* Initialize members */ #ifdef OBJC_SPARSE3 arr->capacity = num_indices*INDEX_CAPACITY; - new_indices = (struct sindex**) - objc_malloc(sizeof(struct sindex*)*num_indices); + new_indices = (struct sindex **) + objc_malloc (sizeof (struct sindex *) * num_indices); - arr->empty_index = (struct sindex*) objc_malloc(sizeof(struct sindex)); + arr->empty_index = (struct sindex *) objc_malloc (sizeof (struct sindex)); arr->empty_index->version.version = 0; narrays += 1; @@ -238,35 +234,35 @@ sarray_new (int size, void* default_element) #else /* OBJC_SPARSE2 */ arr->capacity = num_indices*BUCKET_SIZE; - new_buckets = (struct sbucket**) - objc_malloc(sizeof(struct sbucket*)*num_indices); + new_buckets = (struct sbucket **) + objc_malloc (sizeof (struct sbucket *) * num_indices); narrays += 1; idxsize += num_indices; #endif - arr->empty_bucket = (struct sbucket*) objc_malloc(sizeof(struct sbucket)); + arr->empty_bucket = (struct sbucket *) objc_malloc (sizeof (struct sbucket)); arr->empty_bucket->version.version = 0; nbuckets += 1; arr->ref_count = 1; - arr->is_copy_of = (struct sarray*)0; + arr->is_copy_of = (struct sarray *) 0; - for (counter=0; counterempty_bucket->elems[counter] = default_element; #ifdef OBJC_SPARSE3 - for (counter=0; counterempty_index->buckets[counter] = arr->empty_bucket; - for (counter=0; counterempty_index; #else /* OBJC_SPARSE2 */ - for (counter=0; counterempty_bucket; #endif @@ -286,48 +282,48 @@ sarray_new (int size, void* default_element) any concurrent readers notice the update. */ void -sarray_realloc(struct sarray* array, int newsize) +sarray_realloc (struct sarray *array, int newsize) { #ifdef OBJC_SPARSE3 - size_t old_max_index = (array->capacity-1)/INDEX_CAPACITY; - size_t new_max_index = ((newsize-1)/INDEX_CAPACITY); - size_t rounded_size = (new_max_index+1)*INDEX_CAPACITY; + size_t old_max_index = (array->capacity - 1)/INDEX_CAPACITY; + size_t new_max_index = ((newsize - 1)/INDEX_CAPACITY); + size_t rounded_size = (new_max_index + 1) * INDEX_CAPACITY; - struct sindex ** new_indices; - struct sindex ** old_indices; + struct sindex **new_indices; + struct sindex **old_indices; #else /* OBJC_SPARSE2 */ - size_t old_max_index = (array->capacity-1)/BUCKET_SIZE; - size_t new_max_index = ((newsize-1)/BUCKET_SIZE); - size_t rounded_size = (new_max_index+1)*BUCKET_SIZE; + size_t old_max_index = (array->capacity - 1)/BUCKET_SIZE; + size_t new_max_index = ((newsize - 1)/BUCKET_SIZE); + size_t rounded_size = (new_max_index + 1) * BUCKET_SIZE; - struct sbucket ** new_buckets; - struct sbucket ** old_buckets; + struct sbucket **new_buckets; + struct sbucket **old_buckets; #endif - int counter; + size_t counter; - assert(newsize > 0); + assert (newsize > 0); /* The size is the same, just ignore the request */ - if(rounded_size <= array->capacity) + if (rounded_size <= array->capacity) return; - assert(array->ref_count == 1); /* stop if lazy copied... */ + assert (array->ref_count == 1); /* stop if lazy copied... */ /* We are asked to extend the array -- allocate new bucket table, */ /* and insert empty_bucket in newly allocated places. */ - if(rounded_size > array->capacity) + if (rounded_size > array->capacity) { #ifdef OBJC_SPARSE3 new_max_index += 4; - rounded_size = (new_max_index+1)*INDEX_CAPACITY; + rounded_size = (new_max_index + 1) * INDEX_CAPACITY; #else /* OBJC_SPARSE2 */ new_max_index += 4; - rounded_size = (new_max_index+1)*BUCKET_SIZE; + rounded_size = (new_max_index + 1) * BUCKET_SIZE; #endif /* update capacity */ @@ -336,16 +332,16 @@ sarray_realloc(struct sarray* array, int newsize) #ifdef OBJC_SPARSE3 /* alloc to force re-read by any concurrent readers. */ old_indices = array->indices; - new_indices = (struct sindex**) - objc_malloc((new_max_index+1)*sizeof(struct sindex*)); + new_indices = (struct sindex **) + objc_malloc ((new_max_index + 1) * sizeof (struct sindex *)); #else /* OBJC_SPARSE2 */ old_buckets = array->buckets; - new_buckets = (struct sbucket**) - objc_malloc((new_max_index+1)*sizeof(struct sbucket*)); + new_buckets = (struct sbucket **) + objc_malloc ((new_max_index + 1) * sizeof (struct sbucket *)); #endif /* copy buckets below old_max_index (they are still valid) */ - for(counter = 0; counter <= old_max_index; counter++ ) { + for (counter = 0; counter <= old_max_index; counter++ ) { #ifdef OBJC_SPARSE3 new_indices[counter] = old_indices[counter]; #else /* OBJC_SPARSE2 */ @@ -355,11 +351,11 @@ sarray_realloc(struct sarray* array, int newsize) #ifdef OBJC_SPARSE3 /* reset entries above old_max_index to empty_bucket */ - for(counter = old_max_index+1; counter <= new_max_index; counter++) + for (counter = old_max_index + 1; counter <= new_max_index; counter++) new_indices[counter] = array->empty_index; #else /* OBJC_SPARSE2 */ /* reset entries above old_max_index to empty_bucket */ - for(counter = old_max_index+1; counter <= new_max_index; counter++) + for (counter = old_max_index + 1; counter <= new_max_index; counter++) new_buckets[counter] = array->empty_bucket; #endif @@ -372,9 +368,9 @@ sarray_realloc(struct sarray* array, int newsize) #ifdef OBJC_SPARSE3 /* free the old indices */ - sarray_free_garbage(old_indices); + sarray_free_garbage (old_indices); #else /* OBJC_SPARSE2 */ - sarray_free_garbage(old_buckets); + sarray_free_garbage (old_buckets); #endif idxsize += (new_max_index-old_max_index); @@ -386,20 +382,19 @@ sarray_realloc(struct sarray* array, int newsize) /* Free a sparse array allocated with sarray_new */ void -sarray_free(struct sarray* array) { - +sarray_free (struct sarray *array) { #ifdef OBJC_SPARSE3 - size_t old_max_index = (array->capacity-1)/INDEX_CAPACITY; - struct sindex ** old_indices; + size_t old_max_index = (array->capacity - 1)/INDEX_CAPACITY; + struct sindex **old_indices; #else - size_t old_max_index = (array->capacity-1)/BUCKET_SIZE; - struct sbucket ** old_buckets; + size_t old_max_index = (array->capacity - 1)/BUCKET_SIZE; + struct sbucket **old_buckets; #endif - int counter = 0; + size_t counter = 0; - assert(array->ref_count != 0); /* Freed multiple times!!! */ + assert (array->ref_count != 0); /* Freed multiple times!!! */ - if(--(array->ref_count) != 0) /* There exists copies of me */ + if (--(array->ref_count) != 0) /* There exists copies of me */ return; #ifdef OBJC_SPARSE3 @@ -407,35 +402,32 @@ sarray_free(struct sarray* array) { #else old_buckets = array->buckets; #endif - - if((array->is_copy_of) && ((array->is_copy_of->ref_count - 1) == 0)) - sarray_free(array->is_copy_of); /* Free all entries that do not point to empty_bucket */ - for(counter = 0; counter <= old_max_index; counter++ ) { + for (counter = 0; counter <= old_max_index; counter++ ) { #ifdef OBJC_SPARSE3 - struct sindex* idx = old_indices[counter]; - if((idx != array->empty_index) && + struct sindex *idx = old_indices[counter]; + if ((idx != array->empty_index) && (idx->version.version == array->version.version)) { int c2; - for(c2=0; c2buckets[c2]; - if((bkt != array->empty_bucket) && + for (c2 = 0; c2 < INDEX_SIZE; c2++) { + struct sbucket *bkt = idx->buckets[c2]; + if ((bkt != array->empty_bucket) && (bkt->version.version == array->version.version)) { - sarray_free_garbage(bkt); + sarray_free_garbage (bkt); nbuckets -= 1; } } - sarray_free_garbage(idx); + sarray_free_garbage (idx); nindices -= 1; } #else /* OBJC_SPARSE2 */ - struct sbucket* bkt = array->buckets[counter]; + struct sbucket *bkt = array->buckets[counter]; if ((bkt != array->empty_bucket) && (bkt->version.version == array->version.version)) { - sarray_free_garbage(bkt); + sarray_free_garbage (bkt); nbuckets -= 1; } #endif @@ -443,52 +435,58 @@ sarray_free(struct sarray* array) { #ifdef OBJC_SPARSE3 /* free empty_index */ - if(array->empty_index->version.version == array->version.version) { - sarray_free_garbage(array->empty_index); + if (array->empty_index->version.version == array->version.version) { + sarray_free_garbage (array->empty_index); nindices -= 1; } #endif /* free empty_bucket */ - if(array->empty_bucket->version.version == array->version.version) { - sarray_free_garbage(array->empty_bucket); + if (array->empty_bucket->version.version == array->version.version) { + sarray_free_garbage (array->empty_bucket); nbuckets -= 1; } - idxsize -= (old_max_index+1); + idxsize -= (old_max_index + 1); narrays -= 1; #ifdef OBJC_SPARSE3 /* free bucket table */ - sarray_free_garbage(array->indices); + sarray_free_garbage (array->indices); #else /* free bucket table */ - sarray_free_garbage(array->buckets); + sarray_free_garbage (array->buckets); #endif + /* If this is a copy of another array, we free it (which might just + * decrement its reference count so it will be freed when no longer in use). + */ + if (array->is_copy_of) + sarray_free (array->is_copy_of); + /* free array */ - sarray_free_garbage(array); + sarray_free_garbage (array); } /* This is a lazy copy. Only the core of the structure is actually */ /* copied. */ -struct sarray* -sarray_lazy_copy(struct sarray* oarr) +struct sarray * +sarray_lazy_copy (struct sarray *oarr) { - struct sarray* arr; + struct sarray *arr; #ifdef OBJC_SPARSE3 - size_t num_indices = ((oarr->capacity-1)/INDEX_CAPACITY)+1; - struct sindex ** new_indices; + size_t num_indices = ((oarr->capacity - 1)/INDEX_CAPACITY) + 1; + struct sindex **new_indices; #else /* OBJC_SPARSE2 */ - size_t num_indices = ((oarr->capacity-1)/BUCKET_SIZE)+1; - struct sbucket ** new_buckets; + size_t num_indices = ((oarr->capacity - 1)/BUCKET_SIZE) + 1; + struct sbucket **new_buckets; #endif /* Allocate core array */ - arr = (struct sarray*) objc_malloc(sizeof(struct sarray)); /* !!! */ + arr = (struct sarray *) objc_malloc (sizeof (struct sarray)); /* !!! */ arr->version.version = oarr->version.version + 1; #ifdef OBJC_SPARSE3 arr->empty_index = oarr->empty_index; @@ -501,17 +499,15 @@ sarray_lazy_copy(struct sarray* oarr) #ifdef OBJC_SPARSE3 /* Copy bucket table */ - new_indices = (struct sindex**) - objc_malloc(sizeof(struct sindex*)*num_indices); - memcpy( new_indices,oarr->indices, - sizeof(struct sindex*)*num_indices); + new_indices = (struct sindex **) + objc_malloc (sizeof (struct sindex *) * num_indices); + memcpy (new_indices, oarr->indices, sizeof (struct sindex *) * num_indices); arr->indices = new_indices; #else /* Copy bucket table */ - new_buckets = (struct sbucket**) - objc_malloc(sizeof(struct sbucket*)*num_indices); - memcpy( new_buckets,oarr->buckets, - sizeof(struct sbucket*)*num_indices); + new_buckets = (struct sbucket **) + objc_malloc (sizeof (struct sbucket *) * num_indices); + memcpy (new_buckets, oarr->buckets, sizeof (struct sbucket *) * num_indices); arr->buckets = new_buckets; #endif