diff options
Diffstat (limited to 'libraries/eina/src/tests/ecore_hash.c')
-rw-r--r-- | libraries/eina/src/tests/ecore_hash.c | 949 |
1 files changed, 949 insertions, 0 deletions
diff --git a/libraries/eina/src/tests/ecore_hash.c b/libraries/eina/src/tests/ecore_hash.c new file mode 100644 index 0000000..f957d52 --- /dev/null +++ b/libraries/eina/src/tests/ecore_hash.c | |||
@@ -0,0 +1,949 @@ | |||
1 | #ifdef HAVE_CONFIG_H | ||
2 | # include <config.h> | ||
3 | #endif | ||
4 | |||
5 | #include <stdlib.h> | ||
6 | #include <stdio.h> | ||
7 | #include <string.h> | ||
8 | |||
9 | #include "Ecore_Data.h" | ||
10 | |||
11 | #define PRIME_TABLE_MAX 21 | ||
12 | #define PRIME_MIN 17 | ||
13 | #define PRIME_MAX 16777213 | ||
14 | |||
15 | #define ECORE_HASH_CHAIN_MAX 3 | ||
16 | |||
17 | #define ECORE_COMPUTE_HASH(hash, key) hash->hash_func(key) % \ | ||
18 | ecore_prime_table[hash->size]; | ||
19 | |||
20 | #define ECORE_HASH_INCREASE(hash) ((hash && ecore_prime_table[hash->size] < \ | ||
21 | PRIME_MAX) ? \ | ||
22 | (hash->nodes / \ | ||
23 | ecore_prime_table[hash->size]) > \ | ||
24 | ECORE_HASH_CHAIN_MAX : FALSE) | ||
25 | #define ECORE_HASH_REDUCE(hash) ((hash && ecore_prime_table[hash->size] > \ | ||
26 | PRIME_MIN) ? \ | ||
27 | (double)hash->nodes / \ | ||
28 | (double)ecore_prime_table[hash->size - 1] \ | ||
29 | < ((double)ECORE_HASH_CHAIN_MAX * \ | ||
30 | 0.375) : FALSE) | ||
31 | |||
32 | |||
33 | static const unsigned int ecore_prime_table[] = | ||
34 | { | ||
35 | 17, 31, 61, 127, 257, 509, 1021, | ||
36 | 2053, 4093, 8191, 16381, 32771, 65537, 131071, 262147, 524287, 1048573, | ||
37 | 2097143, 4194301, 8388617, 16777213 | ||
38 | }; | ||
39 | |||
40 | |||
41 | /* Private hash manipulation functions */ | ||
42 | static int _ecore_hash_node_add(Ecore_Hash *hash, | ||
43 | Ecore_Hash_Node *node); | ||
44 | static Ecore_Hash_Node * _ecore_hash_node_get(Ecore_Hash *hash, | ||
45 | const void *key); | ||
46 | static int _ecore_hash_increase(Ecore_Hash *hash); | ||
47 | static int _ecore_hash_decrease(Ecore_Hash *hash); | ||
48 | static inline int _ecore_hash_rehash(Ecore_Hash *hash, | ||
49 | Ecore_Hash_Node **old_table, | ||
50 | int old_size); | ||
51 | static int _ecore_hash_bucket_destroy(Ecore_Hash_Node *list, | ||
52 | Ecore_Free_Cb keyd, | ||
53 | Ecore_Free_Cb valued); | ||
54 | static inline Ecore_Hash_Node *_ecore_hash_bucket_get(Ecore_Hash *hash, | ||
55 | Ecore_Hash_Node *bucket, | ||
56 | const void *key); | ||
57 | |||
58 | static Ecore_Hash_Node * _ecore_hash_node_new(void *key, void *value); | ||
59 | static int _ecore_hash_node_init(Ecore_Hash_Node *node, | ||
60 | void *key, | ||
61 | void *value); | ||
62 | static int _ecore_hash_node_destroy(Ecore_Hash_Node *node, | ||
63 | Ecore_Free_Cb keyd, | ||
64 | Ecore_Free_Cb valued); | ||
65 | |||
66 | /** | ||
67 | * @defgroup Ecore_Data_Hash_ADT_Creation_Group Hash Creation Functions | ||
68 | * | ||
69 | * Functions that create hash tables. | ||
70 | */ | ||
71 | |||
72 | /** | ||
73 | * Creates and initializes a new hash | ||
74 | * @param hash_func The function for determining hash position. | ||
75 | * @param compare The function for comparing node keys. | ||
76 | * @return @c NULL on error, a new hash on success. | ||
77 | * @ingroup Ecore_Data_Hash_ADT_Creation_Group | ||
78 | */ | ||
79 | EAPI Ecore_Hash * | ||
80 | ecore_hash_new(Ecore_Hash_Cb hash_func, Ecore_Compare_Cb compare) | ||
81 | { | ||
82 | Ecore_Hash *new_hash = (Ecore_Hash *)malloc(sizeof(Ecore_Hash)); | ||
83 | if (!new_hash) | ||
84 | return NULL; | ||
85 | |||
86 | if (!ecore_hash_init(new_hash, hash_func, compare)) | ||
87 | { | ||
88 | FREE(new_hash); | ||
89 | return NULL; | ||
90 | } | ||
91 | |||
92 | return new_hash; | ||
93 | } | ||
94 | |||
95 | /** | ||
96 | * Initializes the given hash. | ||
97 | * @param hash The given hash. | ||
98 | * @param hash_func The function used for hashing node keys. | ||
99 | * @param compare The function used for comparing node keys. | ||
100 | * @return @c TRUE on success, @c FALSE on an error. | ||
101 | * @ingroup Ecore_Data_Hash_ADT_Creation_Group | ||
102 | */ | ||
103 | EAPI int | ||
104 | ecore_hash_init(Ecore_Hash *hash, | ||
105 | Ecore_Hash_Cb hash_func, | ||
106 | Ecore_Compare_Cb compare) | ||
107 | { | ||
108 | CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE); | ||
109 | |||
110 | memset(hash, 0, sizeof(Ecore_Hash)); | ||
111 | |||
112 | hash->hash_func = hash_func; | ||
113 | hash->compare = compare; | ||
114 | |||
115 | hash->buckets = (Ecore_Hash_Node **)calloc(ecore_prime_table[0], | ||
116 | sizeof(Ecore_Hash_Node *)); | ||
117 | |||
118 | return TRUE; | ||
119 | } | ||
120 | |||
121 | /** | ||
122 | * @defgroup Ecore_Data_Hash_ADT_Destruction_Group Hash Destruction Functions | ||
123 | * | ||
124 | * Functions that destroy hash tables and their contents. | ||
125 | */ | ||
126 | |||
127 | /** | ||
128 | * Sets the function to destroy the keys of the given hash. | ||
129 | * @param hash The given hash. | ||
130 | * @param function The function used to free the node keys. NULL is a | ||
131 | * valid value and means that no function will be called. | ||
132 | * @return @c TRUE on success, @c FALSE on error. | ||
133 | * @ingroup Ecore_Data_Hash_ADT_Destruction_Group | ||
134 | */ | ||
135 | EAPI int | ||
136 | ecore_hash_free_key_cb_set(Ecore_Hash *hash, Ecore_Free_Cb function) | ||
137 | { | ||
138 | CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE); | ||
139 | |||
140 | hash->free_key = function; | ||
141 | |||
142 | return TRUE; | ||
143 | } | ||
144 | |||
145 | /** | ||
146 | * Sets the function to destroy the values in the given hash. | ||
147 | * @param hash The given hash. | ||
148 | * @param function The function that will free the node values. NULL is a | ||
149 | * valid value and means that no function will be called. | ||
150 | * @return @c TRUE on success, @c FALSE on error | ||
151 | * @ingroup Ecore_Data_Hash_ADT_Destruction_Group | ||
152 | */ | ||
153 | EAPI int | ||
154 | ecore_hash_free_value_cb_set(Ecore_Hash *hash, Ecore_Free_Cb function) | ||
155 | { | ||
156 | CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE); | ||
157 | |||
158 | hash->free_value = function; | ||
159 | |||
160 | return TRUE; | ||
161 | } | ||
162 | |||
163 | /** | ||
164 | * @defgroup Ecore_Data_Hash_ADT_Data_Group Hash Data Functions | ||
165 | * | ||
166 | * Functions that set, access and delete values from the hash tables. | ||
167 | */ | ||
168 | |||
169 | /** | ||
170 | * Sets a key-value pair in the given hash table. | ||
171 | * @param hash The given hash table. | ||
172 | * @param key The key. | ||
173 | * @param value The value. | ||
174 | * @return @c TRUE if successful, @c FALSE if not. | ||
175 | * @ingroup Ecore_Data_Hash_ADT_Data_Group | ||
176 | */ | ||
177 | EAPI int | ||
178 | ecore_hash_set(Ecore_Hash *hash, void *key, void *value) | ||
179 | { | ||
180 | int ret = FALSE; | ||
181 | Ecore_Hash_Node *node; | ||
182 | |||
183 | CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE); | ||
184 | |||
185 | node = _ecore_hash_node_get(hash, key); | ||
186 | if (node) | ||
187 | { | ||
188 | if (hash->free_key) | ||
189 | hash->free_key(key); | ||
190 | |||
191 | if (node->value && hash->free_value) | ||
192 | hash->free_value(node->value); | ||
193 | |||
194 | node->value = value; | ||
195 | ret = TRUE; | ||
196 | } | ||
197 | else | ||
198 | { | ||
199 | node = _ecore_hash_node_new(key, value); | ||
200 | if (node) | ||
201 | ret = _ecore_hash_node_add(hash, node); | ||
202 | } | ||
203 | |||
204 | return ret; | ||
205 | } | ||
206 | |||
207 | /** | ||
208 | * Sets all key-value pairs from set in the given hash table. | ||
209 | * @param hash The given hash table. | ||
210 | * @param set The hash table to import. | ||
211 | * @return @c TRUE if successful, @c FALSE if not. | ||
212 | * @ingroup Ecore_Data_Hash_ADT_Data_Group | ||
213 | */ | ||
214 | EAPI int | ||
215 | ecore_hash_hash_set(Ecore_Hash *hash, Ecore_Hash *set) | ||
216 | { | ||
217 | unsigned int i; | ||
218 | Ecore_Hash_Node *node, *old; | ||
219 | |||
220 | CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE); | ||
221 | CHECK_PARAM_POINTER_RETURN("set", set, FALSE); | ||
222 | |||
223 | for (i = 0; i < ecore_prime_table[set->size]; i++) | ||
224 | { | ||
225 | /* Hash into a new list to avoid loops of rehashing the same nodes */ | ||
226 | while ((old = set->buckets[i])) | ||
227 | { | ||
228 | set->buckets[i] = old->next; | ||
229 | old->next = NULL; | ||
230 | node = _ecore_hash_node_get(hash, old->key); | ||
231 | if (node) | ||
232 | { | ||
233 | /* This key already exists. Delete the old and add the new | ||
234 | * value */ | ||
235 | if (hash->free_key) | ||
236 | hash->free_key(node->key); | ||
237 | |||
238 | if (hash->free_value) | ||
239 | hash->free_key(node->value); | ||
240 | |||
241 | node->key = old->key; | ||
242 | node->value = old->value; | ||
243 | free(old); | ||
244 | } | ||
245 | else | ||
246 | _ecore_hash_node_add(hash, old); | ||
247 | } | ||
248 | } | ||
249 | FREE(set->buckets); | ||
250 | ecore_hash_init(set, set->hash_func, set->compare); | ||
251 | return TRUE; | ||
252 | } | ||
253 | |||
254 | /** | ||
255 | * Frees the hash table and the data contained inside it. | ||
256 | * @param hash The hash table to destroy. | ||
257 | * @return @c TRUE on success, @c FALSE on error. | ||
258 | * @ingroup Ecore_Data_Hash_ADT_Destruction_Group | ||
259 | */ | ||
260 | EAPI void | ||
261 | ecore_hash_destroy(Ecore_Hash *hash) | ||
262 | { | ||
263 | unsigned int i = 0; | ||
264 | |||
265 | CHECK_PARAM_POINTER("hash", hash); | ||
266 | |||
267 | if (hash->buckets) | ||
268 | { | ||
269 | while (i < ecore_prime_table[hash->size]) | ||
270 | { | ||
271 | if (hash->buckets[i]) | ||
272 | { | ||
273 | Ecore_Hash_Node *bucket; | ||
274 | |||
275 | /* | ||
276 | * Remove the bucket list to avoid possible recursion | ||
277 | * on the free callbacks. | ||
278 | */ | ||
279 | bucket = hash->buckets[i]; | ||
280 | hash->buckets[i] = NULL; | ||
281 | _ecore_hash_bucket_destroy(bucket, | ||
282 | hash->free_key, | ||
283 | hash->free_value); | ||
284 | } | ||
285 | |||
286 | i++; | ||
287 | } | ||
288 | |||
289 | FREE(hash->buckets); | ||
290 | } | ||
291 | |||
292 | FREE(hash); | ||
293 | |||
294 | return; | ||
295 | } | ||
296 | |||
297 | /** | ||
298 | * @defgroup Ecore_Data_Hash_ADT_Traverse_Group Hash Traverse Functions | ||
299 | * | ||
300 | * Functions that iterate through hash tables. | ||
301 | */ | ||
302 | |||
303 | /** | ||
304 | * Counts the number of nodes in a hash table. | ||
305 | * @param hash The hash table to count current nodes. | ||
306 | * @return The number of nodes in the hash. | ||
307 | * @ingroup Ecore_Data_Hash_ADT_Destruction_Group | ||
308 | */ | ||
309 | EAPI int | ||
310 | ecore_hash_count(Ecore_Hash *hash) | ||
311 | { | ||
312 | CHECK_PARAM_POINTER_RETURN("hash", hash, 0); | ||
313 | |||
314 | return hash->nodes; | ||
315 | } | ||
316 | |||
317 | /** | ||
318 | * Runs the @p for_each_func function on each entry in the given hash. | ||
319 | * @param hash The given hash. | ||
320 | * @param for_each_func The function that each entry is passed to. | ||
321 | * @param user_data a pointer passed to calls of for_each_func | ||
322 | * @return TRUE on success, FALSE otherwise. | ||
323 | * @ingroup Ecore_Data_Hash_ADT_Traverse_Group | ||
324 | */ | ||
325 | EAPI int | ||
326 | ecore_hash_for_each_node(Ecore_Hash *hash, | ||
327 | Ecore_For_Each for_each_func, | ||
328 | void *user_data) | ||
329 | { | ||
330 | unsigned int i = 0; | ||
331 | |||
332 | CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE); | ||
333 | CHECK_PARAM_POINTER_RETURN("for_each_func", for_each_func, FALSE); | ||
334 | |||
335 | while (i < ecore_prime_table[hash->size]) | ||
336 | { | ||
337 | if (hash->buckets[i]) | ||
338 | { | ||
339 | Ecore_Hash_Node *node; | ||
340 | |||
341 | for (node = hash->buckets[i]; node; node = node->next) | ||
342 | { | ||
343 | for_each_func(node, user_data); | ||
344 | } | ||
345 | } | ||
346 | |||
347 | i++; | ||
348 | } | ||
349 | |||
350 | return TRUE; | ||
351 | } | ||
352 | |||
353 | /** | ||
354 | * Retrieves an ecore_list of all keys in the given hash. | ||
355 | * @param hash The given hash. | ||
356 | * @return new ecore_list on success, NULL otherwise | ||
357 | * @ingroup Ecore_Data_Hash_ADT_Traverse_Group | ||
358 | */ | ||
359 | EAPI Ecore_List * | ||
360 | ecore_hash_keys(Ecore_Hash *hash) | ||
361 | { | ||
362 | unsigned int i = 0; | ||
363 | Ecore_List *keys; | ||
364 | |||
365 | CHECK_PARAM_POINTER_RETURN("hash", hash, NULL); | ||
366 | |||
367 | keys = ecore_list_new(); | ||
368 | while (i < ecore_prime_table[hash->size]) | ||
369 | { | ||
370 | if (hash->buckets[i]) | ||
371 | { | ||
372 | Ecore_Hash_Node *node; | ||
373 | |||
374 | for (node = hash->buckets[i]; node; node = node->next) | ||
375 | { | ||
376 | ecore_list_append(keys, node->key); | ||
377 | } | ||
378 | } | ||
379 | |||
380 | i++; | ||
381 | } | ||
382 | ecore_list_first_goto(keys); | ||
383 | |||
384 | return keys; | ||
385 | } | ||
386 | |||
387 | /** | ||
388 | * Prints the distribution of the given hash table for graphing. | ||
389 | * @param hash The given hash table. | ||
390 | */ | ||
391 | EAPI void | ||
392 | ecore_hash_dump_graph(Ecore_Hash *hash) | ||
393 | { | ||
394 | unsigned int i; | ||
395 | |||
396 | for (i = 0; i < ecore_prime_table[hash->size]; i++) | ||
397 | if (hash->buckets[i]) | ||
398 | { | ||
399 | int n = 0; | ||
400 | Ecore_Hash_Node *node; | ||
401 | for (node = hash->buckets[i]; node; node = node->next) | ||
402 | n++; | ||
403 | printf("%d\t%u", i, n); | ||
404 | } | ||
405 | else | ||
406 | printf("%d\t0", i); | ||
407 | |||
408 | } | ||
409 | |||
410 | /** | ||
411 | * Prints the distribution of the given hash table for graphing. | ||
412 | * @param hash The given hash table. | ||
413 | */ | ||
414 | EAPI void | ||
415 | ecore_hash_dump_stats(Ecore_Hash *hash) | ||
416 | { | ||
417 | unsigned int i; | ||
418 | double variance, sum_n_2 = 0, sum_n = 0; | ||
419 | |||
420 | for (i = 0; i < ecore_prime_table[hash->size]; i++) | ||
421 | { | ||
422 | if (hash->buckets[i]) | ||
423 | { | ||
424 | int n = 0; | ||
425 | Ecore_Hash_Node *node; | ||
426 | for (node = hash->buckets[i]; node; node = node->next) | ||
427 | n++; | ||
428 | sum_n_2 += ((double)n * (double)n); | ||
429 | sum_n += (double)n; | ||
430 | } | ||
431 | } | ||
432 | variance = (sum_n_2 - ((sum_n * sum_n) / (double)i)) / (double)i; | ||
433 | printf("Average length: %f\n\tvariance^2: %f", (sum_n / (double)i), | ||
434 | variance); | ||
435 | } | ||
436 | |||
437 | static int | ||
438 | _ecore_hash_bucket_destroy(Ecore_Hash_Node *list, | ||
439 | Ecore_Free_Cb keyd, | ||
440 | Ecore_Free_Cb valued) | ||
441 | { | ||
442 | Ecore_Hash_Node *node; | ||
443 | |||
444 | CHECK_PARAM_POINTER_RETURN("list", list, FALSE); | ||
445 | |||
446 | for (node = list; node; node = list) | ||
447 | { | ||
448 | list = list->next; | ||
449 | _ecore_hash_node_destroy(node, keyd, valued); | ||
450 | } | ||
451 | |||
452 | return TRUE; | ||
453 | } | ||
454 | |||
455 | /* | ||
456 | * @brief Add the node to the hash table | ||
457 | * @param hash: the hash table to add the key | ||
458 | * @param node: the node to add to the hash table | ||
459 | * @return Returns FALSE on error, TRUE on success | ||
460 | */ | ||
461 | static int | ||
462 | _ecore_hash_node_add(Ecore_Hash *hash, Ecore_Hash_Node *node) | ||
463 | { | ||
464 | unsigned long hash_val; | ||
465 | |||
466 | CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE); | ||
467 | CHECK_PARAM_POINTER_RETURN("node", node, FALSE); | ||
468 | |||
469 | /* Check to see if the hash needs to be resized */ | ||
470 | if (ECORE_HASH_INCREASE(hash)) | ||
471 | _ecore_hash_increase(hash); | ||
472 | |||
473 | /* Compute the position in the table */ | ||
474 | if (!hash->hash_func) | ||
475 | hash_val = (unsigned long)node->key % ecore_prime_table[hash->size]; | ||
476 | else | ||
477 | hash_val = ECORE_COMPUTE_HASH(hash, node->key); | ||
478 | |||
479 | /* Prepend the node to the list at the index position */ | ||
480 | node->next = hash->buckets[hash_val]; | ||
481 | hash->buckets[hash_val] = node; | ||
482 | hash->nodes++; | ||
483 | |||
484 | return TRUE; | ||
485 | } | ||
486 | |||
487 | /** | ||
488 | * Retrieves the value associated with the given key from the given hash | ||
489 | * table. | ||
490 | * @param hash The given hash table. | ||
491 | * @param key The key to search for. | ||
492 | * @return The value corresponding to key on success, @c NULL otherwise. | ||
493 | * @ingroup Ecore_Data_Hash_ADT_Data_Group | ||
494 | */ | ||
495 | EAPI void * | ||
496 | ecore_hash_get(Ecore_Hash *hash, const void *key) | ||
497 | { | ||
498 | void *data; | ||
499 | Ecore_Hash_Node *node; | ||
500 | |||
501 | CHECK_PARAM_POINTER_RETURN("hash", hash, NULL); | ||
502 | |||
503 | node = _ecore_hash_node_get(hash, key); | ||
504 | if (!node) | ||
505 | return NULL; | ||
506 | |||
507 | data = node->value; | ||
508 | |||
509 | return data; | ||
510 | } | ||
511 | |||
512 | /** | ||
513 | * Removes the value associated with the given key in the given hash | ||
514 | * table. | ||
515 | * @param hash The given hash table. | ||
516 | * @param key The key to search for. | ||
517 | * @return The value corresponding to the key on success. @c NULL is | ||
518 | * returned if there is an error. | ||
519 | * @ingroup Ecore_Data_Hash_ADT_Data_Group | ||
520 | */ | ||
521 | EAPI void * | ||
522 | ecore_hash_remove(Ecore_Hash *hash, const void *key) | ||
523 | { | ||
524 | Ecore_Hash_Node *node = NULL; | ||
525 | Ecore_Hash_Node *list; | ||
526 | unsigned long hash_val; | ||
527 | void *ret = NULL; | ||
528 | |||
529 | CHECK_PARAM_POINTER_RETURN("hash", hash, NULL); | ||
530 | |||
531 | /* Compute the position in the table */ | ||
532 | if (!hash->hash_func) | ||
533 | hash_val = (unsigned long )key % ecore_prime_table[hash->size]; | ||
534 | else | ||
535 | hash_val = ECORE_COMPUTE_HASH(hash, key); | ||
536 | |||
537 | /* | ||
538 | * If their is a list that could possibly hold the key/value pair | ||
539 | * traverse it and remove the hash node. | ||
540 | */ | ||
541 | if (hash->buckets[hash_val]) | ||
542 | { | ||
543 | list = hash->buckets[hash_val]; | ||
544 | |||
545 | /* | ||
546 | * Traverse the list to find the specified key | ||
547 | */ | ||
548 | node = list; | ||
549 | if (hash->compare) | ||
550 | while ((node) && (hash->compare(node->key, key) != 0)) | ||
551 | { | ||
552 | list = node; | ||
553 | node = node->next; | ||
554 | } | ||
555 | else | ||
556 | while ((node) && (node->key != key)) | ||
557 | { | ||
558 | list = node; | ||
559 | node = node->next; | ||
560 | } | ||
561 | |||
562 | /* | ||
563 | * Remove the node with the matching key and free it's memory | ||
564 | */ | ||
565 | if (node) | ||
566 | { | ||
567 | if (list == node) | ||
568 | hash->buckets[hash_val] = node->next; | ||
569 | else | ||
570 | list->next = node->next; | ||
571 | |||
572 | ret = node->value; | ||
573 | node->value = NULL; | ||
574 | _ecore_hash_node_destroy(node, hash->free_key, NULL); | ||
575 | hash->nodes--; | ||
576 | } | ||
577 | } | ||
578 | |||
579 | if (ECORE_HASH_REDUCE(hash)) | ||
580 | _ecore_hash_decrease(hash); | ||
581 | |||
582 | return ret; | ||
583 | } | ||
584 | |||
585 | /** | ||
586 | * Retrieves the first value that matches | ||
587 | * table. | ||
588 | * @param hash The given hash table. | ||
589 | * @param key The key to search for. | ||
590 | * @return The value corresponding to key on success, @c NULL otherwise. | ||
591 | * @ingroup Ecore_Data_Hash_ADT_Data_Group | ||
592 | */ | ||
593 | EAPI void * | ||
594 | ecore_hash_find(Ecore_Hash *hash, Ecore_Compare_Cb compare, const void *value) | ||
595 | { | ||
596 | unsigned int i = 0; | ||
597 | |||
598 | CHECK_PARAM_POINTER_RETURN("hash", hash, NULL); | ||
599 | CHECK_PARAM_POINTER_RETURN("compare", compare, NULL); | ||
600 | CHECK_PARAM_POINTER_RETURN("value", value, NULL); | ||
601 | |||
602 | while (i < ecore_prime_table[hash->size]) | ||
603 | { | ||
604 | if (hash->buckets[i]) | ||
605 | { | ||
606 | Ecore_Hash_Node *node; | ||
607 | |||
608 | for (node = hash->buckets[i]; node; node = node->next) | ||
609 | { | ||
610 | if (!compare(node->value, value)) | ||
611 | return node->value; | ||
612 | } | ||
613 | } | ||
614 | |||
615 | i++; | ||
616 | } | ||
617 | |||
618 | return NULL; | ||
619 | } | ||
620 | |||
621 | /* | ||
622 | * @brief Retrieve the node associated with key | ||
623 | * @param hash: the hash table to search for the key | ||
624 | * @param key: the key to search for in the hash table | ||
625 | * @return Returns NULL on error, node corresponding to key on success | ||
626 | */ | ||
627 | static Ecore_Hash_Node * | ||
628 | _ecore_hash_node_get(Ecore_Hash *hash, const void *key) | ||
629 | { | ||
630 | unsigned long hash_val; | ||
631 | Ecore_Hash_Node *node = NULL; | ||
632 | |||
633 | CHECK_PARAM_POINTER_RETURN("hash", hash, NULL); | ||
634 | |||
635 | if (!hash->buckets) | ||
636 | return NULL; | ||
637 | |||
638 | /* Compute the position in the table */ | ||
639 | if (!hash->hash_func) | ||
640 | hash_val = (unsigned long)key % ecore_prime_table[hash->size]; | ||
641 | else | ||
642 | hash_val = ECORE_COMPUTE_HASH(hash, key); | ||
643 | |||
644 | /* Grab the bucket at the specified position */ | ||
645 | if (hash->buckets[hash_val]) | ||
646 | { | ||
647 | node = _ecore_hash_bucket_get(hash, hash->buckets[hash_val], key); | ||
648 | /* | ||
649 | * Move matched node to the front of the list as it's likely | ||
650 | * to be searched for again soon. | ||
651 | */ | ||
652 | if (node && node != hash->buckets[hash_val]) | ||
653 | { | ||
654 | node->next = hash->buckets[hash_val]; | ||
655 | hash->buckets[hash_val] = node; | ||
656 | } | ||
657 | } | ||
658 | |||
659 | return node; | ||
660 | } | ||
661 | |||
662 | /* | ||
663 | * @brief Search the hash bucket for a specified key | ||
664 | * @param hash: the hash table to retrieve the comparison function | ||
665 | * @param bucket: the list to search for the key | ||
666 | * @param key: the key to search for in the list | ||
667 | * @return Returns NULL on error or not found, the found node on success | ||
668 | */ | ||
669 | static inline Ecore_Hash_Node * | ||
670 | _ecore_hash_bucket_get(Ecore_Hash *hash, | ||
671 | Ecore_Hash_Node *bucket, | ||
672 | const void *key) | ||
673 | { | ||
674 | Ecore_Hash_Node *prev = NULL; | ||
675 | Ecore_Hash_Node *node = NULL; | ||
676 | |||
677 | /* | ||
678 | * Traverse the list to find the desired node, if the node is in the | ||
679 | * list, then return the node. | ||
680 | */ | ||
681 | if (hash->compare) | ||
682 | for (node = bucket; node; node = node->next) | ||
683 | { | ||
684 | if (hash->compare(node->key, key) == 0) | ||
685 | break; | ||
686 | |||
687 | prev = node; | ||
688 | } | ||
689 | else | ||
690 | for (node = bucket; node; node = node->next) | ||
691 | { | ||
692 | if (node->key == key) | ||
693 | break; | ||
694 | |||
695 | prev = node; | ||
696 | } | ||
697 | |||
698 | /* | ||
699 | * Remove node from the list to replace it at the beginning. | ||
700 | */ | ||
701 | if (node && prev) | ||
702 | { | ||
703 | prev->next = node->next; | ||
704 | node->next = NULL; | ||
705 | } | ||
706 | |||
707 | return node; | ||
708 | } | ||
709 | |||
710 | /* | ||
711 | * @brief Increase the size of the hash table by approx. 2 * current size | ||
712 | * @param hash: the hash table to increase the size of | ||
713 | * @return Returns TRUE on success, FALSE on error | ||
714 | */ | ||
715 | static int | ||
716 | _ecore_hash_increase(Ecore_Hash *hash) | ||
717 | { | ||
718 | void *old; | ||
719 | |||
720 | CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE); | ||
721 | |||
722 | /* Max size reached so return FALSE */ | ||
723 | if ((ecore_prime_table[hash->size] == PRIME_MAX) || | ||
724 | (hash->size == PRIME_TABLE_MAX)) | ||
725 | return FALSE; | ||
726 | |||
727 | /* | ||
728 | * Increase the size of the hash and save a pointer to the old data | ||
729 | */ | ||
730 | hash->size++; | ||
731 | old = hash->buckets; | ||
732 | |||
733 | /* | ||
734 | * Allocate a new bucket area, of the new larger size | ||
735 | */ | ||
736 | hash->buckets = | ||
737 | calloc(ecore_prime_table[hash->size], sizeof(Ecore_Hash_Node *)); | ||
738 | |||
739 | /* | ||
740 | * Make sure the allocation succeeded, if not replace the old data and | ||
741 | * return a failure. | ||
742 | */ | ||
743 | if (!hash->buckets) | ||
744 | { | ||
745 | hash->buckets = old; | ||
746 | hash->size--; | ||
747 | return FALSE; | ||
748 | } | ||
749 | |||
750 | hash->nodes = 0; | ||
751 | |||
752 | /* | ||
753 | * Now move all of the old data into the new bucket area | ||
754 | */ | ||
755 | if (_ecore_hash_rehash(hash, old, hash->size - 1)) | ||
756 | { | ||
757 | FREE(old); | ||
758 | return TRUE; | ||
759 | } | ||
760 | |||
761 | /* | ||
762 | * Free the old buckets regardless of success. | ||
763 | */ | ||
764 | FREE(old); | ||
765 | |||
766 | return FALSE; | ||
767 | } | ||
768 | |||
769 | /* | ||
770 | * @brief Decrease the size of the hash table by < 1/2 * current size | ||
771 | * @param hash: the hash table to decrease the size of | ||
772 | * @return Returns TRUE on success, FALSE on error | ||
773 | */ | ||
774 | static int | ||
775 | _ecore_hash_decrease(Ecore_Hash *hash) | ||
776 | { | ||
777 | Ecore_Hash_Node **old; | ||
778 | |||
779 | CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE); | ||
780 | |||
781 | if (ecore_prime_table[hash->size] == PRIME_MIN) | ||
782 | return FALSE; | ||
783 | |||
784 | /* | ||
785 | * Decrease the hash size and store a pointer to the old data | ||
786 | */ | ||
787 | hash->size--; | ||
788 | old = hash->buckets; | ||
789 | |||
790 | /* | ||
791 | * Allocate a new area to store the data | ||
792 | */ | ||
793 | hash->buckets = (Ecore_Hash_Node **)calloc(ecore_prime_table[hash->size], | ||
794 | sizeof(Ecore_Hash_Node *)); | ||
795 | |||
796 | /* | ||
797 | * Make sure allocation succeeded otherwise rreturn to the previous | ||
798 | * state | ||
799 | */ | ||
800 | if (!hash->buckets) | ||
801 | { | ||
802 | hash->buckets = old; | ||
803 | hash->size++; | ||
804 | return FALSE; | ||
805 | } | ||
806 | |||
807 | hash->nodes = 0; | ||
808 | |||
809 | if (_ecore_hash_rehash(hash, old, hash->size + 1)) | ||
810 | { | ||
811 | FREE(old); | ||
812 | return TRUE; | ||
813 | } | ||
814 | |||
815 | return FALSE; | ||
816 | } | ||
817 | |||
818 | /* | ||
819 | * @brief Rehash the nodes of a table into the hash table | ||
820 | * @param hash: the hash to place the nodes of the table | ||
821 | * @param table: the table to remove the nodes from and place in hash | ||
822 | * @return Returns TRUE on success, FALSE on error | ||
823 | */ | ||
824 | static inline int | ||
825 | _ecore_hash_rehash(Ecore_Hash *hash, Ecore_Hash_Node **old_table, int old_size) | ||
826 | { | ||
827 | unsigned int i; | ||
828 | Ecore_Hash_Node *old; | ||
829 | |||
830 | CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE); | ||
831 | CHECK_PARAM_POINTER_RETURN("old_table", old_table, FALSE); | ||
832 | |||
833 | for (i = 0; i < ecore_prime_table[old_size]; i++) | ||
834 | { | ||
835 | /* Hash into a new list to avoid loops of rehashing the same nodes */ | ||
836 | while ((old = old_table[i])) | ||
837 | { | ||
838 | old_table[i] = old->next; | ||
839 | old->next = NULL; | ||
840 | _ecore_hash_node_add(hash, old); | ||
841 | } | ||
842 | } | ||
843 | |||
844 | return TRUE; | ||
845 | } | ||
846 | |||
847 | /* | ||
848 | * @brief Create a new hash node for key and value storage | ||
849 | * @param key: the key for this node | ||
850 | * @param value: the value that the key references | ||
851 | * @return Returns NULL on error, a new hash node on success | ||
852 | */ | ||
853 | static Ecore_Hash_Node * | ||
854 | _ecore_hash_node_new(void *key, void *value) | ||
855 | { | ||
856 | Ecore_Hash_Node *node; | ||
857 | |||
858 | node = (Ecore_Hash_Node *)malloc(sizeof(Ecore_Hash_Node)); | ||
859 | if (!node) | ||
860 | return NULL; | ||
861 | |||
862 | if (!_ecore_hash_node_init(node, key, value)) | ||
863 | { | ||
864 | FREE(node); | ||
865 | return NULL; | ||
866 | } | ||
867 | |||
868 | return node; | ||
869 | } | ||
870 | |||
871 | /* | ||
872 | * @brief Initialize a hash node to some sane default values | ||
873 | * @param node: the node to set the values | ||
874 | * @param key: the key to reference this node | ||
875 | * @param value: the value that key refers to | ||
876 | * @return Returns TRUE on success, FALSE on error | ||
877 | */ | ||
878 | static int | ||
879 | _ecore_hash_node_init(Ecore_Hash_Node *node, void *key, void *value) | ||
880 | { | ||
881 | CHECK_PARAM_POINTER_RETURN("node", node, FALSE); | ||
882 | |||
883 | node->key = key; | ||
884 | node->value = value; | ||
885 | |||
886 | return TRUE; | ||
887 | } | ||
888 | |||
889 | /* | ||
890 | * @brief Destroy a node and call the specified callbacks to free data | ||
891 | * @param node: the node to be destroyed | ||
892 | * @param keyd: the function to free the key | ||
893 | * @param valued: the function to free the value | ||
894 | * @return Returns TRUE on success, FALSE on error | ||
895 | */ | ||
896 | static int | ||
897 | _ecore_hash_node_destroy(Ecore_Hash_Node *node, | ||
898 | Ecore_Free_Cb keyd, | ||
899 | Ecore_Free_Cb valued) | ||
900 | { | ||
901 | CHECK_PARAM_POINTER_RETURN("node", node, FALSE); | ||
902 | |||
903 | if (keyd) | ||
904 | keyd(node->key); | ||
905 | |||
906 | if (valued) | ||
907 | valued(node->value); | ||
908 | |||
909 | FREE(node); | ||
910 | |||
911 | return TRUE; | ||
912 | } | ||
913 | |||
914 | int | ||
915 | ecore_str_compare(const void *key1, const void *key2) | ||
916 | { | ||
917 | const char *k1, *k2; | ||
918 | |||
919 | if (!key1 || !key2) | ||
920 | return ecore_direct_compare(key1, key2); | ||
921 | else if (key1 == key2) | ||
922 | return 0; | ||
923 | |||
924 | k1 = key1; | ||
925 | k2 = key2; | ||
926 | |||
927 | return strcmp(k1, k2); | ||
928 | } | ||
929 | |||
930 | unsigned int | ||
931 | ecore_str_hash(const void *key) | ||
932 | { | ||
933 | int i; | ||
934 | unsigned int mask; | ||
935 | unsigned int value = 0; | ||
936 | const char *k = key; | ||
937 | |||
938 | if (!k) | ||
939 | return 0; | ||
940 | |||
941 | mask = (sizeof(unsigned int) * 8) - 1; | ||
942 | |||
943 | for (i = 0; k[i] != '\0'; i++) | ||
944 | { | ||
945 | value ^= ((unsigned int)k[i] << ((i * 5) & mask)); | ||
946 | } | ||
947 | |||
948 | return value; | ||
949 | } | ||