diff options
Diffstat (limited to 'gcc-4.6/libobjc/objc/deprecated/sarray.h')
| -rw-r--r-- | gcc-4.6/libobjc/objc/deprecated/sarray.h | 240 |
1 files changed, 240 insertions, 0 deletions
diff --git a/gcc-4.6/libobjc/objc/deprecated/sarray.h b/gcc-4.6/libobjc/objc/deprecated/sarray.h new file mode 100644 index 000000000..aa2f3350a --- /dev/null +++ b/gcc-4.6/libobjc/objc/deprecated/sarray.h @@ -0,0 +1,240 @@ +/* Sparse Arrays for Objective C dispatch tables + Copyright (C) 1993, 1995, 1996, 2004, 2009 Free Software Foundation, Inc. + Contributed by Kresten Krab Thorup. + +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/>. */ + + +#ifndef __sarray_INCLUDE_GNU +#define __sarray_INCLUDE_GNU + +#define OBJC_SPARSE2 /* 2-level sparse array */ +/* #define OBJC_SPARSE3 */ /* 3-level sparse array */ + +#ifdef OBJC_SPARSE2 +extern const char* __objc_sparse2_id; +#endif + +#ifdef OBJC_SPARSE3 +extern const char* __objc_sparse3_id; +#endif + +#include <stddef.h> + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +extern int nbuckets; /* for stats */ +extern int nindices; +extern int narrays; +extern int idxsize; + +/* An unsigned integer of same size as a pointer */ +#define SIZET_BITS (sizeof(size_t)*8) + +#if defined(__sparc__) || defined(OBJC_SPARSE2) +#define PRECOMPUTE_SELECTORS +#endif + +#ifdef OBJC_SPARSE3 + +/* Buckets are 8 words each */ +#define BUCKET_BITS 3 +#define BUCKET_SIZE (1<<BUCKET_BITS) +#define BUCKET_MASK (BUCKET_SIZE-1) + +/* Indices are 16 words each */ +#define INDEX_BITS 4 +#define INDEX_SIZE (1<<INDEX_BITS) +#define INDEX_MASK (INDEX_SIZE-1) + +#define INDEX_CAPACITY (BUCKET_SIZE*INDEX_SIZE) + +#else /* OBJC_SPARSE2 */ + +/* Buckets are 32 words each */ +#define BUCKET_BITS 5 +#define BUCKET_SIZE (1<<BUCKET_BITS) +#define BUCKET_MASK (BUCKET_SIZE-1) + +#endif /* OBJC_SPARSE2 */ + +typedef size_t sidx; + +#ifdef PRECOMPUTE_SELECTORS + +struct soffset { +#ifdef OBJC_SPARSE3 + unsigned int unused : SIZET_BITS/4; + unsigned int eoffset : SIZET_BITS/4; + unsigned int boffset : SIZET_BITS/4; + unsigned int ioffset : SIZET_BITS/4; +#else /* OBJC_SPARSE2 */ +#ifdef __sparc__ + unsigned long boffset : (SIZET_BITS - 2) - BUCKET_BITS; + unsigned int eoffset : BUCKET_BITS; + unsigned int unused : 2; +#else + unsigned int boffset : SIZET_BITS/2; + unsigned int eoffset : SIZET_BITS/2; +#endif +#endif /* OBJC_SPARSE2 */ +}; + +union sofftype { + struct soffset off; + sidx idx; +}; + +#endif /* not PRECOMPUTE_SELECTORS */ + +union sversion { + int version; + void *next_free; +}; + +struct sbucket { + void* elems[BUCKET_SIZE]; /* elements stored in array */ + union sversion version; /* used for copy-on-write */ +}; + +#ifdef OBJC_SPARSE3 + +struct sindex { + struct sbucket* buckets[INDEX_SIZE]; + union sversion version; /* used for copy-on-write */ +}; + +#endif /* OBJC_SPARSE3 */ + +struct sarray { +#ifdef OBJC_SPARSE3 + struct sindex** indices; + struct sindex* empty_index; +#else /* OBJC_SPARSE2 */ + struct sbucket** buckets; +#endif /* OBJC_SPARSE2 */ + struct sbucket* empty_bucket; + union sversion version; /* used for copy-on-write */ + short ref_count; + struct sarray* is_copy_of; + size_t capacity; +}; + +struct sarray* sarray_new(int, void* default_element); +void sarray_free(struct sarray*); +struct sarray* sarray_lazy_copy(struct sarray*); +void sarray_realloc(struct sarray*, int new_size); +void sarray_at_put(struct sarray*, sidx indx, void* elem); +void sarray_at_put_safe(struct sarray*, sidx indx, void* elem); + +struct sarray* sarray_hard_copy(struct sarray*); /* ... like the name? */ +void sarray_remove_garbage(void); + + +#ifdef PRECOMPUTE_SELECTORS +/* Transform soffset values to ints and vica verca */ +static inline unsigned int +soffset_decode(sidx indx) +{ + union sofftype x; + x.idx = indx; +#ifdef OBJC_SPARSE3 + return x.off.eoffset + + (x.off.boffset*BUCKET_SIZE) + + (x.off.ioffset*INDEX_CAPACITY); +#else /* OBJC_SPARSE2 */ + return x.off.eoffset + (x.off.boffset*BUCKET_SIZE); +#endif /* OBJC_SPARSE2 */ +} + +static inline sidx +soffset_encode(size_t offset) +{ + union sofftype x; + x.off.eoffset = offset%BUCKET_SIZE; +#ifdef OBJC_SPARSE3 + x.off.boffset = (offset/BUCKET_SIZE)%INDEX_SIZE; + x.off.ioffset = offset/INDEX_CAPACITY; +#else /* OBJC_SPARSE2 */ + x.off.boffset = offset/BUCKET_SIZE; +#endif + return (sidx)x.idx; +} + +#else /* not PRECOMPUTE_SELECTORS */ + +static inline size_t +soffset_decode(sidx indx) +{ + return indx; +} + +static inline sidx +soffset_encode(size_t offset) +{ + return offset; +} +#endif /* not PRECOMPUTE_SELECTORS */ + +/* Get element from the Sparse array `array' at offset `indx' */ + +static inline void* sarray_get(struct sarray* array, sidx indx) +{ +#ifdef PRECOMPUTE_SELECTORS + union sofftype x; + x.idx = indx; +#ifdef OBJC_SPARSE3 + return + array-> + indices[x.off.ioffset]-> + buckets[x.off.boffset]-> + elems[x.off.eoffset]; +#else /* OBJC_SPARSE2 */ + return array->buckets[x.off.boffset]->elems[x.off.eoffset]; +#endif /* OBJC_SPARSE2 */ +#else /* not PRECOMPUTE_SELECTORS */ +#ifdef OBJC_SPARSE3 + return array-> + indices[indx/INDEX_CAPACITY]-> + buckets[(indx/BUCKET_SIZE)%INDEX_SIZE]-> + elems[indx%BUCKET_SIZE]; +#else /* OBJC_SPARSE2 */ + return array->buckets[indx/BUCKET_SIZE]->elems[indx%BUCKET_SIZE]; +#endif /* not OBJC_SPARSE3 */ +#endif /* not PRECOMPUTE_SELECTORS */ +} + +static inline void* sarray_get_safe(struct sarray* array, sidx indx) +{ + if(soffset_decode(indx) < array->capacity) + return sarray_get(array, indx); + else + return (array->empty_bucket->elems[0]); +} + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif /* __sarray_INCLUDE_GNU */ |