hashtable.c 13.2 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*
 * Copyright (c) 2015, EURECOM (www.eurecom.fr)
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice, this
 *    list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * The views and conclusions contained in the software and documentation are those
 * of the authors and should not be interpreted as representing official policies,
 * either expressed or implied, of the FreeBSD Project.
 */
ghaddab's avatar
ghaddab committed
29

gauthier's avatar
???    
gauthier committed
30
31
32
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
33
#include <inttypes.h>
gauthier's avatar
???    
gauthier committed
34
#include "hashtable.h"
gauthier's avatar
gauthier committed
35
#include "assertions.h"
gauthier's avatar
???    
gauthier committed
36
37
38


//-------------------------------------------------------------------------------------------------------------------------------
39
char* hashtable_rc_code2string(hashtable_rc_t rcP)
gauthier's avatar
???    
gauthier committed
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
//-------------------------------------------------------------------------------------------------------------------------------
{
    switch (rcP) {
    case HASH_TABLE_OK:                      return "HASH_TABLE_OK";break;
    case HASH_TABLE_INSERT_OVERWRITTEN_DATA: return "HASH_TABLE_INSERT_OVERWRITTEN_DATA";break;
    case HASH_TABLE_KEY_NOT_EXISTS:          return "HASH_TABLE_KEY_NOT_EXISTS";break;
    case HASH_TABLE_KEY_ALREADY_EXISTS:      return "HASH_TABLE_KEY_ALREADY_EXISTS";break;
    case HASH_TABLE_BAD_PARAMETER_HASHTABLE: return "HASH_TABLE_BAD_PARAMETER_HASHTABLE";break;
    default:                                 return "UNKNOWN hashtable_rc_t";
    }
}
//-------------------------------------------------------------------------------------------------------------------------------
/*
 * free int function
 * hash_free_int_func() is used when this hashtable is used to store int values as data (pointer = value).
 */

void hash_free_int_func(void* memoryP){}

//-------------------------------------------------------------------------------------------------------------------------------
/*
 * Default hash function
 * def_hashfunc() is the default used by hashtable_create() when the user didn't specify one.
 * This is a simple/naive hash function which adds the key's ASCII char values. It will probably generate lots of collisions on large hash tables.
 */

static hash_size_t def_hashfunc(const uint64_t keyP)
{
gauthier's avatar
gauthier committed
68
    return (hash_size_t)keyP;
gauthier's avatar
???    
gauthier committed
69
70
71
72
73
74
75
76
77
}

//-------------------------------------------------------------------------------------------------------------------------------
/*
 * Initialisation
 * hashtable_create() sets up the initial structure of the hash table. The user specified size will be allocated and initialized to NULL.
 * The user can also specify a hash function. If the hashfunc argument is NULL, a default hash function is used.
 * If an error occurred, NULL is returned. All other values in the returned hash_table_t pointer should be released with hashtable_destroy().
 */
78
hash_table_t *hashtable_create(const hash_size_t sizeP, hash_size_t (*hashfuncP)(const hash_key_t ), void (*freefuncP)(void*))
gauthier's avatar
???    
gauthier committed
79
{
gauthier's avatar
gauthier committed
80
    hash_table_t *hashtbl = NULL;
gauthier's avatar
???    
gauthier committed
81

gauthier's avatar
gauthier committed
82
83
84
    if(!(hashtbl=malloc(sizeof(hash_table_t)))) {
        return NULL;
    }
gauthier's avatar
???    
gauthier committed
85

gauthier's avatar
gauthier committed
86
87
88
89
    if(!(hashtbl->nodes=calloc(sizeP, sizeof(hash_node_t*)))) {
        free(hashtbl);
        return NULL;
    }
gauthier's avatar
???    
gauthier committed
90

gauthier's avatar
gauthier committed
91
    hashtbl->size=sizeP;
gauthier's avatar
???    
gauthier committed
92

gauthier's avatar
gauthier committed
93
94
    if(hashfuncP) hashtbl->hashfunc=hashfuncP;
    else hashtbl->hashfunc=def_hashfunc;
gauthier's avatar
???    
gauthier committed
95

gauthier's avatar
gauthier committed
96
97
    if(freefuncP) hashtbl->freefunc=freefuncP;
    else hashtbl->freefunc=free;
gauthier's avatar
???    
gauthier committed
98

gauthier's avatar
gauthier committed
99
    return hashtbl;
gauthier's avatar
???    
gauthier committed
100
101
102
103
104
105
}
//-------------------------------------------------------------------------------------------------------------------------------
/*
 * Cleanup
 * The hashtable_destroy() walks through the linked lists for each possible hash value, and releases the elements. It also releases the nodes array and the hash_table_t.
 */
