src/shared/hash_op.c

   1 /* @(#) $Id$ */
   2
   3 /* Copyright (C) 2009 Trend Micro Inc.
   4  * All rights reserved.
   5  *
   6  * This program is a free software; you can redistribute it
   7  * and/or modify it under the terms of the GNU General Public
   8  * License (version 2) as published by the FSF - Free Software
   9  * Foundation.
  10  *
  11  * License details at the LICENSE file included with OSSEC or
  12  * online at: http://www.ossec.net/en/licensing.html
  13  */
  14
  15
  16 /* Common API for dealing with hashes/maps */
  17
  18
  19 #include "shared.h"
  20
  21
  22
  23 /** OSHash *OSHash_Create()
  24  * Creates the Hash.
  25  * Returns NULL on error.
  26  */
  27 OSHash *OSHash_Create()
  28 {
  29     int i = 0;
  30     OSHash *self;
  31
  32     /* Allocating memory for the hash */
  33     self = calloc(1, sizeof(OSHash));
  34     if(!self)
  35     {
  36         return(NULL);
  37     }
  38
  39
  40     /* Setting default row size */
  41     self->rows = os_getprime(1024);
  42     if(self->rows == 0)
  43     {
  44         free(self);
  45         return(NULL);
  46     }
  47
  48
  49     /* Creating hashing table */
  50     self->table = (OSHashNode **)calloc(self->rows +1, sizeof(OSHashNode *));
  51     if(!self->table)
  52     {
  53         free(self);
  54         return(NULL);
  55     }
  56
  57
  58     /* Zeroing our tables */
  59     for(i = 0; i <= self->rows; i++)
  60     {
  61         self->table[i] = NULL;
  62     }
  63
  64
  65     /* Getting seed */
  66     srandom(time(0));
  67     self->initial_seed = os_getprime(random() % self->rows);
  68     self->constant = os_getprime(random() % self->rows);
  69
  70
  71     return(self);
  72 }
  73
  74
  75
  76 /** void *OSHash_Free(OSHash *self)
  77  * Frees the memory used by the hash.
  78  */
  79 void *OSHash_Free(OSHash *self)
  80 {
  81     int i = 0;
  82     OSHashNode *curr_node;
  83     OSHashNode *next_node;
  84
  85
  86     /* Freeing each entry */
  87     while(i <= self->rows)
  88     {
  89         curr_node = self->table[i];
  90         next_node = curr_node;
  91         while(next_node)
  92         {
  93             next_node = next_node->next;
  94             free(curr_node);
  95             curr_node = next_node;
  96         }
  97         i++;
  98     }
  99
 100
 101     /* Freeing the hash table */
 102     free(self->table);
 103
 104     free(self);
 105     return(NULL);
 106 }
 107
 108
 109
 110 /** int _os_genhash(OSHash *self, char *key)
 111  * Generates hash for key
 112  */
 113 int _os_genhash(OSHash *self, char *key)
 114 {
 115     unsigned int hash_key = self->initial_seed;
 116
 117     /* What we have here is a simple polynomial hash.
 118      * x0 * a^k-1 .. xk * a^k-k +1
 119      */
 120     while(*key)
 121     {
 122         hash_key *= self->constant;
 123         hash_key += *key;
 124         key++;
 125     }
 126
 127     return(hash_key);
 128 }
 129
 130
 131
 132 /** int OSHash_setSize(OSHash *self, int size)
 133  * Sets new size for hash.
 134  * Returns 0 on error (out of memory).
 135  */
 136 int OSHash_setSize(OSHash *self, int new_size)
 137 {
 138     int i = 0;
 139
 140     /* We can't decrease the size */
 141     if(new_size <= self->rows)
 142     {
 143         return(1);
 144     }
 145
 146
 147     /* Getting next prime */
 148     self->rows = os_getprime(new_size);
 149     if(self->rows == 0)
 150     {
 151         return(0);
 152     }
 153
 154
 155     /* If we fail, the hash should not be used anymore */
 156     self->table = realloc(self->table, (self->rows +1) * sizeof(OSHashNode *));
 157     if(!self->table)
 158     {
 159         return(0);
 160     }
 161
 162
 163     /* Zeroing our tables */
 164     for(i = 0; i <= self->rows; i++)
 165     {
 166         self->table[i] = NULL;
 167     }
 168
 169
 170     /* New seed */
 171     self->initial_seed = os_getprime(random() % self->rows);
 172     self->constant = os_getprime(random() % self->rows);
 173
 174     return(1);
 175 }
 176
 177
 178
 179 /** int OSHash_Add(OSHash *self, char *key, void *data)
 180  * Returns 0 on error.
 181  * Returns 1 on duplicated key (not added)
 182  * Returns 2 on success
 183  * Key must not be NULL.
 184  */
 185 int OSHash_Add(OSHash *self, char *key, void *data)
 186 {
 187     unsigned int hash_key;
 188     unsigned int index;
 189
 190     OSHashNode *curr_node;
 191     OSHashNode *new_node;
 192
 193
 194     /* Generating hash of the message */
 195     hash_key = _os_genhash(self, key);
 196
 197
 198     /* Getting array index */
 199     index = hash_key % self->rows;
 200
 201
 202     /* Checking for duplicated entries in the index */
 203     curr_node = self->table[index];
 204     while(curr_node)
 205     {
 206         /* Checking for duplicated key -- not adding */
 207         if(strcmp(curr_node->key, key) == 0)
 208         {
 209             /* Not adding */
 210             return(1);
 211         }
 212         curr_node = curr_node->next;
 213     }
 214
 215
 216     /* Creating new node */
 217     new_node = calloc(1, sizeof(OSHashNode));
 218     if(!new_node)
 219     {
 220         return(0);
 221     }
 222     new_node->next = NULL;
 223     new_node->data = data;
 224     new_node->key = key;
 225
 226
 227     /* Adding to table */
 228     if(!self->table[index])
 229     {
 230         self->table[index] = new_node;
 231     }
 232     /* If there is duplicated, add to the beginning */
 233     else
 234     {
 235         new_node->next = self->table[index];
 236         self->table[index] = new_node;
 237     }
 238
 239     return(2);
 240 }
 241
 242
 243
 244 /** void *OSHash_Get(OSHash *self, char *key)
 245  * Returns NULL on error (key not found).
 246  * Returns the key otherwise.
 247  * Key must not be NULL.
 248  */
 249 void *OSHash_Get(OSHash *self, char *key)
 250 {
 251     unsigned int hash_key;
 252     unsigned int index;
 253
 254     OSHashNode *curr_node;
 255
 256
 257     /* Generating hash of the message */
 258     hash_key = _os_genhash(self, key);
 259
 260
 261     /* Getting array index */
 262     index = hash_key % self->rows;
 263
 264
 265     /* Getting entry */
 266     curr_node = self->table[index];
 267     while(curr_node)
 268     {
 269         /* We may have colisions, so double check with strcmp */
 270         if(strcmp(curr_node->key, key) == 0)
 271         {
 272             return(curr_node->data);
 273         }
 274
 275         curr_node = curr_node->next;
 276     }
 277
 278     return(NULL);
 279 }
 280
 281
 282
 283 /* EOF */