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