aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/datastore/plugin_datastore_sqlite.c2
-rw-r--r--src/include/gnunet_container_lib.h303
-rw-r--r--src/util/Makefile.am7
-rw-r--r--src/util/container_multihashmap.c6
-rw-r--r--src/util/container_multihashmap32.c4
-rw-r--r--src/util/container_multipeermap.c893
-rw-r--r--src/util/test_container_multipeermap.c121
7 files changed, 1296 insertions, 40 deletions
diff --git a/src/datastore/plugin_datastore_sqlite.c b/src/datastore/plugin_datastore_sqlite.c
index 9a4b40255..bd344dbb1 100644
--- a/src/datastore/plugin_datastore_sqlite.c
+++ b/src/datastore/plugin_datastore_sqlite.c
@@ -470,7 +470,7 @@ delete_by_rowid (struct Plugin *plugin, unsigned long long rid)
470 * @param replication replication-level for the content 470 * @param replication replication-level for the content
471 * @param expiration expiration time for the content 471 * @param expiration expiration time for the content
472 * @param msg set to an error message 472 * @param msg set to an error message
473 * @return GNUNET_OK on success 473 * @return #GNUNET_OK on success
474 */ 474 */
475static int 475static int
476sqlite_plugin_put (void *cls, const struct GNUNET_HashCode * key, uint32_t size, 476sqlite_plugin_put (void *cls, const struct GNUNET_HashCode * key, uint32_t size,
diff --git a/src/include/gnunet_container_lib.h b/src/include/gnunet_container_lib.h
index ad7bb8cc0..39176e93b 100644
--- a/src/include/gnunet_container_lib.h
+++ b/src/include/gnunet_container_lib.h
@@ -634,8 +634,7 @@ GNUNET_CONTAINER_multihashmap_create (unsigned int len,
634 * @param map the map 634 * @param map the map
635 */ 635 */
636void 636void
637GNUNET_CONTAINER_multihashmap_destroy (struct GNUNET_CONTAINER_MultiHashMap 637GNUNET_CONTAINER_multihashmap_destroy (struct GNUNET_CONTAINER_MultiHashMap *map);
638 *map);
639 638
640 639
641/** 640/**
@@ -650,8 +649,8 @@ GNUNET_CONTAINER_multihashmap_destroy (struct GNUNET_CONTAINER_MultiHashMap
650 * key-value pairs with value NULL 649 * key-value pairs with value NULL
651 */ 650 */
652void * 651void *
653GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap 652GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap *map,
654 *map, const struct GNUNET_HashCode * key); 653 const struct GNUNET_HashCode *key);
655 654
656 655
657/** 656/**
@@ -668,7 +667,7 @@ GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap
668 */ 667 */
669int 668int
670GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map, 669GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map,
671 const struct GNUNET_HashCode * key, 670 const struct GNUNET_HashCode *key,
672 const void *value); 671 const void *value);
673 672
674/** 673/**
@@ -681,8 +680,8 @@ GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map,
681 * @return number of values removed 680 * @return number of values removed
682 */ 681 */
683int 682int
684GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap 683GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap *map,
685 *map, const struct GNUNET_HashCode * key); 684 const struct GNUNET_HashCode *key);
686 685
687 686
688/** 687/**
@@ -696,8 +695,7 @@ GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap
696 * #GNUNET_NO if not 695 * #GNUNET_NO if not
697 */ 696 */
698int 697int
699GNUNET_CONTAINER_multihashmap_contains (const struct 698GNUNET_CONTAINER_multihashmap_contains (const struct GNUNET_CONTAINER_MultiHashMap *map,
700 GNUNET_CONTAINER_MultiHashMap *map,
701 const struct GNUNET_HashCode * key); 699 const struct GNUNET_HashCode * key);
702 700
703 701
@@ -713,9 +711,8 @@ GNUNET_CONTAINER_multihashmap_contains (const struct
713 * #GNUNET_NO if not 711 * #GNUNET_NO if not
714 */ 712 */
715int 713int
716GNUNET_CONTAINER_multihashmap_contains_value (const struct 714GNUNET_CONTAINER_multihashmap_contains_value (const struct GNUNET_CONTAINER_MultiHashMap *map,
717 GNUNET_CONTAINER_MultiHashMap 715 const struct GNUNET_HashCode *key,
718 *map, const struct GNUNET_HashCode * key,
719 const void *value); 716 const void *value);
720 717
721 718
@@ -729,7 +726,7 @@ GNUNET_CONTAINER_multihashmap_contains_value (const struct
729 * @param opt options for put 726 * @param opt options for put
730 * @return #GNUNET_OK on success, 727 * @return #GNUNET_OK on success,
731 * #GNUNET_NO if a value was replaced (with REPLACE) 728 * #GNUNET_NO if a value was replaced (with REPLACE)
732 * #GNUNET_SYSERR if UNIQUE_ONLY was the option and the 729 * #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
733 * value already exists 730 * value already exists
734 */ 731 */
735int 732int
@@ -772,7 +769,7 @@ GNUNET_CONTAINER_multihashmap_iterate (const struct
772 * Create an iterator for a multihashmap. 769 * Create an iterator for a multihashmap.
773 * The iterator can be used to retrieve all the elements in the multihashmap 770 * The iterator can be used to retrieve all the elements in the multihashmap
774 * one by one, without having to handle all elements at once (in contrast to 771 * one by one, without having to handle all elements at once (in contrast to
775 * 'GNUNET_CONTAINER_multihashmap_iterate'). Note that the iterator can not be 772 * #GNUNET_CONTAINER_multihashmap_iterate). Note that the iterator can not be
776 * used anymore if elements have been removed from 'map' after the creation of 773 * used anymore if elements have been removed from 'map' after the creation of
777 * the iterator, or 'map' has been destroyed. Adding elements to 'map' may 774 * the iterator, or 'map' has been destroyed. Adding elements to 'map' may
778 * result in skipped or repeated elements. 775 * result in skipped or repeated elements.
@@ -801,7 +798,8 @@ GNUNET_CONTAINER_multihashmap_iterator_create (const struct GNUNET_CONTAINER_Mul
801 */ 798 */
802int 799int
803GNUNET_CONTAINER_multihashmap_iterator_next (struct GNUNET_CONTAINER_MultiHashMapIterator *iter, 800GNUNET_CONTAINER_multihashmap_iterator_next (struct GNUNET_CONTAINER_MultiHashMapIterator *iter,
804 struct GNUNET_HashCode *key, const void **value); 801 struct GNUNET_HashCode *key,
802 const void **value);
805 803
806 804
807/** 805/**
@@ -832,6 +830,250 @@ GNUNET_CONTAINER_multihashmap_get_multiple (const struct
832 GNUNET_CONTAINER_HashMapIterator it, 830 GNUNET_CONTAINER_HashMapIterator it,
833 void *it_cls); 831 void *it_cls);
834 832
833
834/* ***************** Version of Multihashmap for peer identities ****************** */
835
836/**
837 * @ingroup hashmap
838 * Iterator over hash map entries.
839 *
840 * @param cls closure
841 * @param key current public key
842 * @param value value in the hash map
843 * @return #GNUNET_YES if we should continue to
844 * iterate,
845 * #GNUNET_NO if not.
846 */
847typedef int (*GNUNET_CONTAINER_PeerMapIterator) (void *cls,
848 const struct GNUNET_PeerIdentity *key,
849 void *value);
850
851
852/**
853 * @ingroup hashmap
854 * Create a multi peer map (hash map for public keys of peers).
855 *
856 * @param len initial size (map will grow as needed)
857 * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default;
858 * #GNUNET_YES means that on 'put', the 'key' does not have
859 * to be copied as the destination of the pointer is
860 * guaranteed to be life as long as the value is stored in
861 * the hashmap. This can significantly reduce memory
862 * consumption, but of course is also a recipie for
863 * heap corruption if the assumption is not true. Only
864 * use this if (1) memory use is important in this case and
865 * (2) you have triple-checked that the invariant holds
866 * @return NULL on error
867 */
868struct GNUNET_CONTAINER_MultiPeerMap *
869GNUNET_CONTAINER_multipeermap_create (unsigned int len,
870 int do_not_copy_keys);
871
872
873/**
874 * @ingroup hashmap
875 * Destroy a hash map. Will not free any values
876 * stored in the hash map!
877 *
878 * @param map the map
879 */
880void
881GNUNET_CONTAINER_multipeermap_destroy (struct GNUNET_CONTAINER_MultiPeerMap *map);
882
883
884/**
885 * @ingroup hashmap
886 * Given a key find a value in the map matching the key.
887 *
888 * @param map the map
889 * @param key what to look for
890 * @return NULL if no value was found; note that
891 * this is indistinguishable from values that just
892 * happen to be NULL; use "contains" to test for
893 * key-value pairs with value NULL
894 */
895void *
896GNUNET_CONTAINER_multipeermap_get (const struct GNUNET_CONTAINER_MultiPeerMap *map,
897 const struct GNUNET_PeerIdentity *key);
898
899
900/**
901 * @ingroup hashmap
902 * Remove the given key-value pair from the map. Note that if the
903 * key-value pair is in the map multiple times, only one of the pairs
904 * will be removed.
905 *
906 * @param map the map
907 * @param key key of the key-value pair
908 * @param value value of the key-value pair
909 * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
910 * is not in the map
911 */
912int
913GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map,
914 const struct GNUNET_PeerIdentity * key,
915 const void *value);
916
917/**
918 * @ingroup hashmap
919 * Remove all entries for the given key from the map.
920 * Note that the values would not be "freed".
921 *
922 * @param map the map
923 * @param key identifies values to be removed
924 * @return number of values removed
925 */
926int
927GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap *map,
928 const struct GNUNET_PeerIdentity *key);
929
930
931/**
932 * @ingroup hashmap
933 * Check if the map contains any value under the given
934 * key (including values that are NULL).
935 *
936 * @param map the map
937 * @param key the key to test if a value exists for it
938 * @return #GNUNET_YES if such a value exists,
939 * #GNUNET_NO if not
940 */
941int
942GNUNET_CONTAINER_multipeermap_contains (const struct GNUNET_CONTAINER_MultiPeerMap *map,
943 const struct GNUNET_PeerIdentity *key);
944
945
946/**
947 * @ingroup hashmap
948 * Check if the map contains the given value under the given
949 * key.
950 *
951 * @param map the map
952 * @param key the key to test if a value exists for it
953 * @param value value to test for
954 * @return #GNUNET_YES if such a value exists,
955 * #GNUNET_NO if not
956 */
957int
958GNUNET_CONTAINER_multipeermap_contains_value (const struct GNUNET_CONTAINER_MultiPeerMap *map,
959 const struct GNUNET_PeerIdentity * key,
960 const void *value);
961
962
963/**
964 * @ingroup hashmap
965 * Store a key-value pair in the map.
966 *
967 * @param map the map
968 * @param key key to use
969 * @param value value to use
970 * @param opt options for put
971 * @return #GNUNET_OK on success,
972 * #GNUNET_NO if a value was replaced (with REPLACE)
973 * #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
974 * value already exists
975 */
976int
977GNUNET_CONTAINER_multipeermap_put (struct GNUNET_CONTAINER_MultiPeerMap *map,
978 const struct GNUNET_PeerIdentity *key,
979 void *value,
980 enum GNUNET_CONTAINER_MultiHashMapOption opt);
981
982
983/**
984 * @ingroup hashmap
985 * Get the number of key-value pairs in the map.
986 *
987 * @param map the map
988 * @return the number of key value pairs
989 */
990unsigned int
991GNUNET_CONTAINER_multipeermap_size (const struct GNUNET_CONTAINER_MultiPeerMap *map);
992
993
994/**
995 * @ingroup hashmap
996 * Iterate over all entries in the map.
997 *
998 * @param map the map
999 * @param it function to call on each entry
1000 * @param it_cls extra argument to @a it
1001 * @return the number of key value pairs processed,
1002 * #GNUNET_SYSERR if it aborted iteration
1003 */
1004int
1005GNUNET_CONTAINER_multipeermap_iterate (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1006 GNUNET_CONTAINER_PeerMapIterator it,
1007 void *it_cls);
1008
1009
1010/**
1011 * @ingroup hashmap
1012 * Create an iterator for a multihashmap.
1013 * The iterator can be used to retrieve all the elements in the multihashmap
1014 * one by one, without having to handle all elements at once (in contrast to
1015 * #GNUNET_CONTAINER_multipeermap_iterate). Note that the iterator can not be
1016 * used anymore if elements have been removed from @a map after the creation of
1017 * the iterator, or 'map' has been destroyed. Adding elements to @a map may
1018 * result in skipped or repeated elements.
1019 *
1020 * @param map the map to create an iterator for
1021 * @return an iterator over the given multihashmap @a map
1022 */
1023struct GNUNET_CONTAINER_MultiPeerMapIterator *
1024GNUNET_CONTAINER_multipeermap_iterator_create (const struct GNUNET_CONTAINER_MultiPeerMap *map);
1025
1026
1027/**
1028 * @ingroup hashmap
1029 * Retrieve the next element from the hash map at the iterator's
1030 * position. If there are no elements left, #GNUNET_NO is returned,
1031 * and @a key and @a value are not modified. This operation is only
1032 * allowed if no elements have been removed from the multihashmap
1033 * since the creation of @a iter, and the map has not been destroyed.
1034 * Adding elements may result in repeating or skipping elements.
1035 *
1036 * @param iter the iterator to get the next element from
1037 * @param key pointer to store the key in, can be NULL
1038 * @param value pointer to store the value in, can be NULL
1039 * @return #GNUNET_YES we returned an element,
1040 * #GNUNET_NO if we are out of elements
1041 */
1042int
1043GNUNET_CONTAINER_multipeermap_iterator_next (struct GNUNET_CONTAINER_MultiPeerMapIterator *iter,
1044 struct GNUNET_PeerIdentity *key,
1045 const void **value);
1046
1047
1048/**
1049 * @ingroup hashmap
1050 * Destroy a multipeermap iterator.
1051 *
1052 * @param iter the iterator to destroy
1053 */
1054void
1055GNUNET_CONTAINER_multipeermap_iterator_destroy (struct GNUNET_CONTAINER_MultiPeerMapIterator *iter);
1056
1057
1058/**
1059 * @ingroup hashmap
1060 * Iterate over all entries in the map that match a particular key.
1061 *
1062 * @param map the map
1063 * @param key public key that the entries must correspond to
1064 * @param it function to call on each entry
1065 * @param it_cls extra argument to @a it
1066 * @return the number of key value pairs processed,
1067 * #GNUNET_SYSERR if it aborted iteration
1068 */
1069int
1070GNUNET_CONTAINER_multipeermap_get_multiple (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1071 const struct GNUNET_PeerIdentity *key,
1072 GNUNET_CONTAINER_PeerMapIterator it,
1073 void *it_cls);
1074
1075
1076
835/* Version of multihashmap with 32 bit keys */ 1077/* Version of multihashmap with 32 bit keys */
836 1078
837/** 1079/**
@@ -939,8 +1181,7 @@ GNUNET_CONTAINER_multihashmap32_iterate (const struct
939 * is not in the map 1181 * is not in the map
940 */ 1182 */
941int 1183int
942GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 1184GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 *map,
943 *map,
944 uint32_t key, 1185 uint32_t key,
945 const void *value); 1186 const void *value);
946 1187
@@ -955,9 +1196,7 @@ GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32
955 * @return number of values removed 1196 * @return number of values removed
956 */ 1197 */
957int 1198int
958GNUNET_CONTAINER_multihashmap32_remove_all (struct 1199GNUNET_CONTAINER_multihashmap32_remove_all (struct GNUNET_CONTAINER_MultiHashMap32 *map,
959 GNUNET_CONTAINER_MultiHashMap32
960 *map,
961 uint32_t key); 1200 uint32_t key);
962 1201
963 1202
@@ -972,8 +1211,7 @@ GNUNET_CONTAINER_multihashmap32_remove_all (struct
972 * #GNUNET_NO if not 1211 * #GNUNET_NO if not
973 */ 1212 */
974int 1213int
975GNUNET_CONTAINER_multihashmap32_contains (const struct 1214GNUNET_CONTAINER_multihashmap32_contains (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
976 GNUNET_CONTAINER_MultiHashMap32 *map,
977 uint32_t key); 1215 uint32_t key);
978 1216
979 1217
@@ -989,9 +1227,7 @@ GNUNET_CONTAINER_multihashmap32_contains (const struct
989 * #GNUNET_NO if not 1227 * #GNUNET_NO if not
990 */ 1228 */
991int 1229int
992GNUNET_CONTAINER_multihashmap32_contains_value (const struct 1230GNUNET_CONTAINER_multihashmap32_contains_value (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
993 GNUNET_CONTAINER_MultiHashMap32
994 *map,
995 uint32_t key, 1231 uint32_t key,
996 const void *value); 1232 const void *value);
997 1233
@@ -1010,10 +1246,10 @@ GNUNET_CONTAINER_multihashmap32_contains_value (const struct
1010 * value already exists 1246 * value already exists
1011 */ 1247 */
1012int 1248int
1013GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32 1249GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32 *map,
1014 *map, uint32_t key, void *value, 1250 uint32_t key,
1015 enum GNUNET_CONTAINER_MultiHashMapOption 1251 void *value,
1016 opt); 1252 enum GNUNET_CONTAINER_MultiHashMapOption opt);
1017 1253
1018 1254
1019/** 1255/**
@@ -1028,11 +1264,10 @@ GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32
1028 * #GNUNET_SYSERR if it aborted iteration 1264 * #GNUNET_SYSERR if it aborted iteration
1029 */ 1265 */
1030int 1266int
1031GNUNET_CONTAINER_multihashmap32_get_multiple (const struct 1267GNUNET_CONTAINER_multihashmap32_get_multiple (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
1032 GNUNET_CONTAINER_MultiHashMap32 1268 uint32_t key,
1033 *map, uint32_t key, 1269 GNUNET_CONTAINER_HashMapIterator32 it,
1034 GNUNET_CONTAINER_HashMapIterator32 1270 void *it_cls);
1035 it, void *it_cls);
1036 1271
1037 1272
1038 1273
diff --git a/src/util/Makefile.am b/src/util/Makefile.am
index 934385663..ee3349db7 100644
--- a/src/util/Makefile.am
+++ b/src/util/Makefile.am
@@ -73,6 +73,7 @@ libgnunetutil_la_SOURCES = \
73 container_heap.c \ 73 container_heap.c \
74 container_meta_data.c \ 74 container_meta_data.c \
75 container_multihashmap.c \ 75 container_multihashmap.c \
76 container_multipeermap.c \
76 container_multihashmap32.c \ 77 container_multihashmap32.c \
77 container_slist.c \ 78 container_slist.c \
78 crypto_symmetric.c \ 79 crypto_symmetric.c \
@@ -204,6 +205,7 @@ check_PROGRAMS = \
204 test_container_meta_data \ 205 test_container_meta_data \
205 test_container_multihashmap \ 206 test_container_multihashmap \
206 test_container_multihashmap32 \ 207 test_container_multihashmap32 \
208 test_container_multipeermap \
207 test_container_heap \ 209 test_container_heap \
208 test_container_slist \ 210 test_container_slist \
209 test_crypto_symmetric \ 211 test_crypto_symmetric \
@@ -310,6 +312,11 @@ test_container_multihashmap32_SOURCES = \
310test_container_multihashmap32_LDADD = \ 312test_container_multihashmap32_LDADD = \
311 $(top_builddir)/src/util/libgnunetutil.la 313 $(top_builddir)/src/util/libgnunetutil.la
312 314
315test_container_multipeermap_SOURCES = \
316 test_container_multipeermap.c
317test_container_multipeermap_LDADD = \
318 $(top_builddir)/src/util/libgnunetutil.la
319
313test_container_heap_SOURCES = \ 320test_container_heap_SOURCES = \
314 test_container_heap.c 321 test_container_heap.c
315test_container_heap_LDADD = \ 322test_container_heap_LDADD = \
diff --git a/src/util/container_multihashmap.c b/src/util/container_multihashmap.c
index 3950684d1..5d12644cf 100644
--- a/src/util/container_multihashmap.c
+++ b/src/util/container_multihashmap.c
@@ -180,7 +180,7 @@ GNUNET_CONTAINER_multihashmap_create (unsigned int len,
180 struct GNUNET_CONTAINER_MultiHashMap *map; 180 struct GNUNET_CONTAINER_MultiHashMap *map;
181 181
182 GNUNET_assert (len > 0); 182 GNUNET_assert (len > 0);
183 map = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_MultiHashMap)); 183 map = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap);
184 map->map = GNUNET_malloc (len * sizeof (union MapEntry)); 184 map->map = GNUNET_malloc (len * sizeof (union MapEntry));
185 map->map_length = len; 185 map->map_length = len;
186 map->use_small_entries = do_not_copy_keys; 186 map->use_small_entries = do_not_copy_keys;
@@ -718,7 +718,7 @@ GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map,
718 { 718 {
719 struct SmallMapEntry *sme; 719 struct SmallMapEntry *sme;
720 720
721 sme = GNUNET_malloc (sizeof (struct SmallMapEntry)); 721 sme = GNUNET_new (struct SmallMapEntry);
722 sme->key = key; 722 sme->key = key;
723 sme->value = value; 723 sme->value = value;
724 sme->next = map->map[i].sme; 724 sme->next = map->map[i].sme;
@@ -728,7 +728,7 @@ GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map,
728 { 728 {
729 struct BigMapEntry *bme; 729 struct BigMapEntry *bme;
730 730
731 bme = GNUNET_malloc (sizeof (struct BigMapEntry)); 731 bme = GNUNET_new (struct BigMapEntry);
732 bme->key = *key; 732 bme->key = *key;
733 bme->value = value; 733 bme->value = value;
734 bme->next = map->map[i].bme; 734 bme->next = map->map[i].bme;
diff --git a/src/util/container_multihashmap32.c b/src/util/container_multihashmap32.c
index 8bfff0616..29ad14d3a 100644
--- a/src/util/container_multihashmap32.c
+++ b/src/util/container_multihashmap32.c
@@ -90,7 +90,7 @@ GNUNET_CONTAINER_multihashmap32_create (unsigned int len)
90 struct GNUNET_CONTAINER_MultiHashMap32 *ret; 90 struct GNUNET_CONTAINER_MultiHashMap32 *ret;
91 91
92 GNUNET_assert (len > 0); 92 GNUNET_assert (len > 0);
93 ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_MultiHashMap32)); 93 ret = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap32);
94 ret->map = GNUNET_malloc (len * sizeof (struct MapEntry *)); 94 ret->map = GNUNET_malloc (len * sizeof (struct MapEntry *));
95 ret->map_length = len; 95 ret->map_length = len;
96 return ret; 96 return ret;
@@ -448,7 +448,7 @@ GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32
448 grow (map); 448 grow (map);
449 i = idx_of (map, key); 449 i = idx_of (map, key);
450 } 450 }
451 e = GNUNET_malloc (sizeof (struct MapEntry)); 451 e = GNUNET_new (struct MapEntry);
452 e->key = key; 452 e->key = key;
453 e->value = value; 453 e->value = value;
454 e->next = map->map[i]; 454 e->next = map->map[i];
diff --git a/src/util/container_multipeermap.c b/src/util/container_multipeermap.c
new file mode 100644
index 000000000..6519f6c84
--- /dev/null
+++ b/src/util/container_multipeermap.c
@@ -0,0 +1,893 @@
1/*
2 This file is part of GNUnet.
3 (C) 2008, 2012 Christian Grothoff (and other contributing authors)
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., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
19*/
20/**
21 * @file util/container_multipeermap.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_common.h"
28#include "gnunet_container_lib.h"
29#include "gnunet_crypto_lib.h"
30
31#define LOG(kind,...) GNUNET_log_from (kind, "util", __VA_ARGS__)
32
33/**
34 * An entry in the hash map with the full key.
35 */
36struct BigMapEntry
37{
38
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 /**
50 * Key for the entry.
51 */
52 struct GNUNET_PeerIdentity key;
53
54};
55
56
57/**
58 * An entry in the hash map with just a pointer to the key.
59 */
60struct SmallMapEntry
61{
62
63 /**
64 * Value of the entry.
65 */
66 void *value;
67
68 /**
69 * If there is a hash collision, we create a linked list.
70 */
71 struct SmallMapEntry *next;
72
73 /**
74 * Key for the entry.
75 */
76 const struct GNUNET_PeerIdentity *key;
77
78};
79
80
81/**
82 * Entry in the map.
83 */
84union 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
98/**
99 * Internal representation of the hash map.
100 */
101struct GNUNET_CONTAINER_MultiPeerMap
102{
103 /**
104 * All of our buckets.
105 */
106 union MapEntry *map;
107
108 /**
109 * Number of entries in the map.
110 */
111 unsigned int size;
112
113 /**
114 * Length of the "map" array.
115 */
116 unsigned int map_length;
117
118 /**
119 * GNUNET_NO if the map entries are of type 'struct BigMapEntry',
120 * GNUNET_YES if the map entries are of type 'struct SmallMapEntry'.
121 */
122 int use_small_entries;
123
124 /**
125 * Counts the destructive modifications (grow, remove)
126 * to the map, so that iterators can check if they are still valid.
127 */
128 unsigned int modification_counter;
129};
130
131
132/**
133 * Cursor into a multipeermap.
134 * Allows to enumerate elements asynchronously.
135 */
136struct GNUNET_CONTAINER_MultiPeerMapIterator
137{
138 /**
139 * Position in the bucket 'idx'
140 */
141 union MapEntry me;
142
143 /**
144 * Current bucket index.
145 */
146 unsigned int idx;
147
148 /**
149 * Modification counter as observed on the map when the iterator
150 * was created.
151 */
152 unsigned int modification_counter;
153
154 /**
155 * Map that we are iterating over.
156 */
157 const struct GNUNET_CONTAINER_MultiPeerMap *map;
158};
159
160
161/**
162 * Create a multi hash map.
163 *
164 * @param len initial size (map will grow as needed)
165 * @param do_not_copy_keys GNUNET_NO is always safe and should be used by default;
166 * GNUNET_YES means that on 'put', the 'key' does not have
167 * to be copied as the destination of the pointer is
168 * guaranteed to be life as long as the value is stored in
169 * the hashmap. This can significantly reduce memory
170 * consumption, but of course is also a recipie for
171 * heap corruption if the assumption is not true. Only
172 * use this if (1) memory use is important in this case and
173 * (2) you have triple-checked that the invariant holds
174 * @return NULL on error
175 */
176struct GNUNET_CONTAINER_MultiPeerMap *
177GNUNET_CONTAINER_multipeermap_create (unsigned int len,
178 int do_not_copy_keys)
179{
180 struct GNUNET_CONTAINER_MultiPeerMap *map;
181
182 GNUNET_assert (len > 0);
183 map = GNUNET_new (struct GNUNET_CONTAINER_MultiPeerMap);
184 map->map = GNUNET_malloc (len * sizeof (union MapEntry));
185 map->map_length = len;
186 map->use_small_entries = do_not_copy_keys;
187 return map;
188}
189
190
191/**
192 * Destroy a hash map. Will not free any values
193 * stored in the hash map!
194 *
195 * @param map the map
196 */
197void
198GNUNET_CONTAINER_multipeermap_destroy (struct GNUNET_CONTAINER_MultiPeerMap
199 *map)
200{
201 unsigned int i;
202 union MapEntry me;
203
204 for (i = 0; i < map->map_length; i++)
205 {
206 me = map->map[i];
207 if (map->use_small_entries)
208 {
209 struct SmallMapEntry *sme;
210 struct SmallMapEntry *nxt;
211
212 nxt = me.sme;
213 while (NULL != (sme = nxt))
214 {
215 nxt = sme->next;
216 GNUNET_free (sme);
217 }
218 me.sme = NULL;
219 }
220 else
221 {
222 struct BigMapEntry *bme;
223 struct BigMapEntry *nxt;
224
225 nxt = me.bme;
226 while (NULL != (bme = nxt))
227 {
228 nxt = bme->next;
229 GNUNET_free (bme);
230 }
231 me.bme = NULL;
232 }
233 }
234 GNUNET_free (map->map);
235 GNUNET_free (map);
236}
237
238
239/**
240 * Compute the index of the bucket for the given key.
241 *
242 * @param map hash map for which to compute the index
243 * @param key what key should the index be computed for
244 * @return offset into the "map" array of "map"
245 */
246static unsigned int
247idx_of (const struct GNUNET_CONTAINER_MultiPeerMap *map,
248 const struct GNUNET_PeerIdentity *key)
249{
250 GNUNET_assert (map != NULL);
251 return (*(unsigned int *) key) % map->map_length;
252}
253
254
255/**
256 * Get the number of key-value pairs in the map.
257 *
258 * @param map the map
259 * @return the number of key value pairs
260 */
261unsigned int
262GNUNET_CONTAINER_multipeermap_size (const struct GNUNET_CONTAINER_MultiPeerMap
263 *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_multipeermap_get (const struct GNUNET_CONTAINER_MultiPeerMap
281 *map, 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_multipeermap_iterate (const struct
317 GNUNET_CONTAINER_MultiPeerMap *map,
318 GNUNET_CONTAINER_PeerMapIterator it,
319 void *it_cls)
320{
321 int count;
322 unsigned int i;
323 union MapEntry me;
324 struct GNUNET_PeerIdentity kc;
325
326 count = 0;
327 GNUNET_assert (NULL != map);
328 for (i = 0; i < map->map_length; i++)
329 {
330 me = map->map[i];
331 if (map->use_small_entries)
332 {
333 struct SmallMapEntry *sme;
334 struct SmallMapEntry *nxt;
335
336 nxt = me.sme;
337 while (NULL != (sme = nxt))
338 {
339 nxt = sme->next;
340 if (NULL != it)
341 {
342 if (GNUNET_OK != it (it_cls, sme->key, sme->value))
343 return GNUNET_SYSERR;
344 }
345 count++;
346 }
347 }
348 else
349 {
350 struct BigMapEntry *bme;
351 struct BigMapEntry *nxt;
352
353 nxt = me.bme;
354 while (NULL != (bme = nxt))
355 {
356 nxt = bme->next;
357 if (NULL != it)
358 {
359 kc = bme->key;
360 if (GNUNET_OK != it (it_cls, &kc, bme->value))
361 return GNUNET_SYSERR;
362 }
363 count++;
364 }
365 }
366 }
367 return count;
368}
369
370
371/**
372 * Remove the given key-value pair from the map. Note that if the
373 * key-value pair is in the map multiple times, only one of the pairs
374 * will be removed.
375 *
376 * @param map the map
377 * @param key key of the key-value pair
378 * @param value value of the key-value pair
379 * @return GNUNET_YES on success, GNUNET_NO if the key-value pair
380 * is not in the map
381 */
382int
383GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map,
384 const struct GNUNET_PeerIdentity *key,
385 const void *value)
386{
387 union MapEntry me;
388 unsigned int i;
389
390 map->modification_counter++;
391
392 i = idx_of (map, key);
393 me = map->map[i];
394 if (map->use_small_entries)
395 {
396 struct SmallMapEntry *sme;
397 struct SmallMapEntry *p;
398
399 p = NULL;
400 for (sme = me.sme; NULL != sme; sme = sme->next)
401 {
402 if ((0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) &&
403 (value == sme->value))
404 {
405 if (NULL == p)
406 map->map[i].sme = sme->next;
407 else
408 p->next = sme->next;
409 GNUNET_free (sme);
410 map->size--;
411 return GNUNET_YES;
412 }
413 p = sme;
414 }
415 }
416 else
417 {
418 struct BigMapEntry *bme;
419 struct BigMapEntry *p;
420
421 p = NULL;
422 for (bme = me.bme; NULL != bme; bme = bme->next)
423 {
424 if ((0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) &&
425 (value == bme->value))
426 {
427 if (NULL == p)
428 map->map[i].bme = bme->next;
429 else
430 p->next = bme->next;
431 GNUNET_free (bme);
432 map->size--;
433 return GNUNET_YES;
434 }
435 p = bme;
436 }
437 }
438 return GNUNET_NO;
439}
440
441
442/**
443 * Remove all entries for the given key from the map.
444 * Note that the values would not be "freed".
445 *
446 * @param map the map
447 * @param key identifies values to be removed
448 * @return number of values removed
449 */
450int
451GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap
452 *map, const struct GNUNET_PeerIdentity *key)
453{
454 union MapEntry me;
455 unsigned int i;
456 int ret;
457
458 map->modification_counter++;
459
460 ret = 0;
461 i = idx_of (map, key);
462 me = map->map[i];
463 if (map->use_small_entries)
464 {
465 struct SmallMapEntry *sme;
466 struct SmallMapEntry *p;
467
468 p = NULL;
469 sme = me.sme;
470 while (NULL != sme)
471 {
472 if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity)))
473 {
474 if (NULL == p)
475 map->map[i].sme = sme->next;
476 else
477 p->next = sme->next;
478 GNUNET_free (sme);
479 map->size--;
480 if (NULL == p)
481 sme = map->map[i].sme;
482 else
483 sme = p->next;
484 ret++;
485 }
486 else
487 {
488 p = sme;
489 sme = sme->next;
490 }
491 }
492 }
493 else
494 {
495 struct BigMapEntry *bme;
496 struct BigMapEntry *p;
497
498 p = NULL;
499 bme = me.bme;
500 while (NULL != bme)
501 {
502 if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity)))
503 {
504 if (NULL == p)
505 map->map[i].bme = bme->next;
506 else
507 p->next = bme->next;
508 GNUNET_free (bme);
509 map->size--;
510 if (NULL == p)
511 bme = map->map[i].bme;
512 else
513 bme = p->next;
514 ret++;
515 }
516 else
517 {
518 p = bme;
519 bme = bme->next;
520 }
521 }
522 }
523 return ret;
524}
525
526
527/**
528 * Check if the map contains any value under the given
529 * key (including values that are NULL).
530 *
531 * @param map the map
532 * @param key the key to test if a value exists for it
533 * @return GNUNET_YES if such a value exists,
534 * GNUNET_NO if not
535 */
536int
537GNUNET_CONTAINER_multipeermap_contains (const struct
538 GNUNET_CONTAINER_MultiPeerMap *map,
539 const struct GNUNET_PeerIdentity *key)
540{
541 union MapEntry me;
542
543 me = map->map[idx_of (map, key)];
544 if (map->use_small_entries)
545 {
546 struct SmallMapEntry *sme;
547
548 for (sme = me.sme; NULL != sme; sme = sme->next)
549 if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity)))
550 return GNUNET_YES;
551 }
552 else
553 {
554 struct BigMapEntry *bme;
555
556 for (bme = me.bme; NULL != bme; bme = bme->next)
557 if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity)))
558 return GNUNET_YES;
559 }
560 return GNUNET_NO;
561}
562
563
564/**
565 * Check if the map contains the given value under the given
566 * key.
567 *
568 * @param map the map
569 * @param key the key to test if a value exists for it
570 * @param value value to test for
571 * @return GNUNET_YES if such a value exists,
572 * GNUNET_NO if not
573 */
574int
575GNUNET_CONTAINER_multipeermap_contains_value (const struct
576 GNUNET_CONTAINER_MultiPeerMap
577 *map, const struct GNUNET_PeerIdentity *key,
578 const void *value)
579{
580 union MapEntry me;
581
582 me = map->map[idx_of (map, key)];
583 if (map->use_small_entries)
584 {
585 struct SmallMapEntry *sme;
586
587 for (sme = me.sme; NULL != sme; sme = sme->next)
588 if ( (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) &&
589 (sme->value == value) )
590 return GNUNET_YES;
591 }
592 else
593 {
594 struct BigMapEntry *bme;
595
596 for (bme = me.bme; NULL != bme; bme = bme->next)
597 if ( (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) &&
598 (bme->value == value) )
599 return GNUNET_YES;
600 }
601 return GNUNET_NO;
602}
603
604
605/**
606 * Grow the given map to a more appropriate size.
607 *
608 * @param map the hash map to grow
609 */
610static void
611grow (struct GNUNET_CONTAINER_MultiPeerMap *map)
612{
613 union MapEntry *old_map;
614 union MapEntry *new_map;
615 unsigned int old_len;
616 unsigned int new_len;
617 unsigned int idx;
618 unsigned int i;
619
620 map->modification_counter++;
621
622 old_map = map->map;
623 old_len = map->map_length;
624 new_len = old_len * 2;
625 new_map = GNUNET_malloc (sizeof (union MapEntry) * new_len);
626 map->map_length = new_len;
627 map->map = new_map;
628 for (i = 0; i < old_len; i++)
629 {
630 if (map->use_small_entries)
631 {
632 struct SmallMapEntry *sme;
633
634 while (NULL != (sme = old_map[i].sme))
635 {
636 old_map[i].sme = sme->next;
637 idx = idx_of (map, sme->key);
638 sme->next = new_map[idx].sme;
639 new_map[idx].sme = sme;
640 }
641 }
642 else
643 {
644 struct BigMapEntry *bme;
645
646 while (NULL != (bme = old_map[i].bme))
647 {
648 old_map[i].bme = bme->next;
649 idx = idx_of (map, &bme->key);
650 bme->next = new_map[idx].bme;
651 new_map[idx].bme = bme;
652 }
653 }
654 }
655 GNUNET_free (old_map);
656}
657
658
659/**
660 * Store a key-value pair in the map.
661 *
662 * @param map the map
663 * @param key key to use
664 * @param value value to use
665 * @param opt options for put
666 * @return #GNUNET_OK on success,
667 * #GNUNET_NO if a value was replaced (with REPLACE)
668 * #GNUNET_SYSERR if GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
669 * value already exists
670 */
671int
672GNUNET_CONTAINER_multipeermap_put (struct GNUNET_CONTAINER_MultiPeerMap *map,
673 const struct GNUNET_PeerIdentity *key,
674 void *value,
675 enum GNUNET_CONTAINER_MultiHashMapOption opt)
676{
677 union MapEntry me;
678 unsigned int i;
679
680 i = idx_of (map, key);
681 if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
682 (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
683 {
684 me = map->map[i];
685 if (map->use_small_entries)
686 {
687 struct SmallMapEntry *sme;
688
689 for (sme = me.sme; NULL != sme; sme = sme->next)
690 if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity)))
691 {
692 if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
693 return GNUNET_SYSERR;
694 sme->value = value;
695 return GNUNET_NO;
696 }
697 }
698 else
699 {
700 struct BigMapEntry *bme;
701
702 for (bme = me.bme; NULL != bme; bme = bme->next)
703 if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity)))
704 {
705 if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
706 return GNUNET_SYSERR;
707 bme->value = value;
708 return GNUNET_NO;
709 }
710 }
711 }
712 if (map->size / 3 >= map->map_length / 4)
713 {
714 grow (map);
715 i = idx_of (map, key);
716 }
717 if (map->use_small_entries)
718 {
719 struct SmallMapEntry *sme;
720
721 sme = GNUNET_new (struct SmallMapEntry);
722 sme->key = key;
723 sme->value = value;
724 sme->next = map->map[i].sme;
725 map->map[i].sme = sme;
726 }
727 else
728 {
729 struct BigMapEntry *bme;
730
731 bme = GNUNET_new (struct BigMapEntry);
732 bme->key = *key;
733 bme->value = value;
734 bme->next = map->map[i].bme;
735 map->map[i].bme = bme;
736 }
737 map->size++;
738 return GNUNET_OK;
739}
740
741
742/**
743 * Iterate over all entries in the map that match a particular key.
744 *
745 * @param map the map
746 * @param key key that the entries must correspond to
747 * @param it function to call on each entry
748 * @param it_cls extra argument to @a it
749 * @return the number of key value pairs processed,
750 * #GNUNET_SYSERR if it aborted iteration
751 */
752int
753GNUNET_CONTAINER_multipeermap_get_multiple (const struct GNUNET_CONTAINER_MultiPeerMap *map,
754 const struct GNUNET_PeerIdentity *key,
755 GNUNET_CONTAINER_PeerMapIterator it,
756 void *it_cls)
757{
758 int count;
759 union MapEntry me;
760
761 count = 0;
762 me = map->map[idx_of (map, key)];
763 if (map->use_small_entries)
764 {
765 struct SmallMapEntry *sme;
766 struct SmallMapEntry *nxt;
767
768 nxt = me.sme;
769 while (NULL != (sme = nxt))
770 {
771 nxt = sme->next;
772 if (0 != memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity)))
773 continue;
774 if ((it != NULL) && (GNUNET_OK != it (it_cls, key, sme->value)))
775 return GNUNET_SYSERR;
776 count++;
777 }
778 }
779 else
780 {
781 struct BigMapEntry *bme;
782 struct BigMapEntry *nxt;
783
784 nxt = me.bme;
785 while (NULL != (bme = nxt))
786 {
787 nxt = bme->next;
788 if (0 != memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity)))
789 continue;
790 if ((it != NULL) && (GNUNET_OK != it (it_cls, key, bme->value)))
791 return GNUNET_SYSERR;
792 count++;
793 }
794 }
795 return count;
796}
797
798
799/**
800 * Create an iterator for a multipeermap.
801 * The iterator can be used to retrieve all the elements in the multipeermap
802 * one by one, without having to handle all elements at once (in contrast to
803 * #GNUNET_CONTAINER_multipeermap_iterate). Note that the iterator can not be
804 * used anymore if elements have been removed from 'map' after the creation of
805 * the iterator, or 'map' has been destroyed. Adding elements to 'map' may
806 * result in skipped or repeated elements.
807 *
808 * @param map the map to create an iterator for
809 * @return an iterator over the given multipeermap 'map'
810 */
811struct GNUNET_CONTAINER_MultiPeerMapIterator *
812GNUNET_CONTAINER_multipeermap_iterator_create (const struct GNUNET_CONTAINER_MultiPeerMap *map)
813{
814 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
815
816 iter = GNUNET_new (struct GNUNET_CONTAINER_MultiPeerMapIterator);
817 iter->map = map;
818 iter->modification_counter = map->modification_counter;
819 iter->me = map->map[0];
820 return iter;
821}
822
823
824/**
825 * Retrieve the next element from the hash map at the iterator's position.
826 * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
827 * are not modified.
828 * This operation is only allowed if no elements have been removed from the
829 * multipeermap since the creation of 'iter', and the map has not been destroyed.
830 * Adding elements may result in repeating or skipping elements.
831 *
832 * @param iter the iterator to get the next element from
833 * @param key pointer to store the key in, can be NULL
834 * @param value pointer to store the value in, can be NULL
835 * @return #GNUNET_YES we returned an element,
836 * #GNUNET_NO if we are out of elements
837 */
838int
839GNUNET_CONTAINER_multipeermap_iterator_next (struct GNUNET_CONTAINER_MultiPeerMapIterator *iter,
840 struct GNUNET_PeerIdentity *key, const void **value)
841{
842 /* make sure the map has not been modified */
843 GNUNET_assert (iter->modification_counter == iter->map->modification_counter);
844
845 /* look for the next entry, skipping empty buckets */
846 while (1)
847 {
848 if (iter->idx >= iter->map->map_length)
849 return GNUNET_NO;
850 if (GNUNET_YES == iter->map->use_small_entries)
851 {
852 if (NULL != iter->me.sme)
853 {
854 if (NULL != key)
855 *key = *iter->me.sme->key;
856 if (NULL != value)
857 *value = iter->me.sme->value;
858 iter->me.sme = iter->me.sme->next;
859 return GNUNET_YES;
860 }
861 }
862 else
863 {
864 if (NULL != iter->me.bme)
865 {
866 if (NULL != key)
867 *key = iter->me.bme->key;
868 if (NULL != value)
869 *value = iter->me.bme->value;
870 iter->me.bme = iter->me.bme->next;
871 return GNUNET_YES;
872 }
873 }
874 iter->idx += 1;
875 if (iter->idx < iter->map->map_length)
876 iter->me = iter->map->map[iter->idx];
877 }
878}
879
880
881/**
882 * Destroy a multipeermap iterator.
883 *
884 * @param iter the iterator to destroy
885 */
886void
887GNUNET_CONTAINER_multipeermap_iterator_destroy (struct GNUNET_CONTAINER_MultiPeerMapIterator *iter)
888{
889 GNUNET_free (iter);
890}
891
892
893/* end of container_multipeermap.c */
diff --git a/src/util/test_container_multipeermap.c b/src/util/test_container_multipeermap.c
new file mode 100644
index 000000000..aa67eb5e0
--- /dev/null
+++ b/src/util/test_container_multipeermap.c
@@ -0,0 +1,121 @@
1/*
2 This file is part of GNUnet.
3 (C) 2008, 2013 Christian Grothoff (and other contributing authors)
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., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
19*/
20
21/**
22 * @file util/test_container_multipeermap.c
23 * @brief Test for container_multipeermap.c
24 * @author Christian Grothoff
25 */
26
27#include "platform.h"
28#include "gnunet_common.h"
29#include "gnunet_container_lib.h"
30
31#define ABORT() { fprintf(stderr, "Error at %s:%d\n", __FILE__, __LINE__); if (NULL != m) GNUNET_CONTAINER_multipeermap_destroy(m); return 1; }
32#define CHECK(c) { if (! (c)) ABORT(); }
33
34static int
35testMap (int i)
36{
37 struct GNUNET_CONTAINER_MultiPeerMap *m;
38 struct GNUNET_PeerIdentity k1;
39 struct GNUNET_PeerIdentity k2;
40 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
41 struct GNUNET_PeerIdentity key_ret;
42 const char *ret;
43 int j;
44
45 CHECK (NULL != (m = GNUNET_CONTAINER_multipeermap_create (i, GNUNET_NO)));
46 memset (&k1, 0, sizeof (k1));
47 memset (&k2, 1, sizeof (k2));
48 CHECK (GNUNET_NO == GNUNET_CONTAINER_multipeermap_contains (m, &k1));
49 CHECK (GNUNET_NO == GNUNET_CONTAINER_multipeermap_contains (m, &k2));
50 CHECK (GNUNET_NO == GNUNET_CONTAINER_multipeermap_remove (m, &k1, NULL));
51 CHECK (GNUNET_NO == GNUNET_CONTAINER_multipeermap_remove (m, &k2, NULL));
52 CHECK (NULL == GNUNET_CONTAINER_multipeermap_get (m, &k1));
53 CHECK (NULL == GNUNET_CONTAINER_multipeermap_get (m, &k2));
54 CHECK (0 == GNUNET_CONTAINER_multipeermap_remove_all (m, &k1));
55 CHECK (0 == GNUNET_CONTAINER_multipeermap_size (m));
56 CHECK (0 == GNUNET_CONTAINER_multipeermap_iterate (m, NULL, NULL));
57 CHECK (0 == GNUNET_CONTAINER_multipeermap_get_multiple (m, &k1, NULL, NULL));
58
59 CHECK (GNUNET_OK ==
60 GNUNET_CONTAINER_multipeermap_put (m, &k1, "v1",
61 GNUNET_CONTAINER_MULTIHASHMAPOPTION_REPLACE));
62 CHECK (1 == GNUNET_CONTAINER_multipeermap_size (m));
63 ret = GNUNET_CONTAINER_multipeermap_get (m, &k1);
64 GNUNET_assert (ret != NULL);
65 CHECK (0 == strcmp ("v1", ret));
66 CHECK (GNUNET_NO ==
67 GNUNET_CONTAINER_multipeermap_put (m, &k1, "v1",
68 GNUNET_CONTAINER_MULTIHASHMAPOPTION_REPLACE));
69 CHECK (1 == GNUNET_CONTAINER_multipeermap_size (m));
70 CHECK (GNUNET_OK ==
71 GNUNET_CONTAINER_multipeermap_put (m, &k1, "v2",
72 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
73 CHECK (GNUNET_OK ==
74 GNUNET_CONTAINER_multipeermap_put (m, &k1, "v3",
75 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
76 CHECK (3 == GNUNET_CONTAINER_multipeermap_size (m));
77 CHECK (GNUNET_OK == GNUNET_CONTAINER_multipeermap_remove (m, &k1, "v3"));
78 CHECK (2 == GNUNET_CONTAINER_multipeermap_size (m));
79 CHECK (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (m, &k1));
80 CHECK (GNUNET_NO == GNUNET_CONTAINER_multipeermap_contains (m, &k2));
81 CHECK (2 == GNUNET_CONTAINER_multipeermap_get_multiple (m, &k1, NULL, NULL));
82 CHECK (0 == GNUNET_CONTAINER_multipeermap_get_multiple (m, &k2, NULL, NULL));
83 CHECK (2 == GNUNET_CONTAINER_multipeermap_iterate (m, NULL, NULL));
84 iter = GNUNET_CONTAINER_multipeermap_iterator_create (m);
85 CHECK (GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter, &key_ret, (const void **)&ret));
86 CHECK (0 == memcmp (&key_ret, &k1, sizeof (key_ret)));
87 CHECK (GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter, &key_ret, (const void **)&ret));
88 CHECK (0 == memcmp (&key_ret, &k1, sizeof (key_ret)));
89 CHECK (GNUNET_NO == GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
90 GNUNET_free (iter);
91
92 CHECK (2 == GNUNET_CONTAINER_multipeermap_remove_all (m, &k1));
93 for (j = 0; j < 1024; j++)
94 CHECK (GNUNET_OK ==
95 GNUNET_CONTAINER_multipeermap_put (m, &k1, "v2",
96 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
97 iter = GNUNET_CONTAINER_multipeermap_iterator_create (m);
98 for (j = 0; j < GNUNET_CONTAINER_multipeermap_size (m); j++)
99 CHECK (GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
100 CHECK (GNUNET_NO == GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
101 GNUNET_free (iter);
102
103 GNUNET_CONTAINER_multipeermap_destroy (m);
104 return 0;
105}
106
107int
108main (int argc, char *argv[])
109{
110 int failureCount = 0;
111 int i;
112
113 GNUNET_log_setup ("test-container-multipeermap", "WARNING", NULL);
114 for (i = 1; i < 255; i++)
115 failureCount += testMap (i);
116 if (failureCount != 0)
117 return 1;
118 return 0;
119}
120
121/* end of test_container_multipeermap.c */
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-20 11:49:54 +0000