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 5064 : void tommy_hashdyn_init(tommy_hashdyn* hashdyn)
35 : {
36 : /* fixed initial size */
37 5064 : hashdyn->bucket_bit = TOMMY_HASHDYN_BIT;
38 5064 : hashdyn->bucket_max = 1 << hashdyn->bucket_bit;
39 5064 : hashdyn->bucket_mask = hashdyn->bucket_max - 1;
40 5064 : hashdyn->bucket = tommy_cast(tommy_hashdyn_node**, tommy_calloc(hashdyn->bucket_max, sizeof(tommy_hashdyn_node*)));
41 :
42 5064 : hashdyn->count = 0;
43 5064 : }
44 :
45 5064 : void tommy_hashdyn_done(tommy_hashdyn* hashdyn)
46 : {
47 5064 : tommy_free(hashdyn->bucket);
48 5064 : }
49 :
50 : /**
51 : * Resize the bucket vector.
52 : */
53 83966 : static void tommy_hashdyn_resize(tommy_hashdyn* hashdyn, tommy_size_t new_bucket_bit)
54 : {
55 : tommy_size_t bucket_bit;
56 : tommy_size_t bucket_max;
57 : tommy_size_t new_bucket_max;
58 : tommy_size_t new_bucket_mask;
59 : tommy_hashdyn_node** new_bucket;
60 :
61 83966 : bucket_bit = hashdyn->bucket_bit;
62 83966 : bucket_max = hashdyn->bucket_max;
63 :
64 83966 : new_bucket_max = 1 << new_bucket_bit;
65 83966 : 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 83966 : new_bucket = tommy_cast(tommy_hashdyn_node**, tommy_malloc(new_bucket_max * sizeof(tommy_hashdyn_node*)));
70 :
71 : /* reinsert all the elements */
72 83966 : if (new_bucket_bit > bucket_bit) {
73 : tommy_size_t i;
74 :
75 : /* grow */
76 41341423 : for (i = 0; i < bucket_max; ++i) {
77 : tommy_hashdyn_node* j;
78 :
79 : /* setup the new two buckets */
80 41299440 : new_bucket[i] = 0;
81 41299440 : new_bucket[i + bucket_max] = 0;
82 :
83 : /* reinsert the bucket */
84 41299440 : j = hashdyn->bucket[i];
85 103248600 : while (j) {
86 20649720 : tommy_hashdyn_node* j_next = j->next;
87 20649720 : tommy_size_t pos = j->index & new_bucket_mask;
88 20649720 : if (new_bucket[pos])
89 572864 : tommy_list_insert_tail_not_empty(new_bucket[pos], j);
90 : else
91 20076856 : tommy_list_insert_first(&new_bucket[pos], j);
92 20649720 : j = j_next;
93 : }
94 : }
95 : } else {
96 : tommy_size_t i;
97 :
98 : /* shrink */
99 41341423 : for (i = 0; i < new_bucket_max; ++i) {
100 : /* setup the new bucket with the lower bucket*/
101 41299440 : new_bucket[i] = hashdyn->bucket[i];
102 :
103 : /* concat the upper bucket */
104 41299440 : tommy_list_concat(&new_bucket[i], &hashdyn->bucket[i + new_bucket_max]);
105 : }
106 : }
107 :
108 83966 : tommy_free(hashdyn->bucket);
109 :
110 : /* setup */
111 83966 : hashdyn->bucket_bit = new_bucket_bit;
112 83966 : hashdyn->bucket_max = new_bucket_max;
113 83966 : hashdyn->bucket_mask = new_bucket_mask;
114 83966 : hashdyn->bucket = new_bucket;
115 83966 : }
116 :
117 : /**
118 : * Grow.
119 : */
120 76497500 : tommy_inline void hashdyn_grow_step(tommy_hashdyn* hashdyn)
121 : {
122 : /* grow if more than 50% full */
123 76497500 : if (hashdyn->count >= hashdyn->bucket_max / 2)
124 41983 : tommy_hashdyn_resize(hashdyn, hashdyn->bucket_bit + 1);
125 76497500 : }
126 :
127 : /**
128 : * Shrink.
129 : */
130 76495000 : tommy_inline void hashdyn_shrink_step(tommy_hashdyn* hashdyn)
131 : {
132 : /* shrink if less than 12.5% full */
133 76495000 : if (hashdyn->count <= hashdyn->bucket_max / 8 && hashdyn->bucket_bit > TOMMY_HASHDYN_BIT)
134 41983 : tommy_hashdyn_resize(hashdyn, hashdyn->bucket_bit - 1);
135 76495000 : }
136 :
137 76497500 : void tommy_hashdyn_insert(tommy_hashdyn* hashdyn, tommy_hashdyn_node* node, void* data, tommy_hash_t hash)
138 : {
139 76497500 : tommy_size_t pos = hash & hashdyn->bucket_mask;
140 :
141 76497500 : tommy_list_insert_tail(&hashdyn->bucket[pos], node, data);
142 :
143 76497500 : node->index = hash;
144 :
145 76497500 : ++hashdyn->count;
146 :
147 76497500 : hashdyn_grow_step(hashdyn);
148 76497500 : }
149 :
150 68745609 : void* tommy_hashdyn_remove_existing(tommy_hashdyn* hashdyn, tommy_hashdyn_node* node)
151 : {
152 68745609 : tommy_size_t pos = node->index & hashdyn->bucket_mask;
153 :
154 68745609 : tommy_list_remove_existing(&hashdyn->bucket[pos], node);
155 :
156 68745609 : --hashdyn->count;
157 :
158 68745609 : hashdyn_shrink_step(hashdyn);
159 :
160 68745609 : return node->data;
161 : }
162 :
163 14496891 : void* tommy_hashdyn_remove(tommy_hashdyn* hashdyn, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash)
164 : {
165 14496891 : tommy_size_t pos = hash & hashdyn->bucket_mask;
166 14496891 : tommy_hashdyn_node* node = hashdyn->bucket[pos];
167 :
168 30243782 : while (node) {
169 : /* we first check if the hash matches, as in the same bucket we may have multiples hash values */
170 8999391 : if (node->index == hash && cmp(cmp_arg, node->data) == 0) {
171 7749391 : tommy_list_remove_existing(&hashdyn->bucket[pos], node);
172 :
173 7749391 : --hashdyn->count;
174 :
175 7749391 : hashdyn_shrink_step(hashdyn);
176 :
177 7749391 : return node->data;
178 : }
179 1250000 : node = node->next;
180 : }
181 :
182 6747500 : return 0;
183 : }
184 :
185 5001 : void tommy_hashdyn_foreach(tommy_hashdyn* hashdyn, tommy_foreach_func* func)
186 : {
187 5001 : tommy_size_t bucket_max = hashdyn->bucket_max;
188 5001 : tommy_hashdyn_node** bucket = hashdyn->bucket;
189 : tommy_size_t pos;
190 :
191 39282953 : for (pos = 0; pos < bucket_max; ++pos) {
192 39277952 : tommy_hashdyn_node* node = bucket[pos];
193 :
194 92053404 : while (node) {
195 13497500 : void* data = node->data;
196 13497500 : node = node->next;
197 13497500 : func(data);
198 : }
199 : }
200 5001 : }
201 :
202 63 : void tommy_hashdyn_foreach_arg(tommy_hashdyn* hashdyn, tommy_foreach_arg_func* func, void* arg)
203 : {
204 63 : tommy_size_t bucket_max = hashdyn->bucket_max;
205 63 : tommy_hashdyn_node** bucket = hashdyn->bucket;
206 : tommy_size_t pos;
207 :
208 2102463 : for (pos = 0; pos < bucket_max; ++pos) {
209 2102400 : tommy_hashdyn_node* node = bucket[pos];
210 :
211 5206691 : while (node) {
212 1001891 : void* data = node->data;
213 1001891 : node = node->next;
214 1001891 : func(arg, data);
215 : }
216 : }
217 63 : }
218 :
219 5001 : tommy_size_t tommy_hashdyn_memory_usage(tommy_hashdyn* hashdyn)
220 : {
221 10002 : return hashdyn->bucket_max * (tommy_size_t)sizeof(hashdyn->bucket[0])
222 5001 : + tommy_hashdyn_count(hashdyn) * (tommy_size_t)sizeof(tommy_hashdyn_node);
223 : }
224 :
|
