diff options
author | Florian Dold <florian.dold@gmail.com> | 2013-08-12 14:33:26 +0000 |
---|---|---|
committer | Florian Dold <florian.dold@gmail.com> | 2013-08-12 14:33:26 +0000 |
commit | e0af01758cb7eec5aea8e942c3d54a71b2c2100b (patch) | |
tree | 11c3a656bcce5eeda9bbd85671fecda07448a45c /src/util/container_multihashmap.c | |
parent | 210ad40c32a0aa11696786354690f0230b60b86a (diff) | |
download | gnunet-e0af01758cb7eec5aea8e942c3d54a71b2c2100b.tar.gz gnunet-e0af01758cb7eec5aea8e942c3d54a71b2c2100b.zip |
- external iterator for multihashmap
Diffstat (limited to 'src/util/container_multihashmap.c')
-rw-r--r-- | src/util/container_multihashmap.c | 134 |
1 files changed, 133 insertions, 1 deletions
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 | */ |
101 | struct GNUNET_CONTAINER_MultiHashMap | 101 | struct 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 | */ | ||
136 | struct 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 | */ | ||
812 | struct GNUNET_CONTAINER_MultiHashMapIterator * | ||
813 | GNUNET_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 | */ | ||
839 | int | ||
840 | GNUNET_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 | */ | ||
885 | void | ||
886 | GNUNET_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 */ |