aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorFlorian Dold <florian.dold@gmail.com>2013-08-12 14:33:26 +0000
committerFlorian Dold <florian.dold@gmail.com>2013-08-12 14:33:26 +0000
commite0af01758cb7eec5aea8e942c3d54a71b2c2100b (patch)
tree11c3a656bcce5eeda9bbd85671fecda07448a45c
parent210ad40c32a0aa11696786354690f0230b60b86a (diff)
downloadgnunet-e0af01758cb7eec5aea8e942c3d54a71b2c2100b.tar.gz
gnunet-e0af01758cb7eec5aea8e942c3d54a71b2c2100b.zip
- external iterator for multihashmap
-rw-r--r--src/include/gnunet_container_lib.h50
-rw-r--r--src/util/container_multihashmap.c134
2 files changed, 183 insertions, 1 deletions
diff --git a/src/include/gnunet_container_lib.h b/src/include/gnunet_container_lib.h
index c36190b7a..a6a0e519d 100644
--- a/src/include/gnunet_container_lib.h
+++ b/src/include/gnunet_container_lib.h
@@ -490,6 +490,12 @@ GNUNET_CONTAINER_meta_data_deserialize (const char *input, size_t size);
490struct GNUNET_CONTAINER_MultiHashMap; 490struct GNUNET_CONTAINER_MultiHashMap;
491 491
492/** 492/**
493 * Opaque handle to an iterator over
494 * a multihashmap.
495 */
496struct GNUNET_CONTAINER_MultiHashMapIterator;
497
498/**
493 * Options for storing values in the HashMap. 499 * Options for storing values in the HashMap.
494 */ 500 */
495enum GNUNET_CONTAINER_MultiHashMapOption 501enum GNUNET_CONTAINER_MultiHashMapOption
@@ -691,6 +697,50 @@ GNUNET_CONTAINER_multihashmap_iterate (const struct
691 697
692 698
693/** 699/**
700 * Create an iterator for a multihashmap.
701 * The iterator can be used to retrieve all the elements in the multihashmap
702 * one by one, without having to handle all elements at once (in contrast to
703 * 'GNUNET_CONTAINER_multihashmap_iterate'). Note that the iterator can not be
704 * used anymore if elements have been removed from 'map' after the creation of
705 * the iterator, or 'map' has been destroyed. Adding elements to 'map' may
706 * result in skipped or repeated elements.
707 *
708 * @param map the map to create an iterator for
709 * @return an iterator over the given multihashmap 'map'
710 */
711struct GNUNET_CONTAINER_MultiHashMapIterator *
712GNUNET_CONTAINER_multihashmap_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap *map);
713
714
715/**
716 * Retrieve the next element from the hash map at the iterator's position.
717 * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
718 * are not modified.
719 * This operation is only allowed if no elements have been removed from the
720 * multihashmap since the creation of 'iter', and the map has not been destroyed.
721 * Adding elements may result in repeating or skipping elements.
722 *
723 * @param iter the iterator to get the next element from
724 * @param key pointer to store the key in, can be NULL
725 * @param value pointer to store the value in, can be NULL
726 * @return GNUNET_YES we returned an element,
727 * GNUNET_NO if we are out of elements
728 */
729int
730GNUNET_CONTAINER_multihashmap_iterator_next (struct GNUNET_CONTAINER_MultiHashMapIterator *iter,
731 struct GNUNET_HashCode *key, void **value);
732
733
734/**
735 * Destroy a multihashmap iterator.
736 *
737 * @param iter the iterator to destroy
738 */
739void
740GNUNET_CONTAINER_multihashmap_iterator_destroy (struct GNUNET_CONTAINER_MultiHashMapIterator *iter);
741
742
743/**
694 * Iterate over all entries in the map that match a particular key. 744 * Iterate over all entries in the map that match a particular key.
695 * 745 *
696 * @param map the map 746 * @param map the map
diff --git a/src/util/container_multihashmap.c b/src/util/container_multihashmap.c
index 14ddd06a5..bd22732be 100644
--- a/src/util/container_multihashmap.c
+++ b/src/util/container_multihashmap.c
@@ -100,7 +100,6 @@ union MapEntry
100 */ 100 */
101struct GNUNET_CONTAINER_MultiHashMap 101struct GNUNET_CONTAINER_MultiHashMap
102{ 102{
103
104 /** 103 /**
105 * All of our buckets. 104 * All of our buckets.
106 */ 105 */
@@ -121,6 +120,41 @@ struct GNUNET_CONTAINER_MultiHashMap
121 * GNUNET_YES if the map entries are of type 'struct SmallMapEntry'. 120 * GNUNET_YES if the map entries are of type 'struct SmallMapEntry'.
122 */ 121 */
123 int use_small_entries; 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 multihashmap.
134 * Allows to enumerate elements asynchronously.
135 */
136struct GNUNET_CONTAINER_MultiHashMapIterator
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_MultiHashMap *map;
124}; 158};
125 159
126 160
@@ -353,6 +387,8 @@ GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map,
353 union MapEntry me; 387 union MapEntry me;
354 unsigned int i; 388 unsigned int i;
355 389
390 map->modification_counter++;
391
356 i = idx_of (map, key); 392 i = idx_of (map, key);
357 me = map->map[i]; 393 me = map->map[i];
358 if (map->use_small_entries) 394 if (map->use_small_entries)
@@ -419,6 +455,8 @@ GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap
419 unsigned int i; 455 unsigned int i;
420 int ret; 456 int ret;
421 457
458 map->modification_counter++;
459
422 ret = 0; 460 ret = 0;
423 i = idx_of (map, key); 461 i = idx_of (map, key);
424 me = map->map[i]; 462 me = map->map[i];
@@ -579,6 +617,8 @@ grow (struct GNUNET_CONTAINER_MultiHashMap *map)
579 unsigned int idx; 617 unsigned int idx;
580 unsigned int i; 618 unsigned int i;
581 619
620 map->modification_counter++;
621
582 old_map = map->map; 622 old_map = map->map;
583 old_len = map->map_length; 623 old_len = map->map_length;
584 new_len = old_len * 2; 624 new_len = old_len * 2;
@@ -757,4 +797,96 @@ GNUNET_CONTAINER_multihashmap_get_multiple (const struct
757} 797}
758 798
759 799
800/**
801 * Create an iterator for a multihashmap.
802 * The iterator can be used to retrieve all the elements in the multihashmap
803 * one by one, without having to handle all elements at once (in contrast to
804 * 'GNUNET_CONTAINER_multihashmap_iterate'). Note that the iterator can not be
805 * used anymore if elements have been removed from 'map' after the creation of
806 * the iterator, or 'map' has been destroyed. Adding elements to 'map' may
807 * result in skipped or repeated elements.
808 *
809 * @param map the map to create an iterator for
810 * @return an iterator over the given multihashmap 'map'
811 */
812struct GNUNET_CONTAINER_MultiHashMapIterator *
813GNUNET_CONTAINER_multihashmap_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap *map)
814{
815 struct GNUNET_CONTAINER_MultiHashMapIterator *iter;
816
817 iter = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMapIterator);
818 iter->map = map;
819 iter->modification_counter = map->modification_counter;
820 iter->me = map->map[0];
821 return iter;
822}
823
824
825/**
826 * Retrieve the next element from the hash map at the iterator's position.
827 * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
828 * are not modified.
829 * This operation is only allowed if no elements have been removed from the
830 * multihashmap since the creation of 'iter', and the map has not been destroyed.
831 * Adding elements may result in repeating or skipping elements.
832 *
833 * @param iter the iterator to get the next element from
834 * @param key pointer to store the key in, can be NULL
835 * @param value pointer to store the value in, can be NULL
836 * @return GNUNET_YES we returned an element,
837 * GNUNET_NO if we are out of elements
838 */
839int
840GNUNET_CONTAINER_multihashmap_iterator_next (struct GNUNET_CONTAINER_MultiHashMapIterator *iter,
841 struct GNUNET_HashCode *key, void **value)
842{
843 /* make sure nobody modified the map */
844 GNUNET_assert (iter->modification_counter == iter->map->modification_counter);
845
846 /* look for the next entry, skipping empty buckets */
847 while (1)
848 {
849 if (iter->idx >= iter->map->map_length)
850 return GNUNET_NO;
851 if (GNUNET_YES == iter->map->use_small_entries)
852 {
853 if (NULL != iter->me.sme)
854 {
855 if (NULL != key)
856 *key = *iter->me.sme->key;
857 if (NULL != value)
858 *value = iter->me.sme->value;
859 iter->me.sme = iter->me.sme->next;
860 return GNUNET_YES;
861 }
862 }
863 else
864 {
865 if (NULL != iter->me.bme)
866 {
867 if (NULL != key)
868 *key = iter->me.bme->key;
869 if (NULL != value)
870 *value = iter->me.bme->value;
871 iter->me.bme = iter->me.bme->next;
872 return GNUNET_YES;
873 }
874 }
875 iter->idx++;
876 }
877}
878
879
880/**
881 * Destroy a multihashmap iterator.
882 *
883 * @param iter the iterator to destroy
884 */
885void
886GNUNET_CONTAINER_multihashmap_enumerator_destroy (struct GNUNET_CONTAINER_MultiHashMapIterator *iter)
887{
888 GNUNET_free (iter);
889}
890
891
760/* end of container_multihashmap.c */ 892/* end of container_multihashmap.c */