/* 
 * sc.c
 *
 * x-kernel v3.3
 *
 * Copyright (c) 1996,1993,1991,1990  Arizona Board of Regents
 */

/*============================              ==============================
  ============================  File: sc.c  ==============================
  ============================              ==============================

  Searchable Collections:

  Expanding hash tables with a string key and arbitrary data.

  ========================================================================*/

#include <stdio.h>
#include "sc.h"

extern char *malloc();

#ifdef XMEMTRACK

static int TrackId = 0;

extern char *xMallocTrack(unsigned, int);
extern void xFreeTrack(char *, unsigned, int);
extern int  TrackGetId(char *);

#define xMalloc(s) xMallocTrack(s, TrackId)

#endif

extern void free();

static int   sizes[] = { 5, 7, 17, 31, 67, 131, 257, 521, 1031, 2053,
			4099, 8093, 16193, 32377, 65557, 131071, 262187,
			524869, 1048829, 2097223, 4194371, 8388697,
			16777291 };

#define MAXFILL 	0.375
#define MAXFILLSET      0.5
#define BEGINAT 	2


/*-------------------------------  Hash  -------------------------------

  String Hashing function, from Red Dragon book, plus other.

*/
static unsigned Hash (key, sc)

register unsigned char *key;
Sc       sc;
{
  register unsigned long h=0, g;

  switch (sc->type) {
	 case 0: for (; *key; key++) {
                     h = (h << 4) + *key;
                     if (g = (h & 0xf0000000)) {
                        h = h ^ (g >> 24);
                        h = h ^ g;
                     }
		 }
                 return (unsigned) (h % sc->size);
	 case 1: h = (long) key;
		 return (unsigned) (h % sc->size);
	 case 2: h = ((long) key) >> 2;
		 return (unsigned) (h % sc->size);
  }
  return 0;
}  /* End of Hash .......................................................*/


/*-----------------------------  ScNew  -----------------------------

  Return a new, empty Searchable Collection.

*/
Sc	ScNew (type, isset, size)

int	type, isset, size;
{
  register int i;
  register Sc  sc;

  if (type < 0  ||  type > 2)
     return NULL;
#ifdef XMEMTRACK
  if (TrackId == 0)
    TrackId = TrackGetId("sc: sim");
#endif

  sc = (Sc)xMalloc(sizeof(ScRecord));
  for (i=BEGINAT; i<23; i++) 
    if (size < sizes[i]) {
      sc->size = sizes[i];
      break;
    }
/*   sc->size = sizes[BEGINAT]; */
  if (isset)
     sc->maxCount = sc->size*MAXFILLSET;
  else
     sc->maxCount = sc->size*MAXFILL;
  sc->count = 0;
  sc->type = type;
  sc->isset = isset;
  sc->first = sc->last = NULL;
  sc->table = (TEptr)xMalloc(sc->size*sizeof(_TE));
  for (i=0; i < sc->size; i++) {
      sc->table[i].key = NULL;
      sc->table[i].value = NULL;
  }
  return sc;

}  /* End of ScNew .................................................*/


/*---------------------------  ScCreate  ---------------------------
*/
Sc	ScCreate (type, size)

int	type, size;
{
  return ScNew(type, 0, size);

}  /* End of ScCreate ..............................................*/


/*----------------------------  SetCreate  ---------------------------
*/
Sc	SetCreate (type)

int	type;
{
  return ScNew(type, 1);

}  /* End of SetCreate ..............................................*/


/*----------------------------  ExpandHashTable  --------------------------
*/
static void ExpandHashTable (sc)

register Sc sc;
{
  register TEptr nh, oe, ne, le;
  register int oldHashTableSize=sc->size, i;
  register char *key;
  int      index, isset=sc->isset, ibeg=0;

  for (i=0; sizes[i] <= oldHashTableSize; i++)
      ;
  sc->size = sizes[i];
  if (isset)
     sc->maxCount = sc->size*MAXFILLSET;
  else
     sc->maxCount = sc->size*MAXFILL;
  nh = (TEptr)xMalloc((unsigned)(sc->size*sizeof(_TE)));
  for (i=0; i < sc->size; i++) {
      nh[i].key = NULL;
      nh[i].value = NULL;
  }
  if (isset) {
     for (i=0; i < oldHashTableSize; i++) {
         oe = &sc->table[i];
         key = oe->key;
         if (key == NULL)
	    continue;
         index = Hash(key, sc);
         le = &nh[index];
         le->key = key;
         sc->first = le;
	 ibeg = i + 1;
	 break;
      }
  }
  for (i=ibeg; i < oldHashTableSize; i++) {
      oe = &sc->table[i];
      key = oe->key;
      if (key == NULL)
	 continue;
      index = Hash(key, sc);
      while (1) {
	    ne = &nh[index];
	    if (ne->key == NULL) {
	       ne->key = oe->key;
	       if (isset) {
                  le->value = (void *) ne;
		  le = ne;
	       }
	       else
	          ne->value = oe->value;
	       break;
	    }
	    else {
	       index++;
	       if (index >= sc->size)
		  index = 0;
	    }
      }
  }
  if (isset) {
     sc->last = le;
     le->value = NULL;
  }
#ifdef XMEMTRACK
  xFreeTrack((char *)sc->table, (unsigned)sc->size*sizeof(_TE), TrackId);
#else
  xFree((char *)sc->table);
#endif
  sc->table = nh;

}  /* End of ExpandHashTable .............................................*/


