![[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 [GCC 2.x] / gcc / objc|
Return to sarray.h CVS log | Up to [GCC 2.x] / gcc / 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:
1.1.1.2 ! root 42: #include <stddef.h>
1.1 root 43:
44: extern int nbuckets; /* for stats */
45: extern int nindices;
46: extern int narrays;
47: extern int idxsize;
48:
49: #include <assert.h>
50:
51: /* An unsigned integer of same size as a pointer */
52: #define SIZET_BITS (sizeof(size_t)*8)
53:
54: #if defined(sparc) || defined(OBJC_SPARSE2)
55: #define PRECOMPUTE_SELECTORS
56: #endif
57:
58: #ifdef OBJC_SPARSE3
59:
60: /* Buckets are 8 words each */
61: #define BUCKET_BITS 3
62: #define BUCKET_SIZE (1<<BUCKET_BITS)
63: #define BUCKET_MASK (BUCKET_SIZE-1)
64:
65: /* Indices are 16 words each */
66: #define INDEX_BITS 4
67: #define INDEX_SIZE (1<<INDEX_BITS)
68: #define INDEX_MASK (INDEX_SIZE-1)
69:
70: #define INDEX_CAPACITY (BUCKET_SIZE*INDEX_SIZE)
71:
72: #else /* OBJC_SPARSE2 */
73:
74: /* Buckets are 32 words each */
75: #define BUCKET_BITS 5
76: #define BUCKET_SIZE (1<<BUCKET_BITS)
77: #define BUCKET_MASK (BUCKET_SIZE-1)
78:
79: #endif /* OBJC_SPARSE2 */
80:
81: typedef size_t sidx;
82:
83: #ifdef PRECOMPUTE_SELECTORS
84:
85: struct soffset {
86: #ifdef OBJC_SPARSE3
87: unsigned int unused : SIZET_BITS/4;
88: unsigned int eoffset : SIZET_BITS/4;
89: unsigned int boffset : SIZET_BITS/4;
90: unsigned int ioffset : SIZET_BITS/4;
91: #else /* OBJC_SPARSE2 */
92: #ifdef sparc
93: unsigned int boffset : (SIZET_BITS - 2) - BUCKET_BITS;
94: unsigned int eoffset : BUCKET_BITS;
95: unsigned int unused : 2;
96: #else
97: unsigned int boffset : SIZET_BITS/2;
98: unsigned int eoffset : SIZET_BITS/2;
99: #endif
100: #endif /* OBJC_SPARSE2 */
101: };
102:
103: union sofftype {
104: struct soffset off;
105: sidx idx;
106: };
107:
108: #endif /* not PRECOMPUTE_SELECTORS */
109:
110: void * __objc_xrealloc (void *optr, size_t size);
111: void * __objc_xmalloc (size_t size);
112:
113: struct sbucket {
114: void* elems[BUCKET_SIZE]; /* elements stored in array */
115: short version; /* used for copy-on-write */
116: };
117:
118: #ifdef OBJC_SPARSE3
119:
120: struct sindex {
121: struct sbucket* buckets[INDEX_SIZE];
122: short version;
123: };
124:
125: #endif /* OBJC_SPARSE3 */
126:
127: struct sarray {
128: #ifdef OBJC_SPARSE3
129: struct sindex** indices;
130: struct sindex* empty_index;
131: #else /* OBJC_SPARSE2 */
132: struct sbucket** buckets;
133: #endif /* OBJC_SPARSE2 */
134: struct sbucket* empty_bucket;
135: short version;
136: short ref_count;
137: struct sarray* is_copy_of;
138: int capacity;
139: };
140:
141: struct sarray* sarray_new(int, void* default_element);
142: void sarray_free(struct sarray*);
143: struct sarray* sarray_lazy_copy(struct sarray*);
144: struct sarray* sarray_hard_copy(struct sarray*); /* ... like the name? */
145: void sarray_realloc(struct sarray*, int new_size);
146: void sarray_at_put(struct sarray*, sidx index, void* elem);
147: void sarray_at_put_safe(struct sarray*, sidx index, void* elem);
148:
149:
150: #ifdef PRECOMPUTE_SELECTORS
151: /* Transform soffset values to ints and vica verca */
152: static inline unsigned int
153: soffset_decode(sidx index)
154: {
155: union sofftype x;
156: x.idx = index;
157: #ifdef OBJC_SPARSE3
158: return x.off.eoffset
159: + (x.off.boffset*BUCKET_SIZE)
160: + (x.off.ioffset*INDEX_CAPACITY);
161: #else /* OBJC_SPARSE2 */
162: return x.off.eoffset + (x.off.boffset*BUCKET_SIZE);
163: #endif /* OBJC_SPARSE2 */
164: }
165:
166: static inline sidx
167: soffset_encode(size_t offset)
168: {
169: union sofftype x;
170: x.off.eoffset = offset%BUCKET_SIZE;
171: #ifdef OBJC_SPARSE3
172: x.off.boffset = (offset/BUCKET_SIZE)%INDEX_SIZE;
173: x.off.ioffset = offset/INDEX_CAPACITY;
174: #else /* OBJC_SPARSE2 */
175: x.off.boffset = offset/BUCKET_SIZE;
176: #endif
177: return (sidx)x.idx;
178: }
179:
180: #else /* not PRECOMPUTE_SELECTORS */
181:
182: static inline size_t
183: soffset_decode(sidx index)
184: {
185: return index;
186: }
187:
188: static inline sidx
189: soffset_encode(size_t offset)
190: {
191: return offset;
192: }
193: #endif /* not PRECOMPUTE_SELECTORS */
194:
195: /* Get element from the Sparse array `array' at offset `index' */
196:
197: static inline void* sarray_get(struct sarray* array, sidx index)
198: {
199: #ifdef PRECOMPUTE_SELECTORS
200: union sofftype x;
201: x.idx = index;
202: #ifdef OBJC_SPARSE3
203: return
204: array->
205: indices[x.off.ioffset]->
206: buckets[x.off.boffset]->
207: elems[x.off.eoffset];
208: #else /* OBJC_SPARSE2 */
209: return array->buckets[x.off.boffset]->elems[x.off.eoffset];
210: #endif /* OBJC_SPARSE2 */
211: #else /* not PRECOMPUTE_SELECTORS */
212: #ifdef OBJC_SPARSE3
213: return array->
214: indices[index/INDEX_CAPACITY]->
215: buckets[(index/BUCKET_SIZE)%INDEX_SIZE]->
216: elems[index%BUCKET_SIZE];
217: #else /* OBJC_SPARSE2 */
218: return array->buckets[index/BUCKET_SIZE]->elems[index%BUCKET_SIZE];
219: #endif /* not OBJC_SPARSE3 */
220: #endif /* not PRECOMPUTE_SELECTORS */
221: }
222:
223: static inline void* sarray_get_safe(struct sarray* array, sidx index)
224: {
225: if(soffset_decode(index) < array->capacity)
226: return sarray_get(array, index);
227: else
228: return (array->empty_bucket->elems[0]);
229: }
230:
231: #endif /* __sarray_INCLUDE_GNU */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.