Line data Source code
1 : /*
2 : * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
3 : *
4 : * Redistribution and use in source and binary forms, with or without
5 : * modification, are permitted provided that the following conditions
6 : * are met:
7 : *
8 : * 1. Redistributions of source code must retain the above copyright
9 : * notice, this list of conditions and the following disclaimer.
10 : *
11 : * 2. Redistributions in binary form must reproduce the above copyright
12 : * notice, this list of conditions and the following disclaimer in the
13 : * documentation and/or other materials provided with the distribution.
14 : *
15 : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
16 : * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 : * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
19 : * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
20 : * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
21 : * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
22 : * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
23 : * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
24 : * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
25 : * POSSIBILITY OF SUCH DAMAGE.
26 : */
27 :
28 : #include "tommyhashtbl.h"
29 : #include "tommylist.h"
30 :
31 : #include <string.h> /* for memset */
32 :
33 : /******************************************************************************/
34 : /* hashtable */
35 :
36 5065 : void tommy_hashtable_init(tommy_hashtable* hashtable, tommy_size_t bucket_max)
37 : {
38 5065 : if (bucket_max < 16)
39 1 : bucket_max = 16;
40 : else
41 5064 : bucket_max = tommy_roundup_pow2(bucket_max);
42 :
43 5065 : hashtable->bucket_max = bucket_max;
44 5065 : hashtable->bucket_mask = hashtable->bucket_max - 1;
45 :
46 : /* initialize the vector using malloc()+memset() instead of calloc() */
47 : /* to ensure that all the memory in really allocated immediately */
48 : /* by the OS, and not deferred at later time. */
49 : /* this improves performance, because we start with a fully initialized hashtable. */
50 5065 : hashtable->bucket = tommy_cast(tommy_hashtable_node**, tommy_malloc(hashtable->bucket_max * sizeof(tommy_hashtable_node*)));
51 5065 : memset(hashtable->bucket, 0, hashtable->bucket_max * sizeof(tommy_hashtable_node*));
52 :
53 5065 : hashtable->count = 0;
54 5065 : }
55 :
56 5065 : void tommy_hashtable_done(tommy_hashtable* hashtable)
57 : {
58 5065 : tommy_free(hashtable->bucket);
59 5065 : }
60 :
61 76497500 : void tommy_hashtable_insert(tommy_hashtable* hashtable, tommy_hashtable_node* node, void* data, tommy_hash_t hash)
62 : {
63 76497500 : tommy_size_t pos = hash & hashtable->bucket_mask;
64 :
65 76497500 : tommy_list_insert_tail(&hashtable->bucket[pos], node, data);
66 :
67 76497500 : node->index = hash;
68 :
69 76497500 : ++hashtable->count;
70 76497500 : }
71 :
72 68745609 : void* tommy_hashtable_remove_existing(tommy_hashtable* hashtable, tommy_hashtable_node* node)
73 : {
74 68745609 : tommy_size_t pos = node->index & hashtable->bucket_mask;
75 :
76 68745609 : tommy_list_remove_existing(&hashtable->bucket[pos], node);
77 :
78 68745609 : --hashtable->count;
79 :
80 68745609 : return node->data;
81 : }
82 :
83 14496891 : void* tommy_hashtable_remove(tommy_hashtable* hashtable, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash)
84 : {
85 14496891 : tommy_size_t pos = hash & hashtable->bucket_mask;
86 14496891 : tommy_hashtable_node* node = hashtable->bucket[pos];
87 :
88 30651938 : while (node) {
89 : /* we first check if the hash matches, as in the same bucket we may have multiples hash values */
90 9407547 : if (node->index == hash && cmp(cmp_arg, node->data) == 0) {
91 7749391 : tommy_list_remove_existing(&hashtable->bucket[pos], node);
92 :
93 7749391 : --hashtable->count;
94 :
95 7749391 : return node->data;
96 : }
97 1658156 : node = node->next;
98 : }
99 :
100 6747500 : return 0;
101 : }
102 :
103 5001 : void tommy_hashtable_foreach(tommy_hashtable* hashtable, tommy_foreach_func* func)
104 : {
105 5001 : tommy_size_t bucket_max = hashtable->bucket_max;
106 5001 : tommy_hashtable_node** bucket = hashtable->bucket;
107 : tommy_size_t pos;
108 :
109 21009289 : for (pos = 0; pos < bucket_max; ++pos) {
110 21004288 : tommy_hashtable_node* node = bucket[pos];
111 :
112 55506076 : while (node) {
113 13497500 : void* data = node->data;
114 13497500 : node = node->next;
115 13497500 : func(data);
116 : }
117 : }
118 5001 : }
119 :
120 63 : void tommy_hashtable_foreach_arg(tommy_hashtable* hashtable, tommy_foreach_arg_func* func, void* arg)
121 : {
122 63 : tommy_size_t bucket_max = hashtable->bucket_max;
123 63 : tommy_hashtable_node** bucket = hashtable->bucket;
124 : tommy_size_t pos;
125 :
126 526335 : for (pos = 0; pos < bucket_max; ++pos) {
127 526272 : tommy_hashtable_node* node = bucket[pos];
128 :
129 2054435 : while (node) {
130 1001891 : void* data = node->data;
131 1001891 : node = node->next;
132 1001891 : func(arg, data);
133 : }
134 : }
135 63 : }
136 :
137 5001 : tommy_size_t tommy_hashtable_memory_usage(tommy_hashtable* hashtable)
138 : {
139 10002 : return hashtable->bucket_max * (tommy_size_t)sizeof(hashtable->bucket[0])
140 5001 : + tommy_hashtable_count(hashtable) * (tommy_size_t)sizeof(tommy_hashtable_node);
141 : }
142 :
|
