1 /****************************************************************************
2 *
3 * Copyright (C) 2014-2021 Cisco and/or its affiliates. All rights reserved.
4 * Copyright (C) 2003-2013 Sourcefire, Inc.
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License Version 2 as
8 * published by the Free Software Foundation. You may not use, modify or
9 * distribute this program under any other version of the GNU General
10 * Public License.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
20 *
21 ****************************************************************************/
22
23 /*
24 *
25 * sfxhash.h
26 *
27 * generic hash table - stores and maps key + data pairs
28 * (supports memcap and automatic memory recovery when out of memory)
29 *
30 * Author: Marc Norton
31 *
32 */
33
34 #ifndef _SFXHASH_
35 #define _SFXHASH_
36
37 #include <stdlib.h>
38 #include <string.h>
39 #include <time.h>
40
41 #include "sfmemcap.h"
42 #include "sfhashfcn.h"
43 /*
44 * ERROR DEFINES
45 */
46 #define SFXHASH_NOMEM -2
47 #define SFXHASH_ERR -1
48 #define SFXHASH_OK 0
49 #define SFXHASH_INTABLE 1
50 #define SFXHASH_PENDING 2
51
52 /**
53 * HASH NODE
54 */
55 typedef struct _sfxhash_node
56 {
57 struct _sfxhash_node * gnext, * gprev; /// global node list - used for ageing nodes
58 struct _sfxhash_node * next, * prev; /// row node list
59
60 int rindex; /// row index of table this node belongs to.
61
62 void * key; /// Pointer to the key.
63 void * data; /// Pointer to the users data, this is not copied !
64
65 } SFXHASH_NODE;
66
67 typedef int (*SFXHASH_FREE_FCN)( void * key, void * data );
68 /**
69 * SFGX HASH Table
70 */
71 typedef struct _sfxhash
72 {
73 SFHASHFCN * sfhashfcn; /// hash function
74 int keysize; /// bytes in key, if <= 0 -> keys are strings
75 int datasize; /// bytes in key, if == 0 -> user data
76 SFXHASH_NODE ** table; /// array of node ptr's */
77 unsigned nrows; /// # rows int the hash table use a prime number 211, 9871
78 unsigned count; /// total # nodes in table
79
80 unsigned crow; /// findfirst/next row in table
81 unsigned pad;
82 SFXHASH_NODE * cnode; /// findfirst/next node ptr
83 int splay; /// whether to splay nodes with same hash bucket
84
85 unsigned max_nodes; ///maximum # of nodes within a hash
86 MEMCAP mc;
87 unsigned overhead_bytes; /// # of bytes that will be unavailable for nodes inside the table
88 unsigned overhead_blocks; /// # of blocks consumed by the table
89 unsigned find_fail;
90 unsigned find_success;
91
92 SFXHASH_NODE * ghead, * gtail; /// global - root of all nodes allocated in table
93
94 SFXHASH_NODE * fhead, * ftail; /// list of free nodes, which are recyled
95 SFXHASH_NODE * gnode; /* gfirst/gnext node ptr */
96 int recycle_nodes; /// recycle nodes. Nodes are not freed, but are used for subsequent new nodes
97
98 /**Automatic Node Recover (ANR): When number of nodes in hash is equal to max_nodes, remove the least recently
99 * used nodes and use it for the new node. anr_tries indicates # of ANR tries.*/
100 unsigned anr_tries;
101 unsigned anr_count; /// # ANR ops performaed
102 int anr_flag; /// 0=off, !0=on
103 unsigned free_count; /// total # nodes in table
104
105 SFXHASH_FREE_FCN anrfree;
106 SFXHASH_FREE_FCN usrfree;
107
108 } SFXHASH;
109
110 /*
111 * HASH PROTOTYPES
112 */
113 int sfxhash_calcrows(int num);
114 SFXHASH * sfxhash_new( unsigned nrows, int keysize, int datasize, unsigned long memcap,
115 int anr_flag,
116 SFXHASH_FREE_FCN anrfunc,
117 SFXHASH_FREE_FCN usrfunc,
118 int recycle_flag );
119
120 void sfxhash_set_max_nodes( SFXHASH *h, int max_nodes );
121
122 void sfxhash_delete( SFXHASH * h );
123 int sfxhash_make_empty(SFXHASH *);
124
125 int sfxhash_add ( SFXHASH * h, void * key, void * data );
126 SFXHASH_NODE * sfxhash_get_node( SFXHASH * t, const void * key );
127 int sfxhash_remove( SFXHASH * h, void * key );
128
129 /*!
130 * Get the # of Nodes in HASH the table
131 *
132 * @param t SFXHASH table pointer
133 *
134 */
sfxhash_count(SFXHASH * t)135 static inline unsigned sfxhash_count( SFXHASH * t )
136 {
137 return t->count;
138 }
139
140 /*!
141 * Get the # of Nodes in HASH the table
142 *
143 * @param t SFXHASH table pointer
144 *
145 */
sfxhash_total_count(SFXHASH * t)146 static inline unsigned sfxhash_total_count( SFXHASH * t )
147 {
148 return t->count + t->anr_count;
149 }
150
151 /*!
152 * Get the # auto recovery
153 *
154 * @param t SFXHASH table pointer
155 *
156 */
sfxhash_anr_count(SFXHASH * t)157 static inline unsigned sfxhash_anr_count( SFXHASH * t )
158 {
159 return t->anr_count;
160 }
161
162 /*!
163 * Get the # finds
164 *
165 * @param t SFXHASH table pointer
166 *
167 */
sfxhash_find_total(SFXHASH * t)168 static inline unsigned sfxhash_find_total( SFXHASH * t )
169 {
170 return t->find_success + t->find_fail;
171 }
172
173 /*!
174 * Get the # unsucessful finds
175 *
176 * @param t SFXHASH table pointer
177 *
178 */
sfxhash_find_fail(SFXHASH * t)179 static inline unsigned sfxhash_find_fail( SFXHASH * t )
180 {
181 return t->find_fail;
182 }
183
184 /*!
185 * Get the # sucessful finds
186 *
187 * @param t SFXHASH table pointer
188 *
189 */
sfxhash_find_success(SFXHASH * t)190 static inline unsigned sfxhash_find_success( SFXHASH * t )
191 {
192 return t->find_success;
193 }
194
195 /*!
196 * Get the # of overhead bytes
197 *
198 * @param t SFXHASH table pointer
199 *
200 */
sfxhash_overhead_bytes(SFXHASH * t)201 static inline unsigned sfxhash_overhead_bytes( SFXHASH * t )
202 {
203 return t->overhead_bytes;
204 }
205
206 /*!
207 * Get the # of overhead blocks
208 *
209 * @param t SFXHASH table pointer
210 *
211 */
sfxhash_overhead_blocks(SFXHASH * t)212 static inline unsigned sfxhash_overhead_blocks( SFXHASH * t )
213 {
214 return t->overhead_blocks;
215 }
216
217 void * sfxhash_mru( SFXHASH * t );
218 void * sfxhash_lru( SFXHASH * t );
219 SFXHASH_NODE * sfxhash_mru_node( SFXHASH * t );
220 SFXHASH_NODE * sfxhash_lru_node( SFXHASH * t );
221 void * sfxhash_find( SFXHASH * h, void * key );
222 SFXHASH_NODE * sfxhash_find_node( SFXHASH * t, const void * key);
223
224 SFXHASH_NODE * sfxhash_findfirst( SFXHASH * h );
225 SFXHASH_NODE * sfxhash_findnext ( SFXHASH * h );
226
227 SFXHASH_NODE * sfxhash_ghead( SFXHASH * h );
228 SFXHASH_NODE * sfxhash_gnext( SFXHASH_NODE * n );
229 void sfxhash_gmovetofront( SFXHASH *t, SFXHASH_NODE * hnode );
230
231
232 void sfxhash_splaymode( SFXHASH * h, int mode );
233
234 void * sfxhash_alloc( SFXHASH * t, unsigned nbytes );
235 void sfxhash_free( SFXHASH * t, void * p );
236 int sfxhash_free_node(SFXHASH *t, SFXHASH_NODE *node);
237 /* sfxhash_free_anr_lru frees a node from the free list or the LRU node */
238 int sfxhash_free_anr_lru(SFXHASH *t);
239 /* sfxhash_free_anr frees a node from the free list */
240 int sfxhash_free_anr(SFXHASH *t);
241
242 unsigned sfxhash_maxdepth( SFXHASH * t );
243
244
245 int sfxhash_set_keyops( SFXHASH *h ,
246 unsigned (*hash_fcn)( SFHASHFCN * p,
247 unsigned char *d,
248 int n),
249 int (*keycmp_fcn)( const void *s1,
250 const void *s2,
251 size_t n));
252
253
254 SFXHASH_NODE *sfxhash_gfindfirst( SFXHASH * t );
255 SFXHASH_NODE *sfxhash_gfindnext( SFXHASH * t );
256 int sfxhash_add_return_data_ptr( SFXHASH * t, const void * key, void **data );
257 unsigned sfxhash_calc_maxmem(unsigned num_entries, unsigned entry_cost);
258 int sfxhash_change_memcap( SFXHASH * t, unsigned long new_memcap, unsigned *max_work );
259 #endif
260
261