aboutsummaryrefslogtreecommitdiff
path: root/src/util/container_multihashmap32.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/util/container_multihashmap32.c')
-rw-r--r--src/util/container_multihashmap32.c169
1 files changed, 110 insertions, 59 deletions
diff --git a/src/util/container_multihashmap32.c b/src/util/container_multihashmap32.c
index daf5059b6..72940489e 100644
--- a/src/util/container_multihashmap32.c
+++ b/src/util/container_multihashmap32.c
@@ -28,6 +28,15 @@
28 28
29#define LOG(kind,...) GNUNET_log_from (kind, "util-container-multihashmap32", __VA_ARGS__) 29#define LOG(kind,...) GNUNET_log_from (kind, "util-container-multihashmap32", __VA_ARGS__)
30 30
31
32/**
33 * Maximum recursion depth for callbacks of
34 * #GNUNET_CONTAINER_multihashmap_get_multiple() themselves
35 * again calling #GNUNET_CONTAINER_multihashmap_get_multiple().
36 * Should be totally excessive, but if violated we die.
37 */
38#define NEXT_CACHE_SIZE 16
39
31/** 40/**
32 * An entry in the hash map. 41 * An entry in the hash map.
33 */ 42 */
@@ -68,7 +77,7 @@ struct GNUNET_CONTAINER_MultiHashMap32
68 unsigned int size; 77 unsigned int size;
69 78
70 /** 79 /**
71 * Length of the "map" array. 80 * Length of the @e map array.
72 */ 81 */
73 unsigned int map_length; 82 unsigned int map_length;
74 83
@@ -77,6 +86,19 @@ struct GNUNET_CONTAINER_MultiHashMap32
77 * to the map, so that iterators can check if they are still valid. 86 * to the map, so that iterators can check if they are still valid.
78 */ 87 */
79 unsigned int modification_counter; 88 unsigned int modification_counter;
89
90 /**
91 * Map entries indicating iteration positions currently
92 * in use by #GNUNET_CONTAINER_multihashmap_get_multiple().
93 * Only used up to @e next_cache_off.
94 */
95 struct MapEntry *next_cache[NEXT_CACHE_SIZE];
96
97 /**
98 * Offset of @e next_cache entries in use, must be smaller
99 * than #NEXT_CACHE_SIZE.
100 */
101 unsigned int next_cache_off;
80}; 102};
81 103
82 104
@@ -87,7 +109,7 @@ struct GNUNET_CONTAINER_MultiHashMap32
87struct GNUNET_CONTAINER_MultiHashMap32Iterator 109struct GNUNET_CONTAINER_MultiHashMap32Iterator
88{ 110{
89 /** 111 /**
90 * Position in the bucket 'idx' 112 * Position in the bucket @e idx
91 */ 113 */
92 struct MapEntry *me; 114 struct MapEntry *me;
93 115
@@ -122,7 +144,8 @@ GNUNET_CONTAINER_multihashmap32_create (unsigned int len)
122 144
123 GNUNET_assert (len > 0); 145 GNUNET_assert (len > 0);
124 ret = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap32); 146 ret = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap32);
125 ret->map = GNUNET_malloc (len * sizeof (struct MapEntry *)); 147 ret->map = GNUNET_new_array (len,
148 struct MapEntry *);
126 ret->map_length = len; 149 ret->map_length = len;
127 return ret; 150 return ret;
128} 151}
@@ -135,13 +158,11 @@ GNUNET_CONTAINER_multihashmap32_create (unsigned int len)
135 * @param map the map 158 * @param map the map
136 */ 159 */
137void 160void
138GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32 161GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32 *map)
139 *map)
140{ 162{
141 unsigned int i;
142 struct MapEntry *e; 163 struct MapEntry *e;
143 164
144 for (i = 0; i < map->map_length; i++) 165 for (unsigned int i = 0; i < map->map_length; i++)
145 { 166 {
146 while (NULL != (e = map->map[i])) 167 while (NULL != (e = map->map[i]))
147 { 168 {
@@ -165,7 +186,7 @@ static unsigned int
165idx_of (const struct GNUNET_CONTAINER_MultiHashMap32 *m, 186idx_of (const struct GNUNET_CONTAINER_MultiHashMap32 *m,
166 const uint32_t key) 187 const uint32_t key)
167{ 188{
168 GNUNET_assert (m != NULL); 189 GNUNET_assert (NULL != m);
169 return ((unsigned int) key) % m->map_length; 190 return ((unsigned int) key) % m->map_length;
170} 191}
171 192
@@ -177,8 +198,7 @@ idx_of (const struct GNUNET_CONTAINER_MultiHashMap32 *m,
177 * @return the number of key value pairs 198 * @return the number of key value pairs
178 */ 199 */
179unsigned int 200unsigned int
180GNUNET_CONTAINER_multihashmap32_size (const struct 201GNUNET_CONTAINER_multihashmap32_size (const struct GNUNET_CONTAINER_MultiHashMap32 *map)
181 GNUNET_CONTAINER_MultiHashMap32 *map)
182{ 202{
183 return map->size; 203 return map->size;
184} 204}
@@ -195,14 +215,13 @@ GNUNET_CONTAINER_multihashmap32_size (const struct
195 * key-value pairs with value NULL 215 * key-value pairs with value NULL
196 */ 216 */
197void * 217void *
198GNUNET_CONTAINER_multihashmap32_get (const struct 218GNUNET_CONTAINER_multihashmap32_get (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
199 GNUNET_CONTAINER_MultiHashMap32 *map,
200 uint32_t key) 219 uint32_t key)
201{ 220{
202 struct MapEntry *e; 221 struct MapEntry *e;
203 222
204 e = map->map[idx_of (map, key)]; 223 e = map->map[idx_of (map, key)];
205 while (e != NULL) 224 while (NULL != e)
206 { 225 {
207 if (key == e->key) 226 if (key == e->key)
208 return e->value; 227 return e->value;
@@ -222,37 +241,61 @@ GNUNET_CONTAINER_multihashmap32_get (const struct
222 * #GNUNET_SYSERR if it aborted iteration 241 * #GNUNET_SYSERR if it aborted iteration
223 */ 242 */
224int 243int
225GNUNET_CONTAINER_multihashmap32_iterate (const struct 244GNUNET_CONTAINER_multihashmap32_iterate (struct GNUNET_CONTAINER_MultiHashMap32 *map,
226 GNUNET_CONTAINER_MultiHashMap32 *map, 245 GNUNET_CONTAINER_HashMapIterator32 it,
227 GNUNET_CONTAINER_HashMapIterator32 it,
228 void *it_cls) 246 void *it_cls)
229{ 247{
230 int count; 248 int count;
231 unsigned int i; 249 struct MapEntry **ce;
232 struct MapEntry *e;
233 struct MapEntry *n;
234 250
235 count = 0; 251 count = 0;
236 GNUNET_assert (NULL != map); 252 GNUNET_assert (NULL != map);
237 for (i = 0; i < map->map_length; i++) 253 ce = &map->next_cache[map->next_cache_off];
254 GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
255 for (unsigned int i = 0; i < map->map_length; i++)
238 { 256 {
239 n = map->map[i]; 257 struct MapEntry *e;
240 while (NULL != (e = n)) 258
259 *ce = map->map[i];
260 while (NULL != (e = *ce))
241 { 261 {
242 n = e->next; 262 *ce = e->next;
243 if (NULL != it) 263 if (NULL != it)
244 { 264 {
245 if (GNUNET_OK != it (it_cls, e->key, e->value)) 265 if (GNUNET_OK != it (it_cls,
266 e->key,
267 e->value))
268 {
269 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
246 return GNUNET_SYSERR; 270 return GNUNET_SYSERR;
271 }
247 } 272 }
248 count++; 273 count++;
249 } 274 }
250 } 275 }
276 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
251 return count; 277 return count;
252} 278}
253 279
254 280
255/** 281/**
282 * We are about to free() the @a bme, make sure it is not in
283 * the list of next values for any iterator in the @a map's next_cache.
284 *
285 * @param map the map to check
286 * @param bme the entry that is about to be free'd
287 */
288static void
289update_next_cache (struct GNUNET_CONTAINER_MultiHashMap32 *map,
290 const struct MapEntry *me)
291{
292 for (unsigned int i=0;i<map->next_cache_off;i++)
293 if (map->next_cache[i] == me)
294 map->next_cache[i] = me->next;
295}
296
297
298/**
256 * Remove the given key-value pair from the map. Note that if the 299 * Remove the given key-value pair from the map. Note that if the
257 * key-value pair is in the map multiple times, only one of the pairs 300 * key-value pair is in the map multiple times, only one of the pairs
258 * will be removed. 301 * will be removed.
@@ -260,13 +303,13 @@ GNUNET_CONTAINER_multihashmap32_iterate (const struct
260 * @param map the map 303 * @param map the map
261 * @param key key of the key-value pair 304 * @param key key of the key-value pair
262 * @param value value of the key-value pair 305 * @param value value of the key-value pair
263 * @return GNUNET_YES on success, GNUNET_NO if the key-value pair 306 * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
264 * is not in the map 307 * is not in the map
265 */ 308 */
266int 309int
267GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 310GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 *map,
268 *map, 311 uint32_t key,
269 uint32_t key, const void *value) 312 const void *value)
270{ 313{
271 struct MapEntry *e; 314 struct MapEntry *e;
272 struct MapEntry *p; 315 struct MapEntry *p;
@@ -285,6 +328,8 @@ GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32
285 map->map[i] = e->next; 328 map->map[i] = e->next;
286 else 329 else
287 p->next = e->next; 330 p->next = e->next;
331 update_next_cache (map,
332 e);
288 GNUNET_free (e); 333 GNUNET_free (e);
289 map->size--; 334 map->size--;
290 return GNUNET_YES; 335 return GNUNET_YES;
@@ -305,9 +350,7 @@ GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32
305 * @return number of values removed 350 * @return number of values removed
306 */ 351 */
307int 352int
308GNUNET_CONTAINER_multihashmap32_remove_all (struct 353GNUNET_CONTAINER_multihashmap32_remove_all (struct GNUNET_CONTAINER_MultiHashMap32 *map,
309 GNUNET_CONTAINER_MultiHashMap32
310 *map,
311 uint32_t key) 354 uint32_t key)
312{ 355{
313 struct MapEntry *e; 356 struct MapEntry *e;
@@ -329,6 +372,8 @@ GNUNET_CONTAINER_multihashmap32_remove_all (struct
329 map->map[i] = e->next; 372 map->map[i] = e->next;
330 else 373 else
331 p->next = e->next; 374 p->next = e->next;
375 update_next_cache (map,
376 e);
332 GNUNET_free (e); 377 GNUNET_free (e);
333 map->size--; 378 map->size--;
334 if (p == NULL) 379 if (p == NULL)
@@ -353,12 +398,11 @@ GNUNET_CONTAINER_multihashmap32_remove_all (struct
353 * 398 *
354 * @param map the map 399 * @param map the map
355 * @param key the key to test if a value exists for it 400 * @param key the key to test if a value exists for it
356 * @return GNUNET_YES if such a value exists, 401 * @return #GNUNET_YES if such a value exists,
357 * GNUNET_NO if not 402 * #GNUNET_NO if not
358 */ 403 */
359int 404int
360GNUNET_CONTAINER_multihashmap32_contains (const struct 405GNUNET_CONTAINER_multihashmap32_contains (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
361 GNUNET_CONTAINER_MultiHashMap32 *map,
362 uint32_t key) 406 uint32_t key)
363{ 407{
364 struct MapEntry *e; 408 struct MapEntry *e;
@@ -381,13 +425,11 @@ GNUNET_CONTAINER_multihashmap32_contains (const struct
381 * @param map the map 425 * @param map the map
382 * @param key the key to test if a value exists for it 426 * @param key the key to test if a value exists for it
383 * @param value value to test for 427 * @param value value to test for
384 * @return GNUNET_YES if such a value exists, 428 * @return #GNUNET_YES if such a value exists,
385 * GNUNET_NO if not 429 * #GNUNET_NO if not
386 */ 430 */
387int 431int
388GNUNET_CONTAINER_multihashmap32_contains_value (const struct 432GNUNET_CONTAINER_multihashmap32_contains_value (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
389 GNUNET_CONTAINER_MultiHashMap32
390 *map,
391 uint32_t key, 433 uint32_t key,
392 const void *value) 434 const void *value)
393{ 435{
@@ -418,17 +460,17 @@ grow (struct GNUNET_CONTAINER_MultiHashMap32 *map)
418 unsigned int old_len; 460 unsigned int old_len;
419 unsigned int new_len; 461 unsigned int new_len;
420 unsigned int idx; 462 unsigned int idx;
421 unsigned int i;
422 463
423 map->modification_counter++; 464 map->modification_counter++;
424 465
425 old_map = map->map; 466 old_map = map->map;
426 old_len = map->map_length; 467 old_len = map->map_length;
427 new_len = old_len * 2; 468 new_len = old_len * 2;
428 new_map = GNUNET_malloc (sizeof (struct MapEntry *) * new_len); 469 new_map = GNUNET_new_array (new_len,
470 struct MapEntry *);
429 map->map_length = new_len; 471 map->map_length = new_len;
430 map->map = new_map; 472 map->map = new_map;
431 for (i = 0; i < old_len; i++) 473 for (unsigned int i = 0; i < old_len; i++)
432 { 474 {
433 while (NULL != (e = old_map[i])) 475 while (NULL != (e = old_map[i]))
434 { 476 {
@@ -449,9 +491,9 @@ grow (struct GNUNET_CONTAINER_MultiHashMap32 *map)
449 * @param key key to use 491 * @param key key to use
450 * @param value value to use 492 * @param value value to use
451 * @param opt options for put 493 * @param opt options for put
452 * @return GNUNET_OK on success, 494 * @return #GNUNET_OK on success,
453 * GNUNET_NO if a value was replaced (with REPLACE) 495 * #GNUNET_NO if a value was replaced (with REPLACE)
454 * GNUNET_SYSERR if UNIQUE_ONLY was the option and the 496 * #GNUNET_SYSERR if UNIQUE_ONLY was the option and the
455 * value already exists 497 * value already exists
456 */ 498 */
457int 499int
@@ -501,32 +543,41 @@ GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32
501 * @param map the map 543 * @param map the map
502 * @param key key that the entries must correspond to 544 * @param key key that the entries must correspond to
503 * @param it function to call on each entry 545 * @param it function to call on each entry
504 * @param it_cls extra argument to it 546 * @param it_cls extra argument to @a it
505 * @return the number of key value pairs processed, 547 * @return the number of key value pairs processed,
506 * GNUNET_SYSERR if it aborted iteration 548 * GNUNET_SYSERR if it aborted iteration
507 */ 549 */
508int 550int
509GNUNET_CONTAINER_multihashmap32_get_multiple (const struct 551GNUNET_CONTAINER_multihashmap32_get_multiple (struct GNUNET_CONTAINER_MultiHashMap32 *map,
510 GNUNET_CONTAINER_MultiHashMap32 552 uint32_t key,
511 *map, uint32_t key, 553 GNUNET_CONTAINER_HashMapIterator32 it,
512 GNUNET_CONTAINER_HashMapIterator32 554 void *it_cls)
513 it, void *it_cls)
514{ 555{
515 int count; 556 int count;
516 struct MapEntry *e; 557 struct MapEntry *e;
517 struct MapEntry *n; 558 struct MapEntry **ce;
518 559
519 count = 0; 560 count = 0;
520 n = map->map[idx_of (map, key)]; 561 ce = &map->next_cache[map->next_cache_off];
521 while (NULL != (e = n)) 562 GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
563
564 *ce = map->map[idx_of (map, key)];
565 while (NULL != (e = *ce))
522 { 566 {
523 n = e->next; 567 *ce = e->next;
524 if (key != e->key) 568 if (key != e->key)
525 continue; 569 continue;
526 if ((it != NULL) && (GNUNET_OK != it (it_cls, key, e->value))) 570 if ( (NULL != it) &&
527 return GNUNET_SYSERR; 571 (GNUNET_OK != it (it_cls,
572 key,
573 e->value)) )
574 {
575 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
576 return GNUNET_SYSERR;
577 }
528 count++; 578 count++;
529 } 579 }
580 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
530 return count; 581 return count;
531} 582}
532 583
@@ -541,7 +592,7 @@ GNUNET_CONTAINER_multihashmap32_get_multiple (const struct
541 * result in skipped or repeated elements. 592 * result in skipped or repeated elements.
542 * 593 *
543 * @param map the map to create an iterator for 594 * @param map the map to create an iterator for
544 * @return an iterator over the given multihashmap 'map' 595 * @return an iterator over the given multihashmap @a map
545 */ 596 */
546struct GNUNET_CONTAINER_MultiHashMap32Iterator * 597struct GNUNET_CONTAINER_MultiHashMap32Iterator *
547GNUNET_CONTAINER_multihashmap32_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap32 *map) 598GNUNET_CONTAINER_multihashmap32_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap32 *map)