📄 cm_hash.c
字号:
/* search this bin for exact key match */
hashListBin = &hashListCp->hl[idx];
hashListEnt = (CmHashListEnt *) hashListBin->next;
/* examine each entry in bin */
i = 0;
while (hashListBin != (CmListEnt *) hashListEnt)
{
/* check if key matches */
if (cmHashMatchKey(hashListEnt->key, hashListEnt->keyLen, key, keyLen)
== ROK)
{
/* matching key */
*entry = (PTR) (((U8 *) hashListEnt) - hashListCp->offset);
/* check for duplicates */
if (!hashListCp->dupFlg)
RETVALUE(ROK);
/* for duplicate key, check sequence number */
if (i++ == seqNmb)
RETVALUE(ROK);
}
/* go to next entry */
hashListEnt = (CmHashListEnt *) hashListEnt->list.next;
}
/* no matching key found */
RETVALUE(RFAILED);
} /* end of cmHashListFind */
/*
*
* Fun: cmHashListGetNext
*
* Desc: Gets next entry in hash list with respect to the specified
* previous entry. If previous entry is NULLP, gets first
* entry in hash list. Parameters are:
*
* hashListCp control point for hash list
* prevEnt pointer to previous entry
* entry pointer to next entry to be returned
*
* Ret: ROK - get successful, *entry points to found entry
* (at beginning of list or in the list)
* RFAILED - get failed, *entry is unchanged
* (incorrect parameter values)
* ROKDNA - get failed, *entry is unchanged.
* (end of list)
* Notes: None.
*
* File: cm_hash.c
*
*/
#ifdef ANSI
PUBLIC S16 cmHashListGetNext
(
CmHashListCp *hashListCp, /* hash list to get from */
PTR prevEnt, /* previous entry */
PTR *entry /* entry to be returned */
)
#else
PUBLIC S16 cmHashListGetNext(hashListCp, prevEnt, entry)
CmHashListCp *hashListCp; /* hash list to get from */
PTR prevEnt; /* previous entry */
PTR *entry; /* entry to be returned */
#endif
{
CmListEnt *hashListBin; /* temporary hash list bin pointer */
CmHashListEnt *hashListEnt; /* temporary hash list entry pointer */
CmHashListEnt *prevListEnt; /* previous hash list entry pointer */
U16 i; /* hash list counter */
TRC2(cmHashListGetNext);
#if (ERRCLASS & ERRCLS_DEBUG)
/* error check on parameters */
if ((hashListCp == NULLP) || (entry == NULLP))
RETVALUE(RFAILED);
#endif
/* check if need to get first entry */
if (prevEnt == NULLP)
{
/* get first entry in hash list */
for (i = 0; i < hashListCp->nmbBins; i++)
/* check for non-empty bin */
if (hashListCp->hl[i].next != &hashListCp->hl[i])
{
/* get first entry in bin */
hashListEnt = (CmHashListEnt *) hashListCp->hl[i].next;
/* requested entry is in nxtEnt */
*entry = (PTR) (((U8 *) hashListEnt) - hashListCp->offset);
RETVALUE(ROK);
}
/* no more entries */
RETVALUE(ROKDNA);
}
/* use previous entry to find next entry */
/* get pointer to previous hash list entry header */
prevListEnt = (CmHashListEnt *) (((U8 *) prevEnt) + hashListCp->offset);
/* get index of previous entry */
i = prevListEnt->hashVal;
/* set pointers to get next entry */
hashListBin = &hashListCp->hl[i];
prevListEnt = (CmHashListEnt *) prevListEnt->list.next;
for (;;)
{
/* check if more entries in this bin */
if (prevListEnt != (CmHashListEnt *) hashListBin)
{
/* found next entry */
*entry = (PTR) (((U8 *) prevListEnt) - hashListCp->offset);
RETVALUE(ROK);
}
/* no more entries in this bin, go to next bin, check if more bins */
if (++i >= hashListCp->nmbBins)
/* no more entries */
break;
/* reset pointers for next bin */
hashListBin = &hashListCp->hl[i];
prevListEnt = (CmHashListEnt *) hashListBin->next;
}
/* no more entries */
RETVALUE(ROKDNA);
} /* end of cmHashListGetNext */
/*
*
* Fun: cmHashListQuery
*
* Desc: Gets hash list attributes. Parameters are:
*
* hashListCp control point for hash list
* queryType type of attribute being queried
* result result of query, to be returned
*
* Ret: ROK - successful, *result contains query result
* RFAILED - failed, *result unchanged (incorrect parameter values)
*
* Notes: This function is obsoleted!
* Use macros defined in cm_hash.h instead
*
* File: cm_hash.c
*
*/
#ifdef ANSI
PUBLIC S16 cmHashListQuery
(
CmHashListCp *hashListCp, /* hash list to query */
U8 queryType, /* type of query */
U16 *result /* result of query */
)
#else
PUBLIC S16 cmHashListQuery(hashListCp, queryType, result)
CmHashListCp *hashListCp; /* hash list to query */
U8 queryType; /* type of query */
U16 *result; /* result of query */
#endif
{
TRC2(cmHashListQuery);
/* deal with queries that do not need hashListCp */
#if (ERRCLASS & ERRCLS_DEBUG)
/* error check on parameters */
if (result == NULLP)
RETVALUE(RFAILED);
#endif
/* respond depending on query type */
if (queryType == CM_HASH_QUERYTYPE_BINSIZE)
{
/* storage for each bin */
*result = (U16) sizeof(CmListEnt);
RETVALUE(ROK);
}
/* deal with queries that do need hashListCp */
#if (ERRCLASS & ERRCLS_DEBUG)
/* error check on parameters */
if (hashListCp == NULLP)
RETVALUE(RFAILED);
#endif
/* respond depending on query type */
switch (queryType)
{
case CM_HASH_QUERYTYPE_ENTRIES: /* current number of entries */
*result = (U16) hashListCp->nmbEnt;
RETVALUE(ROK);
case CM_HASH_QUERYTYPE_BINS: /* number of bins */
*result = (U16) hashListCp->nmbBins;
RETVALUE(ROK);
case CM_HASH_QUERYTYPE_OFFSET: /* offset of CmHashListEnt in entries */
*result = (U16) hashListCp->offset;
RETVALUE(ROK);
case CM_HASH_QUERYTYPE_DUPFLG: /* allow duplicate keys */
*result = (U16) hashListCp->dupFlg;
RETVALUE(ROK);
case CM_HASH_QUERYTYPE_KEYTYPE: /* key type for selecting hash functions */
*result = (U16) hashListCp->keyType;
RETVALUE(ROK);
default: /* process other query types */
break;
}
/* illegal query type */
RETVALUE(RFAILED);
} /* end of cmHashListQuery */
#ifdef HASH_OPEN_ADDRESSING
/*
*
* Fun: cmHashListOAInsert
*
* Desc: Inserts a new entry in the hash list with open addressing.
* 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 cmHashListOAInsert
(
CmHashListCp *hashListCp, /* hash table to add to */
PTR entry, /* entry to add */
U8 *key, /* pointer to key */
U16 keyLen /* length of key */
)
#else
PUBLIC S16 cmHashListOAInsert(hashListCp, entry, key, keyLen)
CmHashListCp *hashListCp; /* hash table to add to */
PTR entry; /* entry to add */
U8 *key; /* pointer to key */
U16 keyLen; /* length of key */
#endif
{
CmListEnt *hashBin; /* temporary hash list bin pointer */
CmHashListEnt *hashListEnt; /* pointer to hash list entry header */
U16 idx; /* index for insertion into hash list */
U16 hashSize; /* hash size */
U16 i;
TRC2(cmHashListOAInsert);
#if (ERRCLASS & ERRCLS_DEBUG)
/* error check on parameters */
if ((hashListCp == NULLP) || (entry == NULLP) ||
(key == NULLP) || (keyLen == 0))
RETVALUE(RFAILED);
#endif
/* check if table is full */
if (hashListCp->nmbBins == hashListCp->nmbEnt)
RETVALUE(ROUTRES);
/* 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);
/*
* find an empty bin
*/
hashSize = hashListCp->nmbBins;
hashBin = &hashListCp->hl[idx];
for (i = hashSize; i > 0; i--)
{
if (hashBin->next == hashBin)
break; /* found */
if (++idx >= hashSize)
{
idx = 0;
hashBin = &hashListCp->hl[0];
}
else
hashBin++;
}
/* insert into list */
if (cmListInsert(hashBin->prev, &hashListEnt->list) != ROK)
RETVALUE(RFAILED);
hashListEnt->hashVal = idx;
/* increment count of entries in hash list */
hashListCp->nmbEnt++;
RETVALUE(ROK);
} /* end of cmHashListOAInsert */
#endif /* HASH_OPENADDRESSING */
/********************************************************************30**
End of file: cm_hash.c 1.11 - 02/11/00 11:55:45
*********************************************************************31*/
/********************************************************************40**
Notes:
*********************************************************************41*/
/********************************************************************50**
*********************************************************************51*/
/********************************************************************60**
Revision history:
*********************************************************************61*/
/********************************************************************80**
version pat init description
----------- ----- ---- ------------------------------------------------
1.1 --- rg 1. initial release.
1.2 --- bw 1. store hash value in struct CmHashListEnt.
--- bw 2. new functions for hash table with open addressing
--- bw 3. change copyright header
1.3 --- ak 1. fixed compile time warnings in cmHashListOAInsert
1.4 --- rg 1. changed cmHashListQuery to allow queries with
NULL hashListCp for some query types.
*********************************************************************81*/
/********************************************************************90**
ver pat init description
------------ -------- ---- ----------------------------------------------
1.5 --- rg 1. corrected cmHashListQuery to allow queries with
NULL hashListCp for some query types.
--- rg 2. changed cmHashListInit to initialize nmbBins
only after successfully allocating bins.
--- rg 3. included cm_lib.x to use cmMemcmp for hash key
matching.
--- rg 4. replaced cmHashFindIndex with a hashFunc field
in CmHashListCp, which is computed based on key
type at initialization time.
--- rg 5. Added cmHashFuncDefault to handle default
key type.
--- rg 6. used 32-bit or 16-bit operations, when possible,
to add the bytes of a key for default key type.
--- rg 7. replaced ERRCHK with (ERRCLASS & ERCLS_DEBUG).
--- rg 8. removed unnecessary error checks in support
functions.
--- rg 9. added support for binBitMask computation to
speed up hash index calculation.
--- kvm 10. added support for multiplication method of
hash list index computation (cmHashFuncMult24)
--- kvm 11. added code for nmbBinBits computation
--- kvm 12. added support for direct indexing
(cmHashFuncDirIdx)
--- ak 13. added comment to indicate obsolescence of
cmHashListQuery
--- ak 14. Fixed return-value bug in cmHashListQuery
--- ak 15. changed ERRCHK -> ERRCLS_DEBUG
1.6 --- rg 1. corrected cmHashFuncDefault to do only 8-bit
operations so the hash index value is not
influenced by the key pointer alignment.
1.7 --- sg 1. removed a unused variable from cmHashFuncDefault
1.8 --- mk 1. Changed the typecast from S16 to PTR in
call to the function cmMemcmp.
--- mg 2. Corrected pointer adjustment logic in
cmListDelete
--- mg 3. Changes to pass through chksrc.
1.9 --- bbk 1. Changed copyright header date.
1.10 --- tej 1. Changed copyright header date.
1.11 --- bbk 1. Added cmHashFuncString as hash function for
strings
2. Removed the use of variable index as
VxWorks has a keyword as "index"
*********************************************************************91*/
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -