1 /* Sparse Arrays for Objective C dispatch tables 2 Copyright (C) 1993, 1995, 1996, 2002, 2004, 2009 Free Software Foundation, Inc. 3 4 This file is part of GCC. 5 6 GCC 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 3, or (at your option) 9 any later version. 10 11 GCC 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 Under Section 7 of GPL version 3, you are granted additional 17 permissions described in the GCC Runtime Library Exception, version 18 3.1, as published by the Free Software Foundation. 19 20 You should have received a copy of the GNU General Public License and 21 a copy of the GCC Runtime Library Exception along with this program; 22 see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 <http://www.gnu.org/licenses/>. */ 24 25 26 #include "objc/sarray.h" 27 #include "objc/runtime.h" 28 #include <stdio.h> 29 #include "assert.h" 30 31 int nbuckets = 0; /* !T:MUTEX */ 32 int nindices = 0; /* !T:MUTEX */ 33 int narrays = 0; /* !T:MUTEX */ 34 int idxsize = 0; /* !T:MUTEX */ 35 36 static void *first_free_data = NULL; /* !T:MUTEX */ 37 38 #ifdef OBJC_SPARSE2 39 const char *__objc_sparse2_id = "2 level sparse indices"; 40 #endif 41 42 #ifdef OBJC_SPARSE3 43 const char *__objc_sparse3_id = "3 level sparse indices"; 44 #endif 45 46 /* This function removes any structures left over from free operations 47 that were not safe in a multi-threaded environment. */ 48 void 49 sarray_remove_garbage (void) 50 { 51 void **vp; 52 void *np; 53 54 objc_mutex_lock (__objc_runtime_mutex); 55 56 vp = first_free_data; 57 first_free_data = NULL; 58 59 while (vp) { 60 np = *vp; 61 objc_free (vp); 62 vp = np; 63 } 64 65 objc_mutex_unlock (__objc_runtime_mutex); 66 } 67 68 /* Free a block of dynamically allocated memory. If we are in multi-threaded 69 mode, it is ok to free it. If not, we add it to the garbage heap to be 70 freed later. */ 71 72 static void 73 sarray_free_garbage (void *vp) 74 { 75 objc_mutex_lock (__objc_runtime_mutex); 76 77 if (__objc_runtime_threads_alive == 1) { 78 objc_free (vp); 79 if (first_free_data) 80 sarray_remove_garbage (); 81 } 82 else { 83 *(void **)vp = first_free_data; 84 first_free_data = vp; 85 } 86 87 objc_mutex_unlock (__objc_runtime_mutex); 88 } 89 90 /* sarray_at_put : copies data in such a way as to be thread reader safe. */ 91 void 92 sarray_at_put (struct sarray *array, sidx index, void *element) 93 { 94 #ifdef OBJC_SPARSE3 95 struct sindex **the_index; 96 struct sindex *new_index; 97 #endif 98 struct sbucket **the_bucket; 99 struct sbucket *new_bucket; 100 #ifdef OBJC_SPARSE3 101 size_t ioffset; 102 #endif 103 size_t boffset; 104 size_t eoffset; 105 #ifdef PRECOMPUTE_SELECTORS 106 union sofftype xx; 107 xx.idx = index; 108 #ifdef OBJC_SPARSE3 109 ioffset = xx.off.ioffset; 110 #endif 111 boffset = xx.off.boffset; 112 eoffset = xx.off.eoffset; 113 #else /* not PRECOMPUTE_SELECTORS */ 114 #ifdef OBJC_SPARSE3 115 ioffset = index/INDEX_CAPACITY; 116 boffset = (index/BUCKET_SIZE)%INDEX_SIZE; 117 eoffset = index%BUCKET_SIZE; 118 #else 119 boffset = index/BUCKET_SIZE; 120 eoffset = index%BUCKET_SIZE; 121 #endif 122 #endif /* not PRECOMPUTE_SELECTORS */ 123 124 assert (soffset_decode (index) < array->capacity); /* Range check */ 125 126 #ifdef OBJC_SPARSE3 127 the_index = &(array->indices[ioffset]); 128 the_bucket = &((*the_index)->buckets[boffset]); 129 #else 130 the_bucket = &(array->buckets[boffset]); 131 #endif 132 133 if ((*the_bucket)->elems[eoffset] == element) 134 return; /* great! we just avoided a lazy copy */ 135 136 #ifdef OBJC_SPARSE3 137 138 /* First, perform lazy copy/allocation of index if needed */ 139 140 if ((*the_index) == array->empty_index) { 141 142 /* The index was previously empty, allocate a new */ 143 new_index = (struct sindex *) objc_malloc (sizeof (struct sindex)); 144 memcpy (new_index, array->empty_index, sizeof (struct sindex)); 145 new_index->version.version = array->version.version; 146 *the_index = new_index; /* Prepared for install. */ 147 the_bucket = &((*the_index)->buckets[boffset]); 148 149 nindices += 1; 150 } else if ((*the_index)->version.version != array->version.version) { 151 152 /* This index must be lazy copied */ 153 struct sindex *old_index = *the_index; 154 new_index = (struct sindex *) objc_malloc (sizeof (struct sindex)); 155 memcpy (new_index, old_index, sizeof (struct sindex)); 156 new_index->version.version = array->version.version; 157 *the_index = new_index; /* Prepared for install. */ 158 the_bucket = &((*the_index)->buckets[boffset]); 159 160 nindices += 1; 161 } 162 163 #endif /* OBJC_SPARSE3 */ 164 165 /* next, perform lazy allocation/copy of the bucket if needed */ 166 167 if ((*the_bucket) == array->empty_bucket) { 168 169 /* The bucket was previously empty (or something like that), */ 170 /* allocate a new. This is the effect of `lazy' allocation */ 171 new_bucket = (struct sbucket *) objc_malloc (sizeof (struct sbucket)); 172 memcpy ((void *) new_bucket, (const void *) array->empty_bucket, 173 sizeof (struct sbucket)); 174 new_bucket->version.version = array->version.version; 175 *the_bucket = new_bucket; /* Prepared for install. */ 176 177 nbuckets += 1; 178 179 } else if ((*the_bucket)->version.version != array->version.version) { 180 181 /* Perform lazy copy. */ 182 struct sbucket *old_bucket = *the_bucket; 183 new_bucket = (struct sbucket *) objc_malloc (sizeof (struct sbucket)); 184 memcpy (new_bucket, old_bucket, sizeof (struct sbucket)); 185 new_bucket->version.version = array->version.version; 186 *the_bucket = new_bucket; /* Prepared for install. */ 187 188 nbuckets += 1; 189 190 } 191 (*the_bucket)->elems[eoffset] = element; 192 } 193 194 void 195 sarray_at_put_safe (struct sarray *array, sidx index, void *element) 196 { 197 if (soffset_decode (index) >= array->capacity) 198 sarray_realloc (array, soffset_decode (index) + 1); 199 sarray_at_put (array, index, element); 200 } 201 202 struct sarray * 203 sarray_new (int size, void *default_element) 204 { 205 struct sarray *arr; 206 #ifdef OBJC_SPARSE3 207 size_t num_indices = ((size - 1)/(INDEX_CAPACITY)) + 1; 208 struct sindex **new_indices; 209 #else /* OBJC_SPARSE2 */ 210 size_t num_indices = ((size - 1)/BUCKET_SIZE) + 1; 211 struct sbucket **new_buckets; 212 #endif 213 size_t counter; 214 215 assert (size > 0); 216 217 /* Allocate core array */ 218 arr = (struct sarray *) objc_malloc (sizeof (struct sarray)); 219 arr->version.version = 0; 220 221 /* Initialize members */ 222 #ifdef OBJC_SPARSE3 223 arr->capacity = num_indices*INDEX_CAPACITY; 224 new_indices = (struct sindex **) 225 objc_malloc (sizeof (struct sindex *) * num_indices); 226 227 arr->empty_index = (struct sindex *) objc_malloc (sizeof (struct sindex)); 228 arr->empty_index->version.version = 0; 229 230 narrays += 1; 231 idxsize += num_indices; 232 nindices += 1; 233 234 #else /* OBJC_SPARSE2 */ 235 arr->capacity = num_indices*BUCKET_SIZE; 236 new_buckets = (struct sbucket **) 237 objc_malloc (sizeof (struct sbucket *) * num_indices); 238 239 narrays += 1; 240 idxsize += num_indices; 241 242 #endif 243 244 arr->empty_bucket = (struct sbucket *) objc_malloc (sizeof (struct sbucket)); 245 arr->empty_bucket->version.version = 0; 246 247 nbuckets += 1; 248 249 arr->ref_count = 1; 250 arr->is_copy_of = (struct sarray *) 0; 251 252 for (counter = 0; counter < BUCKET_SIZE; counter++) 253 arr->empty_bucket->elems[counter] = default_element; 254 255 #ifdef OBJC_SPARSE3 256 for (counter = 0; counter < INDEX_SIZE; counter++) 257 arr->empty_index->buckets[counter] = arr->empty_bucket; 258 259 for (counter = 0; counter < num_indices; counter++) 260 new_indices[counter] = arr->empty_index; 261 262 #else /* OBJC_SPARSE2 */ 263 264 for (counter = 0; counter < num_indices; counter++) 265 new_buckets[counter] = arr->empty_bucket; 266 267 #endif 268 269 #ifdef OBJC_SPARSE3 270 arr->indices = new_indices; 271 #else /* OBJC_SPARSE2 */ 272 arr->buckets = new_buckets; 273 #endif 274 275 return arr; 276 } 277 278 279 /* Reallocate the sparse array to hold `newsize' entries 280 Note: We really allocate and then free. We have to do this to ensure that 281 any concurrent readers notice the update. */ 282 283 void 284 sarray_realloc (struct sarray *array, int newsize) 285 { 286 #ifdef OBJC_SPARSE3 287 size_t old_max_index = (array->capacity - 1)/INDEX_CAPACITY; 288 size_t new_max_index = ((newsize - 1)/INDEX_CAPACITY); 289 size_t rounded_size = (new_max_index + 1) * INDEX_CAPACITY; 290 291 struct sindex **new_indices; 292 struct sindex **old_indices; 293 294 #else /* OBJC_SPARSE2 */ 295 size_t old_max_index = (array->capacity - 1)/BUCKET_SIZE; 296 size_t new_max_index = ((newsize - 1)/BUCKET_SIZE); 297 size_t rounded_size = (new_max_index + 1) * BUCKET_SIZE; 298 299 struct sbucket **new_buckets; 300 struct sbucket **old_buckets; 301 302 #endif 303 304 size_t counter; 305 306 assert (newsize > 0); 307 308 /* The size is the same, just ignore the request */ 309 if (rounded_size <= array->capacity) 310 return; 311 312 assert (array->ref_count == 1); /* stop if lazy copied... */ 313 314 /* We are asked to extend the array -- allocate new bucket table, */ 315 /* and insert empty_bucket in newly allocated places. */ 316 if (rounded_size > array->capacity) 317 { 318 319 #ifdef OBJC_SPARSE3 320 new_max_index += 4; 321 rounded_size = (new_max_index + 1) * INDEX_CAPACITY; 322 323 #else /* OBJC_SPARSE2 */ 324 new_max_index += 4; 325 rounded_size = (new_max_index + 1) * BUCKET_SIZE; 326 #endif 327 328 /* update capacity */ 329 array->capacity = rounded_size; 330 331 #ifdef OBJC_SPARSE3 332 /* alloc to force re-read by any concurrent readers. */ 333 old_indices = array->indices; 334 new_indices = (struct sindex **) 335 objc_malloc ((new_max_index + 1) * sizeof (struct sindex *)); 336 #else /* OBJC_SPARSE2 */ 337 old_buckets = array->buckets; 338 new_buckets = (struct sbucket **) 339 objc_malloc ((new_max_index + 1) * sizeof (struct sbucket *)); 340 #endif 341 342 /* copy buckets below old_max_index (they are still valid) */ 343 for (counter = 0; counter <= old_max_index; counter++ ) { 344 #ifdef OBJC_SPARSE3 345 new_indices[counter] = old_indices[counter]; 346 #else /* OBJC_SPARSE2 */ 347 new_buckets[counter] = old_buckets[counter]; 348 #endif 349 } 350 351 #ifdef OBJC_SPARSE3 352 /* reset entries above old_max_index to empty_bucket */ 353 for (counter = old_max_index + 1; counter <= new_max_index; counter++) 354 new_indices[counter] = array->empty_index; 355 #else /* OBJC_SPARSE2 */ 356 /* reset entries above old_max_index to empty_bucket */ 357 for (counter = old_max_index + 1; counter <= new_max_index; counter++) 358 new_buckets[counter] = array->empty_bucket; 359 #endif 360 361 #ifdef OBJC_SPARSE3 362 /* install the new indices */ 363 array->indices = new_indices; 364 #else /* OBJC_SPARSE2 */ 365 array->buckets = new_buckets; 366 #endif 367 368 #ifdef OBJC_SPARSE3 369 /* free the old indices */ 370 sarray_free_garbage (old_indices); 371 #else /* OBJC_SPARSE2 */ 372 sarray_free_garbage (old_buckets); 373 #endif 374 375 idxsize += (new_max_index-old_max_index); 376 return; 377 } 378 } 379 380 381 /* Free a sparse array allocated with sarray_new */ 382 383 void 384 sarray_free (struct sarray *array) { 385 #ifdef OBJC_SPARSE3 386 size_t old_max_index = (array->capacity - 1)/INDEX_CAPACITY; 387 struct sindex **old_indices; 388 #else 389 size_t old_max_index = (array->capacity - 1)/BUCKET_SIZE; 390 struct sbucket **old_buckets; 391 #endif 392 size_t counter = 0; 393 394 assert (array->ref_count != 0); /* Freed multiple times!!! */ 395 396 if (--(array->ref_count) != 0) /* There exists copies of me */ 397 return; 398 399 #ifdef OBJC_SPARSE3 400 old_indices = array->indices; 401 #else 402 old_buckets = array->buckets; 403 #endif 404 405 /* Free all entries that do not point to empty_bucket */ 406 for (counter = 0; counter <= old_max_index; counter++ ) { 407 #ifdef OBJC_SPARSE3 408 struct sindex *idx = old_indices[counter]; 409 if ((idx != array->empty_index) && 410 (idx->version.version == array->version.version)) { 411 int c2; 412 for (c2 = 0; c2 < INDEX_SIZE; c2++) { 413 struct sbucket *bkt = idx->buckets[c2]; 414 if ((bkt != array->empty_bucket) && 415 (bkt->version.version == array->version.version)) 416 { 417 sarray_free_garbage (bkt); 418 nbuckets -= 1; 419 } 420 } 421 sarray_free_garbage (idx); 422 nindices -= 1; 423 } 424 #else /* OBJC_SPARSE2 */ 425 struct sbucket *bkt = old_buckets[counter]; 426 if ((bkt != array->empty_bucket) && 427 (bkt->version.version == array->version.version)) 428 { 429 sarray_free_garbage (bkt); 430 nbuckets -= 1; 431 } 432 #endif 433 } 434 435 #ifdef OBJC_SPARSE3 436 /* free empty_index */ 437 if (array->empty_index->version.version == array->version.version) { 438 sarray_free_garbage (array->empty_index); 439 nindices -= 1; 440 } 441 #endif 442 443 /* free empty_bucket */ 444 if (array->empty_bucket->version.version == array->version.version) { 445 sarray_free_garbage (array->empty_bucket); 446 nbuckets -= 1; 447 } 448 idxsize -= (old_max_index + 1); 449 narrays -= 1; 450 451 #ifdef OBJC_SPARSE3 452 /* free bucket table */ 453 sarray_free_garbage (array->indices); 454 455 #else 456 /* free bucket table */ 457 sarray_free_garbage (array->buckets); 458 459 #endif 460 461 /* If this is a copy of another array, we free it (which might just 462 * decrement its reference count so it will be freed when no longer in use). 463 */ 464 if (array->is_copy_of) 465 sarray_free (array->is_copy_of); 466 467 /* free array */ 468 sarray_free_garbage (array); 469 } 470 471 /* This is a lazy copy. Only the core of the structure is actually */ 472 /* copied. */ 473 474 struct sarray * 475 sarray_lazy_copy (struct sarray *oarr) 476 { 477 struct sarray *arr; 478 479 #ifdef OBJC_SPARSE3 480 size_t num_indices = ((oarr->capacity - 1)/INDEX_CAPACITY) + 1; 481 struct sindex **new_indices; 482 #else /* OBJC_SPARSE2 */ 483 size_t num_indices = ((oarr->capacity - 1)/BUCKET_SIZE) + 1; 484 struct sbucket **new_buckets; 485 #endif 486 487 /* Allocate core array */ 488 arr = (struct sarray *) objc_malloc (sizeof (struct sarray)); /* !!! */ 489 arr->version.version = oarr->version.version + 1; 490 #ifdef OBJC_SPARSE3 491 arr->empty_index = oarr->empty_index; 492 #endif 493 arr->empty_bucket = oarr->empty_bucket; 494 arr->ref_count = 1; 495 oarr->ref_count += 1; 496 arr->is_copy_of = oarr; 497 arr->capacity = oarr->capacity; 498 499 #ifdef OBJC_SPARSE3 500 /* Copy bucket table */ 501 new_indices = (struct sindex **) 502 objc_malloc (sizeof (struct sindex *) * num_indices); 503 memcpy (new_indices, oarr->indices, sizeof (struct sindex *) * num_indices); 504 arr->indices = new_indices; 505 #else 506 /* Copy bucket table */ 507 new_buckets = (struct sbucket **) 508 objc_malloc (sizeof (struct sbucket *) * num_indices); 509 memcpy (new_buckets, oarr->buckets, sizeof (struct sbucket *) * num_indices); 510 arr->buckets = new_buckets; 511 #endif 512 513 idxsize += num_indices; 514 narrays += 1; 515 516 return arr; 517 } 518