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