//-----------------------------------------------------------------------------
// Copyright (c) 1994,1995 Southeastern Universities Research Association,
//                         Continuous Electron Beam Accelerator Facility
//
// This software was developed under a United States Government license
// described in the NOTICE file included as part of this distribution.
//
// CEBAF Data Acquisition Group, 12000 Jefferson Ave., Newport News, VA 23606
// Email: coda@cebaf.gov  Tel: (804) 249-7101  Fax: (804) 249-7363
//-----------------------------------------------------------------------------
// 
// Description:
//	 rsvcHash: rsvc hash table keyed by a variable length string
//                    Open Hash with buckets implemented by single linked lists
//    
//              Note: void *s are stored inside the table. This class
//                    will not manage these pointers. Callers have to
//                    manage these pointers
// 
//              Note: this is unsafe C++ practice. Use at your own risk
//              
//            Reason: It is so difficult to use a template class inside
//                    a shared library. (Cfront based C++ compiler cannot
//                    instantiate a template class during compilation time
//	
// Author:  Jie Chen
//       CEBAF Data Acquisition Group
//
// Revision History:
//   rsvcHash.cc,v
// Revision 1.3  1998/02/26  19:10:24  chen
// provide direct access to array of linked list
//
// Revision 1.2  1998/02/20  19:29:54  chen
// Remove debug print
//
// Revision 1.1  1998/01/22  17:08:13  akers
// Addition of new NameServer
//
//
//
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
#include "rsvcHash.h"

// the following are 10 prime numbers. Each is twice of value of the
// one in front of it.

static unsigned int rsvc_prime_table[] = 
{11, 97, 199, 499, 997, 1999, 4999, 9973, 25013, 49999, 99991};

static unsigned int rsvc_prime_table_size = 11;

static unsigned int 
rsvc_pick_prime (unsigned max, int* index)
{
  unsigned int diff = 12345678;
  unsigned int tmp;
  
  for (int i = 0; i < rsvc_prime_table_size; i++) {
    tmp = abs ((int)((int)max - (int)rsvc_prime_table[i]));
    if (tmp < diff) {
      diff = tmp;
      *index = i;
    }
  }
  return rsvc_prime_table[*index];
}

// a simple string hash function
unsigned int rsvcHashFunc (const char *src)
{
  unsigned int hash = 0, g;

  for (int i = 0; src[i] != '\0'; i++){
    hash = (hash << 4) + src[i];
    // assume 32 bit integer
    if (g = hash & 0xf0000000){
      hash ^= g >> 24;
      hash ^= g;
    }
  }
  return hash;
}


//======================================================================
//	class rsvcHash implementation
//======================================================================

// lock_ has default constructor, so compiler will do it for us

rsvcHash::rsvcHash (unsigned int max, unsigned int loadfactor)
:lf (loadfactor)
{
#ifdef _TRACE_OBJECTS
  printf ("Create rsvcHash Class Objects\n");
#endif

  // figure out nearest prime number for max
  tablesize = rsvc_pick_prime (max, &primeindex);
#ifdef _RSVC_DEBUG
  /*printf ("table size for str hash is %d, index is %d\n", tablesize,
	  primeindex);*/
#endif
  // rsvcSlist has a default constructor, so one can create an array of the list
  buckets = new rsvcHSlist[tablesize];
  assert (buckets);
}

rsvcHash::~rsvcHash (void)
{
#ifdef _TRACE_OBJECTS
  printf ("Delete rsvcHash Class Objects\n");
#endif
  delete []buckets;
  buckets = 0;
}

void
rsvcHash::rehash (void)
{
  if (primeindex == rsvc_prime_table_size - 1) {
    fprintf (stderr, "Cannot exapnd the hash table size %d anymore\n",
	     rsvc_prime_table[primeindex]);
    return;
  }
  // remember old values
  unsigned int oldtablesize = tablesize;
  rsvcHSlist*   oldbuckets = buckets;

  // create new values
  tablesize = rsvc_prime_table[primeindex + 1];
  buckets = new rsvcHSlist[tablesize];
  assert (buckets);

#ifdef _RSVC_DEBUG
  /* fprintf (stderr, "Expand hash table from %d to %d (reaching lf %d) \n",
	   oldtablesize, tablesize, lf);*/
#endif
  primeindex ++;

  rsvcHashable* elem = 0;
  for (int i = 0; i < oldtablesize; i++) {
    rsvcHSlistIterator site (oldbuckets[i]);
    for (site.init (); !site; ++site) {
      elem = site ();
      add (elem);
    }
  }

  // remove old memory
  delete []oldbuckets;
}
    


