src/shared/hash_op.c

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