src/cm/cm_hash.h

   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
  19 /********************************************************************20**
  20
  21      Name:     common hash functions
  22
  23      Type:     C include file
  24
  25      Desc:     Defines required by common functions.
  26                (Newer version of functions in cm_bdy1)
  27
  28      File:     cm_hash.h
  29
  30 *********************************************************************21*/
  31
  32 #ifndef __CMHASHH__
  33 #define __CMHASHH__
  34
  35 \f
  36 /* defines */
  37
  38 /* key types */
  39
  40 #define CM_HASH_KEYTYPE_DEF         0  /* default key type - selects
  41                                           Trillium supplied default function */
  42 #define CM_HASH_KEYTYPE_MULT24      1  /* key type which uses multiplication
  43                                           method to compute hash list index
  44                                           - function supplied by Trillium */
  45 #define CM_HASH_KEYTYPE_DIRIDX      2  /* direct indexing of hash tables */
  46
  47 #define CM_HASH_KEYTYPE_STR         3  /* Hash Function for Strings */
  48
  49 #define CM_HASH_KEYTYPE_U32MOD      4  /* Mods the key with number of bins
  50                                         * useful if key is U32 numeric */
  51
  52 #define CM_HASH_KEYTYPE_CONID       5  /* Uses diff computation for keylen
  53                                          < U32. Ideal fo conId type params */
  54
  55 #define CM_HASH_KEYTYPE_BCD8        6  /* Converts the 8 BCD coded octets
  56                                         * into 2 U32s and then adds 2
  57                                         * U32s to get one U32. Then applies the
  58                                         * U32Mod technique to get the index */
  59 #define CM_HASH_KEYTYPE_ANY         7  /* Converts a variable length key into
  60                                         * a U32 which is then mapped to number
  61                                         * of hash bins
  62                                         */
  63
  64 /* Constants */
  65 #define CM_STR_HASHFUNC_CONSTANT    31 /* Constant for CM_HASH_KEYTYPE_STR */
  66
  67 /* CONSTANTS for CmHashFuncConId */
  68 /* cm_hash_h_001.main_13 : Fixed for 64 Bit */
  69 #define CM_HASHKEYLEN_U32              sizeof(U32)  /* size of U32 */
  70 #define CM_HASHKEYLEN_U16              sizeof(U16)  /* size of U16 */
  71 #define CM_HASHKEYLEN_U8               sizeof(U8)  /* size of U8 */
  72
  73 /* query types */
  74
  75 #define CM_HASH_QUERYTYPE_BINS     1  /* number of bins */
  76 #define CM_HASH_QUERYTYPE_BINSIZE  2  /* storage for each bin */
  77 #define CM_HASH_QUERYTYPE_ENTRIES  3  /* current number of entries */
  78 #define CM_HASH_QUERYTYPE_OFFSET   4  /* offset of CmHashListEnt in entries */
  79 #define CM_HASH_QUERYTYPE_DUPFLG   5  /* allow duplicate keys */
  80 #define CM_HASH_QUERYTYPE_KEYTYPE  6  /* key type for selecting hash functions */
  81
  82 #define CM_HASH_VALUE(entry)       (entry)->hashVal  /* computed hash value */
  83 #define CM_HASH_SIZE(tbl)          (tbl)->nmbBins    /* hash table size */
  84
  85 #ifndef CM_MT_HASH_BIN
  86 #define CM_HASH_NMBENT(tbl)        (tbl)->nmbEnt     /* number of entries in
  87                                                       * table
  88                                                       */
  89 #endif
  90
  91 #define CM_HASH_DUPFLG(tbl)        (tbl)->dupFlg     /* allow duplicate keys */
  92
  93 #define CM_HASH_OFFSET(tbl)        (tbl)->offset     /* offset of CmHashListEnt
  94                                                       * structure in hash list
  95                                                       * entry
  96                                                       */
  97
  98 #define CM_HASH_KEYTYPE(tbl)       (tbl)->keyType    /* key type for selecting
  99                                                       * hash function
 100                                                       */
 101
 102 #define CM_HASH_BINSIZE       sizeof(CmListEnt) /* size of a single bin
 103                                                  */
 104 /* bin bit mask */
 105
 106 #define CM_HASH_NOBITMASK          0x8000  /* illegal bin bit mask */
 107
 108 /* constant multiplier for multiplication method of computing hash index */
 109 #define CM_HASH_MULT24_CONST       10368890   /* when key is of max 24 bits */
 110
 111 /* bit position where the hash index is extracted in multiplication method */
 112 #define CM_HASH_MULT24_BITPOS        24       /* when key is of max 24 bits */
 113
 114 /*
 115  *  delete an entry from the hash table with open addressing
 116  */
 117 #define cmHashListOADelete(hashListCp, entry) cmHashListDelete(hashListCp, (PTR)entry)
 118
 119
 120 /*
 121  * CM_HASH_MIX -- mix 3 32-bit values reversibly.
 122  * For every delta with one or two bits set, and the deltas of all three
 123  * high bits or all three low bits, whether the original value of a,b,c
 124  * is almost all zero or is uniformly distributed,
 125  * If CM_HASH_MIX() is run forward or backward, at least 32 bits in a,b,c
 126  * have at least 1/4 probability of changing.
 127  * If CM_HASH_MIX() is run forward, every bit of c will change between 1/3 and
 128  * 2/3 of the time.  (Well, 22/100 and 78/100 for some 2-bit deltas.)
 129  * CM_HASH_MIX() was built out of 36 single-cycle latency instructions in a
 130  * structure that could supported 2x parallelism, like so:
 131  *     a -= b;
 132  *     a -= c; x = (c>>13);
 133  *     b -= c; a ^= x;
 134  *     b -= a; x = (a<<8);
 135  *     c -= a; b ^= x;
 136  *     c -= b; x = (b>>13);
 137  *     ...
 138  */
 139 #define CM_HASH_MIX(a,b,c) \
 140 { \
 141   a -= b; a -= c; a ^= (c>>13); \
 142   b -= c; b -= a; b ^= (a<<8);  \
 143   c -= a; c -= b; c ^= (b>>13); \
 144   a -= b; a -= c; a ^= (c>>12); \
 145   b -= c; b -= a; b ^= (a<<16); \
 146   c -= a; c -= b; c ^= (b>>5);  \
 147   a -= b; a -= c; a ^= (c>>3);  \
 148   b -= c; b -= a; b ^= (a<<10); \
 149   c -= a; c -= b; c ^= (b>>15); \
 150 }
 151
 152 #endif /* __CMHASHH__ */
 153
 154 \f
 155 /********************************************************************30**
 156
 157          End of file
 158 **********************************************************************/