Daily bump.
[official-gcc.git] / libobjc / sarray.c
blobbd2e09bd2428650704018abb9581673dcbc0dc41
1 /* Sparse Arrays for Objective C dispatch tables
2 Copyright (C) 1993-2021 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
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.
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/>. */
25 #include "objc-private/common.h"
26 #include "objc-private/sarray.h"
27 #include "objc/runtime.h" /* For objc_malloc */
28 #include "objc/thr.h" /* For objc_mutex_lock */
29 #include "objc-private/module-abi-8.h"
30 #include "objc-private/runtime.h"
31 #include <stdio.h>
32 #include <string.h> /* For memset */
33 #include <assert.h> /* For assert */
35 int nbuckets = 0; /* !T:MUTEX */
36 int nindices = 0; /* !T:MUTEX */
37 int narrays = 0; /* !T:MUTEX */
38 int idxsize = 0; /* !T:MUTEX */
40 static void *first_free_data = NULL; /* !T:MUTEX */
42 #ifdef OBJC_SPARSE2
43 const char *__objc_sparse2_id = "2 level sparse indices";
44 #endif
46 #ifdef OBJC_SPARSE3
47 const char *__objc_sparse3_id = "3 level sparse indices";
48 #endif
50 /* This function removes any structures left over from free operations
51 that were not safe in a multi-threaded environment. */
52 void
53 sarray_remove_garbage (void)
55 void **vp;
56 void *np;
58 objc_mutex_lock (__objc_runtime_mutex);
60 vp = first_free_data;
61 first_free_data = NULL;
63 while (vp)
65 np = *vp;
66 objc_free (vp);
67 vp = np;
70 objc_mutex_unlock (__objc_runtime_mutex);
73 /* Free a block of dynamically allocated memory. If we are in
74 multi-threaded mode, it is ok to free it. If not, we add it to the
75 garbage heap to be freed later. */
76 static void
77 sarray_free_garbage (void *vp)
79 objc_mutex_lock (__objc_runtime_mutex);
81 if (__objc_runtime_threads_alive == 1)
83 objc_free (vp);
84 if (first_free_data)
85 sarray_remove_garbage ();
87 else
89 *(void **)vp = first_free_data;
90 first_free_data = vp;
93 objc_mutex_unlock (__objc_runtime_mutex);
96 /* sarray_at_put copies data in such a way as to be thread reader
97 safe. */
98 void
99 sarray_at_put (struct sarray *array, sidx index, void *element)
101 #ifdef OBJC_SPARSE3
102 struct sindex **the_index;
103 struct sindex *new_index;
104 #endif
105 struct sbucket **the_bucket;
106 struct sbucket *new_bucket;
107 #ifdef OBJC_SPARSE3
108 size_t ioffset;
109 #endif
110 size_t boffset;
111 size_t eoffset;
112 #ifdef PRECOMPUTE_SELECTORS
113 union sofftype xx;
114 xx.idx = index;
115 #ifdef OBJC_SPARSE3
116 ioffset = xx.off.ioffset;
117 #endif
118 boffset = xx.off.boffset;
119 eoffset = xx.off.eoffset;
120 #else /* not PRECOMPUTE_SELECTORS */
121 #ifdef OBJC_SPARSE3
122 ioffset = index/INDEX_CAPACITY;
123 boffset = (index/BUCKET_SIZE)%INDEX_SIZE;
124 eoffset = index%BUCKET_SIZE;
125 #else
126 boffset = index/BUCKET_SIZE;
127 eoffset = index%BUCKET_SIZE;
128 #endif
129 #endif /* not PRECOMPUTE_SELECTORS */
131 assert (soffset_decode (index) < array->capacity); /* Range check */
133 #ifdef OBJC_SPARSE3
134 the_index = &(array->indices[ioffset]);
135 the_bucket = &((*the_index)->buckets[boffset]);
136 #else
137 the_bucket = &(array->buckets[boffset]);
138 #endif
140 if ((*the_bucket)->elems[eoffset] == element)
141 return; /* Great! we just avoided a lazy copy. */
143 #ifdef OBJC_SPARSE3
145 /* First, perform lazy copy/allocation of index if needed. */
147 if ((*the_index) == array->empty_index)
149 /* The index was previously empty, allocate a new. */
150 new_index = (struct sindex *) objc_malloc (sizeof (struct sindex));
151 memcpy (new_index, array->empty_index, sizeof (struct sindex));
152 new_index->version.version = array->version.version;
153 *the_index = new_index; /* Prepared for install. */
154 the_bucket = &((*the_index)->buckets[boffset]);
156 nindices += 1;
158 else if ((*the_index)->version.version != array->version.version)
160 /* This index must be lazy copied. */
161 struct sindex *old_index = *the_index;
162 new_index = (struct sindex *) objc_malloc (sizeof (struct sindex));
163 memcpy (new_index, old_index, sizeof (struct sindex));
164 new_index->version.version = array->version.version;
165 *the_index = new_index; /* Prepared for install. */
166 the_bucket = &((*the_index)->buckets[boffset]);
168 nindices += 1;
171 #endif /* OBJC_SPARSE3 */
173 /* Next, perform lazy allocation/copy of the bucket if needed. */
174 if ((*the_bucket) == array->empty_bucket)
176 /* The bucket was previously empty (or something like that),
177 allocate a new. This is the effect of `lazy' allocation. */
178 new_bucket = (struct sbucket *) objc_malloc (sizeof (struct sbucket));
179 memcpy ((void *) new_bucket, (const void *) array->empty_bucket,
180 sizeof (struct sbucket));
181 new_bucket->version.version = array->version.version;
182 *the_bucket = new_bucket; /* Prepared for install. */
184 nbuckets += 1;
187 else if ((*the_bucket)->version.version != array->version.version)
189 /* Perform lazy copy. */
190 struct sbucket *old_bucket = *the_bucket;
191 new_bucket = (struct sbucket *) objc_malloc (sizeof (struct sbucket));
192 memcpy (new_bucket, old_bucket, sizeof (struct sbucket));
193 new_bucket->version.version = array->version.version;
194 *the_bucket = new_bucket; /* Prepared for install. */
196 nbuckets += 1;
198 (*the_bucket)->elems[eoffset] = element;
201 void
202 sarray_at_put_safe (struct sarray *array, sidx index, void *element)
204 if (soffset_decode (index) >= array->capacity)
205 sarray_realloc (array, soffset_decode (index) + 1);
206 sarray_at_put (array, index, element);
209 struct sarray *
210 sarray_new (int size, void *default_element)
212 struct sarray *arr;
213 #ifdef OBJC_SPARSE3
214 size_t num_indices = ((size - 1)/(INDEX_CAPACITY)) + 1;
215 struct sindex **new_indices;
216 #else /* OBJC_SPARSE2 */
217 size_t num_indices = ((size - 1)/BUCKET_SIZE) + 1;
218 struct sbucket **new_buckets;
219 #endif
220 size_t counter;
222 assert (size > 0);
224 /* Allocate core array. */
225 arr = (struct sarray *) objc_malloc (sizeof (struct sarray));
226 arr->version.version = 0;
228 /* Initialize members. */
229 #ifdef OBJC_SPARSE3
230 arr->capacity = num_indices*INDEX_CAPACITY;
231 new_indices = (struct sindex **)
232 objc_malloc (sizeof (struct sindex *) * num_indices);
234 arr->empty_index = (struct sindex *) objc_malloc (sizeof (struct sindex));
235 arr->empty_index->version.version = 0;
237 narrays += 1;
238 idxsize += num_indices;
239 nindices += 1;
241 #else /* OBJC_SPARSE2 */
242 arr->capacity = num_indices*BUCKET_SIZE;
243 new_buckets = (struct sbucket **)
244 objc_malloc (sizeof (struct sbucket *) * num_indices);
246 narrays += 1;
247 idxsize += num_indices;
249 #endif
251 arr->empty_bucket = (struct sbucket *) objc_malloc (sizeof (struct sbucket));
252 arr->empty_bucket->version.version = 0;
254 nbuckets += 1;
256 arr->ref_count = 1;
257 arr->is_copy_of = (struct sarray *) 0;
259 for (counter = 0; counter < BUCKET_SIZE; counter++)
260 arr->empty_bucket->elems[counter] = default_element;
262 #ifdef OBJC_SPARSE3
263 for (counter = 0; counter < INDEX_SIZE; counter++)
264 arr->empty_index->buckets[counter] = arr->empty_bucket;
266 for (counter = 0; counter < num_indices; counter++)
267 new_indices[counter] = arr->empty_index;
269 #else /* OBJC_SPARSE2 */
271 for (counter = 0; counter < num_indices; counter++)
272 new_buckets[counter] = arr->empty_bucket;
274 #endif
276 #ifdef OBJC_SPARSE3
277 arr->indices = new_indices;
278 #else /* OBJC_SPARSE2 */
279 arr->buckets = new_buckets;
280 #endif
282 return arr;
286 /* Reallocate the sparse array to hold `newsize' entries Note: We
287 really allocate and then free. We have to do this to ensure that
288 any concurrent readers notice the update. */
289 void
290 sarray_realloc (struct sarray *array, int newsize)
292 #ifdef OBJC_SPARSE3
293 size_t old_max_index = (array->capacity - 1)/INDEX_CAPACITY;
294 size_t new_max_index = ((newsize - 1)/INDEX_CAPACITY);
295 size_t rounded_size = (new_max_index + 1) * INDEX_CAPACITY;
297 struct sindex **new_indices;
298 struct sindex **old_indices;
300 #else /* OBJC_SPARSE2 */
301 size_t old_max_index = (array->capacity - 1)/BUCKET_SIZE;
302 size_t new_max_index = ((newsize - 1)/BUCKET_SIZE);
303 size_t rounded_size = (new_max_index + 1) * BUCKET_SIZE;
305 struct sbucket **new_buckets;
306 struct sbucket **old_buckets;
308 #endif
310 size_t counter;
312 assert (newsize > 0);
314 /* The size is the same, just ignore the request. */
315 if (rounded_size <= array->capacity)
316 return;
318 assert (array->ref_count == 1); /* stop if lazy copied... */
320 /* We are asked to extend the array -- allocate new bucket table,
321 and insert empty_bucket in newly allocated places. */
322 if (rounded_size > array->capacity)
324 #ifdef OBJC_SPARSE3
325 new_max_index += 4;
326 rounded_size = (new_max_index + 1) * INDEX_CAPACITY;
327 #else /* OBJC_SPARSE2 */
328 new_max_index += 4;
329 rounded_size = (new_max_index + 1) * BUCKET_SIZE;
330 #endif
332 /* Update capacity. */
333 array->capacity = rounded_size;
335 #ifdef OBJC_SPARSE3
336 /* Alloc to force re-read by any concurrent readers. */
337 old_indices = array->indices;
338 new_indices = (struct sindex **)
339 objc_malloc ((new_max_index + 1) * sizeof (struct sindex *));
340 #else /* OBJC_SPARSE2 */
341 old_buckets = array->buckets;
342 new_buckets = (struct sbucket **)
343 objc_malloc ((new_max_index + 1) * sizeof (struct sbucket *));
344 #endif
346 /* Copy buckets below old_max_index (they are still valid). */
347 for (counter = 0; counter <= old_max_index; counter++ )
349 #ifdef OBJC_SPARSE3
350 new_indices[counter] = old_indices[counter];
351 #else /* OBJC_SPARSE2 */
352 new_buckets[counter] = old_buckets[counter];
353 #endif
356 #ifdef OBJC_SPARSE3
357 /* Reset entries above old_max_index to empty_bucket. */
358 for (counter = old_max_index + 1; counter <= new_max_index; counter++)
359 new_indices[counter] = array->empty_index;
360 #else /* OBJC_SPARSE2 */
361 /* Reset entries above old_max_index to empty_bucket. */
362 for (counter = old_max_index + 1; counter <= new_max_index; counter++)
363 new_buckets[counter] = array->empty_bucket;
364 #endif
366 #ifdef OBJC_SPARSE3
367 /* Install the new indices. */
368 array->indices = new_indices;
369 #else /* OBJC_SPARSE2 */
370 array->buckets = new_buckets;
371 #endif
373 #ifdef OBJC_SPARSE3
374 /* Free the old indices. */
375 sarray_free_garbage (old_indices);
376 #else /* OBJC_SPARSE2 */
377 sarray_free_garbage (old_buckets);
378 #endif
380 idxsize += (new_max_index-old_max_index);
381 return;
386 /* Free a sparse array allocated with sarray_new */
387 void
388 sarray_free (struct sarray *array) {
389 #ifdef OBJC_SPARSE3
390 size_t old_max_index = (array->capacity - 1)/INDEX_CAPACITY;
391 struct sindex **old_indices;
392 #else
393 size_t old_max_index = (array->capacity - 1)/BUCKET_SIZE;
394 struct sbucket **old_buckets;
395 #endif
396 size_t counter = 0;
398 assert (array->ref_count != 0); /* Freed multiple times!!! */
400 if (--(array->ref_count) != 0) /* There exists copies of me */
401 return;
403 #ifdef OBJC_SPARSE3
404 old_indices = array->indices;
405 #else
406 old_buckets = array->buckets;
407 #endif
409 /* Free all entries that do not point to empty_bucket. */
410 for (counter = 0; counter <= old_max_index; counter++ )
412 #ifdef OBJC_SPARSE3
413 struct sindex *idx = old_indices[counter];
414 if ((idx != array->empty_index)
415 && (idx->version.version == array->version.version))
417 int c2;
418 for (c2 = 0; c2 < INDEX_SIZE; c2++)
420 struct sbucket *bkt = idx->buckets[c2];
421 if ((bkt != array->empty_bucket)
422 && (bkt->version.version == array->version.version))
424 sarray_free_garbage (bkt);
425 nbuckets -= 1;
428 sarray_free_garbage (idx);
429 nindices -= 1;
431 #else /* OBJC_SPARSE2 */
432 struct sbucket *bkt = old_buckets[counter];
433 if ((bkt != array->empty_bucket)
434 && (bkt->version.version == array->version.version))
436 sarray_free_garbage (bkt);
437 nbuckets -= 1;
439 #endif
442 #ifdef OBJC_SPARSE3
443 /* Free empty_index. */
444 if (array->empty_index->version.version == array->version.version)
446 sarray_free_garbage (array->empty_index);
447 nindices -= 1;
449 #endif
451 /* Free empty_bucket. */
452 if (array->empty_bucket->version.version == array->version.version)
454 sarray_free_garbage (array->empty_bucket);
455 nbuckets -= 1;
457 idxsize -= (old_max_index + 1);
458 narrays -= 1;
460 #ifdef OBJC_SPARSE3
461 /* Free bucket table. */
462 sarray_free_garbage (array->indices);
463 #else
464 /* Free bucket table. */
465 sarray_free_garbage (array->buckets);
466 #endif
468 /* If this is a copy of another array, we free it (which might just
469 decrement its reference count so it will be freed when no longer
470 in use). */
471 if (array->is_copy_of)
472 sarray_free (array->is_copy_of);
474 /* Free array. */
475 sarray_free_garbage (array);
478 /* This is a lazy copy. Only the core of the structure is actually
479 copied. */
480 struct sarray *
481 sarray_lazy_copy (struct sarray *oarr)
483 struct sarray *arr;
485 #ifdef OBJC_SPARSE3
486 size_t num_indices = ((oarr->capacity - 1)/INDEX_CAPACITY) + 1;
487 struct sindex **new_indices;
488 #else /* OBJC_SPARSE2 */
489 size_t num_indices = ((oarr->capacity - 1)/BUCKET_SIZE) + 1;
490 struct sbucket **new_buckets;
491 #endif
493 /* Allocate core array. */
494 arr = (struct sarray *) objc_malloc (sizeof (struct sarray)); /* !!! */
495 arr->version.version = oarr->version.version + 1;
496 #ifdef OBJC_SPARSE3
497 arr->empty_index = oarr->empty_index;
498 #endif
499 arr->empty_bucket = oarr->empty_bucket;
500 arr->ref_count = 1;
501 oarr->ref_count += 1;
502 arr->is_copy_of = oarr;
503 arr->capacity = oarr->capacity;
505 #ifdef OBJC_SPARSE3
506 /* Copy bucket table. */
507 new_indices = (struct sindex **)
508 objc_malloc (sizeof (struct sindex *) * num_indices);
509 memcpy (new_indices, oarr->indices, sizeof (struct sindex *) * num_indices);
510 arr->indices = new_indices;
511 #else
512 /* Copy bucket table. */
513 new_buckets = (struct sbucket **)
514 objc_malloc (sizeof (struct sbucket *) * num_indices);
515 memcpy (new_buckets, oarr->buckets, sizeof (struct sbucket *) * num_indices);
516 arr->buckets = new_buckets;
517 #endif
519 idxsize += num_indices;
520 narrays += 1;
522 return arr;