/*----------------------------  ScLookup  -------------------------------

  If sc is a set, return 1 if key is in the set or 0 if it is not.
  If sc is not a set, return the value associated with key in collection sc,
  or 0 if no such pair exists.

*/
void 	*ScLookup(sc, key)

register Sc    sc;
register char *key;
{
  register int   index=Hash(key,sc), type=sc->type;
  register TEptr e;

  if (sc->count == 0)
     return NULL;
  while (1) {
	e = &sc->table[index];
	if (e->key == NULL) {
	   return NULL;
	}
	else if (type) {
	   if (e->key == key) {
	      if (sc->isset)
	         return (void *)1;
	      else
		 return e->value;
	   }
	}
	else if (!strcmp(e->key, key)) {
	   if (sc->isset)
	      return (void *)1;
	   else
	      return e->value;
	}
	if (++index >= sc->size)
	   index = 0;
  }

}  /* End of ScLookup ...................................................*/


/*----------------------------  ScInsert  -------------------------------

  Insert the pair <key, value> into the collection sc, or key into the set sc.

*/
void	ScInsert (sc, key, value)

register Sc    sc;
register char *key;
void	      *value;
{
  register int   index, type=sc->type;
  register TEptr e;

  if (sc->count >= sc->maxCount)
     ExpandHashTable(sc);
  index = Hash(key, sc);
  while (1) {
	e = &sc->table[index];
	if (e->key == NULL) {
	   if (sc->isset  &&  sc->first == NULL)
	      sc->first = e;
	   e->key = key;
	   if (sc->isset  &&  e->value == NULL) {
	      if (sc->last != NULL)
	         sc->last->value = (void *) e;
	      sc->last = e;
           }
	   else if (!sc->isset)
	      e->value = value;
	   sc->count++;
	   return;
	}
	else if (type) {
	   if (e->key == key) {
	      if (!sc->isset)
                 e->value = value;
              return;
           }
	}
	else if (!strcmp(e->key, key)) {
           if (!sc->isset)
              e->value = value;
           return;
        }
        if (++index >= sc->size)
           index = 0;
  }

}  /* End of ScInsert ..................................................*/


/*----------------------------  ScRemove  ------------------------------

  Remove the pair <key, ? > from the collection sc.

*/
int	ScRemove (sc, key)

register Sc    sc;
register char *key;
{
  register int   index, type=sc->type;
  register TEptr e;

  index = Hash(key, sc);
  while (1) {
	e = &sc->table[index];
	if (e->key == NULL)
	   return -1;
	else if (type) {
           if (e->key == key) {
	      e->key = NULL;
	      sc->count--;
	      if (sc->count == 0)
		 sc->first = sc->last = NULL;
	      return 0;
	   }
	}
	else if (!strcmp(e->key, key)) {
	   e->key = NULL;
	   sc->count--;
	   if (sc->count == 0)
	      sc->first = sc->last = NULL;
	   return 0;
	}
	if (++index >= sc->size)
	   index = 0;
  }

}  /* End of ScRemove .................................................*/


/*----------------------------  ScDestroy  ------------------------------

  Free all space previously allocated to sc.

*/
void	ScDestroy (sc)

register Sc  sc;
{
#ifdef XMEMTRACK
  xFreeTrack((char *)sc->table, (unsigned)sc->size*sizeof(_TE), TrackId);
  xFreeTrack((char *)sc, (unsigned)sizeof(ScRecord), TrackId);
#else
  xFree((char *)sc->table);
  xFree((char *)sc);
#endif

}  /* End of ScDestroy ................................................*/


/*-------------------------------  ScClear  -----------------------------

  Empty the collection sc. It does not free any space.

*/
void	ScClear (sc)

register Sc sc;
{
  register int k=0;

  for (k=0; k<sc->size; k++) {
	(sc->table[k]).key = NULL;
	(sc->table[k]).value = NULL;
  }
  sc->count = 0;
  sc->first = NULL;
  sc->last = NULL;

}  /* End of ScClear ...................................................*/


/*-----------------------------  ScPrint  -------------------------------

  Prints all the keys in the Searchable Collection, a key per line.

*/
void	ScPrint (sc)

register Sc sc;
{
  register int k=0;

  printf("\nfirst:%ld, last:%ld, count:%d, type:%d, isset:%d", 
         sc->first,
	 sc->last, sc->count, sc->type, sc->isset);
  if (sc->type == 0) {
     for (k=0; k<sc->size; k++)
	 if ((sc->table[k]).key != NULL)
	    printf ("\n%s  %ld",(sc->table[k]).key,((sc->table[k]).value));
	 else
	    printf(".");
     printf("\n");
  }
  else if (sc->type == 1) {
     for (k=0; k<sc->size; k++)
	 if ((sc->table[k]).key != NULL)
	    printf("\n%ld", (sc->table[k]).key);
     printf("\n");
  }
  else {
     for (k=0; k<sc->size; k++)
	 if ((sc->table[k]).key != NULL)
	    printf("\n%8lx  %s", (sc->table[k]).key, 
		   (sc->table[k].value));
     printf("\n");
  }

}  /* End of ScPrint ...................................................*/