aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/include/gnunet_container_lib.h269
-rw-r--r--src/include/gnunet_crypto_lib.h13
-rw-r--r--src/util/Makefile.am1
-rw-r--r--src/util/container_multishortmap.c964
4 files changed, 1246 insertions, 1 deletions
diff --git a/src/include/gnunet_container_lib.h b/src/include/gnunet_container_lib.h
index 075c0822a..c99b911a1 100644
--- a/src/include/gnunet_container_lib.h
+++ b/src/include/gnunet_container_lib.h
@@ -1285,6 +1285,275 @@ GNUNET_CONTAINER_multipeermap_get_random (const struct GNUNET_CONTAINER_MultiPee
1285 void *it_cls); 1285 void *it_cls);
1286 1286
1287 1287
1288/* ***************** Version of Multihashmap for short hashes ****************** */
1289
1290/**
1291 * @ingroup hashmap
1292 * Iterator over hash map entries.
1293 *
1294 * @param cls closure
1295 * @param key current public key
1296 * @param value value in the hash map
1297 * @return #GNUNET_YES if we should continue to
1298 * iterate,
1299 * #GNUNET_NO if not.
1300 */
1301typedef int
1302(*GNUNET_CONTAINER_ShortmapIterator) (void *cls,
1303 const struct GNUNET_PeerIdentity *key,
1304 void *value);
1305
1306
1307/**
1308 * Hash map from peer identities to values.
1309 */
1310struct GNUNET_CONTAINER_MultiShortmap;
1311
1312
1313/**
1314 * @ingroup hashmap
1315 * Create a multi peer map (hash map for public keys of peers).
1316 *
1317 * @param len initial size (map will grow as needed)
1318 * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default;
1319 * #GNUNET_YES means that on 'put', the 'key' does not have
1320 * to be copied as the destination of the pointer is
1321 * guaranteed to be life as long as the value is stored in
1322 * the hashmap. This can significantly reduce memory
1323 * consumption, but of course is also a recipie for
1324 * heap corruption if the assumption is not true. Only
1325 * use this if (1) memory use is important in this case and
1326 * (2) you have triple-checked that the invariant holds
1327 * @return NULL on error
1328 */
1329struct GNUNET_CONTAINER_MultiShortmap *
1330GNUNET_CONTAINER_multishortmap_create (unsigned int len,
1331 int do_not_copy_keys);
1332
1333
1334/**
1335 * @ingroup hashmap
1336 * Destroy a hash map. Will not free any values
1337 * stored in the hash map!
1338 *
1339 * @param map the map
1340 */
1341void
1342GNUNET_CONTAINER_multishortmap_destroy (struct GNUNET_CONTAINER_MultiShortmap *map);
1343
1344
1345/**
1346 * @ingroup hashmap
1347 * Given a key find a value in the map matching the key.
1348 *
1349 * @param map the map
1350 * @param key what to look for
1351 * @return NULL if no value was found; note that
1352 * this is indistinguishable from values that just
1353 * happen to be NULL; use "contains" to test for
1354 * key-value pairs with value NULL
1355 */
1356void *
1357GNUNET_CONTAINER_multishortmap_get (const struct GNUNET_CONTAINER_MultiShortmap *map,
1358 const struct GNUNET_PeerIdentity *key);
1359
1360
1361/**
1362 * @ingroup hashmap
1363 * Remove the given key-value pair from the map. Note that if the
1364 * key-value pair is in the map multiple times, only one of the pairs
1365 * will be removed.
1366 *
1367 * @param map the map
1368 * @param key key of the key-value pair
1369 * @param value value of the key-value pair
1370 * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
1371 * is not in the map
1372 */
1373int
1374GNUNET_CONTAINER_multishortmap_remove (struct GNUNET_CONTAINER_MultiShortmap *map,
1375 const struct GNUNET_PeerIdentity * key,
1376 const void *value);
1377
1378/**
1379 * @ingroup hashmap
1380 * Remove all entries for the given key from the map.
1381 * Note that the values would not be "freed".
1382 *
1383 * @param map the map
1384 * @param key identifies values to be removed
1385 * @return number of values removed
1386 */
1387int
1388GNUNET_CONTAINER_multishortmap_remove_all (struct GNUNET_CONTAINER_MultiShortmap *map,
1389 const struct GNUNET_PeerIdentity *key);
1390
1391
1392/**
1393 * @ingroup hashmap
1394 * Check if the map contains any value under the given
1395 * key (including values that are NULL).
1396 *
1397 * @param map the map
1398 * @param key the key to test if a value exists for it
1399 * @return #GNUNET_YES if such a value exists,
1400 * #GNUNET_NO if not
1401 */
1402int
1403GNUNET_CONTAINER_multishortmap_contains (const struct GNUNET_CONTAINER_MultiShortmap *map,
1404 const struct GNUNET_PeerIdentity *key);
1405
1406
1407/**
1408 * @ingroup hashmap
1409 * Check if the map contains the given value under the given
1410 * key.
1411 *
1412 * @param map the map
1413 * @param key the key to test if a value exists for it
1414 * @param value value to test for
1415 * @return #GNUNET_YES if such a value exists,
1416 * #GNUNET_NO if not
1417 */
1418int
1419GNUNET_CONTAINER_multishortmap_contains_value (const struct GNUNET_CONTAINER_MultiShortmap *map,
1420 const struct GNUNET_PeerIdentity * key,
1421 const void *value);
1422
1423
1424/**
1425 * @ingroup hashmap
1426 * Store a key-value pair in the map.
1427 *
1428 * @param map the map
1429 * @param key key to use
1430 * @param value value to use
1431 * @param opt options for put
1432 * @return #GNUNET_OK on success,
1433 * #GNUNET_NO if a value was replaced (with REPLACE)
1434 * #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
1435 * value already exists
1436 */
1437int
1438GNUNET_CONTAINER_multishortmap_put (struct GNUNET_CONTAINER_MultiShortmap *map,
1439 const struct GNUNET_PeerIdentity *key,
1440 void *value,
1441 enum GNUNET_CONTAINER_MultiHashMapOption opt);
1442
1443
1444/**
1445 * @ingroup hashmap
1446 * Get the number of key-value pairs in the map.
1447 *
1448 * @param map the map
1449 * @return the number of key value pairs
1450 */
1451unsigned int
1452GNUNET_CONTAINER_multishortmap_size (const struct GNUNET_CONTAINER_MultiShortmap *map);
1453
1454
1455/**
1456 * @ingroup hashmap
1457 * Iterate over all entries in the map.
1458 *
1459 * @param map the map
1460 * @param it function to call on each entry
1461 * @param it_cls extra argument to @a it
1462 * @return the number of key value pairs processed,
1463 * #GNUNET_SYSERR if it aborted iteration
1464 */
1465int
1466GNUNET_CONTAINER_multishortmap_iterate (const struct GNUNET_CONTAINER_MultiShortmap *map,
1467 GNUNET_CONTAINER_ShortmapIterator it,
1468 void *it_cls);
1469
1470
1471struct GNUNET_CONTAINER_MultiShortmapIterator;
1472
1473
1474/**
1475 * @ingroup hashmap
1476 * Create an iterator for a multihashmap.
1477 * The iterator can be used to retrieve all the elements in the multihashmap
1478 * one by one, without having to handle all elements at once (in contrast to
1479 * #GNUNET_CONTAINER_multishortmap_iterate). Note that the iterator can not be
1480 * used anymore if elements have been removed from @a map after the creation of
1481 * the iterator, or 'map' has been destroyed. Adding elements to @a map may
1482 * result in skipped or repeated elements.
1483 *
1484 * @param map the map to create an iterator for
1485 * @return an iterator over the given multihashmap @a map
1486 */
1487struct GNUNET_CONTAINER_MultiShortmapIterator *
1488GNUNET_CONTAINER_multishortmap_iterator_create (const struct GNUNET_CONTAINER_MultiShortmap *map);
1489
1490
1491/**
1492 * @ingroup hashmap
1493 * Retrieve the next element from the hash map at the iterator's
1494 * position. If there are no elements left, #GNUNET_NO is returned,
1495 * and @a key and @a value are not modified. This operation is only
1496 * allowed if no elements have been removed from the multihashmap
1497 * since the creation of @a iter, and the map has not been destroyed.
1498 * Adding elements may result in repeating or skipping elements.
1499 *
1500 * @param iter the iterator to get the next element from
1501 * @param key pointer to store the key in, can be NULL
1502 * @param value pointer to store the value in, can be NULL
1503 * @return #GNUNET_YES we returned an element,
1504 * #GNUNET_NO if we are out of elements
1505 */
1506int
1507GNUNET_CONTAINER_multishortmap_iterator_next (struct GNUNET_CONTAINER_MultiShortmapIterator *iter,
1508 struct GNUNET_PeerIdentity *key,
1509 const void **value);
1510
1511
1512/**
1513 * @ingroup hashmap
1514 * Destroy a multishortmap iterator.
1515 *
1516 * @param iter the iterator to destroy
1517 */
1518void
1519GNUNET_CONTAINER_multishortmap_iterator_destroy (struct GNUNET_CONTAINER_MultiShortmapIterator *iter);
1520
1521
1522/**
1523 * @ingroup hashmap
1524 * Iterate over all entries in the map that match a particular key.
1525 *
1526 * @param map the map
1527 * @param key public key that the entries must correspond to
1528 * @param it function to call on each entry
1529 * @param it_cls extra argument to @a it
1530 * @return the number of key value pairs processed,
1531 * #GNUNET_SYSERR if it aborted iteration
1532 */
1533int
1534GNUNET_CONTAINER_multishortmap_get_multiple (const struct GNUNET_CONTAINER_MultiShortmap *map,
1535 const struct GNUNET_PeerIdentity *key,
1536 GNUNET_CONTAINER_ShortmapIterator it,
1537 void *it_cls);
1538
1539
1540/**
1541 * @ingroup hashmap
1542 * Call @a it on a random value from the map, or not at all
1543 * if the map is empty. Note that this function has linear
1544 * complexity (in the size of the map).
1545 *
1546 * @param map the map
1547 * @param it function to call on a random entry
1548 * @param it_cls extra argument to @a it
1549 * @return the number of key value pairs processed, zero or one.
1550 */
1551unsigned int
1552GNUNET_CONTAINER_multishortmap_get_random (const struct GNUNET_CONTAINER_MultiShortmap *map,
1553 GNUNET_CONTAINER_ShortmapIterator it,
1554 void *it_cls);
1555
1556
1288/* Version of multihashmap with 32 bit keys */ 1557/* Version of multihashmap with 32 bit keys */
1289 1558
1290/** 1559/**
diff --git a/src/include/gnunet_crypto_lib.h b/src/include/gnunet_crypto_lib.h
index 8002b7710..b6875c5cf 100644
--- a/src/include/gnunet_crypto_lib.h
+++ b/src/include/gnunet_crypto_lib.h
@@ -66,7 +66,7 @@ struct GNUNET_PeerIdentity;
66 66
67 67
68/** 68/**
69 * @brief A 512-bit hashcode 69 * @brief A 512-bit hashcode. These are the default length for GNUnet, using SHA-512.
70 */ 70 */
71struct GNUNET_HashCode 71struct GNUNET_HashCode
72{ 72{
@@ -74,6 +74,17 @@ struct GNUNET_HashCode
74}; 74};
75 75
76 76
77
78/**
79 * @brief A 256-bit hashcode. Used under special conditions, like when space
80 * is critical and security is not impacted by it.
81 */
82struct GNUNET_ShortHashCode
83{
84 uint32_t bits[256 / 8 / sizeof (uint32_t)]; /* = 8 */
85};
86
87
77/** 88/**
78 * Maximum length of an ECC signature. 89 * Maximum length of an ECC signature.
79 * Note: round up to multiple of 8 minus 2 for alignment. 90 * Note: round up to multiple of 8 minus 2 for alignment.
diff --git a/src/util/Makefile.am b/src/util/Makefile.am
index c7f069206..f49aee17f 100644
--- a/src/util/Makefile.am
+++ b/src/util/Makefile.am
@@ -70,6 +70,7 @@ libgnunetutil_la_SOURCES = \
70 container_heap.c \ 70 container_heap.c \
71 container_meta_data.c \ 71 container_meta_data.c \
72 container_multihashmap.c \ 72 container_multihashmap.c \
73 container_multishortmap.c \
73 container_multipeermap.c \ 74 container_multipeermap.c \
74 container_multihashmap32.c \ 75 container_multihashmap32.c \
75 crypto_symmetric.c \ 76 crypto_symmetric.c \
diff --git a/src/util/container_multishortmap.c b/src/util/container_multishortmap.c
new file mode 100644
index 000000000..71d1073b0
--- /dev/null
+++ b/src/util/container_multishortmap.c
@@ -0,0 +1,964 @@
1/*
2 This file is part of GNUnet.
3 Copyright (C) 2008, 2012 GNUnet e.V.
4
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
7 by the Free Software Foundation; either version 3, or (at your
8 option) any later version.
9
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18 Boston, MA 02110-1301, USA.
19*/
20/**
21 * @file util/container_multishortmap.c
22 * @brief hash map where the same key may be present multiple times
23 * @author Christian Grothoff
24 */
25
26#include "platform.h"
27#include "gnunet_util_lib.h"
28
29#define LOG(kind,...) GNUNET_log_from (kind, "util", __VA_ARGS__)
30
31/**
32 * An entry in the hash map with the full key.
33 */
34struct BigMapEntry
35{
36
37 /**
38 * Value of the entry.
39 */
40 void *value;
41
42 /**
43 * If there is a hash collision, we create a linked list.
44 */
45 struct BigMapEntry *next;
46
47 /**
48 * Key for the entry.
49 */
50 struct GNUNET_PeerIdentity key;
51
52};
53
54
55/**
56 * An entry in the hash map with just a pointer to the key.
57 */
58struct SmallMapEntry
59{
60
61 /**
62 * Value of the entry.
63 */
64 void *value;
65
66 /**
67 * If there is a hash collision, we create a linked list.
68 */
69 struct SmallMapEntry *next;
70
71 /**
72 * Key for the entry.
73 */
74 const struct GNUNET_PeerIdentity *key;
75
76};
77
78
79/**
80 * Entry in the map.
81 */
82union MapEntry
83{
84 /**
85 * Variant used if map entries only contain a pointer to the key.
86 */
87 struct SmallMapEntry *sme;
88
89 /**
90 * Variant used if map entries contain the full key.
91 */
92 struct BigMapEntry *bme;
93};
94
95
96/**
97 * Internal representation of the hash map.
98 */
99struct GNUNET_CONTAINER_MultiShortmap
100{
101 /**
102 * All of our buckets.
103 */
104 union MapEntry *map;
105
106 /**
107 * Number of entries in the map.
108 */
109 unsigned int size;
110
111 /**
112 * Length of the "map" array.
113 */
114 unsigned int map_length;
115
116 /**
117 * GNUNET_NO if the map entries are of type 'struct BigMapEntry',
118 * GNUNET_YES if the map entries are of type 'struct SmallMapEntry'.
119 */
120 int use_small_entries;
121
122 /**
123 * Counts the destructive modifications (grow, remove)
124 * to the map, so that iterators can check if they are still valid.
125 */
126 unsigned int modification_counter;
127};
128
129
130/**
131 * Cursor into a multishortmap.
132 * Allows to enumerate elements asynchronously.
133 */
134struct GNUNET_CONTAINER_MultiShortmapIterator
135{
136 /**
137 * Position in the bucket 'idx'
138 */
139 union MapEntry me;
140
141 /**
142 * Current bucket index.
143 */
144 unsigned int idx;
145
146 /**
147 * Modification counter as observed on the map when the iterator
148 * was created.
149 */
150 unsigned int modification_counter;
151
152 /**
153 * Map that we are iterating over.
154 */
155 const struct GNUNET_CONTAINER_MultiShortmap *map;
156};
157
158
159/**
160 * Create a multi hash map.
161 *
162 * @param len initial size (map will grow as needed)
163 * @param do_not_copy_keys GNUNET_NO is always safe and should be used by default;
164 * GNUNET_YES means that on 'put', the 'key' does not have
165 * to be copied as the destination of the pointer is
166 * guaranteed to be life as long as the value is stored in
167 * the hashmap. This can significantly reduce memory
168 * consumption, but of course is also a recipie for
169 * heap corruption if the assumption is not true. Only
170 * use this if (1) memory use is important in this case and
171 * (2) you have triple-checked that the invariant holds
172 * @return NULL on error
173 */
174struct GNUNET_CONTAINER_MultiShortmap *
175GNUNET_CONTAINER_multishortmap_create (unsigned int len,
176 int do_not_copy_keys)
177{
178 struct GNUNET_CONTAINER_MultiShortmap *map;
179
180 GNUNET_assert (len > 0);
181 map = GNUNET_new (struct GNUNET_CONTAINER_MultiShortmap);
182 map->map = GNUNET_malloc (len * sizeof (union MapEntry));
183 map->map_length = len;
184 map->use_small_entries = do_not_copy_keys;
185 return map;
186}
187
188
189/**
190 * Destroy a hash map. Will not free any values
191 * stored in the hash map!
192 *
193 * @param map the map
194 */
195void
196GNUNET_CONTAINER_multishortmap_destroy (struct GNUNET_CONTAINER_MultiShortmap
197 *map)
198{
199 unsigned int i;
200 union MapEntry me;
201
202 for (i = 0; i < map->map_length; i++)
203 {
204 me = map->map[i];
205 if (map->use_small_entries)
206 {
207 struct SmallMapEntry *sme;
208 struct SmallMapEntry *nxt;
209
210 nxt = me.sme;
211 while (NULL != (sme = nxt))
212 {
213 nxt = sme->next;
214 GNUNET_free (sme);
215 }
216 me.sme = NULL;
217 }
218 else
219 {
220 struct BigMapEntry *bme;
221 struct BigMapEntry *nxt;
222
223 nxt = me.bme;
224 while (NULL != (bme = nxt))
225 {
226 nxt = bme->next;
227 GNUNET_free (bme);
228 }
229 me.bme = NULL;
230 }
231 }
232 GNUNET_free (map->map);
233 GNUNET_free (map);
234}
235
236
237/**
238 * Compute the index of the bucket for the given key.
239 *
240 * @param map hash map for which to compute the index
241 * @param key what key should the index be computed for
242 * @return offset into the "map" array of "map"
243 */
244static unsigned int
245idx_of (const struct GNUNET_CONTAINER_MultiShortmap *map,
246 const struct GNUNET_PeerIdentity *key)
247{
248 unsigned int kx;
249
250 GNUNET_assert (NULL != map);
251 GNUNET_memcpy (&kx, key, sizeof (kx));
252 return kx % map->map_length;
253}
254
255
256/**
257 * Get the number of key-value pairs in the map.
258 *
259 * @param map the map
260 * @return the number of key value pairs
261 */
262unsigned int
263GNUNET_CONTAINER_multishortmap_size (const struct GNUNET_CONTAINER_MultiShortmap *map)
264{
265 return map->size;
266}
267
268
269/**
270 * Given a key find a value in the map matching the key.
271 *
272 * @param map the map
273 * @param key what to look for
274 * @return NULL if no value was found; note that
275 * this is indistinguishable from values that just
276 * happen to be NULL; use "contains" to test for
277 * key-value pairs with value NULL
278 */
279void *
280GNUNET_CONTAINER_multishortmap_get (const struct GNUNET_CONTAINER_MultiShortmap *map,
281 const struct GNUNET_PeerIdentity *key)
282{
283 union MapEntry me;
284
285 me = map->map[idx_of (map, key)];
286 if (map->use_small_entries)
287 {
288 struct SmallMapEntry *sme;
289
290 for (sme = me.sme; NULL != sme; sme = sme->next)
291 if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity)))
292 return sme->value;
293 }
294 else
295 {
296 struct BigMapEntry *bme;
297
298 for (bme = me.bme; NULL != bme; bme = bme->next)
299 if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity)))
300 return bme->value;
301 }
302 return NULL;
303}
304
305
306/**
307 * Iterate over all entries in the map.
308 *
309 * @param map the map
310 * @param it function to call on each entry
311 * @param it_cls extra argument to @a it
312 * @return the number of key value pairs processed,
313 * #GNUNET_SYSERR if it aborted iteration
314 */
315int
316GNUNET_CONTAINER_multishortmap_iterate (const struct GNUNET_CONTAINER_MultiShortmap *map,
317 GNUNET_CONTAINER_ShortmapIterator it,
318 void *it_cls)
319{
320 int count;
321 unsigned int i;
322 union MapEntry me;
323 struct GNUNET_PeerIdentity kc;
324
325 count = 0;
326 GNUNET_assert (NULL != map);
327 for (i = 0; i < map->map_length; i++)
328 {
329 me = map->map[i];
330 if (map->use_small_entries)
331 {
332 struct SmallMapEntry *sme;
333 struct SmallMapEntry *nxt;
334
335 nxt = me.sme;
336 while (NULL != (sme = nxt))
337 {
338 nxt = sme->next;
339 if (NULL != it)
340 {
341 if (GNUNET_OK != it (it_cls, sme->key, sme->value))
342 return GNUNET_SYSERR;
343 }
344 count++;
345 }
346 }
347 else
348 {
349 struct BigMapEntry *bme;
350 struct BigMapEntry *nxt;
351
352 nxt = me.bme;
353 while (NULL != (bme = nxt))
354 {
355 nxt = bme->next;
356 if (NULL != it)
357 {
358 kc = bme->key;
359 if (GNUNET_OK != it (it_cls, &kc, bme->value))
360 return GNUNET_SYSERR;
361 }
362 count++;
363 }
364 }
365 }
366 return count;
367}
368
369
370/**
371 * Remove the given key-value pair from the map. Note that if the
372 * key-value pair is in the map multiple times, only one of the pairs
373 * will be removed.
374 *
375 * @param map the map
376 * @param key key of the key-value pair
377 * @param value value of the key-value pair
378 * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
379 * is not in the map
380 */
381int
382GNUNET_CONTAINER_multishortmap_remove (struct GNUNET_CONTAINER_MultiShortmap *map,
383 const struct GNUNET_PeerIdentity *key,
384 const void *value)
385{
386 union MapEntry me;
387 unsigned int i;
388
389 map->modification_counter++;
390
391 i = idx_of (map, key);
392 me = map->map[i];
393 if (map->use_small_entries)
394 {
395 struct SmallMapEntry *sme;
396 struct SmallMapEntry *p;
397
398 p = NULL;
399 for (sme = me.sme; NULL != sme; sme = sme->next)
400 {
401 if ((0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) &&
402 (value == sme->value))
403 {
404 if (NULL == p)
405 map->map[i].sme = sme->next;
406 else
407 p->next = sme->next;
408 GNUNET_free (sme);
409 map->size--;
410 return GNUNET_YES;
411 }
412 p = sme;
413 }
414 }
415 else
416 {
417 struct BigMapEntry *bme;
418 struct BigMapEntry *p;
419
420 p = NULL;
421 for (bme = me.bme; NULL != bme; bme = bme->next)
422 {
423 if ((0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) &&
424 (value == bme->value))
425 {
426 if (NULL == p)
427 map->map[i].bme = bme->next;
428 else
429 p->next = bme->next;
430 GNUNET_free (bme);
431 map->size--;
432 return GNUNET_YES;
433 }
434 p = bme;
435 }
436 }
437 return GNUNET_NO;
438}
439
440
441/**
442 * Remove all entries for the given key from the map.
443 * Note that the values would not be "freed".
444 *
445 * @param map the map
446 * @param key identifies values to be removed
447 * @return number of values removed
448 */
449int
450GNUNET_CONTAINER_multishortmap_remove_all (struct GNUNET_CONTAINER_MultiShortmap *map,
451 const struct GNUNET_PeerIdentity *key)
452{
453 union MapEntry me;
454 unsigned int i;
455 int ret;
456
457 map->modification_counter++;
458
459 ret = 0;
460 i = idx_of (map, key);
461 me = map->map[i];
462 if (map->use_small_entries)
463 {
464 struct SmallMapEntry *sme;
465 struct SmallMapEntry *p;
466
467 p = NULL;
468 sme = me.sme;
469 while (NULL != sme)
470 {
471 if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity)))
472 {
473 if (NULL == p)
474 map->map[i].sme = sme->next;
475 else
476 p->next = sme->next;
477 GNUNET_free (sme);
478 map->size--;
479 if (NULL == p)
480 sme = map->map[i].sme;
481 else
482 sme = p->next;
483 ret++;
484 }
485 else
486 {
487 p = sme;
488 sme = sme->next;
489 }
490 }
491 }
492 else
493 {
494 struct BigMapEntry *bme;
495 struct BigMapEntry *p;
496
497 p = NULL;
498 bme = me.bme;
499 while (NULL != bme)
500 {
501 if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity)))
502 {
503 if (NULL == p)
504 map->map[i].bme = bme->next;
505 else
506 p->next = bme->next;
507 GNUNET_free (bme);
508 map->size--;
509 if (NULL == p)
510 bme = map->map[i].bme;
511 else
512 bme = p->next;
513 ret++;
514 }
515 else
516 {
517 p = bme;
518 bme = bme->next;
519 }
520 }
521 }
522 return ret;
523}
524
525
526/**
527 * Check if the map contains any value under the given
528 * key (including values that are NULL).
529 *
530 * @param map the map
531 * @param key the key to test if a value exists for it
532 * @return #GNUNET_YES if such a value exists,
533 * #GNUNET_NO if not
534 */
535int
536GNUNET_CONTAINER_multishortmap_contains (const struct GNUNET_CONTAINER_MultiShortmap *map,
537 const struct GNUNET_PeerIdentity *key)
538{
539 union MapEntry me;
540
541 me = map->map[idx_of (map, key)];
542 if (map->use_small_entries)
543 {
544 struct SmallMapEntry *sme;
545
546 for (sme = me.sme; NULL != sme; sme = sme->next)
547 if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity)))
548 return GNUNET_YES;
549 }
550 else
551 {
552 struct BigMapEntry *bme;
553
554 for (bme = me.bme; NULL != bme; bme = bme->next)
555 if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity)))
556 return GNUNET_YES;
557 }
558 return GNUNET_NO;
559}
560
561
562/**
563 * Check if the map contains the given value under the given
564 * key.
565 *
566 * @param map the map
567 * @param key the key to test if a value exists for it
568 * @param value value to test for
569 * @return #GNUNET_YES if such a value exists,
570 * #GNUNET_NO if not
571 */
572int
573GNUNET_CONTAINER_multishortmap_contains_value (const struct GNUNET_CONTAINER_MultiShortmap *map,
574 const struct GNUNET_PeerIdentity *key,
575 const void *value)
576{
577 union MapEntry me;
578
579 me = map->map[idx_of (map, key)];
580 if (map->use_small_entries)
581 {
582 struct SmallMapEntry *sme;
583
584 for (sme = me.sme; NULL != sme; sme = sme->next)
585 if ( (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) &&
586 (sme->value == value) )
587 return GNUNET_YES;
588 }
589 else
590 {
591 struct BigMapEntry *bme;
592
593 for (bme = me.bme; NULL != bme; bme = bme->next)
594 if ( (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) &&
595 (bme->value == value) )
596 return GNUNET_YES;
597 }
598 return GNUNET_NO;
599}
600
601
602/**
603 * Grow the given map to a more appropriate size.
604 *
605 * @param map the hash map to grow
606 */
607static void
608grow (struct GNUNET_CONTAINER_MultiShortmap *map)
609{
610 union MapEntry *old_map;
611 union MapEntry *new_map;
612 unsigned int old_len;
613 unsigned int new_len;
614 unsigned int idx;
615 unsigned int i;
616
617 map->modification_counter++;
618
619 old_map = map->map;
620 old_len = map->map_length;
621 new_len = old_len * 2;
622 new_map = GNUNET_malloc (sizeof (union MapEntry) * new_len);
623 map->map_length = new_len;
624 map->map = new_map;
625 for (i = 0; i < old_len; i++)
626 {
627 if (map->use_small_entries)
628 {
629 struct SmallMapEntry *sme;
630
631 while (NULL != (sme = old_map[i].sme))
632 {
633 old_map[i].sme = sme->next;
634 idx = idx_of (map, sme->key);
635 sme->next = new_map[idx].sme;
636 new_map[idx].sme = sme;
637 }
638 }
639 else
640 {
641 struct BigMapEntry *bme;
642
643 while (NULL != (bme = old_map[i].bme))
644 {
645 old_map[i].bme = bme->next;
646 idx = idx_of (map, &bme->key);
647 bme->next = new_map[idx].bme;
648 new_map[idx].bme = bme;
649 }
650 }
651 }
652 GNUNET_free (old_map);
653}
654
655
656/**
657 * Store a key-value pair in the map.
658 *
659 * @param map the map
660 * @param key key to use
661 * @param value value to use
662 * @param opt options for put
663 * @return #GNUNET_OK on success,
664 * #GNUNET_NO if a value was replaced (with REPLACE)
665 * #GNUNET_SYSERR if GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
666 * value already exists
667 */
668int
669GNUNET_CONTAINER_multishortmap_put (struct GNUNET_CONTAINER_MultiShortmap *map,
670 const struct GNUNET_PeerIdentity *key,
671 void *value,
672 enum GNUNET_CONTAINER_MultiHashMapOption opt)
673{
674 union MapEntry me;
675 unsigned int i;
676
677 i = idx_of (map, key);
678 if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
679 (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
680 {
681 me = map->map[i];
682 if (map->use_small_entries)
683 {
684 struct SmallMapEntry *sme;
685
686 for (sme = me.sme; NULL != sme; sme = sme->next)
687 if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity)))
688 {
689 if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
690 return GNUNET_SYSERR;
691 sme->value = value;
692 return GNUNET_NO;
693 }
694 }
695 else
696 {
697 struct BigMapEntry *bme;
698
699 for (bme = me.bme; NULL != bme; bme = bme->next)
700 if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity)))
701 {
702 if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
703 return GNUNET_SYSERR;
704 bme->value = value;
705 return GNUNET_NO;
706 }
707 }
708 }
709 if (map->size / 3 >= map->map_length / 4)
710 {
711 grow (map);
712 i = idx_of (map, key);
713 }
714 if (map->use_small_entries)
715 {
716 struct SmallMapEntry *sme;
717
718 sme = GNUNET_new (struct SmallMapEntry);
719 sme->key = key;
720 sme->value = value;
721 sme->next = map->map[i].sme;
722 map->map[i].sme = sme;
723 }
724 else
725 {
726 struct BigMapEntry *bme;
727
728 bme = GNUNET_new (struct BigMapEntry);
729 bme->key = *key;
730 bme->value = value;
731 bme->next = map->map[i].bme;
732 map->map[i].bme = bme;
733 }
734 map->size++;
735 return GNUNET_OK;
736}
737
738
739/**
740 * Iterate over all entries in the map that match a particular key.
741 *
742 * @param map the map
743 * @param key key that the entries must correspond to
744 * @param it function to call on each entry
745 * @param it_cls extra argument to @a it
746 * @return the number of key value pairs processed,
747 * #GNUNET_SYSERR if it aborted iteration
748 */
749int
750GNUNET_CONTAINER_multishortmap_get_multiple (const struct GNUNET_CONTAINER_MultiShortmap *map,
751 const struct GNUNET_PeerIdentity *key,
752 GNUNET_CONTAINER_ShortmapIterator it,
753 void *it_cls)
754{
755 int count;
756 union MapEntry me;
757
758 count = 0;
759 me = map->map[idx_of (map, key)];
760 if (map->use_small_entries)
761 {
762 struct SmallMapEntry *sme;
763 struct SmallMapEntry *nxt;
764
765 nxt = me.sme;
766 while (NULL != (sme = nxt))
767 {
768 nxt = sme->next;
769 if (0 != memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity)))
770 continue;
771 if ((it != NULL) && (GNUNET_OK != it (it_cls, key, sme->value)))
772 return GNUNET_SYSERR;
773 count++;
774 }
775 }
776 else
777 {
778 struct BigMapEntry *bme;
779 struct BigMapEntry *nxt;
780
781 nxt = me.bme;
782 while (NULL != (bme = nxt))
783 {
784 nxt = bme->next;
785 if (0 != memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity)))
786 continue;
787 if ((it != NULL) && (GNUNET_OK != it (it_cls, key, bme->value)))
788 return GNUNET_SYSERR;
789 count++;
790 }
791 }
792 return count;
793}
794
795
796/**
797 * @ingroup hashmap
798 * Call @a it on a random value from the map, or not at all
799 * if the map is empty. Note that this function has linear
800 * complexity (in the size of the map).
801 *
802 * @param map the map
803 * @param it function to call on a random entry
804 * @param it_cls extra argument to @a it
805 * @return the number of key value pairs processed, zero or one.
806 */
807unsigned int
808GNUNET_CONTAINER_multishortmap_get_random (const struct GNUNET_CONTAINER_MultiShortmap *map,
809 GNUNET_CONTAINER_ShortmapIterator it,
810 void *it_cls)
811{
812 unsigned int off;
813 unsigned int idx;
814 union MapEntry me;
815
816 if (0 == map->size)
817 return 0;
818 if (NULL == it)
819 return 1;
820 off = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE,
821 map->size);
822 for (idx = 0; idx < map->map_length; idx++)
823 {
824 me = map->map[idx];
825 if (map->use_small_entries)
826 {
827 struct SmallMapEntry *sme;
828 struct SmallMapEntry *nxt;
829
830 nxt = me.sme;
831 while (NULL != (sme = nxt))
832 {
833 nxt = sme->next;
834 if (0 == off)
835 {
836 if (GNUNET_OK != it (it_cls,
837 sme->key,
838 sme->value))
839 return GNUNET_SYSERR;
840 return 1;
841 }
842 off--;
843 }
844 }
845 else
846 {
847 struct BigMapEntry *bme;
848 struct BigMapEntry *nxt;
849
850 nxt = me.bme;
851 while (NULL != (bme = nxt))
852 {
853 nxt = bme->next;
854 if (0 == off)
855 {
856 if (GNUNET_OK != it (it_cls,
857 &bme->key, bme->value))
858 return GNUNET_SYSERR;
859 return 1;
860 }
861 off--;
862 }
863 }
864 }
865 GNUNET_break (0);
866 return GNUNET_SYSERR;
867}
868
869
870/**
871 * Create an iterator for a multishortmap.
872 * The iterator can be used to retrieve all the elements in the multishortmap
873 * one by one, without having to handle all elements at once (in contrast to
874 * #GNUNET_CONTAINER_multishortmap_iterate). Note that the iterator can not be
875 * used anymore if elements have been removed from 'map' after the creation of
876 * the iterator, or 'map' has been destroyed. Adding elements to 'map' may
877 * result in skipped or repeated elements.
878 *
879 * @param map the map to create an iterator for
880 * @return an iterator over the given multishortmap 'map'
881 */
882struct GNUNET_CONTAINER_MultiShortmapIterator *
883GNUNET_CONTAINER_multishortmap_iterator_create (const struct GNUNET_CONTAINER_MultiShortmap *map)
884{
885 struct GNUNET_CONTAINER_MultiShortmapIterator *iter;
886
887 iter = GNUNET_new (struct GNUNET_CONTAINER_MultiShortmapIterator);
888 iter->map = map;
889 iter->modification_counter = map->modification_counter;
890 iter->me = map->map[0];
891 return iter;
892}
893
894
895/**
896 * Retrieve the next element from the hash map at the iterator's position.
897 * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
898 * are not modified.
899 * This operation is only allowed if no elements have been removed from the
900 * multishortmap since the creation of 'iter', and the map has not been destroyed.
901 * Adding elements may result in repeating or skipping elements.
902 *
903 * @param iter the iterator to get the next element from
904 * @param key pointer to store the key in, can be NULL
905 * @param value pointer to store the value in, can be NULL
906 * @return #GNUNET_YES we returned an element,
907 * #GNUNET_NO if we are out of elements
908 */
909int
910GNUNET_CONTAINER_multishortmap_iterator_next (struct GNUNET_CONTAINER_MultiShortmapIterator *iter,
911 struct GNUNET_PeerIdentity *key, const void **value)
912{
913 /* make sure the map has not been modified */
914 GNUNET_assert (iter->modification_counter == iter->map->modification_counter);
915
916 /* look for the next entry, skipping empty buckets */
917 while (1)
918 {
919 if (iter->idx >= iter->map->map_length)
920 return GNUNET_NO;
921 if (GNUNET_YES == iter->map->use_small_entries)
922 {
923 if (NULL != iter->me.sme)
924 {
925 if (NULL != key)
926 *key = *iter->me.sme->key;
927 if (NULL != value)
928 *value = iter->me.sme->value;
929 iter->me.sme = iter->me.sme->next;
930 return GNUNET_YES;
931 }
932 }
933 else
934 {
935 if (NULL != iter->me.bme)
936 {
937 if (NULL != key)
938 *key = iter->me.bme->key;
939 if (NULL != value)
940 *value = iter->me.bme->value;
941 iter->me.bme = iter->me.bme->next;
942 return GNUNET_YES;
943 }
944 }
945 iter->idx += 1;
946 if (iter->idx < iter->map->map_length)
947 iter->me = iter->map->map[iter->idx];
948 }
949}
950
951
952/**
953 * Destroy a multishortmap iterator.
954 *
955 * @param iter the iterator to destroy
956 */
957void
958GNUNET_CONTAINER_multishortmap_iterator_destroy (struct GNUNET_CONTAINER_MultiShortmapIterator *iter)
959{
960 GNUNET_free (iter);
961}
962
963
964/* end of container_multishortmap.c */
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-30 09:41:27 +0000