106
hashtable_rc_t hashtable_destroy(hash_table_t * const hashtblP)
gauthier's avatar
???    
gauthier committed
107
{
gauthier's avatar
gauthier committed
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
    hash_size_t n;
    hash_node_t *node, *oldnode;

    if (hashtblP == NULL) {
        return HASH_TABLE_BAD_PARAMETER_HASHTABLE;
    }

    for(n=0; n<hashtblP->size; ++n) {
        node=hashtblP->nodes[n];
        while(node) {
            oldnode=node;
            node=node->next;
            if (oldnode->data) {
                hashtblP->freefunc(oldnode->data);
            }
            free(oldnode);
        }
    }
    free(hashtblP->nodes);
    free(hashtblP);
    return HASH_TABLE_OK;
gauthier's avatar
???    
gauthier committed
129
130
}
//-------------------------------------------------------------------------------------------------------------------------------
131
hashtable_rc_t hashtable_is_key_exists (const hash_table_t * const hashtblP, const hash_key_t keyP)
gauthier's avatar
???    
gauthier committed
132
133
//-------------------------------------------------------------------------------------------------------------------------------
{
gauthier's avatar
gauthier committed
134
135
    hash_node_t *node = NULL;
    hash_size_t  hash = 0;
gauthier's avatar
gauthier committed
136
137
138
139
140
141
142
143
144
145
146
147
148
149

    if (hashtblP == NULL) {
        return HASH_TABLE_BAD_PARAMETER_HASHTABLE;
    }

    hash=hashtblP->hashfunc(keyP)%hashtblP->size;
    node=hashtblP->nodes[hash];
    while(node) {
        if(node->key == keyP) {
            return HASH_TABLE_OK;
        }
        node=node->next;
    }
    return HASH_TABLE_KEY_NOT_EXISTS;
gauthier's avatar
???    
gauthier committed
150
151
}
//-------------------------------------------------------------------------------------------------------------------------------
152
hashtable_rc_t hashtable_apply_funct_on_elements (hash_table_t *const hashtblP, void functP(hash_key_t keyP, void* dataP, void* parameterP), void* parameterP)
gauthier's avatar
???    
gauthier committed
153
154
//-------------------------------------------------------------------------------------------------------------------------------
{
gauthier's avatar
gauthier committed
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
    hash_node_t  *node         = NULL;
    unsigned int  i            = 0;
    unsigned int  num_elements = 0;
    if (hashtblP == NULL) {
        return HASH_TABLE_BAD_PARAMETER_HASHTABLE;
    }
    while ((num_elements < hashtblP->num_elements) && (i < hashtblP->size)) {
        if (hashtblP->nodes[i] != NULL) {
            node=hashtblP->nodes[i];
            while(node) {
                num_elements += 1;
                functP(node->key, node->data, parameterP);
                node=node->next;
            }
        }
        i += 1;
    }
    return HASH_TABLE_OK;
gauthier's avatar
???    
gauthier committed
173
}
174
//-------------------------------------------------------------------------------------------------------------------------------
175
hashtable_rc_t hashtable_dump_content (const hash_table_t * const hashtblP, char * const buffer_pP, int * const remaining_bytes_in_buffer_pP )
176
177
178
179
180
//-------------------------------------------------------------------------------------------------------------------------------
{
    hash_node_t  *node         = NULL;
    unsigned int  i            = 0;
    if (hashtblP == NULL) {
181
        *remaining_bytes_in_buffer_pP = snprintf(
182
183
184
185
186
187
188
189
190
                buffer_pP,
                *remaining_bytes_in_buffer_pP,
                "HASH_TABLE_BAD_PARAMETER_HASHTABLE");
        return HASH_TABLE_BAD_PARAMETER_HASHTABLE;
    }
    while ((i < hashtblP->size) && (*remaining_bytes_in_buffer_pP > 0)) {
        if (hashtblP->nodes[i] != NULL) {
            node=hashtblP->nodes[i];
            while(node) {
191
192
193
194
195
196
                *remaining_bytes_in_buffer_pP = snprintf(
                                buffer_pP,
                                *remaining_bytes_in_buffer_pP,
                                "Key 0x%"PRIx64" Element %p\n",
                                node->key,
                                node->data);
197
198
199
200
201
202
203
204
                node=node->next;
            }
        }
        i += 1;
    }
    return HASH_TABLE_OK;
}

