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