sarray.c

/* Sparse Arrays for Objective C dispatch tables
   Copyright (C) 1993-2017 Free Software Foundation, Inc.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3, or (at your option)
any later version.

GCC is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

Under Section 7 of GPL version 3, you are granted additional
permissions described in the GCC Runtime Library Exception, version
3.1, as published by the Free Software Foundation.

You should have received a copy of the GNU General Public License and
a copy of the GCC Runtime Library Exception along with this program;
see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
<http://www.gnu.org/licenses/>.  */

#include "objc-private/common.h"
#include "objc-private/sarray.h"
#include "objc/runtime.h" /* For objc_malloc */
#include "objc/thr.h"     /* For objc_mutex_lock */
#include "objc-private/module-abi-8.h"
#include "objc-private/runtime.h"
#include <stdio.h>
#include <string.h> /* For memset */
#include <assert.h> /* For assert */

int nbuckets = 0;					/* !T:MUTEX */
int nindices = 0;					/* !T:MUTEX */
int narrays = 0;					/* !T:MUTEX */
int idxsize = 0;					/* !T:MUTEX */

static void *first_free_data = NULL;			/* !T:MUTEX */

#ifdef OBJC_SPARSE2
const char *__objc_sparse2_id = "2 level sparse indices";
#endif

#ifdef OBJC_SPARSE3
const char *__objc_sparse3_id = "3 level sparse indices";
#endif

/* This function removes any structures left over from free operations
   that were not safe in a multi-threaded environment. */
void
sarray_remove_garbage (void)
{
  void **vp;
  void *np;
  
  objc_mutex_lock (__objc_runtime_mutex);

  vp = first_free_data;
  first_free_data = NULL;

  while (vp)
    {
      np = *vp;
      objc_free (vp);
      vp = np;
    }
  
  objc_mutex_unlock (__objc_runtime_mutex);
}

/* Free a block of dynamically allocated memory.  If we are in
   multi-threaded mode, it is ok to free it.  If not, we add it to the
   garbage heap to be freed later. */
static void
sarray_free_garbage (void *vp)
{
  objc_mutex_lock (__objc_runtime_mutex);
  
  if (__objc_runtime_threads_alive == 1)
    {
      objc_free (vp);
      if (first_free_data)
	sarray_remove_garbage ();
    }
  else
    {
      *(void **)vp = first_free_data;
      first_free_data = vp;
    }

  objc_mutex_unlock (__objc_runtime_mutex);
}

/* sarray_at_put copies data in such a way as to be thread reader
   safe.  */
