hashtable.c 12.7 KB
Newer Older
1
2
3
4
5
/*
 * Licensed to the OpenAirInterface (OAI) Software Alliance under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The OpenAirInterface Software Alliance licenses this file to You under 
Cedric Roux's avatar
Cedric Roux committed
6
 * the OAI Public License, Version 1.1  (the "License"); you may not use this file
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 * except in compliance with the License.  
 * You may obtain a copy of the License at
 *
 *      http://www.openairinterface.org/?page_id=698
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *-------------------------------------------------------------------------------
 * For more information about the OpenAirInterface (OAI) Software Alliance:
 *      contact@openairinterface.org
 */

gauthier's avatar
???  
gauthier committed
22
23
24
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
25
#include <inttypes.h>
gauthier's avatar
???  
gauthier committed
26
#include "hashtable.h"
gauthier's avatar
gauthier committed
27
#include "assertions.h"
gauthier's avatar
???  
gauthier committed
28
29
30


//-------------------------------------------------------------------------------------------------------------------------------
31
char* hashtable_rc_code2string(hashtable_rc_t rcP)
gauthier's avatar
???  
gauthier committed
32
33
34
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
//-------------------------------------------------------------------------------------------------------------------------------
{
    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
60
    return (hash_size_t)keyP;
gauthier's avatar
???  
gauthier committed
61
62
63
64
65
66
67
68
69
}

//-------------------------------------------------------------------------------------------------------------------------------
/*
 * 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().
 */
70
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
71
{
gauthier's avatar
gauthier committed
72
    hash_table_t *hashtbl = NULL;
gauthier's avatar
???  
gauthier committed
73

gauthier's avatar
gauthier committed
74
75
76
    if(!(hashtbl=malloc(sizeof(hash_table_t)))) {
        return NULL;
    }
gauthier's avatar
???  
gauthier committed
77

gauthier's avatar
gauthier committed
78
79
80
81
    if(!(hashtbl->nodes=calloc(sizeP, sizeof(hash_node_t*)))) {
        free(hashtbl);
        return NULL;
    }
gauthier's avatar
???  
gauthier committed
82

gauthier's avatar
gauthier committed
83
    hashtbl->size=sizeP;
gauthier's avatar
???  
gauthier committed
84

gauthier's avatar
gauthier committed
85
86
    if(hashfuncP) hashtbl->hashfunc=hashfuncP;
    else hashtbl->hashfunc=def_hashfunc;
gauthier's avatar
???  
gauthier committed
87

gauthier's avatar
gauthier committed
88
89
    if(freefuncP) hashtbl->freefunc=freefuncP;
    else hashtbl->freefunc=free;
gauthier's avatar
???  
gauthier committed
90

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

    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
142
143
}
//-------------------------------------------------------------------------------------------------------------------------------
144
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
145
146
//-------------------------------------------------------------------------------------------------------------------------------
{
gauthier's avatar
gauthier committed
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
    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
165
}
166
//-------------------------------------------------------------------------------------------------------------------------------
167
hashtable_rc_t hashtable_dump_content (const hash_table_t * const hashtblP, char * const buffer_pP, int * const remaining_bytes_in_buffer_pP )
168
169
170
171
172
//-------------------------------------------------------------------------------------------------------------------------------
{
    hash_node_t  *node         = NULL;
    unsigned int  i            = 0;
    if (hashtblP == NULL) {
173
        *remaining_bytes_in_buffer_pP = snprintf(
174
175
176
177
178
179
180
181
182
                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) {
183
184
185
186
187
188
                *remaining_bytes_in_buffer_pP = snprintf(
                                buffer_pP,
                                *remaining_bytes_in_buffer_pP,
                                "Key 0x%"PRIx64" Element %p\n",
                                node->key,
                                node->data);
189
190
191
192
193
194
195
196
                node=node->next;
            }
        }
        i += 1;
    }
    return HASH_TABLE_OK;
}

