/* Generic hash table package */
/* It assumes some suitable definition for CELL
   that can be assigned and passed around (int,
   or char *, for instance) */

typedef struct gent { /* Hash bucket */
    UINT hval;	      /* Hash value (not mod'd by #slots) */
    UINT index;	      /* Index in table */
    CELL ent;	      /* entry */
    CELL other;	      /* other information (up to user) */
    struct gent * next; /* Next bucket */
    } * GENT;

# define GENT_POOL_SIZE 16

typedef struct gent_pool { /* Pool of buckets to speed up allocation */
    struct gent lotsa_gents[GENT_POOL_SIZE];
    UINT next; /* Index of next bucket to allocate */
    struct gent_pool * lastpool; /* Previous pool */
    } * GENTPOOL;

typedef struct { /* Hash table */
    UINT calls;		/* Number of calls */
    UINT probes;	/* Number of probes since last expansion */
    UINT nelts;		/* Number of entries */
    UINT nslots;	/* Number of hash slots (size of "slots") */
    UINT max_elts;	/* Max (before expansion) number of inverses */
    GENT * slots;	/* Array of bucket lists */
    GENT * inverse;	/* Array of pointers to buckets (inverses) */
    GENTPOOL cache;	/* Allocation cache */
    UINT (*hasher)();	/* Subroutine to hash a CELL */
    void (*freer)();	/* Subroutine to free a CELL */
    CELL (*copier)();	/*    "       "  copy "  "   */
    UINT (*tester)();	/*    "       "  test two cells for equality */
    } * GMAP;

extern UINT g_map(GMAP m, CELL t);  /* Returns index, 0 < index <= g_map_size(map) */
				    /* If ent is new, g_map_size(map) increases by one and value returned */
				    /* is equal to the new value.					  */

extern UINT g_inmap(GMAP m, CELL t);

extern GMAP g_new_map(
    UINT (*h)(),
    void (*f)(),
    CELL (*c)(),
    UINT (*t)());

extern UINT g_map_last;

# define g_unmap(m,i) ((m)->inverse[i]->ent)
# define g_other(m,i) ((m)->inverse[i]->other) /* Free for use by user */
# define g_map_size(m) ((m)->nelts)