/*******************************************************************************
* YORKTOWN ADVANCED SGML PARSER (YASP)                                         *
*         An SGML Parser conforming to International Standard ISO 8879 --      *
*         Standard Generalized Markup Language                                 *
*------------------------------------------------------------------------------*
* Written 1987 - 1993 by                                                       *
*         Pierre G. Richard                                                    *
*         IBM T.J. Watson Research Center                                      *
*         Yorktown Heights, New York                                           *
*         petrus@watson.ibm.com                                                *
*------------------------------------------------------------------------------*
* FUNCTION NAME    = YASP / General Library                                    *
* STATUS           = Version 0, Release 1, Level 17 and up                     *
* COMPONENT NAME   = hash.c                                                    *
* DESCRIPTIVE NAME = install and retrieve symbols using a hash technique       *
* DATE_WR          = 01/11/1987                                                *
* AUTHOR           = Pierre G. Richard - PETRUS at YKTVMX                      *
*                                                                              *
* FUNCTIONAL DESCRIPTION =                                                     *
*                                                                              *
* Typical calls are:                                                           *
*                                                                              *
* At initialization:                                                           *
*     +-------------------------------------+                                  *
*     |scope_id = (void *)ehsh_ini(hashsiz) |                                  *
*     |uint hashsiz;                        |                                  *
*     +-------------------------------------+                                  *
* returns a "scope_id" used by further calls, to reference this scope of       *
* members.                                                                     *
*                                                                              *
* To access to a member, even a new one:                                       *
*     +----------------------------------------------+                         *
*     |EHSH *ehsh_acc(scope_id,var_name_p,create_it) |                         *
*     |void *scope_id;                               |                         *
*     |uchar  *var_name_p;                           |                         *
*     |boolean create_it;                            |                         *
*     +----------------------------------------------+                         *
* If "create_it" is FALSE, the code just tries to find a member; it returns    *
* either an EHSH pointer (member found) or a NULL pointer (not found).         *
*                                                                              *
* If "create_it" is TRUE, a member will be created if it didn't exist; then    *
* an EHSH pointer is *always* returned.  If the member is created, the         *
* "var_p" in the EHSH strusture is set to NULL: this would allow the caller    *
* to recognize a new member from an existing one.                              *
*                                                                              *
* IMPORTANT NOTE: var_p must be set by the caller to a mallocated area         *
*                 (or left to NULL):  at unload time, it will be freed.        *
*                                                                              *
* To associate a structure (rather than just a pointer) to a member:           *
*     +-----------------------------------------------+                        *
*     |void **ehsh_lnk(scope_id,var_name_p,size)      |                        *
*     |void *scope_id;                                |                        *
*     |uchar *var_name_p;                             |                        *
*     |uint size;                                     |                        *
*     +-----------------------------------------------+                        *
*  Returns a pointer to a structure of "size" associated to a member           *
*  in a given scope.                                                           *
*  If the member is new, the structure is created and zeroed.                  *
*                                                                              *
* To traverse all members sequentially:                                        *
*     +---------------------------------------+                                *
*     |ehsh_tvr(scope_id,check_function,arg0) |                                *
*     |void *scope_id;                        |                                *
*     |void (*check_function)(void *, EHSH *) |                                *
*     |void *arg0;                            |                                *
*     +---------------------------------------+                                *
*                                                                              *
* At termination:                                                              *
*     +-------------------------------------------+                            *
*     |uint ehsh_uld(scope_id,item_size, where_p) |                            *
*     |void *scope_id;                            |                            *
*     |uint item_size;                            |                            *
*     |void **where_p;                            |                            *
*     +-------------------------------------------+                            *
* "stringize" the hashtable and "unload" it in core, put the address of the    *
* "unloaded" area in *where_p, return the size.                                *
*                                                                              *
* This will permit the caller to write the hashtable on an external device,    *
* as in: io_vput(fh,*where_p,size); see comments in the module.                *
*                                                                              *
* To reload the "unloaded" hashtable:                                          *
*     +-------------------------------+                                        *
*     |void *shsh_lod(where,itembase) |                                        *
*     |void *itembase;                |                                        *
*     +-------------------------------+                                        *
*      - where is the address of the "unloaded" hash table                     *
*        (obtained for example by: io_vget(fh,&where)                          *
*      - itembase is the address of the sequential array of hashed items.      *
*                                                                              *
* Return a "hashtable" pointer, to be used subsequently by shsh_fnd.           *
*                                                                              *
* Then:                                                                        *
*     +------------------------------------------------+                       *
*     |void *shsh_fnd(hashtab,var_name_p)              |                       *
*     |void *hashtab;                                  |                       *
*     |uchar *var_name_p;                              |                       *
*     +------------------------------------------------+                       *
* will try to find the item named in *var_name_p.                              *
*                                                                              *
* CHANGE HISTORY =                                                             *
* Number Date     Inits    Change & reason (brief)                             *
*      1 07/22/87 PETRUS   Keep the hashtable - Make it more versatile         *
*      2 08/03/87 PETRUS   Collision List in ascending order (faster)          *
*      3 02/25/88 PETRUS   Simplified version / Do not need patch              *
*      4 04/09/88 PETRUS   Parameter: hashsize saved at init time              *
*      5 10/16/88 PETRUS   Normalizations (general tool, rather than sgml)     *
*      6 02/07/90 PETRUS   Make stringized hash extendable (for entities)      *
*******************************************************************************/

