#ifndef STRINGTABLE_H

#define STRINGTABLE_H

#include <cstddef>
#include <cassert>

// Opaque structs

struct StringHashHeader;
struct StringHashBucket;
struct StringHashData;

/*
  String Table
  ------------

  This implements a hashed string table similar to the one found in the
  ELF object file format.  It consists of a character array of null terminated
  strings, where each string in the array is unique.  Lookup into this
  string table is done using a hash table.

  Hash Table
  ----------
  This is a simple hash table implemented in a continuous region of memory.
  It uses a linked list conflict resolution policy.  The hash table is layed
  out as follows (n = number of buckets, k = number of entries in the hash
  table):

    Number of Buckets (1 word)
    Bucket 0          (1 word)
    ...
    Bucket n - 1      (1 word)
    Data 0            (2 words)
    ...
    Data k - 1        (2 words)

  Each bucket consits of an index into the "Data" portion of the table (e.g.
  if a bucket contains "0", it refers to "Data 0").  Each data item consits of
  an index into the string table character array as well as a "next" pointer
  into another "Data" entry.

  Public Methods
  --------------

  StringTable(size_t initStrSize, size_t numInitHashes, size_t numBuckets);
    Constructor.  Creates a string table, giving it an initial buffer size
    of "initStrSize" characters.  Also creates a hash table that has
    "numBuckets" hash buckets and an initial "Data" portion size of
    "numInitHashes" data items.  These sizes will be expanded automatically
    as necessary.

  ~StringTable()
    Destructor.

  size_t add(char *s)
    Add null terminated string "s".  Return index into string table where
    the string can be found.

  char *getStrTableVolatile()
    Return the string table as a character array.  The result may become
    invalid once any other method calls to this class are made.

  size_t getStrTableSizeVolatile()
    Return the string table size.  The result may become invalid once any
    other method calls to this class are made.

  char *getStrTable()
    Return the string table as a character array.  The resulting pointer
    will always be valid.  Once this is called, the string table is frozen
    and calls to methods that would change it fail.  The table, in effect,
    becomes read-only.

  size_t getStrTableSize()
    Return the string table size, freezing the table.

  char *getHashTable()
    Return the hash table associated with the string table.  Do a freeze.

  size_t getHashTableSize()
    Return the hash table size.  Do a freeze.

  Private Methods
  ---------------

  size_t search(char *s)
    Search the string table using the hash table for "s", returning an
    index into the string table.  A special value "NOT_FOUND" is returned
    if the string is not contained in the table.

  inline size_t hash(char *s)
    A simple hasher for null terminated string "s".

  void updateHashCache()
    Some values are cached in the object which need to be updated if any of
    the internal data structures are resized.  This does the update.

  */

class StringTable {
public:
  StringTable(size_t, size_t, size_t);
  ~StringTable();

  size_t add(const char *);

  char *getStrTableVolatile() { return strTable; }
  size_t getStrTableSizeVolatile() { return strTableSize; }
  char *getStrTable() { frozen = true; return strTable; }
  size_t getStrTableSize() { frozen = true; return strTableSize; }

  char *getHashTable() { frozen = true; return hashTable; }
  size_t getHashTableSize() { frozen = true; return hashTableSize; }

private:
  size_t search(const char *);
  inline size_t hash(const char *);
  void updateHashCache();

  // Frozen?
  bool frozen;

  // String table
  char *strTable;
  size_t strTableSize;
  size_t strBlockSize;

  // Hash table
  char *hashTable;
  size_t hashTableSize;
  size_t hashBlockSize;
  size_t hashTableDataItems;

  // Hash cache
  StringHashHeader *hashTableHeaderCache;
  StringHashBucket *hashTableBucketsCache;
  StringHashData *hashTableDataCache;
  size_t numHashBucketsCache;
};

inline size_t StringTable::hash(const char *s)
{
  size_t rv;
  int count;

  assert(s != NULL);
  // Hash function to hash using all characters.  Too slow.
  // for (rv = 0; *s != '\0'; rv += ((*s) + (rv << 1)), s++);
  // Instead, hash with up to 16 characters only.
  for (count = 0, rv = 0;
       *s != '\0' && count < 16;
       rv += ((*s) + (rv << 1)), s++, count++);

  return (rv % numHashBucketsCache);
}

#endif // STRINGTABLE_H