src/cm/cm_hash.c

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