/*
 * Copyright (c) 1998-2010 NetApp, Inc.
 * All rights reserved.
 */

#include <stdlib.h>
#include "ivsc.h"
#include <assert.h>

/*
 * Searchable Collections:
 *
 * Expanding hash tables with a key and data.
 */

static int sizes[] = {
  4, 8, 16, 32,
  64, 128, 256, 512,
  1024, 2048, 4096, 8192,
  16*1024, 32*1024, 64*1024, 128*1024,
  256*1024, 512*1024, 1024*1024, 2*1024*1024,
  4*1024*1024, 8*1024*1024, 16*1024*1024 };
#define Hash(a,sc) (IVScHASH((unsigned long)a) & (sc->size - 1))

#define MAXFILL(x) (((x) * 17) / 20)

/*
 * Turning this on will cause the package to self-check on every (modifying)
 * operation.  The package runs very slowly when this is enabled.
 */
#undef DEBUGSC

#ifdef DEBUGSC
void IVScCheckOut();
#define IVScCHECKOUT(sc) IVScCheckOut(sc)
#else
#define IVScCHECKOUT(sc) 
#endif

cmm_value_t IVScNILValue;

/* Return a new, empty IVSc */
IVSc IVScCreateN(int howbig, enum iv_tag tag)
{
  register int i=0;
  register IVSc sc;

  sc = (IVSc) malloc(sizeof(IVScRecord));
  while (sizes[i] < howbig) {
       assert((unsigned int)i < sizeof(sizes) / sizeof(sizes[0]));
       i++;
  }
  sc->tag = tag;
  sc->size = sizes[i];
  sc->maxCount = MAXFILL(sc->size);
  sc->count = 0;
  sc->table = (IVScTEPtr) malloc((unsigned) sc->size * sizeof(IVScTE));
  sc->outer = 0;
  for (i = 0; i < sc->size; i++) {
    sc->table[i].key = IVScNIL;
  }
  IVScCHECKOUT(sc);
  return sc;
}

void IVScDestroy(IVSc sc)
{
  free((char *)sc->table);
  free((char *)sc);
}

/* Expand the hash table.  Each element in the table is re-hashed and entered
 * in the new table. */
static void ExpandHashTable(IVSc sc)
{
  register IVScTE *nh, *oe, *ne;
  register int oldHashTableSize = sc->size, i=0;
  register IVScDomainType key;
  int index;

  while (sizes[i] <= oldHashTableSize) {
    assert((unsigned int)i < sizeof(sizes) / sizeof(sizes[0]));
    i++;
  }
  sc->size = sizes[i];
  sc->maxCount = MAXFILL(sc->size);
  nh = (IVScTEPtr) malloc((unsigned)(sc->size * sizeof(IVScTE)));
  for (i = 0; i < sc->size; i++) nh[i].key = IVScNIL;
  for (i = 0; i < oldHashTableSize; i++) {
    oe = &sc->table[i];
    key = oe->key;
    if (key == IVScNIL) continue;
    index = Hash(key, sc);
    while (1) {
      ne = &nh[index];
      if (ne->key == IVScNIL) {
	ne->key = oe->key;
	ne->value = oe->value;
	break;
      } else {
	index++;
	if (index >= sc->size) index = 0;
      }
    }
  }
  free((char *)sc->table);
  sc->table = nh;
  IVScCHECKOUT(sc);
}

/* Return the value associated with key in collection sc, or IVScNIL */
IVScRangeType IVScLookup(IVSc sc, IVScDomainType key)
{
  register int index = Hash(key, sc);
  register IVScTEPtr e;

  IVScCHECKOUT(sc);
  while (1) {
    e = &sc->table[index];
    if (e->key == IVScNIL) {            /* we did not find it */
      return IVScNILValue;
    } else if (IVScCOMPARE(e->key, key)) {
      return e->value;
    }
    if (++index >= sc->size) index = 0;
  }
}

/* Insert the key, value pair in sc.  If the key already exists, change its 
 * value. */
void IVScInsert(IVSc sc, IVScDomainType key, IVScRangeType value)
{
  register int index;
  register IVScTEPtr e;

  if (sc->count >= sc->maxCount) ExpandHashTable(sc);
  index = Hash(key, sc);
  while (1) {
    e = &sc->table[index];
    if (e->key == IVScNIL) {            /* put it here */
      e->key = key;
      e->value = value;
      sc->count++;
      IVScCHECKOUT(sc);
      return;
    } else if (IVScCOMPARE(e->key, key)) {
      e->value = value;
      IVScCHECKOUT(sc);
      return;
    }
    if (++index >= sc->size) index = 0;
  }
}

/* Select a random (the first) key from the set sc */
IVScDomainType IVScSelect(IVSc sc, IVScRangeType *rangeptr)
{
  register int index = 0;
  register IVScTEPtr e;

  IVScCHECKOUT(sc);
  while (1) {
    e = &sc->table[index];
    if (e->key != IVScNIL) {            /* we found it */
      *rangeptr = e->value;
      return e->key;
    }
    if (++index >= sc->size) return IVScNIL;
  }
}

/* Remove the entry, if it is there */
void IVScDelete(IVSc sc, IVScDomainType key)
{
  register int index = Hash(key, sc);
  register IVScRangeType value;
  register IVScTEPtr e;

  while (1) {
    e = &sc->table[index];
    if (e->key == IVScNIL) {            /* we did not find it */
      IVScCHECKOUT(sc);
      return;
    }
    if (IVScCOMPARE(e->key, key)) {
      /* Found it, now remove it */
      sc->count--;
      e->key = IVScNIL;
      e->value = IVScNILValue;
      while (1) {
	/* rehash until we reach nil again */
	if (++index >= sc->size) index = 0;
	e = & sc->table[index];
	key = e->key;
	if (key == IVScNIL) {
	  IVScCHECKOUT(sc);
	  return;
	}
	/* rehashing is done by removing then reinserting */
	value = e->value;
	e->key = IVScNIL;
	e->value = IVScNILValue;
	sc->count--;
	IVScInsert(sc, key, value);
      }
    }
    if (++index >= sc->size) index = 0;
  }
}

#ifdef DEBUGSC
/* DEBUGGING: Print the sc */
void IVScPrint(IVSc sc)
{
  IVScDomainType key;
  IVScRangeType value;
  int index;

  printf(
    "\nDump of sc @ 0x%05x, %d entr%s, current max %d\nIndex\tKey\t\tValue\n",
    (int)sc, sc->count, sc->count == 1 ? "y" : "ies",  sc->maxCount);
  for (index = 0; index < sc->size; index++) {
    key = sc->table[index].key;
    value = sc->table[index].value;
    if (key != IVScNIL) 
      printf("%3d\t0x%08x\t%08x\n", index, key, value);
  }
}

/* Make sure that the hash table is internally consistent:
 *      every key is findable, 
 *      count reflects the number of elements
 */
void IVScCheckOut(IVSc sc)
{
  register int i;
  register IVScTEPtr realElement;
  register int count;
  count = 0;

  for (i = 0; i < sc->size; i++) {
    realElement = &sc->table[i];
    if (!IVScIsNIL(realElement->key)) {
      count++;
      if (IVScIsNILValue(IVScLookup(sc, realElement->key))) {
	printf("IVSc problem: Key %#x value 0x%x\n",
		realElement->key, realElement->value);
	IVScPrint(sc);
	abort();
      }
    }
  }
  if (count != sc->count) {
    printf("Sc problem: Should have %d entries, but found %d.\n", sc->count,
      count);
    IVScPrint(sc);
    abort();
  }
}
#endif