/********************************************************************20**
  
     Name:     common hash functions
  
     Type:     C source file
  
     Desc:     Hashing functions used by various layers.
               (Newer version of functions in cm_bdy1)
  
               Using hash lists in a product:
               ------------------------------

               Wherever a hash list is needed, a corresponding hash list
               control point (CmHashListCp) should be declared. The structure 
               definition of the entries that belong to the hash list must 
               include a declaration of the hash list entry header
               (CmHashListEnt) along with the key for the hash list (this
               may be any scalar or structure type subfield of the entry).
               For example, we need a hash list in a SAP to maintain a table
               of addresses:

               typedef struct xySAPCb       (SAP control block)
               {
                  ...
                  CmHashListCp addrHlCp;    (hash list for addresses)
                  ...
               } XySAPCb;

               typedef struct xyAddrEnt     (hash list entry for an address)
               {
                  ...
                  CmHashListEnt hl;         (hash list entry header)
                  ...
                  XyAddr addr;              (hash list key)
                  ...
               } XyAddrEnt;

               Functions available:
               --------------------

               The functions available for using hash lists are defined
               below. The accompanying comments explain the usage in detail.

               Implementation details:
               -----------------------

               A hash list is identified by its control point
               (CmHashListCp). This control point stores the characteristics
               of the hash list as well as a pointer to the hash list bins.
               The storage for the bins is allocated when the hash list is
               initialized. Each bin is organized as a doubly linked list of
               entries whose key maps to this bin. The hash function used to
               map keys to a bin simply adds up all the octets of the key
               and then divides the sum by the number of bins. Variable size
               keys are allowed. Duplicate keys may be present if explicitly
               allowed; if so, they can be retrieved by supplying a sequence
               number in the find routine. A given structure may be attached
               to more than one hash list if it contains multiple hash list
               entry header fields.

     File:     cm_hash.c
  
     Sid:      cm_hash.c 1.11  -  02/11/00 11:55:45
 
     Prg:      rg
  
*********************************************************************21*/
  
  
/* header include files -- defines (.h) */

#include "envopt.h"        /* environment options */
#include "envdep.h"        /* environment dependent */
#include "envind.h"        /* environment independent */

#include "gen.h"           /* general */
#include "ssi.h"           /* system services */
#include "cm_hash.h"       /* common hash functions */
#include "cm_err.h"        /* common functions error */

/* header include -- typedef structs (.x) */

#include "gen.x"           /* general */
#include "ssi.x"           /* system services */
#include "cm_lib.x"        /* common library functions */
#include "cm_hash.x"       /* common hash functions */


/* local defines */

/* local externs */

/* forward references */

PRIVATE S16 cmHashFuncString  ARGS((CmHashListCp *hashListCp, U8 *key, 
                                         U16 keyLen, U16 *idx));

PRIVATE S16 cmHashFuncDefault ARGS((CmHashListCp *hashListCp, U8 *key, 
                                         U16 keyLen, U16 *idx));

PRIVATE S16 cmHashMatchKey ARGS((U8 *key1, U16 keyLen1, U8 *key2, U16 keyLen2));
PRIVATE S16 cmListInsert   ARGS((CmListEnt *oldEntry, CmListEnt *newEntry));
PRIVATE S16 cmListDelete   ARGS((CmListEnt *entry));

/* functions in other modules */
  
/* public variable declarations */

/* private variable declarations */


/*
 *     private support functions
 */


/*
*
*       Fun:   cmHashFuncString
*
*       Desc:  Computes the hash list index (bin number) for a specified
*              key of type CM_HASH_KEYTYPE_STR. 
*
*              for (length of string)
*                 idx = (31 * idx) + *string;
*
*              return (idx % hash_table_size);
*
*       Ret:   ROK     - successful, *idx contains computed index 
*
*       Notes: None.
*
*       File:  cm_hash.c
*
*/

