1 /* Sparse Arrays for Objective C dispatch tables
2 Copyright (C) 1993, 1995, 1996, 2004 Free Software Foundation, Inc.
3 Contributed by Kresten Krab Thorup.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
22 /* As a special exception, if you link this library with files
23 compiled with GCC to produce an executable, this does not cause
24 the resulting executable to be covered by the GNU General Public License.
25 This exception does not however invalidate any other reasons why
26 the executable file might be covered by the GNU General Public License. */
28 #ifndef __sarray_INCLUDE_GNU
29 #define __sarray_INCLUDE_GNU
33 #define OBJC_SPARSE2 /* 2-level sparse array */
34 /* #define OBJC_SPARSE3 */ /* 3-level sparse array */
37 extern const char* __objc_sparse2_id
;
41 extern const char* __objc_sparse3_id
;
48 #endif /* __cplusplus */
50 extern int nbuckets
; /* for stats */
57 #endif /* __cplusplus */
62 /* An unsigned integer of same size as a pointer */
63 #define SIZET_BITS (sizeof(size_t)*8)
65 #if defined(__sparc__) || defined(OBJC_SPARSE2)
66 #define PRECOMPUTE_SELECTORS
71 /* Buckets are 8 words each */
73 #define BUCKET_SIZE (1<<BUCKET_BITS)
74 #define BUCKET_MASK (BUCKET_SIZE-1)
76 /* Indices are 16 words each */
78 #define INDEX_SIZE (1<<INDEX_BITS)
79 #define INDEX_MASK (INDEX_SIZE-1)
81 #define INDEX_CAPACITY (BUCKET_SIZE*INDEX_SIZE)
83 #else /* OBJC_SPARSE2 */
85 /* Buckets are 32 words each */
87 #define BUCKET_SIZE (1<<BUCKET_BITS)
88 #define BUCKET_MASK (BUCKET_SIZE-1)
90 #endif /* OBJC_SPARSE2 */
94 #ifdef PRECOMPUTE_SELECTORS
98 unsigned int unused
: SIZET_BITS
/4;
99 unsigned int eoffset
: SIZET_BITS
/4;
100 unsigned int boffset
: SIZET_BITS
/4;
101 unsigned int ioffset
: SIZET_BITS
/4;
102 #else /* OBJC_SPARSE2 */
104 unsigned long boffset
: (SIZET_BITS
- 2) - BUCKET_BITS
;
105 unsigned int eoffset
: BUCKET_BITS
;
106 unsigned int unused
: 2;
108 unsigned int boffset
: SIZET_BITS
/2;
109 unsigned int eoffset
: SIZET_BITS
/2;
111 #endif /* OBJC_SPARSE2 */
119 #endif /* not PRECOMPUTE_SELECTORS */
127 void* elems
[BUCKET_SIZE
]; /* elements stored in array */
128 union sversion version
; /* used for copy-on-write */
134 struct sbucket
* buckets
[INDEX_SIZE
];
135 union sversion version
; /* used for copy-on-write */
138 #endif /* OBJC_SPARSE3 */
142 struct sindex
** indices
;
143 struct sindex
* empty_index
;
144 #else /* OBJC_SPARSE2 */
145 struct sbucket
** buckets
;
146 #endif /* OBJC_SPARSE2 */
147 struct sbucket
* empty_bucket
;
148 union sversion version
; /* used for copy-on-write */
150 struct sarray
* is_copy_of
;
156 #endif /* __cplusplus */
158 struct sarray
* sarray_new(int, void* default_element
);
159 void sarray_free(struct sarray
*);
160 struct sarray
* sarray_lazy_copy(struct sarray
*);
161 void sarray_realloc(struct sarray
*, int new_size
);
162 void sarray_at_put(struct sarray
*, sidx indx
, void* elem
);
163 void sarray_at_put_safe(struct sarray
*, sidx indx
, void* elem
);
165 struct sarray
* sarray_hard_copy(struct sarray
*); /* ... like the name? */
166 void sarray_remove_garbage(void);
169 #ifdef PRECOMPUTE_SELECTORS
170 /* Transform soffset values to ints and vica verca */
171 static inline unsigned int
172 soffset_decode(sidx indx
)
178 + (x
.off
.boffset
*BUCKET_SIZE
)
179 + (x
.off
.ioffset
*INDEX_CAPACITY
);
180 #else /* OBJC_SPARSE2 */
181 return x
.off
.eoffset
+ (x
.off
.boffset
*BUCKET_SIZE
);
182 #endif /* OBJC_SPARSE2 */
186 soffset_encode(size_t offset
)
189 x
.off
.eoffset
= offset
%BUCKET_SIZE
;
191 x
.off
.boffset
= (offset
/BUCKET_SIZE
)%INDEX_SIZE
;
192 x
.off
.ioffset
= offset
/INDEX_CAPACITY
;
193 #else /* OBJC_SPARSE2 */
194 x
.off
.boffset
= offset
/BUCKET_SIZE
;
199 #else /* not PRECOMPUTE_SELECTORS */
202 soffset_decode(sidx indx
)
208 soffset_encode(size_t offset
)
212 #endif /* not PRECOMPUTE_SELECTORS */
214 /* Get element from the Sparse array `array' at offset `indx' */
216 static inline void* sarray_get(struct sarray
* array
, sidx indx
)
218 #ifdef PRECOMPUTE_SELECTORS
224 indices
[x
.off
.ioffset
]->
225 buckets
[x
.off
.boffset
]->
226 elems
[x
.off
.eoffset
];
227 #else /* OBJC_SPARSE2 */
228 return array
->buckets
[x
.off
.boffset
]->elems
[x
.off
.eoffset
];
229 #endif /* OBJC_SPARSE2 */
230 #else /* not PRECOMPUTE_SELECTORS */
233 indices
[indx
/INDEX_CAPACITY
]->
234 buckets
[(indx
/BUCKET_SIZE
)%INDEX_SIZE
]->
235 elems
[indx
%BUCKET_SIZE
];
236 #else /* OBJC_SPARSE2 */
237 return array
->buckets
[indx
/BUCKET_SIZE
]->elems
[indx
%BUCKET_SIZE
];
238 #endif /* not OBJC_SPARSE3 */
239 #endif /* not PRECOMPUTE_SELECTORS */
242 static inline void* sarray_get_safe(struct sarray
* array
, sidx indx
)
244 if(soffset_decode(indx
) < array
->capacity
)
245 return sarray_get(array
, indx
);
247 return (array
->empty_bucket
->elems
[0]);
252 #endif /* __cplusplus */
254 #endif /* __sarray_INCLUDE_GNU */