void
sarray_at_put (struct sarray *array, sidx index, void *element)
{
#ifdef OBJC_SPARSE3
  struct sindex **the_index;
  struct sindex *new_index;
#endif
  struct sbucket **the_bucket;
  struct sbucket *new_bucket;
#ifdef OBJC_SPARSE3
  size_t ioffset;
#endif
  size_t boffset;
  size_t eoffset;
#ifdef PRECOMPUTE_SELECTORS
  union sofftype xx; 
  xx.idx = index;
#ifdef OBJC_SPARSE3
  ioffset = xx.off.ioffset;
#endif
  boffset = xx.off.boffset;
  eoffset = xx.off.eoffset;
#else /* not PRECOMPUTE_SELECTORS */
#ifdef OBJC_SPARSE3
  ioffset = index/INDEX_CAPACITY;
  boffset = (index/BUCKET_SIZE)%INDEX_SIZE;
  eoffset = index%BUCKET_SIZE;
#else
  boffset = index/BUCKET_SIZE;
  eoffset = index%BUCKET_SIZE;
#endif
#endif /* not PRECOMPUTE_SELECTORS */

  assert (soffset_decode (index) < array->capacity); /* Range check */

#ifdef OBJC_SPARSE3
  the_index = &(array->indices[ioffset]);
  the_bucket = &((*the_index)->buckets[boffset]);
#else
  the_bucket = &(array->buckets[boffset]);
#endif
  
  if ((*the_bucket)->elems[eoffset] == element)
    return;		/* Great! we just avoided a lazy copy.  */

#ifdef OBJC_SPARSE3

  /* First, perform lazy copy/allocation of index if needed.  */

  if ((*the_index) == array->empty_index)
    {
      /* The index was previously empty, allocate a new.  */
      new_index = (struct sindex *) objc_malloc (sizeof (struct sindex));
      memcpy (new_index, array->empty_index, sizeof (struct sindex));
      new_index->version.version = array->version.version;
      *the_index = new_index;                     /* Prepared for install. */
      the_bucket = &((*the_index)->buckets[boffset]);
      
      nindices += 1;
    }
  else if ((*the_index)->version.version != array->version.version)
    {
      /* This index must be lazy copied.  */
      struct sindex *old_index = *the_index;
      new_index = (struct sindex *) objc_malloc (sizeof (struct sindex));
      memcpy (new_index, old_index, sizeof (struct sindex));
      new_index->version.version = array->version.version;
      *the_index = new_index;                     /* Prepared for install. */
      the_bucket = &((*the_index)->buckets[boffset]);
      
      nindices += 1;
    }
  
#endif /* OBJC_SPARSE3 */
  
  /* Next, perform lazy allocation/copy of the bucket if needed.  */
  if ((*the_bucket) == array->empty_bucket)
    {
      /* The bucket was previously empty (or something like that),
	 allocate a new.  This is the effect of `lazy' allocation.  */  
      new_bucket = (struct sbucket *) objc_malloc (sizeof (struct sbucket));
      memcpy ((void *) new_bucket, (const void *) array->empty_bucket, 
	      sizeof (struct sbucket));
      new_bucket->version.version = array->version.version;
      *the_bucket = new_bucket;                   /* Prepared for install. */
      
      nbuckets += 1;
      
    }
  else if ((*the_bucket)->version.version != array->version.version)
    {
      /* Perform lazy copy.  */
      struct sbucket *old_bucket = *the_bucket;
      new_bucket = (struct sbucket *) objc_malloc (sizeof (struct sbucket));
      memcpy (new_bucket, old_bucket, sizeof (struct sbucket));
      new_bucket->version.version = array->version.version;
      *the_bucket = new_bucket;                   /* Prepared for install. */
      
      nbuckets += 1;
    }
  (*the_bucket)->elems[eoffset] = element;
}

void
sarray_at_put_safe (struct sarray *array, sidx index, void *element)
{
  if (soffset_decode (index) >= array->capacity)
    sarray_realloc (array, soffset_decode (index) + 1);
  sarray_at_put (array, index, element);
}

struct sarray *
sarray_new (int size, void *default_element)
{
  struct sarray *arr;
#ifdef OBJC_SPARSE3
  size_t num_indices = ((size - 1)/(INDEX_CAPACITY)) + 1;
  struct sindex **new_indices;
#else /* OBJC_SPARSE2 */
  size_t num_indices = ((size - 1)/BUCKET_SIZE) + 1;
  struct sbucket **new_buckets;
#endif
  size_t counter;

  assert (size > 0);

  /* Allocate core array.  */
  arr = (struct sarray *) objc_malloc (sizeof (struct sarray));
  arr->version.version = 0;
  
  /* Initialize members.  */
#ifdef OBJC_SPARSE3
  arr->capacity = num_indices*INDEX_CAPACITY;
  new_indices = (struct sindex **) 
    objc_malloc (sizeof (struct sindex *) * num_indices);
  
  arr->empty_index = (struct sindex *) objc_malloc (sizeof (struct sindex));
  arr->empty_index->version.version = 0;
  
  narrays  += 1;
  idxsize  += num_indices;
  nindices += 1;

#else /* OBJC_SPARSE2 */
  arr->capacity = num_indices*BUCKET_SIZE;
  new_buckets = (struct sbucket **) 
    objc_malloc (sizeof (struct sbucket *) * num_indices);
  
  narrays  += 1;
  idxsize  += num_indices;

#endif

  arr->empty_bucket = (struct sbucket *) objc_malloc (sizeof (struct sbucket));
  arr->empty_bucket->version.version = 0;
  
  nbuckets += 1;

  arr->ref_count = 1;
  arr->is_copy_of = (struct sarray *) 0;
  
  for (counter = 0; counter < BUCKET_SIZE; counter++)
    arr->empty_bucket->elems[counter] = default_element;

#ifdef OBJC_SPARSE3
  for (counter = 0; counter < INDEX_SIZE; counter++)
    arr->empty_index->buckets[counter] = arr->empty_bucket;

  for (counter = 0; counter < num_indices; counter++)
    new_indices[counter] = arr->empty_index;

#else /* OBJC_SPARSE2 */

  for (counter = 0; counter < num_indices; counter++)
    new_buckets[counter] = arr->empty_bucket;

#endif
  
#ifdef OBJC_SPARSE3
  arr->indices = new_indices;
#else /* OBJC_SPARSE2 */
  arr->buckets = new_buckets;
#endif
  
  return arr;
}


