hashtable.c 10.3 KB
Newer Older
gauthier's avatar
???  
gauthier committed
1
2
3
4
5
6
7
/* from: http://en.literateprograms.org/Hash_table_%28C%29#chunk%20def:node
 *
 */
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include "hashtable.h"
gauthier's avatar
gauthier committed
8
#include "assertions.h"
gauthier's avatar
???  
gauthier committed
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


//-------------------------------------------------------------------------------------------------------------------------------
char* hashtble_rc_code2string(hashtable_rc_t rcP)
//-------------------------------------------------------------------------------------------------------------------------------
{
    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
41
    return (hash_size_t)keyP;
gauthier's avatar
???  
gauthier committed
42
43
44
45
46
47
48
49
50
51
52
}

//-------------------------------------------------------------------------------------------------------------------------------
/*
 * 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().
 */
hash_table_t *hashtable_create(hash_size_t sizeP, hash_size_t (*hashfuncP)(const uint64_t ), void (*freefuncP)(void*))
{
gauthier's avatar
gauthier committed
53
    hash_table_t *hashtbl = NULL;
gauthier's avatar
???  
gauthier committed
54

gauthier's avatar
gauthier committed
55
56
57
    if(!(hashtbl=malloc(sizeof(hash_table_t)))) {
        return NULL;
    }
gauthier's avatar
???  
gauthier committed
58

gauthier's avatar
gauthier committed
59
60
61
62
    if(!(hashtbl->nodes=calloc(sizeP, sizeof(hash_node_t*)))) {
        free(hashtbl);
        return NULL;
    }
gauthier's avatar
???  
gauthier committed
63

gauthier's avatar
gauthier committed
64
    hashtbl->size=sizeP;
gauthier's avatar
???  
gauthier committed
65

gauthier's avatar
gauthier committed
66
67
    if(hashfuncP) hashtbl->hashfunc=hashfuncP;
    else hashtbl->hashfunc=def_hashfunc;
gauthier's avatar
???  
gauthier committed
68

gauthier's avatar
gauthier committed
69
70
    if(freefuncP) hashtbl->freefunc=freefuncP;
    else hashtbl->freefunc=free;
gauthier's avatar
???  
gauthier committed
71

gauthier's avatar
gauthier committed
72
    return hashtbl;
gauthier's avatar
???  
gauthier committed
73
74
75
76
77
78
79
80
}
//-------------------------------------------------------------------------------------------------------------------------------
/*
 * 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.
 */
hashtable_rc_t hashtable_destroy(hash_table_t *hashtblP)
{
gauthier's avatar
gauthier committed
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
    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
102
103
104
105
106
}
//-------------------------------------------------------------------------------------------------------------------------------
hashtable_rc_t hashtable_is_key_exists (hash_table_t *hashtblP, const uint64_t keyP)
//-------------------------------------------------------------------------------------------------------------------------------
{
gauthier's avatar
gauthier committed
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
    hash_node_t *node;
    hash_size_t  hash;

    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
123
124
125
126
127
}
//-------------------------------------------------------------------------------------------------------------------------------
hashtable_rc_t hashtable_apply_funct_on_elements (hash_table_t *hashtblP, void functP(uint64_t keyP, void* dataP, void* parameterP), void* parameterP)
//-------------------------------------------------------------------------------------------------------------------------------
{
gauthier's avatar
gauthier committed
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
    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
146
147
148
149
150
151
152
153
}
//-------------------------------------------------------------------------------------------------------------------------------
/*
 * 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.
 */
hashtable_rc_t hashtable_insert(hash_table_t *hashtblP, const uint64_t keyP, void *dataP)
{
gauthier's avatar
gauthier committed
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
    hash_node_t *node;
    hash_size_t hash;
    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
183
184
185
186
187
188
189
190
}
//-------------------------------------------------------------------------------------------------------------------------------
/*
 * 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.
 */
hashtable_rc_t hashtable_remove(hash_table_t *hashtblP, const uint64_t keyP)
{
gauthier's avatar
gauthier committed
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
    hash_node_t *node, *prevnode=NULL;
    hash_size_t  hash;

    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(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
214
215
216
217
218
219
220
221
}
//-------------------------------------------------------------------------------------------------------------------------------
/*
 * 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.
 */
hashtable_rc_t hashtable_get(hash_table_t *hashtblP, const uint64_t keyP, void** dataP)
{
gauthier's avatar
gauthier committed
222
223
224
225
226
227
228
229
    hash_node_t *node;
    hash_size_t  hash;

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

gauthier's avatar
gauthier committed
232
233
234
235
236
237
238
239
240
241
242
    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
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
}
//-------------------------------------------------------------------------------------------------------------------------------
/*
 * 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.
 * This allows us to reuse hashtable_insert() and hashtable_remove(), when moving the elements to the new table.
 * After that, we can just free the old table and copy the elements from newtbl to hashtbl.
 */

hashtable_rc_t hashtable_resize(hash_table_t *hashtblP, hash_size_t sizeP)
{
gauthier's avatar
gauthier committed
258
259
260
    hash_table_t       newtbl;
    hash_size_t        n;
    hash_node_t       *node,*next;
gauthier's avatar
???  
gauthier committed
261

gauthier's avatar
gauthier committed
262
263
264
    if (hashtblP == NULL) {
        return HASH_TABLE_BAD_PARAMETER_HASHTABLE;
    }
gauthier's avatar
???  
gauthier committed
265

gauthier's avatar
gauthier committed
266
267
    newtbl.size     = sizeP;
    newtbl.hashfunc = hashtblP->hashfunc;
gauthier's avatar
???  
gauthier committed
268

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

gauthier's avatar
gauthier committed
271
272
273
274
275
276
    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
            hashtable_remove(hashtblP, node->key);
gauthier's avatar
???  
gauthier committed
277

gauthier's avatar
gauthier committed
278
279
        }
    }
gauthier's avatar
???  
gauthier committed
280

gauthier's avatar
gauthier committed
281
282
283
    free(hashtblP->nodes);
    hashtblP->size=newtbl.size;
    hashtblP->nodes=newtbl.nodes;
gauthier's avatar
???  
gauthier committed
284

gauthier's avatar
gauthier committed
285
    return HASH_TABLE_OK;
gauthier's avatar
???  
gauthier committed
286
287
288
289
}