src/cm/cm_hash.c

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