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