/*
   HASH.H
   Declare interface to hash routines

   $Id: hash.h,v 1.1 1993/08/27 18:32:09 munro Exp $
 */
/*    Copyright (c) 1994.  The Regents of the University of California.
                    All rights reserved.  */

#ifndef HASH_H
#define HASH_H

/* ------------------------------------------------------------------------ */

typedef struct HashTable HashTable;

extern long hashIndex;  /* set by HashFind, HashAdd, etc. */

extern int HashFind(const HashTable *table, const char *name, long n);
/* Note-- n is the exact length of name, or n==0 to use strlen(name)
   Usage:
     if (HashFind(table, name, n)) {
       ... name exists in table, and was the hashIndex +1st item
           added to the table ...
     } else {
       ... name does not exist, and hashIndex is the value of the
           hashing function (a slot index) ...
     }
 */

extern int HashAdd(HashTable *table, const char *name, long n);
/* Note-- n is the exact length of name, or n==0 to use strlen(name)
   Usage:
     if (HashAdd(table, name, n)) {
       ... name existed previously in table, as the hashIndex +1st item
           added to the table ...
     } else {
       ... name did not exist previously, and is now the hashIndex +1st
           item added to the table ...
       ... use the HASH_MANAGE macro to manage any lists associated with
           this hash table, in case they need to be lengthened ...
     }
   Note well: The name is copied if added to the table, so the caller
              should dispose of it as appropriate.
 */

/* ------------------------------------------------------------------------ */

extern int hashRealloc;  /* set by HashAdd if it returned 0 and if
			    the call forced table->maxItems to grow */

#define HASH_MANAGE(table, type, list) \
  if (hashRealloc) (list)= p_realloc((list), (table).maxItems*sizeof(type))
/* NOTE: If you use this, you need to include defmem.h or otherwise
         declare Yrealloc (same semantics as ANSI standard realloc).
   Usage:
     HashTable table;   == associates name with index into table.names ==
     Object *list;      == typically, one or more lists in addition to
			   table.names are maintained representing the
			   objects which bear the names ==
     ...
     if (HashAdd(&table, name, n)) {
       == often, it is an error to add a duplicate name ==
     } else {
       HASH_MANAGE(table, Object, list);  == lengthen list if reqd ==
       list[hashIndex]= value_of_name;
     }
 */

/* ------------------------------------------------------------------------ */

extern void HashInit(HashTable *table, int estSize);
/* Pass HashInit the estimated final nItems for the table to bypass
   the rehashing which otherwise takes place every with every factor
   of two size increase.  A HashTable with all its members 0 is also
   a legal initialization; this is the situation after HashClear.  */

extern void HashClear(HashTable *table);
/* Clear a hash table, freeing all associated memory.  */

extern void HashShrink(HashTable *table);
/* Shrink maxItems to nItems, and rehash if the number of slots
   can be reduced.  Follow this with the HASH_MANAGE macro if the
   table has associated lists.  */

extern void HashRemove(HashTable *table, long index0);
/* Removing an item from a hash table is a very expensive operation,
   unless it is one of the few elements most recently added to the
   table.  The index0 must have been returned as the hashIndex for a
   previous call to HashFind or HashAdd.  */

extern void HashSwap(HashTable *table, long index0, long index1);
/* Swaps the item->index and names corresponding to the two
   entries, to reorder the names list after an incorrectly ordered
   sequence of calls to HashAdd.  */

/* ------------------------------------------------------------------------ */

typedef struct HashItem HashItem;

struct HashTable {
  long nItems, maxItems;  /* used and actual length of names array */
  char **names;
  long nSlots;            /* length of items, or number of hash slots */
  HashItem **items;
};

struct HashItem {
  HashItem *next;  /* next item in this hash slot */
  long index;      /* index into names array in associated HashTable */
};

/* ------------------------------------------------------------------------ */

typedef struct HashXTable HashXTable;
struct HashXTable {
  long nItems, maxItems;  /* used and actual length of names array */
  long nSlots;            /* length of items, or number of hash slots */
  HashItem **items;
};

extern int HashXFind(const HashXTable *table, const void *key, long n,
		     int (*Compare)(void *keyTable,
				    long index, const void *key),
		     void *keyTable);
/* Notes-- 1. n>0 is the exact length of key (uses HashN)
           2. Compare(keyTable, index, key) should return 0 when
	      the key matches the index-th entry of the keyTable
   Usage:
     if (HashXFind(table, key, n, Compare, keyTable)) {
       ... key exists in (table,keyTable), and was the hashIndex +1st
           item added to the table ...
     } else {
       ... key does not exist, and hashIndex is the value of the
           hashing function (a slot index) ...
     }
 */

extern int HashXAdd(HashXTable *table, const char *key, long n,
		    int (*Compare)(void *keyTable,
				   long index, const void *key),
		    void *(*Index)(void *keyTable, long index),
		    void *keyTable);
/* Notes-- 1. n>0 is the exact length of key (uses HashN)
           2. Compare(keyTable, index, key) should return 0 when
	      the key matches the index-th entry of the keyTable
           3. Index(keyTable, index) should return the key for
              the index-th entry of the keyTable (required for rehash)
   Usage:
     HashXTable *table;
     KeyedObject *keyTable;
     ...
     if (HashXAdd(table, name, n, Compare, Index, keyTable)) {
       ... key existed previously in table, as the hashIndex +1st item
           added to the table ...
     } else {
       ... key did not exist previously, and is now the hashIndex +1st
           item added to the table ...
       HASH_MANAGE(*table, KeyedObject, keyTable);
       keyTable[hashIndex]= object_corresponding_to_key;
       ... use the HASH_MANAGE macro to manage other lists associated with
           this hash table, in case they need to be lengthened ...
     }
 */

extern void HashXClear(HashXTable *table);
/* Clear a hash table, freeing all associated memory.  */

/* ------------------------------------------------------------------------ */

#endif