int 
rsvcHash::isEmpty()
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard (lock_);
#endif
  // if any table is non-empty, return 0
  for (int i = 0; i < tablesize; i++)
    if (!buckets[i].isEmpty_i())
      return 0;

  // all empty
  return 1;
}

void
rsvcHash::deleteAllValues()
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard (lock_);
#endif
  // delete all values from a hash table
  // clear the elements from each of teh buckets
  for (int i = 0; i < tablesize; i++)
    buckets[i].deleteAllValues_i();
}

unsigned int 
rsvcHash::hash(rsvcHashable* ele) const
{
  // return hashed value of key
  return (ele->hash () % tablesize);
}

void
rsvcHash::add (rsvcHashable* newele)
{
  buckets[hash (newele)].add (newele);
  if (buckets[hash (newele)].count () > lf) {
#ifdef _RSVC_DEBUG
/*    fprintf (stderr, "Hash buckets %d has %d elements > load factor %d, resize\n", 
	     hash (newele), buckets[hash (newele)].count (), lf);*/
#endif
    rehash ();
  }
}

rsvcHSlist&
rsvcHash::bucketRef (rsvcHashable* ele)
{
  return (buckets[hash (ele)]);
}

rsvcHSlist&
rsvcHash::bucketRef (unsigned int hashcode)
{
  return (buckets[hashcode % tablesize]);
}

void
rsvcHash::bucketList (rsvcHSlist* &lists, unsigned int& size)
{
  lists = buckets;
  size = tablesize;
}


void
rsvcHash::asciiDump (FILE* fd)
{
  fprintf (fd, "Hash table looks like the following\n");
  fprintf (fd, "====================================================\n");
    
  for (int i = 0; i < tablesize; i++) 
    fprintf (fd, "Bucket[%d] contains %d elements\n", i, buckets[i].count ());
  fprintf (fd, "====================================================\n");
}


//======================================================================
//	class rsvcHashIterator implementation
//======================================================================
rsvcHashIterator::rsvcHashIterator (rsvcHash& v)
:base(v), currentIndex(0), itr(0)
{
#ifdef _TRACE_OBJECTS
  printf ("Create rsvcHashIterator Class Object \n");
#endif
  // no further initialization
}

rsvcHashIterator::~rsvcHashIterator (void)
{
#ifdef _TRACE_OBJECTS
  printf ("Delete rsvcHashIterator Class Object \n");
#endif
  currentIndex = 0;
  if (itr)
    delete itr;
}

int 
rsvcHashIterator::init (void)
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard (lock_);
#endif

  // initialize iterator, 
  // start search with first bucket
  currentIndex = 0; 
  itr = 0;
  return getNextIterator(); 
}

rsvcHashable *
rsvcHashIterator::operator() (void)
{
  // return current element
  return (*itr)();
}

int 
rsvcHashIterator::operator ! (void)
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard (lock_);
#endif

  // test if there is a current element
  return itr != 0;
}

int 
rsvcHashIterator::operator ++ (void)
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard (lock_);
#endif

  // see if current iterator can be advanced
  if (itr && itr->forward_i ()) 
    return 1;

  // if not, get next iterator
  currentIndex++;
  return getNextIterator();
}

void 
rsvcHashIterator::operator = (rsvcHashable* val)
{
  // change the current value
  (*itr) = val;
}

void
rsvcHashIterator::removeCurrent (void)
{
#if defined (RSVC_USE_THREAD) && defined (_REENTRANT)
  cpMutexGuard guard (lock_);
#endif

  if (itr) 
    itr->removeCurrent_i ();
}

int 
rsvcHashIterator::getNextIterator (void)
{
  // if there is an old iterator, delete it
  if (itr != 0) 
    delete itr;

  // now search for a new one
  for (; currentIndex < base.tablesize; currentIndex++){
    // generate a new iterator at the current point
    itr = new rsvcHSlistIterator (base.buckets[currentIndex]);
    assert(itr != 0);

    // if it has at least one element, we're done
    if (itr->init_i())
      return 1;

    // otherwise delete it, try again
    delete itr;
  }
  // all out of iterators, can quit
  itr = 0;
  return 0;
}
