2
* \file mei_hash_table.c
4
* \brief Hash table, intended to provide a symbol table
8
This file is part of Code_Saturne, a general-purpose CFD tool.
10
Copyright (C) 1998-2011 EDF S.A.
12
This program is free software; you can redistribute it and/or modify it under
13
the terms of the GNU General Public License as published by the Free Software
14
Foundation; either version 2 of the License, or (at your option) any later
17
This program is distributed in the hope that it will be useful, but WITHOUT
18
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
19
FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
22
You should have received a copy of the GNU General Public License along with
23
this program; if not, write to the Free Software Foundation, Inc., 51 Franklin
24
Street, Fifth Floor, Boston, MA 02110-1301, USA.
27
/*----------------------------------------------------------------------------*/
31
#endif /* __cplusplus */
33
/*----------------------------------------------------------------------------
34
* Standard C library headers
35
*----------------------------------------------------------------------------*/
41
/*----------------------------------------------------------------------------
43
*----------------------------------------------------------------------------*/
46
#include <bft_error.h>
48
/*----------------------------------------------------------------------------
50
*----------------------------------------------------------------------------*/
52
#include "mei_math_util.h"
54
/*----------------------------------------------------------------------------
55
* Header for the current file
56
*----------------------------------------------------------------------------*/
58
#include "mei_hash_table.h"
60
/*============================================================================
61
* Private function definitions
62
*============================================================================*/
65
* \brief Hash function.
68
* \param [in] modulo internal parameter for hash table
70
* \return value associated to the key s
74
_hash(const char *const s, const int modulo)
79
for (i = 0; s[i] != '\0'; i++) {
80
h = h*256 + (unsigned) s[i];
81
if (h >= (unsigned) modulo)
87
/*----------------------------------------------------------------------------
88
* Allocation d'une struct item
89
*----------------------------------------------------------------------------*/
92
_new_item(const char *const key)
96
/* Allocate item proper */
97
BFT_MALLOC(new, 1, struct item);
99
bft_error(__FILE__, __LINE__, 0,
100
"Error in memory allocation\n");
102
/* Allocate memory for string */
103
BFT_MALLOC(new->key, strlen(key)+1, char);
104
if (new->key == NULL)
105
bft_error(__FILE__, __LINE__, 0,
106
"Error in memory allocation\n");
108
BFT_MALLOC(new->data, 1, data_t);
109
if (new->data == NULL)
110
bft_error(__FILE__, __LINE__, 0,
111
"Error in memory allocation\n");
117
/*============================================================================
118
* Fonctions publiques
119
*============================================================================*/
122
/*----------------------------------------------------------------------------
123
* Fonction qui alloue une table de hachage
124
*----------------------------------------------------------------------------*/
126
/* Initialize the hash table to the size (modulo) asked for.
127
* Allocates space for the correct number of pointers and sets them to NULL.
128
* If it can't allocate sufficient memory, signals error by setting the size
133
mei_hash_table_create(hash_table_t *const htable, const int modulo)
137
/* htable length and record number */
139
htable->length = modulo;
141
htable->table = NULL;
143
/* htable memory allocation */
144
BFT_MALLOC(htable->table, modulo, struct item*);
145
if (htable->table == NULL) {
147
bft_error(__FILE__, __LINE__, 0,
148
"Error in memory allocation\n");
151
/*htable default initialization: at the beginning all lists are empty */
152
for (i = 0; i < modulo; i++)
153
htable->table[i] = NULL;
157
/*----------------------------------------------------------------------------
158
* Insert an element in a hash table
160
* If the element is already present in the hash table, the pointer
161
* to it is returned. Otherwise, a new element is added, and a pointer
162
* to that element is added.
163
*----------------------------------------------------------------------------*/
166
mei_hash_table_find(hash_table_t *const htable, const char *const key)
172
/* List where the string is to be found */
173
v = _hash(key, htable->length);
174
l = htable->table[v];
176
/* Parcours de la liste */
177
for ( p = l; p != 0; p = p->next)
178
if (strcmp(p->key, key) == 0) return p;
184
/*----------------------------------------------------------------------------
185
* Insertion d'un identificateur dans une table
186
*----------------------------------------------------------------------------*/
189
mei_hash_table_insert(hash_table_t *const htable,
190
const char *const key,
191
const mei_flag_t type,
199
struct item* item = mei_hash_table_find(htable, key);
203
/* The string was not found. Create a new item to insert it */
204
item = _new_item(key);
208
item->data->func = f1;
210
} else if (type == FUNC2) {
213
} else if (type == FUNC3) {
214
bft_error(__FILE__, __LINE__, 0, "not implemented yet \n");
216
} else if (type == FUNC4) {
217
bft_error(__FILE__, __LINE__, 0, "not implemented yet \n");
220
item->data->value = value;
222
strcpy(item->key, key);
226
/* Insert a cell at the head of a list */
227
v = _hash(key, htable->length);
228
item->next = htable->table[v];
229
htable->table[v]= item;
232
item->data->value = value;
237
/*----------------------------------------------------------------------------
239
*----------------------------------------------------------------------------*/
243
mei_hash_table_lookup(hash_table_t *const htable, const char *const key)
246
struct item *item, *next; /* Pointers to current and next record
247
* while traversing hash table bucket. */
249
v = _hash(key, htable->length);
251
/* Lookup for name in hash table bucket corresponding to above hash value. */
253
item = htable->table[v];
257
if (!strcmp(item->key, key)) return item;
265
/*----------------------------------------------------------------------------
266
* Destruction de la table de hachage
267
*----------------------------------------------------------------------------*/
271
mei_hash_table_free(hash_table_t *const htable)
274
struct item *item, *next; /* Pointers to current and next record
275
* while traversing hash table bucket. */
277
if (htable == NULL) return;
279
/* Delete hash table as well as data structure representing symbol table. */
280
for (i = 0; i < htable->length; i++) {
282
item = htable->table[i];
287
BFT_FREE(item->data);
292
BFT_FREE(htable->table);
296
/*----------------------------------------------------------------------------
297
* Fonction qui initialise la table de hachage
298
*----------------------------------------------------------------------------*/
302
mei_hash_table_init(hash_table_t *const htable)
306
/* predefined constants names*/
307
static const char *constants_names[] = { "e", "pi" };
309
/* predefined constants values */
310
static const double constants[] = {2.7182818284590452354, 3.14159265358979323846};
312
/* predefined functions names with one arguments*/
313
static const char *functions_names[] = { "exp", "log", "sqrt",
315
"asin", "acos", "atan",
316
"sinh", "cosh", "tanh",
319
/* predefined functions pointers to functions to calculate them */
320
static double (*functions[]) (double) = { exp, log, sqrt,
326
/* predefined functions names with two arguments*/
327
static const char *functions2_names[] = { "atan2", "min", "max", "mod" };
329
/* predefined functions pointers to functions to calculate them */
330
static double (*functions2[]) (double, double) = { atan2, mei_min, mei_max, fmod };
333
j = sizeof(constants_names) / sizeof(constants_names[0]);
334
for (i = 0; i < j; i++)
335
mei_hash_table_insert(htable,
344
j = sizeof(functions_names) / sizeof(functions_names[0]);
345
for (i = 0; i < j; i++)
346
mei_hash_table_insert(htable,
355
j = sizeof(functions2_names) / sizeof(functions2_names[0]);
356
for (i = 0; i < j; i++)
357
mei_hash_table_insert(htable,
368
/*----------------------------------------------------------------------------
369
* Impression des item de la table de hachage pour debugage
370
*----------------------------------------------------------------------------*/
374
mei_hash_table_item_print(struct item *item)
376
/* Affichage d'une liste */
377
while (item != NULL) {
378
printf("%s -> %i \n", item->key, item->type);
379
if (item->type != FUNC1 && item->type != FUNC2 && item->type != FUNC3 && item->type != FUNC4)
380
printf("valeur : %f\n", item->data->value);
386
/*----------------------------------------------------------------------------
387
* Dump of table contents for debuging purpose
388
*----------------------------------------------------------------------------*/
392
mei_hash_table_dump(hash_table_t *const htable)
395
for (i = 0; i < htable->length; i++) {
396
if (htable->table[i] != NULL) {
397
printf("Entry %d \n", i);
398
mei_hash_table_item_print(htable->table[i]);
404
/*============================================================================
406
*============================================================================*/
413
main_test(int argc, char *argv[])
415
#define HASHSIZE 701 // Modulo by default for hash tables (101, 211, 701,...)
419
printf("Hash Table Testing\n");
421
mei_hash_table_create(&htable, HASHSIZE);
422
mei_hash_table_init(&htable);
423
mei_hash_table_dump(&htable);
424
item = mei_hash_table_lookup(&htable, toto);
425
if (item) mei_hash_table_item_print(item);
426
mei_hash_table_free(&htable);
436
#endif /* __cplusplus */
added
removed
src/mei/mei_hash_table.c