/* Reallocate the sparse array to hold `newsize' entries Note: We
   really allocate and then free.  We have to do this to ensure that
   any concurrent readers notice the update.  */
void 
sarray_realloc (struct sarray *array, int newsize)
{
#ifdef OBJC_SPARSE3
  size_t old_max_index = (array->capacity - 1)/INDEX_CAPACITY;
  size_t new_max_index = ((newsize - 1)/INDEX_CAPACITY);
  size_t rounded_size = (new_max_index + 1) * INDEX_CAPACITY;

  struct sindex **new_indices;
  struct sindex **old_indices;
  
#else /* OBJC_SPARSE2 */
  size_t old_max_index = (array->capacity - 1)/BUCKET_SIZE;
  size_t new_max_index = ((newsize - 1)/BUCKET_SIZE);
  size_t rounded_size = (new_max_index + 1) * BUCKET_SIZE;

  struct sbucket **new_buckets;
  struct sbucket **old_buckets;
  
#endif

  size_t counter;

  assert (newsize > 0);

  /* The size is the same, just ignore the request.  */
  if (rounded_size <= array->capacity)
    return;

  assert (array->ref_count == 1);	/* stop if lazy copied... */

  /* We are asked to extend the array -- allocate new bucket table,
     and insert empty_bucket in newly allocated places.  */
  if (rounded_size > array->capacity) 
    {
#ifdef OBJC_SPARSE3
      new_max_index += 4;
      rounded_size = (new_max_index + 1) * INDEX_CAPACITY;
#else /* OBJC_SPARSE2 */
      new_max_index += 4;
      rounded_size = (new_max_index + 1) * BUCKET_SIZE;
#endif
      
      /* Update capacity.  */
      array->capacity = rounded_size;

#ifdef OBJC_SPARSE3
      /* Alloc to force re-read by any concurrent readers.  */
      old_indices = array->indices;
      new_indices = (struct sindex **)
	objc_malloc ((new_max_index + 1) * sizeof (struct sindex *));
#else /* OBJC_SPARSE2 */
      old_buckets = array->buckets;
      new_buckets = (struct sbucket **)
	objc_malloc ((new_max_index + 1) * sizeof (struct sbucket *));
#endif

      /* Copy buckets below old_max_index (they are still valid).  */
      for (counter = 0; counter <= old_max_index; counter++ )
	{
#ifdef OBJC_SPARSE3
	  new_indices[counter] = old_indices[counter];
#else /* OBJC_SPARSE2 */
	  new_buckets[counter] = old_buckets[counter];
#endif
	}

#ifdef OBJC_SPARSE3
      /* Reset entries above old_max_index to empty_bucket.  */
      for (counter = old_max_index + 1; counter <= new_max_index; counter++)
	new_indices[counter] = array->empty_index;
#else /* OBJC_SPARSE2 */
      /* Reset entries above old_max_index to empty_bucket.  */
      for (counter = old_max_index + 1; counter <= new_max_index; counter++)
	new_buckets[counter] = array->empty_bucket;
#endif
      
#ifdef OBJC_SPARSE3
      /* Install the new indices.  */
      array->indices = new_indices;
#else /* OBJC_SPARSE2 */
      array->buckets = new_buckets;
#endif

#ifdef OBJC_SPARSE3
      /* Free the old indices.  */
      sarray_free_garbage (old_indices);
#else /* OBJC_SPARSE2 */
      sarray_free_garbage (old_buckets);
#endif
      
      idxsize += (new_max_index-old_max_index);
      return;
    }
}