gauthier's avatar
???    
gauthier committed
205
206
207
208
209
//-------------------------------------------------------------------------------------------------------------------------------
/*
 * Adding a new element
 * To make sure the hash value is not bigger than size, the result of the user provided hash function is used modulo size.
 */
210
hashtable_rc_t hashtable_insert(hash_table_t * const hashtblP, const hash_key_t keyP, void *dataP)
gauthier's avatar
???    
gauthier committed
211
{
gauthier's avatar
gauthier committed
212
213
    hash_node_t *node = NULL;
    hash_size_t  hash = 0;
gauthier's avatar
gauthier committed
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
    if (hashtblP == NULL) {
        return HASH_TABLE_BAD_PARAMETER_HASHTABLE;
    }
    hash=hashtblP->hashfunc(keyP)%hashtblP->size;

    node=hashtblP->nodes[hash];
    while(node) {
        if(node->key == keyP) {
            if (node->data) {
                hashtblP->freefunc(node->data);
            }
            node->data=dataP;
            return HASH_TABLE_INSERT_OVERWRITTEN_DATA;
        }
        node=node->next;
    }
    if(!(node=malloc(sizeof(hash_node_t)))) return -1;
    node->key=keyP;
    node->data=dataP;
    if (hashtblP->nodes[hash]) {
        node->next=hashtblP->nodes[hash];
    } else {
        node->next = NULL;
    }
    hashtblP->nodes[hash]=node;
    hashtblP->num_elements += 1;
    return HASH_TABLE_OK;
gauthier's avatar
???    
gauthier committed
241
242
243
}
//-------------------------------------------------------------------------------------------------------------------------------
/*
244
245
 * To remove an element from the hash table, we just search for it in the linked list for that hash value,
 * and remove it if it is found. If it was not found, it is an error and -1 is returned.
gauthier's avatar
???    
gauthier committed
246
 */
247
hashtable_rc_t hashtable_remove(hash_table_t * const hashtblP, const hash_key_t keyP)
gauthier's avatar
???    
gauthier committed
248
{
gauthier's avatar
gauthier committed
249
    hash_node_t *node, *prevnode=NULL;
gauthier's avatar
gauthier committed
250
    hash_size_t  hash = 0;
gauthier's avatar
gauthier committed
251
252
253
254
255
256
257

    if (hashtblP == NULL) {
        return HASH_TABLE_BAD_PARAMETER_HASHTABLE;
    }
    hash=hashtblP->hashfunc(keyP)%hashtblP->size;
    node=hashtblP->nodes[hash];
    while(node) {
258
        if(node->key == keyP) {
gauthier's avatar
gauthier committed
259
260
261
262
263
264
265
266
267
268
269
270
271
            if(prevnode) prevnode->next=node->next;
            else hashtblP->nodes[hash]=node->next;
            if (node->data) {
                hashtblP->freefunc(node->data);
            }
            free(node);
            hashtblP->num_elements -= 1;
            return HASH_TABLE_OK;
        }
        prevnode=node;
        node=node->next;
    }
    return HASH_TABLE_KEY_NOT_EXISTS;
gauthier's avatar
???    
gauthier committed
272
273
274
275
276
277
}
//-------------------------------------------------------------------------------------------------------------------------------
/*
 * Searching for an element is easy. We just search through the linked list for the corresponding hash value.
 * NULL is returned if we didn't find it.
 */
