BadVPN – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 /**
2 * @file CHash_impl.h
3 * @author Ambroz Bizjak <ambrop7@gmail.com>
4 *
5 * @section LICENSE
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
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 * 3. Neither the name of the author nor the
15 * names of its contributors may be used to endorse or promote products
16 * derived from this software without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
20 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
21 * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
22 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
23 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
24 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
25 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
27 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29  
30 #include "CHash_header.h"
31  
32 static void CHash_assert_valid_entry (CHashArg arg, CHashRef entry)
33 {
34 ASSERT(entry.link != CHashNullLink())
35 ASSERT(entry.ptr == CHASH_PARAM_DEREF(arg, entry.link))
36 }
37  
38 static CHashLink CHashNullLink (void)
39 {
40 return CHASH_PARAM_NULL;
41 }
42  
43 static CHashRef CHashNullRef (void)
44 {
45 CHashRef entry = {NULL, CHashNullLink()};
46 return entry;
47 }
48  
49 static int CHashIsNullLink (CHashLink link)
50 {
51 return (link == CHashNullLink());
52 }
53  
54 static int CHashIsNullRef (CHashRef ref)
55 {
56 return CHashIsNullLink(ref.link);
57 }
58  
59 static CHashRef CHashDerefMayNull (CHashArg arg, CHashLink link)
60 {
61 if (link == CHashNullLink()) {
62 return CHashNullRef();
63 }
64  
65 CHashRef entry = {CHASH_PARAM_DEREF(arg, link), link};
66 ASSERT(entry.ptr)
67  
68 return entry;
69 }
70  
71 static CHashRef CHashDerefNonNull (CHashArg arg, CHashLink link)
72 {
73 ASSERT(link != CHashNullLink())
74  
75 CHashRef entry = {CHASH_PARAM_DEREF(arg, link), link};
76 ASSERT(entry.ptr)
77  
78 return entry;
79 }
80  
81 static int CHash_Init (CHash *o, size_t num_buckets)
82 {
83 if (num_buckets == 0) {
84 num_buckets = 1;
85 }
86  
87 o->num_buckets = num_buckets;
88  
89 o->buckets = (CHashLink *)BAllocArray(o->num_buckets, sizeof(o->buckets[0]));
90 if (!o->buckets) {
91 return 0;
92 }
93  
94 for (size_t i = 0; i < o->num_buckets; i++) {
95 o->buckets[i] = CHashNullLink();
96 }
97  
98 return 1;
99 }
100  
101 static void CHash_Free (CHash *o)
102 {
103 BFree(o->buckets);
104 }
105  
106 static int CHash_Insert (CHash *o, CHashArg arg, CHashRef entry, CHashRef *out_existing)
107 {
108 CHash_assert_valid_entry(arg, entry);
109  
110 size_t index = CHASH_PARAM_ENTRYHASH(arg, entry) % o->num_buckets;
111  
112 CHashLink link = o->buckets[index];
113 while (link != CHashNullLink()) {
114 CHashRef cur = CHashDerefNonNull(arg, link);
115 if (CHASH_PARAM_COMPARE_ENTRIES(arg, cur, entry)) {
116 if (out_existing) {
117 *out_existing = cur;
118 }
119 return 0;
120 }
121 link = CHash_next(cur);
122 }
123  
124 CHash_next(entry) = o->buckets[index];
125 o->buckets[index] = entry.link;
126  
127 return 1;
128 }
129  
130 static void CHash_InsertMulti (CHash *o, CHashArg arg, CHashRef entry)
131 {
132 CHash_assert_valid_entry(arg, entry);
133  
134 size_t index = CHASH_PARAM_ENTRYHASH(arg, entry) % o->num_buckets;
135  
136 CHashRef prev = CHashNullRef();
137 CHashLink link = o->buckets[index];
138 while (link != CHashNullLink()) {
139 CHashRef cur = CHashDerefNonNull(arg, link);
140 if (CHASH_PARAM_COMPARE_ENTRIES(arg, cur, entry)) {
141 break;
142 }
143 prev = cur;
144 link = CHash_next(cur);
145 }
146  
147 if (link == CHashNullLink() || prev.link == CHashNullLink()) {
148 CHash_next(entry) = o->buckets[index];
149 o->buckets[index] = entry.link;
150 } else {
151 CHash_next(entry) = link;
152 CHash_next(prev) = entry.link;
153 }
154 }
155  
156 static void CHash_Remove (CHash *o, CHashArg arg, CHashRef entry)
157 {
158 CHash_assert_valid_entry(arg, entry);
159  
160 size_t index = CHASH_PARAM_ENTRYHASH(arg, entry) % o->num_buckets;
161  
162 CHashRef prev = CHashNullRef();
163 CHashLink link = o->buckets[index];
164 while (link != entry.link) {
165 CHashRef cur = CHashDerefNonNull(arg, link);
166 prev = cur;
167 link = CHash_next(cur);
168 ASSERT(link != CHashNullLink())
169 }
170  
171 if (prev.link == CHashNullLink()) {
172 o->buckets[index] = CHash_next(entry);
173 } else {
174 CHash_next(prev) = CHash_next(entry);
175 }
176 }
177  
178 static CHashRef CHash_Lookup (const CHash *o, CHashArg arg, CHashKey key)
179 {
180 size_t hash = CHASH_PARAM_KEYHASH(arg, key);
181 size_t index = hash % o->num_buckets;
182  
183 CHashLink link = o->buckets[index];
184 while (link != CHashNullLink()) {
185 CHashRef cur = CHashDerefNonNull(arg, link);
186 #if CHASH_PARAM_ENTRYHASH_IS_CHEAP
187 if (CHASH_PARAM_ENTRYHASH(arg, cur) == hash && CHASH_PARAM_COMPARE_KEY_ENTRY(arg, key, cur)) {
188 #else
189 if (CHASH_PARAM_COMPARE_KEY_ENTRY(arg, key, cur)) {
190 #endif
191 return cur;
192 }
193 link = CHash_next(cur);
194 }
195  
196 return CHashNullRef();
197 }
198  
199 static CHashRef CHash_GetNextEqual (const CHash *o, CHashArg arg, CHashRef entry)
200 {
201 CHash_assert_valid_entry(arg, entry);
202  
203 CHashLink next = CHash_next(entry);
204  
205 if (next == CHashNullLink()) {
206 return CHashNullRef();
207 }
208  
209 CHashRef next_ref = CHashDerefNonNull(arg, next);
210 if (!CHASH_PARAM_COMPARE_ENTRIES(arg, next_ref, entry)) {
211 return CHashNullRef();
212 }
213  
214 return next_ref;
215 }
216  
217 static int CHash_MultiplyBuckets (CHash *o, CHashArg arg, int exp)
218 {
219 ASSERT(exp > 0)
220  
221 size_t new_num_buckets = o->num_buckets;
222 while (exp-- > 0) {
223 if (new_num_buckets > SIZE_MAX / 2) {
224 return 0;
225 }
226 new_num_buckets *= 2;
227 }
228  
229 CHashLink *new_buckets = (CHashLink *)BReallocArray(o->buckets, new_num_buckets, sizeof(new_buckets[0]));
230 if (!new_buckets) {
231 return 0;
232 }
233 o->buckets = new_buckets;
234  
235 for (size_t i = o->num_buckets; i < new_num_buckets; i++) {
236 o->buckets[i] = CHashNullLink();
237 }
238  
239 for (size_t i = 0; i < o->num_buckets; i++) {
240 CHashRef prev = CHashNullRef();
241 CHashLink link = o->buckets[i];
242  
243 while (link != CHashNullLink()) {
244 CHashRef cur = CHashDerefNonNull(arg, link);
245 link = CHash_next(cur);
246  
247 size_t new_index = CHASH_PARAM_ENTRYHASH(arg, cur) % new_num_buckets;
248 if (new_index == i) {
249 prev = cur;
250 continue;
251 }
252  
253 if (CHashIsNullRef(prev)) {
254 o->buckets[i] = CHash_next(cur);
255 } else {
256 CHash_next(prev) = CHash_next(cur);
257 }
258  
259 CHash_next(cur) = o->buckets[new_index];
260 o->buckets[new_index] = cur.link;
261 }
262 }
263  
264 for (size_t i = o->num_buckets; i < new_num_buckets; i++) {
265 CHashLink new_bucket_link = CHashNullLink();
266  
267 CHashLink link = o->buckets[i];
268 while (link != CHashNullLink()) {
269 CHashRef cur = CHashDerefNonNull(arg, link);
270 link = CHash_next(cur);
271  
272 CHash_next(cur) = new_bucket_link;
273 new_bucket_link = cur.link;
274 }
275  
276 o->buckets[i] = new_bucket_link;
277 }
278  
279 o->num_buckets = new_num_buckets;
280  
281 return 1;
282 }
283  
284 static void CHash_Verify (const CHash *o, CHashArg arg)
285 {
286 ASSERT_FORCE(o->num_buckets > 0)
287 ASSERT_FORCE(o->buckets)
288  
289 for (size_t i = 0; i < o->num_buckets; i++) {
290 CHashRef cur = CHashDerefMayNull(arg, o->buckets[i]);
291 CHashRef same_first = cur;
292  
293 while (!CHashIsNullRef(cur)) {
294 size_t index = CHASH_PARAM_ENTRYHASH(arg, cur) % o->num_buckets;
295 ASSERT_FORCE(index == i)
296  
297 if (!CHASH_PARAM_COMPARE_ENTRIES(arg, cur, same_first)) {
298 same_first = cur;
299 }
300  
301 CHashRef ccur = CHashDerefNonNull(arg, o->buckets[i]);
302 while (ccur.link != same_first.link) {
303 ASSERT_FORCE(!CHASH_PARAM_COMPARE_ENTRIES(arg, ccur, cur))
304 ccur = CHashDerefMayNull(arg, CHash_next(ccur));
305 }
306  
307 cur = CHashDerefMayNull(arg, CHash_next(cur));
308 }
309 }
310 }
311  
312 #include "CHash_footer.h"