2 This file is part of GNUnet.
3 Copyright (C) 2001-2015 GNUnet e.V.
5 GNUnet is free software: you can redistribute it and/or modify it
6 under the terms of the GNU Affero General Public License as published
7 by the Free Software Foundation, either version 3 of the License,
8 or (at your option) any later version.
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 Affero General Public License for more details.
15 You should have received a copy of the GNU Affero General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
20 * @author Christian Grothoff
24 * Container classes for GNUnet
26 * @defgroup hashmap Container library: MultiHashMap
27 * Hash map with multiple values per key.
29 * @see [Documentation](https://gnunet.org/util_multihashmap)
31 * @defgroup heap Container library: Heap
32 * Min- or max-heap with arbitrary element removal
34 * @defgroup bloomfilter Container library: Bloom filter
35 * Probabilistic set tests
37 * @defgroup dll Container library: Doubly-linked list
39 * @see [Documentation](https://gnunet.org/mdll-api)
41 * @defgroup metadata Container library: Metadata
42 * GNU libextractor key-value pairs
45 #ifndef GNUNET_CONTAINER_LIB_H
46 #define GNUNET_CONTAINER_LIB_H
48 /* add error and config prototypes */
49 #include "gnunet_crypto_lib.h"
53 * Try to compress the given block of data using libz. Only returns
54 * the compressed block if compression worked and the new block is
55 * actually smaller. Decompress using #GNUNET_decompress().
57 * @param data block to compress; if compression
58 * resulted in a smaller block, the first
59 * bytes of data are updated to the compressed
61 * @param old_size number of bytes in data
62 * @param[out] result set to the compressed data, if compression worked
63 * @param[out] new_size set to size of result, if compression worked
64 * @return #GNUNET_YES if compression reduce the size,
65 * #GNUNET_NO if compression did not help
68 GNUNET_try_compression (const char *data,
75 * Decompress input, return the decompressed data as output. Dual to
76 * #GNUNET_try_compression(). Caller must set @a output_size to the
77 * number of bytes that were originally compressed.
79 * @param input compressed data
80 * @param input_size number of bytes in input
81 * @param output_size expected size of the output
82 * @return NULL on error, buffer of @a output_size decompressed bytes otherwise
85 GNUNET_decompress (const char *input,
92 #include <extractor.h>
96 /* definitions from extractor.h we need for the build */
99 * Enumeration defining various sources of keywords. See also
100 * http://dublincore.org/documents/1998/09/dces/
102 enum EXTRACTOR_MetaType {
103 EXTRACTOR_METATYPE_RESERVED = 0,
104 EXTRACTOR_METATYPE_MIMETYPE = 1,
105 EXTRACTOR_METATYPE_FILENAME = 2,
106 EXTRACTOR_METATYPE_COMMENT = 3,
107 EXTRACTOR_METATYPE_TITLE = 4,
108 EXTRACTOR_METATYPE_BOOK_TITLE = 5,
109 EXTRACTOR_METATYPE_JOURNAL_NAME = 8,
110 EXTRACTOR_METATYPE_AUTHOR_NAME = 13,
111 EXTRACTOR_METATYPE_PUBLICATION_DATE = 24,
112 EXTRACTOR_METATYPE_URL = 29,
113 EXTRACTOR_METATYPE_URI = 30,
114 EXTRACTOR_METATYPE_ISRC = 31,
115 EXTRACTOR_METATYPE_UNKNOWN = 45,
116 EXTRACTOR_METATYPE_DESCRIPTION = 46,
117 EXTRACTOR_METATYPE_KEYWORDS = 49,
118 EXTRACTOR_METATYPE_SUBJECT = 52,
119 EXTRACTOR_METATYPE_PACKAGE_NAME = 69,
120 EXTRACTOR_METATYPE_THUMBNAIL = 114,
121 EXTRACTOR_METATYPE_ALBUM = 129,
122 EXTRACTOR_METATYPE_ARTIST = 130,
123 EXTRACTOR_METATYPE_ORIGINAL_TITLE = 162,
124 EXTRACTOR_METATYPE_GNUNET_FULL_DATA = 174,
125 EXTRACTOR_METATYPE_GNUNET_ORIGINAL_FILENAME = 180,
130 * Format in which the extracted meta data is presented.
132 enum EXTRACTOR_MetaFormat {
136 EXTRACTOR_METAFORMAT_UNKNOWN = 0,
139 * 0-terminated, UTF-8 encoded string. "data_len"
142 EXTRACTOR_METAFORMAT_UTF8 = 1,
145 * Some kind of binary format, see given Mime type.
147 EXTRACTOR_METAFORMAT_BINARY = 2,
150 * 0-terminated string. The specific encoding is unknown.
151 * "data_len" is strlen (data)+1.
153 EXTRACTOR_METAFORMAT_C_STRING = 3
158 * Type of a function that libextractor calls for each
159 * meta data item found.
161 * @param cls closure (user-defined)
162 * @param plugin_name name of the plugin that produced this value;
163 * special values can be used (i.e. '<zlib>' for zlib being
164 * used in the main libextractor library and yielding
166 * @param type libextractor-type describing the meta data
167 * @param format basic format information about @a data
168 * @param data_mime_type mime-type of @a data (not of the original file);
169 * can be NULL (if mime-type is not known)
170 * @param data actual meta-data found
171 * @param data_len number of bytes in @a data
172 * @return 0 to continue extracting, 1 to abort
175 (*EXTRACTOR_MetaDataProcessor) (void *cls,
176 const char *plugin_name,
177 enum EXTRACTOR_MetaType type,
178 enum EXTRACTOR_MetaFormat format,
179 const char *data_mime_type,
185 #ifndef EXTRACTOR_METATYPE_GNUNET_ORIGINAL_FILENAME
186 /* hack for LE < 0.6.3 */
187 #define EXTRACTOR_METATYPE_GNUNET_ORIGINAL_FILENAME 180
193 #if 0 /* keep Emacsens' auto-indent happy */
199 /* ******************* bloomfilter ***************** */
202 * @brief bloomfilter representation (opaque)
203 * @ingroup bloomfilter
205 struct GNUNET_CONTAINER_BloomFilter;
209 * @ingroup bloomfilter
210 * Iterator over `struct GNUNET_HashCode`.
213 * @param next set to the next hash code
214 * @return #GNUNET_YES if next was updated
215 * #GNUNET_NO if there are no more entries
218 (*GNUNET_CONTAINER_HashCodeIterator) (void *cls,
219 struct GNUNET_HashCode *next);
223 * @ingroup bloomfilter
224 * Load a Bloom filter from a file.
226 * @param filename the name of the file (or the prefix)
227 * @param size the size of the bloom-filter (number of
228 * bytes of storage space to use); will be rounded up
230 * @param k the number of #GNUNET_CRYPTO_hash-functions to apply per
231 * element (number of bits set per element in the set)
232 * @return the bloomfilter
234 struct GNUNET_CONTAINER_BloomFilter *
235 GNUNET_CONTAINER_bloomfilter_load (const char *filename,
241 * @ingroup bloomfilter
242 * Create a Bloom filter from raw bits.
244 * @param data the raw bits in memory (maybe NULL,
245 * in which case all bits should be considered
247 * @param size the size of the bloom-filter (number of
248 * bytes of storage space to use); also size of @a data
249 * -- unless data is NULL. Must be a power of 2.
250 * @param k the number of #GNUNET_CRYPTO_hash-functions to apply per
251 * element (number of bits set per element in the set)
252 * @return the bloomfilter
254 struct GNUNET_CONTAINER_BloomFilter *
255 GNUNET_CONTAINER_bloomfilter_init (const char *data,
261 * @ingroup bloomfilter
262 * Copy the raw data of this Bloom filter into
263 * the given data array.
265 * @param data where to write the data
266 * @param size the size of the given @a data array
267 * @return #GNUNET_SYSERR if the data array of the wrong size
270 GNUNET_CONTAINER_bloomfilter_get_raw_data (const struct GNUNET_CONTAINER_BloomFilter *bf,
276 * @ingroup bloomfilter
277 * Test if an element is in the filter.
279 * @param e the element
280 * @param bf the filter
281 * @return #GNUNET_YES if the element is in the filter, #GNUNET_NO if not
284 GNUNET_CONTAINER_bloomfilter_test (const struct GNUNET_CONTAINER_BloomFilter *bf,
285 const struct GNUNET_HashCode *e);
289 * @ingroup bloomfilter
290 * Add an element to the filter.
292 * @param bf the filter
293 * @param e the element
296 GNUNET_CONTAINER_bloomfilter_add (struct GNUNET_CONTAINER_BloomFilter *bf,
297 const struct GNUNET_HashCode *e);
301 * @ingroup bloomfilter
302 * Remove an element from the filter.
304 * @param bf the filter
305 * @param e the element to remove
308 GNUNET_CONTAINER_bloomfilter_remove (struct GNUNET_CONTAINER_BloomFilter *bf,
309 const struct GNUNET_HashCode *e);
313 * @ingroup bloomfilter
314 * Create a copy of a bloomfilter.
316 * @param bf the filter
319 struct GNUNET_CONTAINER_BloomFilter *
320 GNUNET_CONTAINER_bloomfilter_copy (const struct GNUNET_CONTAINER_BloomFilter *bf);
325 * @ingroup bloomfilter
326 * Free the space associcated with a filter
327 * in memory, flush to drive if needed (do not
328 * free the space on the drive).
330 * @param bf the filter
333 GNUNET_CONTAINER_bloomfilter_free (struct GNUNET_CONTAINER_BloomFilter *bf);
337 * Get the number of the addresses set per element in the bloom filter.
339 * @param bf the filter
340 * @return addresses set per element in the bf
343 GNUNET_CONTAINER_bloomfilter_get_element_addresses (const struct GNUNET_CONTAINER_BloomFilter *bf);
347 * @ingroup bloomfilter
348 * Get size of the bloom filter.
350 * @param bf the filter
351 * @return number of bytes used for the data of the bloom filter
354 GNUNET_CONTAINER_bloomfilter_get_size (const struct GNUNET_CONTAINER_BloomFilter *bf);
358 * @ingroup bloomfilter
359 * Reset a Bloom filter to empty.
361 * @param bf the filter
364 GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter *bf);
368 * @ingroup bloomfilter
369 * "or" the entries of the given raw data array with the
370 * data of the given Bloom filter. Assumes that
371 * the @a size of the @a data array and the current filter
374 * @param bf the filter
375 * @param data data to OR-in
376 * @param size size of @a data
377 * @return #GNUNET_OK on success
380 GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf,
381 const char *data, size_t size);
385 * @ingroup bloomfilter
386 * "or" the entries of the given raw data array with the
387 * data of the given Bloom filter. Assumes that
388 * the size of the two filters matches.
390 * @param bf the filter
391 * @param to_or the bloomfilter to or-in
392 * @return #GNUNET_OK on success
395 GNUNET_CONTAINER_bloomfilter_or2 (struct GNUNET_CONTAINER_BloomFilter *bf,
396 const struct GNUNET_CONTAINER_BloomFilter *to_or);
400 * @ingroup bloomfilter
401 * Resize a bloom filter. Note that this operation
402 * is pretty costly. Essentially, the Bloom filter
403 * needs to be completely re-build.
405 * @param bf the filter
406 * @param iterator an iterator over all elements stored in the BF
407 * @param iterator_cls closure for @a iterator
408 * @param size the new size for the filter
409 * @param k the new number of #GNUNET_CRYPTO_hash-function to apply per element
412 GNUNET_CONTAINER_bloomfilter_resize (struct GNUNET_CONTAINER_BloomFilter *bf,
413 GNUNET_CONTAINER_HashCodeIterator iterator,
419 /* ****************** metadata ******************* */
423 * Meta data to associate with a file, directory or namespace.
425 struct GNUNET_CONTAINER_MetaData;
430 * Create a fresh meta data container.
432 * @return empty meta-data container
434 struct GNUNET_CONTAINER_MetaData *
435 GNUNET_CONTAINER_meta_data_create (void);
440 * Duplicate a MetaData token.
442 * @param md what to duplicate
443 * @return duplicate meta-data container
445 struct GNUNET_CONTAINER_MetaData *
446 GNUNET_CONTAINER_meta_data_duplicate (const struct GNUNET_CONTAINER_MetaData *md);
453 * @param md what to free
456 GNUNET_CONTAINER_meta_data_destroy (struct GNUNET_CONTAINER_MetaData *md);
461 * Test if two MDs are equal. We consider them equal if
462 * the meta types, formats and content match (we do not
463 * include the mime types and plugins names in this
466 * @param md1 first value to check
467 * @param md2 other value to check
468 * @return #GNUNET_YES if they are equal
471 GNUNET_CONTAINER_meta_data_test_equal (const struct GNUNET_CONTAINER_MetaData *md1,
472 const struct GNUNET_CONTAINER_MetaData *md2);
479 * @param md metadata to extend
480 * @param plugin_name name of the plugin that produced this value;
481 * special values can be used (i.e. '<zlib>' for zlib being
482 * used in the main libextractor library and yielding
484 * @param type libextractor-type describing the meta data
485 * @param format basic format information about data
486 * @param data_mime_type mime-type of data (not of the original file);
487 * can be NULL (if mime-type is not known)
488 * @param data actual meta-data found
489 * @param data_size number of bytes in data
490 * @return #GNUNET_OK on success, #GNUNET_SYSERR if this entry already exists
491 * data_mime_type and plugin_name are not considered for "exists" checks
494 GNUNET_CONTAINER_meta_data_insert (struct GNUNET_CONTAINER_MetaData *md,
495 const char *plugin_name,
496 enum EXTRACTOR_MetaType type,
497 enum EXTRACTOR_MetaFormat format,
498 const char *data_mime_type,
505 * Extend metadata. Merges the meta data from the second argument
506 * into the first, discarding duplicate key-value pairs.
508 * @param md metadata to extend
509 * @param in metadata to merge
512 GNUNET_CONTAINER_meta_data_merge (struct GNUNET_CONTAINER_MetaData *md,
513 const struct GNUNET_CONTAINER_MetaData *in);
520 * @param md metadata to manipulate
521 * @param type type of the item to remove
522 * @param data specific value to remove, NULL to remove all
523 * entries of the given type
524 * @param data_size number of bytes in data
525 * @return #GNUNET_OK on success, #GNUNET_SYSERR if the item does not exist in md
528 GNUNET_CONTAINER_meta_data_delete (struct GNUNET_CONTAINER_MetaData *md,
529 enum EXTRACTOR_MetaType type,
536 * Remove all items in the container.
538 * @param md metadata to manipulate
541 GNUNET_CONTAINER_meta_data_clear (struct GNUNET_CONTAINER_MetaData *md);
546 * Add the current time as the publication date
549 * @param md metadata to modify
552 GNUNET_CONTAINER_meta_data_add_publication_date (struct GNUNET_CONTAINER_MetaData *md);
557 * Iterate over MD entries.
559 * @param md metadata to inspect
560 * @param iter function to call on each entry, return 0 to continue to iterate
561 * and 1 to abort iteration in this function (GNU libextractor API!)
562 * @param iter_cls closure for @a iter
563 * @return number of entries
566 GNUNET_CONTAINER_meta_data_iterate (const struct GNUNET_CONTAINER_MetaData *md,
567 EXTRACTOR_MetaDataProcessor iter,
573 * Get the first MD entry of the given type. Caller
574 * is responsible for freeing the return value.
575 * Also, only meta data items that are strings (0-terminated)
576 * are returned by this function.
578 * @param md metadata to inspect
579 * @param type type to look for
580 * @return NULL if no entry was found
583 GNUNET_CONTAINER_meta_data_get_by_type (const struct GNUNET_CONTAINER_MetaData *md,
584 enum EXTRACTOR_MetaType type);
589 * Get the first matching MD entry of the given types. Caller is
590 * responsible for freeing the return value. Also, only meta data
591 * items that are strings (0-terminated) are returned by this
594 * @param md metadata to inspect
595 * @param ... -1-terminated list of types
596 * @return NULL if we do not have any such entry,
597 * otherwise client is responsible for freeing the value!
600 GNUNET_CONTAINER_meta_data_get_first_by_types (const struct GNUNET_CONTAINER_MetaData *md,
605 * Get a thumbnail from the meta-data (if present). Only matches meta
606 * data with mime type "image" and binary format.
608 * @param md metadata to inspect
609 * @param thumb will be set to the thumbnail data. Must be
610 * freed by the caller!
611 * @return number of bytes in thumbnail, 0 if not available
614 GNUNET_CONTAINER_meta_data_get_thumbnail (const struct GNUNET_CONTAINER_MetaData *md,
615 unsigned char **thumb);
621 * Options for metadata serialization.
623 enum GNUNET_CONTAINER_MetaDataSerializationOptions
627 * Serialize all of the data.
629 GNUNET_CONTAINER_META_DATA_SERIALIZE_FULL = 0,
633 * If not enough space is available, it is acceptable
634 * to only serialize some of the metadata.
636 GNUNET_CONTAINER_META_DATA_SERIALIZE_PART = 1,
640 * Speed is of the essence, do not allow compression.
642 GNUNET_CONTAINER_META_DATA_SERIALIZE_NO_COMPRESS = 2
648 * Serialize meta-data to target.
650 * @param md metadata to serialize
651 * @param target where to write the serialized metadata;
652 * *target can be NULL, in which case memory is allocated
653 * @param max maximum number of bytes available
654 * @param opt is it ok to just write SOME of the
655 * meta-data to match the size constraint,
656 * possibly discarding some data?
657 * @return number of bytes written on success,
658 * -1 on error (typically: not enough
662 GNUNET_CONTAINER_meta_data_serialize (const struct GNUNET_CONTAINER_MetaData *md,
665 enum GNUNET_CONTAINER_MetaDataSerializationOptions opt);
670 * Get the size of the full meta-data in serialized form.
672 * @param md metadata to inspect
673 * @return number of bytes needed for serialization, -1 on error
676 GNUNET_CONTAINER_meta_data_get_serialized_size (const struct GNUNET_CONTAINER_MetaData *md);
681 * Deserialize meta-data. Initializes md.
683 * @param input serialized meta-data.
684 * @param size number of bytes available
685 * @return MD on success, NULL on error (i.e.
688 struct GNUNET_CONTAINER_MetaData *
689 GNUNET_CONTAINER_meta_data_deserialize (const char *input,
693 /* ******************************* HashMap **************************** */
697 * Opaque handle for a HashMap.
699 struct GNUNET_CONTAINER_MultiHashMap;
703 * Opaque handle to an iterator over
706 struct GNUNET_CONTAINER_MultiHashMapIterator;
710 * Options for storing values in the HashMap.
712 enum GNUNET_CONTAINER_MultiHashMapOption
717 * If a value with the given key exists, replace it. Note that the
718 * old value would NOT be freed by replace (the application has to
719 * make sure that this happens if required).
721 GNUNET_CONTAINER_MULTIHASHMAPOPTION_REPLACE,
725 * Allow multiple values with the same key.
727 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE,
731 * There must only be one value per key; storing a value should fail
732 * if a value under the same key already exists.
734 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY,
737 * @ingroup hashmap There must only be one value per key, but don't
738 * bother checking if a value already exists (faster than
739 * #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY; implemented
740 * just like #GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE but this
741 * option documents better what is intended if
742 * #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY is what is
745 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST
751 * Iterator over hash map entries.
754 * @param key current key code
755 * @param value value in the hash map
756 * @return #GNUNET_YES if we should continue to
761 (*GNUNET_CONTAINER_HashMapIterator) (void *cls,
762 const struct GNUNET_HashCode *key,
768 * Create a multi hash map.
770 * @param len initial size (map will grow as needed)
771 * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default;
772 * #GNUNET_YES means that on 'put', the 'key' does not have
773 * to be copied as the destination of the pointer is
774 * guaranteed to be life as long as the value is stored in
775 * the hashmap. This can significantly reduce memory
776 * consumption, but of course is also a recipie for
777 * heap corruption if the assumption is not true. Only
778 * use this if (1) memory use is important in this case and
779 * (2) you have triple-checked that the invariant holds
780 * @return NULL on error
782 struct GNUNET_CONTAINER_MultiHashMap *
783 GNUNET_CONTAINER_multihashmap_create (unsigned int len,
784 int do_not_copy_keys);
789 * Destroy a hash map. Will not free any values
790 * stored in the hash map!
795 GNUNET_CONTAINER_multihashmap_destroy (struct GNUNET_CONTAINER_MultiHashMap *map);
800 * Given a key find a value in the map matching the key.
803 * @param key what to look for
804 * @return NULL if no value was found; note that
805 * this is indistinguishable from values that just
806 * happen to be NULL; use "contains" to test for
807 * key-value pairs with value NULL
810 GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap *map,
811 const struct GNUNET_HashCode *key);
816 * Remove the given key-value pair from the map. Note that if the
817 * key-value pair is in the map multiple times, only one of the pairs
821 * @param key key of the key-value pair
822 * @param value value of the key-value pair
823 * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
827 GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map,
828 const struct GNUNET_HashCode *key,
833 * Remove all entries for the given key from the map.
834 * Note that the values would not be "freed".
837 * @param key identifies values to be removed
838 * @return number of values removed
841 GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap *map,
842 const struct GNUNET_HashCode *key);
847 * Remove all entries from the map.
848 * Note that the values would not be "freed".
851 * @return number of values removed
854 GNUNET_CONTAINER_multihashmap_clear (struct GNUNET_CONTAINER_MultiHashMap *map);
859 * Check if the map contains any value under the given
860 * key (including values that are NULL).
863 * @param key the key to test if a value exists for it
864 * @return #GNUNET_YES if such a value exists,
868 GNUNET_CONTAINER_multihashmap_contains (const struct GNUNET_CONTAINER_MultiHashMap *map,
869 const struct GNUNET_HashCode * key);
874 * Check if the map contains the given value under the given
878 * @param key the key to test if a value exists for it
879 * @param value value to test for
880 * @return #GNUNET_YES if such a value exists,
884 GNUNET_CONTAINER_multihashmap_contains_value (const struct GNUNET_CONTAINER_MultiHashMap *map,
885 const struct GNUNET_HashCode *key,
891 * Store a key-value pair in the map.
894 * @param key key to use
895 * @param value value to use
896 * @param opt options for put
897 * @return #GNUNET_OK on success,
898 * #GNUNET_NO if a value was replaced (with REPLACE)
899 * #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
900 * value already exists
903 GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map,
904 const struct GNUNET_HashCode *key,
906 enum GNUNET_CONTAINER_MultiHashMapOption
911 * Get the number of key-value pairs in the map.
914 * @return the number of key value pairs
917 GNUNET_CONTAINER_multihashmap_size (const struct GNUNET_CONTAINER_MultiHashMap *map);
922 * Iterate over all entries in the map.
925 * @param it function to call on each entry
926 * @param it_cls extra argument to @a it
927 * @return the number of key value pairs processed,
928 * #GNUNET_SYSERR if it aborted iteration
931 GNUNET_CONTAINER_multihashmap_iterate (struct GNUNET_CONTAINER_MultiHashMap *map,
932 GNUNET_CONTAINER_HashMapIterator it,
938 * Create an iterator for a multihashmap.
939 * The iterator can be used to retrieve all the elements in the multihashmap
940 * one by one, without having to handle all elements at once (in contrast to
941 * #GNUNET_CONTAINER_multihashmap_iterate). Note that the iterator can not be
942 * used anymore if elements have been removed from 'map' after the creation of
943 * the iterator, or 'map' has been destroyed. Adding elements to 'map' may
944 * result in skipped or repeated elements.
946 * @param map the map to create an iterator for
947 * @return an iterator over the given multihashmap @a map
949 struct GNUNET_CONTAINER_MultiHashMapIterator *
950 GNUNET_CONTAINER_multihashmap_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap *map);
955 * Retrieve the next element from the hash map at the iterator's
956 * position. If there are no elements left, #GNUNET_NO is returned,
957 * and @a key and @a value are not modified. This operation is only
958 * allowed if no elements have been removed from the multihashmap
959 * since the creation of @a iter, and the map has not been destroyed.
960 * Adding elements may result in repeating or skipping elements.
962 * @param iter the iterator to get the next element from
963 * @param key pointer to store the key in, can be NULL
964 * @param value pointer to store the value in, can be NULL
965 * @return #GNUNET_YES we returned an element,
966 * #GNUNET_NO if we are out of elements
969 GNUNET_CONTAINER_multihashmap_iterator_next (struct GNUNET_CONTAINER_MultiHashMapIterator *iter,
970 struct GNUNET_HashCode *key,
976 * Destroy a multihashmap iterator.
978 * @param iter the iterator to destroy
981 GNUNET_CONTAINER_multihashmap_iterator_destroy (struct GNUNET_CONTAINER_MultiHashMapIterator *iter);
986 * Iterate over all entries in the map that match a particular key.
989 * @param key key that the entries must correspond to
990 * @param it function to call on each entry
991 * @param it_cls extra argument to @a it
992 * @return the number of key value pairs processed,
993 * #GNUNET_SYSERR if it aborted iteration
996 GNUNET_CONTAINER_multihashmap_get_multiple (struct GNUNET_CONTAINER_MultiHashMap *map,
997 const struct GNUNET_HashCode *key,
998 GNUNET_CONTAINER_HashMapIterator it,
1004 * Call @a it on a random value from the map, or not at all
1005 * if the map is empty. Note that this function has linear
1006 * complexity (in the size of the map).
1008 * @param map the map
1009 * @param it function to call on a random entry
1010 * @param it_cls extra argument to @a it
1011 * @return the number of key value pairs processed, zero or one.
1014 GNUNET_CONTAINER_multihashmap_get_random (const struct GNUNET_CONTAINER_MultiHashMap *map,
1015 GNUNET_CONTAINER_HashMapIterator it,
1019 /* ***************** Version of Multihashmap for peer identities ****************** */
1023 * Iterator over hash map entries.
1025 * @param cls closure
1026 * @param key current public key
1027 * @param value value in the hash map
1028 * @return #GNUNET_YES if we should continue to
1030 * #GNUNET_NO if not.
1033 (*GNUNET_CONTAINER_PeerMapIterator) (void *cls,
1034 const struct GNUNET_PeerIdentity *key,
1039 * Hash map from peer identities to values.
1041 struct GNUNET_CONTAINER_MultiPeerMap;
1046 * Create a multi peer map (hash map for public keys of peers).
1048 * @param len initial size (map will grow as needed)
1049 * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default;
1050 * #GNUNET_YES means that on 'put', the 'key' does not have
1051 * to be copied as the destination of the pointer is
1052 * guaranteed to be life as long as the value is stored in
1053 * the hashmap. This can significantly reduce memory
1054 * consumption, but of course is also a recipie for
1055 * heap corruption if the assumption is not true. Only
1056 * use this if (1) memory use is important in this case and
1057 * (2) you have triple-checked that the invariant holds
1058 * @return NULL on error
1060 struct GNUNET_CONTAINER_MultiPeerMap *
1061 GNUNET_CONTAINER_multipeermap_create (unsigned int len,
1062 int do_not_copy_keys);
1067 * Destroy a hash map. Will not free any values
1068 * stored in the hash map!
1070 * @param map the map
1073 GNUNET_CONTAINER_multipeermap_destroy (struct GNUNET_CONTAINER_MultiPeerMap *map);
1078 * Given a key find a value in the map matching the key.
1080 * @param map the map
1081 * @param key what to look for
1082 * @return NULL if no value was found; note that
1083 * this is indistinguishable from values that just
1084 * happen to be NULL; use "contains" to test for
1085 * key-value pairs with value NULL
1088 GNUNET_CONTAINER_multipeermap_get (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1089 const struct GNUNET_PeerIdentity *key);
1094 * Remove the given key-value pair from the map. Note that if the
1095 * key-value pair is in the map multiple times, only one of the pairs
1098 * @param map the map
1099 * @param key key of the key-value pair
1100 * @param value value of the key-value pair
1101 * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
1105 GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map,
1106 const struct GNUNET_PeerIdentity * key,
1111 * Remove all entries for the given key from the map.
1112 * Note that the values would not be "freed".
1114 * @param map the map
1115 * @param key identifies values to be removed
1116 * @return number of values removed
1119 GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap *map,
1120 const struct GNUNET_PeerIdentity *key);
1125 * Check if the map contains any value under the given
1126 * key (including values that are NULL).
1128 * @param map the map
1129 * @param key the key to test if a value exists for it
1130 * @return #GNUNET_YES if such a value exists,
1134 GNUNET_CONTAINER_multipeermap_contains (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1135 const struct GNUNET_PeerIdentity *key);
1140 * Check if the map contains the given value under the given
1143 * @param map the map
1144 * @param key the key to test if a value exists for it
1145 * @param value value to test for
1146 * @return #GNUNET_YES if such a value exists,
1150 GNUNET_CONTAINER_multipeermap_contains_value (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1151 const struct GNUNET_PeerIdentity * key,
1157 * Store a key-value pair in the map.
1159 * @param map the map
1160 * @param key key to use
1161 * @param value value to use
1162 * @param opt options for put
1163 * @return #GNUNET_OK on success,
1164 * #GNUNET_NO if a value was replaced (with REPLACE)
1165 * #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
1166 * value already exists
1169 GNUNET_CONTAINER_multipeermap_put (struct GNUNET_CONTAINER_MultiPeerMap *map,
1170 const struct GNUNET_PeerIdentity *key,
1172 enum GNUNET_CONTAINER_MultiHashMapOption opt);
1177 * Get the number of key-value pairs in the map.
1179 * @param map the map
1180 * @return the number of key value pairs
1183 GNUNET_CONTAINER_multipeermap_size (const struct GNUNET_CONTAINER_MultiPeerMap *map);
1188 * Iterate over all entries in the map.
1190 * @param map the map
1191 * @param it function to call on each entry
1192 * @param it_cls extra argument to @a it
1193 * @return the number of key value pairs processed,
1194 * #GNUNET_SYSERR if it aborted iteration
1197 GNUNET_CONTAINER_multipeermap_iterate (struct GNUNET_CONTAINER_MultiPeerMap *map,
1198 GNUNET_CONTAINER_PeerMapIterator it,
1202 struct GNUNET_CONTAINER_MultiPeerMapIterator;
1205 * Create an iterator for a multihashmap.
1206 * The iterator can be used to retrieve all the elements in the multihashmap
1207 * one by one, without having to handle all elements at once (in contrast to
1208 * #GNUNET_CONTAINER_multipeermap_iterate). Note that the iterator can not be
1209 * used anymore if elements have been removed from @a map after the creation of
1210 * the iterator, or 'map' has been destroyed. Adding elements to @a map may
1211 * result in skipped or repeated elements.
1213 * @param map the map to create an iterator for
1214 * @return an iterator over the given multihashmap @a map
1216 struct GNUNET_CONTAINER_MultiPeerMapIterator *
1217 GNUNET_CONTAINER_multipeermap_iterator_create (const struct GNUNET_CONTAINER_MultiPeerMap *map);
1222 * Retrieve the next element from the hash map at the iterator's
1223 * position. If there are no elements left, #GNUNET_NO is returned,
1224 * and @a key and @a value are not modified. This operation is only
1225 * allowed if no elements have been removed from the multihashmap
1226 * since the creation of @a iter, and the map has not been destroyed.
1227 * Adding elements may result in repeating or skipping elements.
1229 * @param iter the iterator to get the next element from
1230 * @param key pointer to store the key in, can be NULL
1231 * @param value pointer to store the value in, can be NULL
1232 * @return #GNUNET_YES we returned an element,
1233 * #GNUNET_NO if we are out of elements
1236 GNUNET_CONTAINER_multipeermap_iterator_next (struct GNUNET_CONTAINER_MultiPeerMapIterator *iter,
1237 struct GNUNET_PeerIdentity *key,
1238 const void **value);
1243 * Destroy a multipeermap iterator.
1245 * @param iter the iterator to destroy
1248 GNUNET_CONTAINER_multipeermap_iterator_destroy (struct GNUNET_CONTAINER_MultiPeerMapIterator *iter);
1253 * Iterate over all entries in the map that match a particular key.
1255 * @param map the map
1256 * @param key public key that the entries must correspond to
1257 * @param it function to call on each entry
1258 * @param it_cls extra argument to @a it
1259 * @return the number of key value pairs processed,
1260 * #GNUNET_SYSERR if it aborted iteration
1263 GNUNET_CONTAINER_multipeermap_get_multiple (struct GNUNET_CONTAINER_MultiPeerMap *map,
1264 const struct GNUNET_PeerIdentity *key,
1265 GNUNET_CONTAINER_PeerMapIterator it,
1271 * Call @a it on a random value from the map, or not at all
1272 * if the map is empty. Note that this function has linear
1273 * complexity (in the size of the map).
1275 * @param map the map
1276 * @param it function to call on a random entry
1277 * @param it_cls extra argument to @a it
1278 * @return the number of key value pairs processed, zero or one.
1281 GNUNET_CONTAINER_multipeermap_get_random (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1282 GNUNET_CONTAINER_PeerMapIterator it,
1286 /* ***************** Version of Multihashmap for short hashes ****************** */
1290 * Iterator over hash map entries.
1292 * @param cls closure
1293 * @param key current public key
1294 * @param value value in the hash map
1295 * @return #GNUNET_YES if we should continue to
1297 * #GNUNET_NO if not.
1300 (*GNUNET_CONTAINER_ShortmapIterator) (void *cls,
1301 const struct GNUNET_ShortHashCode *key,
1306 * Hash map from peer identities to values.
1308 struct GNUNET_CONTAINER_MultiShortmap;
1313 * Create a multi peer map (hash map for public keys of peers).
1315 * @param len initial size (map will grow as needed)
1316 * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default;
1317 * #GNUNET_YES means that on 'put', the 'key' does not have
1318 * to be copied as the destination of the pointer is
1319 * guaranteed to be life as long as the value is stored in
1320 * the hashmap. This can significantly reduce memory
1321 * consumption, but of course is also a recipie for
1322 * heap corruption if the assumption is not true. Only
1323 * use this if (1) memory use is important in this case and
1324 * (2) you have triple-checked that the invariant holds
1325 * @return NULL on error
1327 struct GNUNET_CONTAINER_MultiShortmap *
1328 GNUNET_CONTAINER_multishortmap_create (unsigned int len,
1329 int do_not_copy_keys);
1334 * Destroy a hash map. Will not free any values
1335 * stored in the hash map!
1337 * @param map the map
1340 GNUNET_CONTAINER_multishortmap_destroy (struct GNUNET_CONTAINER_MultiShortmap *map);
1345 * Given a key find a value in the map matching the key.
1347 * @param map the map
1348 * @param key what to look for
1349 * @return NULL if no value was found; note that
1350 * this is indistinguishable from values that just
1351 * happen to be NULL; use "contains" to test for
1352 * key-value pairs with value NULL
1355 GNUNET_CONTAINER_multishortmap_get (const struct GNUNET_CONTAINER_MultiShortmap *map,
1356 const struct GNUNET_ShortHashCode *key);
1361 * Remove the given key-value pair from the map. Note that if the
1362 * key-value pair is in the map multiple times, only one of the pairs
1365 * @param map the map
1366 * @param key key of the key-value pair
1367 * @param value value of the key-value pair
1368 * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
1372 GNUNET_CONTAINER_multishortmap_remove (struct GNUNET_CONTAINER_MultiShortmap *map,
1373 const struct GNUNET_ShortHashCode * key,
1378 * Remove all entries for the given key from the map.
1379 * Note that the values would not be "freed".
1381 * @param map the map
1382 * @param key identifies values to be removed
1383 * @return number of values removed
1386 GNUNET_CONTAINER_multishortmap_remove_all (struct GNUNET_CONTAINER_MultiShortmap *map,
1387 const struct GNUNET_ShortHashCode *key);
1392 * Check if the map contains any value under the given
1393 * key (including values that are NULL).
1395 * @param map the map
1396 * @param key the key to test if a value exists for it
1397 * @return #GNUNET_YES if such a value exists,
1401 GNUNET_CONTAINER_multishortmap_contains (const struct GNUNET_CONTAINER_MultiShortmap *map,
1402 const struct GNUNET_ShortHashCode *key);
1407 * Check if the map contains the given value under the given
1410 * @param map the map
1411 * @param key the key to test if a value exists for it
1412 * @param value value to test for
1413 * @return #GNUNET_YES if such a value exists,
1417 GNUNET_CONTAINER_multishortmap_contains_value (const struct GNUNET_CONTAINER_MultiShortmap *map,
1418 const struct GNUNET_ShortHashCode * key,
1424 * Store a key-value pair in the map.
1426 * @param map the map
1427 * @param key key to use
1428 * @param value value to use
1429 * @param opt options for put
1430 * @return #GNUNET_OK on success,
1431 * #GNUNET_NO if a value was replaced (with REPLACE)
1432 * #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
1433 * value already exists
1436 GNUNET_CONTAINER_multishortmap_put (struct GNUNET_CONTAINER_MultiShortmap *map,
1437 const struct GNUNET_ShortHashCode *key,
1439 enum GNUNET_CONTAINER_MultiHashMapOption opt);
1444 * Get the number of key-value pairs in the map.
1446 * @param map the map
1447 * @return the number of key value pairs
1450 GNUNET_CONTAINER_multishortmap_size (const struct GNUNET_CONTAINER_MultiShortmap *map);
1455 * Iterate over all entries in the map.
1457 * @param map the map
1458 * @param it function to call on each entry
1459 * @param it_cls extra argument to @a it
1460 * @return the number of key value pairs processed,
1461 * #GNUNET_SYSERR if it aborted iteration
1464 GNUNET_CONTAINER_multishortmap_iterate (struct GNUNET_CONTAINER_MultiShortmap *map,
1465 GNUNET_CONTAINER_ShortmapIterator it,
1469 struct GNUNET_CONTAINER_MultiShortmapIterator;
1474 * Create an iterator for a multihashmap.
1475 * The iterator can be used to retrieve all the elements in the multihashmap
1476 * one by one, without having to handle all elements at once (in contrast to
1477 * #GNUNET_CONTAINER_multishortmap_iterate). Note that the iterator can not be
1478 * used anymore if elements have been removed from @a map after the creation of
1479 * the iterator, or 'map' has been destroyed. Adding elements to @a map may
1480 * result in skipped or repeated elements.
1482 * @param map the map to create an iterator for
1483 * @return an iterator over the given multihashmap @a map
1485 struct GNUNET_CONTAINER_MultiShortmapIterator *
1486 GNUNET_CONTAINER_multishortmap_iterator_create (const struct GNUNET_CONTAINER_MultiShortmap *map);
1491 * Retrieve the next element from the hash map at the iterator's
1492 * position. If there are no elements left, #GNUNET_NO is returned,
1493 * and @a key and @a value are not modified. This operation is only
1494 * allowed if no elements have been removed from the multihashmap
1495 * since the creation of @a iter, and the map has not been destroyed.
1496 * Adding elements may result in repeating or skipping elements.
1498 * @param iter the iterator to get the next element from
1499 * @param key pointer to store the key in, can be NULL
1500 * @param value pointer to store the value in, can be NULL
1501 * @return #GNUNET_YES we returned an element,
1502 * #GNUNET_NO if we are out of elements
1505 GNUNET_CONTAINER_multishortmap_iterator_next (struct GNUNET_CONTAINER_MultiShortmapIterator *iter,
1506 struct GNUNET_ShortHashCode *key,
1507 const void **value);
1512 * Destroy a multishortmap iterator.
1514 * @param iter the iterator to destroy
1517 GNUNET_CONTAINER_multishortmap_iterator_destroy (struct GNUNET_CONTAINER_MultiShortmapIterator *iter);
1522 * Iterate over all entries in the map that match a particular key.
1524 * @param map the map
1525 * @param key public key that the entries must correspond to
1526 * @param it function to call on each entry
1527 * @param it_cls extra argument to @a it
1528 * @return the number of key value pairs processed,
1529 * #GNUNET_SYSERR if it aborted iteration
1532 GNUNET_CONTAINER_multishortmap_get_multiple (struct GNUNET_CONTAINER_MultiShortmap *map,
1533 const struct GNUNET_ShortHashCode *key,
1534 GNUNET_CONTAINER_ShortmapIterator it,
1540 * Call @a it on a random value from the map, or not at all
1541 * if the map is empty. Note that this function has linear
1542 * complexity (in the size of the map).
1544 * @param map the map
1545 * @param it function to call on a random entry
1546 * @param it_cls extra argument to @a it
1547 * @return the number of key value pairs processed, zero or one.
1550 GNUNET_CONTAINER_multishortmap_get_random (const struct GNUNET_CONTAINER_MultiShortmap *map,
1551 GNUNET_CONTAINER_ShortmapIterator it,
1555 /* Version of multihashmap with 32 bit keys */
1559 * Opaque handle for the 32-bit key HashMap.
1561 struct GNUNET_CONTAINER_MultiHashMap32;
1566 * Opaque handle to an iterator over
1567 * a 32-bit key multihashmap.
1569 struct GNUNET_CONTAINER_MultiHashMap32Iterator;
1574 * Iterator over hash map entries.
1576 * @param cls closure
1577 * @param key current key code
1578 * @param value value in the hash map
1579 * @return #GNUNET_YES if we should continue to
1581 * #GNUNET_NO if not.
1584 (*GNUNET_CONTAINER_HashMapIterator32) (void *cls,
1591 * Create a 32-bit key multi hash map.
1593 * @param len initial size (map will grow as needed)
1594 * @return NULL on error
1596 struct GNUNET_CONTAINER_MultiHashMap32 *
1597 GNUNET_CONTAINER_multihashmap32_create (unsigned int len);
1602 * Destroy a 32-bit key hash map. Will not free any values
1603 * stored in the hash map!
1605 * @param map the map
1608 GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32 *map);
1613 * Get the number of key-value pairs in the map.
1615 * @param map the map
1616 * @return the number of key value pairs
1619 GNUNET_CONTAINER_multihashmap32_size (const struct
1620 GNUNET_CONTAINER_MultiHashMap32 *map);
1625 * Given a key find a value in the map matching the key.
1627 * @param map the map
1628 * @param key what to look for
1629 * @return NULL if no value was found; note that
1630 * this is indistinguishable from values that just
1631 * happen to be NULL; use "contains" to test for
1632 * key-value pairs with value NULL
1635 GNUNET_CONTAINER_multihashmap32_get (const struct
1636 GNUNET_CONTAINER_MultiHashMap32 *map,
1642 * Iterate over all entries in the map.
1644 * @param map the map
1645 * @param it function to call on each entry
1646 * @param it_cls extra argument to @a it
1647 * @return the number of key value pairs processed,
1648 * #GNUNET_SYSERR if it aborted iteration
1651 GNUNET_CONTAINER_multihashmap32_iterate (struct GNUNET_CONTAINER_MultiHashMap32 *map,
1652 GNUNET_CONTAINER_HashMapIterator32 it,
1658 * Remove the given key-value pair from the map. Note that if the
1659 * key-value pair is in the map multiple times, only one of the pairs
1662 * @param map the map
1663 * @param key key of the key-value pair
1664 * @param value value of the key-value pair
1665 * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
1669 GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 *map,
1676 * Remove all entries for the given key from the map.
1677 * Note that the values would not be "freed".
1679 * @param map the map
1680 * @param key identifies values to be removed
1681 * @return number of values removed
1684 GNUNET_CONTAINER_multihashmap32_remove_all (struct GNUNET_CONTAINER_MultiHashMap32 *map,
1690 * Check if the map contains any value under the given
1691 * key (including values that are NULL).
1693 * @param map the map
1694 * @param key the key to test if a value exists for it
1695 * @return #GNUNET_YES if such a value exists,
1699 GNUNET_CONTAINER_multihashmap32_contains (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
1705 * Check if the map contains the given value under the given
1708 * @param map the map
1709 * @param key the key to test if a value exists for it
1710 * @param value value to test for
1711 * @return #GNUNET_YES if such a value exists,
1715 GNUNET_CONTAINER_multihashmap32_contains_value (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
1722 * Store a key-value pair in the map.
1724 * @param map the map
1725 * @param key key to use
1726 * @param value value to use
1727 * @param opt options for put
1728 * @return #GNUNET_OK on success,
1729 * #GNUNET_NO if a value was replaced (with REPLACE)
1730 * #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
1731 * value already exists
1734 GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32 *map,
1737 enum GNUNET_CONTAINER_MultiHashMapOption opt);
1742 * Iterate over all entries in the map that match a particular key.
1744 * @param map the map
1745 * @param key key that the entries must correspond to
1746 * @param it function to call on each entry
1747 * @param it_cls extra argument to @a it
1748 * @return the number of key value pairs processed,
1749 * #GNUNET_SYSERR if it aborted iteration
1752 GNUNET_CONTAINER_multihashmap32_get_multiple (struct GNUNET_CONTAINER_MultiHashMap32 *map,
1754 GNUNET_CONTAINER_HashMapIterator32 it,
1759 * Create an iterator for a 32-bit multihashmap.
1760 * The iterator can be used to retrieve all the elements in the multihashmap
1761 * one by one, without having to handle all elements at once (in contrast to
1762 * #GNUNET_CONTAINER_multihashmap32_iterate). Note that the iterator can not be
1763 * used anymore if elements have been removed from 'map' after the creation of
1764 * the iterator, or 'map' has been destroyed. Adding elements to 'map' may
1765 * result in skipped or repeated elements.
1767 * @param map the map to create an iterator for
1768 * @return an iterator over the given multihashmap map
1770 struct GNUNET_CONTAINER_MultiHashMap32Iterator *
1771 GNUNET_CONTAINER_multihashmap32_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap32 *map);
1775 * Retrieve the next element from the hash map at the iterator's position.
1776 * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
1778 * This operation is only allowed if no elements have been removed from the
1779 * multihashmap since the creation of 'iter', and the map has not been destroyed.
1780 * Adding elements may result in repeating or skipping elements.
1782 * @param iter the iterator to get the next element from
1783 * @param key pointer to store the key in, can be NULL
1784 * @param value pointer to store the value in, can be NULL
1785 * @return #GNUNET_YES we returned an element,
1786 * #GNUNET_NO if we are out of elements
1789 GNUNET_CONTAINER_multihashmap32_iterator_next (struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter,
1791 const void **value);
1795 * Destroy a 32-bit multihashmap iterator.
1797 * @param iter the iterator to destroy
1800 GNUNET_CONTAINER_multihashmap32_iterator_destroy (struct GNUNET_CONTAINER_MultiHashMapIterator *iter);
1803 /* ******************** doubly-linked list *************** */
1804 /* To avoid mistakes: head->prev == tail->next == NULL */
1808 * Insert an element at the head of a DLL. Assumes that head, tail and
1809 * element are structs with prev and next fields.
1811 * @param head pointer to the head of the DLL
1812 * @param tail pointer to the tail of the DLL
1813 * @param element element to insert
1815 #define GNUNET_CONTAINER_DLL_insert(head,tail,element) do { \
1816 GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1817 GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1818 (element)->next = (head); \
1819 (element)->prev = NULL; \
1820 if ((tail) == NULL) \
1823 (head)->prev = element; \
1824 (head) = (element); } while (0)
1829 * Insert an element at the tail of a DLL. Assumes that head, tail and
1830 * element are structs with prev and next fields.
1832 * @param head pointer to the head of the DLL
1833 * @param tail pointer to the tail of the DLL
1834 * @param element element to insert
1836 #define GNUNET_CONTAINER_DLL_insert_tail(head,tail,element) do { \
1837 GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1838 GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1839 (element)->prev = (tail); \
1840 (element)->next = NULL; \
1841 if ((head) == NULL) \
1844 (tail)->next = element; \
1845 (tail) = (element); } while (0)
1850 * Insert an element into a DLL after the given other element. Insert
1851 * at the head if the other element is NULL.
1853 * @param head pointer to the head of the DLL
1854 * @param tail pointer to the tail of the DLL
1855 * @param other prior element, NULL for insertion at head of DLL
1856 * @param element element to insert
1858 #define GNUNET_CONTAINER_DLL_insert_after(head,tail,other,element) do { \
1859 GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1860 GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1861 (element)->prev = (other); \
1862 if (NULL == other) \
1864 (element)->next = (head); \
1865 (head) = (element); \
1869 (element)->next = (other)->next; \
1870 (other)->next = (element); \
1872 if (NULL == (element)->next) \
1873 (tail) = (element); \
1875 (element)->next->prev = (element); } while (0)
1880 * Insert an element into a DLL before the given other element. Insert
1881 * at the tail if the other element is NULL.
1883 * @param head pointer to the head of the DLL
1884 * @param tail pointer to the tail of the DLL
1885 * @param other prior element, NULL for insertion at head of DLL
1886 * @param element element to insert
1888 #define GNUNET_CONTAINER_DLL_insert_before(head,tail,other,element) do { \
1889 GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1890 GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1891 (element)->next = (other); \
1892 if (NULL == other) \
1894 (element)->prev = (tail); \
1895 (tail) = (element); \
1899 (element)->prev = (other)->prev; \
1900 (other)->prev = (element); \
1902 if (NULL == (element)->prev) \
1903 (head) = (element); \
1905 (element)->prev->next = (element); } while (0)
1910 * Remove an element from a DLL. Assumes that head, tail and
1911 * element point to structs with prev and next fields.
1913 * Using the head or tail pointer as the element
1914 * argument does NOT work with this macro.
1915 * Make sure to store head/tail in another pointer
1916 * and use it to remove the head or tail of the list.
1918 * @param head pointer to the head of the DLL
1919 * @param tail pointer to the tail of the DLL
1920 * @param element element to remove
1922 #define GNUNET_CONTAINER_DLL_remove(head,tail,element) do { \
1923 GNUNET_assert ( ( (element)->prev != NULL) || ((head) == (element))); \
1924 GNUNET_assert ( ( (element)->next != NULL) || ((tail) == (element))); \
1925 if ((element)->prev == NULL) \
1926 (head) = (element)->next; \
1928 (element)->prev->next = (element)->next; \
1929 if ((element)->next == NULL) \
1930 (tail) = (element)->prev; \
1932 (element)->next->prev = (element)->prev; \
1933 (element)->next = NULL; \
1934 (element)->prev = NULL; } while (0)
1937 /* ************ Multi-DLL interface, allows DLL elements to be
1938 in multiple lists at the same time *********************** */
1942 * Insert an element at the head of a MDLL. Assumes that head, tail and
1943 * element are structs with prev and next fields.
1945 * @param mdll suffix name for the next and prev pointers in the element
1946 * @param head pointer to the head of the MDLL
1947 * @param tail pointer to the tail of the MDLL
1948 * @param element element to insert
1950 #define GNUNET_CONTAINER_MDLL_insert(mdll,head,tail,element) do { \
1951 GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1952 GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1953 (element)->next_##mdll = (head); \
1954 (element)->prev_##mdll = NULL; \
1955 if ((tail) == NULL) \
1958 (head)->prev_##mdll = element; \
1959 (head) = (element); } while (0)
1964 * Insert an element at the tail of a MDLL. Assumes that head, tail and
1965 * element are structs with prev and next fields.
1967 * @param mdll suffix name for the next and prev pointers in the element
1968 * @param head pointer to the head of the MDLL
1969 * @param tail pointer to the tail of the MDLL
1970 * @param element element to insert
1972 #define GNUNET_CONTAINER_MDLL_insert_tail(mdll,head,tail,element) do { \
1973 GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1974 GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1975 (element)->prev_##mdll = (tail); \
1976 (element)->next_##mdll = NULL; \
1977 if ((head) == NULL) \
1980 (tail)->next_##mdll = element; \
1981 (tail) = (element); } while (0)
1986 * Insert an element into a MDLL after the given other element. Insert
1987 * at the head if the other element is NULL.
1989 * @param mdll suffix name for the next and prev pointers in the element
1990 * @param head pointer to the head of the MDLL
1991 * @param tail pointer to the tail of the MDLL
1992 * @param other prior element, NULL for insertion at head of MDLL
1993 * @param element element to insert
1995 #define GNUNET_CONTAINER_MDLL_insert_after(mdll,head,tail,other,element) do { \
1996 GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1997 GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1998 (element)->prev_##mdll = (other); \
1999 if (NULL == other) \
2001 (element)->next_##mdll = (head); \
2002 (head) = (element); \
2006 (element)->next_##mdll = (other)->next_##mdll; \
2007 (other)->next_##mdll = (element); \
2009 if (NULL == (element)->next_##mdll) \
2010 (tail) = (element); \
2012 (element)->next->prev_##mdll = (element); } while (0)
2017 * Insert an element into a MDLL before the given other element. Insert
2018 * at the tail if the other element is NULL.
2020 * @param mdll suffix name for the next and prev pointers in the element
2021 * @param head pointer to the head of the MDLL
2022 * @param tail pointer to the tail of the MDLL
2023 * @param other prior element, NULL for insertion at head of MDLL
2024 * @param element element to insert
2026 #define GNUNET_CONTAINER_MDLL_insert_before(mdll,head,tail,other,element) do { \
2027 GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
2028 GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
2029 (element)->next_##mdll = (other); \
2030 if (NULL == other) \
2032 (element)->prev = (tail); \
2033 (tail) = (element); \
2037 (element)->prev_##mdll = (other)->prev_##mdll; \
2038 (other)->prev_##mdll = (element); \
2040 if (NULL == (element)->prev_##mdll) \
2041 (head) = (element); \
2043 (element)->prev_##mdll->next_##mdll = (element); } while (0)
2048 * Remove an element from a MDLL. Assumes
2049 * that head, tail and element are structs
2050 * with prev and next fields.
2052 * @param mdll suffix name for the next and prev pointers in the element
2053 * @param head pointer to the head of the MDLL
2054 * @param tail pointer to the tail of the MDLL
2055 * @param element element to remove
2057 #define GNUNET_CONTAINER_MDLL_remove(mdll,head,tail,element) do { \
2058 GNUNET_assert ( ( (element)->prev_##mdll != NULL) || ((head) == (element))); \
2059 GNUNET_assert ( ( (element)->next_##mdll != NULL) || ((tail) == (element))); \
2060 if ((element)->prev_##mdll == NULL) \
2061 (head) = (element)->next_##mdll; \
2063 (element)->prev_##mdll->next_##mdll = (element)->next_##mdll; \
2064 if ((element)->next_##mdll == NULL) \
2065 (tail) = (element)->prev_##mdll; \
2067 (element)->next_##mdll->prev_##mdll = (element)->prev_##mdll; \
2068 (element)->next_##mdll = NULL; \
2069 (element)->prev_##mdll = NULL; } while (0)
2074 * Insertion sort of @a element into DLL from @a head to @a tail
2075 * sorted by @a comparator.
2077 * @param TYPE element type of the elements, i.e. `struct ListElement`
2078 * @param comparator function like memcmp() to compare elements; takes
2079 * three arguments, the @a comparator_cls and two elements,
2080 * returns an `int` (-1, 0 or 1)
2081 * @param comparator_cls closure for @a comparator
2082 * @param[in,out] head head of DLL
2083 * @param[in,out] tail tail of DLL
2084 * @param element element to insert
2086 #define GNUNET_CONTAINER_DLL_insert_sorted(TYPE,comparator,comparator_cls,head,tail,element) do { \
2087 if ( (NULL == head) || \
2088 (0 < comparator (comparator_cls, \
2092 /* insert at head, element < head */ \
2093 GNUNET_CONTAINER_DLL_insert (head, \
2105 comparator (comparator_cls, \
2108 break; /* element < pos */ \
2109 if (NULL == pos) /* => element > tail */ \
2111 GNUNET_CONTAINER_DLL_insert_tail (head, \
2115 else /* prev < element < pos */ \
2117 GNUNET_CONTAINER_DLL_insert_after (head, \
2126 /* ******************** Heap *************** */
2131 * Cost by which elements in a heap can be ordered.
2133 typedef uint64_t GNUNET_CONTAINER_HeapCostType;
2138 * Heap type, either max or min.
2140 enum GNUNET_CONTAINER_HeapOrder
2144 * Heap with the maximum cost at the root.
2146 GNUNET_CONTAINER_HEAP_ORDER_MAX,
2150 * Heap with the minimum cost at the root.
2152 GNUNET_CONTAINER_HEAP_ORDER_MIN
2160 struct GNUNET_CONTAINER_Heap;
2165 * Handle to a node in a heap.
2167 struct GNUNET_CONTAINER_HeapNode;
2172 * Create a new heap.
2174 * @param order how should the heap be sorted?
2175 * @return handle to the heap
2177 struct GNUNET_CONTAINER_Heap *
2178 GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order);
2183 * Destroys the heap. Only call on a heap that
2186 * @param heap heap to destroy
2189 GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap);
2194 * Get element stored at the root of @a heap.
2196 * @param heap Heap to inspect.
2197 * @return Element at the root, or NULL if heap is empty.
2200 GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap);
2204 * Get @a element and @a cost stored at the root of @a heap.
2206 * @param[in] heap Heap to inspect.
2207 * @param[out] element Root element is returned here.
2208 * @param[out] cost Cost of @a element is returned here.
2209 * @return #GNUNET_YES if an element is returned,
2210 * #GNUNET_NO if the heap is empty.
2213 GNUNET_CONTAINER_heap_peek2 (const struct GNUNET_CONTAINER_Heap *heap,
2215 GNUNET_CONTAINER_HeapCostType *cost);
2220 * Get the current size of the heap
2222 * @param heap the heap to get the size of
2223 * @return number of elements stored
2226 GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap);
2231 * Get the current cost of the node
2233 * @param node the node to get the cost of
2234 * @return cost of the node
2236 GNUNET_CONTAINER_HeapCostType
2237 GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode *node);
2244 * @param cls closure
2245 * @param node internal node of the heap
2246 * @param element value stored at the node
2247 * @param cost cost associated with the node
2248 * @return #GNUNET_YES if we should continue to iterate,
2249 * #GNUNET_NO if not.
2252 (*GNUNET_CONTAINER_HeapIterator) (void *cls,
2253 struct GNUNET_CONTAINER_HeapNode *node,
2255 GNUNET_CONTAINER_HeapCostType cost);
2260 * Iterate over all entries in the heap.
2262 * @param heap the heap
2263 * @param iterator function to call on each entry
2264 * @param iterator_cls closure for @a iterator
2267 GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
2268 GNUNET_CONTAINER_HeapIterator iterator,
2269 void *iterator_cls);
2273 * Perform a random walk of the tree. The walk is biased
2274 * towards elements closer to the root of the tree (since
2275 * each walk starts at the root and ends at a random leaf).
2276 * The heap internally tracks the current position of the
2279 * @param heap heap to walk
2280 * @return data stored at the next random node in the walk;
2281 * NULL if the tree is empty.
2284 GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap);
2289 * Inserts a new element into the heap.
2291 * @param heap heap to modify
2292 * @param element element to insert
2293 * @param cost cost for the element
2294 * @return node for the new element
2296 struct GNUNET_CONTAINER_HeapNode *
2297 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap,
2299 GNUNET_CONTAINER_HeapCostType cost);
2304 * Remove root of the heap.
2306 * @param heap heap to modify
2307 * @return element data stored at the root node
2310 GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap);
2315 * Removes a node from the heap.
2317 * @param node node to remove
2318 * @return element data stored at the node, NULL if heap is empty
2321 GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node);
2326 * Updates the cost of any node in the tree
2328 * @param node node for which the cost is to be changed
2329 * @param new_cost new cost for the node
2332 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_HeapNode *node,
2333 GNUNET_CONTAINER_HeapCostType new_cost);
2336 #if 0 /* keep Emacsens' auto-indent happy */
2344 /* ifndef GNUNET_CONTAINER_LIB_H */
2346 /* end of gnunet_container_lib.h */