#ifdef ANSI
PRIVATE S16 cmHashFuncString
(
CmHashListCp       *hashListCp,        /* hash list control point */
U8                 *key,               /* key string */
U16                keyLen,             /* length of key string */
U16                *idx                /* idx to return */
) 
#else
PRIVATE S16 cmHashFuncString (hashListCp, key, keyLen, idx)
CmHashListCp       *hashListCp;        /* hash list control point */
U8                 *key;               /* key string */
U16                keyLen;             /* length of key string */
U16                *idx;               /* idx to return */
#endif
{
   U16             cntr;               /* Index */
   U32             sum;                /* Sum of octets for hash function */

   TRC2(cmHashFuncString)

   sum = 0;

   for (cntr = 0; cntr < keyLen; cntr++)
   {
      sum = (CM_STR_HASHFUNC_CONSTANT * sum) + key[cntr];
   }

   /* if nmbBins is a power of 2, use shift, else use division */
   if (hashListCp->binBitMask != CM_HASH_NOBITMASK)
      *idx = (U16) (sum & hashListCp->binBitMask);
   else
      *idx = (U16) (sum % hashListCp->nmbBins);

   RETVALUE(ROK);

} /* end of cmHashFuncString () */


  
/*
*
*       Fun:   cmHashFuncDefault
*
*       Desc:  Computes the hash list index (bin number) for a specified
*              key of type CM_HASH_KEYTYPE_DEF. 
*
*              Adds up all the octets of the key string
*              and divides the sum by the range to get the desired index.
*
*       Ret:   ROK     - successful, *idx contains computed index 
*
*       Notes: None.
*
*       File:  cm_hash.c
*
*/

#ifdef ANSI
PRIVATE S16 cmHashFuncDefault
(
CmHashListCp       *hashListCp,        /* hash list control point */
U8                 *key,               /* key string */
U16                keyLen,             /* length of key string */
U16                *idx                /* index to return */
) 
#else
PRIVATE S16 cmHashFuncDefault(hashListCp, key, keyLen, idx)
CmHashListCp       *hashListCp;        /* hash list control point */
U8                 *key;               /* key string */
U16                keyLen;             /* length of key string */
U16                *idx;               /* index to return */
#endif
{
   U32             sum;                /* sum of key string octets */

   TRC2(cmHashFuncDefault);

   /* add all bytes of the key */
   sum = 0;
   while (keyLen--)
      sum += (U32) (*key++);

   /* compute index by dividing the range into the sum */

   /* if nmbBins is a power of 2, use shift, else use division */
   if (hashListCp->binBitMask != CM_HASH_NOBITMASK)
      *idx = (U16) (sum & hashListCp->binBitMask);
   else
      *idx = (U16) (sum % hashListCp->nmbBins);

   RETVALUE(ROK);

} /* end of cmHashFuncDefault */

  
/*
*
*       Fun:   cmHashFuncMult24
*
*       Desc:  Computes the hash list index (bin number) for a specified
*              key of type CM_HASH_KEYTYPE_MULT24. 
*
*              Multiplies the given key (max k bits) with a constant
*              multiplier and extracts p bits of the result, from the 
*              bit position k-1 to bit position k-p, to get the hash
*              list index. p is such that 2^p is number of bins.
*
*              The constant multiplier is the floor of A * 2^k, for
*              some constant A.
*
*              This function uses a pre-computed constant multiplier
*              CM_HASH_MULTMETHOD_CNST24, which is computed for 
*              A = (sqrt(5) - 1)/2, and k = 24 bits.
*
*              This hashing method is explained in section 12.3.2 of
*              "Introduction to Algorithms" by Thomas H. Cormen et al.,
*              The MIT Press.
*
*       Ret:   ROK     - successful, *idx contains computed index 
*
*       Notes: None.
*
*       File:  cm_hash.c
*
*/

