sfxhash.h

   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