2 This file is part of GNUnet.
3 Copyright (C) 2001-2015 Christian Grothoff (and other contributing authors)
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.
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.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18 Boston, MA 02110-1301, USA.
22 * @file include/gnunet_container_lib.h
23 * @brief container classes for GNUnet
24 * @author Christian Grothoff
26 * @defgroup hashmap multi hash-map
27 * @defgroup heap min- or max-heap with arbitrary element removal
28 * @defgroup bloomfilter Bloom filter (probabilistic set tests)
29 * @defgroup dll Doubly-linked list
30 * @defgroup metadata Meta data (GNU libextractor key-value pairs)
33 #ifndef GNUNET_CONTAINER_LIB_H
34 #define GNUNET_CONTAINER_LIB_H
36 /* add error and config prototypes */
37 #include "gnunet_crypto_lib.h"
41 * Try to compress the given block of data using libz. Only returns
42 * the compressed block if compression worked and the new block is
43 * actually smaller. Decompress using #GNUNET_decompress().
45 * @param data block to compress; if compression
46 * resulted in a smaller block, the first
47 * bytes of data are updated to the compressed
49 * @param old_size number of bytes in data
50 * @param[out] result set to the compressed data, if compression worked
51 * @param[out] new_size set to size of result, if compression worked
52 * @return #GNUNET_YES if compression reduce the size,
53 * #GNUNET_NO if compression did not help
56 GNUNET_try_compression (const char *data,
63 * Decompress input, return the decompressed data as output. Dual to
64 * #GNUNET_try_compression(). Caller must set @a output_size to the
65 * number of bytes that were originally compressed.
67 * @param input compressed data
68 * @param input_size number of bytes in input
69 * @param output_size expected size of the output
70 * @return NULL on error, buffer of @a output_size decompressed bytes otherwise
73 GNUNET_decompress (const char *input,
78 #if HAVE_EXTRACTOR_H && HAVE_LIBEXTRACTOR
80 #include <extractor.h>
86 /* definitions from extractor.h we need for the build */
89 * Enumeration defining various sources of keywords. See also
90 * http://dublincore.org/documents/1998/09/dces/
92 enum EXTRACTOR_MetaType {
93 EXTRACTOR_METATYPE_RESERVED = 0,
94 EXTRACTOR_METATYPE_MIMETYPE = 1,
95 EXTRACTOR_METATYPE_FILENAME = 2,
96 EXTRACTOR_METATYPE_COMMENT = 3,
97 EXTRACTOR_METATYPE_TITLE = 4,
98 EXTRACTOR_METATYPE_BOOK_TITLE = 5,
99 EXTRACTOR_METATYPE_JOURNAL_NAME = 8,
100 EXTRACTOR_METATYPE_AUTHOR_NAME = 13,
101 EXTRACTOR_METATYPE_PUBLICATION_DATE = 24,
102 EXTRACTOR_METATYPE_URL = 29,
103 EXTRACTOR_METATYPE_URI = 30,
104 EXTRACTOR_METATYPE_ISRC = 31,
105 EXTRACTOR_METATYPE_UNKNOWN = 45,
106 EXTRACTOR_METATYPE_DESCRIPTION = 46,
107 EXTRACTOR_METATYPE_KEYWORDS = 49,
108 EXTRACTOR_METATYPE_SUBJECT = 52,
109 EXTRACTOR_METATYPE_PACKAGE_NAME = 69,
110 EXTRACTOR_METATYPE_THUMBNAIL = 114,
111 EXTRACTOR_METATYPE_ALBUM = 129,
112 EXTRACTOR_METATYPE_ARTIST = 130,
113 EXTRACTOR_METATYPE_ORIGINAL_TITLE = 162,
114 EXTRACTOR_METATYPE_GNUNET_FULL_DATA = 174,
115 EXTRACTOR_METATYPE_GNUNET_ORIGINAL_FILENAME = 180,
120 * Format in which the extracted meta data is presented.
122 enum EXTRACTOR_MetaFormat {
126 EXTRACTOR_METAFORMAT_UNKNOWN = 0,
129 * 0-terminated, UTF-8 encoded string. "data_len"
132 EXTRACTOR_METAFORMAT_UTF8 = 1,
135 * Some kind of binary format, see given Mime type.
137 EXTRACTOR_METAFORMAT_BINARY = 2,
140 * 0-terminated string. The specific encoding is unknown.
141 * "data_len" is strlen (data)+1.
143 EXTRACTOR_METAFORMAT_C_STRING = 3
148 * Type of a function that libextractor calls for each
149 * meta data item found.
151 * @param cls closure (user-defined)
152 * @param plugin_name name of the plugin that produced this value;
153 * special values can be used (i.e. '<zlib>' for zlib being
154 * used in the main libextractor library and yielding
156 * @param type libextractor-type describing the meta data
157 * @param format basic format information about @a data
158 * @param data_mime_type mime-type of @a data (not of the original file);
159 * can be NULL (if mime-type is not known)
160 * @param data actual meta-data found
161 * @param data_len number of bytes in @a data
162 * @return 0 to continue extracting, 1 to abort
165 (*EXTRACTOR_MetaDataProcessor) (void *cls,
166 const char *plugin_name,
167 enum EXTRACTOR_MetaType type,
168 enum EXTRACTOR_MetaFormat format,
169 const char *data_mime_type,
175 #ifndef EXTRACTOR_METATYPE_GNUNET_ORIGINAL_FILENAME
176 /* hack for LE < 0.6.3 */
177 #define EXTRACTOR_METATYPE_GNUNET_ORIGINAL_FILENAME 180
183 #if 0 /* keep Emacsens' auto-indent happy */
189 /* ******************* bloomfilter ***************** */
192 * @brief bloomfilter representation (opaque)
193 * @ingroup bloomfilter
195 struct GNUNET_CONTAINER_BloomFilter;
199 * @ingroup bloomfilter
200 * Iterator over `struct GNUNET_HashCode`.
203 * @param next set to the next hash code
204 * @return #GNUNET_YES if next was updated
205 * #GNUNET_NO if there are no more entries
208 (*GNUNET_CONTAINER_HashCodeIterator) (void *cls,
209 struct GNUNET_HashCode *next);
213 * @ingroup bloomfilter
214 * Load a Bloom filter from a file.
216 * @param filename the name of the file (or the prefix)
217 * @param size the size of the bloom-filter (number of
218 * bytes of storage space to use); will be rounded up
220 * @param k the number of #GNUNET_CRYPTO_hash-functions to apply per
221 * element (number of bits set per element in the set)
222 * @return the bloomfilter
224 struct GNUNET_CONTAINER_BloomFilter *
225 GNUNET_CONTAINER_bloomfilter_load (const char *filename,
231 * @ingroup bloomfilter
232 * Create a Bloom filter from raw bits.
234 * @param data the raw bits in memory (maybe NULL,
235 * in which case all bits should be considered
237 * @param size the size of the bloom-filter (number of
238 * bytes of storage space to use); also size of @a data
239 * -- unless data is NULL. Must be a power of 2.
240 * @param k the number of #GNUNET_CRYPTO_hash-functions to apply per
241 * element (number of bits set per element in the set)
242 * @return the bloomfilter
244 struct GNUNET_CONTAINER_BloomFilter *
245 GNUNET_CONTAINER_bloomfilter_init (const char *data,
251 * @ingroup bloomfilter
252 * Copy the raw data of this Bloom filter into
253 * the given data array.
255 * @param data where to write the data
256 * @param size the size of the given @a data array
257 * @return #GNUNET_SYSERR if the data array of the wrong size
260 GNUNET_CONTAINER_bloomfilter_get_raw_data (const struct GNUNET_CONTAINER_BloomFilter *bf,
266 * @ingroup bloomfilter
267 * Test if an element is in the filter.
269 * @param e the element
270 * @param bf the filter
271 * @return #GNUNET_YES if the element is in the filter, #GNUNET_NO if not
274 GNUNET_CONTAINER_bloomfilter_test (const struct GNUNET_CONTAINER_BloomFilter *bf,
275 const struct GNUNET_HashCode *e);
279 * @ingroup bloomfilter
280 * Add an element to the filter.
282 * @param bf the filter
283 * @param e the element
286 GNUNET_CONTAINER_bloomfilter_add (struct GNUNET_CONTAINER_BloomFilter *bf,
287 const struct GNUNET_HashCode *e);
291 * @ingroup bloomfilter
292 * Remove an element from the filter.
294 * @param bf the filter
295 * @param e the element to remove
298 GNUNET_CONTAINER_bloomfilter_remove (struct GNUNET_CONTAINER_BloomFilter *bf,
299 const struct GNUNET_HashCode *e);
303 * @ingroup bloomfilter
304 * Create a copy of a bloomfilter.
306 * @param bf the filter
309 struct GNUNET_CONTAINER_BloomFilter *
310 GNUNET_CONTAINER_bloomfilter_copy (const struct GNUNET_CONTAINER_BloomFilter *bf);
315 * @ingroup bloomfilter
316 * Free the space associcated with a filter
317 * in memory, flush to drive if needed (do not
318 * free the space on the drive).
320 * @param bf the filter
323 GNUNET_CONTAINER_bloomfilter_free (struct GNUNET_CONTAINER_BloomFilter *bf);
327 * Get the number of the addresses set per element in the bloom filter.
329 * @param bf the filter
330 * @return addresses set per element in the bf
333 GNUNET_CONTAINER_bloomfilter_get_element_addresses (const struct GNUNET_CONTAINER_BloomFilter *bf);
337 * @ingroup bloomfilter
338 * Get size of the bloom filter.
340 * @param bf the filter
341 * @return number of bytes used for the data of the bloom filter
344 GNUNET_CONTAINER_bloomfilter_get_size (const struct GNUNET_CONTAINER_BloomFilter *bf);
348 * @ingroup bloomfilter
349 * Reset a Bloom filter to empty.
351 * @param bf the filter
354 GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter *bf);
358 * @ingroup bloomfilter
359 * "or" the entries of the given raw data array with the
360 * data of the given Bloom filter. Assumes that
361 * the @a size of the @a data array and the current filter
364 * @param bf the filter
365 * @param data data to OR-in
366 * @param size size of @a data
367 * @return #GNUNET_OK on success
370 GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf,
371 const char *data, size_t size);
375 * @ingroup bloomfilter
376 * "or" the entries of the given raw data array with the
377 * data of the given Bloom filter. Assumes that
378 * the size of the two filters matches.
380 * @param bf the filter
381 * @param to_or the bloomfilter to or-in
382 * @return #GNUNET_OK on success
385 GNUNET_CONTAINER_bloomfilter_or2 (struct GNUNET_CONTAINER_BloomFilter *bf,
386 const struct GNUNET_CONTAINER_BloomFilter *to_or);
390 * @ingroup bloomfilter
391 * Resize a bloom filter. Note that this operation
392 * is pretty costly. Essentially, the Bloom filter
393 * needs to be completely re-build.
395 * @param bf the filter
396 * @param iterator an iterator over all elements stored in the BF
397 * @param iterator_cls closure for @a iterator
398 * @param size the new size for the filter
399 * @param k the new number of #GNUNET_CRYPTO_hash-function to apply per element
402 GNUNET_CONTAINER_bloomfilter_resize (struct GNUNET_CONTAINER_BloomFilter *bf,
403 GNUNET_CONTAINER_HashCodeIterator iterator,
409 /* ****************** metadata ******************* */
413 * Meta data to associate with a file, directory or namespace.
415 struct GNUNET_CONTAINER_MetaData;
420 * Create a fresh meta data container.
422 * @return empty meta-data container
424 struct GNUNET_CONTAINER_MetaData *
425 GNUNET_CONTAINER_meta_data_create (void);
430 * Duplicate a MetaData token.
432 * @param md what to duplicate
433 * @return duplicate meta-data container
435 struct GNUNET_CONTAINER_MetaData *
436 GNUNET_CONTAINER_meta_data_duplicate (const struct GNUNET_CONTAINER_MetaData *md);
443 * @param md what to free
446 GNUNET_CONTAINER_meta_data_destroy (struct GNUNET_CONTAINER_MetaData *md);
451 * Test if two MDs are equal. We consider them equal if
452 * the meta types, formats and content match (we do not
453 * include the mime types and plugins names in this
456 * @param md1 first value to check
457 * @param md2 other value to check
458 * @return #GNUNET_YES if they are equal
461 GNUNET_CONTAINER_meta_data_test_equal (const struct GNUNET_CONTAINER_MetaData *md1,
462 const struct GNUNET_CONTAINER_MetaData *md2);
469 * @param md metadata to extend
470 * @param plugin_name name of the plugin that produced this value;
471 * special values can be used (i.e. '<zlib>' for zlib being
472 * used in the main libextractor library and yielding
474 * @param type libextractor-type describing the meta data
475 * @param format basic format information about data
476 * @param data_mime_type mime-type of data (not of the original file);
477 * can be NULL (if mime-type is not known)
478 * @param data actual meta-data found
479 * @param data_size number of bytes in data
480 * @return #GNUNET_OK on success, #GNUNET_SYSERR if this entry already exists
481 * data_mime_type and plugin_name are not considered for "exists" checks
484 GNUNET_CONTAINER_meta_data_insert (struct GNUNET_CONTAINER_MetaData *md,
485 const char *plugin_name,
486 enum EXTRACTOR_MetaType type,
487 enum EXTRACTOR_MetaFormat format,
488 const char *data_mime_type,
495 * Extend metadata. Merges the meta data from the second argument
496 * into the first, discarding duplicate key-value pairs.
498 * @param md metadata to extend
499 * @param in metadata to merge
502 GNUNET_CONTAINER_meta_data_merge (struct GNUNET_CONTAINER_MetaData *md,
503 const struct GNUNET_CONTAINER_MetaData *in);
510 * @param md metadata to manipulate
511 * @param type type of the item to remove
512 * @param data specific value to remove, NULL to remove all
513 * entries of the given type
514 * @param data_size number of bytes in data
515 * @return #GNUNET_OK on success, #GNUNET_SYSERR if the item does not exist in md
518 GNUNET_CONTAINER_meta_data_delete (struct GNUNET_CONTAINER_MetaData *md,
519 enum EXTRACTOR_MetaType type,
526 * Remove all items in the container.
528 * @param md metadata to manipulate
531 GNUNET_CONTAINER_meta_data_clear (struct GNUNET_CONTAINER_MetaData *md);
536 * Add the current time as the publication date
539 * @param md metadata to modify
542 GNUNET_CONTAINER_meta_data_add_publication_date (struct GNUNET_CONTAINER_MetaData *md);
547 * Iterate over MD entries.
549 * @param md metadata to inspect
550 * @param iter function to call on each entry, return 0 to continue to iterate
551 * and 1 to abort iteration in this function (GNU libextractor API!)
552 * @param iter_cls closure for @a iter
553 * @return number of entries
556 GNUNET_CONTAINER_meta_data_iterate (const struct GNUNET_CONTAINER_MetaData *md,
557 EXTRACTOR_MetaDataProcessor iter,
563 * Get the first MD entry of the given type. Caller
564 * is responsible for freeing the return value.
565 * Also, only meta data items that are strings (0-terminated)
566 * are returned by this function.
568 * @param md metadata to inspect
569 * @param type type to look for
570 * @return NULL if no entry was found
573 GNUNET_CONTAINER_meta_data_get_by_type (const struct GNUNET_CONTAINER_MetaData *md,
574 enum EXTRACTOR_MetaType type);
579 * Get the first matching MD entry of the given types. Caller is
580 * responsible for freeing the return value. Also, only meta data
581 * items that are strings (0-terminated) are returned by this
584 * @param md metadata to inspect
585 * @param ... -1-terminated list of types
586 * @return NULL if we do not have any such entry,
587 * otherwise client is responsible for freeing the value!
590 GNUNET_CONTAINER_meta_data_get_first_by_types (const struct GNUNET_CONTAINER_MetaData *md,
595 * Get a thumbnail from the meta-data (if present). Only matches meta
596 * data with mime type "image" and binary format.
598 * @param md metadata to inspect
599 * @param thumb will be set to the thumbnail data. Must be
600 * freed by the caller!
601 * @return number of bytes in thumbnail, 0 if not available
604 GNUNET_CONTAINER_meta_data_get_thumbnail (const struct GNUNET_CONTAINER_MetaData *md,
605 unsigned char **thumb);
611 * Options for metadata serialization.
613 enum GNUNET_CONTAINER_MetaDataSerializationOptions
617 * Serialize all of the data.
619 GNUNET_CONTAINER_META_DATA_SERIALIZE_FULL = 0,
623 * If not enough space is available, it is acceptable
624 * to only serialize some of the metadata.
626 GNUNET_CONTAINER_META_DATA_SERIALIZE_PART = 1,
630 * Speed is of the essence, do not allow compression.
632 GNUNET_CONTAINER_META_DATA_SERIALIZE_NO_COMPRESS = 2
638 * Serialize meta-data to target.
640 * @param md metadata to serialize
641 * @param target where to write the serialized metadata;
642 * *target can be NULL, in which case memory is allocated
643 * @param max maximum number of bytes available
644 * @param opt is it ok to just write SOME of the
645 * meta-data to match the size constraint,
646 * possibly discarding some data?
647 * @return number of bytes written on success,
648 * -1 on error (typically: not enough
652 GNUNET_CONTAINER_meta_data_serialize (const struct GNUNET_CONTAINER_MetaData *md,
655 enum GNUNET_CONTAINER_MetaDataSerializationOptions opt);
660 * Get the size of the full meta-data in serialized form.
662 * @param md metadata to inspect
663 * @return number of bytes needed for serialization, -1 on error
666 GNUNET_CONTAINER_meta_data_get_serialized_size (const struct GNUNET_CONTAINER_MetaData *md);
671 * Deserialize meta-data. Initializes md.
673 * @param input serialized meta-data.
674 * @param size number of bytes available
675 * @return MD on success, NULL on error (i.e.
678 struct GNUNET_CONTAINER_MetaData *
679 GNUNET_CONTAINER_meta_data_deserialize (const char *input,
683 /* ******************************* HashMap **************************** */
687 * Opaque handle for a HashMap.
689 struct GNUNET_CONTAINER_MultiHashMap;
693 * Opaque handle to an iterator over
696 struct GNUNET_CONTAINER_MultiHashMapIterator;
700 * Options for storing values in the HashMap.
702 enum GNUNET_CONTAINER_MultiHashMapOption
707 * If a value with the given key exists, replace it. Note that the
708 * old value would NOT be freed by replace (the application has to
709 * make sure that this happens if required).
711 GNUNET_CONTAINER_MULTIHASHMAPOPTION_REPLACE,
715 * Allow multiple values with the same key.
717 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE,
721 * There must only be one value per key; storing a value should fail
722 * if a value under the same key already exists.
724 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY,
727 * @ingroup hashmap There must only be one value per key, but don't
728 * bother checking if a value already exists (faster than
729 * #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY; implemented
730 * just like #GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE but this
731 * option documents better what is intended if
732 * #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY is what is
735 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST
741 * Iterator over hash map entries.
744 * @param key current key code
745 * @param value value in the hash map
746 * @return #GNUNET_YES if we should continue to
751 (*GNUNET_CONTAINER_HashMapIterator) (void *cls,
752 const struct GNUNET_HashCode *key,
758 * Create a multi hash map.
760 * @param len initial size (map will grow as needed)
761 * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default;
762 * #GNUNET_YES means that on 'put', the 'key' does not have
763 * to be copied as the destination of the pointer is
764 * guaranteed to be life as long as the value is stored in
765 * the hashmap. This can significantly reduce memory
766 * consumption, but of course is also a recipie for
767 * heap corruption if the assumption is not true. Only
768 * use this if (1) memory use is important in this case and
769 * (2) you have triple-checked that the invariant holds
770 * @return NULL on error
772 struct GNUNET_CONTAINER_MultiHashMap *
773 GNUNET_CONTAINER_multihashmap_create (unsigned int len,
774 int do_not_copy_keys);
779 * Destroy a hash map. Will not free any values
780 * stored in the hash map!
785 GNUNET_CONTAINER_multihashmap_destroy (struct GNUNET_CONTAINER_MultiHashMap *map);
790 * Given a key find a value in the map matching the key.
793 * @param key what to look for
794 * @return NULL if no value was found; note that
795 * this is indistinguishable from values that just
796 * happen to be NULL; use "contains" to test for
797 * key-value pairs with value NULL
800 GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap *map,
801 const struct GNUNET_HashCode *key);
806 * Remove the given key-value pair from the map. Note that if the
807 * key-value pair is in the map multiple times, only one of the pairs
811 * @param key key of the key-value pair
812 * @param value value of the key-value pair
813 * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
817 GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map,
818 const struct GNUNET_HashCode *key,
823 * Remove all entries for the given key from the map.
824 * Note that the values would not be "freed".
827 * @param key identifies values to be removed
828 * @return number of values removed
831 GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap *map,
832 const struct GNUNET_HashCode *key);
837 * Remove all entries from the map.
838 * Note that the values would not be "freed".
841 * @return number of values removed
844 GNUNET_CONTAINER_multihashmap_clear (struct GNUNET_CONTAINER_MultiHashMap *map);
849 * Check if the map contains any value under the given
850 * key (including values that are NULL).
853 * @param key the key to test if a value exists for it
854 * @return #GNUNET_YES if such a value exists,
858 GNUNET_CONTAINER_multihashmap_contains (const struct GNUNET_CONTAINER_MultiHashMap *map,
859 const struct GNUNET_HashCode * key);
864 * Check if the map contains the given value under the given
868 * @param key the key to test if a value exists for it
869 * @param value value to test for
870 * @return #GNUNET_YES if such a value exists,
874 GNUNET_CONTAINER_multihashmap_contains_value (const struct GNUNET_CONTAINER_MultiHashMap *map,
875 const struct GNUNET_HashCode *key,
881 * Store a key-value pair in the map.
884 * @param key key to use
885 * @param value value to use
886 * @param opt options for put
887 * @return #GNUNET_OK on success,
888 * #GNUNET_NO if a value was replaced (with REPLACE)
889 * #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
890 * value already exists
893 GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map,
894 const struct GNUNET_HashCode *key,
896 enum GNUNET_CONTAINER_MultiHashMapOption
901 * Get the number of key-value pairs in the map.
904 * @return the number of key value pairs
907 GNUNET_CONTAINER_multihashmap_size (const struct GNUNET_CONTAINER_MultiHashMap *map);
912 * Iterate over all entries in the map.
915 * @param it function to call on each entry
916 * @param it_cls extra argument to @a it
917 * @return the number of key value pairs processed,
918 * #GNUNET_SYSERR if it aborted iteration
921 GNUNET_CONTAINER_multihashmap_iterate (const struct GNUNET_CONTAINER_MultiHashMap *map,
922 GNUNET_CONTAINER_HashMapIterator it,
928 * Create an iterator for a multihashmap.
929 * The iterator can be used to retrieve all the elements in the multihashmap
930 * one by one, without having to handle all elements at once (in contrast to
931 * #GNUNET_CONTAINER_multihashmap_iterate). Note that the iterator can not be
932 * used anymore if elements have been removed from 'map' after the creation of
933 * the iterator, or 'map' has been destroyed. Adding elements to 'map' may
934 * result in skipped or repeated elements.
936 * @param map the map to create an iterator for
937 * @return an iterator over the given multihashmap @a map
939 struct GNUNET_CONTAINER_MultiHashMapIterator *
940 GNUNET_CONTAINER_multihashmap_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap *map);
945 * Retrieve the next element from the hash map at the iterator's
946 * position. If there are no elements left, #GNUNET_NO is returned,
947 * and @a key and @a value are not modified. This operation is only
948 * allowed if no elements have been removed from the multihashmap
949 * since the creation of @a iter, and the map has not been destroyed.
950 * Adding elements may result in repeating or skipping elements.
952 * @param iter the iterator to get the next element from
953 * @param key pointer to store the key in, can be NULL
954 * @param value pointer to store the value in, can be NULL
955 * @return #GNUNET_YES we returned an element,
956 * #GNUNET_NO if we are out of elements
959 GNUNET_CONTAINER_multihashmap_iterator_next (struct GNUNET_CONTAINER_MultiHashMapIterator *iter,
960 struct GNUNET_HashCode *key,
966 * Destroy a multihashmap iterator.
968 * @param iter the iterator to destroy
971 GNUNET_CONTAINER_multihashmap_iterator_destroy (struct GNUNET_CONTAINER_MultiHashMapIterator *iter);
976 * Iterate over all entries in the map that match a particular key.
979 * @param key key that the entries must correspond to
980 * @param it function to call on each entry
981 * @param it_cls extra argument to @a it
982 * @return the number of key value pairs processed,
983 * #GNUNET_SYSERR if it aborted iteration
986 GNUNET_CONTAINER_multihashmap_get_multiple (const struct GNUNET_CONTAINER_MultiHashMap *map,
987 const struct GNUNET_HashCode *key,
988 GNUNET_CONTAINER_HashMapIterator it,
994 * Call @a it on a random value from the map, or not at all
995 * if the map is empty. Note that this function has linear
996 * complexity (in the size of the map).
999 * @param it function to call on a random entry
1000 * @param it_cls extra argument to @a it
1001 * @return the number of key value pairs processed, zero or one.
1004 GNUNET_CONTAINER_multihashmap_get_random (const struct GNUNET_CONTAINER_MultiHashMap *map,
1005 GNUNET_CONTAINER_HashMapIterator it,
1009 /* ***************** Version of Multihashmap for peer identities ****************** */
1013 * Iterator over hash map entries.
1015 * @param cls closure
1016 * @param key current public key
1017 * @param value value in the hash map
1018 * @return #GNUNET_YES if we should continue to
1020 * #GNUNET_NO if not.
1023 (*GNUNET_CONTAINER_PeerMapIterator) (void *cls,
1024 const struct GNUNET_PeerIdentity *key,
1029 * Hash map from peer identities to values.
1031 struct GNUNET_CONTAINER_MultiPeerMap;
1036 * Create a multi peer map (hash map for public keys of peers).
1038 * @param len initial size (map will grow as needed)
1039 * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default;
1040 * #GNUNET_YES means that on 'put', the 'key' does not have
1041 * to be copied as the destination of the pointer is
1042 * guaranteed to be life as long as the value is stored in
1043 * the hashmap. This can significantly reduce memory
1044 * consumption, but of course is also a recipie for
1045 * heap corruption if the assumption is not true. Only
1046 * use this if (1) memory use is important in this case and
1047 * (2) you have triple-checked that the invariant holds
1048 * @return NULL on error
1050 struct GNUNET_CONTAINER_MultiPeerMap *
1051 GNUNET_CONTAINER_multipeermap_create (unsigned int len,
1052 int do_not_copy_keys);
1057 * Destroy a hash map. Will not free any values
1058 * stored in the hash map!
1060 * @param map the map
1063 GNUNET_CONTAINER_multipeermap_destroy (struct GNUNET_CONTAINER_MultiPeerMap *map);
1068 * Given a key find a value in the map matching the key.
1070 * @param map the map
1071 * @param key what to look for
1072 * @return NULL if no value was found; note that
1073 * this is indistinguishable from values that just
1074 * happen to be NULL; use "contains" to test for
1075 * key-value pairs with value NULL
1078 GNUNET_CONTAINER_multipeermap_get (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1079 const struct GNUNET_PeerIdentity *key);
1084 * Remove the given key-value pair from the map. Note that if the
1085 * key-value pair is in the map multiple times, only one of the pairs
1088 * @param map the map
1089 * @param key key of the key-value pair
1090 * @param value value of the key-value pair
1091 * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
1095 GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map,
1096 const struct GNUNET_PeerIdentity * key,
1101 * Remove all entries for the given key from the map.
1102 * Note that the values would not be "freed".
1104 * @param map the map
1105 * @param key identifies values to be removed
1106 * @return number of values removed
1109 GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap *map,
1110 const struct GNUNET_PeerIdentity *key);
1115 * Check if the map contains any value under the given
1116 * key (including values that are NULL).
1118 * @param map the map
1119 * @param key the key to test if a value exists for it
1120 * @return #GNUNET_YES if such a value exists,
1124 GNUNET_CONTAINER_multipeermap_contains (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1125 const struct GNUNET_PeerIdentity *key);
1130 * Check if the map contains the given value under the given
1133 * @param map the map
1134 * @param key the key to test if a value exists for it
1135 * @param value value to test for
1136 * @return #GNUNET_YES if such a value exists,
1140 GNUNET_CONTAINER_multipeermap_contains_value (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1141 const struct GNUNET_PeerIdentity * key,
1147 * Store a key-value pair in the map.
1149 * @param map the map
1150 * @param key key to use
1151 * @param value value to use
1152 * @param opt options for put
1153 * @return #GNUNET_OK on success,
1154 * #GNUNET_NO if a value was replaced (with REPLACE)
1155 * #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
1156 * value already exists
1159 GNUNET_CONTAINER_multipeermap_put (struct GNUNET_CONTAINER_MultiPeerMap *map,
1160 const struct GNUNET_PeerIdentity *key,
1162 enum GNUNET_CONTAINER_MultiHashMapOption opt);
1167 * Get the number of key-value pairs in the map.
1169 * @param map the map
1170 * @return the number of key value pairs
1173 GNUNET_CONTAINER_multipeermap_size (const struct GNUNET_CONTAINER_MultiPeerMap *map);
1178 * Iterate over all entries in the map.
1180 * @param map the map
1181 * @param it function to call on each entry
1182 * @param it_cls extra argument to @a it
1183 * @return the number of key value pairs processed,
1184 * #GNUNET_SYSERR if it aborted iteration
1187 GNUNET_CONTAINER_multipeermap_iterate (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1188 GNUNET_CONTAINER_PeerMapIterator it,
1192 struct GNUNET_CONTAINER_MultiPeerMapIterator;
1195 * Create an iterator for a multihashmap.
1196 * The iterator can be used to retrieve all the elements in the multihashmap
1197 * one by one, without having to handle all elements at once (in contrast to
1198 * #GNUNET_CONTAINER_multipeermap_iterate). Note that the iterator can not be
1199 * used anymore if elements have been removed from @a map after the creation of
1200 * the iterator, or 'map' has been destroyed. Adding elements to @a map may
1201 * result in skipped or repeated elements.
1203 * @param map the map to create an iterator for
1204 * @return an iterator over the given multihashmap @a map
1206 struct GNUNET_CONTAINER_MultiPeerMapIterator *
1207 GNUNET_CONTAINER_multipeermap_iterator_create (const struct GNUNET_CONTAINER_MultiPeerMap *map);
1212 * Retrieve the next element from the hash map at the iterator's
1213 * position. If there are no elements left, #GNUNET_NO is returned,
1214 * and @a key and @a value are not modified. This operation is only
1215 * allowed if no elements have been removed from the multihashmap
1216 * since the creation of @a iter, and the map has not been destroyed.
1217 * Adding elements may result in repeating or skipping elements.
1219 * @param iter the iterator to get the next element from
1220 * @param key pointer to store the key in, can be NULL
1221 * @param value pointer to store the value in, can be NULL
1222 * @return #GNUNET_YES we returned an element,
1223 * #GNUNET_NO if we are out of elements
1226 GNUNET_CONTAINER_multipeermap_iterator_next (struct GNUNET_CONTAINER_MultiPeerMapIterator *iter,
1227 struct GNUNET_PeerIdentity *key,
1228 const void **value);
1233 * Destroy a multipeermap iterator.
1235 * @param iter the iterator to destroy
1238 GNUNET_CONTAINER_multipeermap_iterator_destroy (struct GNUNET_CONTAINER_MultiPeerMapIterator *iter);
1243 * Iterate over all entries in the map that match a particular key.
1245 * @param map the map
1246 * @param key public key that the entries must correspond to
1247 * @param it function to call on each entry
1248 * @param it_cls extra argument to @a it
1249 * @return the number of key value pairs processed,
1250 * #GNUNET_SYSERR if it aborted iteration
1253 GNUNET_CONTAINER_multipeermap_get_multiple (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1254 const struct GNUNET_PeerIdentity *key,
1255 GNUNET_CONTAINER_PeerMapIterator it,
1261 * Call @a it on a random value from the map, or not at all
1262 * if the map is empty. Note that this function has linear
1263 * complexity (in the size of the map).
1265 * @param map the map
1266 * @param it function to call on a random entry
1267 * @param it_cls extra argument to @a it
1268 * @return the number of key value pairs processed, zero or one.
1271 GNUNET_CONTAINER_multipeermap_get_random (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1272 GNUNET_CONTAINER_PeerMapIterator it,
1276 /* Version of multihashmap with 32 bit keys */
1280 * Opaque handle for the 32-bit key HashMap.
1282 struct GNUNET_CONTAINER_MultiHashMap32;
1287 * Opaque handle to an iterator over
1288 * a 32-bit key multihashmap.
1290 struct GNUNET_CONTAINER_MultiHashMap32Iterator;
1295 * Iterator over hash map entries.
1297 * @param cls closure
1298 * @param key current key code
1299 * @param value value in the hash map
1300 * @return #GNUNET_YES if we should continue to
1302 * #GNUNET_NO if not.
1304 typedef int (*GNUNET_CONTAINER_HashMapIterator32) (void *cls,
1311 * Create a 32-bit key multi hash map.
1313 * @param len initial size (map will grow as needed)
1314 * @return NULL on error
1316 struct GNUNET_CONTAINER_MultiHashMap32 *
1317 GNUNET_CONTAINER_multihashmap32_create (unsigned int len);
1322 * Destroy a 32-bit key hash map. Will not free any values
1323 * stored in the hash map!
1325 * @param map the map
1328 GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32
1334 * Get the number of key-value pairs in the map.
1336 * @param map the map
1337 * @return the number of key value pairs
1340 GNUNET_CONTAINER_multihashmap32_size (const struct
1341 GNUNET_CONTAINER_MultiHashMap32 *map);
1346 * Given a key find a value in the map matching the key.
1348 * @param map the map
1349 * @param key what to look for
1350 * @return NULL if no value was found; note that
1351 * this is indistinguishable from values that just
1352 * happen to be NULL; use "contains" to test for
1353 * key-value pairs with value NULL
1356 GNUNET_CONTAINER_multihashmap32_get (const struct
1357 GNUNET_CONTAINER_MultiHashMap32 *map,
1363 * Iterate over all entries in the map.
1365 * @param map the map
1366 * @param it function to call on each entry
1367 * @param it_cls extra argument to @a it
1368 * @return the number of key value pairs processed,
1369 * #GNUNET_SYSERR if it aborted iteration
1372 GNUNET_CONTAINER_multihashmap32_iterate (const struct
1373 GNUNET_CONTAINER_MultiHashMap32 *map,
1374 GNUNET_CONTAINER_HashMapIterator32 it,
1380 * Remove the given key-value pair from the map. Note that if the
1381 * key-value pair is in the map multiple times, only one of the pairs
1384 * @param map the map
1385 * @param key key of the key-value pair
1386 * @param value value of the key-value pair
1387 * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
1391 GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 *map,
1398 * Remove all entries for the given key from the map.
1399 * Note that the values would not be "freed".
1401 * @param map the map
1402 * @param key identifies values to be removed
1403 * @return number of values removed
1406 GNUNET_CONTAINER_multihashmap32_remove_all (struct GNUNET_CONTAINER_MultiHashMap32 *map,
1412 * Check if the map contains any value under the given
1413 * key (including values that are NULL).
1415 * @param map the map
1416 * @param key the key to test if a value exists for it
1417 * @return #GNUNET_YES if such a value exists,
1421 GNUNET_CONTAINER_multihashmap32_contains (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
1427 * Check if the map contains the given value under the given
1430 * @param map the map
1431 * @param key the key to test if a value exists for it
1432 * @param value value to test for
1433 * @return #GNUNET_YES if such a value exists,
1437 GNUNET_CONTAINER_multihashmap32_contains_value (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
1444 * Store a key-value pair in the map.
1446 * @param map the map
1447 * @param key key to use
1448 * @param value value to use
1449 * @param opt options for put
1450 * @return #GNUNET_OK on success,
1451 * #GNUNET_NO if a value was replaced (with REPLACE)
1452 * #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
1453 * value already exists
1456 GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32 *map,
1459 enum GNUNET_CONTAINER_MultiHashMapOption opt);
1464 * Iterate over all entries in the map that match a particular key.
1466 * @param map the map
1467 * @param key key that the entries must correspond to
1468 * @param it function to call on each entry
1469 * @param it_cls extra argument to @a it
1470 * @return the number of key value pairs processed,
1471 * #GNUNET_SYSERR if it aborted iteration
1474 GNUNET_CONTAINER_multihashmap32_get_multiple (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
1476 GNUNET_CONTAINER_HashMapIterator32 it,
1481 * Create an iterator for a 32-bit multihashmap.
1482 * The iterator can be used to retrieve all the elements in the multihashmap
1483 * one by one, without having to handle all elements at once (in contrast to
1484 * #GNUNET_CONTAINER_multihashmap32_iterate). Note that the iterator can not be
1485 * used anymore if elements have been removed from 'map' after the creation of
1486 * the iterator, or 'map' has been destroyed. Adding elements to 'map' may
1487 * result in skipped or repeated elements.
1489 * @param map the map to create an iterator for
1490 * @return an iterator over the given multihashmap map
1492 struct GNUNET_CONTAINER_MultiHashMap32Iterator *
1493 GNUNET_CONTAINER_multihashmap32_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap32 *map);
1497 * Retrieve the next element from the hash map at the iterator's position.
1498 * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
1500 * This operation is only allowed if no elements have been removed from the
1501 * multihashmap since the creation of 'iter', and the map has not been destroyed.
1502 * Adding elements may result in repeating or skipping elements.
1504 * @param iter the iterator to get the next element from
1505 * @param key pointer to store the key in, can be NULL
1506 * @param value pointer to store the value in, can be NULL
1507 * @return #GNUNET_YES we returned an element,
1508 * #GNUNET_NO if we are out of elements
1511 GNUNET_CONTAINER_multihashmap32_iterator_next (struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter,
1513 const void **value);
1517 * Destroy a 32-bit multihashmap iterator.
1519 * @param iter the iterator to destroy
1522 GNUNET_CONTAINER_multihashmap32_iterator_destroy (struct GNUNET_CONTAINER_MultiHashMapIterator *iter);
1525 /* ******************** doubly-linked list *************** */
1526 /* To avoid mistakes: head->prev == tail->next == NULL */
1530 * Insert an element at the head of a DLL. Assumes that head, tail and
1531 * element are structs with prev and next fields.
1533 * @param head pointer to the head of the DLL
1534 * @param tail pointer to the tail of the DLL
1535 * @param element element to insert
1537 #define GNUNET_CONTAINER_DLL_insert(head,tail,element) do { \
1538 GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1539 GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1540 (element)->next = (head); \
1541 (element)->prev = NULL; \
1542 if ((tail) == NULL) \
1545 (head)->prev = element; \
1546 (head) = (element); } while (0)
1551 * Insert an element at the tail of a DLL. Assumes that head, tail and
1552 * element are structs with prev and next fields.
1554 * @param head pointer to the head of the DLL
1555 * @param tail pointer to the tail of the DLL
1556 * @param element element to insert
1558 #define GNUNET_CONTAINER_DLL_insert_tail(head,tail,element) do { \
1559 GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1560 GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1561 (element)->prev = (tail); \
1562 (element)->next = NULL; \
1563 if ((head) == NULL) \
1566 (tail)->next = element; \
1567 (tail) = (element); } while (0)
1572 * Insert an element into a DLL after the given other element. Insert
1573 * at the head if the other element is NULL.
1575 * @param head pointer to the head of the DLL
1576 * @param tail pointer to the tail of the DLL
1577 * @param other prior element, NULL for insertion at head of DLL
1578 * @param element element to insert
1580 #define GNUNET_CONTAINER_DLL_insert_after(head,tail,other,element) do { \
1581 GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1582 GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1583 (element)->prev = (other); \
1584 if (NULL == other) \
1586 (element)->next = (head); \
1587 (head) = (element); \
1591 (element)->next = (other)->next; \
1592 (other)->next = (element); \
1594 if (NULL == (element)->next) \
1595 (tail) = (element); \
1597 (element)->next->prev = (element); } while (0)
1602 * Insert an element into a DLL before the given other element. Insert
1603 * at the tail if the other element is NULL.
1605 * @param head pointer to the head of the DLL
1606 * @param tail pointer to the tail of the DLL
1607 * @param other prior element, NULL for insertion at head of DLL
1608 * @param element element to insert
1610 #define GNUNET_CONTAINER_DLL_insert_before(head,tail,other,element) do { \
1611 GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1612 GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1613 (element)->next = (other); \
1614 if (NULL == other) \
1616 (element)->prev = (tail); \
1617 (tail) = (element); \
1621 (element)->prev = (other)->prev; \
1622 (other)->prev = (element); \
1624 if (NULL == (element)->prev) \
1625 (head) = (element); \
1627 (element)->prev->next = (element); } while (0)
1632 * Remove an element from a DLL. Assumes that head, tail and
1633 * element point to structs with prev and next fields.
1635 * Using the head or tail pointer as the element
1636 * argument does NOT work with this macro.
1637 * Make sure to store head/tail in another pointer
1638 * and use it to remove the head or tail of the list.
1640 * @param head pointer to the head of the DLL
1641 * @param tail pointer to the tail of the DLL
1642 * @param element element to remove
1644 #define GNUNET_CONTAINER_DLL_remove(head,tail,element) do { \
1645 GNUNET_assert ( ( (element)->prev != NULL) || ((head) == (element))); \
1646 GNUNET_assert ( ( (element)->next != NULL) || ((tail) == (element))); \
1647 if ((element)->prev == NULL) \
1648 (head) = (element)->next; \
1650 (element)->prev->next = (element)->next; \
1651 if ((element)->next == NULL) \
1652 (tail) = (element)->prev; \
1654 (element)->next->prev = (element)->prev; \
1655 (element)->next = NULL; \
1656 (element)->prev = NULL; } while (0)
1659 /* ************ Multi-DLL interface, allows DLL elements to be
1660 in multiple lists at the same time *********************** */
1664 * Insert an element at the head of a MDLL. Assumes that head, tail and
1665 * element are structs with prev and next fields.
1667 * @param mdll suffix name for the next and prev pointers in the element
1668 * @param head pointer to the head of the MDLL
1669 * @param tail pointer to the tail of the MDLL
1670 * @param element element to insert
1672 #define GNUNET_CONTAINER_MDLL_insert(mdll,head,tail,element) do { \
1673 GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1674 GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1675 (element)->next_##mdll = (head); \
1676 (element)->prev_##mdll = NULL; \
1677 if ((tail) == NULL) \
1680 (head)->prev_##mdll = element; \
1681 (head) = (element); } while (0)
1686 * Insert an element at the tail of a MDLL. Assumes that head, tail and
1687 * element are structs with prev and next fields.
1689 * @param mdll suffix name for the next and prev pointers in the element
1690 * @param head pointer to the head of the MDLL
1691 * @param tail pointer to the tail of the MDLL
1692 * @param element element to insert
1694 #define GNUNET_CONTAINER_MDLL_insert_tail(mdll,head,tail,element) do { \
1695 GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1696 GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1697 (element)->prev_##mdll = (tail); \
1698 (element)->next_##mdll = NULL; \
1699 if ((head) == NULL) \
1702 (tail)->next_##mdll = element; \
1703 (tail) = (element); } while (0)
1708 * Insert an element into a MDLL after the given other element. Insert
1709 * at the head if the other element is NULL.
1711 * @param mdll suffix name for the next and prev pointers in the element
1712 * @param head pointer to the head of the MDLL
1713 * @param tail pointer to the tail of the MDLL
1714 * @param other prior element, NULL for insertion at head of MDLL
1715 * @param element element to insert
1717 #define GNUNET_CONTAINER_MDLL_insert_after(mdll,head,tail,other,element) do { \
1718 GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1719 GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1720 (element)->prev_##mdll = (other); \
1721 if (NULL == other) \
1723 (element)->next_##mdll = (head); \
1724 (head) = (element); \
1728 (element)->next_##mdll = (other)->next_##mdll; \
1729 (other)->next_##mdll = (element); \
1731 if (NULL == (element)->next_##mdll) \
1732 (tail) = (element); \
1734 (element)->next->prev_##mdll = (element); } while (0)
1739 * Insert an element into a MDLL before the given other element. Insert
1740 * at the tail if the other element is NULL.
1742 * @param mdll suffix name for the next and prev pointers in the element
1743 * @param head pointer to the head of the MDLL
1744 * @param tail pointer to the tail of the MDLL
1745 * @param other prior element, NULL for insertion at head of MDLL
1746 * @param element element to insert
1748 #define GNUNET_CONTAINER_MDLL_insert_before(mdll,head,tail,other,element) do { \
1749 GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1750 GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1751 (element)->next_##mdll = (other); \
1752 if (NULL == other) \
1754 (element)->prev = (tail); \
1755 (tail) = (element); \
1759 (element)->prev_##mdll = (other)->prev_##mdll; \
1760 (other)->prev_##mdll = (element); \
1762 if (NULL == (element)->prev_##mdll) \
1763 (head) = (element); \
1765 (element)->prev_##mdll->next_##mdll = (element); } while (0)
1770 * Remove an element from a MDLL. Assumes
1771 * that head, tail and element are structs
1772 * with prev and next fields.
1774 * @param mdll suffix name for the next and prev pointers in the element
1775 * @param head pointer to the head of the MDLL
1776 * @param tail pointer to the tail of the MDLL
1777 * @param element element to remove
1779 #define GNUNET_CONTAINER_MDLL_remove(mdll,head,tail,element) do { \
1780 GNUNET_assert ( ( (element)->prev_##mdll != NULL) || ((head) == (element))); \
1781 GNUNET_assert ( ( (element)->next_##mdll != NULL) || ((tail) == (element))); \
1782 if ((element)->prev_##mdll == NULL) \
1783 (head) = (element)->next_##mdll; \
1785 (element)->prev_##mdll->next_##mdll = (element)->next_##mdll; \
1786 if ((element)->next_##mdll == NULL) \
1787 (tail) = (element)->prev_##mdll; \
1789 (element)->next_##mdll->prev_##mdll = (element)->prev_##mdll; \
1790 (element)->next_##mdll = NULL; \
1791 (element)->prev_##mdll = NULL; } while (0)
1795 /* ******************** Heap *************** */
1800 * Cost by which elements in a heap can be ordered.
1802 typedef uint64_t GNUNET_CONTAINER_HeapCostType;
1807 * Heap type, either max or min.
1809 enum GNUNET_CONTAINER_HeapOrder
1813 * Heap with the maximum cost at the root.
1815 GNUNET_CONTAINER_HEAP_ORDER_MAX,
1819 * Heap with the minimum cost at the root.
1821 GNUNET_CONTAINER_HEAP_ORDER_MIN
1829 struct GNUNET_CONTAINER_Heap;
1834 * Handle to a node in a heap.
1836 struct GNUNET_CONTAINER_HeapNode;
1841 * Create a new heap.
1843 * @param order how should the heap be sorted?
1844 * @return handle to the heap
1846 struct GNUNET_CONTAINER_Heap *
1847 GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order);
1852 * Destroys the heap. Only call on a heap that
1855 * @param heap heap to destroy
1858 GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap);
1863 * Get element stored at the root of @a heap.
1865 * @param heap Heap to inspect.
1866 * @return Element at the root, or NULL if heap is empty.
1869 GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap);
1873 * Get @a element and @a cost stored at the root of @a heap.
1875 * @param[in] heap Heap to inspect.
1876 * @param[out] element Root element is returned here.
1877 * @param[out] cost Cost of @a element is returned here.
1878 * @return #GNUNET_YES if an element is returned,
1879 * #GNUNET_NO if the heap is empty.
1882 GNUNET_CONTAINER_heap_peek2 (const struct GNUNET_CONTAINER_Heap *heap,
1884 GNUNET_CONTAINER_HeapCostType *cost);
1889 * Get the current size of the heap
1891 * @param heap the heap to get the size of
1892 * @return number of elements stored
1895 GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap);
1900 * Get the current cost of the node
1902 * @param node the node to get the cost of
1903 * @return cost of the node
1905 GNUNET_CONTAINER_HeapCostType
1906 GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode
1913 * @param cls closure
1914 * @param node internal node of the heap
1915 * @param element value stored at the node
1916 * @param cost cost associated with the node
1917 * @return #GNUNET_YES if we should continue to iterate,
1918 * #GNUNET_NO if not.
1921 (*GNUNET_CONTAINER_HeapIterator) (void *cls,
1922 struct GNUNET_CONTAINER_HeapNode *node,
1924 GNUNET_CONTAINER_HeapCostType cost);
1929 * Iterate over all entries in the heap.
1931 * @param heap the heap
1932 * @param iterator function to call on each entry
1933 * @param iterator_cls closure for @a iterator
1936 GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
1937 GNUNET_CONTAINER_HeapIterator iterator,
1938 void *iterator_cls);
1942 * Perform a random walk of the tree. The walk is biased
1943 * towards elements closer to the root of the tree (since
1944 * each walk starts at the root and ends at a random leaf).
1945 * The heap internally tracks the current position of the
1948 * @param heap heap to walk
1949 * @return data stored at the next random node in the walk;
1950 * NULL if the tree is empty.
1953 GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap);
1958 * Inserts a new element into the heap.
1960 * @param heap heap to modify
1961 * @param element element to insert
1962 * @param cost cost for the element
1963 * @return node for the new element
1965 struct GNUNET_CONTAINER_HeapNode *
1966 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap,
1968 GNUNET_CONTAINER_HeapCostType cost);
1973 * Remove root of the heap.
1975 * @param heap heap to modify
1976 * @return element data stored at the root node
1979 GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap);
1984 * Removes a node from the heap.
1986 * @param node node to remove
1987 * @return element data stored at the node, NULL if heap is empty
1990 GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node);
1995 * Updates the cost of any node in the tree
1997 * @param heap heap to modify
1998 * @param node node for which the cost is to be changed
1999 * @param new_cost new cost for the node
2002 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
2003 struct GNUNET_CONTAINER_HeapNode *node,
2004 GNUNET_CONTAINER_HeapCostType new_cost);
2007 #if 0 /* keep Emacsens' auto-indent happy */
2015 /* ifndef GNUNET_CONTAINER_LIB_H */
2017 /* end of gnunet_container_lib.h */