3 /* Copyright (C) 2009 Trend Micro Inc.
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
11 * License details at the LICENSE file included with OSSEC or
12 * online at: http://www.ossec.net/en/licensing.html
16 /* Common API for dealing with hashes/maps */
23 /** OSHash *OSHash_Create()
25 * Returns NULL on error.
27 OSHash *OSHash_Create()
32 /* Allocating memory for the hash */
33 self = calloc(1, sizeof(OSHash));
40 /* Setting default row size */
41 self->rows = os_getprime(1024);
49 /* Creating hashing table */
50 self->table = (OSHashNode **)calloc(self->rows +1, sizeof(OSHashNode *));
58 /* Zeroing our tables */
59 for(i = 0; i <= self->rows; i++)
61 self->table[i] = NULL;
67 self->initial_seed = os_getprime(random() % self->rows);
68 self->constant = os_getprime(random() % self->rows);
76 /** void *OSHash_Free(OSHash *self)
77 * Frees the memory used by the hash.
79 void *OSHash_Free(OSHash *self)
82 OSHashNode *curr_node;
83 OSHashNode *next_node;
86 /* Freeing each entry */
87 while(i <= self->rows)
89 curr_node = self->table[i];
90 next_node = curr_node;
93 next_node = next_node->next;
95 curr_node = next_node;
101 /* Freeing the hash table */
110 /** int _os_genhash(OSHash *self, char *key)
111 * Generates hash for key
113 int _os_genhash(OSHash *self, char *key)
115 unsigned int hash_key = self->initial_seed;
117 /* What we have here is a simple polynomial hash.
118 * x0 * a^k-1 .. xk * a^k-k +1
122 hash_key *= self->constant;
132 /** int OSHash_setSize(OSHash *self, int size)
133 * Sets new size for hash.
134 * Returns 0 on error (out of memory).
136 int OSHash_setSize(OSHash *self, int new_size)
140 /* We can't decrease the size */
141 if(new_size <= self->rows)
147 /* Getting next prime */
148 self->rows = os_getprime(new_size);
155 /* If we fail, the hash should not be used anymore */
156 self->table = realloc(self->table, (self->rows +1) * sizeof(OSHashNode *));
163 /* Zeroing our tables */
164 for(i = 0; i <= self->rows; i++)
166 self->table[i] = NULL;
171 self->initial_seed = os_getprime(random() % self->rows);
172 self->constant = os_getprime(random() % self->rows);
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.
185 int OSHash_Add(OSHash *self, char *key, void *data)
187 unsigned int hash_key;
190 OSHashNode *curr_node;
191 OSHashNode *new_node;
194 /* Generating hash of the message */
195 hash_key = _os_genhash(self, key);
198 /* Getting array index */
199 index = hash_key % self->rows;
202 /* Checking for duplicated entries in the index */
203 curr_node = self->table[index];
206 /* Checking for duplicated key -- not adding */
207 if(strcmp(curr_node->key, key) == 0)
212 curr_node = curr_node->next;
216 /* Creating new node */
217 new_node = calloc(1, sizeof(OSHashNode));
222 new_node->next = NULL;
223 new_node->data = data;
227 /* Adding to table */
228 if(!self->table[index])
230 self->table[index] = new_node;
232 /* If there is duplicated, add to the beginning */
235 new_node->next = self->table[index];
236 self->table[index] = new_node;
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.
249 void *OSHash_Get(OSHash *self, char *key)
251 unsigned int hash_key;
254 OSHashNode *curr_node;
257 /* Generating hash of the message */
258 hash_key = _os_genhash(self, key);
261 /* Getting array index */
262 index = hash_key % self->rows;
266 curr_node = self->table[index];
269 /* We may have colisions, so double check with strcmp */
270 if(strcmp(curr_node->key, key) == 0)
272 return(curr_node->data);
275 curr_node = curr_node->next;