diff options
author | Christian Grothoff <christian@grothoff.org> | 2012-10-14 20:05:31 +0000 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2012-10-14 20:05:31 +0000 |
commit | dbb1cc93b76cae5145847da04d83851d460325b1 (patch) | |
tree | 8dc3d86f57ab61eacdb300b7f9858ef3d36bbb62 /src/util/container_multihashmap.c | |
parent | c50146d0d092d7881c58df46c237d8b50410a3a4 (diff) | |
download | gnunet-dbb1cc93b76cae5145847da04d83851d460325b1.tar.gz gnunet-dbb1cc93b76cae5145847da04d83851d460325b1.zip |
-enabling new optimized multihashmap
Diffstat (limited to 'src/util/container_multihashmap.c')
-rw-r--r-- | src/util/container_multihashmap.c | 513 |
1 files changed, 385 insertions, 128 deletions
diff --git a/src/util/container_multihashmap.c b/src/util/container_multihashmap.c index 4a41fd015..a23f96798 100644 --- a/src/util/container_multihashmap.c +++ b/src/util/container_multihashmap.c | |||
@@ -1,6 +1,6 @@ | |||
1 | /* | 1 | /* |
2 | This file is part of GNUnet. | 2 | This file is part of GNUnet. |
3 | (C) 2008 Christian Grothoff (and other contributing authors) | 3 | (C) 2008, 2012 Christian Grothoff (and other contributing authors) |
4 | 4 | ||
5 | GNUnet is free software; you can redistribute it and/or modify | 5 | GNUnet is free software; you can redistribute it and/or modify |
6 | it under the terms of the GNU General Public License as published | 6 | it under the terms of the GNU General Public License as published |
@@ -31,16 +31,35 @@ | |||
31 | #define LOG(kind,...) GNUNET_log_from (kind, "util", __VA_ARGS__) | 31 | #define LOG(kind,...) GNUNET_log_from (kind, "util", __VA_ARGS__) |
32 | 32 | ||
33 | /** | 33 | /** |
34 | * An entry in the hash map. | 34 | * An entry in the hash map with the full key. |
35 | */ | 35 | */ |
36 | struct MapEntry | 36 | struct BigMapEntry |
37 | { | 37 | { |
38 | 38 | ||
39 | /** | 39 | /** |
40 | * Value of the entry. | ||
41 | */ | ||
42 | void *value; | ||
43 | |||
44 | /** | ||
45 | * If there is a hash collision, we create a linked list. | ||
46 | */ | ||
47 | struct BigMapEntry *next; | ||
48 | |||
49 | /** | ||
40 | * Key for the entry. | 50 | * Key for the entry. |
41 | */ | 51 | */ |
42 | struct GNUNET_HashCode key; | 52 | struct GNUNET_HashCode key; |
43 | 53 | ||
54 | }; | ||
55 | |||
56 | |||
57 | /** | ||
58 | * An entry in the hash map with just a pointer to the key. | ||
59 | */ | ||
60 | struct SmallMapEntry | ||
61 | { | ||
62 | |||
44 | /** | 63 | /** |
45 | * Value of the entry. | 64 | * Value of the entry. |
46 | */ | 65 | */ |
@@ -49,10 +68,33 @@ struct MapEntry | |||
49 | /** | 68 | /** |
50 | * If there is a hash collision, we create a linked list. | 69 | * If there is a hash collision, we create a linked list. |
51 | */ | 70 | */ |
52 | struct MapEntry *next; | 71 | struct SmallMapEntry *next; |
72 | |||
73 | /** | ||
74 | * Key for the entry. | ||
75 | */ | ||
76 | const struct GNUNET_HashCode *key; | ||
53 | 77 | ||
54 | }; | 78 | }; |
55 | 79 | ||
80 | |||
81 | /** | ||
82 | * Entry in the map. | ||
83 | */ | ||
84 | union MapEntry | ||
85 | { | ||
86 | /** | ||
87 | * Variant used if map entries only contain a pointer to the key. | ||
88 | */ | ||
89 | struct SmallMapEntry *sme; | ||
90 | |||
91 | /** | ||
92 | * Variant used if map entries contain the full key. | ||
93 | */ | ||
94 | struct BigMapEntry *bme; | ||
95 | }; | ||
96 | |||
97 | |||
56 | /** | 98 | /** |
57 | * Internal representation of the hash map. | 99 | * Internal representation of the hash map. |
58 | */ | 100 | */ |
@@ -62,7 +104,7 @@ struct GNUNET_CONTAINER_MultiHashMap | |||
62 | /** | 104 | /** |
63 | * All of our buckets. | 105 | * All of our buckets. |
64 | */ | 106 | */ |
65 | struct MapEntry **map; | 107 | union MapEntry *map; |
66 | 108 | ||
67 | /** | 109 | /** |
68 | * Number of entries in the map. | 110 | * Number of entries in the map. |
@@ -73,6 +115,12 @@ struct GNUNET_CONTAINER_MultiHashMap | |||
73 | * Length of the "map" array. | 115 | * Length of the "map" array. |
74 | */ | 116 | */ |
75 | unsigned int map_length; | 117 | unsigned int map_length; |
118 | |||
119 | /** | ||
120 | * GNUNET_NO if the map entries are of type 'struct BigMapEntry', | ||
121 | * GNUNET_YES if the map entries are of type 'struct SmallMapEntry'. | ||
122 | */ | ||
123 | int use_small_entries; | ||
76 | }; | 124 | }; |
77 | 125 | ||
78 | 126 | ||
@@ -95,13 +143,14 @@ struct GNUNET_CONTAINER_MultiHashMap * | |||
95 | GNUNET_CONTAINER_multihashmap_create (unsigned int len, | 143 | GNUNET_CONTAINER_multihashmap_create (unsigned int len, |
96 | int do_not_copy_keys) | 144 | int do_not_copy_keys) |
97 | { | 145 | { |
98 | struct GNUNET_CONTAINER_MultiHashMap *ret; | 146 | struct GNUNET_CONTAINER_MultiHashMap *map; |
99 | 147 | ||
100 | GNUNET_assert (len > 0); | 148 | GNUNET_assert (len > 0); |
101 | ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_MultiHashMap)); | 149 | map = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_MultiHashMap)); |
102 | ret->map = GNUNET_malloc (len * sizeof (struct MapEntry *)); | 150 | map->map = GNUNET_malloc (len * sizeof (union MapEntry)); |
103 | ret->map_length = len; | 151 | map->map_length = len; |
104 | return ret; | 152 | map->use_small_entries = do_not_copy_keys; |
153 | return map; | ||
105 | } | 154 | } |
106 | 155 | ||
107 | 156 | ||
@@ -116,14 +165,36 @@ GNUNET_CONTAINER_multihashmap_destroy (struct GNUNET_CONTAINER_MultiHashMap | |||
116 | *map) | 165 | *map) |
117 | { | 166 | { |
118 | unsigned int i; | 167 | unsigned int i; |
119 | struct MapEntry *e; | 168 | union MapEntry me; |
120 | 169 | ||
121 | for (i = 0; i < map->map_length; i++) | 170 | for (i = 0; i < map->map_length; i++) |
122 | { | 171 | { |
123 | while (NULL != (e = map->map[i])) | 172 | me = map->map[i]; |
173 | if (map->use_small_entries) | ||
174 | { | ||
175 | struct SmallMapEntry *sme; | ||
176 | struct SmallMapEntry *nxt; | ||
177 | |||
178 | nxt = me.sme; | ||
179 | while (NULL != (sme = nxt)) | ||
180 | { | ||
181 | nxt = sme->next; | ||
182 | GNUNET_free (sme); | ||
183 | } | ||
184 | me.sme = NULL; | ||
185 | } | ||
186 | else | ||
124 | { | 187 | { |
125 | map->map[i] = e->next; | 188 | struct BigMapEntry *bme; |
126 | GNUNET_free (e); | 189 | struct BigMapEntry *nxt; |
190 | |||
191 | nxt = me.bme; | ||
192 | while (NULL != (bme = nxt)) | ||
193 | { | ||
194 | nxt = bme->next; | ||
195 | GNUNET_free (bme); | ||
196 | } | ||
197 | me.bme = NULL; | ||
127 | } | 198 | } |
128 | } | 199 | } |
129 | GNUNET_free (map->map); | 200 | GNUNET_free (map->map); |
@@ -134,16 +205,16 @@ GNUNET_CONTAINER_multihashmap_destroy (struct GNUNET_CONTAINER_MultiHashMap | |||
134 | /** | 205 | /** |
135 | * Compute the index of the bucket for the given key. | 206 | * Compute the index of the bucket for the given key. |
136 | * | 207 | * |
137 | * @param m hash map for which to compute the index | 208 | * @param map hash map for which to compute the index |
138 | * @param key what key should the index be computed for | 209 | * @param key what key should the index be computed for |
139 | * @return offset into the "map" array of "m" | 210 | * @return offset into the "map" array of "map" |
140 | */ | 211 | */ |
141 | static unsigned int | 212 | static unsigned int |
142 | idx_of (const struct GNUNET_CONTAINER_MultiHashMap *m, | 213 | idx_of (const struct GNUNET_CONTAINER_MultiHashMap *map, |
143 | const struct GNUNET_HashCode * key) | 214 | const struct GNUNET_HashCode *key) |
144 | { | 215 | { |
145 | GNUNET_assert (m != NULL); | 216 | GNUNET_assert (map != NULL); |
146 | return (*(unsigned int *) key) % m->map_length; | 217 | return (*(unsigned int *) key) % map->map_length; |
147 | } | 218 | } |
148 | 219 | ||
149 | 220 | ||
@@ -173,16 +244,26 @@ GNUNET_CONTAINER_multihashmap_size (const struct GNUNET_CONTAINER_MultiHashMap | |||
173 | */ | 244 | */ |
174 | void * | 245 | void * |
175 | GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap | 246 | GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap |
176 | *map, const struct GNUNET_HashCode * key) | 247 | *map, const struct GNUNET_HashCode *key) |
177 | { | 248 | { |
178 | struct MapEntry *e; | 249 | union MapEntry me; |
179 | 250 | ||
180 | e = map->map[idx_of (map, key)]; | 251 | me = map->map[idx_of (map, key)]; |
181 | while (e != NULL) | 252 | if (map->use_small_entries) |
182 | { | 253 | { |
183 | if (0 == memcmp (key, &e->key, sizeof (struct GNUNET_HashCode))) | 254 | struct SmallMapEntry *sme; |
184 | return e->value; | 255 | |
185 | e = e->next; | 256 | for (sme = me.sme; NULL != sme; sme = sme->next) |
257 | if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_HashCode))) | ||
258 | return sme->value; | ||
259 | } | ||
260 | else | ||
261 | { | ||
262 | struct BigMapEntry *bme; | ||
263 | |||
264 | for (bme = me.bme; NULL != bme; bme = bme->next) | ||
265 | if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode))) | ||
266 | return bme->value; | ||
186 | } | 267 | } |
187 | return NULL; | 268 | return NULL; |
188 | } | 269 | } |
@@ -205,25 +286,48 @@ GNUNET_CONTAINER_multihashmap_iterate (const struct | |||
205 | { | 286 | { |
206 | int count; | 287 | int count; |
207 | unsigned int i; | 288 | unsigned int i; |
208 | struct MapEntry *e; | 289 | union MapEntry me; |
209 | struct MapEntry *n; | ||
210 | struct GNUNET_HashCode kc; | 290 | struct GNUNET_HashCode kc; |
211 | 291 | ||
212 | count = 0; | 292 | count = 0; |
213 | GNUNET_assert (map != NULL); | 293 | GNUNET_assert (NULL != map); |
214 | for (i = 0; i < map->map_length; i++) | 294 | for (i = 0; i < map->map_length; i++) |
215 | { | 295 | { |
216 | n = map->map[i]; | 296 | me = map->map[i]; |
217 | while (NULL != (e = n)) | 297 | if (map->use_small_entries) |
218 | { | 298 | { |
219 | n = e->next; | 299 | struct SmallMapEntry *sme; |
220 | if (NULL != it) | 300 | struct SmallMapEntry *nxt; |
301 | |||
302 | nxt = me.sme; | ||
303 | while (NULL != (sme = nxt)) | ||
221 | { | 304 | { |
222 | kc = e->key; | 305 | nxt = sme->next; |
223 | if (GNUNET_OK != it (it_cls, &kc, e->value)) | 306 | if (NULL != it) |
224 | return GNUNET_SYSERR; | 307 | { |
308 | if (GNUNET_OK != it (it_cls, sme->key, sme->value)) | ||
309 | return GNUNET_SYSERR; | ||
310 | } | ||
311 | count++; | ||
312 | } | ||
313 | } | ||
314 | else | ||
315 | { | ||
316 | struct BigMapEntry *bme; | ||
317 | struct BigMapEntry *nxt; | ||
318 | |||
319 | nxt = me.bme; | ||
320 | while (NULL != (bme = nxt)) | ||
321 | { | ||
322 | nxt = bme->next; | ||
323 | if (NULL != it) | ||
324 | { | ||
325 | kc = bme->key; | ||
326 | if (GNUNET_OK != it (it_cls, &kc, bme->value)) | ||
327 | return GNUNET_SYSERR; | ||
328 | } | ||
329 | count++; | ||
225 | } | 330 | } |
226 | count++; | ||
227 | } | 331 | } |
228 | } | 332 | } |
229 | return count; | 333 | return count; |
@@ -243,30 +347,57 @@ GNUNET_CONTAINER_multihashmap_iterate (const struct | |||
243 | */ | 347 | */ |
244 | int | 348 | int |
245 | GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map, | 349 | GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map, |
246 | const struct GNUNET_HashCode * key, void *value) | 350 | const struct GNUNET_HashCode *key, |
351 | void *value) | ||
247 | { | 352 | { |
248 | struct MapEntry *e; | 353 | union MapEntry me; |
249 | struct MapEntry *p; | ||
250 | unsigned int i; | 354 | unsigned int i; |
251 | 355 | ||
252 | i = idx_of (map, key); | 356 | i = idx_of (map, key); |
253 | p = NULL; | 357 | me = map->map[i]; |
254 | e = map->map[i]; | 358 | if (map->use_small_entries) |
255 | while (e != NULL) | 359 | { |
360 | struct SmallMapEntry *sme; | ||
361 | struct SmallMapEntry *p; | ||
362 | |||
363 | p = NULL; | ||
364 | for (sme = me.sme; NULL != sme; sme = sme->next) | ||
365 | { | ||
366 | if ((0 == memcmp (key, sme->key, sizeof (struct GNUNET_HashCode))) && | ||
367 | (value == sme->value)) | ||
368 | { | ||
369 | if (NULL == p) | ||
370 | map->map[i].sme = sme->next; | ||
371 | else | ||
372 | p->next = sme->next; | ||
373 | GNUNET_free (sme); | ||
374 | map->size--; | ||
375 | return GNUNET_YES; | ||
376 | } | ||
377 | p = sme; | ||
378 | } | ||
379 | } | ||
380 | else | ||
256 | { | 381 | { |
257 | if ((0 == memcmp (key, &e->key, sizeof (struct GNUNET_HashCode))) && | 382 | struct BigMapEntry *bme; |
258 | (value == e->value)) | 383 | struct BigMapEntry *p; |
384 | |||
385 | p = NULL; | ||
386 | for (bme = me.bme; NULL != bme; bme = bme->next) | ||
259 | { | 387 | { |
260 | if (p == NULL) | 388 | if ((0 == memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode))) && |
261 | map->map[i] = e->next; | 389 | (value == bme->value)) |
262 | else | 390 | { |
263 | p->next = e->next; | 391 | if (NULL == p) |
264 | GNUNET_free (e); | 392 | map->map[i].bme = bme->next; |
265 | map->size--; | 393 | else |
266 | return GNUNET_YES; | 394 | p->next = bme->next; |
395 | GNUNET_free (bme); | ||
396 | map->size--; | ||
397 | return GNUNET_YES; | ||
398 | } | ||
399 | p = bme; | ||
267 | } | 400 | } |
268 | p = e; | ||
269 | e = e->next; | ||
270 | } | 401 | } |
271 | return GNUNET_NO; | 402 | return GNUNET_NO; |
272 | } | 403 | } |
@@ -282,37 +413,73 @@ GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map, | |||
282 | */ | 413 | */ |
283 | int | 414 | int |
284 | GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap | 415 | GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap |
285 | *map, const struct GNUNET_HashCode * key) | 416 | *map, const struct GNUNET_HashCode *key) |
286 | { | 417 | { |
287 | struct MapEntry *e; | 418 | union MapEntry me; |
288 | struct MapEntry *p; | ||
289 | unsigned int i; | 419 | unsigned int i; |
290 | int ret; | 420 | int ret; |
291 | 421 | ||
292 | ret = 0; | 422 | ret = 0; |
293 | i = idx_of (map, key); | 423 | i = idx_of (map, key); |
294 | p = NULL; | 424 | me = map->map[i]; |
295 | e = map->map[i]; | 425 | if (map->use_small_entries) |
296 | while (e != NULL) | 426 | { |
297 | { | 427 | struct SmallMapEntry *sme; |
298 | if (0 == memcmp (key, &e->key, sizeof (struct GNUNET_HashCode))) | 428 | struct SmallMapEntry *p; |
429 | |||
430 | p = NULL; | ||
431 | sme = me.sme; | ||
432 | while (NULL != sme) | ||
299 | { | 433 | { |
300 | if (p == NULL) | 434 | if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_HashCode))) |
301 | map->map[i] = e->next; | 435 | { |
302 | else | 436 | if (NULL == p) |
303 | p->next = e->next; | 437 | map->map[i].sme = sme->next; |
304 | GNUNET_free (e); | 438 | else |
305 | map->size--; | 439 | p->next = sme->next; |
306 | if (p == NULL) | 440 | GNUNET_free (sme); |
307 | e = map->map[i]; | 441 | map->size--; |
442 | if (NULL == p) | ||
443 | sme = map->map[i].sme; | ||
444 | else | ||
445 | sme = p->next; | ||
446 | ret++; | ||
447 | } | ||
308 | else | 448 | else |
309 | e = p->next; | 449 | { |
310 | ret++; | 450 | p = sme; |
451 | sme = sme->next; | ||
452 | } | ||
311 | } | 453 | } |
312 | else | 454 | } |
455 | else | ||
456 | { | ||
457 | struct BigMapEntry *bme; | ||
458 | struct BigMapEntry *p; | ||
459 | |||
460 | p = NULL; | ||
461 | bme = me.bme; | ||
462 | while (NULL != bme) | ||
313 | { | 463 | { |
314 | p = e; | 464 | if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode))) |
315 | e = e->next; | 465 | { |
466 | if (NULL == p) | ||
467 | map->map[i].bme = bme->next; | ||
468 | else | ||
469 | p->next = bme->next; | ||
470 | GNUNET_free (bme); | ||
471 | map->size--; | ||
472 | if (NULL == p) | ||
473 | bme = map->map[i].bme; | ||
474 | else | ||
475 | bme = p->next; | ||
476 | ret++; | ||
477 | } | ||
478 | else | ||
479 | { | ||
480 | p = bme; | ||
481 | bme = bme->next; | ||
482 | } | ||
316 | } | 483 | } |
317 | } | 484 | } |
318 | return ret; | 485 | return ret; |
@@ -331,16 +498,26 @@ GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap | |||
331 | int | 498 | int |
332 | GNUNET_CONTAINER_multihashmap_contains (const struct | 499 | GNUNET_CONTAINER_multihashmap_contains (const struct |
333 | GNUNET_CONTAINER_MultiHashMap *map, | 500 | GNUNET_CONTAINER_MultiHashMap *map, |
334 | const struct GNUNET_HashCode * key) | 501 | const struct GNUNET_HashCode *key) |
335 | { | 502 | { |
336 | struct MapEntry *e; | 503 | union MapEntry me; |
337 | 504 | ||
338 | e = map->map[idx_of (map, key)]; | 505 | me = map->map[idx_of (map, key)]; |
339 | while (e != NULL) | 506 | if (map->use_small_entries) |
340 | { | 507 | { |
341 | if (0 == memcmp (key, &e->key, sizeof (struct GNUNET_HashCode))) | 508 | struct SmallMapEntry *sme; |
342 | return GNUNET_YES; | 509 | |
343 | e = e->next; | 510 | for (sme = me.sme; NULL != sme; sme = sme->next) |
511 | if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_HashCode))) | ||
512 | return GNUNET_YES; | ||
513 | } | ||
514 | else | ||
515 | { | ||
516 | struct BigMapEntry *bme; | ||
517 | |||
518 | for (bme = me.bme; NULL != bme; bme = bme->next) | ||
519 | if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode))) | ||
520 | return GNUNET_YES; | ||
344 | } | 521 | } |
345 | return GNUNET_NO; | 522 | return GNUNET_NO; |
346 | } | 523 | } |
@@ -359,18 +536,29 @@ GNUNET_CONTAINER_multihashmap_contains (const struct | |||
359 | int | 536 | int |
360 | GNUNET_CONTAINER_multihashmap_contains_value (const struct | 537 | GNUNET_CONTAINER_multihashmap_contains_value (const struct |
361 | GNUNET_CONTAINER_MultiHashMap | 538 | GNUNET_CONTAINER_MultiHashMap |
362 | *map, const struct GNUNET_HashCode * key, | 539 | *map, const struct GNUNET_HashCode *key, |
363 | const void *value) | 540 | const void *value) |
364 | { | 541 | { |
365 | struct MapEntry *e; | 542 | union MapEntry me; |
366 | 543 | ||
367 | e = map->map[idx_of (map, key)]; | 544 | me = map->map[idx_of (map, key)]; |
368 | while (e != NULL) | 545 | if (map->use_small_entries) |
369 | { | 546 | { |
370 | if ((0 == memcmp (key, &e->key, sizeof (struct GNUNET_HashCode))) && | 547 | struct SmallMapEntry *sme; |
371 | (e->value == value)) | 548 | |
372 | return GNUNET_YES; | 549 | for (sme = me.sme; NULL != sme; sme = sme->next) |
373 | e = e->next; | 550 | if ( (0 == memcmp (key, sme->key, sizeof (struct GNUNET_HashCode))) && |
551 | (sme->value == value) ) | ||
552 | return GNUNET_YES; | ||
553 | } | ||
554 | else | ||
555 | { | ||
556 | struct BigMapEntry *bme; | ||
557 | |||
558 | for (bme = me.bme; NULL != bme; bme = bme->next) | ||
559 | if ( (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode))) && | ||
560 | (bme->value == value) ) | ||
561 | return GNUNET_YES; | ||
374 | } | 562 | } |
375 | return GNUNET_NO; | 563 | return GNUNET_NO; |
376 | } | 564 | } |
@@ -384,9 +572,8 @@ GNUNET_CONTAINER_multihashmap_contains_value (const struct | |||
384 | static void | 572 | static void |
385 | grow (struct GNUNET_CONTAINER_MultiHashMap *map) | 573 | grow (struct GNUNET_CONTAINER_MultiHashMap *map) |
386 | { | 574 | { |
387 | struct MapEntry **old_map; | 575 | union MapEntry *old_map; |
388 | struct MapEntry **new_map; | 576 | union MapEntry *new_map; |
389 | struct MapEntry *e; | ||
390 | unsigned int old_len; | 577 | unsigned int old_len; |
391 | unsigned int new_len; | 578 | unsigned int new_len; |
392 | unsigned int idx; | 579 | unsigned int idx; |
@@ -395,17 +582,34 @@ grow (struct GNUNET_CONTAINER_MultiHashMap *map) | |||
395 | old_map = map->map; | 582 | old_map = map->map; |
396 | old_len = map->map_length; | 583 | old_len = map->map_length; |
397 | new_len = old_len * 2; | 584 | new_len = old_len * 2; |
398 | new_map = GNUNET_malloc (sizeof (struct MapEntry *) * new_len); | 585 | new_map = GNUNET_malloc (sizeof (union MapEntry) * new_len); |
399 | map->map_length = new_len; | 586 | map->map_length = new_len; |
400 | map->map = new_map; | 587 | map->map = new_map; |
401 | for (i = 0; i < old_len; i++) | 588 | for (i = 0; i < old_len; i++) |
402 | { | 589 | { |
403 | while (NULL != (e = old_map[i])) | 590 | if (map->use_small_entries) |
591 | { | ||
592 | struct SmallMapEntry *sme; | ||
593 | |||
594 | while (NULL != (sme = old_map[i].sme)) | ||
595 | { | ||
596 | old_map[i].sme = sme->next; | ||
597 | idx = idx_of (map, sme->key); | ||
598 | sme->next = new_map[idx].sme; | ||
599 | new_map[idx].sme = sme; | ||
600 | } | ||
601 | } | ||
602 | else | ||
404 | { | 603 | { |
405 | old_map[i] = e->next; | 604 | struct BigMapEntry *bme; |
406 | idx = idx_of (map, &e->key); | 605 | |
407 | e->next = new_map[idx]; | 606 | while (NULL != (bme = old_map[i].bme)) |
408 | new_map[idx] = e; | 607 | { |
608 | old_map[i].bme = bme->next; | ||
609 | idx = idx_of (map, &bme->key); | ||
610 | bme->next = new_map[idx].bme; | ||
611 | new_map[idx].bme = bme; | ||
612 | } | ||
409 | } | 613 | } |
410 | } | 614 | } |
411 | GNUNET_free (old_map); | 615 | GNUNET_free (old_map); |
@@ -426,27 +630,43 @@ grow (struct GNUNET_CONTAINER_MultiHashMap *map) | |||
426 | */ | 630 | */ |
427 | int | 631 | int |
428 | GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map, | 632 | GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map, |
429 | const struct GNUNET_HashCode * key, void *value, | 633 | const struct GNUNET_HashCode *key, |
634 | void *value, | ||
430 | enum GNUNET_CONTAINER_MultiHashMapOption opt) | 635 | enum GNUNET_CONTAINER_MultiHashMapOption opt) |
431 | { | 636 | { |
432 | struct MapEntry *e; | 637 | union MapEntry me; |
433 | unsigned int i; | 638 | unsigned int i; |
434 | 639 | ||
435 | i = idx_of (map, key); | 640 | i = idx_of (map, key); |
436 | if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) && | 641 | if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) && |
437 | (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST)) | 642 | (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST)) |
438 | { | 643 | { |
439 | e = map->map[i]; | 644 | me = map->map[i]; |
440 | while (e != NULL) | 645 | if (map->use_small_entries) |
441 | { | 646 | { |
442 | if (0 == memcmp (key, &e->key, sizeof (struct GNUNET_HashCode))) | 647 | struct SmallMapEntry *sme; |
443 | { | 648 | |
444 | if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) | 649 | for (sme = me.sme; NULL != sme; sme = sme->next) |
445 | return GNUNET_SYSERR; | 650 | if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_HashCode))) |
446 | e->value = value; | 651 | { |
447 | return GNUNET_NO; | 652 | if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) |
448 | } | 653 | return GNUNET_SYSERR; |
449 | e = e->next; | 654 | sme->value = value; |
655 | return GNUNET_NO; | ||
656 | } | ||
657 | } | ||
658 | else | ||
659 | { | ||
660 | struct BigMapEntry *bme; | ||
661 | |||
662 | for (bme = me.bme; NULL != bme; bme = bme->next) | ||
663 | if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode))) | ||
664 | { | ||
665 | if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) | ||
666 | return GNUNET_SYSERR; | ||
667 | bme->value = value; | ||
668 | return GNUNET_NO; | ||
669 | } | ||
450 | } | 670 | } |
451 | } | 671 | } |
452 | if (map->size / 3 >= map->map_length / 4) | 672 | if (map->size / 3 >= map->map_length / 4) |
@@ -454,11 +674,26 @@ GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map, | |||
454 | grow (map); | 674 | grow (map); |
455 | i = idx_of (map, key); | 675 | i = idx_of (map, key); |
456 | } | 676 | } |
457 | e = GNUNET_malloc (sizeof (struct MapEntry)); | 677 | if (map->use_small_entries) |
458 | e->key = *key; | 678 | { |
459 | e->value = value; | 679 | struct SmallMapEntry *sme; |
460 | e->next = map->map[i]; | 680 | |
461 | map->map[i] = e; | 681 | sme = GNUNET_malloc (sizeof (struct SmallMapEntry)); |
682 | sme->key = key; | ||
683 | sme->value = value; | ||
684 | sme->next = map->map[i].sme; | ||
685 | map->map[i].sme = sme; | ||
686 | } | ||
687 | else | ||
688 | { | ||
689 | struct BigMapEntry *bme; | ||
690 | |||
691 | bme = GNUNET_malloc (sizeof (struct BigMapEntry)); | ||
692 | bme->key = *key; | ||
693 | bme->value = value; | ||
694 | bme->next = map->map[i].bme; | ||
695 | map->map[i].bme = bme; | ||
696 | } | ||
462 | map->size++; | 697 | map->size++; |
463 | return GNUNET_OK; | 698 | return GNUNET_OK; |
464 | } | 699 | } |
@@ -477,24 +712,46 @@ GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map, | |||
477 | int | 712 | int |
478 | GNUNET_CONTAINER_multihashmap_get_multiple (const struct | 713 | GNUNET_CONTAINER_multihashmap_get_multiple (const struct |
479 | GNUNET_CONTAINER_MultiHashMap *map, | 714 | GNUNET_CONTAINER_MultiHashMap *map, |
480 | const struct GNUNET_HashCode * key, | 715 | const struct GNUNET_HashCode *key, |
481 | GNUNET_CONTAINER_HashMapIterator it, | 716 | GNUNET_CONTAINER_HashMapIterator it, |
482 | void *it_cls) | 717 | void *it_cls) |
483 | { | 718 | { |
484 | int count; | 719 | int count; |
485 | struct MapEntry *e; | 720 | union MapEntry me; |
486 | struct MapEntry *n; | ||
487 | 721 | ||
488 | count = 0; | 722 | count = 0; |
489 | n = map->map[idx_of (map, key)]; | 723 | me = map->map[idx_of (map, key)]; |
490 | while (NULL != (e = n)) | 724 | if (map->use_small_entries) |
725 | { | ||
726 | struct SmallMapEntry *sme; | ||
727 | struct SmallMapEntry *nxt; | ||
728 | |||
729 | nxt = me.sme; | ||
730 | while (NULL != (sme = nxt)) | ||
731 | { | ||
732 | nxt = sme->next; | ||
733 | if (0 != memcmp (key, sme->key, sizeof (struct GNUNET_HashCode))) | ||
734 | continue; | ||
735 | if ((it != NULL) && (GNUNET_OK != it (it_cls, key, sme->value))) | ||
736 | return GNUNET_SYSERR; | ||
737 | count++; | ||
738 | } | ||
739 | } | ||
740 | else | ||
491 | { | 741 | { |
492 | n = e->next; | 742 | struct BigMapEntry *bme; |
493 | if (0 != memcmp (key, &e->key, sizeof (struct GNUNET_HashCode))) | 743 | struct BigMapEntry *nxt; |
494 | continue; | 744 | |
495 | if ((it != NULL) && (GNUNET_OK != it (it_cls, key, e->value))) | 745 | nxt = me.bme; |
496 | return GNUNET_SYSERR; | 746 | while (NULL != (bme = nxt)) |
497 | count++; | 747 | { |
748 | nxt = bme->next; | ||
749 | if (0 != memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode))) | ||
750 | continue; | ||
751 | if ((it != NULL) && (GNUNET_OK != it (it_cls, key, bme->value))) | ||
752 | return GNUNET_SYSERR; | ||
753 | count++; | ||
754 | } | ||
498 | } | 755 | } |
499 | return count; | 756 | return count; |
500 | } | 757 | } |