src/shared/hash_op.c

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