#ifdef ANSI
PRIVATE S16 cmHashFuncMult24
(
CmHashListCp       *hashListCp,        /* hash list control point */
U8                 *key,               /* key string */
U16                keyLen,             /* length of key string */
U16                *idx                /* index to return */
) 
#else
PRIVATE S16 cmHashFuncMult24(hashListCp, key, keyLen, idx)
CmHashListCp       *hashListCp;        /* hash list control point */
U8                 *key;               /* key string */
U16                keyLen;             /* length of key string */
U16                *idx;               /* index to return */
#endif
{
   U32             prod;               /* (constant multiplier * key) */
   U8              shift;              /* Bits to be shifted to get index */

   TRC2(cmHashFuncMult24);

   UNUSED(keyLen);

#if (ERRCLASS & ERRCLS_DEBUG)
   /* error check on parameters */
   if (hashListCp->binBitMask == CM_HASH_NOBITMASK)
      RETVALUE(RFAILED);
#endif

   prod = CM_HASH_MULT24_CONST * *((U32 *)key);

   shift = CM_HASH_MULT24_BITPOS - hashListCp->nmbBinBits;
   *idx = ((U16) (prod & (hashListCp->binBitMask << shift))) >> shift;

   RETVALUE(ROK);
} /* end of cmHashFuncMult24 */

  
/*
*
*       Fun:   cmHashFuncDirIdx
*
*       Desc:  Computes the hash list index (bin number) for a specified
*              key of type CM_HASH_KEYTYPE_DIRINDEX. 
*
*              The key is the hash table index.
*
*       Ret:   ROK     - successful, *idx contains computed index 
*
*       Notes: None.
*
*       File:  cm_hash.c
*
*/

#ifdef ANSI
PRIVATE S16 cmHashFuncDirIdx
(
CmHashListCp       *hashListCp,        /* hash list control point */
U8                 *key,               /* key string */
U16                keyLen,             /* length of key string */
U16                *idx                /* index to return */
) 
#else
PRIVATE S16 cmHashFuncDirIdx(hashListCp, key, keyLen, idx)
CmHashListCp       *hashListCp;        /* hash list control point */
U8                 *key;               /* key string */
U16                keyLen;             /* length of key string */
U16                *idx;               /* index to return */
#endif
{
   TRC2(cmHashFuncDirIdx);

   UNUSED(hashListCp);
   UNUSED(keyLen);

   *idx = *((U16 *) key);

   RETVALUE(ROK);
} /* end of cmHashFuncDirIdx */

  
/*
*
*       Fun:   cmHashMatchKey
*
*       Desc:  Compares two keys and determines if they match.
*
*       Ret:   ROK     - match successful
*              RFAILED - match failed (non-matching key values)
*
*       Notes: None.
*
*       File:  cm_hash.c
*
*/

#ifdef ANSI
PRIVATE S16 cmHashMatchKey
(
U8 *key1,                         /* first key string */
U16 keyLen1,                      /* length of first key string */
U8 *key2,                         /* second key string */
U16 keyLen2                       /* length of second key string */
) 
#else
PRIVATE S16 cmHashMatchKey(key1, keyLen1, key2, keyLen2)
U8 *key1;                         /* first key string */
U16 keyLen1;                      /* length of first key string */
U8 *key2;                         /* second key string */
U16 keyLen2;                      /* length of second key string */
#endif
{
   TRC2(cmHashMatchKey);

   /* compare key lengths */
   if (keyLen1 != keyLen2)
      RETVALUE(RFAILED);

   /* compare key strings */
   RETVALUE(cmMemcmp(key1, key2, (PTR) keyLen1));
} /* end of cmHashMatchKey */

  
/*
*
*       Fun:   cmListInsert
*
*       Desc:  Adds an entry into a doubly linked list
*
*       Ret:   ROK      - insertion successful
*
*       Notes: None
*
*       File:  cm_hash.c
*
*/

#ifdef ANSI
PRIVATE S16 cmListInsert
(
CmListEnt *oldEntry,                    /* add new entry after this entry */
CmListEnt *newEntry                     /* new entry to add */
) 
#else
PRIVATE S16 cmListInsert(oldEntry, newEntry) 
CmListEnt *oldEntry;                    /* add new entry after this entry */
CmListEnt *newEntry;                    /* new entry to add */
#endif
{
   TRC2(cmListInsert);

   newEntry->next         = oldEntry->next;
   newEntry->prev         = oldEntry;
   oldEntry->next         = newEntry;
   (newEntry->next)->prev = newEntry;

   RETVALUE(ROK);
} /* end of cmListInsert */

  
/*
*
*       Fun:   cmListDelete
*
*       Desc:  Deletes an entry from a doubly linked list
*