![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to sarray.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple XNU] / GNUtools / cc / objc|
Return to sarray.h CVS log | Up to [Apple XNU] / GNUtools / cc / objc |
1.1 root 1: /* Sparse Arrays for Objective C dispatch tables
2: Copyright (C) 1993 Free Software Foundation, Inc.
3:
4: Author: Kresten Krab Thorup
5:
6: This file is part of GNU CC.
7:
8: GNU CC is free software; you can redistribute it and/or modify
9: it under the terms of the GNU General Public License as published by
10: the Free Software Foundation; either version 2, or (at your option)
11: any later version.
12:
13: GNU CC is distributed in the hope that it will be useful,
14: but WITHOUT ANY WARRANTY; without even the implied warranty of
15: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16: GNU General Public License for more details.
17:
18: You should have received a copy of the GNU General Public License
19: along with GNU CC; see the file COPYING. If not, write to
20: the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
21:
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. */
27:
28: #ifndef __sarray_INCLUDE_GNU
29: #define __sarray_INCLUDE_GNU
30:
31: #define OBJC_SPARSE2 /* 2-level sparse array */
32: /* #define OBJC_SPARSE3 */ /* 3-level sparse array */
33:
34: #ifdef OBJC_SPARSE2
35: extern const char* __objc_sparse2_id;
36: #endif
37:
38: #ifdef OBJC_SPARSE3
39: extern const char* __objc_sparse3_id;
40: #endif
41:
42: #ifdef IN_GCC
43: #include "gstddef.h"
44: #else
45: #include "stddef.h"
46: #endif
47:
48: extern int nbuckets; /* for stats */
49: extern int nindices;
50: extern int narrays;
51: extern int idxsize;
52:
53: #include <assert.h>
54:
55: /* An unsigned integer of same size as a pointer */
56: #define SIZET_BITS (sizeof(size_t)*8)
57:
58: #if defined(sparc) || defined(OBJC_SPARSE2)
59: #define PRECOMPUTE_SELECTORS
60: #endif
61:
62: #ifdef OBJC_SPARSE3
63:
64: /* Buckets are 8 words each */
65: #define BUCKET_BITS 3
66: #define BUCKET_SIZE (1<<BUCKET_BITS)
67: #define BUCKET_MASK (BUCKET_SIZE-1)
68:
69: /* Indices are 16 words each */
70: #define INDEX_BITS 4
71: #define INDEX_SIZE (1<<INDEX_BITS)
72: #define INDEX_MASK (INDEX_SIZE-1)
73:
74: #define INDEX_CAPACITY (BUCKET_SIZE*INDEX_SIZE)
75:
76: #else /* OBJC_SPARSE2 */
77:
78: /* Buckets are 32 words each */
79: #define BUCKET_BITS 5
80: #define BUCKET_SIZE (1<<BUCKET_BITS)
81: #define BUCKET_MASK (BUCKET_SIZE-1)
82:
83: #endif /* OBJC_SPARSE2 */
84:
85: typedef size_t sidx;
86:
87: #ifdef PRECOMPUTE_SELECTORS
88:
89: struct soffset {
90: #ifdef OBJC_SPARSE3
91: unsigned int unused : SIZET_BITS/4;
92: unsigned int eoffset : SIZET_BITS/4;
93: unsigned int boffset : SIZET_BITS/4;
94: unsigned int ioffset : SIZET_BITS/4;
95: #else /* OBJC_SPARSE2 */
96: #ifdef sparc
97: unsigned int boffset : (SIZET_BITS - 2) - BUCKET_BITS;
98: unsigned int eoffset : BUCKET_BITS;
99: unsigned int unused : 2;
100: #else
101: unsigned int boffset : SIZET_BITS/2;
102: unsigned int eoffset : SIZET_BITS/2;
103: #endif
104: #endif /* OBJC_SPARSE2 */
105: };
106:
107: union sofftype {
108: struct soffset off;
109: sidx idx;
110: };
111:
112: #endif /* not PRECOMPUTE_SELECTORS */
113:
114: void * __objc_xrealloc (void *optr, size_t size);
115: void * __objc_xmalloc (size_t size);
116:
117: struct sbucket {
118: void* elems[BUCKET_SIZE]; /* elements stored in array */
119: short version; /* used for copy-on-write */
120: };
121:
122: #ifdef OBJC_SPARSE3
123:
124: struct sindex {
125: struct sbucket* buckets[INDEX_SIZE];
126: short version;
127: };
128:
129: #endif /* OBJC_SPARSE3 */
130:
131: struct sarray {
132: #ifdef 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: short version;
140: short ref_count;
141: struct sarray* is_copy_of;
142: int capacity;
143: };
144:
145: struct sarray* sarray_new(int, void* default_element);
146: void sarray_free(struct sarray*);
147: struct sarray* sarray_lazy_copy(struct sarray*);
148: struct sarray* sarray_hard_copy(struct sarray*); /* ... like the name? */
149: void sarray_realloc(struct sarray*, int new_size);
150: void sarray_at_put(struct sarray*, sidx index, void* elem);
151: void sarray_at_put_safe(struct sarray*, sidx index, void* elem);
152:
153:
154: #ifdef PRECOMPUTE_SELECTORS
155: /* Transform soffset values to ints and vica verca */
156: static inline unsigned int
157: soffset_decode(sidx index)
158: {
159: union sofftype x;
160: x.idx = index;
161: #ifdef OBJC_SPARSE3
162: return x.off.eoffset
163: + (x.off.boffset*BUCKET_SIZE)
164: + (x.off.ioffset*INDEX_CAPACITY);
165: #else /* OBJC_SPARSE2 */
166: return x.off.eoffset + (x.off.boffset*BUCKET_SIZE);
167: #endif /* OBJC_SPARSE2 */
168: }
169:
170: static inline sidx
171: soffset_encode(size_t offset)
172: {
173: union sofftype x;
174: x.off.eoffset = offset%BUCKET_SIZE;
175: #ifdef OBJC_SPARSE3
176: x.off.boffset = (offset/BUCKET_SIZE)%INDEX_SIZE;
177: x.off.ioffset = offset/INDEX_CAPACITY;
178: #else /* OBJC_SPARSE2 */
179: x.off.boffset = offset/BUCKET_SIZE;
180: #endif
181: return (sidx)x.idx;
182: }
183:
184: #else /* not PRECOMPUTE_SELECTORS */
185:
186: static inline size_t
187: soffset_decode(sidx index)
188: {
189: return index;
190: }
191:
192: static inline sidx
193: soffset_encode(size_t offset)
194: {
195: return offset;
196: }
197: #endif /* not PRECOMPUTE_SELECTORS */
198:
199: /* Get element from the Sparse array `array' at offset `index' */
200:
201: static inline void* sarray_get(struct sarray* array, sidx index)
202: {
203: #ifdef PRECOMPUTE_SELECTORS
204: union sofftype x;
205: x.idx = index;
206: #ifdef OBJC_SPARSE3
207: return
208: array->
209: indices[x.off.ioffset]->
210: buckets[x.off.boffset]->
211: elems[x.off.eoffset];
212: #else /* OBJC_SPARSE2 */
213: return array->buckets[x.off.boffset]->elems[x.off.eoffset];
214: #endif /* OBJC_SPARSE2 */
215: #else /* not PRECOMPUTE_SELECTORS */
216: #ifdef OBJC_SPARSE3
217: return array->
218: indices[index/INDEX_CAPACITY]->
219: buckets[(index/BUCKET_SIZE)%INDEX_SIZE]->
220: elems[index%BUCKET_SIZE];
221: #else /* OBJC_SPARSE2 */
222: return array->buckets[index/BUCKET_SIZE]->elems[index%BUCKET_SIZE];
223: #endif /* not OBJC_SPARSE3 */
224: #endif /* not PRECOMPUTE_SELECTORS */
225: }
226:
227: static inline void* sarray_get_safe(struct sarray* array, sidx index)
228: {
229: if(soffset_decode(index) < array->capacity)
230: return sarray_get(array, index);
231: else
232: return (array->empty_bucket->elems[0]);
233: }
234:
235: #endif /* __sarray_INCLUDE_GNU */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.