/* 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 <string.h>
#include "assert.h"
#include "objc-api.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 */

const char* __objc_sparse2_id = "2 level sparse indices";

#ifdef __alpha__
const void *memcpy (void*, const void*, size_t);
#endif

static void sarray_free_garbage(void *vp);

/* sparse array 2 */

#if BUCKET_SIZE == 32
static struct sbucket empty_bucket_32 = {
  { NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL }, /* elements */
  { -1 }
};
#elif BUCKET_SIZE == 64
static struct sbucket empty_bucket_64 = {
  { NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL }, /* elements */
  { -1 }
};
#elif BUCKET_SIZE == 256
static struct sbucket empty_bucket_256 = {
  { NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL, NULL, NULL }, /* elements */
  { -1 }
};
#endif

struct sarray *sarray_new (int size)
{
  struct sarray  *arr;
  size_t         num_indices = ((size - 1) / BUCKET_SIZE) + 1;
  struct sbucket **new_buckets;
  int            counter;

  assert(size > 0);

  /* Allocate core array */
  arr = (struct sarray*)OBJC_MALLOC_UNCOLLECTABLE(sizeof(struct sarray));
  arr->version.version = 0;
  
  /* Initialize members */
  arr->capacity = num_indices * BUCKET_SIZE;
  new_buckets = (struct sbucket **)
    OBJC_MALLOC_UNCOLLECTABLE(sizeof(struct sbucket *) * num_indices);
  
  narrays  += 1;
  idxsize  += num_indices;

#if BUCKET_SIZE == 32 || BUCKET_SIZE == 64 ||BUCKET_SIZE == 256
#  if BUCKET_SIZE == 32
    arr->empty_bucket = &empty_bucket_32;
#  elif BUCKET_SIZE == 64
    arr->empty_bucket = &empty_bucket_64;
#  elif BUCKET_SIZE == 256
    arr->empty_bucket = &empty_bucket_256;
#  endif
#else
  arr->empty_bucket =
    (struct sbucket *)OBJC_MALLOC_UNCOLLECTABLE(sizeof(struct sbucket));
  arr->empty_bucket->version.version = 0;
#endif
  
  nbuckets += 1;

  arr->ref_count = 1;
  arr->is_copy_of = (struct sarray*)0;
  
  for (counter = 0; counter < num_indices; counter++)
    new_buckets[counter] = arr->empty_bucket;
  
  arr->buckets = new_buckets;
  
  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)
{
  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;

  int 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) {
      new_max_index += 4;
      rounded_size = (new_max_index+1)*BUCKET_SIZE;
      
      /* update capacity */
      array->capacity = rounded_size;

      old_buckets = array->buckets;
      new_buckets = (struct sbucket**)
	OBJC_MALLOC_UNCOLLECTABLE((new_max_index + 1) * sizeof(struct sbucket*));

      /* copy buckets below old_max_index (they are still valid) */
      for(counter = 0; counter <= old_max_index; counter++ )
	new_buckets[counter] = old_buckets[counter];

      /* 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;
      
      array->buckets = new_buckets;
      sarray_free_garbage(old_buckets);
      
      idxsize += (new_max_index-old_max_index);
      return;
    }
}

/* Free a sparse array allocated with sarray_new */
void sarray_free(struct sarray *array)
{
  size_t old_max_bucket_index;
  struct sbucket **old_buckets;
  register int   counter;

  if (array == NULL)
    return;

  old_max_bucket_index = (array->capacity - 1) / BUCKET_SIZE;

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

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

  old_buckets = array->buckets;

  /* Free all entries that do not point to empty_bucket */
  for(counter = 0; counter <= old_max_bucket_index; counter++ ) {
    register struct sbucket *bkt = array->buckets[counter];

    if ((bkt == NULL) || (bkt == array->empty_bucket))
      continue;
    
    if (bkt->version.version == array->version.version) {
      /*
        only if bucket belongs to this array
        (only written records in lazy copies)
      */
      sarray_free_garbage(bkt); bkt = NULL;
      nbuckets -= 1;
    }
  }

  /* free empty_bucket */
  if(array->empty_bucket->version.version == array->version.version) {
    sarray_free_garbage(array->empty_bucket);
    nbuckets -= 1;
  }
  idxsize -= (old_max_bucket_index + 1);
  narrays -= 1;

  /* free bucket table */
  sarray_free_garbage(array->buckets);

  /* release lazy copy */
  if (array->is_copy_of) {
    assert(array->is_copy_of != array);
    assert(array->is_copy_of->version.version < array->version.version);
    
    sarray_free(array->is_copy_of);
    array->is_copy_of = NULL;
  }

  /* 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;
  size_t num_indices = ((oarr->capacity-1)/BUCKET_SIZE)+1;
  struct sbucket ** new_buckets;

  /* Allocate core array */
  arr = (struct sarray *)OBJC_MALLOC_UNCOLLECTABLE(sizeof(struct sarray));
  assert(arr != oarr);
  arr->version.version =  oarr->version.version + 1;
  arr->empty_bucket    =  oarr->empty_bucket;
  arr->ref_count       =  1;
  oarr->ref_count      += 1;
  arr->is_copy_of      =  oarr;
  arr->capacity        =  oarr->capacity;
  
  /* Copy bucket table */
  new_buckets = (struct sbucket**) 
    OBJC_MALLOC_UNCOLLECTABLE(sizeof(struct sbucket *) * num_indices);
  memcpy(new_buckets, oarr->buckets, sizeof(struct sbucket*)*num_indices);
  arr->buckets = new_buckets;
  idxsize += num_indices;
  narrays += 1;
  
  return arr;
}

void sarray_at_put(struct sarray *array, sidx index, void *element) {
  return sarray_at_put_safe(array, index, element);
}

void
sarray_at_put_safe(struct sarray *array, sidx index, void *element)
{
  register unsigned int idx;
  struct sbucket** the_bucket;
  struct sbucket*  new_bucket;
  size_t boffset;
  size_t eoffset;
  boffset = index / BUCKET_SIZE;
  eoffset = index % BUCKET_SIZE;
  
  idx = index;

#ifdef __WIN32__
  if (array == NULL) 
    abort();
#endif
  
  if (idx >= array->capacity)
    sarray_realloc(array, (idx + 1));
  
  assert(idx < array->capacity); /* Range check */

  the_bucket = &(array->buckets[boffset]);

  if ((*the_bucket)->elems[eoffset] == element)
    return;		/* great! we just avoided a lazy copy */

  /* 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_UNCOLLECTABLE(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_UNCOLLECTABLE(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;
}

/* 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;

  RUNTIME_LOCK;

  vp = first_free_data;
  first_free_data = NULL;

  while (vp) {
    np = *vp;
#if OBJC_WITH_GC
    GC_FREE(vp);
#else
    free(vp);
#endif
    vp = np;
  }
  
  RUNTIME_UNLOCK;
}

/* 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) {
  RUNTIME_LOCK;
  
  if (__objc_runtime_threads_alive == 1) {
#if OBJC_WITH_GC
    GC_FREE(vp);
#else
    free(vp);
#endif
    if (first_free_data)
      sarray_remove_garbage();
  }
  else {
    *(void **)vp = first_free_data;
    first_free_data = vp;
  }
      
  RUNTIME_UNLOCK;
}