1 /*******************************************************************************
2 ################################################################################
3 # Copyright (c) [2017-2019] [Radisys] #
5 # Licensed under the Apache License, Version 2.0 (the "License"); #
6 # you may not use this file except in compliance with the License. #
7 # You may obtain a copy of the License at #
9 # http://www.apache.org/licenses/LICENSE-2.0 #
11 # Unless required by applicable law or agreed to in writing, software #
12 # distributed under the License is distributed on an "AS IS" BASIS, #
13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. #
14 # See the License for the specific language governing permissions and #
15 # limitations under the License. #
16 ################################################################################
17 *******************************************************************************/
19 /********************************************************************20**
21 Name: common hash functions
25 Desc: Hashing functions used by various layers.
26 (Newer version of functions in cm_bdy1)
28 Using hash lists in a product:
29 ------------------------------
31 Wherever a hash list is needed, a corresponding hash list
32 control point (CmHashListCp) should be declared. The structure
33 definition of the entries that belong to the hash list must
34 include a declaration of the hash list entry header
35 (CmHashListEnt) along with the key for the hash list (this
36 may be any scalar or structure type subfield of the entry).
37 For example, we need a hash list in a SAP to maintain a table
40 typedef struct xySAPCb (SAP control block)
43 CmHashListCp addrHlCp; (hash list for addresses)
47 typedef struct xyAddrEnt (hash list entry for an address)
50 CmHashListEnt hl; (hash list entry header)
52 XyAddr addr; (hash list key)
59 The functions available for using hash lists are defined
60 below. The accompanying comments explain the usage in detail.
62 Implementation details:
63 -----------------------
65 A hash list is identified by its control point
66 (CmHashListCp). This control point stores the characteristics
67 of the hash list as well as a pointer to the hash list bins.
68 The storage for the bins is allocated when the hash list is
69 initialized. Each bin is organized as a doubly linked list of
70 entries whose key maps to this bin. The hash function used to
71 map keys to a bin simply adds up all the octets of the key
72 and then divides the sum by the number of bins. Variable size
73 keys are allowed. Duplicate keys may be present if explicitly
74 allowed; if so, they can be retrieved by supplying a sequence
75 number in the find routine. A given structure may be attached
76 to more than one hash list if it contains multiple hash list
81 *********************************************************************21*/
84 /* header include files -- defines (.h) */
86 #include "envopt.h" /* environment options */
87 #include "envdep.h" /* environment dependent */
88 #include "envind.h" /* environment independent */
90 #include "gen.h" /* general */
91 #include "ssi.h" /* system services */
92 #include "cm_hash.h" /* common hash functions */
93 #include "cm_err.h" /* common functions error */
95 /* header include -- typedef structs (.x) */
97 #include "gen.x" /* general */
98 #include "ssi.x" /* system services */
99 #include "cm_lib.x" /* common library functions */
100 #include "cm_hash.x" /* common hash functions */
107 /* forward references */
108 /* cm_hash_c_001.main_22: Fixing warnings on GCC compiler */
113 static S16 cmHashFuncBCD8 ARGS((CmHashListCp *hashListCp, uint8_t *key,
114 uint16_t keyLen, uint16_t *idx));
116 static S16 cmHashFuncConId ARGS((CmHashListCp *hashListCp, uint8_t *key,
117 uint16_t keyLen, uint16_t *idx));
119 static S16 cmHashFuncU32Mod ARGS((CmHashListCp *hashListCp, uint8_t *key,
120 uint16_t keyLen, uint16_t *idx));
122 static S16 cmHashFuncString ARGS((CmHashListCp *hashListCp, uint8_t *key,
123 uint16_t keyLen, uint16_t *idx));
125 static S16 cmHashFuncDefault ARGS((CmHashListCp *hashListCp, uint8_t *key,
126 uint16_t keyLen, uint16_t *idx));
128 static S16 cmHashFuncAnyKey ARGS((CmHashListCp *hashListCp, uint8_t *key,
129 uint16_t keyLen, uint16_t *idx));
131 static S16 cmHashMatchKey ARGS((uint8_t *key1, uint16_t keyLen1, uint8_t *key2, uint16_t keyLen2));
133 static S16 cmListInsert ARGS((CmListEnt *oldEntry, CmListEnt *newEntry));
135 static S16 cmListDelete ARGS((CmListEnt *entry));
137 /* cm_hash_c_001.main_22: Fixing warnings on GCC compiler */
138 static S16 cmHashFuncMult24 ARGS((CmHashListCp *hashListCp, uint8_t *key, uint16_t keyLen, uint16_t *idx));
140 static S16 cmHashFuncDirIdx ARGS((CmHashListCp *hashListCp, uint8_t *key, uint16_t keyLen, uint16_t *idx));
146 /* functions in other modules */
148 /* public variable declarations */
150 /* private variable declarations */
154 * private support functions
159 * Fun: cmHashFuncAnyKey
161 * Desc: Computes the hash list index (bin number) for a specified
162 * key of type CM_HASH_KEYTYPE_ANY.
164 * return index to hash table
166 * Ret: ROK - successful, *idx contains computed index
174 static S16 cmHashFuncAnyKey
176 CmHashListCp *hashListCp, /* hash list control point */
177 uint8_t *key, /* key string */
178 uint16_t keyLen, /* length of key string */
179 uint16_t *idx /* idx to return */
182 uint32_t a; /* hash variables */
183 uint32_t b; /* hash variables */
184 uint32_t c; /* hash variables */
185 uint32_t len; /* length */
187 /*cm_hash_c_001.main_23 : Fix for TRACE5 feature crash due to missing TRC MACRO*/
188 /* Set up the internal state */
189 len = keyLen; /* key length */
190 a = 0x9e3779b9; /* a = b = the golden ratio; an arbitrary value */
192 c = 0x12345678; /* some value */
194 /*---------------------------------------- handle most of the key */
197 a += (key[0] +((uint32_t)key[1]<<8) +((uint32_t)key[2]<<16) +((uint32_t)key[3]<<24));
198 b += (key[4] +((uint32_t)key[5]<<8) +((uint32_t)key[6]<<16) +((uint32_t)key[7]<<24));
199 c += (key[8] +((uint32_t)key[9]<<8) +((uint32_t)key[10]<<16)+((uint32_t)key[11]<<24));
200 CM_HASH_MIX(a, b, c);
201 key += 12; len -= 12;
204 /*------------------------------------- handle the last 11 bytes */
206 switch(len) /* all the case statements fall through */
208 case 11: c+=((uint32_t)key[10]<<24);
209 case 10: c+=((uint32_t)key[9]<<16);
210 case 9 : c+=((uint32_t)key[8]<<8);
211 /* the first byte of c is reserved for the keyLen */
212 case 8 : b+=((uint32_t)key[7]<<24);
213 case 7 : b+=((uint32_t)key[6]<<16);
214 case 6 : b+=((uint32_t)key[5]<<8);
216 case 4 : a+=((uint32_t)key[3]<<24);
217 case 3 : a+=((uint32_t)key[2]<<16);
218 case 2 : a+=((uint32_t)key[1]<<8);
220 /* case 0: nothing left to add */
223 /*-------------------------------------------- report the result */
225 /* if nmbBins is a power of 2, use shift, else use division */
226 if (hashListCp->binBitMask != CM_HASH_NOBITMASK)
227 *idx = (uint16_t) (c & hashListCp->binBitMask);
229 *idx = (uint16_t) (c % hashListCp->nmbBins);
232 } /* end of cmHashFuncAnyKey */
237 * Fun: cmHashFuncU32Mod
239 * Desc: Computes the hash list index (bin number) for a specified
240 * key of type CM_HASH_KEYTYPE_MOD.
242 * return (idx % hash_table_size);
244 * Ret: ROK - successful, *idx contains computed index
252 static S16 cmHashFuncU32Mod
254 CmHashListCp *hashListCp, /* hash list control point */
255 uint8_t *key, /* key string */
256 uint16_t keyLen, /* length of key string */
257 uint16_t *idx /* idx to return */
260 uint32_t sum; /* Sum of octets for hash function */
263 /* keyLen is marked Unused to remove compilation
267 sum = *((uint32_t *)key);
269 /* if nmbBins is a power of 2, use shift, else use division */
270 if (hashListCp->binBitMask != CM_HASH_NOBITMASK)
271 *idx = (uint16_t) (sum & hashListCp->binBitMask);
273 *idx = (uint16_t) (sum % hashListCp->nmbBins);
277 } /* end of cmHashFuncU32Mod () */
281 * Fun: cmHashFuncBCD8
283 * Desc: Computes the hash list index (bin number) for a specified
284 * key of type CM_HASH_KEYTYPE_BCD8.
287 * 1. Converts the 8 BCD coded octets into 2 uint32_ts
288 * 2. Adds 2 uint32_ts to get one uint32_t.
289 * 3. Apply uint32_tMod technique to get the index
290 * 4. Return the index
293 * Here we are no bothered if the keyLen is more than 8.
294 * We are interested only in the first 8 octets.
296 * Ret: ROK - successful, *idx contains computed index
304 static S16 cmHashFuncBCD8
306 CmHashListCp *hashListCp, /* hash list control point */
307 uint8_t *key, /* key string */
308 uint16_t keyLen, /* length of key string */
309 uint16_t *idx /* idx to return */
313 uint32_t firstUInt32 = 0; /* First uint32_t prepared for lower 4 octets */
314 uint32_t secondUInt32 = 0; /* Second uint32_t prepared for higher 4 octets */
315 uint32_t sum; /* Sum of the above 2 octets to get the index */
318 /* keyLen is marked Unused to remove compilation
322 /* Compute second uint32_t */
323 tmp16 = (uint16_t) PutHiByte(tmp16, (uint8_t) key[0]);
324 tmp16 = (uint16_t) PutLoByte(tmp16, (uint8_t) key[1]);
325 secondUInt32 = (uint32_t) PutHiWord(secondUInt32, (uint16_t) tmp16);
326 tmp16 = (uint16_t) PutHiByte(tmp16, (uint8_t) key[2]);
327 tmp16 = (uint16_t) PutLoByte(tmp16, (uint8_t) key[3]);
328 secondUInt32 = (uint32_t) PutLoWord(secondUInt32, (uint16_t) tmp16);
331 /* Compute first uint32_t */
332 tmp16 = (uint16_t) PutHiByte(tmp16, (uint8_t) key[4]);
333 tmp16 = (uint16_t) PutLoByte(tmp16, (uint8_t) key[5]);
334 firstUInt32 = (uint32_t) PutHiWord(firstUInt32, (uint16_t) tmp16);
335 tmp16 = (uint16_t) PutHiByte(tmp16, (uint8_t) key[6]);
336 tmp16 = (uint16_t) PutLoByte(tmp16, (uint8_t) key[7]);
337 firstUInt32 = (uint32_t) PutLoWord(firstUInt32, (uint16_t) tmp16);
339 sum = firstUInt32 + secondUInt32;
341 /* if nmbBins is a power of 2, use shift, else use division */
342 if (hashListCp->binBitMask != CM_HASH_NOBITMASK)
343 *idx = (uint16_t) (sum & hashListCp->binBitMask);
345 *idx = (uint16_t) (sum % hashListCp->nmbBins);
348 } /* end of cmHashFuncBCD8 () */
352 * Fun: cmHashFuncString
354 * Desc: Computes the hash list index (bin number) for a specified
355 * key of type CM_HASH_KEYTYPE_STR.
357 * for (length of string)
358 * idx = (31 * idx) + *string;
360 * return (idx % hash_table_size);
362 * Ret: ROK - successful, *idx contains computed index
370 static S16 cmHashFuncString
372 CmHashListCp *hashListCp, /* hash list control point */
373 uint8_t *key, /* key string */
374 uint16_t keyLen, /* length of key string */
375 uint16_t *idx /* idx to return */
378 uint16_t cntr; /* Index */
379 uint32_t sum; /* Sum of octets for hash function */
384 for (cntr = 0; cntr < keyLen; cntr++)
386 sum = (CM_STR_HASHFUNC_CONSTANT * sum) + key[cntr];
389 /* if nmbBins is a power of 2, use shift, else use division */
390 if (hashListCp->binBitMask != CM_HASH_NOBITMASK)
391 *idx = (uint16_t) (sum & hashListCp->binBitMask);
393 *idx = (uint16_t) (sum % hashListCp->nmbBins);
397 } /* end of cmHashFuncString () */
403 * Fun: cmHashFuncDefault
405 * Desc: Computes the hash list index (bin number) for a specified
406 * key of type CM_HASH_KEYTYPE_DEF.
408 * Adds up all the octets of the key string
409 * and divides the sum by the range to get the desired index.
411 * Ret: ROK - successful, *idx contains computed index
419 static S16 cmHashFuncDefault
421 CmHashListCp *hashListCp, /* hash list control point */
422 uint8_t *key, /* key string */
423 uint16_t keyLen, /* length of key string */
424 uint16_t *idx /* index to return */
427 uint32_t sum; /* sum of key string octets */
430 /* add all bytes of the key */
433 sum += (uint32_t) (*key++);
435 /* compute index by dividing the range into the sum */
437 /* if nmbBins is a power of 2, use shift, else use division */
438 if (hashListCp->binBitMask != CM_HASH_NOBITMASK)
439 *idx = (uint16_t) (sum & hashListCp->binBitMask);
441 *idx = (uint16_t) (sum % hashListCp->nmbBins);
445 } /* end of cmHashFuncDefault */
450 * Fun: cmHashFuncMult24
452 * Desc: Computes the hash list index (bin number) for a specified
453 * key of type CM_HASH_KEYTYPE_MULT24.
455 * Multiplies the given key (max k bits) with a constant
456 * multiplier and extracts p bits of the result, from the
457 * bit position k-1 to bit position k-p, to get the hash
458 * list index. p is such that 2^p is number of bins.
460 * The constant multiplier is the floor of A * 2^k, for
463 * This function uses a pre-computed constant multiplier
464 * CM_HASH_MULTMETHOD_CNST24, which is computed for
465 * A = (sqrt(5) - 1)/2, and k = 24 bits.
467 * This hashing method is explained in section 12.3.2 of
468 * "Introduction to Algorithms" by Thomas H. Cormen et al.,
471 * Ret: ROK - successful, *idx contains computed index
479 static S16 cmHashFuncMult24
481 CmHashListCp *hashListCp, /* hash list control point */
482 uint8_t *key, /* key string */
483 uint16_t keyLen, /* length of key string */
484 uint16_t *idx /* index to return */
487 uint32_t prod; /* (constant multiplier * key) */
488 uint8_t shift; /* Bits to be shifted to get index */
493 #if (ERRCLASS & ERRCLS_DEBUG)
494 /* error check on parameters */
495 if (hashListCp->binBitMask == CM_HASH_NOBITMASK)
499 prod = CM_HASH_MULT24_CONST * *((uint32_t *)key);
501 shift = CM_HASH_MULT24_BITPOS - hashListCp->nmbBinBits;
502 *idx = ((uint16_t) (prod & (hashListCp->binBitMask << shift))) >> shift;
505 } /* end of cmHashFuncMult24 */
512 * Fun: cmHashFuncConId
514 * Desc: Computes the hash list index (bin number) for a specified
515 * key of type CM_HASH_KEYTYPE_CONID.
517 * This function can be used for keys that are an integer whose
518 * size is uint8_t, uint16_t or uint32_t. Instead of adding all octets of the key,
519 * this fn computes the "index" of the bin in which the entry
520 * needs to be inserted by taking a modulo of the integer with the
521 * total number of bins.
522 * This function is typically suitable for a sequentially increasing
523 * number like suConnId/spConnId
525 * Ret: ROK - successful, *idx contains computed index
533 static S16 cmHashFuncConId
535 CmHashListCp *hashListCp, /* hash list control point */
536 uint8_t *key, /* key string */
537 uint16_t keyLen, /* length of key string */
538 uint16_t *idx /* index to return */
543 /* switch based on the length of the key */
546 case CM_HASHKEYLEN_UINT32:
547 if (hashListCp->binBitMask != CM_HASH_NOBITMASK)
548 *idx = (uint16_t) (((uint32_t) *((uint32_t *)key)) & hashListCp->binBitMask);
550 *idx = (uint16_t) (((uint32_t) *((uint32_t *)key)) % hashListCp->nmbBins);
553 case CM_HASHKEYLEN_UINT16:
554 if (hashListCp->binBitMask != CM_HASH_NOBITMASK)
555 *idx = (uint16_t) (((uint16_t)*((uint16_t *)key)) & hashListCp->binBitMask);
557 *idx = (uint16_t) (((uint16_t)*((uint16_t *)key)) % hashListCp->nmbBins);
560 case CM_HASHKEYLEN_UINT8:
561 if (hashListCp->binBitMask != CM_HASH_NOBITMASK)
562 *idx = (uint16_t) (((uint8_t)*((uint8_t *)key)) & hashListCp->binBitMask);
564 *idx = (uint16_t) (((uint8_t)*((uint8_t *)key)) % hashListCp->nmbBins);
572 } /* end of cmHashFuncConId */
578 * Fun: cmHashFuncDirIdx
580 * Desc: Computes the hash list index (bin number) for a specified
581 * key of type CM_HASH_KEYTYPE_DIRINDEX.
583 * The key is the hash table index.
585 * Ret: ROK - successful, *idx contains computed index
593 static S16 cmHashFuncDirIdx
595 CmHashListCp *hashListCp, /* hash list control point */
596 uint8_t *key, /* key string */
597 uint16_t keyLen, /* length of key string */
598 uint16_t *idx /* index to return */
605 *idx = *((uint16_t *) key);
608 } /* end of cmHashFuncDirIdx */
613 * Fun: cmHashMatchKey
615 * Desc: Compares two keys and determines if they match.
617 * Ret: ROK - match successful
618 * RFAILED - match failed (non-matching key values)
626 static S16 cmHashMatchKey
628 uint8_t *key1, /* first key string */
629 uint16_t keyLen1, /* length of first key string */
630 uint8_t *key2, /* second key string */
631 uint16_t keyLen2 /* length of second key string */
635 /* compare key lengths */
636 if (keyLen1 != keyLen2)
639 /* compare key strings */
640 return (cmMemcmp(key1, key2, (PTR) keyLen1));
641 } /* end of cmHashMatchKey */
648 * Desc: Adds an entry into a doubly linked list
650 * Ret: ROK - insertion successful
658 static S16 cmListInsert
660 CmListEnt *oldEntry, /* add new entry after this entry */
661 CmListEnt *newEntry /* new entry to add */
665 newEntry->next = oldEntry->next;
666 newEntry->prev = oldEntry;
667 oldEntry->next = newEntry;
668 (newEntry->next)->prev = newEntry;
671 } /* end of cmListInsert */
678 * Desc: Deletes an entry from a doubly linked list
680 * Ret: ROK - deletion successful
688 static S16 cmListDelete
690 CmListEnt *entry /* entry to delete */
697 if (entry->prev != NULLP)
698 (entry->prev)->next = entry->next;
700 if (entry->next != NULLP)
701 (entry->next)->prev = entry->prev;
704 } /* end of cmListDelete */
715 * Fun: cmHashListInit
717 * Desc: Initializes a hash list. Parameters are:
719 * hashListCp control point for hash list
720 * nmbBins number of bins in the hash list. Storage will
721 * be allocated for them from the indicated memory
723 * offset if the entries in this hash list are also going
724 * to be attached to another hash list, they will
725 * contain multiple hash list entry headers. The
726 * offset indicates the offset of the entry header
727 * for this hash list in the entry structure.
728 * dupFlg whether entries with duplicate keys are allowed
729 * to be inserted in the hash list.
730 * keyType indicates type of key which can be used to select
731 * different hash functions. Ignored in this
734 * pool for allocating storage for bins.
736 * Ret: ROK - initialization successful
737 * RFAILED - initialization failed, lack of memory
746 CmHashListCp *hashListCp, /* hash list to initialize */
747 uint16_t nmbBins, /* number of hash list bins */
748 uint16_t offset, /* offset of CmHashListEnt in entries */
749 Bool dupFlg, /* allow duplicate keys */
750 uint16_t keyType, /* key type for selecting hash fn */
751 Region region, /* memory region to allocate bins */
752 Pool pool /* memory pool to allocate bins */
756 #ifndef CM_MT_HASH_BIN
763 #if (ERRCLASS & ERRCLS_DEBUG)
764 /* error check on parameters */
765 if (hashListCp == NULLP)
769 /* initialize control point fields */
770 hashListCp->hl = NULLP;
771 hashListCp->region = region;
772 hashListCp->pool = pool;
773 hashListCp->nmbBins = 0;
774 hashListCp->binBitMask = CM_HASH_NOBITMASK;
775 hashListCp->nmbBinBits = 0;
776 #ifndef CM_MT_HASH_BIN
777 hashListCp->nmbEnt = 0;
779 hashListCp->offset = offset;
780 hashListCp->dupFlg = dupFlg;
781 hashListCp->keyType = keyType;
782 hashListCp->hashFunc = NULLP;
784 /* initialize hash function for this key type */
787 case CM_HASH_KEYTYPE_MULT24:
788 /* return failure if number of bins is not a power of 2 */
789 if (((nmbBins) & (nmbBins - 1)) != 0)
792 hashListCp->hashFunc = cmHashFuncMult24;
795 case CM_HASH_KEYTYPE_DIRIDX:
796 hashListCp->hashFunc = cmHashFuncDirIdx;
799 case CM_HASH_KEYTYPE_STR:
800 hashListCp->hashFunc = cmHashFuncString;
803 case CM_HASH_KEYTYPE_UINT32_MOD:
804 hashListCp->hashFunc = cmHashFuncU32Mod;
807 case CM_HASH_KEYTYPE_BCD8:
808 hashListCp->hashFunc = cmHashFuncBCD8;
811 case CM_HASH_KEYTYPE_ANY:
812 hashListCp->hashFunc = cmHashFuncAnyKey;
815 case CM_HASH_KEYTYPE_CONID:
816 hashListCp->hashFunc = cmHashFuncConId;
819 case CM_HASH_KEYTYPE_DEF: /* default hash function */
820 default: /* illegal key type */
821 hashListCp->hashFunc = cmHashFuncDefault;
825 /* allocate memory for bins */
828 #ifndef CM_MT_HASH_BIN
829 if (SGetSBuf(region, pool, (Data **) &hashListCp->hl,
830 (Size) (nmbBins * sizeof(CmListEnt))) != ROK)
833 if (SGetSBuf(region, pool, (Data **) &hashListCp->hl,
834 (Size) (nmbBins * sizeof(CmListBinEnt))) != ROK)
838 /* initialize bin pointers */
840 for(i = 0; i < nmbBins; i++)
842 #ifndef CM_MT_HASH_BIN
843 hl[i].next = hl[i].prev = &hl[i];
845 /* This initialization is being done as a part of checking
846 * the presence of empty/non-empty bins.
848 hl[i].next = hl[i].prev = (CmListEnt*)&hl[i];
853 /* initialize bin size */
854 hashListCp->nmbBins = nmbBins;
856 /* initialize bin bit mask */
857 if (((nmbBins) & (nmbBins - 1)) == 0)
861 /* number of bins is a power of 2 */
862 hashListCp->binBitMask = nmbBins - 1;
864 /* compute number of bits in the bit mask */
865 for (binBitMask = hashListCp->binBitMask; binBitMask; binBitMask >>= 1)
866 hashListCp->nmbBinBits++;
872 } /* end of cmHashListInit */
877 * Fun: cmHashListDeinit
879 * Desc: Deinitializes a hash list. Deallocates memory for bins
880 * and resets header fields. Parameters are:
882 * hashListCp control point for hash list
884 * Ret: ROK - successful
893 CmHashListCp *hashListCp /* hash list to deinitialize */
897 #if (ERRCLASS & ERRCLS_DEBUG)
898 /* error check on parameters */
899 if (hashListCp == NULLP)
903 /* deallocate memory for bins */
904 if (hashListCp->nmbBins)
905 #ifndef CM_MT_HASH_BIN
906 (Void) SPutSBuf(hashListCp->region, hashListCp->pool,
907 (Data *) hashListCp->hl,
908 (Size) (hashListCp->nmbBins * sizeof(CmListEnt)));
910 (Void) SPutSBuf(hashListCp->region, hashListCp->pool,
911 (Data *) hashListCp->hl,
912 (Size) (hashListCp->nmbBins * sizeof(CmListBinEnt)));
915 /* deinitialize control point fields */
916 hashListCp->hl = NULLP;
917 hashListCp->region = REGIONNC;
918 hashListCp->pool = 0;
919 hashListCp->nmbBins = 0;
920 hashListCp->binBitMask = CM_HASH_NOBITMASK;
921 #ifndef CM_MT_HASH_BIN
922 hashListCp->nmbEnt = 0;
924 hashListCp->offset = 0;
925 hashListCp->dupFlg = FALSE;
926 hashListCp->keyType = CM_HASH_KEYTYPE_DEF;
927 hashListCp->hashFunc = NULLP;
930 } /* end of cmHashListDeinit */
935 * Fun: cmHashListInsert
937 * Desc: Inserts a new entry in the hash list. Parameters are:
939 * hashListCp control point for hash list
940 * entry pointer to new entry to add in the hash list
941 * key pointer to key string in the new entry
942 * keyLen length of key string
944 * Ret: ROK - insertion successful
945 * ROKDUP - insertion failed (duplicate key not allowed)
946 * RFAILED - insertion failed (incorrect parameter values)
956 CmHashListCp *hashListCp, /* hash list to add to */
957 PTR entry, /* entry to add */
958 uint8_t *key, /* pointer to key */
959 uint16_t keyLen /* length of key */
962 CmHashListEnt *hashListEnt; /* pointer to hash list entry header */
963 PTR dupEntry; /* pointer to entry with duplicate key */
964 uint16_t idx; /* index for insertion into hash list */
967 #if (ERRCLASS & ERRCLS_DEBUG)
968 /* error check on parameters */
969 if ((hashListCp == NULLP) || (entry == NULLP) ||
970 (key == NULLP) || (keyLen == 0))
974 /* check for duplicates */
975 if (hashListCp->dupFlg == FALSE)
977 /* no duplicates allowed, check if key already exists */
978 if (cmHashListFind(hashListCp, key, keyLen, 0, &dupEntry) == ROK)
982 /* get pointer to hash list entry header */
983 hashListEnt = (CmHashListEnt *) (((uint8_t *) entry) + hashListCp->offset);
985 /* initialize hash list entry header */
986 hashListEnt->list.next = NULLP;
987 hashListEnt->list.prev = NULLP;
988 hashListEnt->keyLen = keyLen;
989 hashListEnt->key = key;
991 /* compute index for insertion */
992 if ((*hashListCp->hashFunc)(hashListCp, key, keyLen, &idx) != ROK)
995 hashListEnt->hashVal = idx;
997 /* insert into list */
998 cmListInsert(hashListCp->hl[idx].prev, &hashListEnt->list);
1000 /* increment count of entries in hash list */
1001 #ifndef CM_MT_HASH_BIN
1002 hashListCp->nmbEnt++;
1004 hashListCp->hl[idx].nmbEnt++;
1005 #endif /* #ifndef CM_MT_HASH_BIN */
1008 } /* end of cmHashListInsert */
1013 * Fun: cmHashListDelete
1015 * Desc: Deletes an entry from the hash list. Parameters are:
1017 * hashListCp control point for hash list
1018 * entry pointer to entry to delete from the hash list
1020 * Ret: ROK - deletion successful
1021 * RFAILED - deletion failed (incorrect parameter values)
1029 S16 cmHashListDelete
1031 CmHashListCp *hashListCp, /* hash list to delete from */
1032 PTR entry /* entry to delete */
1035 CmHashListEnt *hashListEnt; /* pointer to hash list entry header */
1036 #ifdef CM_MT_HASH_BIN
1037 uint16_t idx; /* index for selecting the right hash list bin */
1041 #if (ERRCLASS & ERRCLS_DEBUG)
1042 /* error check on parameters */
1043 if ((hashListCp == NULLP) || (entry == NULLP))
1047 /* get pointer to hash list entry header */
1048 hashListEnt = (CmHashListEnt *) (((uint8_t *) entry) + hashListCp->offset);
1050 /* check if entry is already deleted if yes then return OK */
1051 if((hashListEnt->list.next == NULLP) ||
1052 (hashListEnt->list.prev == NULLP))
1055 #ifdef CM_MT_HASH_BIN
1056 /* compute index for insertion */
1057 if ((*hashListCp->hashFunc)(hashListCp, hashListEnt->key,
1058 hashListEnt->keyLen, &idx) != ROK)
1060 #endif /* #ifdef CM_MT_HASH_BIN */
1062 /* delete entry from list */
1063 cmListDelete(&hashListEnt->list);
1065 /* reinitialize hash list entry header */
1066 hashListEnt->list.next = NULLP;
1067 hashListEnt->list.prev = NULLP;
1068 hashListEnt->keyLen = 0;
1069 hashListEnt->key = NULLP;
1070 hashListEnt->hashVal = 0;
1072 /* decrement count of entries in hash list */
1073 #ifndef CM_MT_HASH_BIN
1074 hashListCp->nmbEnt--;
1076 /* Find the right bin index and decrement the nmbEnt counter */
1077 hashListCp->hl[idx].nmbEnt--;
1078 #endif /* #ifndef CM_MT_HASH_BIN */
1081 } /* end of cmHashListDelete */
1086 * Fun: cmHashListFind
1088 * Desc: Finds an entry in the hash list. Parameters are:
1090 * hashListCp control point for hash list
1091 * key pointer to key string for search
1092 * keyLen length of key string
1093 * seqNmb sequence number in case duplicates allowed
1094 * entry pointer to found entry
1096 * Ret: ROK - find successful, *entry points to found entry
1097 * RFAILED - find failed, *entry is unchanged
1098 * (incorrect parameter values, key not found)
1108 CmHashListCp *hashListCp, /* hash list to search */
1109 uint8_t *key, /* pointer to key */
1110 uint16_t keyLen, /* length of key */
1111 uint16_t seqNmb, /* used in case of duplicate keys */
1112 PTR *entry /* entry to be returned */
1115 CmHashListEnt *hashListEnt; /* pointer to hash list entry header */
1116 #ifndef CM_MT_HASH_BIN
1117 CmListEnt *hashListBin; /* pointer to hash list bin */
1119 CmListBinEnt *hashListBin; /* pointer to hash list bin */
1120 uint16_t entCnt=0; /* counter for number of entries */
1122 uint16_t i; /* counter for sequence number */
1123 uint16_t idx; /* index for insertion into hash list */
1126 #if (ERRCLASS & ERRCLS_DEBUG)
1127 /* error check on parameters */
1128 if ((hashListCp == NULLP) || (key == NULLP) ||
1129 (keyLen == 0) || (entry == NULLP))
1133 /* compute hash table index */
1134 if ((*hashListCp->hashFunc)(hashListCp, key, keyLen, &idx) != ROK)
1137 /* search this bin for exact key match */
1138 hashListBin = &hashListCp->hl[idx];
1139 hashListEnt = (CmHashListEnt *) hashListBin->next;
1141 /* examine each entry in bin */
1143 #ifndef CM_MT_HASH_BIN
1144 while (hashListBin != (CmListEnt *) hashListEnt)
1146 for (entCnt=0; entCnt < hashListBin->nmbEnt; entCnt++)
1149 /* check if key matches */
1150 if (cmHashMatchKey(hashListEnt->key, hashListEnt->keyLen, key, keyLen)
1154 *entry = (PTR) (((uint8_t *) hashListEnt) - hashListCp->offset);
1156 /* check for duplicates */
1157 if (!hashListCp->dupFlg)
1160 /* for duplicate key, check sequence number */
1165 /* go to next entry */
1166 hashListEnt = (CmHashListEnt *) hashListEnt->list.next;
1169 /* no matching key found */
1171 } /* end of cmHashListFind */
1176 * Fun: cmHashListGetNext
1178 * Desc: Gets next entry in hash list with respect to the specified
1179 * previous entry. If previous entry is NULLP, gets first
1180 * entry in hash list. Parameters are:
1182 * hashListCp control point for hash list
1183 * prevEnt pointer to previous entry
1184 * entry pointer to next entry to be returned
1186 * Ret: ROK - get successful, *entry points to found entry
1187 * (at beginning of list or in the list)
1188 * RFAILED - get failed, *entry is unchanged
1189 * (incorrect parameter values)
1190 * ROKDNA - get failed, *entry is unchanged.
1193 * Notes: This function has to be used cautiously while the
1194 * CM Hash Module is being compiled with CM_MT_HASH_BIN.
1195 * In such cases, this function should be used only after
1196 * ensuring that none of the other threads are operating
1197 * on the common hash list.
1202 S16 cmHashListGetNext
1204 CmHashListCp *hashListCp, /* hash list to get from */
1205 PTR prevEnt, /* previous entry */
1206 PTR *entry /* entry to be returned */
1209 #ifndef CM_MT_HASH_BIN
1210 CmListEnt *hashListBin; /* temporary hash list bin pointer */
1212 CmListBinEnt *hashListBin; /* temporary hash list bin pointer */
1214 CmHashListEnt *hashListEnt; /* temporary hash list entry pointer */
1215 CmHashListEnt *prevListEnt; /* previous hash list entry pointer */
1216 uint16_t i; /* hash list counter */
1219 #if (ERRCLASS & ERRCLS_DEBUG)
1220 /* error check on parameters */
1221 if ((hashListCp == NULLP) || (entry == NULLP))
1225 /* check if need to get first entry */
1226 if (prevEnt == NULLP)
1228 /* get first entry in hash list */
1229 for (i = 0; i < hashListCp->nmbBins; i++)
1230 /* check for non-empty bin */
1231 #ifndef CM_MT_HASH_BIN
1232 if (hashListCp->hl[i].next != &hashListCp->hl[i])
1234 if (hashListCp->hl[i].next != (CmListEnt*)&hashListCp->hl[i])
1237 /* get first entry in bin */
1238 hashListEnt = (CmHashListEnt *) hashListCp->hl[i].next;
1240 /* requested entry is in nxtEnt */
1241 *entry = (PTR) (((uint8_t *) hashListEnt) - hashListCp->offset);
1246 /* no more entries */
1250 /* use previous entry to find next entry */
1252 /* get pointer to previous hash list entry header */
1253 prevListEnt = (CmHashListEnt *) (((uint8_t *) prevEnt) + hashListCp->offset);
1255 /* get index of previous entry */
1256 i = prevListEnt->hashVal;
1258 /* set pointers to get next entry */
1259 hashListBin = &hashListCp->hl[i];
1260 prevListEnt = (CmHashListEnt *) prevListEnt->list.next;
1263 /* check if more entries in this bin */
1264 if (prevListEnt != (CmHashListEnt *) hashListBin)
1266 /* found next entry */
1267 *entry = (PTR) (((uint8_t *) prevListEnt) - hashListCp->offset);
1272 /* no more entries in this bin, go to next bin, check if more bins */
1273 if (++i >= hashListCp->nmbBins)
1274 /* no more entries */
1277 /* reset pointers for next bin */
1278 hashListBin = &hashListCp->hl[i];
1279 prevListEnt = (CmHashListEnt *) hashListBin->next;
1282 /* no more entries */
1284 } /* end of cmHashListGetNext */
1286 #ifdef CM_MT_HASH_BIN
1290 * Fun: cmHashListBinGetNextEntry
1292 * Desc: Gets next entry in a given hash bin respect to the specified
1293 * previous entry. If previous entry is NULLP, gets first
1294 * entry in hash bin. Parameters are:
1296 * hashListCp control point for hash list
1297 * binIdx Bin Index to find the entry in
1298 * prevEnt pointer to previous entry
1299 * entry pointer to next entry to be returned
1301 * Ret: ROK - get successful, *entry points to found entry
1302 * (at beginning of list or in the list)
1303 * RFAILED - get failed, *entry is unchanged
1304 * (incorrect parameter values)
1305 * ROKDNA - get failed, *entry is unchanged.
1312 S16 cmHashListBinGetNextEntry
1314 CmHashListCp *hashListCp, /* hash list to get from */
1315 uint16_t binIdx, /* Bin Index to retreive the entry */
1316 PTR prevEnt, /* previous entry */
1317 PTR *entry /* entry to be returned */
1320 CmListBinEnt *hashListBin; /* temporary hash list bin pointer */
1321 CmHashListEnt *hashListEnt; /* temporary hash list entry pointer */
1322 CmHashListEnt *prevListEnt; /* previous hash list entry pointer */
1325 #if (ERRCLASS & ERRCLS_DEBUG)
1326 /* error check on parameters */
1327 if ((hashListCp == NULLP) || (entry == NULLP))
1331 /* check if need to get first entry */
1332 if (prevEnt == NULLP)
1334 /* get first entry in hash list */
1335 /* check for non-empty bin */
1336 if (hashListCp->hl[binIdx].next != (CmListEnt*)&hashListCp->hl[binIdx])
1338 /* get first entry in bin */
1339 hashListEnt = (CmHashListEnt *) hashListCp->hl[binIdx].next;
1341 /* requested entry is in nxtEnt */
1342 *entry = (PTR) (((uint8_t *) hashListEnt) - hashListCp->offset);
1347 /* no more entries */
1351 /* use previous entry to find next entry */
1353 /* get pointer to previous hash list entry header */
1354 prevListEnt = (CmHashListEnt *) (((uint8_t *) prevEnt) + hashListCp->offset);
1356 /* set pointers to get next entry */
1357 hashListBin = &hashListCp->hl[binIdx];
1358 prevListEnt = (CmHashListEnt *) prevListEnt->list.next;
1360 /* check if more entries in this bin */
1361 if (prevListEnt != (CmHashListEnt *) hashListBin)
1363 /* found next entry */
1364 *entry = (PTR) (((uint8_t *) prevListEnt) - hashListCp->offset);
1369 /* no more entries */
1371 } /* end of cmHashListBinGetNextEntry */
1377 * Fun: cmHashListQuery
1379 * Desc: Gets hash list attributes. Parameters are:
1381 * hashListCp control point for hash list
1382 * queryType type of attribute being queried
1383 * result result of query, to be returned
1385 * Ret: ROK - successful, *result contains query result
1386 * RFAILED - failed, *result unchanged (incorrect parameter values)
1388 * Notes: This function is obsoleted!
1389 * Use macros defined in cm_hash.h instead
1396 CmHashListCp *hashListCp, /* hash list to query */
1397 uint8_t queryType, /* type of query */
1398 uint16_t *result /* result of query */
1401 #ifdef CM_MT_HASH_BIN
1406 /* deal with queries that do not need hashListCp */
1408 #if (ERRCLASS & ERRCLS_DEBUG)
1409 /* error check on parameters */
1410 if (result == NULLP)
1414 /* respond depending on query type */
1415 if (queryType == CM_HASH_QUERYTYPE_BINSIZE)
1417 /* storage for each bin */
1418 #ifndef CM_MT_HASH_BIN
1419 *result = (uint16_t) sizeof(CmListEnt);
1421 *result = (uint16_t) sizeof(CmListBinEnt);
1426 /* deal with queries that do need hashListCp */
1428 #if (ERRCLASS & ERRCLS_DEBUG)
1429 /* error check on parameters */
1430 if (hashListCp == NULLP)
1434 /* respond depending on query type */
1437 case CM_HASH_QUERYTYPE_ENTRIES: /* current number of entries */
1438 #ifndef CM_MT_HASH_BIN
1439 *result = (uint16_t) hashListCp->nmbEnt;
1442 for (i=0; i < hashListCp->nmbBins; i++)
1444 *result += hashListCp->hl[i].nmbEnt;
1449 case CM_HASH_QUERYTYPE_BINS: /* number of bins */
1450 *result = (uint16_t) hashListCp->nmbBins;
1453 case CM_HASH_QUERYTYPE_OFFSET: /* offset of CmHashListEnt in entries */
1454 *result = (uint16_t) hashListCp->offset;
1457 case CM_HASH_QUERYTYPE_DUPFLG: /* allow duplicate keys */
1458 *result = (uint16_t) hashListCp->dupFlg;
1461 case CM_HASH_QUERYTYPE_KEYTYPE: /* key type for selecting hash functions */
1462 *result = (uint16_t) hashListCp->keyType;
1465 default: /* process other query types */
1469 /* illegal query type */
1471 } /* end of cmHashListQuery */
1473 #ifdef HASH_OPEN_ADDRESSING
1477 * Fun: cmHashListOAInsert
1479 * Desc: Inserts a new entry in the hash list with open addressing.
1482 * hashListCp control point for hash list
1483 * entry pointer to new entry to add in the hash list
1484 * key pointer to key string in the new entry
1485 * keyLen length of key string
1487 * Ret: ROK - insertion successful
1488 * ROKDUP - insertion failed (duplicate key not allowed)
1489 * RFAILED - insertion failed (incorrect parameter values)
1497 S16 cmHashListOAInsert
1499 CmHashListCp *hashListCp, /* hash table to add to */
1500 PTR entry, /* entry to add */
1501 uint8_t *key, /* pointer to key */
1502 uint16_t keyLen /* length of key */
1505 /* cm_hash_c_001.main_21. Modify. Compilation Issue resolved. */
1506 #ifndef CM_MT_HASH_BIN
1507 CmListEnt *hashBin; /* temporary hash list bin pointer */
1509 CmListBinEnt *hashBin; /* temporary hash list bin pointer */
1511 CmHashListEnt *hashListEnt; /* pointer to hash list entry header */
1512 uint16_t idx; /* index for insertion into hash list */
1513 uint16_t hashSize; /* hash size */
1515 /* cm_hash_c_001.main_21. Modify. Compilation Issue resolved. */
1519 #if (ERRCLASS & ERRCLS_DEBUG)
1520 /* error check on parameters */
1521 if ((hashListCp == NULLP) || (entry == NULLP) ||
1522 (key == NULLP) || (keyLen == 0))
1526 #ifndef CM_MT_HASH_BIN
1527 nmbEnt = hashListCp->nmbEnt;
1530 for (i=0; i < hashListCp->nmbBins; i++)
1532 nmbEnt += hashListCp->hl[i].nmbEnt;
1535 /* check if table is full */
1536 if (hashListCp->nmbBins == nmbEnt)
1539 /* get pointer to hash list entry header */
1540 hashListEnt = (CmHashListEnt *) (((uint8_t *) entry) + hashListCp->offset);
1542 /* initialize hash list entry header */
1543 hashListEnt->list.next = NULLP;
1544 hashListEnt->list.prev = NULLP;
1545 hashListEnt->keyLen = keyLen;
1546 hashListEnt->key = key;
1548 /* compute index for insertion */
1549 if ((*hashListCp->hashFunc)(hashListCp, key, keyLen, &idx) != ROK)
1555 hashSize = hashListCp->nmbBins;
1556 hashBin = &hashListCp->hl[idx];
1557 for (i = hashSize; i > 0; i--)
1559 if (hashBin->next == hashBin)
1561 if (++idx >= hashSize)
1564 hashBin = &hashListCp->hl[0];
1570 /* insert into list */
1571 if (cmListInsert(hashBin->prev, &hashListEnt->list) != ROK)
1574 hashListEnt->hashVal = idx;
1576 #ifndef CM_MT_HASH_BIN
1577 /* increment count of entries in hash list */
1578 hashListCp->nmbEnt++;
1584 } /* end of cmHashListOAInsert */
1587 #endif /* HASH_OPENADDRESSING */
1589 /**********************************************************************
1591 **********************************************************************/