/*-------------+
|Include Files |
+-------------*/
#include "machine.h"
#include "portable.h"
#include "yaspapi.h"
#include "global.h"
#include "usrlib.h"
#include "hash.h"

/*------------------------- This could be "shsh.h" ---------------------------*/
typedef struct {              /* This defines the header of each item */
   union {                    /* name */
      OFS ofs;                /* offset of the name (when unloaded only) */
      uchar *p;               /* address when in core */
   }name;
}IHDR;

typedef struct t_XIHDR {      /* This defines the extended header */
   struct t_XIHDR *next;      /* next or 0 if none */
   IHDR  ihdr;                /* name */
}XIHDR;

typedef union {               /* hash array (stringized) */
   struct {                   /* for hastable[0] */
      ushort modulo;
      ushort item_size;
      struct {
        uint extendable: 1;   /* TRUE if the shsh table can have extensions */
        uint future_use: 7;
      }is;
   }f;
   struct {                   /* for hashtable[1..modulo] */
      union {                 /* item */
         uint ofs;            /* offset (only when unloaded) */
         void *p;             /* IHDR address when in core */
      }item;
      uint collision_count;
   }o;
}HT;
/*----------------------------------------------------------------------------*/

#define HASHSIZE (((EHTBE *)hashtable-1)->size)

typedef union {
   GA_P gbla_p;
   int  size;
   EHSH *ehsh_p;        /* to align on an array of (EHSH *) */
}EHTBE;

/*--------------------------------------------------------------------ehsh_ini-+
|Init the hash table - Keep the hashsize in hashtable[-1]                      |
+-----------------------------------------------------------------------------*/
void *P_FCT ehsh_ini(
   GA_P gbla_p,
   uint hashsize)
{
   EHTBE *hashtable;

   hashtable = (EHTBE *)zalloc((2+hashsize)*sizeof(EHTBE));
   hashtable++->gbla_p = gbla_p;
   hashtable++->size = hashsize;
   return((void *)hashtable);
}

/*--------------------------------------------------------------------ehsh_acc-+
|Access a member and, if not found:                                            |
|     - if create_it is TRUE: create a new one, zeroe ehsh_p->var_p            |
|     - if create_it is FALSE: return a NULL ptr                               |
|Returns ehsh_p                                                                |
|The collision list is kept in alphabetic order, to speed up the process.      |
|See also the implementation note in ety_deco (ODTENTY.C).                     |
+-----------------------------------------------------------------------------*/
EHSH * P_FCT ehsh_acc(
   void  *hashtable,
   uchar *var_name_p,
   boolean create_it)
{
   GA_P gbla_p = ((EHTBE *)hashtable - 2)->gbla_p;
   register uchar   *c_p;
   register EHSH **ehsh_pp;
   int hashval, cond;
   uint i;
   EHSH *ehsh_p;

   /*----------------------------------------+
   |point the EHSH pointer in the hash table |
   +----------------------------------------*/
   for (hashval=0, c_p = var_name_p; *c_p; hashval += *c_p++);

   /*---------------+
   |look for a match|
   +---------------*/
   for (
      ehsh_pp = &(((EHTBE *)hashtable + hashval%HASHSIZE)->ehsh_p);
      ;
      ehsh_pp = &(*ehsh_pp)->next ) {
      if ((!*ehsh_pp)||                         /* No more ehsh */
         ((cond=strcmp(var_name_p,(*ehsh_pp)->name_p)) < 0)) {
         if (!create_it) return((EHSH *)0);
         ehsh_p = malloc(sizeof(EHSH) + (i=1+strlen(var_name_p)));
         ehsh_p->next = *ehsh_pp;
         ehsh_p->var_p = (void *)0;
         ehsh_p->name_p = (uchar *)ehsh_p + sizeof(EHSH);
         memcpy(ehsh_p->name_p,var_name_p,i);
         *ehsh_pp = ehsh_p;
         break;
      }else if (!cond) {                       /* match found */
         ehsh_p = *ehsh_pp;
         break;
      }
   }
   return(ehsh_p);
}

