1 /* Copyright (C) 2009 Trend Micro Inc.
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
10 /* Common API for dealing with hashes/maps */
14 static unsigned int _os_genhash(const OSHash *self, const char *key) __attribute__((nonnull));
18 * Returns NULL on error
20 OSHash *OSHash_Create()
25 /* Allocate memory for the hash */
26 self = (OSHash *) calloc(1, sizeof(OSHash));
31 /* Set default row size */
32 self->rows = os_getprime(1024);
33 if (self->rows == 0) {
38 /* Create hashing table */
39 self->table = (OSHashNode **)calloc(self->rows + 1, sizeof(OSHashNode *));
46 for (i = 0; i <= self->rows; i++) {
47 self->table[i] = NULL;
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);
58 /* Free the memory used by the hash */
59 void *OSHash_Free(OSHash *self)
62 OSHashNode *curr_node;
63 OSHashNode *next_node;
66 while (i <= self->rows) {
67 curr_node = self->table[i];
68 next_node = curr_node;
70 next_node = next_node->next;
73 curr_node = next_node;
78 /* Free the hash table */
85 /* Generates hash for key */
86 static unsigned int _os_genhash(const OSHash *self, const char *key)
88 unsigned int hash_key = self->initial_seed;
90 /* What we have here is a simple polynomial hash.
91 * x0 * a^k-1 .. xk * a^k-k +1
94 hash_key *= self->constant;
95 hash_key += (unsigned int) * key;
102 /* Set new size for hash
103 * Returns 0 on error (out of memory)
105 int OSHash_setSize(OSHash *self, unsigned int new_size)
109 /* We can't decrease the size */
110 if (new_size <= self->rows) {
115 self->rows = os_getprime(new_size);
116 if (self->rows == 0) {
120 /* If we fail, the hash should not be used anymore */
121 self->table = (OSHashNode **) realloc(self->table, (self->rows + 1) * sizeof(OSHashNode *));
126 /* Zero our tables */
127 for (i = 0; i <= self->rows; i++) {
128 self->table[i] = NULL;
132 self->initial_seed = os_getprime((unsigned)random() % self->rows);
133 self->constant = os_getprime((unsigned)random() % self->rows);
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.
144 int OSHash_Update(OSHash *self, const char *key, void *data)
146 unsigned int hash_key;
148 OSHashNode *curr_node;
150 /* Generate hash of the message */
151 hash_key = _os_genhash(self, key);
153 /* Get array index */
154 index = hash_key % self->rows;
156 /* Check for duplicated entries in the index */
157 curr_node = self->table[index];
159 /* Checking for duplicated key -- not adding */
160 if (strcmp(curr_node->key, key) == 0) {
161 curr_node->data = data;
164 curr_node = curr_node->next;
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.
175 int OSHash_Add(OSHash *self, const char *key, void *data)
177 unsigned int hash_key;
179 OSHashNode *curr_node;
180 OSHashNode *new_node;
182 /* Generate hash of the message */
183 hash_key = _os_genhash(self, key);
185 /* Get array index */
186 index = hash_key % self->rows;
188 /* Check for duplicated entries in the index */
189 curr_node = self->table[index];
191 /* Checking for duplicated key -- not adding */
192 if (strcmp(curr_node->key, key) == 0) {
196 curr_node = curr_node->next;
199 /* Create new node */
200 new_node = (OSHashNode *) calloc(1, sizeof(OSHashNode));
204 new_node->next = NULL;
205 new_node->data = data;
206 new_node->key = strdup(key);
207 if ( new_node->key == NULL ) {
209 debug1("hash_op: DEBUG: strdup() failed!");
214 if (!self->table[index]) {
215 self->table[index] = new_node;
217 /* If there is duplicated, add to the beginning */
219 new_node->next = self->table[index];
220 self->table[index] = new_node;
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.
231 void *OSHash_Get(const OSHash *self, const char *key)
233 unsigned int hash_key;
235 const OSHashNode *curr_node;
237 /* Generate hash of the message */
238 hash_key = _os_genhash(self, key);
240 /* Get array index */
241 index = hash_key % self->rows;
244 curr_node = self->table[index];
245 while (curr_node != NULL) {
248 /* We may have collisions, so double check with strcmp */
249 if (curr_node->key != NULL && strcmp(curr_node->key, key) == 0) {
251 return (curr_node->data);
254 curr_node = curr_node->next;
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)
263 OSHashNode *curr_node;
264 OSHashNode *prev_node = 0;
265 unsigned int hash_key;
269 /* Generate hash of the message */
270 hash_key = _os_genhash(self, key);
272 /* Get array index */
273 index = hash_key % self->rows;
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;
281 prev_node->next = curr_node->next;
283 free(curr_node->key);
284 data = curr_node->data;
288 prev_node = curr_node;
289 curr_node = curr_node->next;