/* array.c: routines to deal with arrays */

/* Copyright (C) 1999 by the Massachusetts Institute of Technology.
 *
 * Permission to use, copy, modify, and distribute this
 * software and its documentation for any purpose and without
 * fee is hereby granted, provided that the above copyright
 * notice appear in all copies and that both that copyright
 * notice and this permission notice appear in supporting
 * documentation, and that the name of M.I.T. not be used in
 * advertising or publicity pertaining to distribution of the
 * software without specific, written prior permission.
 * M.I.T. makes no representations about the suitability of
 * this software for any purpose.  It is provided "as is"
 * without express or implied warranty.
 */

#include "nawm.h"
#include "lang.h"
#include <assert.h>
#include <stdlib.h>
#include <string.h>

int hashstr(char *str);
void array_free_element(nawmval data, dtype stype);

int hashstr(char *str)
{
  int i, val;

  for (i = val = 0; str; str++)
    val += *str * ++i;
  return val;
}

#define hash(type, val) ((type == T_STR) ? hashstr((char *)val) : val)


typedef struct _achain {
  nawmval index;
  nawmval data;
  struct _achain *next;
} achain;

typedef struct _arraytype {
  int tag;
  dtype basetype;
  dtype subtype;
} arraytype;

struct _array {
  int size, nelts;
  arraytype *type;
  achain **elts;
};

static arraytype *atypes = NULL;
static int natypes = 0;

dtype array_type(dtype base, dtype sub)
{
  int i;

  for (i = 0; i < natypes; i++)
    {
      if (atypes[i].basetype == base && atypes[i].subtype == sub)
	return (dtype)&atypes[i];
    }

  atypes = xrealloc(atypes, (i + 1) * sizeof(arraytype));
  atypes[i].tag = T_ARRAY;
  atypes[i].basetype = base;
  atypes[i].subtype = sub;
  return (dtype)&atypes[i];
}

dtype array_basetype(dtype arrtype)
{
  arraytype *type = (arraytype *)arrtype;
  assert(type->tag == T_ARRAY);
  return type->basetype;
}

dtype array_subtype(dtype arrtype)
{
  arraytype *type = (arraytype *)arrtype;
  assert(type->tag == T_ARRAY);
  return type->subtype;
}

char *array_typename(dtype arrtype)
{
  char *base, *sub, *ans;
  arraytype *type = (arraytype *)arrtype;
  assert(type->tag == T_ARRAY);

  base = typename(type->basetype);
  sub = typename(type->subtype);
  ans = gcmalloc(strlen(base) + strlen(sub) + 3, free);
  sprintf(ans, "%s[%s]", base, sub);
  return ans;
}


array *create_array(dtype type, int nbuckets)
{
  array *ans;

  ans = gcmalloc(sizeof(array), (void (*)(void *))free_array);
  ans->type = (arraytype *)type;
  ans->size = nbuckets;
  ans->nelts = 0;
  ans->elts = xmalloc(nbuckets * sizeof(achain *));
  memset(ans->elts, 0, nbuckets * sizeof(achain *));
  return ans;
}

int array_size(array *arr)
{
  return arr->nelts;
}

nawmval array_lookup(array *arr, nawmval subscript)
{
  int ind = hash(arr->type->subtype, subscript) % arr->size;
  achain *a;

  for (a = arr->elts[ind]; a; a = a->next)
    {
      if (a->index == subscript)
	return a->data;
    }
  return 0;
}

int array_contains(array *arr, nawmval value)
{
  int ind;
  achain *a;

  for (ind = 0; ind < arr->size; ind++)
    {
      for (a = arr->elts[ind]; a; a = a->next)
	{
	  if (arr->type->basetype == T_STR)
	    {
	      if (!strcmp((char *)a->data, (char *)value))
		return 1;
	    }
	  else
	    {
	      if (a->data == value)
		return 1;
	    }
	}
    }
  return 0;
}

void array_insert(array *arr, nawmval subscript, nawmval value)
{
  int ind = hash(arr->type->subtype, subscript) % arr->size;
  achain *a, *atmp;
  int len;

  if (!is_atomic_type(arr->type->basetype))
    ref((void *)value);

  for (a = arr->elts[ind], len = 0; a; a = a->next, len++)
    {
      if (a->index == subscript)
	{
	  array_free_element(a->data, arr->type->subtype);
	  a->data = value;
	  return;
	}
    }

  if (len > 10)
    {
      int nsize, i;
      achain **nelts;

      /* Need to reorganize */
      nsize = (arr->size + 1) * 2 + 1;
      nelts = xmalloc(nsize * sizeof(achain *));
      memset(nelts, 0, nsize * sizeof(achain *));

      for (i = 0; i < arr->size; i++)
	{
	  for (a = arr->elts[i]; a; a = atmp)
	    {
	      atmp = a->next;
	      ind = hash(arr->type->subtype, a->index) % nsize;
	      a->next = nelts[ind];
	      nelts[ind] = a;
	    }
	}
      free(arr->elts);
      arr->elts = nelts;
      arr->size = nsize;

      ind = hash(arr->type->subtype, subscript) % nsize;
    }

  a = xmalloc(sizeof(achain));
  a->index = subscript;
  a->data = value;
  a->next = arr->elts[ind];
  arr->elts[ind] = a;
  arr->nelts++;
}

void array_delete(array *arr, nawmval subscript)
{
  int ind = hash(arr->type->subtype, subscript) % arr->size;
  achain *a, *aprev;

  for (a = arr->elts[ind], aprev = NULL; a; aprev = a, a = a->next)
    {
      if (a->index == subscript)
	{
	  array_free_element(a->data, arr->type->subtype);
	  if (aprev)
	    aprev->next = a->next;
	  else
	    arr->elts[ind] = a->next;
	  free(a);
	  arr->nelts--;
	  return;
	}
    }
}

void free_array(array *arr)
{
  int i;
  achain *a, *atmp;

  for (i = 0; i < arr->size; i++)
    {
      for (a = arr->elts[i]; a; a = atmp)
	{
	  array_free_element(a->data, arr->type->basetype);
	  atmp = a->next;
	  free(a);
	}
      free(arr->elts[i]);
    }
  free(arr->elts);
  free(arr);
}

void array_free_element(nawmval data, dtype type)
{
  if (!is_atomic_type(type))
    unref((void *)data);
}

nawmval array_first(array *arr, arrayiter *ai)
{
  ai->ind = 0;
  ai->chain = arr->elts[ai->ind];

  return ai->chain->data;
}

nawmval array_next(array *arr, arrayiter *ai)
{
  ai->chain = ai->chain->next;

  if (!ai->chain)
    {
      ai->ind++;
      if (ai->ind >= arr->size)
	return 0;
      ai->chain = arr->elts[ai->ind];
    }

  return ai->chain->data;
}