#include <cstring>
#include <cstddef>
#include <cassert>
#include <cstdlib>
#include "StringTable.h"
#include "errors.h"

struct StringHashHeader {
  size_t numBuckets;
};

struct StringHashBucket {
  size_t dataIndex;
};

struct StringHashData {
  size_t strtabIndex;
  size_t next;
};

// Value in hash data and returned by search if string not found.
#define NOT_FOUND ((size_t) -1)

StringTable::StringTable(size_t initStrSize,
			 size_t numInitHashes,
			 size_t numBuckets)
  : frozen(false)
{
  assert(initStrSize > 0);
  assert(numInitHashes > 0);
  assert(numBuckets > 0);

  strBlockSize = initStrSize;
  strTable = new char[strBlockSize];
  strTableSize = 0;

  hashTableSize = (sizeof(StringHashHeader) +
		   numBuckets*sizeof(StringHashBucket));
  hashBlockSize = hashTableSize + numInitHashes*sizeof(StringHashData);
  hashTable = new char[hashBlockSize];
  ((StringHashHeader *) hashTable)->numBuckets = numBuckets;
  updateHashCache();
  for (int i = 0; i < (int)numHashBucketsCache; i++) {
    hashTableBucketsCache[i].dataIndex = NOT_FOUND;
  }
  hashTableDataItems = 0;
}

StringTable::~StringTable()
{
  delete [] strTable;
  delete [] hashTable;
}

void StringTable::updateHashCache()
{
  numHashBucketsCache = ((StringHashHeader *) hashTable)->numBuckets;
  hashTableHeaderCache = (StringHashHeader *) hashTable;
  hashTableBucketsCache = (StringHashBucket *) ((unsigned long) hashTable +
						sizeof(StringHashHeader));
  hashTableDataCache =
    (StringHashData *) ((unsigned long) hashTable +
			sizeof(StringHashHeader) +
			numHashBucketsCache * sizeof(StringHashBucket));
}

// When tables need to grow, expand tables by this formula.
#define EXPAND_SIZE(size) ((size) << 1)

// Add a string. The current implementation uses "realloc" to resize tables
// as necessary.
// DOB: switched to new/delete on 10/19/00
size_t StringTable::add(const char *s)
{
  size_t rv;

  assert(s != NULL);

  if (frozen) {
    fatal_error("");
    return NOT_FOUND;
  }

  rv = search(s);
  if (rv == NOT_FOUND) {
    size_t hash_val;
    size_t s_size = strlen(s) + 1;

    size_t newStrTableSize = strTableSize + s_size;
    if (newStrTableSize > strBlockSize) {
      /* Expand strTable if necessary */
      while (newStrTableSize > strBlockSize) {
        strBlockSize = EXPAND_SIZE(strBlockSize);
      }
      // grow table
      char *temp = new char[strBlockSize];
      memcpy(temp, strTable, strTableSize);
      delete [] strTable;
      strTable = temp;
      }
    memcpy(&strTable[strTableSize], s, s_size);
    rv = strTableSize;

    size_t newHashTableSize = hashTableSize + sizeof(StringHashData);
    if (newHashTableSize > hashBlockSize) {
      /* Expand hashTable if necessary */
      while (newHashTableSize > hashBlockSize) {
        hashBlockSize = EXPAND_SIZE(hashBlockSize);
      }
      // grow table
      char *temp = new char[hashBlockSize];
      memcpy(temp, hashTable, hashTableSize);
      delete [] hashTable;
      hashTable = temp;

      updateHashCache();
      }

    /* Link into head of linked list */
    hash_val = hash(s);
    StringHashBucket &bucket = hashTableBucketsCache[hash_val];
    StringHashData &data = hashTableDataCache[hashTableDataItems];
    data.strtabIndex = strTableSize;
    data.next = bucket.dataIndex;
    bucket.dataIndex = hashTableDataItems;

    /* Update indicies */
    hashTableSize = newHashTableSize;
    strTableSize = newStrTableSize;
    hashTableDataItems++;
    assert(((unsigned long) hashTable + hashTableSize) ==
	   (unsigned long) (&hashTableDataCache[hashTableDataItems]));
  }

  return rv;
}

