1 /* Sparse Arrays for Objective C dispatch tables
2 Copyright (C) 1993, 1995, 1996 Free Software Foundation, Inc.
3 Contributed by Kresten Krab Thorup.
5 This file is part of GNU CC.
7 GNU CC 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 GNU CC 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 GNU CC; 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
31 #define OBJC_SPARSE2 /* 2-level sparse array */
32 /* #define OBJC_SPARSE3 */ /* 3-level sparse array */
35 extern const char* __objc_sparse2_id
;
39 extern const char* __objc_sparse3_id
;
46 extern int nbuckets
; /* for stats */
53 /* An unsigned integer of same size as a pointer */
54 #define SIZET_BITS (sizeof(size_t)*8)
56 #if defined(__sparc__) || defined(OBJC_SPARSE2)
57 #define PRECOMPUTE_SELECTORS
62 /* Buckets are 8 words each */
64 #define BUCKET_SIZE (1<<BUCKET_BITS)
65 #define BUCKET_MASK (BUCKET_SIZE-1)
67 /* Indices are 16 words each */
69 #define INDEX_SIZE (1<<INDEX_BITS)
70 #define INDEX_MASK (INDEX_SIZE-1)
72 #define INDEX_CAPACITY (BUCKET_SIZE*INDEX_SIZE)
74 #else /* OBJC_SPARSE2 */
76 /* Buckets are 32 words each */
78 #define BUCKET_SIZE (1<<BUCKET_BITS)
79 #define BUCKET_MASK (BUCKET_SIZE-1)
81 #endif /* OBJC_SPARSE2 */
85 #ifdef PRECOMPUTE_SELECTORS
89 unsigned int unused
: SIZET_BITS
/4;
90 unsigned int eoffset
: SIZET_BITS
/4;
91 unsigned int boffset
: SIZET_BITS
/4;
92 unsigned int ioffset
: SIZET_BITS
/4;
93 #else /* OBJC_SPARSE2 */
95 unsigned long boffset
: (SIZET_BITS
- 2) - BUCKET_BITS
;
96 unsigned int eoffset
: BUCKET_BITS
;
97 unsigned int unused
: 2;
99 unsigned int boffset
: SIZET_BITS
/2;
100 unsigned int eoffset
: SIZET_BITS
/2;
102 #endif /* OBJC_SPARSE2 */
110 #endif /* not PRECOMPUTE_SELECTORS */
118 void* elems
[BUCKET_SIZE
]; /* elements stored in array */
119 union sversion version
; /* used for copy-on-write */
125 struct sbucket
* buckets
[INDEX_SIZE
];
126 union sversion version
; /* used for copy-on-write */
129 #endif /* OBJC_SPARSE3 */
133 struct sindex
** indices
;
134 struct sindex
* empty_index
;
135 #else /* OBJC_SPARSE2 */
136 struct sbucket
** buckets
;
137 #endif /* OBJC_SPARSE2 */
138 struct sbucket
* empty_bucket
;
139 union sversion version
; /* used for copy-on-write */
141 struct sarray
* is_copy_of
;
145 struct sarray
* sarray_new(int, void* default_element
);
146 void sarray_free(struct sarray
*);
147 struct sarray
* sarray_lazy_copy(struct sarray
*);
148 void sarray_realloc(struct sarray
*, int new_size
);
149 void sarray_at_put(struct sarray
*, sidx index
, void* elem
);
150 void sarray_at_put_safe(struct sarray
*, sidx index
, void* elem
);
152 struct sarray
* sarray_hard_copy(struct sarray
*); /* ... like the name? */
153 void sarray_remove_garbage(void);
156 #ifdef PRECOMPUTE_SELECTORS
157 /* Transform soffset values to ints and vica verca */
158 static inline unsigned int
159 soffset_decode(sidx index
)
165 + (x
.off
.boffset
*BUCKET_SIZE
)
166 + (x
.off
.ioffset
*INDEX_CAPACITY
);
167 #else /* OBJC_SPARSE2 */
168 return x
.off
.eoffset
+ (x
.off
.boffset
*BUCKET_SIZE
);
169 #endif /* OBJC_SPARSE2 */
173 soffset_encode(size_t offset
)
176 x
.off
.eoffset
= offset
%BUCKET_SIZE
;
178 x
.off
.boffset
= (offset
/BUCKET_SIZE
)%INDEX_SIZE
;
179 x
.off
.ioffset
= offset
/INDEX_CAPACITY
;
180 #else /* OBJC_SPARSE2 */
181 x
.off
.boffset
= offset
/BUCKET_SIZE
;
186 #else /* not PRECOMPUTE_SELECTORS */
189 soffset_decode(sidx index
)
195 soffset_encode(size_t offset
)
199 #endif /* not PRECOMPUTE_SELECTORS */
201 /* Get element from the Sparse array `array' at offset `index' */
203 static inline void* sarray_get(struct sarray
* array
, sidx index
)
205 #ifdef PRECOMPUTE_SELECTORS
211 indices
[x
.off
.ioffset
]->
212 buckets
[x
.off
.boffset
]->
213 elems
[x
.off
.eoffset
];
214 #else /* OBJC_SPARSE2 */
215 return array
->buckets
[x
.off
.boffset
]->elems
[x
.off
.eoffset
];
216 #endif /* OBJC_SPARSE2 */
217 #else /* not PRECOMPUTE_SELECTORS */
220 indices
[index
/INDEX_CAPACITY
]->
221 buckets
[(index
/BUCKET_SIZE
)%INDEX_SIZE
]->
222 elems
[index
%BUCKET_SIZE
];
223 #else /* OBJC_SPARSE2 */
224 return array
->buckets
[index
/BUCKET_SIZE
]->elems
[index
%BUCKET_SIZE
];
225 #endif /* not OBJC_SPARSE3 */
226 #endif /* not PRECOMPUTE_SELECTORS */
229 static inline void* sarray_get_safe(struct sarray
* array
, sidx index
)
231 if(soffset_decode(index
) < array
->capacity
)
232 return sarray_get(array
, index
);
234 return (array
->empty_bucket
->elems
[0]);
237 #endif /* __sarray_INCLUDE_GNU */