gauthier's avatar
???  
gauthier committed
197
198
199
200
201
//-------------------------------------------------------------------------------------------------------------------------------
/*
 * 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.
 */
202
hashtable_rc_t hashtable_insert(hash_table_t * const hashtblP, const hash_key_t keyP, void *dataP)
gauthier's avatar
???  
gauthier committed
203
{
gauthier's avatar
gauthier committed
204
205
    hash_node_t *node = NULL;
    hash_size_t  hash = 0;
gauthier's avatar
gauthier committed
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
    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
233
234
235
}
//-------------------------------------------------------------------------------------------------------------------------------
/*
236
237
 * 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
238
 */
239
hashtable_rc_t hashtable_remove(hash_table_t * const hashtblP, const hash_key_t keyP)
gauthier's avatar
???  
gauthier committed
240
{
gauthier's avatar
gauthier committed
241
    hash_node_t *node, *prevnode=NULL;
gauthier's avatar
gauthier committed
242
    hash_size_t  hash = 0;
gauthier's avatar
gauthier committed
243
244
245
246
247
248
249

    if (hashtblP == NULL) {
        return HASH_TABLE_BAD_PARAMETER_HASHTABLE;
    }
    hash=hashtblP->hashfunc(keyP)%hashtblP->size;
    node=hashtblP->nodes[hash];
    while(node) {
250
        if(node->key == keyP) {
gauthier's avatar
gauthier committed
251
252
253
254
255
256
257
258
259
260
261
262
263
            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
264
265
266
267
268
269
}
//-------------------------------------------------------------------------------------------------------------------------------
/*
 * 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.
 */
270
hashtable_rc_t hashtable_get(const hash_table_t * const hashtblP, const hash_key_t keyP, void** dataP)
gauthier's avatar
???  
gauthier committed
271
{
gauthier's avatar
gauthier committed
272
273
    hash_node_t *node = NULL;
    hash_size_t  hash = 0;
gauthier's avatar
gauthier committed
274
275
276
277
278
279

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

gauthier's avatar
gauthier committed
282
283
284
285
286
287
288
289
290
291
292
    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
293
294
295
296
297
298
299
300
301
}
//-------------------------------------------------------------------------------------------------------------------------------
/*
 * 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.
302
 * This allows us to reuse hashtable_insert() and hashtable_remove(), when moving the elements to the new table.
gauthier's avatar
???  
gauthier committed
303
304
305
 * After that, we can just free the old table and copy the elements from newtbl to hashtbl.
 */

306
hashtable_rc_t hashtable_resize(hash_table_t * const hashtblP, const hash_size_t sizeP)
gauthier's avatar
???  
gauthier committed
307
{
gauthier's avatar
gauthier committed
308
309
310
    hash_table_t       newtbl;
    hash_size_t        n;
    hash_node_t       *node,*next;
gauthier's avatar
???  
gauthier committed
311

gauthier's avatar
gauthier committed
312
313
314
    if (hashtblP == NULL) {
        return HASH_TABLE_BAD_PARAMETER_HASHTABLE;
    }
gauthier's avatar
???  
gauthier committed
315

gauthier's avatar
gauthier committed
316
317
    newtbl.size     = sizeP;
    newtbl.hashfunc = hashtblP->hashfunc;
gauthier's avatar
???  
gauthier committed
318

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

gauthier's avatar
gauthier committed
321
322
323
324
325
    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
326
            hashtable_remove(hashtblP, node->key);
gauthier's avatar
???  
gauthier committed
327

gauthier's avatar
gauthier committed
328
329
        }
    }
gauthier's avatar
???  
gauthier committed
330

gauthier's avatar
gauthier committed
331
332
333
    free(hashtblP->nodes);
    hashtblP->size=newtbl.size;
    hashtblP->nodes=newtbl.nodes;
gauthier's avatar
???  
gauthier committed
334

gauthier's avatar
gauthier committed
335
    return HASH_TABLE_OK;
gauthier's avatar
???  
gauthier committed
336
337
338
339
}