/* Free a sparse array allocated with sarray_new */
void 
sarray_free (struct sarray *array) {
#ifdef OBJC_SPARSE3
  size_t old_max_index = (array->capacity - 1)/INDEX_CAPACITY;
  struct sindex **old_indices;
#else
  size_t old_max_index = (array->capacity - 1)/BUCKET_SIZE;
  struct sbucket **old_buckets;
#endif
  size_t counter = 0;

  assert (array->ref_count != 0);	/* Freed multiple times!!! */

  if (--(array->ref_count) != 0)	/* There exists copies of me */
    return;

#ifdef OBJC_SPARSE3
  old_indices = array->indices;
#else
  old_buckets = array->buckets;
#endif

  /* Free all entries that do not point to empty_bucket.  */
  for (counter = 0; counter <= old_max_index; counter++ )
    {
#ifdef OBJC_SPARSE3
      struct sindex *idx = old_indices[counter];
      if ((idx != array->empty_index)
	  && (idx->version.version == array->version.version))
	{
	  int c2; 
	  for (c2 = 0; c2 < INDEX_SIZE; c2++)
	    {
	      struct sbucket *bkt = idx->buckets[c2];
	      if ((bkt != array->empty_bucket)
		  && (bkt->version.version == array->version.version))
		{
		  sarray_free_garbage (bkt);
		  nbuckets -= 1;
		}
	    }
	  sarray_free_garbage (idx);
	  nindices -= 1;
	}
#else /* OBJC_SPARSE2 */
      struct sbucket *bkt = old_buckets[counter];
      if ((bkt != array->empty_bucket)
	  && (bkt->version.version == array->version.version))
	{
	  sarray_free_garbage (bkt);
	  nbuckets -= 1;
	}
#endif
    }
  
#ifdef OBJC_SPARSE3  
  /* Free empty_index.  */
  if (array->empty_index->version.version == array->version.version)
    {
      sarray_free_garbage (array->empty_index);
      nindices -= 1;
    }
#endif

  /* Free empty_bucket.  */
  if (array->empty_bucket->version.version == array->version.version)
    {
      sarray_free_garbage (array->empty_bucket);
      nbuckets -= 1;
    }
  idxsize -= (old_max_index + 1);
  narrays -= 1;
  
#ifdef OBJC_SPARSE3
  /* Free bucket table.  */
  sarray_free_garbage (array->indices);
#else
  /* Free bucket table.  */
  sarray_free_garbage (array->buckets);
#endif
  
  /* If this is a copy of another array, we free it (which might just
     decrement its reference count so it will be freed when no longer
     in use).  */
  if (array->is_copy_of)
    sarray_free (array->is_copy_of);

  /* Free array.  */
  sarray_free_garbage (array);
}

/* This is a lazy copy.  Only the core of the structure is actually
   copied.  */
struct sarray *
sarray_lazy_copy (struct sarray *oarr)
{
  struct sarray *arr;

#ifdef OBJC_SPARSE3
  size_t num_indices = ((oarr->capacity - 1)/INDEX_CAPACITY) + 1;
  struct sindex **new_indices;
#else /* OBJC_SPARSE2 */
  size_t num_indices = ((oarr->capacity - 1)/BUCKET_SIZE) + 1;
  struct sbucket **new_buckets;
#endif

  /* Allocate core array.  */
  arr = (struct sarray *) objc_malloc (sizeof (struct sarray)); /* !!! */
  arr->version.version = oarr->version.version + 1;
#ifdef OBJC_SPARSE3
  arr->empty_index = oarr->empty_index;
#endif
  arr->empty_bucket = oarr->empty_bucket;
  arr->ref_count = 1;
  oarr->ref_count += 1;
  arr->is_copy_of = oarr;
  arr->capacity = oarr->capacity;
  
#ifdef OBJC_SPARSE3
  /* Copy bucket table.  */
  new_indices = (struct sindex **) 
    objc_malloc (sizeof (struct sindex *) * num_indices);
  memcpy (new_indices, oarr->indices, sizeof (struct sindex *) * num_indices);
  arr->indices = new_indices;
#else 
  /* Copy bucket table.  */
  new_buckets = (struct sbucket **) 
    objc_malloc (sizeof (struct sbucket *) * num_indices);
  memcpy (new_buckets, oarr->buckets, sizeof (struct sbucket *) * num_indices);
  arr->buckets = new_buckets;
#endif

  idxsize += num_indices;
  narrays += 1;
  
  return arr;
}