#ifndef _CLIENTDATA
#   ifdef __STDC__
    typedef void *ClientData;
#   else
    typedef int *ClientData;
#   endif /* __STDC__ */
#define _CLIENTDATA
#endif

/*
 * Structure definition for an entry in a hash table.  No-one outside
 * Lx should access any of these fields directly;  use the macros
 * defined below.
 */

typedef struct Lx_HashEntry {
    struct Lx_HashEntry *nextPtr;	/* Pointer to next entry in this
					 * hash bucket, or NULL for end of
					 * chain. */
    struct Lx_HashTable *tablePtr;	/* Pointer to table containing entry. */
    struct Lx_HashEntry **bucketPtr;	/* Pointer to bucket that points to
					 * first entry in this entry's chain:
					 * used for deleting the entry. */
    ClientData clientData;		/* Application stores something here
					 * with Lx_SetHashValue. */
    union {				/* Key has one of these forms: */
	char *oneWordValue;		/* One-word value for key. */
	int words[1];			/* Multiple integer words for key.
					 * The actual size will be as large
					 * as necessary for this table's
					 * keys. */
	char string[4];			/* String for key.  The actual size
					 * will be as large as needed to hold
					 * the key. */
    } key;				/* MUST BE LAST FIELD IN RECORD!! */
} Lx_HashEntry;

/*
 * Structure definition for a hash table.  Clients should never
 * access any fields in this structure.
 */

#define LX_SMALL_HASH_TABLE 4
typedef struct Lx_HashTable {
    Lx_HashEntry **buckets;		/* Pointer to bucket array.  Each
					 * element points to first entry in
					 * bucket's hash chain, or NULL. */
    Lx_HashEntry *staticBuckets[LX_SMALL_HASH_TABLE];
					/* Bucket array used for small tables
					 * (to avoid mallocs and frees). */
    int numBuckets;			/* Total number of buckets allocated
					 * at **bucketPtr. */
    int numEntries;			/* Total number of entries present
					 * in table. */
    int rebuildSize;			/* Enlarge table when numEntries gets
					 * to be this large. */
    int downShift;			/* Shift count used in hashing
					 * function.  Designed to use high-
					 * order bits of randomized keys. */
    int mask;				/* Mask value used in hashing
					 * function. */
    int keyType;			/* Type of keys used in this table. 
					 * It's either LX_STRING_KEYS,
					 * LX_ONE_WORD_KEYS, or an integer
					 * giving the number of ints in a
					 */
    Lx_HashEntry *(*findProc) (struct Lx_HashTable *tablePtr,
	    char *key);
    Lx_HashEntry *(*createProc) (struct Lx_HashTable *tablePtr,
	    char *key, int *newPtr);
} Lx_HashTable;

/*
 * Structure definition for information used to keep track of searches
 * through hash tables:
 */

typedef struct Lx_HashSearch {
    Lx_HashTable *tablePtr;		/* Table being searched. */
    int nextIndex;			/* Index of next bucket to be
					 * enumerated after present one. */
    Lx_HashEntry *nextEntryPtr;	/* Next entry to be enumerated in the
					 * the current bucket. */
} Lx_HashSearch;

/*
 * Acceptable key types for hash tables:
 */

#define LX_STRING_KEYS		0
#define LX_ONE_WORD_KEYS	1

/*
 * Macros for clients to use to access fields of hash entries:
 */

#define Lx_GetHashValue(h) ((h)->clientData)
#define Lx_SetHashValue(h, value) ((h)->clientData = (ClientData) (value))
#define Lx_GetHashKey(tablePtr, h) \
    ((char *) (((tablePtr)->keyType == LX_ONE_WORD_KEYS) ? (h)->key.oneWordValue \
						: (h)->key.string))

/*
 * Macros to use for clients to use to invoke find and create procedures
 * for hash tables:
 */

#define Lx_FindHashEntry(tablePtr, key) \
	(*((tablePtr)->findProc))(tablePtr, key)
#define Lx_CreateHashEntry(tablePtr, key, newPtr) \
	(*((tablePtr)->createProc))(tablePtr, key, newPtr)


extern void	Lx_DeleteHashEntry (
			    Lx_HashEntry *entryPtr);
extern void	Lx_DeleteHashTable (
			    Lx_HashTable *tablePtr);
extern Lx_HashEntry *	Lx_FirstHashEntry (
			    Lx_HashTable *tablePtr,
			    Lx_HashSearch *searchPtr);
extern char *	Lx_HashStats (Lx_HashTable *tablePtr);
extern void	Lx_InitHashTable (Lx_HashTable *tablePtr,
			    int keyType);
extern Lx_HashEntry *	Lx_NextHashEntry (
			    Lx_HashSearch *searchPtr);
