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