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
175 static S16 cmHashFuncAnyKey
177 CmHashListCp *hashListCp, /* hash list control point */
178 uint8_t *key, /* key string */
179 uint16_t keyLen, /* length of key string */
180 uint16_t *idx /* idx to return */
183 static S16 cmHashFuncAnyKey (hashListCp, key, keyLen, idx)
184 CmHashListCp *hashListCp; /* hash list control point */
185 uint8_t *key; /* key string */
186 uint16_t keyLen; /* length of key string */
187 uint16_t *idx; /* idx to return */
190 uint32_t a; /* hash variables */
191 uint32_t b; /* hash variables */
192 uint32_t c; /* hash variables */
193 uint32_t len; /* length */
195 /*cm_hash_c_001.main_23 : Fix for TRACE5 feature crash due to missing TRC MACRO*/
196 /* Set up the internal state */
197 len = keyLen; /* key length */
198 a = 0x9e3779b9; /* a = b = the golden ratio; an arbitrary value */
200 c = 0x12345678; /* some value */
202 /*---------------------------------------- handle most of the key */
205 a += (key[0] +((uint32_t)key[1]<<8) +((uint32_t)key[2]<<16) +((uint32_t)key[3]<<24));
206 b += (key[4] +((uint32_t)key[5]<<8) +((uint32_t)key[6]<<16) +((uint32_t)key[7]<<24));
207 c += (key[8] +((uint32_t)key[9]<<8) +((uint32_t)key[10]<<16)+((uint32_t)key[11]<<24));
208 CM_HASH_MIX(a, b, c);
209 key += 12; len -= 12;
212 /*------------------------------------- handle the last 11 bytes */
214 switch(len) /* all the case statements fall through */
216 case 11: c+=((uint32_t)key[10]<<24);
217 case 10: c+=((uint32_t)key[9]<<16);
218 case 9 : c+=((uint32_t)key[8]<<8);
219 /* the first byte of c is reserved for the keyLen */
220 case 8 : b+=((uint32_t)key[7]<<24);
221 case 7 : b+=((uint32_t)key[6]<<16);
222 case 6 : b+=((uint32_t)key[5]<<8);
224 case 4 : a+=((uint32_t)key[3]<<24);
225 case 3 : a+=((uint32_t)key[2]<<16);
226 case 2 : a+=((uint32_t)key[1]<<8);
228 /* case 0: nothing left to add */
231 /*-------------------------------------------- report the result */
233 /* if nmbBins is a power of 2, use shift, else use division */
234 if (hashListCp->binBitMask != CM_HASH_NOBITMASK)
235 *idx = (uint16_t) (c & hashListCp->binBitMask);
237 *idx = (uint16_t) (c % hashListCp->nmbBins);
240 } /* end of cmHashFuncAnyKey */
245 * Fun: cmHashFuncU32Mod
247 * Desc: Computes the hash list index (bin number) for a specified
248 * key of type CM_HASH_KEYTYPE_MOD.
250 * return (idx % hash_table_size);
252 * Ret: ROK - successful, *idx contains computed index
261 static S16 cmHashFuncU32Mod
263 CmHashListCp *hashListCp, /* hash list control point */
264 uint8_t *key, /* key string */
265 uint16_t keyLen, /* length of key string */
266 uint16_t *idx /* idx to return */
269 static S16 cmHashFuncU32Mod (hashListCp, key, keyLen, idx)
270 CmHashListCp *hashListCp; /* hash list control point */
271 uint8_t *key; /* key string */
272 uint16_t keyLen; /* length of key string */
273 uint16_t *idx; /* idx to return */
276 uint32_t sum; /* Sum of octets for hash function */
279 /* keyLen is marked Unused to remove compilation
283 sum = *((uint32_t *)key);
285 /* if nmbBins is a power of 2, use shift, else use division */
286 if (hashListCp->binBitMask != CM_HASH_NOBITMASK)
287 *idx = (uint16_t) (sum & hashListCp->binBitMask);
289 *idx = (uint16_t) (sum % hashListCp->nmbBins);
293 } /* end of cmHashFuncU32Mod () */
297 * Fun: cmHashFuncBCD8
299 * Desc: Computes the hash list index (bin number) for a specified
300 * key of type CM_HASH_KEYTYPE_BCD8.
303 * 1. Converts the 8 BCD coded octets into 2 uint32_ts
304 * 2. Adds 2 uint32_ts to get one uint32_t.
305 * 3. Apply uint32_tMod technique to get the index
306 * 4. Return the index
309 * Here we are no bothered if the keyLen is more than 8.
310 * We are interested only in the first 8 octets.
312 * Ret: ROK - successful, *idx contains computed index
321 static S16 cmHashFuncBCD8
323 CmHashListCp *hashListCp, /* hash list control point */
324 uint8_t *key, /* key string */
325 uint16_t keyLen, /* length of key string */
326 uint16_t *idx /* idx to return */
329 static S16 cmHashFuncBCD8 (hashListCp, key, keyLen, idx)
330 CmHashListCp *hashListCp; /* hash list control point */
331 uint8_t *key; /* key string */
332 uint16_t keyLen; /* length of key string */
333 uint16_t *idx; /* idx to return */
337 uint32_t firstUInt32 = 0; /* First uint32_t prepared for lower 4 octets */
338 uint32_t secondUInt32 = 0; /* Second uint32_t prepared for higher 4 octets */
339 uint32_t sum; /* Sum of the above 2 octets to get the index */
342 /* keyLen is marked Unused to remove compilation
346 /* Compute second uint32_t */
347 tmp16 = (uint16_t) PutHiByte(tmp16, (uint8_t) key[0]);
348 tmp16 = (uint16_t) PutLoByte(tmp16, (uint8_t) key[1]);
349 secondUInt32 = (uint32_t) PutHiWord(secondUInt32, (uint16_t) tmp16);
350 tmp16 = (uint16_t) PutHiByte(tmp16, (uint8_t) key[2]);
351 tmp16 = (uint16_t) PutLoByte(tmp16, (uint8_t) key[3]);
352 secondUInt32 = (uint32_t) PutLoWord(secondUInt32, (uint16_t) tmp16);
355 /* Compute first uint32_t */
356 tmp16 = (uint16_t) PutHiByte(tmp16, (uint8_t) key[4]);
357 tmp16 = (uint16_t) PutLoByte(tmp16, (uint8_t) key[5]);
358 firstUInt32 = (uint32_t) PutHiWord(firstUInt32, (uint16_t) tmp16);
359 tmp16 = (uint16_t) PutHiByte(tmp16, (uint8_t) key[6]);
360 tmp16 = (uint16_t) PutLoByte(tmp16, (uint8_t) key[7]);
361 firstUInt32 = (uint32_t) PutLoWord(firstUInt32, (uint16_t) tmp16);
363 sum = firstUInt32 + secondUInt32;
365 /* if nmbBins is a power of 2, use shift, else use division */
366 if (hashListCp->binBitMask != CM_HASH_NOBITMASK)
367 *idx = (uint16_t) (sum & hashListCp->binBitMask);
369 *idx = (uint16_t) (sum % hashListCp->nmbBins);
372 } /* end of cmHashFuncBCD8 () */
376 * Fun: cmHashFuncString
378 * Desc: Computes the hash list index (bin number) for a specified
379 * key of type CM_HASH_KEYTYPE_STR.
381 * for (length of string)
382 * idx = (31 * idx) + *string;
384 * return (idx % hash_table_size);
386 * Ret: ROK - successful, *idx contains computed index
395 static S16 cmHashFuncString
397 CmHashListCp *hashListCp, /* hash list control point */
398 uint8_t *key, /* key string */
399 uint16_t keyLen, /* length of key string */
400 uint16_t *idx /* idx to return */
403 static S16 cmHashFuncString (hashListCp, key, keyLen, idx)
404 CmHashListCp *hashListCp; /* hash list control point */
405 uint8_t *key; /* key string */
406 uint16_t keyLen; /* length of key string */
407 uint16_t *idx; /* idx to return */
410 uint16_t cntr; /* Index */
411 uint32_t sum; /* Sum of octets for hash function */
416 for (cntr = 0; cntr < keyLen; cntr++)
418 sum = (CM_STR_HASHFUNC_CONSTANT * sum) + key[cntr];
421 /* if nmbBins is a power of 2, use shift, else use division */
422 if (hashListCp->binBitMask != CM_HASH_NOBITMASK)
423 *idx = (uint16_t) (sum & hashListCp->binBitMask);
425 *idx = (uint16_t) (sum % hashListCp->nmbBins);
429 } /* end of cmHashFuncString () */
435 * Fun: cmHashFuncDefault
437 * Desc: Computes the hash list index (bin number) for a specified
438 * key of type CM_HASH_KEYTYPE_DEF.
440 * Adds up all the octets of the key string
441 * and divides the sum by the range to get the desired index.
443 * Ret: ROK - successful, *idx contains computed index
452 static S16 cmHashFuncDefault
454 CmHashListCp *hashListCp, /* hash list control point */
455 uint8_t *key, /* key string */
456 uint16_t keyLen, /* length of key string */
457 uint16_t *idx /* index to return */
460 static S16 cmHashFuncDefault(hashListCp, key, keyLen, idx)
461 CmHashListCp *hashListCp; /* hash list control point */
462 uint8_t *key; /* key string */
463 uint16_t keyLen; /* length of key string */
464 uint16_t *idx; /* index to return */
467 uint32_t sum; /* sum of key string octets */
470 /* add all bytes of the key */
473 sum += (uint32_t) (*key++);
475 /* compute index by dividing the range into the sum */
477 /* if nmbBins is a power of 2, use shift, else use division */
478 if (hashListCp->binBitMask != CM_HASH_NOBITMASK)
479 *idx = (uint16_t) (sum & hashListCp->binBitMask);
481 *idx = (uint16_t) (sum % hashListCp->nmbBins);
485 } /* end of cmHashFuncDefault */
490 * Fun: cmHashFuncMult24
492 * Desc: Computes the hash list index (bin number) for a specified
493 * key of type CM_HASH_KEYTYPE_MULT24.
495 * Multiplies the given key (max k bits) with a constant
496 * multiplier and extracts p bits of the result, from the
497 * bit position k-1 to bit position k-p, to get the hash
498 * list index. p is such that 2^p is number of bins.
500 * The constant multiplier is the floor of A * 2^k, for
503 * This function uses a pre-computed constant multiplier
504 * CM_HASH_MULTMETHOD_CNST24, which is computed for
505 * A = (sqrt(5) - 1)/2, and k = 24 bits.
507 * This hashing method is explained in section 12.3.2 of
508 * "Introduction to Algorithms" by Thomas H. Cormen et al.,
511 * Ret: ROK - successful, *idx contains computed index
520 static S16 cmHashFuncMult24
522 CmHashListCp *hashListCp, /* hash list control point */
523 uint8_t *key, /* key string */
524 uint16_t keyLen, /* length of key string */
525 uint16_t *idx /* index to return */
528 static S16 cmHashFuncMult24(hashListCp, key, keyLen, idx)
529 CmHashListCp *hashListCp; /* hash list control point */
530 uint8_t *key; /* key string */
531 uint16_t keyLen; /* length of key string */
532 uint16_t *idx; /* index to return */
535 uint32_t prod; /* (constant multiplier * key) */
536 uint8_t shift; /* Bits to be shifted to get index */
541 #if (ERRCLASS & ERRCLS_DEBUG)
542 /* error check on parameters */
543 if (hashListCp->binBitMask == CM_HASH_NOBITMASK)
547 prod = CM_HASH_MULT24_CONST * *((uint32_t *)key);
549 shift = CM_HASH_MULT24_BITPOS - hashListCp->nmbBinBits;
550 *idx = ((uint16_t) (prod & (hashListCp->binBitMask << shift))) >> shift;
553 } /* end of cmHashFuncMult24 */
560 * Fun: cmHashFuncConId
562 * Desc: Computes the hash list index (bin number) for a specified
563 * key of type CM_HASH_KEYTYPE_CONID.
565 * This function can be used for keys that are an integer whose
566 * size is uint8_t, uint16_t or uint32_t. Instead of adding all octets of the key,
567 * this fn computes the "index" of the bin in which the entry
568 * needs to be inserted by taking a modulo of the integer with the
569 * total number of bins.
570 * This function is typically suitable for a sequentially increasing
571 * number like suConnId/spConnId
573 * Ret: ROK - successful, *idx contains computed index
582 static S16 cmHashFuncConId
584 CmHashListCp *hashListCp, /* hash list control point */
585 uint8_t *key, /* key string */
586 uint16_t keyLen, /* length of key string */
587 uint16_t *idx /* index to return */
590 static S16 cmHashFuncConId(hashListCp, key, keyLen, idx)
591 CmHashListCp *hashListCp; /* hash list control point */
592 uint8_t *key; /* key string */
593 uint16_t keyLen; /* length of key string */
594 uint16_t *idx; /* index to return */
599 /* switch based on the length of the key */
602 case CM_HASHKEYLEN_UINT32:
603 if (hashListCp->binBitMask != CM_HASH_NOBITMASK)
604 *idx = (uint16_t) (((uint32_t) *((uint32_t *)key)) & hashListCp->binBitMask);
606 *idx = (uint16_t) (((uint32_t) *((uint32_t *)key)) % hashListCp->nmbBins);
609 case CM_HASHKEYLEN_UINT16:
610 if (hashListCp->binBitMask != CM_HASH_NOBITMASK)
611 *idx = (uint16_t) (((uint16_t)*((uint16_t *)key)) & hashListCp->binBitMask);
613 *idx = (uint16_t) (((uint16_t)*((uint16_t *)key)) % hashListCp->nmbBins);
616 case CM_HASHKEYLEN_UINT8:
617 if (hashListCp->binBitMask != CM_HASH_NOBITMASK)
618 *idx = (uint16_t) (((uint8_t)*((uint8_t *)key)) & hashListCp->binBitMask);
620 *idx = (uint16_t) (((uint8_t)*((uint8_t *)key)) % hashListCp->nmbBins);
628 } /* end of cmHashFuncConId */
634 * Fun: cmHashFuncDirIdx
636 * Desc: Computes the hash list index (bin number) for a specified
637 * key of type CM_HASH_KEYTYPE_DIRINDEX.
639 * The key is the hash table index.
641 * Ret: ROK - successful, *idx contains computed index
650 static S16 cmHashFuncDirIdx
652 CmHashListCp *hashListCp, /* hash list control point */
653 uint8_t *key, /* key string */
654 uint16_t keyLen, /* length of key string */
655 uint16_t *idx /* index to return */
658 static S16 cmHashFuncDirIdx(hashListCp, key, keyLen, idx)
659 CmHashListCp *hashListCp; /* hash list control point */
660 uint8_t *key; /* key string */
661 uint16_t keyLen; /* length of key string */
662 uint16_t *idx; /* index to return */
669 *idx = *((uint16_t *) key);
672 } /* end of cmHashFuncDirIdx */
677 * Fun: cmHashMatchKey
679 * Desc: Compares two keys and determines if they match.
681 * Ret: ROK - match successful
682 * RFAILED - match failed (non-matching key values)
691 static S16 cmHashMatchKey
693 uint8_t *key1, /* first key string */
694 uint16_t keyLen1, /* length of first key string */
695 uint8_t *key2, /* second key string */
696 uint16_t keyLen2 /* length of second key string */
699 static S16 cmHashMatchKey(key1, keyLen1, key2, keyLen2)
700 uint8_t *key1; /* first key string */
701 uint16_t keyLen1; /* length of first key string */
702 uint8_t *key2; /* second key string */
703 uint16_t keyLen2; /* length of second key string */
707 /* compare key lengths */
708 if (keyLen1 != keyLen2)
711 /* compare key strings */
712 return (cmMemcmp(key1, key2, (PTR) keyLen1));
713 } /* end of cmHashMatchKey */
720 * Desc: Adds an entry into a doubly linked list
722 * Ret: ROK - insertion successful
731 static S16 cmListInsert
733 CmListEnt *oldEntry, /* add new entry after this entry */
734 CmListEnt *newEntry /* new entry to add */
737 static S16 cmListInsert(oldEntry, newEntry)
738 CmListEnt *oldEntry; /* add new entry after this entry */
739 CmListEnt *newEntry; /* new entry to add */
743 newEntry->next = oldEntry->next;
744 newEntry->prev = oldEntry;
745 oldEntry->next = newEntry;
746 (newEntry->next)->prev = newEntry;
749 } /* end of cmListInsert */
756 * Desc: Deletes an entry from a doubly linked list
758 * Ret: ROK - deletion successful
767 static S16 cmListDelete
769 CmListEnt *entry /* entry to delete */
772 static S16 cmListDelete(entry)
773 CmListEnt *entry; /* entry to delete */
780 if (entry->prev != NULLP)
781 (entry->prev)->next = entry->next;
783 if (entry->next != NULLP)
784 (entry->next)->prev = entry->prev;
787 } /* end of cmListDelete */
798 * Fun: cmHashListInit
800 * Desc: Initializes a hash list. Parameters are:
802 * hashListCp control point for hash list
803 * nmbBins number of bins in the hash list. Storage will
804 * be allocated for them from the indicated memory
806 * offset if the entries in this hash list are also going
807 * to be attached to another hash list, they will
808 * contain multiple hash list entry headers. The
809 * offset indicates the offset of the entry header
810 * for this hash list in the entry structure.
811 * dupFlg whether entries with duplicate keys are allowed
812 * to be inserted in the hash list.
813 * keyType indicates type of key which can be used to select
814 * different hash functions. Ignored in this
817 * pool for allocating storage for bins.
819 * Ret: ROK - initialization successful
820 * RFAILED - initialization failed, lack of memory
830 CmHashListCp *hashListCp, /* hash list to initialize */
831 uint16_t nmbBins, /* number of hash list bins */
832 uint16_t offset, /* offset of CmHashListEnt in entries */
833 Bool dupFlg, /* allow duplicate keys */
834 uint16_t keyType, /* key type for selecting hash fn */
835 Region region, /* memory region to allocate bins */
836 Pool pool /* memory pool to allocate bins */
839 S16 cmHashListInit(hashListCp, nmbBins, offset, dupFlg, keyType, region, pool)
840 CmHashListCp *hashListCp; /* hash list to initialize */
841 uint16_t nmbBins; /* number of hash list bins */
842 uint16_t offset; /* offset of CmHashListEnt in entries */
843 Bool dupFlg; /* allow duplicate keys */
844 uint16_t keyType; /* key type for selecting hash fn */
845 Region region; /* memory region to allocate bins */
846 Pool pool; /* memory pool to allocate bins */
850 #ifndef CM_MT_HASH_BIN
857 #if (ERRCLASS & ERRCLS_DEBUG)
858 /* error check on parameters */
859 if (hashListCp == NULLP)
863 /* initialize control point fields */
864 hashListCp->hl = NULLP;
865 hashListCp->region = region;
866 hashListCp->pool = pool;
867 hashListCp->nmbBins = 0;
868 hashListCp->binBitMask = CM_HASH_NOBITMASK;
869 hashListCp->nmbBinBits = 0;
870 #ifndef CM_MT_HASH_BIN
871 hashListCp->nmbEnt = 0;
873 hashListCp->offset = offset;
874 hashListCp->dupFlg = dupFlg;
875 hashListCp->keyType = keyType;
876 hashListCp->hashFunc = NULLP;
878 /* initialize hash function for this key type */
881 case CM_HASH_KEYTYPE_MULT24:
882 /* return failure if number of bins is not a power of 2 */
883 if (((nmbBins) & (nmbBins - 1)) != 0)
886 hashListCp->hashFunc = cmHashFuncMult24;
889 case CM_HASH_KEYTYPE_DIRIDX:
890 hashListCp->hashFunc = cmHashFuncDirIdx;
893 case CM_HASH_KEYTYPE_STR:
894 hashListCp->hashFunc = cmHashFuncString;
897 case CM_HASH_KEYTYPE_UINT32_MOD:
898 hashListCp->hashFunc = cmHashFuncU32Mod;
901 case CM_HASH_KEYTYPE_BCD8:
902 hashListCp->hashFunc = cmHashFuncBCD8;
905 case CM_HASH_KEYTYPE_ANY:
906 hashListCp->hashFunc = cmHashFuncAnyKey;
909 case CM_HASH_KEYTYPE_CONID:
910 hashListCp->hashFunc = cmHashFuncConId;
913 case CM_HASH_KEYTYPE_DEF: /* default hash function */
914 default: /* illegal key type */
915 hashListCp->hashFunc = cmHashFuncDefault;
919 /* allocate memory for bins */
922 #ifndef CM_MT_HASH_BIN
923 if (SGetSBuf(region, pool, (Data **) &hashListCp->hl,
924 (Size) (nmbBins * sizeof(CmListEnt))) != ROK)
927 if (SGetSBuf(region, pool, (Data **) &hashListCp->hl,
928 (Size) (nmbBins * sizeof(CmListBinEnt))) != ROK)
932 /* initialize bin pointers */
934 for(i = 0; i < nmbBins; i++)
936 #ifndef CM_MT_HASH_BIN
937 hl[i].next = hl[i].prev = &hl[i];
939 /* This initialization is being done as a part of checking
940 * the presence of empty/non-empty bins.
942 hl[i].next = hl[i].prev = (CmListEnt*)&hl[i];
947 /* initialize bin size */
948 hashListCp->nmbBins = nmbBins;
950 /* initialize bin bit mask */
951 if (((nmbBins) & (nmbBins - 1)) == 0)
955 /* number of bins is a power of 2 */
956 hashListCp->binBitMask = nmbBins - 1;
958 /* compute number of bits in the bit mask */
959 for (binBitMask = hashListCp->binBitMask; binBitMask; binBitMask >>= 1)
960 hashListCp->nmbBinBits++;
966 } /* end of cmHashListInit */
971 * Fun: cmHashListDeinit
973 * Desc: Deinitializes a hash list. Deallocates memory for bins
974 * and resets header fields. Parameters are:
976 * hashListCp control point for hash list
978 * Ret: ROK - successful
988 CmHashListCp *hashListCp /* hash list to deinitialize */
991 S16 cmHashListDeinit(hashListCp)
992 CmHashListCp *hashListCp; /* hash list to deinitialize */
996 #if (ERRCLASS & ERRCLS_DEBUG)
997 /* error check on parameters */
998 if (hashListCp == NULLP)
1002 /* deallocate memory for bins */
1003 if (hashListCp->nmbBins)
1004 #ifndef CM_MT_HASH_BIN
1005 (Void) SPutSBuf(hashListCp->region, hashListCp->pool,
1006 (Data *) hashListCp->hl,
1007 (Size) (hashListCp->nmbBins * sizeof(CmListEnt)));
1009 (Void) SPutSBuf(hashListCp->region, hashListCp->pool,
1010 (Data *) hashListCp->hl,
1011 (Size) (hashListCp->nmbBins * sizeof(CmListBinEnt)));
1014 /* deinitialize control point fields */
1015 hashListCp->hl = NULLP;
1016 hashListCp->region = REGIONNC;
1017 hashListCp->pool = 0;
1018 hashListCp->nmbBins = 0;
1019 hashListCp->binBitMask = CM_HASH_NOBITMASK;
1020 #ifndef CM_MT_HASH_BIN
1021 hashListCp->nmbEnt = 0;
1023 hashListCp->offset = 0;
1024 hashListCp->dupFlg = FALSE;
1025 hashListCp->keyType = CM_HASH_KEYTYPE_DEF;
1026 hashListCp->hashFunc = NULLP;
1029 } /* end of cmHashListDeinit */
1034 * Fun: cmHashListInsert
1036 * Desc: Inserts a new entry in the hash list. Parameters are:
1038 * hashListCp control point for hash list
1039 * entry pointer to new entry to add in the hash list
1040 * key pointer to key string in the new entry
1041 * keyLen length of key string
1043 * Ret: ROK - insertion successful
1044 * ROKDUP - insertion failed (duplicate key not allowed)
1045 * RFAILED - insertion failed (incorrect parameter values)
1054 S16 cmHashListInsert
1056 CmHashListCp *hashListCp, /* hash list to add to */
1057 PTR entry, /* entry to add */
1058 uint8_t *key, /* pointer to key */
1059 uint16_t keyLen /* length of key */
1062 S16 cmHashListInsert(hashListCp, entry, key, keyLen)
1063 CmHashListCp *hashListCp; /* hash list to add to */
1064 PTR entry; /* entry to add */
1065 uint8_t *key; /* pointer to key */
1066 uint16_t keyLen; /* length of key */
1069 CmHashListEnt *hashListEnt; /* pointer to hash list entry header */
1070 PTR dupEntry; /* pointer to entry with duplicate key */
1071 uint16_t idx; /* index for insertion into hash list */
1074 #if (ERRCLASS & ERRCLS_DEBUG)
1075 /* error check on parameters */
1076 if ((hashListCp == NULLP) || (entry == NULLP) ||
1077 (key == NULLP) || (keyLen == 0))
1081 /* check for duplicates */
1082 if (hashListCp->dupFlg == FALSE)
1084 /* no duplicates allowed, check if key already exists */
1085 if (cmHashListFind(hashListCp, key, keyLen, 0, &dupEntry) == ROK)
1089 /* get pointer to hash list entry header */
1090 hashListEnt = (CmHashListEnt *) (((uint8_t *) entry) + hashListCp->offset);
1092 /* initialize hash list entry header */
1093 hashListEnt->list.next = NULLP;
1094 hashListEnt->list.prev = NULLP;
1095 hashListEnt->keyLen = keyLen;
1096 hashListEnt->key = key;
1098 /* compute index for insertion */
1099 if ((*hashListCp->hashFunc)(hashListCp, key, keyLen, &idx) != ROK)
1102 hashListEnt->hashVal = idx;
1104 /* insert into list */
1105 cmListInsert(hashListCp->hl[idx].prev, &hashListEnt->list);
1107 /* increment count of entries in hash list */
1108 #ifndef CM_MT_HASH_BIN
1109 hashListCp->nmbEnt++;
1111 hashListCp->hl[idx].nmbEnt++;
1112 #endif /* #ifndef CM_MT_HASH_BIN */
1115 } /* end of cmHashListInsert */
1120 * Fun: cmHashListDelete
1122 * Desc: Deletes an entry from the hash list. Parameters are:
1124 * hashListCp control point for hash list
1125 * entry pointer to entry to delete from the hash list
1127 * Ret: ROK - deletion successful
1128 * RFAILED - deletion failed (incorrect parameter values)
1137 S16 cmHashListDelete
1139 CmHashListCp *hashListCp, /* hash list to delete from */
1140 PTR entry /* entry to delete */
1143 S16 cmHashListDelete(hashListCp, entry)
1144 CmHashListCp *hashListCp; /* hash list to delete from */
1145 PTR entry; /* entry to delete */
1148 CmHashListEnt *hashListEnt; /* pointer to hash list entry header */
1149 #ifdef CM_MT_HASH_BIN
1150 uint16_t idx; /* index for selecting the right hash list bin */
1154 #if (ERRCLASS & ERRCLS_DEBUG)
1155 /* error check on parameters */
1156 if ((hashListCp == NULLP) || (entry == NULLP))
1160 /* get pointer to hash list entry header */
1161 hashListEnt = (CmHashListEnt *) (((uint8_t *) entry) + hashListCp->offset);
1163 /* check if entry is already deleted if yes then return OK */
1164 if((hashListEnt->list.next == NULLP) ||
1165 (hashListEnt->list.prev == NULLP))
1168 #ifdef CM_MT_HASH_BIN
1169 /* compute index for insertion */
1170 if ((*hashListCp->hashFunc)(hashListCp, hashListEnt->key,
1171 hashListEnt->keyLen, &idx) != ROK)
1173 #endif /* #ifdef CM_MT_HASH_BIN */
1175 /* delete entry from list */
1176 cmListDelete(&hashListEnt->list);
1178 /* reinitialize hash list entry header */
1179 hashListEnt->list.next = NULLP;
1180 hashListEnt->list.prev = NULLP;
1181 hashListEnt->keyLen = 0;
1182 hashListEnt->key = NULLP;
1183 hashListEnt->hashVal = 0;
1185 /* decrement count of entries in hash list */
1186 #ifndef CM_MT_HASH_BIN
1187 hashListCp->nmbEnt--;
1189 /* Find the right bin index and decrement the nmbEnt counter */
1190 hashListCp->hl[idx].nmbEnt--;
1191 #endif /* #ifndef CM_MT_HASH_BIN */
1194 } /* end of cmHashListDelete */
1199 * Fun: cmHashListFind
1201 * Desc: Finds an entry in the hash list. Parameters are:
1203 * hashListCp control point for hash list
1204 * key pointer to key string for search
1205 * keyLen length of key string
1206 * seqNmb sequence number in case duplicates allowed
1207 * entry pointer to found entry
1209 * Ret: ROK - find successful, *entry points to found entry
1210 * RFAILED - find failed, *entry is unchanged
1211 * (incorrect parameter values, key not found)
1222 CmHashListCp *hashListCp, /* hash list to search */
1223 uint8_t *key, /* pointer to key */
1224 uint16_t keyLen, /* length of key */
1225 uint16_t seqNmb, /* used in case of duplicate keys */
1226 PTR *entry /* entry to be returned */
1229 S16 cmHashListFind(hashListCp, key, keyLen, seqNmb, entry)
1230 CmHashListCp *hashListCp; /* hash list to search */
1231 uint8_t *key; /* pointer to key */
1232 uint16_t keyLen; /* length of key */
1233 uint16_t seqNmb; /* used in case of duplicate keys */
1234 PTR *entry; /* entry to be returned */
1237 CmHashListEnt *hashListEnt; /* pointer to hash list entry header */
1238 #ifndef CM_MT_HASH_BIN
1239 CmListEnt *hashListBin; /* pointer to hash list bin */
1241 CmListBinEnt *hashListBin; /* pointer to hash list bin */
1242 uint16_t entCnt=0; /* counter for number of entries */
1244 uint16_t i; /* counter for sequence number */
1245 uint16_t idx; /* index for insertion into hash list */
1248 #if (ERRCLASS & ERRCLS_DEBUG)
1249 /* error check on parameters */
1250 if ((hashListCp == NULLP) || (key == NULLP) ||
1251 (keyLen == 0) || (entry == NULLP))
1255 /* compute hash table index */
1256 if ((*hashListCp->hashFunc)(hashListCp, key, keyLen, &idx) != ROK)
1259 /* search this bin for exact key match */
1260 hashListBin = &hashListCp->hl[idx];
1261 hashListEnt = (CmHashListEnt *) hashListBin->next;
1263 /* examine each entry in bin */
1265 #ifndef CM_MT_HASH_BIN
1266 while (hashListBin != (CmListEnt *) hashListEnt)
1268 for (entCnt=0; entCnt < hashListBin->nmbEnt; entCnt++)
1271 /* check if key matches */
1272 if (cmHashMatchKey(hashListEnt->key, hashListEnt->keyLen, key, keyLen)
1276 *entry = (PTR) (((uint8_t *) hashListEnt) - hashListCp->offset);
1278 /* check for duplicates */
1279 if (!hashListCp->dupFlg)
1282 /* for duplicate key, check sequence number */
1287 /* go to next entry */
1288 hashListEnt = (CmHashListEnt *) hashListEnt->list.next;
1291 /* no matching key found */
1293 } /* end of cmHashListFind */
1298 * Fun: cmHashListGetNext
1300 * Desc: Gets next entry in hash list with respect to the specified
1301 * previous entry. If previous entry is NULLP, gets first
1302 * entry in hash list. Parameters are:
1304 * hashListCp control point for hash list
1305 * prevEnt pointer to previous entry
1306 * entry pointer to next entry to be returned
1308 * Ret: ROK - get successful, *entry points to found entry
1309 * (at beginning of list or in the list)
1310 * RFAILED - get failed, *entry is unchanged
1311 * (incorrect parameter values)
1312 * ROKDNA - get failed, *entry is unchanged.
1315 * Notes: This function has to be used cautiously while the
1316 * CM Hash Module is being compiled with CM_MT_HASH_BIN.
1317 * In such cases, this function should be used only after
1318 * ensuring that none of the other threads are operating
1319 * on the common hash list.
1325 S16 cmHashListGetNext
1327 CmHashListCp *hashListCp, /* hash list to get from */
1328 PTR prevEnt, /* previous entry */
1329 PTR *entry /* entry to be returned */
1332 S16 cmHashListGetNext(hashListCp, prevEnt, entry)
1333 CmHashListCp *hashListCp; /* hash list to get from */
1334 PTR prevEnt; /* previous entry */
1335 PTR *entry; /* entry to be returned */
1338 #ifndef CM_MT_HASH_BIN
1339 CmListEnt *hashListBin; /* temporary hash list bin pointer */
1341 CmListBinEnt *hashListBin; /* temporary hash list bin pointer */
1343 CmHashListEnt *hashListEnt; /* temporary hash list entry pointer */
1344 CmHashListEnt *prevListEnt; /* previous hash list entry pointer */
1345 uint16_t i; /* hash list counter */
1348 #if (ERRCLASS & ERRCLS_DEBUG)
1349 /* error check on parameters */
1350 if ((hashListCp == NULLP) || (entry == NULLP))
1354 /* check if need to get first entry */
1355 if (prevEnt == NULLP)
1357 /* get first entry in hash list */
1358 for (i = 0; i < hashListCp->nmbBins; i++)
1359 /* check for non-empty bin */
1360 #ifndef CM_MT_HASH_BIN
1361 if (hashListCp->hl[i].next != &hashListCp->hl[i])
1363 if (hashListCp->hl[i].next != (CmListEnt*)&hashListCp->hl[i])
1366 /* get first entry in bin */
1367 hashListEnt = (CmHashListEnt *) hashListCp->hl[i].next;
1369 /* requested entry is in nxtEnt */
1370 *entry = (PTR) (((uint8_t *) hashListEnt) - hashListCp->offset);
1375 /* no more entries */
1379 /* use previous entry to find next entry */
1381 /* get pointer to previous hash list entry header */
1382 prevListEnt = (CmHashListEnt *) (((uint8_t *) prevEnt) + hashListCp->offset);
1384 /* get index of previous entry */
1385 i = prevListEnt->hashVal;
1387 /* set pointers to get next entry */
1388 hashListBin = &hashListCp->hl[i];
1389 prevListEnt = (CmHashListEnt *) prevListEnt->list.next;
1392 /* check if more entries in this bin */
1393 if (prevListEnt != (CmHashListEnt *) hashListBin)
1395 /* found next entry */
1396 *entry = (PTR) (((uint8_t *) prevListEnt) - hashListCp->offset);
1401 /* no more entries in this bin, go to next bin, check if more bins */
1402 if (++i >= hashListCp->nmbBins)
1403 /* no more entries */
1406 /* reset pointers for next bin */
1407 hashListBin = &hashListCp->hl[i];
1408 prevListEnt = (CmHashListEnt *) hashListBin->next;
1411 /* no more entries */
1413 } /* end of cmHashListGetNext */
1415 #ifdef CM_MT_HASH_BIN
1419 * Fun: cmHashListBinGetNextEntry
1421 * Desc: Gets next entry in a given hash bin respect to the specified
1422 * previous entry. If previous entry is NULLP, gets first
1423 * entry in hash bin. Parameters are:
1425 * hashListCp control point for hash list
1426 * binIdx Bin Index to find the entry in
1427 * prevEnt pointer to previous entry
1428 * entry pointer to next entry to be returned
1430 * Ret: ROK - get successful, *entry points to found entry
1431 * (at beginning of list or in the list)
1432 * RFAILED - get failed, *entry is unchanged
1433 * (incorrect parameter values)
1434 * ROKDNA - get failed, *entry is unchanged.
1442 S16 cmHashListBinGetNextEntry
1444 CmHashListCp *hashListCp, /* hash list to get from */
1445 uint16_t binIdx, /* Bin Index to retreive the entry */
1446 PTR prevEnt, /* previous entry */
1447 PTR *entry /* entry to be returned */
1450 S16 cmHashListBinGetNextEntry(hashListCp, binIdx, prevEnt, entry)
1451 CmHashListCp *hashListCp; /* hash list to get from */
1452 uint16_t binIdx; /* Bin Index to retreive the entry */
1453 PTR prevEnt; /* previous entry */
1454 PTR *entry; /* entry to be returned */
1457 CmListBinEnt *hashListBin; /* temporary hash list bin pointer */
1458 CmHashListEnt *hashListEnt; /* temporary hash list entry pointer */
1459 CmHashListEnt *prevListEnt; /* previous hash list entry pointer */
1462 #if (ERRCLASS & ERRCLS_DEBUG)
1463 /* error check on parameters */
1464 if ((hashListCp == NULLP) || (entry == NULLP))
1468 /* check if need to get first entry */
1469 if (prevEnt == NULLP)
1471 /* get first entry in hash list */
1472 /* check for non-empty bin */
1473 if (hashListCp->hl[binIdx].next != (CmListEnt*)&hashListCp->hl[binIdx])
1475 /* get first entry in bin */
1476 hashListEnt = (CmHashListEnt *) hashListCp->hl[binIdx].next;
1478 /* requested entry is in nxtEnt */
1479 *entry = (PTR) (((uint8_t *) hashListEnt) - hashListCp->offset);
1484 /* no more entries */
1488 /* use previous entry to find next entry */
1490 /* get pointer to previous hash list entry header */
1491 prevListEnt = (CmHashListEnt *) (((uint8_t *) prevEnt) + hashListCp->offset);
1493 /* set pointers to get next entry */
1494 hashListBin = &hashListCp->hl[binIdx];
1495 prevListEnt = (CmHashListEnt *) prevListEnt->list.next;
1497 /* check if more entries in this bin */
1498 if (prevListEnt != (CmHashListEnt *) hashListBin)
1500 /* found next entry */
1501 *entry = (PTR) (((uint8_t *) prevListEnt) - hashListCp->offset);
1506 /* no more entries */
1508 } /* end of cmHashListBinGetNextEntry */
1514 * Fun: cmHashListQuery
1516 * Desc: Gets hash list attributes. Parameters are:
1518 * hashListCp control point for hash list
1519 * queryType type of attribute being queried
1520 * result result of query, to be returned
1522 * Ret: ROK - successful, *result contains query result
1523 * RFAILED - failed, *result unchanged (incorrect parameter values)
1525 * Notes: This function is obsoleted!
1526 * Use macros defined in cm_hash.h instead
1534 CmHashListCp *hashListCp, /* hash list to query */
1535 uint8_t queryType, /* type of query */
1536 uint16_t *result /* result of query */
1539 S16 cmHashListQuery(hashListCp, queryType, result)
1540 CmHashListCp *hashListCp; /* hash list to query */
1541 uint8_t queryType; /* type of query */
1542 uint16_t *result; /* result of query */
1545 #ifdef CM_MT_HASH_BIN
1550 /* deal with queries that do not need hashListCp */
1552 #if (ERRCLASS & ERRCLS_DEBUG)
1553 /* error check on parameters */
1554 if (result == NULLP)
1558 /* respond depending on query type */
1559 if (queryType == CM_HASH_QUERYTYPE_BINSIZE)
1561 /* storage for each bin */
1562 #ifndef CM_MT_HASH_BIN
1563 *result = (uint16_t) sizeof(CmListEnt);
1565 *result = (uint16_t) sizeof(CmListBinEnt);
1570 /* deal with queries that do need hashListCp */
1572 #if (ERRCLASS & ERRCLS_DEBUG)
1573 /* error check on parameters */
1574 if (hashListCp == NULLP)
1578 /* respond depending on query type */
1581 case CM_HASH_QUERYTYPE_ENTRIES: /* current number of entries */
1582 #ifndef CM_MT_HASH_BIN
1583 *result = (uint16_t) hashListCp->nmbEnt;
1586 for (i=0; i < hashListCp->nmbBins; i++)
1588 *result += hashListCp->hl[i].nmbEnt;
1593 case CM_HASH_QUERYTYPE_BINS: /* number of bins */
1594 *result = (uint16_t) hashListCp->nmbBins;
1597 case CM_HASH_QUERYTYPE_OFFSET: /* offset of CmHashListEnt in entries */
1598 *result = (uint16_t) hashListCp->offset;
1601 case CM_HASH_QUERYTYPE_DUPFLG: /* allow duplicate keys */
1602 *result = (uint16_t) hashListCp->dupFlg;
1605 case CM_HASH_QUERYTYPE_KEYTYPE: /* key type for selecting hash functions */
1606 *result = (uint16_t) hashListCp->keyType;
1609 default: /* process other query types */
1613 /* illegal query type */
1615 } /* end of cmHashListQuery */
1617 #ifdef HASH_OPEN_ADDRESSING
1621 * Fun: cmHashListOAInsert
1623 * Desc: Inserts a new entry in the hash list with open addressing.
1626 * hashListCp control point for hash list
1627 * entry pointer to new entry to add in the hash list
1628 * key pointer to key string in the new entry
1629 * keyLen length of key string
1631 * Ret: ROK - insertion successful
1632 * ROKDUP - insertion failed (duplicate key not allowed)
1633 * RFAILED - insertion failed (incorrect parameter values)
1642 S16 cmHashListOAInsert
1644 CmHashListCp *hashListCp, /* hash table to add to */
1645 PTR entry, /* entry to add */
1646 uint8_t *key, /* pointer to key */
1647 uint16_t keyLen /* length of key */
1650 S16 cmHashListOAInsert(hashListCp, entry, key, keyLen)
1651 CmHashListCp *hashListCp; /* hash table to add to */
1652 PTR entry; /* entry to add */
1653 uint8_t *key; /* pointer to key */
1654 uint16_t keyLen; /* length of key */
1657 /* cm_hash_c_001.main_21. Modify. Compilation Issue resolved. */
1658 #ifndef CM_MT_HASH_BIN
1659 CmListEnt *hashBin; /* temporary hash list bin pointer */
1661 CmListBinEnt *hashBin; /* temporary hash list bin pointer */
1663 CmHashListEnt *hashListEnt; /* pointer to hash list entry header */
1664 uint16_t idx; /* index for insertion into hash list */
1665 uint16_t hashSize; /* hash size */
1667 /* cm_hash_c_001.main_21. Modify. Compilation Issue resolved. */
1671 #if (ERRCLASS & ERRCLS_DEBUG)
1672 /* error check on parameters */
1673 if ((hashListCp == NULLP) || (entry == NULLP) ||
1674 (key == NULLP) || (keyLen == 0))
1678 #ifndef CM_MT_HASH_BIN
1679 nmbEnt = hashListCp->nmbEnt;
1682 for (i=0; i < hashListCp->nmbBins; i++)
1684 nmbEnt += hashListCp->hl[i].nmbEnt;
1687 /* check if table is full */
1688 if (hashListCp->nmbBins == nmbEnt)
1691 /* get pointer to hash list entry header */
1692 hashListEnt = (CmHashListEnt *) (((uint8_t *) entry) + hashListCp->offset);
1694 /* initialize hash list entry header */
1695 hashListEnt->list.next = NULLP;
1696 hashListEnt->list.prev = NULLP;
1697 hashListEnt->keyLen = keyLen;
1698 hashListEnt->key = key;
1700 /* compute index for insertion */
1701 if ((*hashListCp->hashFunc)(hashListCp, key, keyLen, &idx) != ROK)
1707 hashSize = hashListCp->nmbBins;
1708 hashBin = &hashListCp->hl[idx];
1709 for (i = hashSize; i > 0; i--)
1711 if (hashBin->next == hashBin)
1713 if (++idx >= hashSize)
1716 hashBin = &hashListCp->hl[0];
1722 /* insert into list */
1723 if (cmListInsert(hashBin->prev, &hashListEnt->list) != ROK)
1726 hashListEnt->hashVal = idx;
1728 #ifndef CM_MT_HASH_BIN
1729 /* increment count of entries in hash list */
1730 hashListCp->nmbEnt++;
1736 } /* end of cmHashListOAInsert */
1739 #endif /* HASH_OPENADDRESSING */
1741 /**********************************************************************
1743 **********************************************************************/