1 /* @(#) $Id: ./src/shared/hash_op.c, 2011/09/08 dcid Exp $
4 /* Copyright (C) 2009 Trend Micro Inc.
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
12 * License details at the LICENSE file included with OSSEC or
13 * online at: http://www.ossec.net/en/licensing.html
17 /* Common API for dealing with hashes/maps */
24 /** OSHash *OSHash_Create()
26 * Returns NULL on error.
28 OSHash *OSHash_Create()
33 /* Allocating memory for the hash */
34 self = calloc(1, sizeof(OSHash));
41 /* Setting default row size */
42 self->rows = os_getprime(1024);
50 /* Creating hashing table */
51 self->table = (OSHashNode **)calloc(self->rows +1, sizeof(OSHashNode *));
59 /* Zeroing our tables */
60 for(i = 0; i <= self->rows; i++)
62 self->table[i] = NULL;
68 self->initial_seed = os_getprime(random() % self->rows);
69 self->constant = os_getprime(random() % self->rows);
77 /** void *OSHash_Free(OSHash *self)
78 * Frees the memory used by the hash.
80 void *OSHash_Free(OSHash *self)
83 OSHashNode *curr_node;
84 OSHashNode *next_node;
87 /* Freeing each entry */
88 while(i <= self->rows)
90 curr_node = self->table[i];
91 next_node = curr_node;
94 next_node = next_node->next;
96 curr_node = next_node;
102 /* Freeing the hash table */
111 /** int _os_genhash(OSHash *self, char *key)
112 * Generates hash for key
114 int _os_genhash(OSHash *self, char *key)
116 unsigned int hash_key = self->initial_seed;
118 /* What we have here is a simple polynomial hash.
119 * x0 * a^k-1 .. xk * a^k-k +1
123 hash_key *= self->constant;
133 /** int OSHash_setSize(OSHash *self, int size)
134 * Sets new size for hash.
135 * Returns 0 on error (out of memory).
137 int OSHash_setSize(OSHash *self, int new_size)
141 /* We can't decrease the size */
142 if(new_size <= self->rows)
148 /* Getting next prime */
149 self->rows = os_getprime(new_size);
156 /* If we fail, the hash should not be used anymore */
157 self->table = realloc(self->table, (self->rows +1) * sizeof(OSHashNode *));
164 /* Zeroing our tables */
165 for(i = 0; i <= self->rows; i++)
167 self->table[i] = NULL;
172 self->initial_seed = os_getprime(random() % self->rows);
173 self->constant = os_getprime(random() % self->rows);
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.
184 int OSHash_Update(OSHash *self, char *key, void *data)
186 unsigned int hash_key;
189 OSHashNode *curr_node;
192 /* Generating hash of the message */
193 hash_key = _os_genhash(self, key);
196 /* Getting array index */
197 index = hash_key % self->rows;
200 /* Checking for duplicated entries in the index */
201 curr_node = self->table[index];
204 /* Checking for duplicated key -- not adding */
205 if(strcmp(curr_node->key, key) == 0)
207 free(curr_node->data);
208 curr_node->data = data;
211 curr_node = curr_node->next;
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.
224 int OSHash_Add(OSHash *self, char *key, void *data)
226 unsigned int hash_key;
229 OSHashNode *curr_node;
230 OSHashNode *new_node;
233 /* Generating hash of the message */
234 hash_key = _os_genhash(self, key);
237 /* Getting array index */
238 index = hash_key % self->rows;
241 /* Checking for duplicated entries in the index */
242 curr_node = self->table[index];
245 /* Checking for duplicated key -- not adding */
246 if(strcmp(curr_node->key, key) == 0)
251 curr_node = curr_node->next;
255 /* Creating new node */
256 new_node = calloc(1, sizeof(OSHashNode));
261 new_node->next = NULL;
262 new_node->data = data;
266 /* Adding to table */
267 if(!self->table[index])
269 self->table[index] = new_node;
271 /* If there is duplicated, add to the beginning */
274 new_node->next = self->table[index];
275 self->table[index] = new_node;
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.
288 void *OSHash_Get(OSHash *self, char *key)
290 unsigned int hash_key;
293 OSHashNode *curr_node;
296 /* Generating hash of the message */
297 hash_key = _os_genhash(self, key);
300 /* Getting array index */
301 index = hash_key % self->rows;
305 curr_node = self->table[index];
308 /* We may have colisions, so double check with strcmp */
309 if(strcmp(curr_node->key, key) == 0)
311 return(curr_node->data);
314 curr_node = curr_node->next;