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 "tommyhashdyn.h"
29 : #include "tommylist.h"
30 :
31 : /******************************************************************************/
32 : /* hashdyn */
33 :
34 8763 : void tommy_hashdyn_init(tommy_hashdyn* hashdyn)
35 : {
36 : /* fixed initial size */
37 8763 : hashdyn->bucket_bit = TOMMY_HASHDYN_BIT;
38 8763 : hashdyn->bucket_max = 1 << hashdyn->bucket_bit;
39 8763 : hashdyn->bucket_mask = hashdyn->bucket_max - 1;
40 8763 : hashdyn->bucket = tommy_cast(tommy_hashdyn_node**, tommy_calloc(hashdyn->bucket_max, sizeof(tommy_hashdyn_node*)));
41 :
42 8763 : hashdyn->count = 0;
43 8763 : }
44 :
45 8034 : void tommy_hashdyn_done(tommy_hashdyn* hashdyn)
46 : {
47 8034 : tommy_free(hashdyn->bucket);
48 8034 : }
49 :
50 : /**
51 : * Resize the bucket vector.
52 : */
53 41539 : static void tommy_hashdyn_resize(tommy_hashdyn* hashdyn, tommy_count_t new_bucket_bit)
54 : {
55 : tommy_count_t bucket_bit;
56 : tommy_count_t bucket_max;
57 : tommy_count_t new_bucket_max;
58 : tommy_count_t new_bucket_mask;
59 : tommy_hashdyn_node** new_bucket;
60 :
61 41539 : bucket_bit = hashdyn->bucket_bit;
62 41539 : bucket_max = hashdyn->bucket_max;
63 :
64 41539 : new_bucket_max = 1 << new_bucket_bit;
65 41539 : new_bucket_mask = new_bucket_max - 1;
66 :
67 : /* allocate the new vector using malloc() and not calloc() */
68 : /* because data is fully initialized in the update process */
69 41539 : new_bucket = tommy_cast(tommy_hashdyn_node**, tommy_malloc(new_bucket_max * sizeof(tommy_hashdyn_node*)));
70 :
71 : /* reinsert all the elements */
72 41539 : if (new_bucket_bit > bucket_bit) {
73 : tommy_count_t i;
74 :
75 : /* grow */
76 32211884 : for (i = 0; i < bucket_max; ++i) {
77 : tommy_hashdyn_node* j;
78 :
79 : /* setup the new two buckets */
80 32170400 : new_bucket[i] = 0;
81 32170400 : new_bucket[i + bucket_max] = 0;
82 :
83 : /* reinsert the bucket */
84 32170400 : j = hashdyn->bucket[i];
85 80426000 : while (j) {
86 16085200 : tommy_hashdyn_node* j_next = j->next;
87 16085200 : tommy_count_t pos = j->key & new_bucket_mask;
88 16085200 : if (new_bucket[pos])
89 1888367 : tommy_list_insert_tail_not_empty(new_bucket[pos], j);
90 : else
91 14196833 : tommy_list_insert_first(&new_bucket[pos], j);
92 16085200 : j = j_next;
93 : }
94 : }
95 : } else {
96 : tommy_count_t i;
97 :
98 : /* shrink */
99 79335 : for (i = 0; i < new_bucket_max; ++i) {
100 : /* setup the new bucket with the lower bucket*/
101 79280 : new_bucket[i] = hashdyn->bucket[i];
102 :
103 : /* concat the upper bucket */
104 79280 : tommy_list_concat(&new_bucket[i], &hashdyn->bucket[i + new_bucket_max]);
105 : }
106 : }
107 :
108 41539 : tommy_free(hashdyn->bucket);
109 :
110 : /* setup */
111 41539 : hashdyn->bucket_bit = new_bucket_bit;
112 41539 : hashdyn->bucket_max = new_bucket_max;
113 41539 : hashdyn->bucket_mask = new_bucket_mask;
114 41539 : hashdyn->bucket = new_bucket;
115 41539 : }
116 :
117 : /**
118 : * Grow.
119 : */
120 13249747 : tommy_inline void hashdyn_grow_step(tommy_hashdyn* hashdyn)
121 : {
122 : /* grow if more than 50% full */
123 13249747 : if (hashdyn->count >= hashdyn->bucket_max / 2)
124 41484 : tommy_hashdyn_resize(hashdyn, hashdyn->bucket_bit + 1);
125 13249747 : }
126 :
127 : /**
128 : * Shrink.
129 : */
130 295446 : tommy_inline void hashdyn_shrink_step(tommy_hashdyn* hashdyn)
131 : {
132 : /* shrink if less than 12.5% full */
133 295446 : if (hashdyn->count <= hashdyn->bucket_max / 8 && hashdyn->bucket_bit > TOMMY_HASHDYN_BIT)
134 55 : tommy_hashdyn_resize(hashdyn, hashdyn->bucket_bit - 1);
135 295446 : }
136 :
137 13249747 : void tommy_hashdyn_insert(tommy_hashdyn* hashdyn, tommy_hashdyn_node* node, void* data, tommy_hash_t hash)
138 : {
139 13249747 : tommy_count_t pos = hash & hashdyn->bucket_mask;
140 :
141 13249747 : tommy_list_insert_tail(&hashdyn->bucket[pos], node, data);
142 :
143 13249747 : node->key = hash;
144 :
145 13249747 : ++hashdyn->count;
146 :
147 13249747 : hashdyn_grow_step(hashdyn);
148 13249747 : }
149 :
150 295318 : void* tommy_hashdyn_remove_existing(tommy_hashdyn* hashdyn, tommy_hashdyn_node* node)
151 : {
152 295318 : tommy_count_t pos = node->key & hashdyn->bucket_mask;
153 :
154 295318 : tommy_list_remove_existing(&hashdyn->bucket[pos], node);
155 :
156 295318 : --hashdyn->count;
157 :
158 295318 : hashdyn_shrink_step(hashdyn);
159 :
160 295318 : return node->data;
161 : }
162 :
163 256 : void* tommy_hashdyn_remove(tommy_hashdyn* hashdyn, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash)
164 : {
165 256 : tommy_count_t pos = hash & hashdyn->bucket_mask;
166 256 : tommy_hashdyn_node* node = hashdyn->bucket[pos];
167 :
168 768 : while (node) {
169 : /* we first check if the hash matches, as in the same bucket we may have multiples hash values */
170 384 : if (node->key == hash && cmp(cmp_arg, node->data) == 0) {
171 128 : tommy_list_remove_existing(&hashdyn->bucket[pos], node);
172 :
173 128 : --hashdyn->count;
174 :
175 128 : hashdyn_shrink_step(hashdyn);
176 :
177 128 : return node->data;
178 : }
179 256 : node = node->next;
180 : }
181 :
182 128 : return 0;
183 : }
184 :
185 251 : void tommy_hashdyn_foreach(tommy_hashdyn* hashdyn, tommy_foreach_func* func)
186 : {
187 251 : tommy_count_t bucket_max = hashdyn->bucket_max;
188 251 : tommy_hashdyn_node** bucket = hashdyn->bucket;
189 : tommy_count_t pos;
190 :
191 5812843 : for (pos = 0; pos < bucket_max; ++pos) {
192 5812592 : tommy_hashdyn_node* node = bucket[pos];
193 :
194 13486021 : while (node) {
195 1860837 : void* data = node->data;
196 1860837 : node = node->next;
197 1860837 : func(data);
198 : }
199 : }
200 251 : }
201 :
202 4 : void tommy_hashdyn_foreach_arg(tommy_hashdyn* hashdyn, tommy_foreach_arg_func* func, void* arg)
203 : {
204 4 : tommy_count_t bucket_max = hashdyn->bucket_max;
205 4 : tommy_hashdyn_node** bucket = hashdyn->bucket;
206 : tommy_count_t pos;
207 :
208 1316 : for (pos = 0; pos < bucket_max; ++pos) {
209 1312 : tommy_hashdyn_node* node = bucket[pos];
210 :
211 2941 : while (node) {
212 317 : void* data = node->data;
213 317 : node = node->next;
214 317 : func(arg, data);
215 : }
216 : }
217 4 : }
218 :
219 1 : tommy_size_t tommy_hashdyn_memory_usage(tommy_hashdyn* hashdyn)
220 : {
221 2 : return hashdyn->bucket_max * (tommy_size_t)sizeof(hashdyn->bucket[0])
222 1 : + tommy_hashdyn_count(hashdyn) * (tommy_size_t)sizeof(tommy_hashdyn_node);
223 : }
224 :
|