278
hashtable_rc_t hashtable_get(const hash_table_t * const hashtblP, const hash_key_t keyP, void** dataP)
gauthier's avatar
???    
gauthier committed
279
{
gauthier's avatar
gauthier committed
280
281
    hash_node_t *node = NULL;
    hash_size_t  hash = 0;
gauthier's avatar
gauthier committed
282
283
284
285
286
287

    if (hashtblP == NULL) {
        *dataP = NULL;
        return HASH_TABLE_BAD_PARAMETER_HASHTABLE;
    }
    hash=hashtblP->hashfunc(keyP)%hashtblP->size;
gauthier's avatar
???    
gauthier committed
288
289
/*	fprintf(stderr, "hashtable_get() key=%s, hash=%d\n", key, hash);*/

gauthier's avatar
gauthier committed
290
291
292
293
294
295
296
297
298
299
300
    node=hashtblP->nodes[hash];

    while(node) {
        if(node->key == keyP) {
            *dataP = node->data;
            return HASH_TABLE_OK;
        }
        node=node->next;
    }
    *dataP = NULL;
    return HASH_TABLE_KEY_NOT_EXISTS;
gauthier's avatar
???    
gauthier committed
301
302
303
304
305
306
307
308
309
}
//-------------------------------------------------------------------------------------------------------------------------------
/*
 * Resizing
 * The number of elements in a hash table is not always known when creating the table.
 * If the number of elements grows too large, it will seriously reduce the performance of most hash table operations.
 * If the number of elements are reduced, the hash table will waste memory. That is why we provide a function for resizing the table.
 * Resizing a hash table is not as easy as a realloc(). All hash values must be recalculated and each element must be inserted into its new position.
 * We create a temporary hash_table_t object (newtbl) to be used while building the new hashes.
310
 * This allows us to reuse hashtable_insert() and hashtable_remove(), when moving the elements to the new table.
gauthier's avatar
???    
gauthier committed
311
312
313
 * After that, we can just free the old table and copy the elements from newtbl to hashtbl.
 */

314
hashtable_rc_t hashtable_resize(hash_table_t * const hashtblP, const hash_size_t sizeP)
gauthier's avatar
???    
gauthier committed
315
{
gauthier's avatar
gauthier committed
316
317
318
    hash_table_t       newtbl;
    hash_size_t        n;
    hash_node_t       *node,*next;
gauthier's avatar
???    
gauthier committed
319

gauthier's avatar
gauthier committed
320
321
322
    if (hashtblP == NULL) {
        return HASH_TABLE_BAD_PARAMETER_HASHTABLE;
    }
gauthier's avatar
???    
gauthier committed
323

gauthier's avatar
gauthier committed
324
325
    newtbl.size     = sizeP;
    newtbl.hashfunc = hashtblP->hashfunc;
gauthier's avatar
???    
gauthier committed
326

gauthier's avatar
gauthier committed
327
    if(!(newtbl.nodes=calloc(sizeP, sizeof(hash_node_t*)))) return -1;
gauthier's avatar
???    
gauthier committed
328

gauthier's avatar
gauthier committed
329
330
331
332
333
    for(n=0; n<hashtblP->size; ++n) {
        for(node=hashtblP->nodes[n]; node; node=next) {
            next = node->next;
            hashtable_insert(&newtbl, node->key, node->data);
            // Lionel GAUTHIER: BAD CODE TO BE REWRITTEN
334
            hashtable_remove(hashtblP, node->key);
gauthier's avatar
???    
gauthier committed
335

gauthier's avatar
gauthier committed
336
337
        }
    }
gauthier's avatar
???    
gauthier committed
338

gauthier's avatar
gauthier committed
339
340
341
    free(hashtblP->nodes);
    hashtblP->size=newtbl.size;
    hashtblP->nodes=newtbl.nodes;
gauthier's avatar
???    
gauthier committed
342

gauthier's avatar
gauthier committed
343
    return HASH_TABLE_OK;
gauthier's avatar
???    
gauthier committed
344
345
346
347
}