source: trunk/src/gcc/libobjc/sarray.c@ 46

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

This file is part of GNU CC.

GNU CC 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 2, or (at your option)
any later version.

GNU CC 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.

You should have received a copy of the GNU General Public License
along with GNU CC; see the file COPYING.  If not, write to
the Free Software Foundation, 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA.  */

/* As a special exception, if you link this library with files
   compiled with GCC to produce an executable, this does not cause
   the resulting executable to be covered by the GNU General Public License.
   This exception does not however invalidate any other reasons why
   the executable file might be covered by the GNU General Public License.  */

#include "sarray.h"
#include "runtime.h"
#include <stdio.h>
#include "assert.h"

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;