hashtable.c 12.9 KB
Newer Older
ghaddab's avatar
ghaddab committed
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
/*******************************************************************************
    OpenAirInterface 
    Copyright(c) 1999 - 2014 Eurecom

    OpenAirInterface is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.


    OpenAirInterface is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with OpenAirInterface.The full GNU General Public License is 
   included in this distribution in the file called "COPYING". If not, 
   see <http://www.gnu.org/licenses/>.

  Contact Information
  OpenAirInterface Admin: openair_admin@eurecom.fr
  OpenAirInterface Tech : openair_tech@eurecom.fr
  OpenAirInterface Dev  : openair4g-devel@eurecom.fr
  
ghaddab's avatar
ghaddab committed
26
  Address      : Eurecom, Campus SophiaTech, 450 Route des Chappes, CS 50193 - 06904 Biot Sophia Antipolis cedex, FRANCE
ghaddab's avatar
ghaddab committed
27
28
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
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
//-------------------------------------------------------------------------------------------------------------------------------
hashtable_rc_t hashtable_dump_content (const hash_table_t * const hashtblP, char * const buffer_pP, int * const remaining_bytes_in_buffer_pP )
//-------------------------------------------------------------------------------------------------------------------------------
{
    hash_node_t  *node         = NULL;
    unsigned int  i            = 0;
    unsigned int  num_elements = 0;
    if (hashtblP == NULL) {
        *remaining_bytes_in_buffer_pP = snprintf(
                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) {
                *remaining_bytes_in_buffer_pP = snprintf(
                                buffer_pP,
                                *remaining_bytes_in_buffer_pP,
                                "Key 0x%"PRIx64" Element %p\n",
                                node->key,
                                node->data);
                node=node->next;
            }
        }
        i += 1;
    }
    return HASH_TABLE_OK;
}

gauthier's avatar
???  
gauthier committed
206
207
208
209
210
//-------------------------------------------------------------------------------------------------------------------------------
/*
 * 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.
 */
211
hashtable_rc_t hashtable_insert(hash_table_t * const hashtblP, const hash_key_t keyP, void *dataP)
gauthier's avatar
???  
gauthier committed
212
{
gauthier's avatar
gauthier committed
213
214
    hash_node_t *node = NULL;
    hash_size_t  hash = 0;
gauthier's avatar
gauthier committed
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
241
    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
242
243
244
245
246
247
}
//-------------------------------------------------------------------------------------------------------------------------------
/*
 * 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.
 */
248
hashtable_rc_t hashtable_remove(hash_table_t * const hashtblP, const hash_key_t keyP)
gauthier's avatar
???  
gauthier committed
249
{
gauthier's avatar
gauthier committed
250
    hash_node_t *node, *prevnode=NULL;
gauthier's avatar
gauthier committed
251
    hash_size_t  hash = 0;
gauthier's avatar
gauthier committed
252
253
254
255
256
257
258

    if (hashtblP == NULL) {
        return HASH_TABLE_BAD_PARAMETER_HASHTABLE;
    }
    hash=hashtblP->hashfunc(keyP)%hashtblP->size;
    node=hashtblP->nodes[hash];
    while(node) {
259
        if(node->key == keyP) {
gauthier's avatar
gauthier committed
260
261
262
263
264
265
266
267
268
269
270
271
272
            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
273
274
275
276
277
278
}
//-------------------------------------------------------------------------------------------------------------------------------
/*
 * 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.
 */
279
hashtable_rc_t hashtable_get(const hash_table_t * const hashtblP, const hash_key_t keyP, void** dataP)
gauthier's avatar
???  
gauthier committed
280
{
gauthier's avatar
gauthier committed
281
282
    hash_node_t *node = NULL;
    hash_size_t  hash = 0;
gauthier's avatar
gauthier committed
283
284
285
286
287
288

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

gauthier's avatar
gauthier committed
291
292
293
294
295
296
297
298
299
300
301
    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
302
303
304
305
306
307
308
309
310
311
312
313
314
}
//-------------------------------------------------------------------------------------------------------------------------------
/*
 * 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.
 */

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

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

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

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

gauthier's avatar
gauthier committed
330
331
332
333
334
335
    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
336

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

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

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