136ac495dSmrg /* Sparse Arrays for Objective C dispatch tables
2*8feb0f0bSmrg Copyright (C) 1993-2020 Free Software Foundation, Inc.
336ac495dSmrg
436ac495dSmrg This file is part of GCC.
536ac495dSmrg
636ac495dSmrg GCC is free software; you can redistribute it and/or modify
736ac495dSmrg it under the terms of the GNU General Public License as published by
836ac495dSmrg the Free Software Foundation; either version 3, or (at your option)
936ac495dSmrg any later version.
1036ac495dSmrg
1136ac495dSmrg GCC is distributed in the hope that it will be useful,
1236ac495dSmrg but WITHOUT ANY WARRANTY; without even the implied warranty of
1336ac495dSmrg MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
1436ac495dSmrg GNU General Public License for more details.
1536ac495dSmrg
1636ac495dSmrg Under Section 7 of GPL version 3, you are granted additional
1736ac495dSmrg permissions described in the GCC Runtime Library Exception, version
1836ac495dSmrg 3.1, as published by the Free Software Foundation.
1936ac495dSmrg
2036ac495dSmrg You should have received a copy of the GNU General Public License and
2136ac495dSmrg a copy of the GCC Runtime Library Exception along with this program;
2236ac495dSmrg see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
2336ac495dSmrg <http://www.gnu.org/licenses/>. */
2436ac495dSmrg
2536ac495dSmrg #include "objc-private/common.h"
2636ac495dSmrg #include "objc-private/sarray.h"
2736ac495dSmrg #include "objc/runtime.h" /* For objc_malloc */
2836ac495dSmrg #include "objc/thr.h" /* For objc_mutex_lock */
2936ac495dSmrg #include "objc-private/module-abi-8.h"
3036ac495dSmrg #include "objc-private/runtime.h"
3136ac495dSmrg #include <stdio.h>
3236ac495dSmrg #include <string.h> /* For memset */
3336ac495dSmrg #include <assert.h> /* For assert */
3436ac495dSmrg
3536ac495dSmrg int nbuckets = 0; /* !T:MUTEX */
3636ac495dSmrg int nindices = 0; /* !T:MUTEX */
3736ac495dSmrg int narrays = 0; /* !T:MUTEX */
3836ac495dSmrg int idxsize = 0; /* !T:MUTEX */
3936ac495dSmrg
4036ac495dSmrg static void *first_free_data = NULL; /* !T:MUTEX */
4136ac495dSmrg
4236ac495dSmrg #ifdef OBJC_SPARSE2
4336ac495dSmrg const char *__objc_sparse2_id = "2 level sparse indices";
4436ac495dSmrg #endif
4536ac495dSmrg
4636ac495dSmrg #ifdef OBJC_SPARSE3
4736ac495dSmrg const char *__objc_sparse3_id = "3 level sparse indices";
4836ac495dSmrg #endif
4936ac495dSmrg
5036ac495dSmrg /* This function removes any structures left over from free operations
5136ac495dSmrg that were not safe in a multi-threaded environment. */
5236ac495dSmrg void
sarray_remove_garbage(void)5336ac495dSmrg sarray_remove_garbage (void)
5436ac495dSmrg {
5536ac495dSmrg void **vp;
5636ac495dSmrg void *np;
5736ac495dSmrg
5836ac495dSmrg objc_mutex_lock (__objc_runtime_mutex);
5936ac495dSmrg
6036ac495dSmrg vp = first_free_data;
6136ac495dSmrg first_free_data = NULL;
6236ac495dSmrg
6336ac495dSmrg while (vp)
6436ac495dSmrg {
6536ac495dSmrg np = *vp;
6636ac495dSmrg objc_free (vp);
6736ac495dSmrg vp = np;
6836ac495dSmrg }
6936ac495dSmrg
7036ac495dSmrg objc_mutex_unlock (__objc_runtime_mutex);
7136ac495dSmrg }
7236ac495dSmrg
7336ac495dSmrg /* Free a block of dynamically allocated memory. If we are in
7436ac495dSmrg multi-threaded mode, it is ok to free it. If not, we add it to the
7536ac495dSmrg garbage heap to be freed later. */
7636ac495dSmrg static void
sarray_free_garbage(void * vp)7736ac495dSmrg sarray_free_garbage (void *vp)
7836ac495dSmrg {
7936ac495dSmrg objc_mutex_lock (__objc_runtime_mutex);
8036ac495dSmrg
8136ac495dSmrg if (__objc_runtime_threads_alive == 1)
8236ac495dSmrg {
8336ac495dSmrg objc_free (vp);
8436ac495dSmrg if (first_free_data)
8536ac495dSmrg sarray_remove_garbage ();
8636ac495dSmrg }
8736ac495dSmrg else
8836ac495dSmrg {
8936ac495dSmrg *(void **)vp = first_free_data;
9036ac495dSmrg first_free_data = vp;
9136ac495dSmrg }
9236ac495dSmrg
9336ac495dSmrg objc_mutex_unlock (__objc_runtime_mutex);
9436ac495dSmrg }
9536ac495dSmrg
9636ac495dSmrg /* sarray_at_put copies data in such a way as to be thread reader
9736ac495dSmrg safe. */
9836ac495dSmrg void
sarray_at_put(struct sarray * array,sidx index,void * element)9936ac495dSmrg sarray_at_put (struct sarray *array, sidx index, void *element)
10036ac495dSmrg {
10136ac495dSmrg #ifdef OBJC_SPARSE3
10236ac495dSmrg struct sindex **the_index;
10336ac495dSmrg struct sindex *new_index;
10436ac495dSmrg #endif
10536ac495dSmrg struct sbucket **the_bucket;
10636ac495dSmrg struct sbucket *new_bucket;
10736ac495dSmrg #ifdef OBJC_SPARSE3
10836ac495dSmrg size_t ioffset;
10936ac495dSmrg #endif
11036ac495dSmrg size_t boffset;
11136ac495dSmrg size_t eoffset;
11236ac495dSmrg #ifdef PRECOMPUTE_SELECTORS
11336ac495dSmrg union sofftype xx;
11436ac495dSmrg xx.idx = index;
11536ac495dSmrg #ifdef OBJC_SPARSE3
11636ac495dSmrg ioffset = xx.off.ioffset;
11736ac495dSmrg #endif
11836ac495dSmrg boffset = xx.off.boffset;
11936ac495dSmrg eoffset = xx.off.eoffset;
12036ac495dSmrg #else /* not PRECOMPUTE_SELECTORS */
12136ac495dSmrg #ifdef OBJC_SPARSE3
12236ac495dSmrg ioffset = index/INDEX_CAPACITY;
12336ac495dSmrg boffset = (index/BUCKET_SIZE)%INDEX_SIZE;
12436ac495dSmrg eoffset = index%BUCKET_SIZE;
12536ac495dSmrg #else
12636ac495dSmrg boffset = index/BUCKET_SIZE;
12736ac495dSmrg eoffset = index%BUCKET_SIZE;
12836ac495dSmrg #endif
12936ac495dSmrg #endif /* not PRECOMPUTE_SELECTORS */
13036ac495dSmrg
13136ac495dSmrg assert (soffset_decode (index) < array->capacity); /* Range check */
13236ac495dSmrg
13336ac495dSmrg #ifdef OBJC_SPARSE3
13436ac495dSmrg the_index = &(array->indices[ioffset]);
13536ac495dSmrg the_bucket = &((*the_index)->buckets[boffset]);
13636ac495dSmrg #else
13736ac495dSmrg the_bucket = &(array->buckets[boffset]);
13836ac495dSmrg #endif
13936ac495dSmrg
14036ac495dSmrg if ((*the_bucket)->elems[eoffset] == element)
14136ac495dSmrg return; /* Great! we just avoided a lazy copy. */
14236ac495dSmrg
14336ac495dSmrg #ifdef OBJC_SPARSE3
14436ac495dSmrg
14536ac495dSmrg /* First, perform lazy copy/allocation of index if needed. */
14636ac495dSmrg
14736ac495dSmrg if ((*the_index) == array->empty_index)
14836ac495dSmrg {
14936ac495dSmrg /* The index was previously empty, allocate a new. */
15036ac495dSmrg new_index = (struct sindex *) objc_malloc (sizeof (struct sindex));
15136ac495dSmrg memcpy (new_index, array->empty_index, sizeof (struct sindex));
15236ac495dSmrg new_index->version.version = array->version.version;
15336ac495dSmrg *the_index = new_index; /* Prepared for install. */
15436ac495dSmrg the_bucket = &((*the_index)->buckets[boffset]);
15536ac495dSmrg
15636ac495dSmrg nindices += 1;
15736ac495dSmrg }
15836ac495dSmrg else if ((*the_index)->version.version != array->version.version)
15936ac495dSmrg {
16036ac495dSmrg /* This index must be lazy copied. */
16136ac495dSmrg struct sindex *old_index = *the_index;
16236ac495dSmrg new_index = (struct sindex *) objc_malloc (sizeof (struct sindex));
16336ac495dSmrg memcpy (new_index, old_index, sizeof (struct sindex));
16436ac495dSmrg new_index->version.version = array->version.version;
16536ac495dSmrg *the_index = new_index; /* Prepared for install. */
16636ac495dSmrg the_bucket = &((*the_index)->buckets[boffset]);
16736ac495dSmrg
16836ac495dSmrg nindices += 1;
16936ac495dSmrg }
17036ac495dSmrg
17136ac495dSmrg #endif /* OBJC_SPARSE3 */
17236ac495dSmrg
17336ac495dSmrg /* Next, perform lazy allocation/copy of the bucket if needed. */
17436ac495dSmrg if ((*the_bucket) == array->empty_bucket)
17536ac495dSmrg {
17636ac495dSmrg /* The bucket was previously empty (or something like that),
17736ac495dSmrg allocate a new. This is the effect of `lazy' allocation. */
17836ac495dSmrg new_bucket = (struct sbucket *) objc_malloc (sizeof (struct sbucket));
17936ac495dSmrg memcpy ((void *) new_bucket, (const void *) array->empty_bucket,
18036ac495dSmrg sizeof (struct sbucket));
18136ac495dSmrg new_bucket->version.version = array->version.version;
18236ac495dSmrg *the_bucket = new_bucket; /* Prepared for install. */
18336ac495dSmrg
18436ac495dSmrg nbuckets += 1;
18536ac495dSmrg
18636ac495dSmrg }
18736ac495dSmrg else if ((*the_bucket)->version.version != array->version.version)
18836ac495dSmrg {
18936ac495dSmrg /* Perform lazy copy. */
19036ac495dSmrg struct sbucket *old_bucket = *the_bucket;
19136ac495dSmrg new_bucket = (struct sbucket *) objc_malloc (sizeof (struct sbucket));
19236ac495dSmrg memcpy (new_bucket, old_bucket, sizeof (struct sbucket));
19336ac495dSmrg new_bucket->version.version = array->version.version;
19436ac495dSmrg *the_bucket = new_bucket; /* Prepared for install. */
19536ac495dSmrg
19636ac495dSmrg nbuckets += 1;
19736ac495dSmrg }
19836ac495dSmrg (*the_bucket)->elems[eoffset] = element;
19936ac495dSmrg }
20036ac495dSmrg
20136ac495dSmrg void
sarray_at_put_safe(struct sarray * array,sidx index,void * element)20236ac495dSmrg sarray_at_put_safe (struct sarray *array, sidx index, void *element)
20336ac495dSmrg {
20436ac495dSmrg if (soffset_decode (index) >= array->capacity)
20536ac495dSmrg sarray_realloc (array, soffset_decode (index) + 1);
20636ac495dSmrg sarray_at_put (array, index, element);
20736ac495dSmrg }
20836ac495dSmrg
20936ac495dSmrg struct sarray *
sarray_new(int size,void * default_element)21036ac495dSmrg sarray_new (int size, void *default_element)
21136ac495dSmrg {
21236ac495dSmrg struct sarray *arr;
21336ac495dSmrg #ifdef OBJC_SPARSE3
21436ac495dSmrg size_t num_indices = ((size - 1)/(INDEX_CAPACITY)) + 1;
21536ac495dSmrg struct sindex **new_indices;
21636ac495dSmrg #else /* OBJC_SPARSE2 */
21736ac495dSmrg size_t num_indices = ((size - 1)/BUCKET_SIZE) + 1;
21836ac495dSmrg struct sbucket **new_buckets;
21936ac495dSmrg #endif
22036ac495dSmrg size_t counter;
22136ac495dSmrg
22236ac495dSmrg assert (size > 0);
22336ac495dSmrg
22436ac495dSmrg /* Allocate core array. */
22536ac495dSmrg arr = (struct sarray *) objc_malloc (sizeof (struct sarray));
22636ac495dSmrg arr->version.version = 0;
22736ac495dSmrg
22836ac495dSmrg /* Initialize members. */
22936ac495dSmrg #ifdef OBJC_SPARSE3
23036ac495dSmrg arr->capacity = num_indices*INDEX_CAPACITY;
23136ac495dSmrg new_indices = (struct sindex **)
23236ac495dSmrg objc_malloc (sizeof (struct sindex *) * num_indices);
23336ac495dSmrg
23436ac495dSmrg arr->empty_index = (struct sindex *) objc_malloc (sizeof (struct sindex));
23536ac495dSmrg arr->empty_index->version.version = 0;
23636ac495dSmrg
23736ac495dSmrg narrays += 1;
23836ac495dSmrg idxsize += num_indices;
23936ac495dSmrg nindices += 1;
24036ac495dSmrg
24136ac495dSmrg #else /* OBJC_SPARSE2 */
24236ac495dSmrg arr->capacity = num_indices*BUCKET_SIZE;
24336ac495dSmrg new_buckets = (struct sbucket **)
24436ac495dSmrg objc_malloc (sizeof (struct sbucket *) * num_indices);
24536ac495dSmrg
24636ac495dSmrg narrays += 1;
24736ac495dSmrg idxsize += num_indices;
24836ac495dSmrg
24936ac495dSmrg #endif
25036ac495dSmrg
25136ac495dSmrg arr->empty_bucket = (struct sbucket *) objc_malloc (sizeof (struct sbucket));
25236ac495dSmrg arr->empty_bucket->version.version = 0;
25336ac495dSmrg
25436ac495dSmrg nbuckets += 1;
25536ac495dSmrg
25636ac495dSmrg arr->ref_count = 1;
25736ac495dSmrg arr->is_copy_of = (struct sarray *) 0;
25836ac495dSmrg
25936ac495dSmrg for (counter = 0; counter < BUCKET_SIZE; counter++)
26036ac495dSmrg arr->empty_bucket->elems[counter] = default_element;
26136ac495dSmrg
26236ac495dSmrg #ifdef OBJC_SPARSE3
26336ac495dSmrg for (counter = 0; counter < INDEX_SIZE; counter++)
26436ac495dSmrg arr->empty_index->buckets[counter] = arr->empty_bucket;
26536ac495dSmrg
26636ac495dSmrg for (counter = 0; counter < num_indices; counter++)
26736ac495dSmrg new_indices[counter] = arr->empty_index;
26836ac495dSmrg
26936ac495dSmrg #else /* OBJC_SPARSE2 */
27036ac495dSmrg
27136ac495dSmrg for (counter = 0; counter < num_indices; counter++)
27236ac495dSmrg new_buckets[counter] = arr->empty_bucket;
27336ac495dSmrg
27436ac495dSmrg #endif
27536ac495dSmrg
27636ac495dSmrg #ifdef OBJC_SPARSE3
27736ac495dSmrg arr->indices = new_indices;
27836ac495dSmrg #else /* OBJC_SPARSE2 */
27936ac495dSmrg arr->buckets = new_buckets;
28036ac495dSmrg #endif
28136ac495dSmrg
28236ac495dSmrg return arr;
28336ac495dSmrg }
28436ac495dSmrg
28536ac495dSmrg
28636ac495dSmrg /* Reallocate the sparse array to hold `newsize' entries Note: We
28736ac495dSmrg really allocate and then free. We have to do this to ensure that
28836ac495dSmrg any concurrent readers notice the update. */
28936ac495dSmrg void
sarray_realloc(struct sarray * array,int newsize)29036ac495dSmrg sarray_realloc (struct sarray *array, int newsize)
29136ac495dSmrg {
29236ac495dSmrg #ifdef OBJC_SPARSE3
29336ac495dSmrg size_t old_max_index = (array->capacity - 1)/INDEX_CAPACITY;
29436ac495dSmrg size_t new_max_index = ((newsize - 1)/INDEX_CAPACITY);
29536ac495dSmrg size_t rounded_size = (new_max_index + 1) * INDEX_CAPACITY;
29636ac495dSmrg
29736ac495dSmrg struct sindex **new_indices;
29836ac495dSmrg struct sindex **old_indices;
29936ac495dSmrg
30036ac495dSmrg #else /* OBJC_SPARSE2 */
30136ac495dSmrg size_t old_max_index = (array->capacity - 1)/BUCKET_SIZE;
30236ac495dSmrg size_t new_max_index = ((newsize - 1)/BUCKET_SIZE);
30336ac495dSmrg size_t rounded_size = (new_max_index + 1) * BUCKET_SIZE;
30436ac495dSmrg
30536ac495dSmrg struct sbucket **new_buckets;
30636ac495dSmrg struct sbucket **old_buckets;
30736ac495dSmrg
30836ac495dSmrg #endif
30936ac495dSmrg
31036ac495dSmrg size_t counter;
31136ac495dSmrg
31236ac495dSmrg assert (newsize > 0);
31336ac495dSmrg
31436ac495dSmrg /* The size is the same, just ignore the request. */
31536ac495dSmrg if (rounded_size <= array->capacity)
31636ac495dSmrg return;
31736ac495dSmrg
31836ac495dSmrg assert (array->ref_count == 1); /* stop if lazy copied... */
31936ac495dSmrg
32036ac495dSmrg /* We are asked to extend the array -- allocate new bucket table,
32136ac495dSmrg and insert empty_bucket in newly allocated places. */
32236ac495dSmrg if (rounded_size > array->capacity)
32336ac495dSmrg {
32436ac495dSmrg #ifdef OBJC_SPARSE3
32536ac495dSmrg new_max_index += 4;
32636ac495dSmrg rounded_size = (new_max_index + 1) * INDEX_CAPACITY;
32736ac495dSmrg #else /* OBJC_SPARSE2 */
32836ac495dSmrg new_max_index += 4;
32936ac495dSmrg rounded_size = (new_max_index + 1) * BUCKET_SIZE;
33036ac495dSmrg #endif
33136ac495dSmrg
33236ac495dSmrg /* Update capacity. */
33336ac495dSmrg array->capacity = rounded_size;
33436ac495dSmrg
33536ac495dSmrg #ifdef OBJC_SPARSE3
33636ac495dSmrg /* Alloc to force re-read by any concurrent readers. */
33736ac495dSmrg old_indices = array->indices;
33836ac495dSmrg new_indices = (struct sindex **)
33936ac495dSmrg objc_malloc ((new_max_index + 1) * sizeof (struct sindex *));
34036ac495dSmrg #else /* OBJC_SPARSE2 */
34136ac495dSmrg old_buckets = array->buckets;
34236ac495dSmrg new_buckets = (struct sbucket **)
34336ac495dSmrg objc_malloc ((new_max_index + 1) * sizeof (struct sbucket *));
34436ac495dSmrg #endif
34536ac495dSmrg
34636ac495dSmrg /* Copy buckets below old_max_index (they are still valid). */
34736ac495dSmrg for (counter = 0; counter <= old_max_index; counter++ )
34836ac495dSmrg {
34936ac495dSmrg #ifdef OBJC_SPARSE3
35036ac495dSmrg new_indices[counter] = old_indices[counter];
35136ac495dSmrg #else /* OBJC_SPARSE2 */
35236ac495dSmrg new_buckets[counter] = old_buckets[counter];
35336ac495dSmrg #endif
35436ac495dSmrg }
35536ac495dSmrg
35636ac495dSmrg #ifdef OBJC_SPARSE3
35736ac495dSmrg /* Reset entries above old_max_index to empty_bucket. */
35836ac495dSmrg for (counter = old_max_index + 1; counter <= new_max_index; counter++)
35936ac495dSmrg new_indices[counter] = array->empty_index;
36036ac495dSmrg #else /* OBJC_SPARSE2 */
36136ac495dSmrg /* Reset entries above old_max_index to empty_bucket. */
36236ac495dSmrg for (counter = old_max_index + 1; counter <= new_max_index; counter++)
36336ac495dSmrg new_buckets[counter] = array->empty_bucket;
36436ac495dSmrg #endif
36536ac495dSmrg
36636ac495dSmrg #ifdef OBJC_SPARSE3
36736ac495dSmrg /* Install the new indices. */
36836ac495dSmrg array->indices = new_indices;
36936ac495dSmrg #else /* OBJC_SPARSE2 */
37036ac495dSmrg array->buckets = new_buckets;
37136ac495dSmrg #endif
37236ac495dSmrg
37336ac495dSmrg #ifdef OBJC_SPARSE3
37436ac495dSmrg /* Free the old indices. */
37536ac495dSmrg sarray_free_garbage (old_indices);
37636ac495dSmrg #else /* OBJC_SPARSE2 */
37736ac495dSmrg sarray_free_garbage (old_buckets);
37836ac495dSmrg #endif
37936ac495dSmrg
38036ac495dSmrg idxsize += (new_max_index-old_max_index);
38136ac495dSmrg return;
38236ac495dSmrg }
38336ac495dSmrg }
38436ac495dSmrg
38536ac495dSmrg
38636ac495dSmrg /* Free a sparse array allocated with sarray_new */
38736ac495dSmrg void
sarray_free(struct sarray * array)38836ac495dSmrg sarray_free (struct sarray *array) {
38936ac495dSmrg #ifdef OBJC_SPARSE3
39036ac495dSmrg size_t old_max_index = (array->capacity - 1)/INDEX_CAPACITY;
39136ac495dSmrg struct sindex **old_indices;
39236ac495dSmrg #else
39336ac495dSmrg size_t old_max_index = (array->capacity - 1)/BUCKET_SIZE;
39436ac495dSmrg struct sbucket **old_buckets;
39536ac495dSmrg #endif
39636ac495dSmrg size_t counter = 0;
39736ac495dSmrg
39836ac495dSmrg assert (array->ref_count != 0); /* Freed multiple times!!! */
39936ac495dSmrg
40036ac495dSmrg if (--(array->ref_count) != 0) /* There exists copies of me */
40136ac495dSmrg return;
40236ac495dSmrg
40336ac495dSmrg #ifdef OBJC_SPARSE3
40436ac495dSmrg old_indices = array->indices;
40536ac495dSmrg #else
40636ac495dSmrg old_buckets = array->buckets;
40736ac495dSmrg #endif
40836ac495dSmrg
40936ac495dSmrg /* Free all entries that do not point to empty_bucket. */
41036ac495dSmrg for (counter = 0; counter <= old_max_index; counter++ )
41136ac495dSmrg {
41236ac495dSmrg #ifdef OBJC_SPARSE3
41336ac495dSmrg struct sindex *idx = old_indices[counter];
41436ac495dSmrg if ((idx != array->empty_index)
41536ac495dSmrg && (idx->version.version == array->version.version))
41636ac495dSmrg {
41736ac495dSmrg int c2;
41836ac495dSmrg for (c2 = 0; c2 < INDEX_SIZE; c2++)
41936ac495dSmrg {
42036ac495dSmrg struct sbucket *bkt = idx->buckets[c2];
42136ac495dSmrg if ((bkt != array->empty_bucket)
42236ac495dSmrg && (bkt->version.version == array->version.version))
42336ac495dSmrg {
42436ac495dSmrg sarray_free_garbage (bkt);
42536ac495dSmrg nbuckets -= 1;
42636ac495dSmrg }
42736ac495dSmrg }
42836ac495dSmrg sarray_free_garbage (idx);
42936ac495dSmrg nindices -= 1;
43036ac495dSmrg }
43136ac495dSmrg #else /* OBJC_SPARSE2 */
43236ac495dSmrg struct sbucket *bkt = old_buckets[counter];
43336ac495dSmrg if ((bkt != array->empty_bucket)
43436ac495dSmrg && (bkt->version.version == array->version.version))
43536ac495dSmrg {
43636ac495dSmrg sarray_free_garbage (bkt);
43736ac495dSmrg nbuckets -= 1;
43836ac495dSmrg }
43936ac495dSmrg #endif
44036ac495dSmrg }
44136ac495dSmrg
44236ac495dSmrg #ifdef OBJC_SPARSE3
44336ac495dSmrg /* Free empty_index. */
44436ac495dSmrg if (array->empty_index->version.version == array->version.version)
44536ac495dSmrg {
44636ac495dSmrg sarray_free_garbage (array->empty_index);
44736ac495dSmrg nindices -= 1;
44836ac495dSmrg }
44936ac495dSmrg #endif
45036ac495dSmrg
45136ac495dSmrg /* Free empty_bucket. */
45236ac495dSmrg if (array->empty_bucket->version.version == array->version.version)
45336ac495dSmrg {
45436ac495dSmrg sarray_free_garbage (array->empty_bucket);
45536ac495dSmrg nbuckets -= 1;
45636ac495dSmrg }
45736ac495dSmrg idxsize -= (old_max_index + 1);
45836ac495dSmrg narrays -= 1;
45936ac495dSmrg
46036ac495dSmrg #ifdef OBJC_SPARSE3
46136ac495dSmrg /* Free bucket table. */
46236ac495dSmrg sarray_free_garbage (array->indices);
46336ac495dSmrg #else
46436ac495dSmrg /* Free bucket table. */
46536ac495dSmrg sarray_free_garbage (array->buckets);
46636ac495dSmrg #endif
46736ac495dSmrg
46836ac495dSmrg /* If this is a copy of another array, we free it (which might just
46936ac495dSmrg decrement its reference count so it will be freed when no longer
47036ac495dSmrg in use). */
47136ac495dSmrg if (array->is_copy_of)
47236ac495dSmrg sarray_free (array->is_copy_of);
47336ac495dSmrg
47436ac495dSmrg /* Free array. */
47536ac495dSmrg sarray_free_garbage (array);
47636ac495dSmrg }
47736ac495dSmrg
47836ac495dSmrg /* This is a lazy copy. Only the core of the structure is actually
47936ac495dSmrg copied. */
48036ac495dSmrg struct sarray *
sarray_lazy_copy(struct sarray * oarr)48136ac495dSmrg sarray_lazy_copy (struct sarray *oarr)
48236ac495dSmrg {
48336ac495dSmrg struct sarray *arr;
48436ac495dSmrg
48536ac495dSmrg #ifdef OBJC_SPARSE3
48636ac495dSmrg size_t num_indices = ((oarr->capacity - 1)/INDEX_CAPACITY) + 1;
48736ac495dSmrg struct sindex **new_indices;
48836ac495dSmrg #else /* OBJC_SPARSE2 */
48936ac495dSmrg size_t num_indices = ((oarr->capacity - 1)/BUCKET_SIZE) + 1;
49036ac495dSmrg struct sbucket **new_buckets;
49136ac495dSmrg #endif
49236ac495dSmrg
49336ac495dSmrg /* Allocate core array. */
49436ac495dSmrg arr = (struct sarray *) objc_malloc (sizeof (struct sarray)); /* !!! */
49536ac495dSmrg arr->version.version = oarr->version.version + 1;
49636ac495dSmrg #ifdef OBJC_SPARSE3
49736ac495dSmrg arr->empty_index = oarr->empty_index;
49836ac495dSmrg #endif
49936ac495dSmrg arr->empty_bucket = oarr->empty_bucket;
50036ac495dSmrg arr->ref_count = 1;
50136ac495dSmrg oarr->ref_count += 1;
50236ac495dSmrg arr->is_copy_of = oarr;
50336ac495dSmrg arr->capacity = oarr->capacity;
50436ac495dSmrg
50536ac495dSmrg #ifdef OBJC_SPARSE3
50636ac495dSmrg /* Copy bucket table. */
50736ac495dSmrg new_indices = (struct sindex **)
50836ac495dSmrg objc_malloc (sizeof (struct sindex *) * num_indices);
50936ac495dSmrg memcpy (new_indices, oarr->indices, sizeof (struct sindex *) * num_indices);
51036ac495dSmrg arr->indices = new_indices;
51136ac495dSmrg #else
51236ac495dSmrg /* Copy bucket table. */
51336ac495dSmrg new_buckets = (struct sbucket **)
51436ac495dSmrg objc_malloc (sizeof (struct sbucket *) * num_indices);
51536ac495dSmrg memcpy (new_buckets, oarr->buckets, sizeof (struct sbucket *) * num_indices);
51636ac495dSmrg arr->buckets = new_buckets;
51736ac495dSmrg #endif
51836ac495dSmrg
51936ac495dSmrg idxsize += num_indices;
52036ac495dSmrg narrays += 1;
52136ac495dSmrg
52236ac495dSmrg return arr;
52336ac495dSmrg }
524