// A faster string compare
// Avoid a potentially slow function call if possible.
#define STRCMP(s1, s2) \
  (assert(s1 != NULL), \
   assert(s2 != NULL), \
   ((*(s1) != *(s2)) ? (*(s1) - *(s2)) : strcmp((s1), (s2))))

size_t StringTable::search(const char *s)
{
  size_t hash_val;
  size_t currDataIndex;

  assert(s != NULL);
  hash_val = hash(s);
  StringHashBucket &bucket = hashTableBucketsCache[hash_val];

  for (currDataIndex = bucket.dataIndex;
       currDataIndex != NOT_FOUND;
       ) {
    StringHashData &data = hashTableDataCache[currDataIndex];
    if (STRCMP(strTable + data.strtabIndex, s) == 0) {
      return data.strtabIndex;
    }
    currDataIndex = data.next;
  }

  return NOT_FOUND;
}


#if 0 /* Test */
#include <cstdio>
#include <cstdlib>

void dumpc(char *s, size_t size)
{
  int count = 0;
  printf("Memory (char): 0x%lx for %d\n", s, size);
  while (size > 0) {
    switch (*s) {
    case '\0': printf("\\0 ", *s); break;
    case '\n': printf("\\n ", *s); break;
    case '\t': printf("\\t ", *s); break;
    default:   printf(" %c ", *s);
    }
    count++;
    if ((count % 16) == 0) {
      printf("\n");
    }
    size--;
    s++;
  }
  printf("\n");
}

void dumpi(size_t *s, size_t size)
{
  int count = 0;
  printf("Memory (word): 0x%lx for %d\n", s, size);
  while (size > 0) {
    printf("%5d ", *s);
    count++;
    if ((count % 16) == 0) {
      printf("\n");
    }
    size -= 4;
    s++;
  }
  printf("\n");
}

int main()
{
  StringTable *st;
  int index;

  // st = new StringTable(8192,1024,9970);
  st = new StringTable(1,1,2);
  index = st->add("Foo"); printf("%s %d\n", st->getStrTableVolatile() + index, index);
  index = st->add("Foo"); printf("%s %d\n", st->getStrTableVolatile() + index, index);
  index = st->add("Bar"); printf("%s %d\n", st->getStrTableVolatile() + index, index);
  index = st->add("Foo"); printf("%s %d\n", st->getStrTableVolatile() + index, index);
  index = st->add("Bar"); printf("%s %d\n", st->getStrTableVolatile() + index, index);
  index = st->add("Bazzer"); printf("%s %d\n", st->getStrTableVolatile() + index, index);
  index = st->add("Bazzer"); printf("%s %d\n", st->getStrTableVolatile() + index, index);
  index = st->add("This is a very long string"); printf("%s %d\n", st->getStrTableVolatile() + index, index);
  index = st->add("1"); printf("%s %d\n", st->getStrTableVolatile() + index, index);
  index = st->add("2"); printf("%s %d\n", st->getStrTableVolatile() + index, index);
  index = st->add("12"); printf("%s %d\n", st->getStrTableVolatile() + index, index);
  index = st->add("2"); printf("%s %d\n", st->getStrTableVolatile() + index, index);
  index = st->add("This is a very long string"); printf("%s %d\n", st->getStrTableVolatile() + index, index);
  index = st->add("Foo"); printf("%s %d\n", st->getStrTableVolatile() + index, index);
  index = st->add("Bar"); printf("%s %d\n", st->getStrTableVolatile() + index, index);

  char buf[1024];
  for (int i = 0; i < 10000; i++) {
    if ((i % 1000) == 0) printf("%d\n", i);
    sprintf(buf, "%c Hello this is a very long unique string %d", i % 127 + 1, i);
    index = st->add(buf);
    index = st->add("Foo");    index = st->add("Foo");
    index = st->add("Bar");    index = st->add("Foo");
    index = st->add("Bar");    index = st->add("Bazzer");
    index = st->add("Bazzer"); index = st->add("This is a very long string");
    index = st->add("1");      index = st->add("2");
    index = st->add("12");     index = st->add("2");
    index = st->add("This is a very long string");
    index = st->add("Foo");    index = st->add("Bar");
  }

  // dumpc(st->getStrTable(), st->getStrTableSize());
  // dumpi((size_t *) st->getHashTable(), st->getHashTableSize());

  delete st;

  return 0;
}

#endif