/*--------------------------------------------------------------------ehsh_fnd-+
|Get the structure associated to a member,                                     |
|or returns a NULL pointer if not found.                                       |
+-----------------------------------------------------------------------------*/
void *P_FCT ehsh_fnd(
   void *hashtable,
   uchar *name_p)
{
   EHSH *ehsh_p;
   if (!(ehsh_p = ehsh_acc(hashtable,name_p,FALSE))) {
      return((void *)0);
   }else {
      return(ehsh_p->var_p);
   }
}

/*--------------------------------------------------------------------ehsh_lnk-+
|Link a structure to a member in a given hash table.                           |
|If the member is new, create the structure and zero it.                       |
|Return a pointer to the structure.                                            |
|ehsh_p->var_p stores the address of the structure.                            |
+-----------------------------------------------------------------------------*/
void *P_FCT ehsh_lnk(
   void  *hashtable,
   uchar *name,
   uint   size)
{
   EHSH *ehsh_p;
   GA_P gbla_p = ((EHTBE *)hashtable - 2)->gbla_p;

   if (!(ehsh_p = ehsh_open(hashtable,name))->var_p) ehsh_p->var_p=zalloc(size);
   return(ehsh_p->var_p);
}

/*--------------------------------------------------------------------ehsh_tvr-+
|Call "check function" for all variables installed/solved                      |
+-----------------------------------------------------------------------------*/
void P_FCT ehsh_tvr(
   void *hashtable,
   void (P_FCT *checkf)(void STACK_BASED *, EHSH *),
   void STACK_BASED *arg0)
{
   register EHSH *ehsh_p;
   EHTBE *ehtbe_p, *ehtbe_pM;

   /*----------------------------------+
   |Descend sequentially the Hashtable |
   +----------------------------------*/
   for (ehtbe_p = (EHTBE *)hashtable, ehtbe_pM = (EHTBE *)hashtable + HASHSIZE;
      ehtbe_p < ehtbe_pM; ++ehtbe_p) {
      /*------------------------------------------------+
      |Traverse the collision chain for each hash entry |
      +------------------------------------------------*/
      for (ehsh_p = ehtbe_p->ehsh_p; ehsh_p; ehsh_p = ehsh_p->next) {
         (*checkf)(arg0,ehsh_p);               /* call caller's check */
      }
   }
}

/*--------------------------------------------------------------------ehsh_uld-+
|Unload (stringize and dis-allocate) the ehsh table.                           |
|Returns the size of a mallocated area that contains the unloaded table.       |
|                                                                              |
|Caller is deemed to have made a copy of all items (pointed by non-zero var_p),|
|in a sequential array (each entry being of item_size).                        |
|If a NULL pointer is in var_p, this means the entry was not used and          |
|therefore IT IS NOT ENTERED in the unloaded hashtable.                        |
|Otherwhise, the item must have been mallocated (ehsh_open + caller, or        |
|ehsh_lnk): it is then freed by this routine.                                  |
|                                                                              |
|The "unloaded" area is mallocated: it's the responsability of the caller      |
|to free it.                                                                   |
+-----------------------------------------------------------------------------*/
uint P_FCT ehsh_uld(
   void   *hashtable,
   uint    item_size,
   boolean is_extendable,
   void  **where_p)
{
   GA_P gbla_p = ((EHTBE *)hashtable - 2)->gbla_p;
   HT *ht_p;
   uint size;
   register EHSH *ehsh_p, *ehsh_pS;
   EHTBE *ehtbe_p, *ehtbe_pM;
   uint collision_count = 0;
   uint item_ofs = 0;

   size = (1+HASHSIZE)*sizeof(HT);
   if (is_extendable) size += (HASHSIZE * sizeof(void *));
   *where_p = (void *)(ht_p = (HT *)malloc(size));
   ht_p->f.modulo = HASHSIZE;
   ht_p->f.is.extendable = is_extendable;
   ht_p++->f.item_size = item_size;
   for (ehtbe_p = (EHTBE *)hashtable, ehtbe_pM = (EHTBE *)hashtable + HASHSIZE;
      ehtbe_p < ehtbe_pM; ++ehtbe_p, ++ht_p) {
      ht_p->o.item.ofs = item_ofs;
      collision_count = 0;
      if ((ehsh_p = ehtbe_p->ehsh_p) != (EHSH *)0) {    /* real entry */
         do {
            if (ehsh_p->var_p) {
               free(ehsh_p->var_p);
               item_ofs += item_size;
               ++collision_count;
            }
            ehsh_pS = ehsh_p->next;
            free(ehsh_p);
         }while ((ehsh_p=ehsh_pS) != (EHSH *)0);
      }
      ht_p->o.collision_count = collision_count;
   }
   free((uchar *)((EHTBE *)hashtable - 2));
   if (is_extendable) memset(ht_p,0,HASHSIZE * sizeof(void *));
   return(size);

   /********* io_vput(fh,*where_p,size); ************/
}

