1 /**************************************************************************** 2 * 3 * Copyright (C) 2003-2009 Sourcefire, Inc. 4 * 5 * This program is free software; you can redistribute it and/or modify 6 * it under the terms of the GNU General Public License Version 2 as 7 * published by the Free Software Foundation. You may not use, modify or 8 * distribute this program under any other version of the GNU General 9 * Public License. 10 * 11 * This program is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU General Public License for more details. 15 * 16 * You should have received a copy of the GNU General Public License 17 * along with this program; if not, write to the Free Software 18 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 19 * 20 ****************************************************************************/ 21 22 /* 23 * 24 * sfxhash.h 25 * 26 * generic hash table - stores and maps key + data pairs 27 * (supports memcap and automatic memory recovery when out of memory) 28 * 29 * Author: Marc Norton 30 * 31 */ 32 33 #ifndef _SFXHASH_ 34 #define _SFXHASH_ 35 36 #include <stdlib.h> 37 #include <string.h> 38 #include <time.h> 39 40 #include "sfmemcap.h" 41 #include "sfhashfcn.h" 42 /* 43 * ERROR DEFINES 44 */ 45 #define SFXHASH_NOMEM -2 46 #define SFXHASH_ERR -1 47 #define SFXHASH_OK 0 48 #define SFXHASH_INTABLE 1 49 50 /** 51 * HASH NODE 52 */ 53 typedef struct _sfxhash_node 54 { 55 struct _sfxhash_node * gnext, * gprev; /// global node list - used for ageing nodes 56 struct _sfxhash_node * next, * prev; /// row node list 57 58 int rindex; /// row index of table this node belongs to. 59 60 void * key; /// Pointer to the key. 61 void * data; /// Pointer to the users data, this is not copied ! 62 63 } SFXHASH_NODE; 64 65 /** 66 * SFGX HASH Table 67 */ 68 typedef struct _sfxhash 69 { 70 SFHASHFCN * sfhashfcn; /// hash function 71 int keysize; /// bytes in key, if <= 0 -> keys are strings 72 int datasize; /// bytes in key, if == 0 -> user data 73 SFXHASH_NODE ** table; /// array of node ptr's */ 74 unsigned nrows; /// # rows int the hash table use a prime number 211, 9871 75 unsigned count; /// total # nodes in table 76 77 unsigned crow; /// findfirst/next row in table 78 SFXHASH_NODE * cnode; /// findfirst/next node ptr 79 int splay; /// whether to splay nodes with same hash bucket 80 81 unsigned max_nodes; ///maximum # of nodes within a hash 82 MEMCAP mc; 83 unsigned overhead_bytes; /// # of bytes that will be unavailable for nodes inside the table 84 unsigned overhead_blocks; /// # of blocks consumed by the table 85 unsigned find_fail; 86 unsigned find_success; 87 88 SFXHASH_NODE * ghead, * gtail; /// global - root of all nodes allocated in table 89 90 SFXHASH_NODE * fhead, * ftail; /// list of free nodes, which are recyled 91 int recycle_nodes; /// recycle nodes. Nodes are not freed, but are used for subsequent new nodes 92 93 /**Automatic Node Recover (ANR): When number of nodes in hash is equal to max_nodes, remove the least recently 94 * used nodes and use it for the new node. anr_tries indicates # of ANR tries.*/ 95 unsigned anr_tries; 96 unsigned anr_count; /// # ANR ops performaed 97 int anr_flag; /// 0=off, !0=on 98 99 int (*anrfree)( void * key, void * data ); 100 int (*usrfree)( void * key, void * data ); 101 } SFXHASH; 102 103 104 /* 105 * HASH PROTOTYPES 106 */ 107 int sfxhash_calcrows(int num); 108 SFXHASH * sfxhash_new( int nrows, int keysize, int datasize, int memcap, 109 int anr_flag, 110 int (*anrfunc)(void *key, void * data), 111 int (*usrfunc)(void *key, void * data), 112 int recycle_flag ); 113 114 void sfxhash_set_max_nodes( SFXHASH *h, int max_nodes ); 115 116 void sfxhash_delete( SFXHASH * h ); 117 int sfxhash_make_empty(SFXHASH *); 118 119 int sfxhash_add ( SFXHASH * h, void * key, void * data ); 120 SFXHASH_NODE * sfxhash_get_node( SFXHASH * t, void * key ); 121 int sfxhash_remove( SFXHASH * h, void * key ); 122 unsigned sfxhash_count( SFXHASH * h ); 123 unsigned sfxhash_anr_count( SFXHASH * h ); 124 125 void * sfxhash_mru( SFXHASH * t ); 126 void * sfxhash_lru( SFXHASH * t ); 127 SFXHASH_NODE * sfxhash_mru_node( SFXHASH * t ); 128 SFXHASH_NODE * sfxhash_lru_node( SFXHASH * t ); 129 void * sfxhash_find( SFXHASH * h, void * key ); 130 SFXHASH_NODE * sfxhash_find_node( SFXHASH * t, void * key); 131 132 SFXHASH_NODE * sfxhash_findfirst( SFXHASH * h ); 133 SFXHASH_NODE * sfxhash_findnext ( SFXHASH * h ); 134 135 SFXHASH_NODE * sfxhash_ghead( SFXHASH * h ); 136 SFXHASH_NODE * sfxhash_gnext( SFXHASH_NODE * n ); 137 void sfxhash_gmovetofront( SFXHASH *t, SFXHASH_NODE * hnode ); 138 139 140 void sfxhash_splaymode( SFXHASH * h, int mode ); 141 142 void * sfxhash_alloc( SFXHASH * t, unsigned nbytes ); 143 void sfxhash_free( SFXHASH * t, void * p ); 144 int sfxhash_free_node(SFXHASH *t, SFXHASH_NODE *node); 145 146 unsigned sfxhash_maxdepth( SFXHASH * t ); 147 unsigned sfxhash_overhead_bytes( SFXHASH * t ); 148 unsigned sfxhash_overhead_blocks( SFXHASH * t ); 149 unsigned sfxhash_find_success( SFXHASH * h ); 150 unsigned sfxhash_find_fail( SFXHASH * h ); 151 unsigned sfxhash_find_total( SFXHASH * h ); 152 153 154 int sfxhash_set_keyops( SFXHASH *h , 155 unsigned (*hash_fcn)( SFHASHFCN * p, 156 unsigned char *d, 157 int n), 158 int (*keycmp_fcn)( const void *s1, 159 const void *s2, 160 size_t n)); 161 162 163 #endif 164 165