/**************************************************************** 
 * PrHashTableImpl.cpp
 *
 * This is an implementation of hash table methods.
 *
 ****************************************************************/

/*
 * modification history
 *----------------------
 *
 * 02/19/98: K.C. Chang: created.
 */

#include "PrHashTableImpl.h"
#include "PrLinkedList.h"
#include "PrBitmap.h"

PrHashTableImpl::PrHashTableImpl(int maxNumItems,int tableSize)
: maxNumItems_(maxNumItems), tableSize_ (tableSize) 
{
    assert(maxNumItems>=0);

    curListNum_ = 0;
    items_ = 0;

    buckets_ = new PrLinkedList<PrHashTableEntry> *[tableSize_];

    int i;
    if (maxNumItems_ != PR_HASHTABLEIMPL_NUM_ITEMS_UNLIMITED)
      {
	  assert(maxNumItems_>0);
	  int n=maxNumItems_/tableSize_;
	  int len = PR_LINKEDLIST_SIZE_DEFAULT;

	  int d = n/len;
	  if (n%len>0)
	    d++;
	  len *= d;

	  for(i=0;i<tableSize_;i++)
	    buckets_[i] = new PrLinkedList<PrHashTableEntry> (len);

	  bitmap_ = new PrBitmap(maxNumItems_);
	  heap_ = new PrHashTableEntry[maxNumItems_];
	  for(i=0;i<maxNumItems_;i++)
	    heap_[i].id(i);
      }
    else
      {
	  for(i=0;i<tableSize_;i++)
	    buckets_[i] = new PrLinkedList<PrHashTableEntry> (PR_LINKEDLIST_SIZE_UNLIMITED);
      }
}

PrHashTableImpl::~PrHashTableImpl()
{
    int i;
    if (maxNumItems_ != PR_HASHTABLEIMPL_NUM_ITEMS_UNLIMITED)
      {
	  assert(items_ == maxNumItems_ - bitmap_->numClear()); 
	  delete bitmap_;
	  delete[] heap_;
      }
    else
      {
	  for(i=0;i<tableSize_;i++)
	    {
		PrLinkedList<PrHashTableEntry> *list = buckets_[i];
		PrHashTableEntry *item = (PrHashTableEntry *)list->firstItem();
		while(item != NULL)
		  {
		      delete item;
		      item = (PrHashTableEntry *)list->nextItem();
		  }
	    }
      }
    for(i=0;i<tableSize_;i++)
      delete buckets_[i];
    delete[] buckets_;
}

/* 
 * Add the new value under the given key.  If the key is already
 * used, just replace the value with the new one.  Otherwise, add
 * a new element to the table.
 */
void 
PrHashTableImpl::newItem(void *data, void *key)
{
  PrHashTableEntry *elem = FindEntry(key);
  if (elem == NULL) 
    {
      int loc = hash(key);
      PrHashTableEntry *newEntry;

    if (maxNumItems_ != PR_HASHTABLEIMPL_NUM_ITEMS_UNLIMITED)
      {
	  int n=bitmap_->findAndSet();
	  assert(n>=-1);
	  newEntry = heap_+n;
	  assert(newEntry->id() == n);
	  newEntry->data(data);
	  newEntry->key(key);
      }
    else
      newEntry = new PrHashTableEntry(data,key);

      buckets_[loc]->newItem(newEntry);
      items_++;
    } 
  else 
    {
      elem -> data(data);
    }
}

void *
PrHashTableImpl::deleteItem(void * key)
{
    void *data = 0;
    PrHashTableEntry *elem = FindEntry(key);

    if (elem != NULL) 
      {
	  int loc = hash(key);
	  elem = buckets_[loc]->deleteItem(elem);
	  data = elem->data();

	  if (maxNumItems_ != PR_HASHTABLEIMPL_NUM_ITEMS_UNLIMITED)
	    bitmap_->clear(elem->id());
	  else
	    delete elem;

	  items_--;
      }
    return data;
}

/* 
 * Return the value or NULL for a given key
 */
void *
PrHashTableImpl::item(void * key) const
{
  PrHashTableEntry *elem = FindEntry(key);
  if (elem != NULL) 
    return elem -> data();
  return NULL;
}

/*
 * firstItem
 * return head of list and set for nextItem () call
 */
void *
PrHashTableImpl::firstItem () const
{
  ((PrHashTableImpl *)this)->curListNum_ = 0;
  while (buckets_[curListNum_]->items() <= 0)
    {
      ((PrHashTableImpl *)this)->curListNum_++;
      if (curListNum_ >= tableSize_) return NULL;
    }
  void *item = buckets_[curListNum_]->firstItem()->data();

  return (item);
}

/*
 * nextItem
 * return next item and update the current entry
 */
void *
PrHashTableImpl::nextItem () const
{
  void *item;

  PrHashTableEntry *entry = buckets_[curListNum_]->nextItem();
  if (entry == NULL)
    {
      ((PrHashTableImpl *)this)->curListNum_++;
      if (curListNum_ >= tableSize_) return NULL;
      while (buckets_[curListNum_]->items() <= 0)
	{
	  ((PrHashTableImpl *)this)->curListNum_++;
	  if (curListNum_ >= tableSize_) 
	    return NULL;
	}
      item = buckets_[curListNum_]->firstItem()->data();
    }
  else
    item = entry->data();
  return (item);
}

/* 
 * Return the element for the given string, or NULL if the key
 * is not found.
 */
inline PrHashTableEntry *
PrHashTableImpl::FindEntry(void * key) const 
{
  PrLinkedList<PrHashTableEntry> *list = buckets_[hash(key)];
  PrHashTableEntry *item = (PrHashTableEntry *)list->firstItem();
  while(item != NULL)
    {
      if (equal(item->key(),key))
	return item;
      item = (PrHashTableEntry *)list->nextItem();
    }
  return NULL;
}
