URL
https://opencores.org/ocsvn/openrisc/openrisc/trunk
Subversion Repositories openrisc
[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libobjc/] [sarray.c] - Rev 867
Go to most recent revision | Compare with Previous | Blame | View Log
/* Sparse Arrays for Objective C dispatch tables Copyright (C) 1993, 1995, 1996, 2002, 2004, 2009, 2010 Free Software Foundation, Inc. This file is part of GCC. 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 3, or (at your option) any later version. 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. Under Section 7 of GPL version 3, you are granted additional permissions described in the GCC Runtime Library Exception, version 3.1, as published by the Free Software Foundation. You should have received a copy of the GNU General Public License and a copy of the GCC Runtime Library Exception along with this program; see the files COPYING3 and COPYING.RUNTIME respectively. If not, see <http://www.gnu.org/licenses/>. */ #include "objc-private/common.h" #include "objc-private/sarray.h" #include "objc/runtime.h" /* For objc_malloc */ #include "objc/thr.h" /* For objc_mutex_lock */ #include "objc-private/module-abi-8.h" #include "objc-private/runtime.h" #include <stdio.h> #include <string.h> /* For memset */ #include <assert.h> /* For assert */ int nbuckets = 0; /* !T:MUTEX */ int nindices = 0; /* !T:MUTEX */ int narrays = 0; /* !T:MUTEX */ int idxsize = 0; /* !T:MUTEX */ static void *first_free_data = NULL; /* !T:MUTEX */ #ifdef OBJC_SPARSE2 const char *__objc_sparse2_id = "2 level sparse indices"; #endif #ifdef OBJC_SPARSE3 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) { void **vp; void *np; objc_mutex_lock (__objc_runtime_mutex); vp = first_free_data; first_free_data = NULL; while (vp) { np = *vp; objc_free (vp); vp = np; } objc_mutex_unlock (__objc_runtime_mutex); } /* Free a block of dynamically allocated memory. If we are in multi-threaded mode, it is ok to free it. If not, we add it to the garbage heap to be freed later. */ static void sarray_free_garbage (void *vp) { objc_mutex_lock (__objc_runtime_mutex); if (__objc_runtime_threads_alive == 1) { objc_free (vp); if (first_free_data) sarray_remove_garbage (); } else { *(void **)vp = first_free_data; first_free_data = vp; } 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) { #ifdef OBJC_SPARSE3 struct sindex **the_index; struct sindex *new_index; #endif struct sbucket **the_bucket; struct sbucket *new_bucket; #ifdef OBJC_SPARSE3 size_t ioffset; #endif size_t boffset; size_t eoffset; #ifdef PRECOMPUTE_SELECTORS union sofftype xx; xx.idx = index; #ifdef OBJC_SPARSE3 ioffset = xx.off.ioffset; #endif boffset = xx.off.boffset; eoffset = xx.off.eoffset; #else /* not PRECOMPUTE_SELECTORS */ #ifdef OBJC_SPARSE3 ioffset = index/INDEX_CAPACITY; boffset = (index/BUCKET_SIZE)%INDEX_SIZE; eoffset = index%BUCKET_SIZE; #else boffset = index/BUCKET_SIZE; eoffset = index%BUCKET_SIZE; #endif #endif /* not PRECOMPUTE_SELECTORS */ assert (soffset_decode (index) < array->capacity); /* Range check */ #ifdef OBJC_SPARSE3 the_index = &(array->indices[ioffset]); the_bucket = &((*the_index)->buckets[boffset]); #else the_bucket = &(array->buckets[boffset]); #endif if ((*the_bucket)->elems[eoffset] == element) return; /* Great! we just avoided a lazy copy. */ #ifdef OBJC_SPARSE3 /* First, perform lazy copy/allocation of index if needed. */ 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->version.version = array->version.version; *the_index = new_index; /* Prepared for install. */ the_bucket = &((*the_index)->buckets[boffset]); nindices += 1; } 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)); new_index->version.version = array->version.version; *the_index = new_index; /* Prepared for install. */ the_bucket = &((*the_index)->buckets[boffset]); nindices += 1; } #endif /* OBJC_SPARSE3 */ /* Next, perform lazy allocation/copy of the bucket if needed. */ if ((*the_bucket) == array->empty_bucket) { /* 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->version.version = array->version.version; *the_bucket = new_bucket; /* Prepared for install. */ nbuckets += 1; } 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)); new_bucket->version.version = array->version.version; *the_bucket = new_bucket; /* Prepared for install. */ nbuckets += 1; } (*the_bucket)->elems[eoffset] = element; } void 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); } struct sarray * sarray_new (int size, void *default_element) { struct sarray *arr; #ifdef OBJC_SPARSE3 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; #endif size_t counter; assert (size > 0); /* Allocate core array. */ 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); arr->empty_index = (struct sindex *) objc_malloc (sizeof (struct sindex)); arr->empty_index->version.version = 0; narrays += 1; idxsize += num_indices; nindices += 1; #else /* OBJC_SPARSE2 */ arr->capacity = num_indices*BUCKET_SIZE; 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->version.version = 0; nbuckets += 1; arr->ref_count = 1; arr->is_copy_of = (struct sarray *) 0; for (counter = 0; counter < BUCKET_SIZE; counter++) arr->empty_bucket->elems[counter] = default_element; #ifdef OBJC_SPARSE3 for (counter = 0; counter < INDEX_SIZE; counter++) arr->empty_index->buckets[counter] = arr->empty_bucket; for (counter = 0; counter < num_indices; counter++) new_indices[counter] = arr->empty_index; #else /* OBJC_SPARSE2 */ for (counter = 0; counter < num_indices; counter++) new_buckets[counter] = arr->empty_bucket; #endif #ifdef OBJC_SPARSE3 arr->indices = new_indices; #else /* OBJC_SPARSE2 */ arr->buckets = new_buckets; #endif return arr; } /* Reallocate the sparse array to hold `newsize' entries Note: We really allocate and then free. We have to do this to ensure that any concurrent readers notice the update. */ void 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; 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; struct sbucket **new_buckets; struct sbucket **old_buckets; #endif size_t counter; assert (newsize > 0); /* The size is the same, just ignore the request. */ if (rounded_size <= array->capacity) return; 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) { #ifdef OBJC_SPARSE3 new_max_index += 4; rounded_size = (new_max_index + 1) * INDEX_CAPACITY; #else /* OBJC_SPARSE2 */ new_max_index += 4; rounded_size = (new_max_index + 1) * BUCKET_SIZE; #endif /* Update capacity. */ array->capacity = rounded_size; #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 *)); #else /* OBJC_SPARSE2 */ old_buckets = array->buckets; 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++ ) { #ifdef OBJC_SPARSE3 new_indices[counter] = old_indices[counter]; #else /* OBJC_SPARSE2 */ new_buckets[counter] = old_buckets[counter]; #endif } #ifdef OBJC_SPARSE3 /* Reset entries above old_max_index to empty_bucket. */ 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++) new_buckets[counter] = array->empty_bucket; #endif #ifdef OBJC_SPARSE3 /* Install the new indices. */ array->indices = new_indices; #else /* OBJC_SPARSE2 */ array->buckets = new_buckets; #endif #ifdef OBJC_SPARSE3 /* Free the old indices. */ sarray_free_garbage (old_indices); #else /* OBJC_SPARSE2 */ sarray_free_garbage (old_buckets); #endif idxsize += (new_max_index-old_max_index); return; } } /* Free a sparse array allocated with sarray_new */ void sarray_free (struct sarray *array) { #ifdef OBJC_SPARSE3 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; #endif size_t counter = 0; assert (array->ref_count != 0); /* Freed multiple times!!! */ if (--(array->ref_count) != 0) /* There exists copies of me */ return; #ifdef OBJC_SPARSE3 old_indices = array->indices; #else old_buckets = array->buckets; #endif /* Free all entries that do not point to empty_bucket. */ for (counter = 0; counter <= old_max_index; counter++ ) { #ifdef OBJC_SPARSE3 struct sindex *idx = old_indices[counter]; if ((idx != array->empty_index) && (idx->version.version == array->version.version)) { int c2; 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); nbuckets -= 1; } } sarray_free_garbage (idx); nindices -= 1; } #else /* OBJC_SPARSE2 */ struct sbucket *bkt = old_buckets[counter]; if ((bkt != array->empty_bucket) && (bkt->version.version == array->version.version)) { sarray_free_garbage (bkt); nbuckets -= 1; } #endif } #ifdef OBJC_SPARSE3 /* Free 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); nbuckets -= 1; } idxsize -= (old_max_index + 1); narrays -= 1; #ifdef OBJC_SPARSE3 /* Free bucket table. */ sarray_free_garbage (array->indices); #else /* Free bucket table. */ 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); } /* This is a lazy copy. Only the core of the structure is actually copied. */ struct sarray * sarray_lazy_copy (struct sarray *oarr) { struct sarray *arr; #ifdef OBJC_SPARSE3 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; #endif /* Allocate core array. */ arr = (struct sarray *) objc_malloc (sizeof (struct sarray)); /* !!! */ arr->version.version = oarr->version.version + 1; #ifdef OBJC_SPARSE3 arr->empty_index = oarr->empty_index; #endif arr->empty_bucket = oarr->empty_bucket; arr->ref_count = 1; oarr->ref_count += 1; arr->is_copy_of = oarr; arr->capacity = oarr->capacity; #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); 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); arr->buckets = new_buckets; #endif idxsize += num_indices; narrays += 1; return arr; }
Go to most recent revision | Compare with Previous | Blame | View Log