hashtable.c 9.47 KB
Newer Older
gauthier's avatar
???  
gauthier 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
26
27
28
29
30
31
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
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
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
209
210
211
212
213
214
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
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
/* from: http://en.literateprograms.org/Hash_table_%28C%29#chunk%20def:node
 *
 */
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include "hashtable.h"


//-------------------------------------------------------------------------------------------------------------------------------
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)
{
	return (hash_size_t)keyP;
}

//-------------------------------------------------------------------------------------------------------------------------------
/*
 * 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*))
{
	hash_table_t *hashtbl;

	if(!(hashtbl=malloc(sizeof(hash_table_t)))) return NULL;

	if(!(hashtbl->nodes=calloc(sizeP, sizeof(hash_node_t*)))) {
		free(hashtbl);
		return NULL;
	}

	hashtbl->size=sizeP;

	if(hashfuncP) hashtbl->hashfunc=hashfuncP;
	else hashtbl->hashfunc=def_hashfunc;

	if(freefuncP) hashtbl->freefunc=freefuncP;
	else hashtbl->freefunc=free;

	return hashtbl;
}
//-------------------------------------------------------------------------------------------------------------------------------
/*
 * 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)
{
	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;
}
//-------------------------------------------------------------------------------------------------------------------------------
hashtable_rc_t hashtable_is_key_exists (hash_table_t *hashtblP, const uint64_t keyP)
//-------------------------------------------------------------------------------------------------------------------------------
{
	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;
}
//-------------------------------------------------------------------------------------------------------------------------------
hashtable_rc_t hashtable_apply_funct_on_elements (hash_table_t *hashtblP, void functP(uint64_t keyP, void* dataP, void* parameterP), void* parameterP)
//-------------------------------------------------------------------------------------------------------------------------------
{
	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;
}
//-------------------------------------------------------------------------------------------------------------------------------
/*
 * 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)
{
	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;
}
//-------------------------------------------------------------------------------------------------------------------------------
/*
 * 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)
{
	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;
}
//-------------------------------------------------------------------------------------------------------------------------------
/*
 * 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)
{
	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;
/*	fprintf(stderr, "hashtable_get() key=%s, hash=%d\n", key, hash);*/

	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;
}
//-------------------------------------------------------------------------------------------------------------------------------
/*
 * 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)
{
	hash_table_t       newtbl;
	hash_size_t        n;
	hash_node_t       *node,*next;

	if (hashtblP == NULL) {
		return HASH_TABLE_BAD_PARAMETER_HASHTABLE;
	}

	newtbl.size     = sizeP;
	newtbl.hashfunc = hashtblP->hashfunc;

	if(!(newtbl.nodes=calloc(sizeP, sizeof(hash_node_t*)))) return -1;

	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);

		}
	}

	free(hashtblP->nodes);
	hashtblP->size=newtbl.size;
	hashtblP->nodes=newtbl.nodes;

	return HASH_TABLE_OK;
}