/*******************************************************************************
*                                                                              *
*         - These routines handle the "stringized" hashtable -                 *
*                                                                              *
*******************************************************************************/

/*--------------------------------------------------------------------shsh_lod-+
|Relocate an "ehsh_unloaded" hash table                                        |
|Itembase is the address of an array of the hashed items.                      |
+-----------------------------------------------------------------------------*/
void *P_FCT shsh_lod(
   void *uwhere,
   void *itembase)
{
   register HT *ht_p = (HT *)uwhere;
   uint i;

   /********** io_vget(fh,&uwhere); ***************************/
   for (i=ht_p++->f.modulo; i--; ++ht_p) {
      if (!ht_p->o.collision_count) {
         ht_p->o.item.p = (void *)0;
      }else {
         ht_p->o.item.p = (char *)itembase + ht_p->o.item.ofs;
      }
   }
   return((void *)((HT *)uwhere + 1));
}

/*--------------------------------------------------------------------shsh_fnd-+
|Find a member in a loaded (stringized) hashtable                              |
|The collision list is kept in alphabetic order, to speed up the process.      |
|** OPTIMIZED **                                                               |
+-----------------------------------------------------------------------------*/
void *P_FCT shsh_fnd(
   void *hashtab,
   uchar *var_name_p)
{
   register void *a_p;
   uint collision_count, item_size, hashval, modulo;
   boolean is_extendable;

   {
      register uchar *c_p;
      for (hashval=0, c_p = var_name_p; *c_p; hashval += *c_p++);
   }
   item_size = ((HT *)hashtab-1)->f.item_size;
   is_extendable = ((HT *)hashtab-1)->f.is.extendable? TRUE : FALSE;
   modulo = ((HT *)hashtab-1)->f.modulo;
   collision_count =
      ((HT *)(a_p=(void *)((HT *)hashtab + (hashval %= modulo))))
      ->o.collision_count;

   if (collision_count) {
      register int cond;
      a_p = ((HT *)a_p)->o.item.p;
      for (;;) {
         if ((cond = strcmp(var_name_p,((IHDR *)a_p)->name.p)) != 0) {
            if ((cond > 0) && (--collision_count)) {
               a_p = (void *)((char *)a_p + item_size);
            }else {
               break;
            }
         }else {
            return(a_p);
         }
      }
   }
   if (is_extendable) {
      register int cond;
      a_p = *(void **)
            ((uchar *)hashtab+((modulo*sizeof(HT))+(hashval*sizeof(void *))));
      while (a_p) {
         if ((cond = strcmp(var_name_p,((XIHDR *)a_p)->ihdr.name.p)) !=0) {
            if (cond > 0) {
               a_p = ((XIHDR *)a_p)->next;
            }else {
               break;
            }
         }else {
            return(&(((XIHDR *)a_p)->ihdr));
         }
      }
   }
   return((void *)0);
}

/*--------------------------------------------------------------------shsh_add-+
|Add a new member in the extended list.                                        |
|The collision list is kept in alphabetic order, to speed up the process.      |
+-----------------------------------------------------------------------------*/
void * P_FCT shsh_add(
   GA_P   gbla_p,
   void  *hashtab,
   uchar *var_name_p,
   uint   size)
{
   XIHDR **xihdr_pp, *xihdr_p;
   uint i, modulo;
   {
      register uchar *c_p;
      for (i=0, c_p = var_name_p; *c_p; i += *c_p++);
   }
   modulo = ((HT *)hashtab-1)->f.modulo;
   xihdr_pp=(XIHDR **)(
      (uchar *)hashtab+((modulo*sizeof(HT))+(sizeof(void *)*(i%modulo)))
   );
   while ((*xihdr_pp) && (strcmp(var_name_p,(*xihdr_pp)->ihdr.name.p) > 0)) {
      xihdr_pp = &(*xihdr_pp)->next;
   }
   xihdr_p = (XIHDR *)malloc(sizeof(XIHDR)-sizeof(IHDR)+ size
      + (i=1+strlen(var_name_p)));
   xihdr_p->ihdr.name.p = (uchar *)xihdr_p + (sizeof(XIHDR)-sizeof(IHDR)+size);
   xihdr_p->next = *xihdr_pp;
   memcpy(xihdr_p->ihdr.name.p,var_name_p,i);
   *xihdr_pp = xihdr_p;
   return(&(xihdr_p->ihdr));
}
/******************************************************************************/
