[Epic-ID: ODUHIGH-462][Task-ID: ODUHIGH-472] Implementation of onduration timer
[o-du/l2.git] / src / cm / cm_hash.c
1 /*******************************************************************************
2 ################################################################################
3 #   Copyright (c) [2017-2019] [Radisys]                                        #
4 #                                                                              #
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                                    #
8 #                                                                              #
9 #       http://www.apache.org/licenses/LICENSE-2.0                             #
10 #                                                                              #
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 *******************************************************************************/
18 \f
19 /********************************************************************20**
20   
21      Name:     common hash functions
22   
23      Type:     C source file
24   
25      Desc:     Hashing functions used by various layers.
26                (Newer version of functions in cm_bdy1)
27   
28                Using hash lists in a product:
29                ------------------------------
30
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
38                of addresses:
39
40                typedef struct xySAPCb       (SAP control block)
41                {
42                   ...
43                   CmHashListCp addrHlCp;    (hash list for addresses)
44                   ...
45                } XySAPCb;
46
47                typedef struct xyAddrEnt     (hash list entry for an address)
48                {
49                   ...
50                   CmHashListEnt hl;         (hash list entry header)
51                   ...
52                   XyAddr addr;              (hash list key)
53                   ...
54                } XyAddrEnt;
55
56                Functions available:
57                --------------------
58
59                The functions available for using hash lists are defined
60                below. The accompanying comments explain the usage in detail.
61
62                Implementation details:
63                -----------------------
64
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
77                entry header fields.
78
79      File:     cm_hash.c
80   
81 *********************************************************************21*/
82   
83 \f  
84 #include <common_def.h>
85
86 \f
87 /* local defines */
88
89 /* local externs */
90
91 /* forward references */
92 /* cm_hash_c_001.main_22: Fixing warnings on GCC compiler */
93 #ifdef __cplusplus
94  extern "C" {
95 #endif
96
97 static S16 cmHashFuncBCD8   ARGS((CmHashListCp *hashListCp, uint8_t *key, 
98                                          uint16_t keyLen, uint16_t *idx));
99
100 static S16 cmHashFuncConId  ARGS((CmHashListCp *hashListCp, uint8_t *key, 
101                                          uint16_t keyLen, uint16_t *idx));
102
103 static S16 cmHashFuncU32Mod  ARGS((CmHashListCp *hashListCp, uint8_t *key, 
104                                          uint16_t keyLen, uint16_t *idx));
105
106 static S16 cmHashFuncString  ARGS((CmHashListCp *hashListCp, uint8_t *key, 
107                                          uint16_t keyLen, uint16_t *idx));
108
109 static S16 cmHashFuncDefault ARGS((CmHashListCp *hashListCp, uint8_t *key, 
110                                          uint16_t keyLen, uint16_t *idx));
111
112 static S16 cmHashFuncAnyKey  ARGS((CmHashListCp *hashListCp, uint8_t *key, 
113                                          uint16_t keyLen, uint16_t *idx));
114
115 static S16 cmHashMatchKey ARGS((uint8_t *key1, uint16_t keyLen1, uint8_t *key2, uint16_t keyLen2));
116
117 static S16 cmListInsert   ARGS((CmListEnt *oldEntry, CmListEnt *newEntry));
118
119 static S16 cmListDelete   ARGS((CmListEnt *entry));
120
121 /* cm_hash_c_001.main_22: Fixing warnings on GCC compiler */
122 static S16 cmHashFuncMult24 ARGS((CmHashListCp *hashListCp, uint8_t *key, uint16_t keyLen, uint16_t *idx));
123
124 static S16 cmHashFuncDirIdx ARGS((CmHashListCp *hashListCp, uint8_t *key, uint16_t keyLen, uint16_t *idx));
125
126 #ifdef __cplusplus
127  }
128 #endif
129
130 /* functions in other modules */
131   
132 /* public variable declarations */
133
134 /* private variable declarations */
135
136 \f
137 /*
138  *     private support functions
139  */
140
141 /*
142 *
143 *       Fun:   cmHashFuncAnyKey
144 *
145 *       Desc:  Computes the hash list index (bin number) for a specified
146 *              key of type CM_HASH_KEYTYPE_ANY. 
147 *
148 *              return index to hash table 
149 *
150 *       Ret:   ROK     - successful, *idx contains computed index 
151 *
152 *       Notes: None.
153 *
154 *       File:  cm_hash.c
155 *
156 */
157
158 static S16 cmHashFuncAnyKey
159 (
160 CmHashListCp  *hashListCp,        /* hash list control point */
161 uint8_t       *key,               /* key string */
162 uint16_t      keyLen,             /* length of key string */
163 uint16_t      *idx                /* idx to return */
164
165 {
166    uint32_t   a;                 /* hash variables */
167    uint32_t   b;                 /* hash variables */         
168    uint32_t   c;                 /* hash variables */
169    uint32_t   len;               /* length */
170
171    /*cm_hash_c_001.main_23 : Fix for TRACE5 feature crash due to missing TRC MACRO*/
172    /* Set up the internal state */
173    len = keyLen;    /* key length */
174    a = 0x9e3779b9;  /* a = b = the golden ratio; an arbitrary value */
175    b = 0x9e3779b9;
176    c = 0x12345678;  /* some value */
177
178    /*---------------------------------------- handle most of the key */
179    while (len >= 12)
180    {
181       a += (key[0] +((uint32_t)key[1]<<8) +((uint32_t)key[2]<<16) +((uint32_t)key[3]<<24));
182       b += (key[4] +((uint32_t)key[5]<<8) +((uint32_t)key[6]<<16) +((uint32_t)key[7]<<24));
183       c += (key[8] +((uint32_t)key[9]<<8) +((uint32_t)key[10]<<16)+((uint32_t)key[11]<<24));
184       CM_HASH_MIX(a, b, c);
185       key += 12; len -= 12;
186    }
187
188    /*------------------------------------- handle the last 11 bytes */
189    c += keyLen;
190    switch(len)              /* all the case statements fall through */
191    {
192    case 11: c+=((uint32_t)key[10]<<24);
193    case 10: c+=((uint32_t)key[9]<<16);
194    case 9 : c+=((uint32_t)key[8]<<8);
195       /* the first byte of c is reserved for the keyLen */
196    case 8 : b+=((uint32_t)key[7]<<24);
197    case 7 : b+=((uint32_t)key[6]<<16);
198    case 6 : b+=((uint32_t)key[5]<<8);
199    case 5 : b+=key[4];
200    case 4 : a+=((uint32_t)key[3]<<24);
201    case 3 : a+=((uint32_t)key[2]<<16);
202    case 2 : a+=((uint32_t)key[1]<<8);
203    case 1 : a+=key[0];
204      /* case 0: nothing left to add */
205    }
206    CM_HASH_MIX(a,b,c);
207    /*-------------------------------------------- report the result */
208
209    /* if nmbBins is a power of 2, use shift, else use division */
210    if (hashListCp->binBitMask != CM_HASH_NOBITMASK)
211       *idx = (uint16_t) (c & hashListCp->binBitMask);
212    else
213       *idx = (uint16_t) (c % hashListCp->nmbBins);
214
215    return ROK;
216 } /* end of cmHashFuncAnyKey */
217
218
219 /*
220 *
221 *       Fun:   cmHashFuncU32Mod
222 *
223 *       Desc:  Computes the hash list index (bin number) for a specified
224 *              key of type CM_HASH_KEYTYPE_MOD. 
225 *
226 *              return (idx % hash_table_size);
227 *
228 *       Ret:   ROK     - successful, *idx contains computed index 
229 *
230 *       Notes: None.
231 *
232 *       File:  cm_hash.c
233 *
234 */
235
236 static S16 cmHashFuncU32Mod
237 (
238 CmHashListCp *hashListCp,        /* hash list control point */
239 uint8_t      *key,               /* key string */
240 uint16_t     keyLen,             /* length of key string */
241 uint16_t     *idx                /* idx to return */
242
243 {
244    uint32_t  sum;                /* Sum of octets for hash function */
245
246
247    /* keyLen is marked Unused to remove compilation 
248     * warnings. */
249    UNUSED(keyLen);
250
251    sum = *((uint32_t *)key);
252
253    /* if nmbBins is a power of 2, use shift, else use division */
254    if (hashListCp->binBitMask != CM_HASH_NOBITMASK)
255       *idx = (uint16_t) (sum & hashListCp->binBitMask);
256    else
257       *idx = (uint16_t) (sum % hashListCp->nmbBins);
258
259    return ROK;
260
261 } /* end of cmHashFuncU32Mod () */
262
263 /*
264 *
265 *       Fun:   cmHashFuncBCD8
266 *
267 *       Desc:  Computes the hash list index (bin number) for a specified
268 *              key of type CM_HASH_KEYTYPE_BCD8. 
269 *
270 *       Steps:
271 *              1. Converts the 8 BCD coded octets into 2 uint32_ts 
272 *              2. Adds 2 uint32_ts to get one uint32_t. 
273 *              3. Apply uint32_tMod technique to get the index 
274 *              4. Return the index
275 *
276 *       Note: 
277 *              Here we are no bothered if the keyLen is more than 8. 
278 *              We are interested only in the first 8 octets.
279 *              
280 *       Ret:   ROK     - successful, *idx contains computed index 
281 *
282 *       Notes: None.
283 *
284 *       File:  cm_hash.c
285 *
286 */
287
288 static S16 cmHashFuncBCD8
289 (
290 CmHashListCp  *hashListCp,        /* hash list control point */
291 uint8_t       *key,               /* key string */
292 uint16_t      keyLen,             /* length of key string */
293 uint16_t      *idx                /* idx to return */
294
295 {
296    uint16_t  tmp16 = 0;
297    uint32_t  firstUInt32 = 0;    /* First  uint32_t prepared for lower 4 octets */
298    uint32_t  secondUInt32 = 0;   /* Second uint32_t prepared for higher 4 octets */
299    uint32_t  sum;             /* Sum of the above 2 octets to get the index */
300
301
302    /* keyLen is marked Unused to remove compilation 
303     * warnings. */
304    UNUSED(keyLen);
305
306    /* Compute second uint32_t */
307    tmp16 = (uint16_t) PutHiByte(tmp16, (uint8_t) key[0]); 
308    tmp16 = (uint16_t) PutLoByte(tmp16, (uint8_t) key[1]);
309    secondUInt32 = (uint32_t) PutHiWord(secondUInt32, (uint16_t) tmp16); 
310    tmp16 = (uint16_t) PutHiByte(tmp16, (uint8_t) key[2]);
311    tmp16 = (uint16_t) PutLoByte(tmp16, (uint8_t) key[3]);
312    secondUInt32 = (uint32_t) PutLoWord(secondUInt32, (uint16_t) tmp16); 
313
314
315    /* Compute first uint32_t */
316    tmp16 = (uint16_t) PutHiByte(tmp16, (uint8_t) key[4]); 
317    tmp16 = (uint16_t) PutLoByte(tmp16, (uint8_t) key[5]);
318    firstUInt32 = (uint32_t) PutHiWord(firstUInt32, (uint16_t) tmp16); 
319    tmp16 = (uint16_t) PutHiByte(tmp16, (uint8_t) key[6]);
320    tmp16 = (uint16_t) PutLoByte(tmp16, (uint8_t) key[7]);
321    firstUInt32 = (uint32_t) PutLoWord(firstUInt32, (uint16_t) tmp16); 
322
323    sum = firstUInt32 + secondUInt32;
324
325    /* if nmbBins is a power of 2, use shift, else use division */
326    if (hashListCp->binBitMask != CM_HASH_NOBITMASK)
327       *idx = (uint16_t) (sum & hashListCp->binBitMask);
328    else
329       *idx = (uint16_t) (sum % hashListCp->nmbBins);
330
331    return ROK;
332 } /* end of cmHashFuncBCD8 () */
333
334 /*
335 *
336 *       Fun:   cmHashFuncString
337 *
338 *       Desc:  Computes the hash list index (bin number) for a specified
339 *              key of type CM_HASH_KEYTYPE_STR. 
340 *
341 *              for (length of string)
342 *                 idx = (31 * idx) + *string;
343 *
344 *              return (idx % hash_table_size);
345 *
346 *       Ret:   ROK     - successful, *idx contains computed index 
347 *
348 *       Notes: None.
349 *
350 *       File:  cm_hash.c
351 *
352 */
353
354 static S16 cmHashFuncString
355 (
356 CmHashListCp *hashListCp,        /* hash list control point */
357 uint8_t      *key,               /* key string */
358 uint16_t     keyLen,             /* length of key string */
359 uint16_t     *idx                /* idx to return */
360
361 {
362    uint16_t  cntr;               /* Index */
363    uint32_t  sum;                /* Sum of octets for hash function */
364
365
366    sum = 0;
367
368    for (cntr = 0; cntr < keyLen; cntr++)
369    {
370       sum = (CM_STR_HASHFUNC_CONSTANT * sum) + key[cntr];
371    }
372
373    /* if nmbBins is a power of 2, use shift, else use division */
374    if (hashListCp->binBitMask != CM_HASH_NOBITMASK)
375       *idx = (uint16_t) (sum & hashListCp->binBitMask);
376    else
377       *idx = (uint16_t) (sum % hashListCp->nmbBins);
378
379    return ROK;
380
381 } /* end of cmHashFuncString () */
382
383
384 \f  
385 /*
386 *
387 *       Fun:   cmHashFuncDefault
388 *
389 *       Desc:  Computes the hash list index (bin number) for a specified
390 *              key of type CM_HASH_KEYTYPE_DEF. 
391 *
392 *              Adds up all the octets of the key string
393 *              and divides the sum by the range to get the desired index.
394 *
395 *       Ret:   ROK     - successful, *idx contains computed index 
396 *
397 *       Notes: None.
398 *
399 *       File:  cm_hash.c
400 *
401 */
402
403 static S16 cmHashFuncDefault
404 (
405 CmHashListCp *hashListCp,        /* hash list control point */
406 uint8_t      *key,               /* key string */
407 uint16_t     keyLen,             /* length of key string */
408 uint16_t     *idx                /* index to return */
409
410 {
411    uint32_t  sum;                /* sum of key string octets */
412
413
414    /* add all bytes of the key */
415    sum = 0;
416    while (keyLen--)
417       sum += (uint32_t) (*key++);
418
419    /* compute index by dividing the range into the sum */
420
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);
424    else
425       *idx = (uint16_t) (sum % hashListCp->nmbBins);
426
427    return ROK;
428
429 } /* end of cmHashFuncDefault */
430
431 \f  
432 /*
433 *
434 *       Fun:   cmHashFuncMult24
435 *
436 *       Desc:  Computes the hash list index (bin number) for a specified
437 *              key of type CM_HASH_KEYTYPE_MULT24. 
438 *
439 *              Multiplies the given key (max k bits) with a constant
440 *              multiplier and extracts p bits of the result, from the 
441 *              bit position k-1 to bit position k-p, to get the hash
442 *              list index. p is such that 2^p is number of bins.
443 *
444 *              The constant multiplier is the floor of A * 2^k, for
445 *              some constant A.
446 *
447 *              This function uses a pre-computed constant multiplier
448 *              CM_HASH_MULTMETHOD_CNST24, which is computed for 
449 *              A = (sqrt(5) - 1)/2, and k = 24 bits.
450 *
451 *              This hashing method is explained in section 12.3.2 of
452 *              "Introduction to Algorithms" by Thomas H. Cormen et al.,
453 *              The MIT Press.
454 *
455 *       Ret:   ROK     - successful, *idx contains computed index 
456 *
457 *       Notes: None.
458 *
459 *       File:  cm_hash.c
460 *
461 */
462
463 static S16 cmHashFuncMult24
464 (
465 CmHashListCp *hashListCp,        /* hash list control point */
466 uint8_t      *key,               /* key string */
467 uint16_t     keyLen,             /* length of key string */
468 uint16_t     *idx                /* index to return */
469
470 {
471    uint32_t  prod;               /* (constant multiplier * key) */
472    uint8_t   shift;              /* Bits to be shifted to get index */
473
474
475    UNUSED(keyLen);
476
477 #if (ERRCLASS & ERRCLS_DEBUG)
478    /* error check on parameters */
479    if (hashListCp->binBitMask == CM_HASH_NOBITMASK)
480       return RFAILED;
481 #endif
482
483    prod = CM_HASH_MULT24_CONST * *((uint32_t *)key);
484
485    shift = CM_HASH_MULT24_BITPOS - hashListCp->nmbBinBits;
486    *idx = ((uint16_t) (prod & (hashListCp->binBitMask << shift))) >> shift;
487
488    return ROK;
489 } /* end of cmHashFuncMult24 */
490
491
492
493 \f  
494 /*
495 *
496 *       Fun:   cmHashFuncConId
497 *
498 *       Desc:  Computes the hash list index (bin number) for a specified
499 *              key of type CM_HASH_KEYTYPE_CONID. 
500 *
501 *              This function can be used for keys that are an integer whose 
502 *              size is uint8_t, uint16_t or uint32_t. Instead of adding all octets of the key,
503 *              this fn computes the "index" of the bin in which the entry
504 *              needs to be inserted by taking a modulo of the integer with the 
505 *              total number of bins.
506 *              This function is typically suitable for a sequentially increasing
507 *              number like suConnId/spConnId
508 *
509 *       Ret:   ROK     - successful, *idx contains computed index 
510 *
511 *       Notes: None.
512 *
513 *       File:  cm_hash.c
514 *
515 */
516
517 static S16 cmHashFuncConId
518 (
519 CmHashListCp *hashListCp,        /* hash list control point */
520 uint8_t      *key,               /* key string */
521 uint16_t     keyLen,             /* length of key string */
522 uint16_t     *idx                /* index to return */
523
524 {
525
526
527    /* switch based on the length of the key */
528    switch (keyLen)
529    {
530       case CM_HASHKEYLEN_UINT32:
531         if (hashListCp->binBitMask != CM_HASH_NOBITMASK)
532          *idx = (uint16_t) (((uint32_t) *((uint32_t *)key)) & hashListCp->binBitMask);
533         else
534          *idx = (uint16_t) (((uint32_t) *((uint32_t *)key)) % hashListCp->nmbBins);  
535         break;
536
537       case CM_HASHKEYLEN_UINT16:
538          if (hashListCp->binBitMask != CM_HASH_NOBITMASK)
539            *idx = (uint16_t) (((uint16_t)*((uint16_t *)key)) & hashListCp->binBitMask);
540          else
541            *idx = (uint16_t) (((uint16_t)*((uint16_t *)key)) % hashListCp->nmbBins);
542          break;
543
544       case CM_HASHKEYLEN_UINT8:
545          if (hashListCp->binBitMask != CM_HASH_NOBITMASK)
546            *idx = (uint16_t) (((uint8_t)*((uint8_t *)key)) & hashListCp->binBitMask);
547          else
548            *idx = (uint16_t) (((uint8_t)*((uint8_t *)key)) % hashListCp->nmbBins);
549          break;
550
551       default:
552          return RFAILED;
553    }
554    return ROK;
555
556 } /* end of cmHashFuncConId */
557
558
559 \f  
560 /*
561 *
562 *       Fun:   cmHashFuncDirIdx
563 *
564 *       Desc:  Computes the hash list index (bin number) for a specified
565 *              key of type CM_HASH_KEYTYPE_DIRINDEX. 
566 *
567 *              The key is the hash table index.
568 *
569 *       Ret:   ROK     - successful, *idx contains computed index 
570 *
571 *       Notes: None.
572 *
573 *       File:  cm_hash.c
574 *
575 */
576
577 static S16 cmHashFuncDirIdx
578 (
579 CmHashListCp *hashListCp,        /* hash list control point */
580 uint8_t      *key,               /* key string */
581 uint16_t     keyLen,             /* length of key string */
582 uint16_t     *idx                /* index to return */
583
584 {
585
586    UNUSED(hashListCp);
587    UNUSED(keyLen);
588
589    *idx = *((uint16_t *) key);
590
591    return ROK;
592 } /* end of cmHashFuncDirIdx */
593
594 \f  
595 /*
596 *
597 *       Fun:   cmHashMatchKey
598 *
599 *       Desc:  Compares two keys and determines if they match.
600 *
601 *       Ret:   ROK     - match successful
602 *              RFAILED - match failed (non-matching key values)
603 *
604 *       Notes: None.
605 *
606 *       File:  cm_hash.c
607 *
608 */
609
610 static S16 cmHashMatchKey
611 (
612 uint8_t *key1,                         /* first key string */
613 uint16_t keyLen1,                      /* length of first key string */
614 uint8_t *key2,                         /* second key string */
615 uint16_t keyLen2                       /* length of second key string */
616
617 {
618
619    /* compare key lengths */
620    if (keyLen1 != keyLen2)
621       return RFAILED;
622
623    /* compare key strings */
624    return (cmMemcmp(key1, key2, (PTR) keyLen1));
625 } /* end of cmHashMatchKey */
626
627 \f  
628 /*
629 *
630 *       Fun:   cmListInsert
631 *
632 *       Desc:  Adds an entry into a doubly linked list
633 *
634 *       Ret:   ROK      - insertion successful
635 *
636 *       Notes: None
637 *
638 *       File:  cm_hash.c
639 *
640 */
641
642 static S16 cmListInsert
643 (
644 CmListEnt *oldEntry,                    /* add new entry after this entry */
645 CmListEnt *newEntry                     /* new entry to add */
646
647 {
648
649    newEntry->next         = oldEntry->next;
650    newEntry->prev         = oldEntry;
651    oldEntry->next         = newEntry;
652    (newEntry->next)->prev = newEntry;
653
654    return ROK;
655 } /* end of cmListInsert */
656
657 \f  
658 /*
659 *
660 *       Fun:   cmListDelete
661 *
662 *       Desc:  Deletes an entry from a doubly linked list
663 *
664 *       Ret:   ROK      - deletion successful
665 *
666 *       Notes: None
667 *
668 *       File:  cm_hash.c
669 *
670 */
671
672 static S16 cmListDelete
673 (
674 CmListEnt *entry                        /* entry to delete */
675
676 {
677
678    if (entry == NULLP) 
679       return RFAILED;
680
681    if (entry->prev != NULLP)
682       (entry->prev)->next = entry->next;
683
684    if (entry->next != NULLP)
685       (entry->next)->prev = entry->prev;
686
687    return ROK;
688 } /* end of cmListDelete */
689
690
691 \f
692 /*
693  *     public functions
694  */
695
696 \f
697 /*
698 *
699 *       Fun:   cmHashListInit
700 *
701 *       Desc:  Initializes a hash list. Parameters are: 
702 *
703 *              hashListCp   control point for hash list
704 *              nmbBins      number of bins in the hash list. Storage will
705 *                           be allocated for them from the indicated memory
706 *                           region and pool.
707 *              offset       if the entries in this hash list are also going
708 *                           to be attached to another hash list, they will
709 *                           contain multiple hash list entry headers. The
710 *                           offset indicates the offset of the entry header
711 *                           for this hash list in the entry structure.
712 *              dupFlg       whether entries with duplicate keys are allowed
713 *                           to be inserted in the hash list.
714 *              keyType      indicates type of key which can be used to select
715 *                           different hash functions. Ignored in this
716 *                           implementation.
717 *              region       
718 *              pool         for allocating storage for bins.
719 *
720 *       Ret:   ROK      - initialization successful
721 *              RFAILED  - initialization failed, lack of memory
722 *
723 *       Notes: None
724 *
725 *       File:  cm_hash.c
726 *
727 */
728 S16 cmHashListInit
729 (
730 CmHashListCp *hashListCp,  /* hash list to initialize */
731 uint16_t     nmbBins,      /* number of hash list bins */
732 uint16_t     offset,       /* offset of CmHashListEnt in entries */
733 Bool         dupFlg,       /* allow duplicate keys */
734 uint16_t     keyType,      /* key type for selecting hash fn */
735 Region       region,       /* memory region to allocate bins */
736 Pool         pool          /* memory pool to allocate bins */
737 )
738 {
739    uint16_t i;
740 #ifndef CM_MT_HASH_BIN
741    CmListEnt *hl;
742 #else
743    CmListBinEnt *hl;
744 #endif
745
746
747 #if (ERRCLASS & ERRCLS_DEBUG)
748    /* error check on parameters */
749    if (hashListCp == NULLP) 
750       return RFAILED;
751 #endif
752
753    /* initialize control point fields */
754    hashListCp->hl      = NULLP;
755    hashListCp->region  = region;
756    hashListCp->pool    = pool;
757    hashListCp->nmbBins = 0;
758    hashListCp->binBitMask = CM_HASH_NOBITMASK;
759    hashListCp->nmbBinBits = 0;
760 #ifndef CM_MT_HASH_BIN
761    hashListCp->nmbEnt  = 0;
762 #endif
763    hashListCp->offset  = offset;
764    hashListCp->dupFlg  = dupFlg;
765    hashListCp->keyType = keyType;
766    hashListCp->hashFunc = NULLP;
767
768    /* initialize hash function for this key type */
769    switch (keyType)
770    {
771       case CM_HASH_KEYTYPE_MULT24:
772          /* return failure if number of bins is not a power of 2 */
773          if (((nmbBins) & (nmbBins - 1)) != 0)
774             return  (RFAILED);
775
776          hashListCp->hashFunc = cmHashFuncMult24;
777          break;
778
779       case CM_HASH_KEYTYPE_DIRIDX:
780          hashListCp->hashFunc = cmHashFuncDirIdx;
781          break;
782
783       case CM_HASH_KEYTYPE_STR:
784          hashListCp->hashFunc = cmHashFuncString;
785          break;
786
787       case CM_HASH_KEYTYPE_UINT32_MOD:
788          hashListCp->hashFunc = cmHashFuncU32Mod;
789          break;
790
791       case CM_HASH_KEYTYPE_BCD8:
792          hashListCp->hashFunc = cmHashFuncBCD8;
793          break;
794
795       case CM_HASH_KEYTYPE_ANY:
796          hashListCp->hashFunc = cmHashFuncAnyKey;
797          break;
798
799       case CM_HASH_KEYTYPE_CONID:
800         hashListCp->hashFunc = cmHashFuncConId;
801         break;
802
803       case CM_HASH_KEYTYPE_DEF:      /* default hash function */
804       default:                       /* illegal key type */
805          hashListCp->hashFunc = cmHashFuncDefault;
806          break;
807    }
808
809    /* allocate memory for bins */
810    if (nmbBins)
811    {
812 #ifndef CM_MT_HASH_BIN
813       if (SGetSBufNewForDebug(__FILE__,__FUNCTION__,__LINE__,region, pool, (Data **) &hashListCp->hl, 
814                    (Size) (nmbBins * sizeof(CmListEnt))) != ROK)
815          return RFAILED;
816 #else
817       if (SGetSBufNewForDebug(__FILE__,__FUNCTION__,__LINE__,region, pool, (Data **) &hashListCp->hl, 
818                    (Size) (nmbBins * sizeof(CmListBinEnt))) != ROK)
819          return RFAILED;
820 #endif
821
822       /* initialize bin pointers */
823       hl = hashListCp->hl;
824       for(i = 0; i < nmbBins; i++)
825       {
826 #ifndef CM_MT_HASH_BIN
827          hl[i].next = hl[i].prev = &hl[i];
828 #else
829          /* This initialization is being done as a part of checking 
830           * the presence of empty/non-empty bins. 
831           */
832          hl[i].next = hl[i].prev = (CmListEnt*)&hl[i];
833          hl[i].nmbEnt = 0;
834 #endif
835       }
836
837       /* initialize bin size */
838       hashListCp->nmbBins = nmbBins;
839
840       /* initialize bin bit mask */
841       if (((nmbBins) & (nmbBins - 1)) == 0)
842       {
843          uint16_t   binBitMask;
844
845          /* number of bins is a power of 2 */
846          hashListCp->binBitMask = nmbBins - 1;
847
848          /* compute number of bits in the bit mask */
849          for (binBitMask = hashListCp->binBitMask; binBitMask; binBitMask >>= 1)
850             hashListCp->nmbBinBits++;
851
852       }
853    }
854
855    return ROK;
856 } /* end of cmHashListInit */
857
858 \f
859 /*
860 *
861 *       Fun:   cmHashListDeinit
862 *
863 *       Desc:  Deinitializes a hash list. Deallocates memory for bins
864 *              and resets header fields. Parameters are: 
865 *
866 *              hashListCp   control point for hash list
867 *
868 *       Ret:   ROK      - successful
869 *
870 *       Notes: None
871 *
872 *       File:  cm_hash.c
873 *
874 */
875 S16 cmHashListDeinit
876 (
877 CmHashListCp *hashListCp   /* hash list to deinitialize */
878 )
879 {
880
881 #if (ERRCLASS & ERRCLS_DEBUG)
882    /* error check on parameters */
883    if (hashListCp == NULLP) 
884       return RFAILED;
885 #endif
886
887    /* deallocate memory for bins */
888    if (hashListCp->nmbBins)
889 #ifndef CM_MT_HASH_BIN
890       (Void) SPutSBufNewForDebug(__FILE__,__FUNCTION__,__LINE__,hashListCp->region, hashListCp->pool, 
891                       (Data *) hashListCp->hl, 
892                       (Size) (hashListCp->nmbBins * sizeof(CmListEnt)));
893 #else
894       (Void) SPutSBufNewForDebug(__FILE__,__FUNCTION__,__LINE__,hashListCp->region, hashListCp->pool, 
895                       (Data *) hashListCp->hl, 
896                       (Size) (hashListCp->nmbBins * sizeof(CmListBinEnt)));
897 #endif
898
899    /* deinitialize control point fields */
900    hashListCp->hl      = NULLP;
901    hashListCp->region  = REGIONNC;
902    hashListCp->pool    = 0;
903    hashListCp->nmbBins = 0;
904    hashListCp->binBitMask = CM_HASH_NOBITMASK;
905 #ifndef CM_MT_HASH_BIN
906    hashListCp->nmbEnt  = 0;
907 #endif
908    hashListCp->offset  = 0;
909    hashListCp->dupFlg  = FALSE;
910    hashListCp->keyType = CM_HASH_KEYTYPE_DEF;
911    hashListCp->hashFunc = NULLP;
912
913    return ROK;
914 } /* end of cmHashListDeinit */
915
916 \f  
917 /*
918 *
919 *       Fun:   cmHashListInsert
920 *
921 *       Desc:  Inserts a new entry in the hash list. Parameters are: 
922 *
923 *              hashListCp   control point for hash list
924 *              entry        pointer to new entry to add in the hash list
925 *              key          pointer to key string in the new entry
926 *              keyLen       length of key string
927 *
928 *       Ret:   ROK      - insertion successful
929 *              ROKDUP   - insertion failed (duplicate key not allowed)
930 *              RFAILED  - insertion failed (incorrect parameter values)
931 *
932 *       Notes: None
933 *
934 *       File:  cm_hash.c
935 *
936 */
937
938 S16 cmHashListInsert
939 (
940 CmHashListCp *hashListCp,  /* hash list to add to */
941 PTR          entry,        /* entry to add */
942 uint8_t      *key,         /* pointer to key */
943 uint16_t     keyLen        /* length of key */
944 )
945 {
946    CmHashListEnt *hashListEnt;    /* pointer to hash list entry header */
947    PTR dupEntry;                  /* pointer to entry with duplicate key */
948    uint16_t idx;                       /* index for insertion into hash list */
949
950
951 #if (ERRCLASS & ERRCLS_DEBUG)
952    /* error check on parameters */
953    if ((hashListCp == NULLP) || (entry == NULLP) || 
954        (key == NULLP) || (keyLen == 0))
955       return RFAILED;
956 #endif
957
958    /* check for duplicates */
959    if (hashListCp->dupFlg == FALSE)
960    {
961       /* no duplicates allowed, check if key already exists */
962       if (cmHashListFind(hashListCp, key, keyLen, 0, &dupEntry) == ROK)
963          return (ROKDUP);
964    }
965
966    /* get pointer to hash list entry header */
967    hashListEnt = (CmHashListEnt *) (((uint8_t *) entry) + hashListCp->offset);
968
969    /* initialize hash list entry header */
970    hashListEnt->list.next = NULLP;
971    hashListEnt->list.prev = NULLP;
972    hashListEnt->keyLen    = keyLen;
973    hashListEnt->key       = key;
974
975    /* compute index for insertion */
976    if ((*hashListCp->hashFunc)(hashListCp, key, keyLen, &idx) != ROK)
977       return RFAILED;
978
979    hashListEnt->hashVal   = idx;
980
981    /* insert into list */
982    cmListInsert(hashListCp->hl[idx].prev, &hashListEnt->list);
983
984    /* increment count of entries in hash list */
985 #ifndef CM_MT_HASH_BIN
986    hashListCp->nmbEnt++;
987 #else
988    hashListCp->hl[idx].nmbEnt++;
989 #endif /* #ifndef CM_MT_HASH_BIN */
990
991    return ROK;
992 } /* end of cmHashListInsert */
993
994 \f  
995 /*
996 *
997 *       Fun:   cmHashListDelete
998 *
999 *       Desc:  Deletes an entry from the hash list. Parameters are:
1000 *
1001 *              hashListCp   control point for hash list
1002 *              entry        pointer to entry to delete from the hash list
1003 *
1004 *       Ret:   ROK      - deletion successful
1005 *              RFAILED  - deletion failed (incorrect parameter values)
1006 *
1007 *       Notes: None
1008 *
1009 *       File:  cm_hash.c
1010 *
1011 */
1012
1013 S16 cmHashListDelete
1014 (
1015 CmHashListCp *hashListCp,  /* hash list to delete from */
1016 PTR          entry         /* entry to delete */
1017 )
1018 {
1019    CmHashListEnt *hashListEnt;    /* pointer to hash list entry header */
1020 #ifdef CM_MT_HASH_BIN
1021    uint16_t idx;           /* index for selecting the right hash list bin */
1022 #endif
1023
1024
1025 #if (ERRCLASS & ERRCLS_DEBUG)
1026    /* error check on parameters */
1027    if ((hashListCp == NULLP) || (entry == NULLP)) 
1028       return RFAILED;
1029 #endif
1030
1031    /* get pointer to hash list entry header */
1032    hashListEnt = (CmHashListEnt *) (((uint8_t *) entry) + hashListCp->offset);
1033
1034    /* check if entry is already deleted if yes then return OK */
1035    if((hashListEnt->list.next == NULLP) ||
1036       (hashListEnt->list.prev == NULLP))
1037       return ROK;
1038
1039 #ifdef CM_MT_HASH_BIN
1040    /* compute index for insertion */
1041    if ((*hashListCp->hashFunc)(hashListCp, hashListEnt->key, 
1042                               hashListEnt->keyLen, &idx) != ROK)
1043       return RFAILED;
1044 #endif /* #ifdef CM_MT_HASH_BIN */
1045
1046    /* delete entry from list */
1047    cmListDelete(&hashListEnt->list);
1048
1049    /* reinitialize hash list entry header */
1050    hashListEnt->list.next = NULLP;
1051    hashListEnt->list.prev = NULLP;
1052    hashListEnt->keyLen    = 0;
1053    hashListEnt->key       = NULLP;
1054    hashListEnt->hashVal   = 0;
1055
1056    /* decrement count of entries in hash list */
1057 #ifndef CM_MT_HASH_BIN
1058    hashListCp->nmbEnt--;
1059 #else
1060    /* Find the right bin index and decrement the nmbEnt counter */
1061    hashListCp->hl[idx].nmbEnt--;
1062 #endif /* #ifndef CM_MT_HASH_BIN */
1063
1064    return ROK;
1065 } /* end of cmHashListDelete */
1066
1067 \f  
1068 /*
1069 *
1070 *       Fun:   cmHashListFind
1071 *
1072 *       Desc:  Finds an entry in the hash list. Parameters are:
1073 *
1074 *              hashListCp   control point for hash list
1075 *              key          pointer to key string for search
1076 *              keyLen       length of key string
1077 *              seqNmb       sequence number in case duplicates allowed
1078 *              entry        pointer to found entry
1079 *
1080 *       Ret:   ROK      - find successful, *entry points to found entry
1081 *              RFAILED  - find failed, *entry is unchanged 
1082 *                         (incorrect parameter values, key not found)
1083 *
1084 *       Notes: None
1085 *
1086 *       File:  cm_hash.c
1087 *
1088 */
1089
1090 S16 cmHashListFind
1091 (
1092 CmHashListCp *hashListCp,  /* hash list to search */
1093 uint8_t      *key,         /* pointer to key */
1094 uint16_t     keyLen,       /* length of key */
1095 uint16_t     seqNmb,       /* used in case of duplicate keys */
1096 PTR          *entry        /* entry to be returned */
1097 )
1098 {
1099    CmHashListEnt *hashListEnt;    /* pointer to hash list entry header */
1100 #ifndef CM_MT_HASH_BIN
1101    CmListEnt *hashListBin;        /* pointer to hash list bin */
1102 #else
1103    CmListBinEnt *hashListBin;        /* pointer to hash list bin */
1104    uint16_t entCnt=0;                     /* counter for number of entries */
1105 #endif
1106    uint16_t i;                         /* counter for sequence number */
1107    uint16_t idx;                       /* index for insertion into hash list */
1108
1109
1110 #if (ERRCLASS & ERRCLS_DEBUG)
1111    /* error check on parameters */
1112    if ((hashListCp == NULLP) || (key == NULLP) || 
1113        (keyLen == 0) || (entry == NULLP))
1114       return RFAILED;
1115 #endif
1116
1117    /* compute hash table index */
1118    if ((*hashListCp->hashFunc)(hashListCp, key, keyLen, &idx) != ROK)
1119       return RFAILED;
1120
1121    /* search this bin for exact key match */
1122    hashListBin = &hashListCp->hl[idx];
1123    hashListEnt = (CmHashListEnt *) hashListBin->next;
1124
1125    /* examine each entry in bin */
1126    i = 0;
1127 #ifndef CM_MT_HASH_BIN
1128    while (hashListBin != (CmListEnt *) hashListEnt)
1129 #else
1130    for (entCnt=0; entCnt < hashListBin->nmbEnt; entCnt++)
1131 #endif
1132    {
1133       /* check if key matches */
1134       if (cmHashMatchKey(hashListEnt->key, hashListEnt->keyLen, key, keyLen) 
1135           == ROK)
1136       {
1137          /* matching key */
1138          *entry = (PTR) (((uint8_t *) hashListEnt) - hashListCp->offset);
1139
1140          /* check for duplicates */
1141          if (!hashListCp->dupFlg)
1142             return ROK;
1143
1144          /* for duplicate key, check sequence number */
1145          if (i++ == seqNmb)
1146             return ROK;
1147       }
1148
1149       /* go to next entry */
1150       hashListEnt = (CmHashListEnt *) hashListEnt->list.next;
1151    }
1152
1153    /* no matching key found */
1154    return RFAILED;
1155 } /* end of cmHashListFind */
1156
1157 \f
1158 /*
1159 *
1160 *       Fun:   cmHashListGetNext
1161 *
1162 *       Desc:  Gets next entry in hash list with respect to the specified
1163 *              previous entry. If previous entry is NULLP, gets first
1164 *              entry in hash list. Parameters are:
1165 *
1166 *              hashListCp   control point for hash list
1167 *              prevEnt      pointer to previous entry
1168 *              entry        pointer to next entry to be returned
1169 *
1170 *       Ret:   ROK      - get successful, *entry points to found entry
1171 *                         (at beginning of list or in the list)
1172 *              RFAILED  - get failed, *entry is unchanged 
1173 *                         (incorrect parameter values)
1174 *              ROKDNA   - get failed, *entry is unchanged.
1175 *                         (end of list)
1176 *
1177 *       Notes:  This function has to be used cautiously while the 
1178 *               CM Hash Module is being compiled with CM_MT_HASH_BIN.
1179 *               In such cases, this function should be used only after
1180 *               ensuring that none of the other threads are operating
1181 *               on the common hash list.
1182 *
1183 *       File:  cm_hash.c
1184 *
1185 */
1186 S16 cmHashListGetNext
1187 (
1188 CmHashListCp *hashListCp,    /* hash list to get from */
1189 PTR          prevEnt,        /* previous entry */
1190 PTR          *entry          /* entry to be returned */
1191 )
1192 {
1193 #ifndef CM_MT_HASH_BIN
1194    CmListEnt     *hashListBin;   /* temporary hash list bin pointer */
1195 #else
1196    CmListBinEnt  *hashListBin;   /* temporary hash list bin pointer */
1197 #endif
1198    CmHashListEnt *hashListEnt;   /* temporary hash list entry pointer */
1199    CmHashListEnt *prevListEnt;   /* previous hash list entry pointer */
1200    uint16_t           i;              /* hash list counter */
1201
1202
1203 #if (ERRCLASS & ERRCLS_DEBUG)
1204    /* error check on parameters */
1205    if ((hashListCp == NULLP) || (entry == NULLP))
1206       return RFAILED;
1207 #endif
1208
1209    /* check if need to get first entry */
1210    if (prevEnt == NULLP)
1211    {
1212       /* get first entry in hash list */
1213       for (i = 0; i < hashListCp->nmbBins; i++)
1214          /* check for non-empty bin */
1215 #ifndef CM_MT_HASH_BIN
1216          if (hashListCp->hl[i].next != &hashListCp->hl[i])
1217 #else
1218          if (hashListCp->hl[i].next != (CmListEnt*)&hashListCp->hl[i])
1219 #endif
1220          {
1221             /* get first entry in bin */
1222             hashListEnt = (CmHashListEnt *) hashListCp->hl[i].next;
1223
1224             /* requested entry is in nxtEnt */
1225             *entry = (PTR) (((uint8_t *) hashListEnt) - hashListCp->offset);
1226
1227             return ROK;
1228          }
1229
1230       /* no more entries */
1231       return (ROKDNA);
1232    }
1233
1234    /* use previous entry to find next entry */
1235
1236    /* get pointer to previous hash list entry header */
1237    prevListEnt = (CmHashListEnt *) (((uint8_t *) prevEnt) + hashListCp->offset);
1238
1239    /* get index of previous entry */
1240    i = prevListEnt->hashVal;
1241
1242    /* set pointers to get next entry */
1243    hashListBin = &hashListCp->hl[i];
1244    prevListEnt = (CmHashListEnt *) prevListEnt->list.next;
1245    for (;;)
1246    {
1247       /* check if more entries in this bin */
1248       if (prevListEnt != (CmHashListEnt *) hashListBin)
1249       {
1250          /* found next entry */
1251          *entry = (PTR) (((uint8_t *) prevListEnt) - hashListCp->offset);
1252
1253          return ROK;
1254       }
1255
1256       /* no more entries in this bin, go to next bin, check if more bins */
1257       if (++i >= hashListCp->nmbBins)
1258          /* no more entries */
1259          break;
1260
1261       /* reset pointers for next bin */
1262       hashListBin = &hashListCp->hl[i];
1263       prevListEnt = (CmHashListEnt *) hashListBin->next;
1264    }
1265
1266    /* no more entries */
1267    return (ROKDNA);
1268 } /* end of cmHashListGetNext */
1269
1270 #ifdef CM_MT_HASH_BIN
1271 \f
1272 /*
1273 *
1274 *       Fun:   cmHashListBinGetNextEntry
1275 *
1276 *       Desc:  Gets next entry in  a given hash bin respect to the specified
1277 *              previous entry. If previous entry is NULLP, gets first
1278 *              entry in hash bin. Parameters are:
1279 *
1280 *              hashListCp   control point for hash list
1281 *              binIdx       Bin Index to find the entry in
1282 *              prevEnt      pointer to previous entry
1283 *              entry        pointer to next entry to be returned
1284 *
1285 *       Ret:   ROK      - get successful, *entry points to found entry
1286 *                         (at beginning of list or in the list)
1287 *              RFAILED  - get failed, *entry is unchanged 
1288 *                         (incorrect parameter values)
1289 *              ROKDNA   - get failed, *entry is unchanged.
1290 *                         (end of list)
1291 *       Notes:  None.
1292 *
1293 *       File:  cm_hash.c
1294 *
1295 */
1296 S16 cmHashListBinGetNextEntry
1297 (
1298 CmHashListCp *hashListCp,    /* hash list to get from */
1299 uint16_t     binIdx,         /* Bin Index to retreive the entry */
1300 PTR          prevEnt,        /* previous entry */
1301 PTR          *entry          /* entry to be returned */
1302 )
1303 {
1304    CmListBinEnt  *hashListBin;   /* temporary hash list bin pointer */
1305    CmHashListEnt *hashListEnt;   /* temporary hash list entry pointer */
1306    CmHashListEnt *prevListEnt;   /* previous hash list entry pointer */
1307
1308
1309 #if (ERRCLASS & ERRCLS_DEBUG)
1310    /* error check on parameters */
1311    if ((hashListCp == NULLP) || (entry == NULLP))
1312       return RFAILED;
1313 #endif
1314
1315    /* check if need to get first entry */
1316    if (prevEnt == NULLP)
1317    {
1318       /* get first entry in hash list */
1319       /* check for non-empty bin */
1320       if (hashListCp->hl[binIdx].next != (CmListEnt*)&hashListCp->hl[binIdx])
1321       {
1322          /* get first entry in bin */
1323          hashListEnt = (CmHashListEnt *) hashListCp->hl[binIdx].next;
1324
1325          /* requested entry is in nxtEnt */
1326          *entry = (PTR) (((uint8_t *) hashListEnt) - hashListCp->offset);
1327
1328          return ROK;
1329       }
1330
1331       /* no more entries */
1332       return (ROKDNA);
1333    }
1334
1335    /* use previous entry to find next entry */
1336
1337    /* get pointer to previous hash list entry header */
1338    prevListEnt = (CmHashListEnt *) (((uint8_t *) prevEnt) + hashListCp->offset);
1339
1340    /* set pointers to get next entry */
1341    hashListBin = &hashListCp->hl[binIdx];
1342    prevListEnt = (CmHashListEnt *) prevListEnt->list.next;
1343
1344    /* check if more entries in this bin */
1345    if (prevListEnt != (CmHashListEnt *) hashListBin)
1346    {
1347       /* found next entry */
1348       *entry = (PTR) (((uint8_t *) prevListEnt) - hashListCp->offset);
1349
1350       return ROK;
1351    }
1352
1353    /* no more entries */
1354    return (ROKDNA);
1355 } /* end of cmHashListBinGetNextEntry */
1356 #endif
1357
1358 \f
1359 /*
1360 *
1361 *       Fun:   cmHashListQuery
1362 *
1363 *       Desc:  Gets hash list attributes.  Parameters are:
1364 *
1365 *              hashListCp   control point for hash list
1366 *              queryType    type of attribute being queried
1367 *              result       result of query, to be returned
1368 *
1369 *       Ret:   ROK      - successful, *result contains query result
1370 *              RFAILED  - failed, *result unchanged (incorrect parameter values)
1371 *
1372 *       Notes: This function is obsoleted! 
1373 *              Use macros defined in cm_hash.h instead
1374 *
1375 *       File:  cm_hash.c
1376 *
1377 */
1378 S16 cmHashListQuery
1379 (
1380 CmHashListCp *hashListCp,    /* hash list to query */
1381 uint8_t      queryType,      /* type of query */
1382 uint16_t     *result         /* result of query */
1383 )
1384 {
1385 #ifdef CM_MT_HASH_BIN
1386    uint8_t       i;
1387 #endif
1388
1389
1390    /* deal with queries that do not need hashListCp */
1391
1392 #if (ERRCLASS & ERRCLS_DEBUG)
1393    /* error check on parameters */
1394    if (result == NULLP)
1395       return RFAILED;
1396 #endif
1397
1398    /* respond depending on query type */
1399    if (queryType == CM_HASH_QUERYTYPE_BINSIZE)
1400    {
1401       /* storage for each bin */
1402 #ifndef CM_MT_HASH_BIN
1403       *result = (uint16_t) sizeof(CmListEnt);
1404 #else
1405       *result = (uint16_t) sizeof(CmListBinEnt);
1406 #endif
1407       return ROK;
1408    }
1409
1410    /* deal with queries that do need hashListCp */
1411
1412 #if (ERRCLASS & ERRCLS_DEBUG)
1413    /* error check on parameters */
1414    if (hashListCp == NULLP)
1415       return RFAILED;
1416 #endif
1417
1418    /* respond depending on query type */
1419    switch (queryType)
1420    {
1421       case CM_HASH_QUERYTYPE_ENTRIES:   /* current number of entries */
1422 #ifndef CM_MT_HASH_BIN
1423          *result = (uint16_t) hashListCp->nmbEnt;
1424 #else
1425          *result = 0;
1426          for (i=0; i < hashListCp->nmbBins; i++)
1427          {
1428             *result += hashListCp->hl[i].nmbEnt;
1429          }
1430 #endif
1431          return ROK;
1432
1433       case CM_HASH_QUERYTYPE_BINS:      /* number of bins */
1434          *result = (uint16_t) hashListCp->nmbBins;
1435          return ROK;
1436
1437       case CM_HASH_QUERYTYPE_OFFSET:    /* offset of CmHashListEnt in entries */
1438          *result = (uint16_t) hashListCp->offset;
1439          return ROK;
1440
1441       case CM_HASH_QUERYTYPE_DUPFLG:    /* allow duplicate keys */
1442          *result = (uint16_t) hashListCp->dupFlg;
1443          return ROK;
1444
1445       case CM_HASH_QUERYTYPE_KEYTYPE:   /* key type for selecting hash functions */
1446          *result = (uint16_t) hashListCp->keyType;
1447          return ROK;
1448
1449       default:                          /* process other query types */
1450          break;
1451    }
1452
1453    /* illegal query type */
1454    return RFAILED;
1455 } /* end of cmHashListQuery */
1456
1457 #ifdef HASH_OPEN_ADDRESSING
1458 \f  
1459 /*
1460 *
1461 *       Fun:   cmHashListOAInsert
1462 *
1463 *       Desc:  Inserts a new entry in the hash list with open addressing.
1464 *              Parameters are: 
1465 *
1466 *              hashListCp   control point for hash list
1467 *              entry        pointer to new entry to add in the hash list
1468 *              key          pointer to key string in the new entry
1469 *              keyLen       length of key string
1470 *
1471 *       Ret:   ROK      - insertion successful
1472 *              ROKDUP   - insertion failed (duplicate key not allowed)
1473 *              RFAILED  - insertion failed (incorrect parameter values)
1474 *
1475 *       Notes: None
1476 *
1477 *       File:  cm_hash.c
1478 *
1479 */
1480
1481 S16 cmHashListOAInsert
1482 (
1483 CmHashListCp *hashListCp,  /* hash table to add to */
1484 PTR          entry,        /* entry to add */
1485 uint8_t      *key,         /* pointer to key */
1486 uint16_t     keyLen        /* length of key */
1487 )
1488 {
1489 /* cm_hash_c_001.main_21. Modify. Compilation Issue resolved. */
1490 #ifndef CM_MT_HASH_BIN
1491    CmListEnt     *hashBin;        /* temporary hash list bin pointer */
1492 #else
1493    CmListBinEnt  *hashBin;        /* temporary hash list bin pointer */
1494 #endif
1495    CmHashListEnt *hashListEnt;    /* pointer to hash list entry header */
1496    uint16_t idx;                       /* index for insertion into hash list */
1497    uint16_t hashSize;                  /* hash size */
1498    uint16_t i;
1499    /* cm_hash_c_001.main_21. Modify. Compilation Issue resolved. */
1500    uint16_t nmbEnt;
1501
1502
1503 #if (ERRCLASS & ERRCLS_DEBUG)
1504    /* error check on parameters */
1505    if ((hashListCp == NULLP) || (entry == NULLP) || 
1506        (key == NULLP) || (keyLen == 0))
1507       return RFAILED;
1508 #endif
1509
1510 #ifndef CM_MT_HASH_BIN
1511    nmbEnt = hashListCp->nmbEnt;
1512 #else
1513    nmbEnt = 0; 
1514    for (i=0; i < hashListCp->nmbBins; i++)
1515    {
1516       nmbEnt += hashListCp->hl[i].nmbEnt;
1517    }
1518 #endif
1519    /* check if table is full */
1520    if (hashListCp->nmbBins == nmbEnt)
1521       return (ROUTRES);
1522
1523    /* get pointer to hash list entry header */
1524    hashListEnt = (CmHashListEnt *) (((uint8_t *) entry) + hashListCp->offset);
1525
1526    /* initialize hash list entry header */
1527    hashListEnt->list.next = NULLP;
1528    hashListEnt->list.prev = NULLP;
1529    hashListEnt->keyLen    = keyLen;
1530    hashListEnt->key       = key;
1531
1532    /* compute index for insertion */
1533    if ((*hashListCp->hashFunc)(hashListCp, key, keyLen, &idx) != ROK)
1534       return RFAILED;
1535
1536    /*
1537     *  find an empty bin
1538     */
1539    hashSize = hashListCp->nmbBins;
1540    hashBin = &hashListCp->hl[idx];
1541    for (i = hashSize; i > 0; i--)
1542    {
1543       if (hashBin->next == hashBin)
1544          break;                            /* found */
1545       if (++idx >= hashSize)
1546       {
1547          idx = 0;
1548          hashBin = &hashListCp->hl[0];
1549       }
1550       else
1551          hashBin++;
1552    }
1553
1554    /* insert into list */
1555    if (cmListInsert(hashBin->prev, &hashListEnt->list) != ROK)
1556       return RFAILED;
1557
1558    hashListEnt->hashVal   = idx;
1559
1560 #ifndef CM_MT_HASH_BIN
1561    /* increment count of entries in hash list */
1562    hashListCp->nmbEnt++;
1563 #else
1564    hashBin->nmbEnt++;
1565 #endif
1566
1567    return ROK;
1568 } /* end of cmHashListOAInsert */
1569
1570
1571 #endif /* HASH_OPENADDRESSING */
1572
1573 /**********************************************************************
1574          End of file
1575 **********************************************************************/