xref: /netbsd-src/external/gpl3/gcc.old/dist/libobjc/sarray.c (revision 8feb0f0b7eaff0608f8350bbfa3098827b4bb91b)
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