Docs and build updates along with prachCfgTableIdx completion
[o-du/l2.git] / 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 **********************************************************************/