![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to sarray.c 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.c 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: This file is part of GNU CC.
5:
6: GNU CC is free software; you can redistribute it and/or modify
7: it under the terms of the GNU General Public License as published by
8: the Free Software Foundation; either version 2, or (at your option)
9: any later version.
10:
11: GNU CC is distributed in the hope that it will be useful,
12: but WITHOUT ANY WARRANTY; without even the implied warranty of
13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14: GNU General Public License for more details.
15:
16: You should have received a copy of the GNU General Public License
17: along with GNU CC; see the file COPYING. If not, write to
18: the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
19:
20: /* As a special exception, if you link this library with files
21: compiled with GCC to produce an executable, this does not cause
22: the resulting executable to be covered by the GNU General Public License.
23: This exception does not however invalidate any other reasons why
24: the executable file might be covered by the GNU General Public License. */
25:
26: #include "objc/sarray.h"
27: #include <stdio.h>
28: #include "assert.h"
29:
30: int nbuckets = 0;
31: int nindices = 0;
32: int narrays = 0;
33: int idxsize = 0;
34:
35: #ifdef OBJC_SPARSE2
36: const char* __objc_sparse2_id = "2 level sparse indices";
37: #endif
38:
39: #ifdef OBJC_SPARSE3
40: const char* __objc_sparse3_id = "3 level sparse indices";
41: #endif
42:
43: #ifdef __alpha__
44: const void *memcpy (void*, const void*, size_t);
45: void free (const void*);
46: #endif
47:
48: void
49: sarray_at_put(struct sarray* array, sidx index, void* element)
50: {
51: #ifdef OBJC_SPARSE3
52: struct sindex** the_index;
53: #endif
54: struct sbucket** the_bucket;
55: #ifdef OBJC_SPARSE3
56: size_t ioffset;
57: #endif
58: size_t boffset;
59: size_t eoffset;
60: #ifdef PRECOMPUTE_SELECTORS
61: union sofftype xx;
62: xx.idx = index;
63: #ifdef OBJC_SPARSE3
64: ioffset = xx.off.ioffset;
65: #endif
66: boffset = xx.off.boffset;
67: eoffset = xx.off.eoffset;
68: #else /* not PRECOMPUTE_SELECTORS */
69: #ifdef OBJC_SPARSE3
70: ioffset = index/INDEX_CAPACITY;
71: boffset = (index/BUCKET_SIZE)%INDEX_SIZE;
72: eoffset = index%BUCKET_SIZE;
73: #else
74: boffset = index/BUCKET_SIZE;
75: eoffset = index%BUCKET_SIZE;
76: #endif
77: #endif /* not PRECOMPUTE_SELECTORS */
78:
79: assert(soffset_decode(index) < array->capacity); /* Range check */
80:
81: #ifdef OBJC_SPARSE3
82: the_index = &(array->indices[ioffset]);
83: the_bucket = &((*the_index)->buckets[boffset]);
84: #else
85: the_bucket = &(array->buckets[boffset]);
86: #endif
87:
88: if ((*the_bucket)->elems[eoffset] == element)
89: return; /* great! we just avoided a lazy copy */
90:
91: #ifdef OBJC_SPARSE3
92:
93: /* First, perform lazy copy/allocation of index if needed */
94:
95: if ((*the_index) == array->empty_index) {
96:
97: /* The index was previously empty, allocate a new */
98: *the_index = (struct sindex*)__objc_xmalloc(sizeof(struct sindex));
99: memcpy(*the_index, array->empty_index, sizeof(struct sindex));
100: (*the_index)->version = array->version;
101: the_bucket = &((*the_index)->buckets[boffset]);
102: nindices += 1;
103:
104: } else if ((*the_index)->version != array->version) {
105:
106: /* This index must be lazy copied */
107: struct sindex* old_index = *the_index;
108: *the_index = (struct sindex*)__objc_xmalloc(sizeof(struct sindex));
109: memcpy( *the_index,old_index, sizeof(struct sindex));
110: (*the_index)->version = array->version;
111: the_bucket = &((*the_index)->buckets[boffset]);
112: nindices += 1;
113:
114: }
115:
116: #endif /* OBJC_SPARSE3 */
117:
118: /* next, perform lazy allocation/copy of the bucket if needed */
119:
120: if ((*the_bucket) == array->empty_bucket) {
121:
122: /* The bucket was previously empty (or something like that), */
123: /* allocate a new. This is the effect of `lazy' allocation */
124: *the_bucket = (struct sbucket*)__objc_xmalloc(sizeof(struct sbucket));
125: memcpy((void *) *the_bucket, (const void*)array->empty_bucket, sizeof(struct sbucket));
126: (*the_bucket)->version = array->version;
127: nbuckets += 1;
128:
129: } else if ((*the_bucket)->version != array->version) {
130:
131: /* Perform lazy copy. */
132: struct sbucket* old_bucket = *the_bucket;
133: *the_bucket = (struct sbucket*)__objc_xmalloc(sizeof(struct sbucket));
134: memcpy( *the_bucket,old_bucket, sizeof(struct sbucket));
135: (*the_bucket)->version = array->version;
136: nbuckets += 1;
137:
138: }
139: (*the_bucket)->elems[eoffset] = element;
140: }
141:
142: void
143: sarray_at_put_safe(struct sarray* array, sidx index, void* element)
144: {
145: if(soffset_decode(index) >= array->capacity)
146: sarray_realloc(array, soffset_decode(index)+1);
147: sarray_at_put(array, index, element);
148: }
149:
150: struct sarray*
151: sarray_new (int size, void* default_element)
152: {
153: #ifdef OBJC_SPARSE3
154: size_t num_indices = ((size-1)/(INDEX_CAPACITY))+1;
155: #else /* OBJC_SPARSE2 */
156: size_t num_indices = ((size-1)/BUCKET_SIZE)+1;
157: #endif
158: int counter;
159: struct sarray* arr;
160:
161: assert(size > 0);
162:
163: /* Allocate core array */
164: arr = (struct sarray*) __objc_xmalloc(sizeof(struct sarray));
165: arr->version = 0;
166: narrays += 1;
167:
168: /* Initialize members */
169: #ifdef OBJC_SPARSE3
170: arr->capacity = num_indices*INDEX_CAPACITY;
171: arr->indices = (struct sindex**)
172: __objc_xmalloc(sizeof(struct sindex*)*num_indices);
173: idxsize += num_indices;
174:
175: arr->empty_index = (struct sindex*) __objc_xmalloc(sizeof(struct sindex));
176: arr->empty_index->version = 0;
177: nindices += 1;
178:
179: #else /* OBJC_SPARSE2 */
180: arr->capacity = num_indices*BUCKET_SIZE;
181: arr->buckets = (struct sbucket**)
182: __objc_xmalloc(sizeof(struct sbucket*)*num_indices);
183: idxsize += num_indices;
184:
185: #endif
186:
187: arr->empty_bucket = (struct sbucket*) __objc_xmalloc(sizeof(struct sbucket));
188: arr->empty_bucket->version = 0;
189: nbuckets += 1;
190:
191: arr->ref_count = 1;
192: arr->is_copy_of = (struct sarray*)0;
193:
194: for (counter=0; counter<BUCKET_SIZE; counter++)
195: arr->empty_bucket->elems[counter] = default_element;
196:
197: #ifdef OBJC_SPARSE3
198: for (counter=0; counter<INDEX_SIZE; counter++)
199: arr->empty_index->buckets[counter] = arr->empty_bucket;
200:
201: for (counter=0; counter<num_indices; counter++)
202: arr->indices[counter] = arr->empty_index;
203:
204: #else /* OBJC_SPARSE2 */
205:
206: for (counter=0; counter<num_indices; counter++)
207: arr->buckets[counter] = arr->empty_bucket;
208:
209: #endif
210:
211: return arr;
212: }
213:
214:
215: /* Reallocate the sparse array to hold `newsize' entries */
216:
217: void
218: sarray_realloc(struct sarray* array, int newsize)
219: {
220: #ifdef OBJC_SPARSE3
221: int old_max_index = (array->capacity-1)/INDEX_CAPACITY;
222: int new_max_index = ((newsize-1)/INDEX_CAPACITY);
223: int rounded_size = (new_max_index+1)*INDEX_CAPACITY;
224:
225: #else /* OBJC_SPARSE2 */
226: int old_max_index = (array->capacity-1)/BUCKET_SIZE;
227: int new_max_index = ((newsize-1)/BUCKET_SIZE);
228: int rounded_size = (new_max_index+1)*BUCKET_SIZE;
229:
230: #endif
231:
232: int counter;
233:
234: assert(newsize > 0);
235:
236: /* The size is the same, just ignore the request */
237: if(rounded_size == array->capacity)
238: return;
239:
240: assert(array->ref_count == 1); /* stop if lazy copied... */
241:
242: if(rounded_size < array->capacity)
243: {
244: /* update capacity */
245: array->capacity = rounded_size;
246:
247: /* free buckets above new_max_index */
248: for(counter = old_max_index; counter > new_max_index; counter-- ) {
249: #ifdef OBJC_SPARSE3
250: struct sindex* idx = array->indices[counter];
251: if((idx != array->empty_index) && (idx->version == array->version)) {
252: int c2;
253: for(c2=0; c2<INDEX_SIZE; c2++) {
254: struct sbucket* bkt = idx->buckets[c2];
255: if((bkt != array->empty_bucket) && (bkt->version == array->version))
256: {
257: free(bkt);
258: nbuckets -= 1;
259: }
260: }
261: free(idx);
262: nindices -= 1;
263: }
264: #else /* OBJC_SPARSE2 */
265: struct sbucket* bkt = array->buckets[counter];
266: if ((bkt != array->empty_bucket) && (bkt->version == array->version))
267: {
268: free(bkt);
269: nbuckets -= 1;
270: }
271: #endif
272: }
273:
274: #ifdef OBJC_SPARSE3
275: /* realloc to free the space above new_max_index */
276: array->indices = (struct sindex**)
277: __objc_xrealloc(array->indices,
278: (new_max_index+1)*sizeof(struct sindex*));
279: #else /* OBJC_SPARSE2 */
280: array->buckets = (struct sbucket**)
281: __objc_xrealloc(array->buckets,
282: (new_max_index+1)*sizeof(struct sbucket*));
283: #endif
284: idxsize -= (old_max_index-new_max_index);
285:
286: return;
287: }
288:
289: /* We are asked to extend the array -- reallocate the bucket table, */
290: /* and insert empty_bucket in newly allocated places. */
291: if(rounded_size > array->capacity)
292: {
293: /* update capacity */
294: array->capacity = rounded_size;
295:
296: #ifdef OBJC_SPARSE3
297: /* realloc to make room in table above old_max_index */
298: array->indices = (struct sindex**)
299: __objc_xrealloc(array->indices,
300: (new_max_index+1)*sizeof(struct sindex*));
301:
302: /* reset entries above old_max_index to empty_bucket */
303: for(counter = old_max_index+1; counter <= new_max_index; counter++)
304: array->indices[counter] = array->empty_index;
305:
306: #else /* OBJC_SPARSE2 */
307:
308: /* realloc to make room in table above old_max_index */
309: array->buckets = (struct sbucket**)
310: __objc_xrealloc(array->buckets,
311: (new_max_index+1)*sizeof(struct sbucket*));
312:
313: /* reset entries above old_max_index to empty_bucket */
314: for(counter = old_max_index+1; counter <= new_max_index; counter++)
315: array->buckets[counter] = array->empty_bucket;
316:
317: #endif
318: idxsize += (new_max_index-old_max_index);
319: return;
320: }
321: }
322:
323:
324: /* Free a sparse array allocated with sarray_new */
325:
326: void
327: sarray_free(struct sarray* array) {
328: #ifdef OBJC_SPARSE3
329: size_t old_max_index = (array->capacity-1)/INDEX_CAPACITY;
330: #else
331: size_t old_max_index = (array->capacity-1)/BUCKET_SIZE;
332: #endif
333: int counter = 0;
334:
335: assert(array->ref_count != 0); /* Freed multiple times!!! */
336:
337: if(--(array->ref_count) != 0) /* There exists copies of me */
338: return;
339:
340: if((array->is_copy_of) && ((array->is_copy_of->ref_count - 1) == 0))
341: sarray_free(array->is_copy_of);
342:
343: /* Free all entries that do not point to empty_bucket */
344: for(counter = 0; counter <= old_max_index; counter++ ) {
345: #ifdef OBJC_SPARSE3
346: struct sindex* idx = array->indices[counter];
347: if((idx != array->empty_index) && (idx->version == array->version)) {
348: int c2;
349: for(c2=0; c2<INDEX_SIZE; c2++) {
350: struct sbucket* bkt = idx->buckets[c2];
351: if((bkt != array->empty_bucket) && (bkt->version == array->version))
352: {
353: free(bkt);
354: nbuckets -= 1;
355: }
356: }
357: free(idx);
358: nindices -= 1;
359: }
360: #else /* OBJC_SPARSE2 */
361: struct sbucket* bkt = array->buckets[counter];
362: if ((bkt != array->empty_bucket) && (bkt->version == array->version))
363: {
364: free(bkt);
365: nbuckets -= 1;
366: }
367: #endif
368: }
369:
370: #ifdef OBJC_SPARSE3
371: /* free empty_index */
372: if(array->empty_index->version == array->version) {
373: free(array->empty_index);
374: nindices -= 1;
375: }
376: #endif
377:
378: /* free empty_bucket */
379: if(array->empty_bucket->version == array->version) {
380: free(array->empty_bucket);
381: nbuckets -= 1;
382: }
383:
384: #ifdef OBJC_SPARSE3
385: /* free bucket table */
386: free(array->indices);
387: idxsize -= (old_max_index+1);
388:
389: #else
390: /* free bucket table */
391: free(array->buckets);
392: idxsize -= (old_max_index+1);
393:
394: #endif
395:
396: /* free array */
397: free(array);
398: narrays -= 1;
399: }
400:
401: /* This is a lazy copy. Only the core of the structure is actually */
402: /* copied. */
403:
404: struct sarray*
405: sarray_lazy_copy(struct sarray* oarr)
406: {
407: #ifdef OBJC_SPARSE3
408: size_t num_indices = ((oarr->capacity-1)/INDEX_CAPACITY)+1;
409: #else /* OBJC_SPARSE2 */
410: size_t num_indices = ((oarr->capacity-1)/BUCKET_SIZE)+1;
411: #endif
412: struct sarray* arr;
413:
414: /* Allocate core array */
415: arr = (struct sarray*) __objc_xmalloc(sizeof(struct sarray));
416: memcpy( arr,oarr, sizeof(struct sarray));
417: arr->version = oarr->version + 1;
418: arr->is_copy_of = oarr;
419: oarr->ref_count += 1;
420: arr->ref_count = 1;
421:
422: #ifdef OBJC_SPARSE3
423: /* Copy bucket table */
424: arr->indices = (struct sindex**)
425: __objc_xmalloc(sizeof(struct sindex*)*num_indices);
426: memcpy( arr->indices,oarr->indices,
427: sizeof(struct sindex*)*num_indices);
428: #else
429: /* Copy bucket table */
430: arr->buckets = (struct sbucket**)
431: __objc_xmalloc(sizeof(struct sbucket*)*num_indices);
432: memcpy( arr->buckets,oarr->buckets,
433: sizeof(struct sbucket*)*num_indices);
434: #endif
435:
436: idxsize += num_indices;
437: narrays += 1;
438:
439: return arr;
440: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.