Subversion Repositories openrisc

/* Sparse Arrays for Objective C dispatch tables

   Copyright (C) 1993, 1995, 1996, 2002, 2004, 2009, 2010

   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;

}