hashtable.c 11.5 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
33
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include "hashtable.h"
gauthier's avatar
gauthier committed
34
#include "assertions.h"
gauthier's avatar
???  
gauthier committed
35
36
37
38
39
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


//-------------------------------------------------------------------------------------------------------------------------------
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
67
    return (hash_size_t)keyP;
gauthier's avatar
???  
gauthier committed
68
69
70
71
72
73
74
75
76
}

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

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

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

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

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

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

gauthier's avatar
gauthier committed
98
    return hashtbl;
gauthier's avatar
???  
gauthier committed
99
100
101
102
103
104
105
106
}
//-------------------------------------------------------------------------------------------------------------------------------
/*
 * 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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
    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
128
129
}
//-------------------------------------------------------------------------------------------------------------------------------
gauthier's avatar
gauthier committed
130
hashtable_rc_t hashtable_is_key_exists (hash_table_t *hashtblP, const hash_key_t keyP)
gauthier's avatar
???  
gauthier committed
131
132
//-------------------------------------------------------------------------------------------------------------------------------
{
gauthier's avatar
gauthier committed
133
134
    hash_node_t *node = NULL;
    hash_size_t  hash = 0;
gauthier's avatar
gauthier committed
135
136
137
138
139
140
141
142
143
144
145
146
147
148

    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
149
150
}
//-------------------------------------------------------------------------------------------------------------------------------
gauthier's avatar
gauthier committed
151
hashtable_rc_t hashtable_apply_funct_on_elements (hash_table_t *hashtblP, void functP(hash_key_t keyP, void* dataP, void* parameterP), void* parameterP)
gauthier's avatar
???  
gauthier committed
152
153
//-------------------------------------------------------------------------------------------------------------------------------
{
gauthier's avatar
gauthier committed
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
    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
172
173
174
175
176
177
}
//-------------------------------------------------------------------------------------------------------------------------------
/*
 * 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.
 */
gauthier's avatar
gauthier committed
178
hashtable_rc_t hashtable_insert(hash_table_t *hashtblP, const hash_key_t keyP, void *dataP)
gauthier's avatar
???  
gauthier committed
179
{
gauthier's avatar
gauthier committed
180
181
    hash_node_t *node = NULL;
    hash_size_t  hash = 0;
gauthier's avatar
gauthier committed
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
    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
209
210
211
212
213
214
}
//-------------------------------------------------------------------------------------------------------------------------------
/*
 * 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
215
hashtable_rc_t hashtable_remove(hash_table_t *hashtblP, const hash_key_t keyP)
gauthier's avatar
???  
gauthier committed
216
{
gauthier's avatar
gauthier committed
217
    hash_node_t *node, *prevnode=NULL;
gauthier's avatar
gauthier committed
218
    hash_size_t  hash = 0;
gauthier's avatar
gauthier committed
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239

    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
240
241
242
243
244
245
}
//-------------------------------------------------------------------------------------------------------------------------------
/*
 * 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.
 */
gauthier's avatar
gauthier committed
246
hashtable_rc_t hashtable_get(hash_table_t *hashtblP, const hash_key_t keyP, void** dataP)
gauthier's avatar
???  
gauthier committed
247
{
gauthier's avatar
gauthier committed
248
249
    hash_node_t *node = NULL;
    hash_size_t  hash = 0;
gauthier's avatar
gauthier committed
250
251
252
253
254
255

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

gauthier's avatar
gauthier committed
258
259
260
261
262
263
264
265
266
267
268
    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
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
}
//-------------------------------------------------------------------------------------------------------------------------------
/*
 * 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
284
285
286
    hash_table_t       newtbl;
    hash_size_t        n;
    hash_node_t       *node,*next;
gauthier's avatar
???  
gauthier committed
287

gauthier's avatar
gauthier committed
288
289
290
    if (hashtblP == NULL) {
        return HASH_TABLE_BAD_PARAMETER_HASHTABLE;
    }
gauthier's avatar
???  
gauthier committed
291

gauthier's avatar
gauthier committed
292
293
    newtbl.size     = sizeP;
    newtbl.hashfunc = hashtblP->hashfunc;
gauthier's avatar
???  
gauthier committed
294

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

gauthier's avatar
gauthier committed
297
298
299
300
301
302
    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
303

gauthier's avatar
gauthier committed
304
305
        }
    }
gauthier's avatar
???  
gauthier committed
306

gauthier's avatar
gauthier committed
307
308
309
    free(hashtblP->nodes);
    hashtblP->size=newtbl.size;
    hashtblP->nodes=newtbl.nodes;
gauthier's avatar
???  
gauthier committed
310

gauthier's avatar
gauthier committed
311
    return HASH_TABLE_OK;
gauthier's avatar
???  
gauthier committed
312
313
314
315
}