cm_hash.c

中国石油二期加油站IC系统后台通讯软件

*       Ret:   ROK      - deletion successful
*
*       Notes: None
*
*       File:  cm_hash.c
*
*/

#ifdef ANSI
PRIVATE S16 cmListDelete
(
CmListEnt *entry                        /* entry to delete */
) 
#else
PRIVATE S16 cmListDelete(entry) 
CmListEnt *entry;                       /* entry to delete */
#endif
{
   TRC2(cmListDelete);

   if (entry == NULLP) 
      RETVALUE(RFAILED);

   if (entry->prev != NULLP)
      (entry->prev)->next = entry->next;

   if (entry->next != NULLP)
      (entry->next)->prev = entry->prev;

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



/*
 *     public functions
 */


/*
*
*       Fun:   cmHashListInit
*
*       Desc:  Initializes a hash list. Parameters are: 
*
*              hashListCp   control point for hash list
*              nmbBins      number of bins in the hash list. Storage will
*                           be allocated for them from the indicated memory
*                           region and pool.
*              offset       if the entries in this hash list are also going
*                           to be attached to another hash list, they will
*                           contain multiple hash list entry headers. The
*                           offset indicates the offset of the entry header
*                           for this hash list in the entry structure.
*              dupFlg       whether entries with duplicate keys are allowed
*                           to be inserted in the hash list.
*              keyType      indicates type of key which can be used to select
*                           different hash functions. Ignored in this
*                           implementation.
*              region       
*              pool         for allocating storage for bins.
*
*       Ret:   ROK      - initialization successful
*              RFAILED  - initialization failed, lack of memory
*
*       Notes: None
*
*       File:  cm_hash.c
*
*/
#ifdef ANSI
PUBLIC S16 cmHashListInit
(
CmHashListCp *hashListCp,  /* hash list to initialize */
U16          nmbBins,      /* number of hash list bins */
U16          offset,       /* offset of CmHashListEnt in entries */
Bool         dupFlg,       /* allow duplicate keys */
U16          keyType,      /* key type for selecting hash fn */
Region       region,       /* memory region to allocate bins */
Pool         pool          /* memory pool to allocate bins */
)
#else
PUBLIC S16 cmHashListInit(hashListCp, nmbBins, offset, dupFlg, keyType, region, pool)
CmHashListCp *hashListCp;  /* hash list to initialize */
U16          nmbBins;      /* number of hash list bins */
U16          offset;       /* offset of CmHashListEnt in entries */
Bool         dupFlg;       /* allow duplicate keys */
U16          keyType;      /* key type for selecting hash fn */
Region       region;       /* memory region to allocate bins */
Pool         pool;         /* memory pool to allocate bins */
#endif
{
   U16 i;
   CmListEnt *hl;

   TRC2(cmHashListInit);

#if (ERRCLASS & ERRCLS_DEBUG)
   /* error check on parameters */
   if (hashListCp == NULLP) 
      RETVALUE(RFAILED);
#endif

   /* initialize control point fields */
   hashListCp->hl      = NULLP;
   hashListCp->region  = region;
   hashListCp->pool    = pool;
   hashListCp->nmbBins = 0;
   hashListCp->binBitMask = CM_HASH_NOBITMASK;
   hashListCp->nmbBinBits = 0;
   hashListCp->nmbEnt  = 0;
   hashListCp->offset  = offset;
   hashListCp->dupFlg  = dupFlg;
   hashListCp->keyType = keyType;
   hashListCp->hashFunc = NULLP;

   /* initialize hash function for this key type */
   switch (keyType)
   {
      case CM_HASH_KEYTYPE_MULT24:
         /* return failure if number of bins is not a power of 2 */
         if (((nmbBins) & (nmbBins - 1)) != 0)
            RETVALUE (RFAILED);

         hashListCp->hashFunc = cmHashFuncMult24;
         break;

      case CM_HASH_KEYTYPE_DIRIDX:
         hashListCp->hashFunc = cmHashFuncDirIdx;
         break;

      case CM_HASH_KEYTYPE_STR:
         hashListCp->hashFunc = cmHashFuncString;
         break;

      case CM_HASH_KEYTYPE_DEF:      /* default hash function */
      default:                       /* illegal key type */
         hashListCp->hashFunc = cmHashFuncDefault;
         break;
   }

   /* allocate memory for bins */
   if (nmbBins)
   {
      if (SGetSBuf(region, pool, (Data **) &hashListCp->hl, 
                   (Size) (nmbBins * sizeof(CmListEnt))) != ROK)
         RETVALUE(RFAILED);

      /* initialize bin pointers */
      hl = hashListCp->hl;
      for(i = 0; i < nmbBins; i++)
         hl[i].next = hl[i].prev = &hl[i];

      /* initialize bin size */
      hashListCp->nmbBins = nmbBins;

      /* initialize bin bit mask */
      if (((nmbBins) & (nmbBins - 1)) == 0)
      {
         U16   binBitMask;

         /* number of bins is a power of 2 */
         hashListCp->binBitMask = nmbBins - 1;

         /* compute number of bits in the bit mask */
         for (binBitMask = hashListCp->binBitMask; binBitMask; binBitMask >>= 1)
            hashListCp->nmbBinBits++;

      }
   }

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


/*
*
*       Fun:   cmHashListDeinit
*
*       Desc:  Deinitializes a hash list. Deallocates memory for bins
*              and resets header fields. Parameters are: 
*
*              hashListCp   control point for hash list
*
*       Ret:   ROK      - successful
*
*       Notes: None
*
*       File:  cm_hash.c
*
*/
#ifdef ANSI
PUBLIC S16 cmHashListDeinit
(
CmHashListCp *hashListCp   /* hash list to deinitialize */
)
#else
PUBLIC S16 cmHashListDeinit(hashListCp)
CmHashListCp *hashListCp;  /* hash list to deinitialize */
#endif
{
   TRC2(cmHashListDeinit);

#if (ERRCLASS & ERRCLS_DEBUG)
   /* error check on parameters */
   if (hashListCp == NULLP) 
      RETVALUE(RFAILED);
#endif

   /* deallocate memory for bins */
   if (hashListCp->nmbBins)
      (Void) SPutSBuf(hashListCp->region, hashListCp->pool, 
                      (Data *) hashListCp->hl, 
                      (Size) (hashListCp->nmbBins * sizeof(CmListEnt)));

   /* deinitialize control point fields */
   hashListCp->hl      = NULLP;
   hashListCp->region  = REGIONNC;
   hashListCp->pool    = 0;
   hashListCp->nmbBins = 0;
   hashListCp->binBitMask = CM_HASH_NOBITMASK;
   hashListCp->nmbEnt  = 0;
   hashListCp->offset  = 0;
   hashListCp->dupFlg  = FALSE;
   hashListCp->keyType = CM_HASH_KEYTYPE_DEF;
   hashListCp->hashFunc = NULLP;

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

  
/*
*
*       Fun:   cmHashListInsert
*
*       Desc:  Inserts a new entry in the hash list. Parameters are: 
*
*              hashListCp   control point for hash list
*              entry        pointer to new entry to add in the hash list
*              key          pointer to key string in the new entry
*              keyLen       length of key string
*
*       Ret:   ROK      - insertion successful
*              ROKDUP   - insertion failed (duplicate key not allowed)
*              RFAILED  - insertion failed (incorrect parameter values)
*
*       Notes: None
*
*       File:  cm_hash.c
*
*/

#ifdef ANSI
PUBLIC S16 cmHashListInsert
(
CmHashListCp *hashListCp,  /* hash list to add to */
PTR          entry,        /* entry to add */
U8           *key,         /* pointer to key */
U16          keyLen        /* length of key */
)
#else
PUBLIC S16 cmHashListInsert(hashListCp, entry, key, keyLen)
CmHashListCp *hashListCp;  /* hash list to add to */
PTR          entry;        /* entry to add */
U8           *key;         /* pointer to key */
U16          keyLen;       /* length of key */
#endif
{
   CmHashListEnt *hashListEnt;    /* pointer to hash list entry header */
   PTR dupEntry;                  /* pointer to entry with duplicate key */
   U16 idx;                       /* index for insertion into hash list */

   TRC2(cmHashListInsert);

#if (ERRCLASS & ERRCLS_DEBUG)
   /* error check on parameters */
   if ((hashListCp == NULLP) || (entry == NULLP) || 
       (key == NULLP) || (keyLen == 0))
      RETVALUE(RFAILED);
#endif

   /* check for duplicates */
   if (hashListCp->dupFlg == FALSE)
   {
      /* no duplicates allowed, check if key already exists */
      if (cmHashListFind(hashListCp, key, keyLen, 0, &dupEntry) == ROK)
         RETVALUE(ROKDUP);
   }

   /* get pointer to hash list entry header */
   hashListEnt = (CmHashListEnt *) (((U8 *) entry) + hashListCp->offset);

   /* initialize hash list entry header */
   hashListEnt->list.next = NULLP;
   hashListEnt->list.prev = NULLP;
   hashListEnt->keyLen    = keyLen;
   hashListEnt->key       = key;

   /* compute index for insertion */
   if ((*hashListCp->hashFunc)(hashListCp, key, keyLen, &idx) != ROK)
      RETVALUE(RFAILED);

   hashListEnt->hashVal   = idx;

   /* insert into list */
   cmListInsert(hashListCp->hl[idx].prev, &hashListEnt->list);

   /* increment count of entries in hash list */
   hashListCp->nmbEnt++;

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

  
/*
*
*       Fun:   cmHashListDelete
*
*       Desc:  Deletes an entry from the hash list. Parameters are:
*
*              hashListCp   control point for hash list
*              entry        pointer to entry to delete from the hash list
*
*       Ret:   ROK      - deletion successful
*              RFAILED  - deletion failed (incorrect parameter values)
*
*       Notes: None
*
*       File:  cm_hash.c
*
*/

#ifdef ANSI
PUBLIC S16 cmHashListDelete
(
CmHashListCp *hashListCp,  /* hash list to delete from */
PTR          entry         /* entry to delete */
)
#else
PUBLIC S16 cmHashListDelete(hashListCp, entry)
CmHashListCp *hashListCp;  /* hash list to delete from */
PTR          entry;        /* entry to delete */
#endif
{
   CmHashListEnt *hashListEnt;    /* pointer to hash list entry header */

   TRC2(cmHashListDelete);

#if (ERRCLASS & ERRCLS_DEBUG)
   /* error check on parameters */
   if ((hashListCp == NULLP) || (entry == NULLP)) 
      RETVALUE(RFAILED);
#endif

   /* get pointer to hash list entry header */
   hashListEnt = (CmHashListEnt *) (((U8 *) entry) + hashListCp->offset);

   /* delete entry from list */
   cmListDelete(&hashListEnt->list);

   /* reinitialize hash list entry header */
   hashListEnt->list.next = NULLP;
   hashListEnt->list.prev = NULLP;
   hashListEnt->keyLen    = 0;
   hashListEnt->key       = NULLP;
   hashListEnt->hashVal   = 0;

   /* decrement count of entries in hash list */
   hashListCp->nmbEnt--;

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

  
/*
*
*       Fun:   cmHashListFind
*
*       Desc:  Finds an entry in the hash list. Parameters are:
*
*              hashListCp   control point for hash list
*              key          pointer to key string for search
*              keyLen       length of key string
*              seqNmb       sequence number in case duplicates allowed
*              entry        pointer to found entry
*
*       Ret:   ROK      - find successful, *entry points to found entry
*              RFAILED  - find failed, *entry is unchanged 
*                         (incorrect parameter values, key not found)
*
*       Notes: None
*
*       File:  cm_hash.c
*
*/

#ifdef ANSI
PUBLIC S16 cmHashListFind
(
CmHashListCp *hashListCp,  /* hash list to search */
U8           *key,         /* pointer to key */
U16          keyLen,       /* length of key */
U16          seqNmb,       /* used in case of duplicate keys */
PTR          *entry        /* entry to be returned */
)
#else
PUBLIC S16 cmHashListFind(hashListCp, key, keyLen, seqNmb, entry)
CmHashListCp *hashListCp;  /* hash list to search */
U8           *key;         /* pointer to key */
U16          keyLen;       /* length of key */
U16          seqNmb;       /* used in case of duplicate keys */
PTR          *entry;       /* entry to be returned */
#endif
{
   CmHashListEnt *hashListEnt;    /* pointer to hash list entry header */
   CmListEnt *hashListBin;        /* pointer to hash list bin */
   U16 i;                         /* counter for sequence number */
   U16 idx;                       /* index for insertion into hash list */

   TRC2(cmHashListFind);

#if (ERRCLASS & ERRCLS_DEBUG)
   /* error check on parameters */
   if ((hashListCp == NULLP) || (key == NULLP) || 
       (keyLen == 0) || (entry == NULLP))
      RETVALUE(RFAILED);
#endif

   /* compute hash table index */
   if ((*hashListCp->hashFunc)(hashListCp, key, keyLen, &idx) != ROK)
      RETVALUE(RFAILED);