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 #include <extractor.h>
45 /* definitions from extractor.h we need for the build */
48 * Enumeration defining various sources of keywords. See also
49 * http://dublincore.org/documents/1998/09/dces/
51 enum EXTRACTOR_MetaType {
52 EXTRACTOR_METATYPE_RESERVED = 0,
53 EXTRACTOR_METATYPE_MIMETYPE = 1,
54 EXTRACTOR_METATYPE_FILENAME = 2,
55 EXTRACTOR_METATYPE_COMMENT = 3,
56 EXTRACTOR_METATYPE_TITLE = 4,
57 EXTRACTOR_METATYPE_BOOK_TITLE = 5,
58 EXTRACTOR_METATYPE_JOURNAL_NAME = 8,
59 EXTRACTOR_METATYPE_AUTHOR_NAME = 13,
60 EXTRACTOR_METATYPE_PUBLICATION_DATE = 24,
61 EXTRACTOR_METATYPE_URL = 29,
62 EXTRACTOR_METATYPE_URI = 30,
63 EXTRACTOR_METATYPE_ISRC = 31,
64 EXTRACTOR_METATYPE_UNKNOWN = 45,
65 EXTRACTOR_METATYPE_DESCRIPTION = 46,
66 EXTRACTOR_METATYPE_KEYWORDS = 49,
67 EXTRACTOR_METATYPE_SUBJECT = 52,
68 EXTRACTOR_METATYPE_PACKAGE_NAME = 69,
69 EXTRACTOR_METATYPE_THUMBNAIL = 114,
70 EXTRACTOR_METATYPE_ALBUM = 129,
71 EXTRACTOR_METATYPE_ARTIST = 130,
72 EXTRACTOR_METATYPE_ORIGINAL_TITLE = 162,
73 EXTRACTOR_METATYPE_GNUNET_FULL_DATA = 174,
74 EXTRACTOR_METATYPE_GNUNET_ORIGINAL_FILENAME = 180,
79 * Format in which the extracted meta data is presented.
81 enum EXTRACTOR_MetaFormat {
85 EXTRACTOR_METAFORMAT_UNKNOWN = 0,
88 * 0-terminated, UTF-8 encoded string. "data_len"
91 EXTRACTOR_METAFORMAT_UTF8 = 1,
94 * Some kind of binary format, see given Mime type.
96 EXTRACTOR_METAFORMAT_BINARY = 2,
99 * 0-terminated string. The specific encoding is unknown.
100 * "data_len" is strlen (data)+1.
102 EXTRACTOR_METAFORMAT_C_STRING = 3
107 * Type of a function that libextractor calls for each
108 * meta data item found.
110 * @param cls closure (user-defined)
111 * @param plugin_name name of the plugin that produced this value;
112 * special values can be used (i.e. '<zlib>' for zlib being
113 * used in the main libextractor library and yielding
115 * @param type libextractor-type describing the meta data
116 * @param format basic format information about @a data
117 * @param data_mime_type mime-type of @a data (not of the original file);
118 * can be NULL (if mime-type is not known)
119 * @param data actual meta-data found
120 * @param data_len number of bytes in @a data
121 * @return 0 to continue extracting, 1 to abort
124 (*EXTRACTOR_MetaDataProcessor) (void *cls,
125 const char *plugin_name,
126 enum EXTRACTOR_MetaType type,
127 enum EXTRACTOR_MetaFormat format,
128 const char *data_mime_type,
134 #ifndef EXTRACTOR_METATYPE_GNUNET_ORIGINAL_FILENAME
135 /* hack for LE < 0.6.3 */
136 #define EXTRACTOR_METATYPE_GNUNET_ORIGINAL_FILENAME 180
142 #if 0 /* keep Emacsens' auto-indent happy */
148 /* ******************* bloomfilter ***************** */
151 * @brief bloomfilter representation (opaque)
152 * @ingroup bloomfilter
154 struct GNUNET_CONTAINER_BloomFilter;
158 * @ingroup bloomfilter
159 * Iterator over `struct GNUNET_HashCode`.
162 * @param next set to the next hash code
163 * @return #GNUNET_YES if next was updated
164 * #GNUNET_NO if there are no more entries
167 (*GNUNET_CONTAINER_HashCodeIterator) (void *cls,
168 struct GNUNET_HashCode *next);
172 * @ingroup bloomfilter
173 * Load a Bloom filter from a file.
175 * @param filename the name of the file (or the prefix)
176 * @param size the size of the bloom-filter (number of
177 * bytes of storage space to use); will be rounded up
179 * @param k the number of #GNUNET_CRYPTO_hash-functions to apply per
180 * element (number of bits set per element in the set)
181 * @return the bloomfilter
183 struct GNUNET_CONTAINER_BloomFilter *
184 GNUNET_CONTAINER_bloomfilter_load (const char *filename,
190 * @ingroup bloomfilter
191 * Create a Bloom filter from raw bits.
193 * @param data the raw bits in memory (maybe NULL,
194 * in which case all bits should be considered
196 * @param size the size of the bloom-filter (number of
197 * bytes of storage space to use); also size of @a data
198 * -- unless data is NULL. Must be a power of 2.
199 * @param k the number of #GNUNET_CRYPTO_hash-functions to apply per
200 * element (number of bits set per element in the set)
201 * @return the bloomfilter
203 struct GNUNET_CONTAINER_BloomFilter *
204 GNUNET_CONTAINER_bloomfilter_init (const char *data,
210 * @ingroup bloomfilter
211 * Copy the raw data of this Bloom filter into
212 * the given data array.
214 * @param data where to write the data
215 * @param size the size of the given @a data array
216 * @return #GNUNET_SYSERR if the data array of the wrong size
219 GNUNET_CONTAINER_bloomfilter_get_raw_data (const struct GNUNET_CONTAINER_BloomFilter *bf,
225 * @ingroup bloomfilter
226 * Test if an element is in the filter.
228 * @param e the element
229 * @param bf the filter
230 * @return #GNUNET_YES if the element is in the filter, #GNUNET_NO if not
233 GNUNET_CONTAINER_bloomfilter_test (const struct GNUNET_CONTAINER_BloomFilter *bf,
234 const struct GNUNET_HashCode *e);
238 * @ingroup bloomfilter
239 * Add an element to the filter.
241 * @param bf the filter
242 * @param e the element
245 GNUNET_CONTAINER_bloomfilter_add (struct GNUNET_CONTAINER_BloomFilter *bf,
246 const struct GNUNET_HashCode *e);
250 * @ingroup bloomfilter
251 * Remove an element from the filter.
253 * @param bf the filter
254 * @param e the element to remove
257 GNUNET_CONTAINER_bloomfilter_remove (struct GNUNET_CONTAINER_BloomFilter *bf,
258 const struct GNUNET_HashCode *e);
262 * @ingroup bloomfilter
263 * Create a copy of a bloomfilter.
265 * @param bf the filter
268 struct GNUNET_CONTAINER_BloomFilter *
269 GNUNET_CONTAINER_bloomfilter_copy (const struct GNUNET_CONTAINER_BloomFilter *bf);
274 * @ingroup bloomfilter
275 * Free the space associcated with a filter
276 * in memory, flush to drive if needed (do not
277 * free the space on the drive).
279 * @param bf the filter
282 GNUNET_CONTAINER_bloomfilter_free (struct GNUNET_CONTAINER_BloomFilter *bf);
286 * Get the number of the addresses set per element in the bloom filter.
288 * @param bf the filter
289 * @return addresses set per element in the bf
292 GNUNET_CONTAINER_bloomfilter_get_element_addresses (const struct GNUNET_CONTAINER_BloomFilter *bf);
296 * @ingroup bloomfilter
297 * Get size of the bloom filter.
299 * @param bf the filter
300 * @return number of bytes used for the data of the bloom filter
303 GNUNET_CONTAINER_bloomfilter_get_size (const struct GNUNET_CONTAINER_BloomFilter *bf);
307 * @ingroup bloomfilter
308 * Reset a Bloom filter to empty.
310 * @param bf the filter
313 GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter *bf);
317 * @ingroup bloomfilter
318 * "or" the entries of the given raw data array with the
319 * data of the given Bloom filter. Assumes that
320 * the @a size of the @a data array and the current filter
323 * @param bf the filter
324 * @param data data to OR-in
325 * @param size size of @a data
326 * @return #GNUNET_OK on success
329 GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf,
330 const char *data, size_t size);
334 * @ingroup bloomfilter
335 * "or" the entries of the given raw data array with the
336 * data of the given Bloom filter. Assumes that
337 * the size of the two filters matches.
339 * @param bf the filter
340 * @param to_or the bloomfilter to or-in
341 * @return #GNUNET_OK on success
344 GNUNET_CONTAINER_bloomfilter_or2 (struct GNUNET_CONTAINER_BloomFilter *bf,
345 const struct GNUNET_CONTAINER_BloomFilter *to_or);
349 * @ingroup bloomfilter
350 * Resize a bloom filter. Note that this operation
351 * is pretty costly. Essentially, the Bloom filter
352 * needs to be completely re-build.
354 * @param bf the filter
355 * @param iterator an iterator over all elements stored in the BF
356 * @param iterator_cls closure for @a iterator
357 * @param size the new size for the filter
358 * @param k the new number of #GNUNET_CRYPTO_hash-function to apply per element
361 GNUNET_CONTAINER_bloomfilter_resize (struct GNUNET_CONTAINER_BloomFilter *bf,
362 GNUNET_CONTAINER_HashCodeIterator iterator,
368 /* ****************** metadata ******************* */
372 * Meta data to associate with a file, directory or namespace.
374 struct GNUNET_CONTAINER_MetaData;
379 * Create a fresh meta data container.
381 * @return empty meta-data container
383 struct GNUNET_CONTAINER_MetaData *
384 GNUNET_CONTAINER_meta_data_create (void);
389 * Duplicate a MetaData token.
391 * @param md what to duplicate
392 * @return duplicate meta-data container
394 struct GNUNET_CONTAINER_MetaData *
395 GNUNET_CONTAINER_meta_data_duplicate (const struct GNUNET_CONTAINER_MetaData *md);
402 * @param md what to free
405 GNUNET_CONTAINER_meta_data_destroy (struct GNUNET_CONTAINER_MetaData *md);
410 * Test if two MDs are equal. We consider them equal if
411 * the meta types, formats and content match (we do not
412 * include the mime types and plugins names in this
415 * @param md1 first value to check
416 * @param md2 other value to check
417 * @return #GNUNET_YES if they are equal
420 GNUNET_CONTAINER_meta_data_test_equal (const struct GNUNET_CONTAINER_MetaData *md1,
421 const struct GNUNET_CONTAINER_MetaData *md2);
428 * @param md metadata to extend
429 * @param plugin_name name of the plugin that produced this value;
430 * special values can be used (i.e. '<zlib>' for zlib being
431 * used in the main libextractor library and yielding
433 * @param type libextractor-type describing the meta data
434 * @param format basic format information about data
435 * @param data_mime_type mime-type of data (not of the original file);
436 * can be NULL (if mime-type is not known)
437 * @param data actual meta-data found
438 * @param data_size number of bytes in data
439 * @return #GNUNET_OK on success, #GNUNET_SYSERR if this entry already exists
440 * data_mime_type and plugin_name are not considered for "exists" checks
443 GNUNET_CONTAINER_meta_data_insert (struct GNUNET_CONTAINER_MetaData *md,
444 const char *plugin_name,
445 enum EXTRACTOR_MetaType type,
446 enum EXTRACTOR_MetaFormat format,
447 const char *data_mime_type,
454 * Extend metadata. Merges the meta data from the second argument
455 * into the first, discarding duplicate key-value pairs.
457 * @param md metadata to extend
458 * @param in metadata to merge
461 GNUNET_CONTAINER_meta_data_merge (struct GNUNET_CONTAINER_MetaData *md,
462 const struct GNUNET_CONTAINER_MetaData *in);
469 * @param md metadata to manipulate
470 * @param type type of the item to remove
471 * @param data specific value to remove, NULL to remove all
472 * entries of the given type
473 * @param data_size number of bytes in data
474 * @return #GNUNET_OK on success, #GNUNET_SYSERR if the item does not exist in md
477 GNUNET_CONTAINER_meta_data_delete (struct GNUNET_CONTAINER_MetaData *md,
478 enum EXTRACTOR_MetaType type,
485 * Remove all items in the container.
487 * @param md metadata to manipulate
490 GNUNET_CONTAINER_meta_data_clear (struct GNUNET_CONTAINER_MetaData *md);
495 * Add the current time as the publication date
498 * @param md metadata to modify
501 GNUNET_CONTAINER_meta_data_add_publication_date (struct GNUNET_CONTAINER_MetaData *md);
506 * Iterate over MD entries.
508 * @param md metadata to inspect
509 * @param iter function to call on each entry, return 0 to continue to iterate
510 * and 1 to abort iteration in this function (GNU libextractor API!)
511 * @param iter_cls closure for @a iter
512 * @return number of entries
515 GNUNET_CONTAINER_meta_data_iterate (const struct GNUNET_CONTAINER_MetaData *md,
516 EXTRACTOR_MetaDataProcessor iter,
522 * Get the first MD entry of the given type. Caller
523 * is responsible for freeing the return value.
524 * Also, only meta data items that are strings (0-terminated)
525 * are returned by this function.
527 * @param md metadata to inspect
528 * @param type type to look for
529 * @return NULL if no entry was found
532 GNUNET_CONTAINER_meta_data_get_by_type (const struct GNUNET_CONTAINER_MetaData *md,
533 enum EXTRACTOR_MetaType type);
538 * Get the first matching MD entry of the given types. Caller is
539 * responsible for freeing the return value. Also, only meta data
540 * items that are strings (0-terminated) are returned by this
543 * @param md metadata to inspect
544 * @param ... -1-terminated list of types
545 * @return NULL if we do not have any such entry,
546 * otherwise client is responsible for freeing the value!
549 GNUNET_CONTAINER_meta_data_get_first_by_types (const struct GNUNET_CONTAINER_MetaData *md,
554 * Get a thumbnail from the meta-data (if present). Only matches meta
555 * data with mime type "image" and binary format.
557 * @param md metadata to inspect
558 * @param thumb will be set to the thumbnail data. Must be
559 * freed by the caller!
560 * @return number of bytes in thumbnail, 0 if not available
563 GNUNET_CONTAINER_meta_data_get_thumbnail (const struct GNUNET_CONTAINER_MetaData *md,
564 unsigned char **thumb);
570 * Options for metadata serialization.
572 enum GNUNET_CONTAINER_MetaDataSerializationOptions
576 * Serialize all of the data.
578 GNUNET_CONTAINER_META_DATA_SERIALIZE_FULL = 0,
582 * If not enough space is available, it is acceptable
583 * to only serialize some of the metadata.
585 GNUNET_CONTAINER_META_DATA_SERIALIZE_PART = 1,
589 * Speed is of the essence, do not allow compression.
591 GNUNET_CONTAINER_META_DATA_SERIALIZE_NO_COMPRESS = 2
597 * Serialize meta-data to target.
599 * @param md metadata to serialize
600 * @param target where to write the serialized metadata;
601 * *target can be NULL, in which case memory is allocated
602 * @param max maximum number of bytes available
603 * @param opt is it ok to just write SOME of the
604 * meta-data to match the size constraint,
605 * possibly discarding some data?
606 * @return number of bytes written on success,
607 * -1 on error (typically: not enough
611 GNUNET_CONTAINER_meta_data_serialize (const struct GNUNET_CONTAINER_MetaData *md,
614 enum GNUNET_CONTAINER_MetaDataSerializationOptions opt);
619 * Get the size of the full meta-data in serialized form.
621 * @param md metadata to inspect
622 * @return number of bytes needed for serialization, -1 on error
625 GNUNET_CONTAINER_meta_data_get_serialized_size (const struct GNUNET_CONTAINER_MetaData *md);
630 * Deserialize meta-data. Initializes md.
632 * @param input serialized meta-data.
633 * @param size number of bytes available
634 * @return MD on success, NULL on error (i.e.
637 struct GNUNET_CONTAINER_MetaData *
638 GNUNET_CONTAINER_meta_data_deserialize (const char *input,
642 /* ******************************* HashMap **************************** */
646 * Opaque handle for a HashMap.
648 struct GNUNET_CONTAINER_MultiHashMap;
652 * Opaque handle to an iterator over
655 struct GNUNET_CONTAINER_MultiHashMapIterator;
659 * Options for storing values in the HashMap.
661 enum GNUNET_CONTAINER_MultiHashMapOption
666 * If a value with the given key exists, replace it. Note that the
667 * old value would NOT be freed by replace (the application has to
668 * make sure that this happens if required).
670 GNUNET_CONTAINER_MULTIHASHMAPOPTION_REPLACE,
674 * Allow multiple values with the same key.
676 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE,
680 * There must only be one value per key; storing a value should fail
681 * if a value under the same key already exists.
683 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY,
686 * @ingroup hashmap There must only be one value per key, but don't
687 * bother checking if a value already exists (faster than
688 * #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY; implemented
689 * just like #GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE but this
690 * option documents better what is intended if
691 * #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY is what is
694 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST
700 * Iterator over hash map entries.
703 * @param key current key code
704 * @param value value in the hash map
705 * @return #GNUNET_YES if we should continue to
710 (*GNUNET_CONTAINER_HashMapIterator) (void *cls,
711 const struct GNUNET_HashCode *key,
717 * Create a multi hash map.
719 * @param len initial size (map will grow as needed)
720 * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default;
721 * #GNUNET_YES means that on 'put', the 'key' does not have
722 * to be copied as the destination of the pointer is
723 * guaranteed to be life as long as the value is stored in
724 * the hashmap. This can significantly reduce memory
725 * consumption, but of course is also a recipie for
726 * heap corruption if the assumption is not true. Only
727 * use this if (1) memory use is important in this case and
728 * (2) you have triple-checked that the invariant holds
729 * @return NULL on error
731 struct GNUNET_CONTAINER_MultiHashMap *
732 GNUNET_CONTAINER_multihashmap_create (unsigned int len,
733 int do_not_copy_keys);
738 * Destroy a hash map. Will not free any values
739 * stored in the hash map!
744 GNUNET_CONTAINER_multihashmap_destroy (struct GNUNET_CONTAINER_MultiHashMap *map);
749 * Given a key find a value in the map matching the key.
752 * @param key what to look for
753 * @return NULL if no value was found; note that
754 * this is indistinguishable from values that just
755 * happen to be NULL; use "contains" to test for
756 * key-value pairs with value NULL
759 GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap *map,
760 const struct GNUNET_HashCode *key);
765 * Remove the given key-value pair from the map. Note that if the
766 * key-value pair is in the map multiple times, only one of the pairs
770 * @param key key of the key-value pair
771 * @param value value of the key-value pair
772 * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
776 GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map,
777 const struct GNUNET_HashCode *key,
782 * Remove all entries for the given key from the map.
783 * Note that the values would not be "freed".
786 * @param key identifies values to be removed
787 * @return number of values removed
790 GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap *map,
791 const struct GNUNET_HashCode *key);
796 * Remove all entries from the map.
797 * Note that the values would not be "freed".
800 * @return number of values removed
803 GNUNET_CONTAINER_multihashmap_clear (struct GNUNET_CONTAINER_MultiHashMap *map);
808 * Check if the map contains any value under the given
809 * key (including values that are NULL).
812 * @param key the key to test if a value exists for it
813 * @return #GNUNET_YES if such a value exists,
817 GNUNET_CONTAINER_multihashmap_contains (const struct GNUNET_CONTAINER_MultiHashMap *map,
818 const struct GNUNET_HashCode * key);
823 * Check if the map contains the given value under the given
827 * @param key the key to test if a value exists for it
828 * @param value value to test for
829 * @return #GNUNET_YES if such a value exists,
833 GNUNET_CONTAINER_multihashmap_contains_value (const struct GNUNET_CONTAINER_MultiHashMap *map,
834 const struct GNUNET_HashCode *key,
840 * Store a key-value pair in the map.
843 * @param key key to use
844 * @param value value to use
845 * @param opt options for put
846 * @return #GNUNET_OK on success,
847 * #GNUNET_NO if a value was replaced (with REPLACE)
848 * #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
849 * value already exists
852 GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map,
853 const struct GNUNET_HashCode *key,
855 enum GNUNET_CONTAINER_MultiHashMapOption
860 * Get the number of key-value pairs in the map.
863 * @return the number of key value pairs
866 GNUNET_CONTAINER_multihashmap_size (const struct GNUNET_CONTAINER_MultiHashMap *map);
871 * Iterate over all entries in the map.
874 * @param it function to call on each entry
875 * @param it_cls extra argument to @a it
876 * @return the number of key value pairs processed,
877 * #GNUNET_SYSERR if it aborted iteration
880 GNUNET_CONTAINER_multihashmap_iterate (const struct GNUNET_CONTAINER_MultiHashMap *map,
881 GNUNET_CONTAINER_HashMapIterator it,
887 * Create an iterator for a multihashmap.
888 * The iterator can be used to retrieve all the elements in the multihashmap
889 * one by one, without having to handle all elements at once (in contrast to
890 * #GNUNET_CONTAINER_multihashmap_iterate). Note that the iterator can not be
891 * used anymore if elements have been removed from 'map' after the creation of
892 * the iterator, or 'map' has been destroyed. Adding elements to 'map' may
893 * result in skipped or repeated elements.
895 * @param map the map to create an iterator for
896 * @return an iterator over the given multihashmap @a map
898 struct GNUNET_CONTAINER_MultiHashMapIterator *
899 GNUNET_CONTAINER_multihashmap_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap *map);
904 * Retrieve the next element from the hash map at the iterator's
905 * position. If there are no elements left, #GNUNET_NO is returned,
906 * and @a key and @a value are not modified. This operation is only
907 * allowed if no elements have been removed from the multihashmap
908 * since the creation of @a iter, and the map has not been destroyed.
909 * Adding elements may result in repeating or skipping elements.
911 * @param iter the iterator to get the next element from
912 * @param key pointer to store the key in, can be NULL
913 * @param value pointer to store the value in, can be NULL
914 * @return #GNUNET_YES we returned an element,
915 * #GNUNET_NO if we are out of elements
918 GNUNET_CONTAINER_multihashmap_iterator_next (struct GNUNET_CONTAINER_MultiHashMapIterator *iter,
919 struct GNUNET_HashCode *key,
925 * Destroy a multihashmap iterator.
927 * @param iter the iterator to destroy
930 GNUNET_CONTAINER_multihashmap_iterator_destroy (struct GNUNET_CONTAINER_MultiHashMapIterator *iter);
935 * Iterate over all entries in the map that match a particular key.
938 * @param key key that the entries must correspond to
939 * @param it function to call on each entry
940 * @param it_cls extra argument to @a it
941 * @return the number of key value pairs processed,
942 * #GNUNET_SYSERR if it aborted iteration
945 GNUNET_CONTAINER_multihashmap_get_multiple (const struct GNUNET_CONTAINER_MultiHashMap *map,
946 const struct GNUNET_HashCode *key,
947 GNUNET_CONTAINER_HashMapIterator it,
953 * Call @a it on a random value from the map, or not at all
954 * if the map is empty. Note that this function has linear
955 * complexity (in the size of the map).
958 * @param it function to call on a random entry
959 * @param it_cls extra argument to @a it
960 * @return the number of key value pairs processed, zero or one.
963 GNUNET_CONTAINER_multihashmap_get_random (const struct GNUNET_CONTAINER_MultiHashMap *map,
964 GNUNET_CONTAINER_HashMapIterator it,
968 /* ***************** Version of Multihashmap for peer identities ****************** */
972 * Iterator over hash map entries.
975 * @param key current public key
976 * @param value value in the hash map
977 * @return #GNUNET_YES if we should continue to
982 (*GNUNET_CONTAINER_PeerMapIterator) (void *cls,
983 const struct GNUNET_PeerIdentity *key,
987 struct GNUNET_CONTAINER_MultiPeerMap;
990 * Create a multi peer map (hash map for public keys of peers).
992 * @param len initial size (map will grow as needed)
993 * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default;
994 * #GNUNET_YES means that on 'put', the 'key' does not have
995 * to be copied as the destination of the pointer is
996 * guaranteed to be life as long as the value is stored in
997 * the hashmap. This can significantly reduce memory
998 * consumption, but of course is also a recipie for
999 * heap corruption if the assumption is not true. Only
1000 * use this if (1) memory use is important in this case and
1001 * (2) you have triple-checked that the invariant holds
1002 * @return NULL on error
1004 struct GNUNET_CONTAINER_MultiPeerMap *
1005 GNUNET_CONTAINER_multipeermap_create (unsigned int len,
1006 int do_not_copy_keys);
1011 * Destroy a hash map. Will not free any values
1012 * stored in the hash map!
1014 * @param map the map
1017 GNUNET_CONTAINER_multipeermap_destroy (struct GNUNET_CONTAINER_MultiPeerMap *map);
1022 * Given a key find a value in the map matching the key.
1024 * @param map the map
1025 * @param key what to look for
1026 * @return NULL if no value was found; note that
1027 * this is indistinguishable from values that just
1028 * happen to be NULL; use "contains" to test for
1029 * key-value pairs with value NULL
1032 GNUNET_CONTAINER_multipeermap_get (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1033 const struct GNUNET_PeerIdentity *key);
1038 * Remove the given key-value pair from the map. Note that if the
1039 * key-value pair is in the map multiple times, only one of the pairs
1042 * @param map the map
1043 * @param key key of the key-value pair
1044 * @param value value of the key-value pair
1045 * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
1049 GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map,
1050 const struct GNUNET_PeerIdentity * key,
1055 * Remove all entries for the given key from the map.
1056 * Note that the values would not be "freed".
1058 * @param map the map
1059 * @param key identifies values to be removed
1060 * @return number of values removed
1063 GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap *map,
1064 const struct GNUNET_PeerIdentity *key);
1069 * Check if the map contains any value under the given
1070 * key (including values that are NULL).
1072 * @param map the map
1073 * @param key the key to test if a value exists for it
1074 * @return #GNUNET_YES if such a value exists,
1078 GNUNET_CONTAINER_multipeermap_contains (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1079 const struct GNUNET_PeerIdentity *key);
1084 * Check if the map contains the given value under the given
1087 * @param map the map
1088 * @param key the key to test if a value exists for it
1089 * @param value value to test for
1090 * @return #GNUNET_YES if such a value exists,
1094 GNUNET_CONTAINER_multipeermap_contains_value (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1095 const struct GNUNET_PeerIdentity * key,
1101 * Store a key-value pair in the map.
1103 * @param map the map
1104 * @param key key to use
1105 * @param value value to use
1106 * @param opt options for put
1107 * @return #GNUNET_OK on success,
1108 * #GNUNET_NO if a value was replaced (with REPLACE)
1109 * #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
1110 * value already exists
1113 GNUNET_CONTAINER_multipeermap_put (struct GNUNET_CONTAINER_MultiPeerMap *map,
1114 const struct GNUNET_PeerIdentity *key,
1116 enum GNUNET_CONTAINER_MultiHashMapOption opt);
1121 * Get the number of key-value pairs in the map.
1123 * @param map the map
1124 * @return the number of key value pairs
1127 GNUNET_CONTAINER_multipeermap_size (const struct GNUNET_CONTAINER_MultiPeerMap *map);
1132 * Iterate over all entries in the map.
1134 * @param map the map
1135 * @param it function to call on each entry
1136 * @param it_cls extra argument to @a it
1137 * @return the number of key value pairs processed,
1138 * #GNUNET_SYSERR if it aborted iteration
1141 GNUNET_CONTAINER_multipeermap_iterate (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1142 GNUNET_CONTAINER_PeerMapIterator it,
1146 struct GNUNET_CONTAINER_MultiPeerMapIterator;
1149 * Create an iterator for a multihashmap.
1150 * The iterator can be used to retrieve all the elements in the multihashmap
1151 * one by one, without having to handle all elements at once (in contrast to
1152 * #GNUNET_CONTAINER_multipeermap_iterate). Note that the iterator can not be
1153 * used anymore if elements have been removed from @a map after the creation of
1154 * the iterator, or 'map' has been destroyed. Adding elements to @a map may
1155 * result in skipped or repeated elements.
1157 * @param map the map to create an iterator for
1158 * @return an iterator over the given multihashmap @a map
1160 struct GNUNET_CONTAINER_MultiPeerMapIterator *
1161 GNUNET_CONTAINER_multipeermap_iterator_create (const struct GNUNET_CONTAINER_MultiPeerMap *map);
1166 * Retrieve the next element from the hash map at the iterator's
1167 * position. If there are no elements left, #GNUNET_NO is returned,
1168 * and @a key and @a value are not modified. This operation is only
1169 * allowed if no elements have been removed from the multihashmap
1170 * since the creation of @a iter, and the map has not been destroyed.
1171 * Adding elements may result in repeating or skipping elements.
1173 * @param iter the iterator to get the next element from
1174 * @param key pointer to store the key in, can be NULL
1175 * @param value pointer to store the value in, can be NULL
1176 * @return #GNUNET_YES we returned an element,
1177 * #GNUNET_NO if we are out of elements
1180 GNUNET_CONTAINER_multipeermap_iterator_next (struct GNUNET_CONTAINER_MultiPeerMapIterator *iter,
1181 struct GNUNET_PeerIdentity *key,
1182 const void **value);
1187 * Destroy a multipeermap iterator.
1189 * @param iter the iterator to destroy
1192 GNUNET_CONTAINER_multipeermap_iterator_destroy (struct GNUNET_CONTAINER_MultiPeerMapIterator *iter);
1197 * Iterate over all entries in the map that match a particular key.
1199 * @param map the map
1200 * @param key public key that the entries must correspond to
1201 * @param it function to call on each entry
1202 * @param it_cls extra argument to @a it
1203 * @return the number of key value pairs processed,
1204 * #GNUNET_SYSERR if it aborted iteration
1207 GNUNET_CONTAINER_multipeermap_get_multiple (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1208 const struct GNUNET_PeerIdentity *key,
1209 GNUNET_CONTAINER_PeerMapIterator it,
1215 * Call @a it on a random value from the map, or not at all
1216 * if the map is empty. Note that this function has linear
1217 * complexity (in the size of the map).
1219 * @param map the map
1220 * @param it function to call on a random entry
1221 * @param it_cls extra argument to @a it
1222 * @return the number of key value pairs processed, zero or one.
1225 GNUNET_CONTAINER_multipeermap_get_random (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1226 GNUNET_CONTAINER_PeerMapIterator it,
1230 /* Version of multihashmap with 32 bit keys */
1234 * Opaque handle for the 32-bit key HashMap.
1236 struct GNUNET_CONTAINER_MultiHashMap32;
1241 * Opaque handle to an iterator over
1242 * a 32-bit key multihashmap.
1244 struct GNUNET_CONTAINER_MultiHashMap32Iterator;
1249 * Iterator over hash map entries.
1251 * @param cls closure
1252 * @param key current key code
1253 * @param value value in the hash map
1254 * @return #GNUNET_YES if we should continue to
1256 * #GNUNET_NO if not.
1258 typedef int (*GNUNET_CONTAINER_HashMapIterator32) (void *cls,
1265 * Create a 32-bit key multi hash map.
1267 * @param len initial size (map will grow as needed)
1268 * @return NULL on error
1270 struct GNUNET_CONTAINER_MultiHashMap32 *
1271 GNUNET_CONTAINER_multihashmap32_create (unsigned int len);
1276 * Destroy a 32-bit key hash map. Will not free any values
1277 * stored in the hash map!
1279 * @param map the map
1282 GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32
1288 * Get the number of key-value pairs in the map.
1290 * @param map the map
1291 * @return the number of key value pairs
1294 GNUNET_CONTAINER_multihashmap32_size (const struct
1295 GNUNET_CONTAINER_MultiHashMap32 *map);
1300 * Given a key find a value in the map matching the key.
1302 * @param map the map
1303 * @param key what to look for
1304 * @return NULL if no value was found; note that
1305 * this is indistinguishable from values that just
1306 * happen to be NULL; use "contains" to test for
1307 * key-value pairs with value NULL
1310 GNUNET_CONTAINER_multihashmap32_get (const struct
1311 GNUNET_CONTAINER_MultiHashMap32 *map,
1317 * Iterate over all entries in the map.
1319 * @param map the map
1320 * @param it function to call on each entry
1321 * @param it_cls extra argument to @a it
1322 * @return the number of key value pairs processed,
1323 * #GNUNET_SYSERR if it aborted iteration
1326 GNUNET_CONTAINER_multihashmap32_iterate (const struct
1327 GNUNET_CONTAINER_MultiHashMap32 *map,
1328 GNUNET_CONTAINER_HashMapIterator32 it,
1334 * Remove the given key-value pair from the map. Note that if the
1335 * key-value pair is in the map multiple times, only one of the pairs
1338 * @param map the map
1339 * @param key key of the key-value pair
1340 * @param value value of the key-value pair
1341 * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
1345 GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 *map,
1352 * Remove all entries for the given key from the map.
1353 * Note that the values would not be "freed".
1355 * @param map the map
1356 * @param key identifies values to be removed
1357 * @return number of values removed
1360 GNUNET_CONTAINER_multihashmap32_remove_all (struct GNUNET_CONTAINER_MultiHashMap32 *map,
1366 * Check if the map contains any value under the given
1367 * key (including values that are NULL).
1369 * @param map the map
1370 * @param key the key to test if a value exists for it
1371 * @return #GNUNET_YES if such a value exists,
1375 GNUNET_CONTAINER_multihashmap32_contains (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
1381 * Check if the map contains the given value under the given
1384 * @param map the map
1385 * @param key the key to test if a value exists for it
1386 * @param value value to test for
1387 * @return #GNUNET_YES if such a value exists,
1391 GNUNET_CONTAINER_multihashmap32_contains_value (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
1398 * Store a key-value pair in the map.
1400 * @param map the map
1401 * @param key key to use
1402 * @param value value to use
1403 * @param opt options for put
1404 * @return #GNUNET_OK on success,
1405 * #GNUNET_NO if a value was replaced (with REPLACE)
1406 * #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
1407 * value already exists
1410 GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32 *map,
1413 enum GNUNET_CONTAINER_MultiHashMapOption opt);
1418 * Iterate over all entries in the map that match a particular key.
1420 * @param map the map
1421 * @param key key that the entries must correspond to
1422 * @param it function to call on each entry
1423 * @param it_cls extra argument to @a it
1424 * @return the number of key value pairs processed,
1425 * #GNUNET_SYSERR if it aborted iteration
1428 GNUNET_CONTAINER_multihashmap32_get_multiple (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
1430 GNUNET_CONTAINER_HashMapIterator32 it,
1435 * Create an iterator for a 32-bit multihashmap.
1436 * The iterator can be used to retrieve all the elements in the multihashmap
1437 * one by one, without having to handle all elements at once (in contrast to
1438 * #GNUNET_CONTAINER_multihashmap32_iterate). Note that the iterator can not be
1439 * used anymore if elements have been removed from 'map' after the creation of
1440 * the iterator, or 'map' has been destroyed. Adding elements to 'map' may
1441 * result in skipped or repeated elements.
1443 * @param map the map to create an iterator for
1444 * @return an iterator over the given multihashmap map
1446 struct GNUNET_CONTAINER_MultiHashMap32Iterator *
1447 GNUNET_CONTAINER_multihashmap32_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap32 *map);
1451 * Retrieve the next element from the hash map at the iterator's position.
1452 * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
1454 * This operation is only allowed if no elements have been removed from the
1455 * multihashmap since the creation of 'iter', and the map has not been destroyed.
1456 * Adding elements may result in repeating or skipping elements.
1458 * @param iter the iterator to get the next element from
1459 * @param key pointer to store the key in, can be NULL
1460 * @param value pointer to store the value in, can be NULL
1461 * @return #GNUNET_YES we returned an element,
1462 * #GNUNET_NO if we are out of elements
1465 GNUNET_CONTAINER_multihashmap32_iterator_next (struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter,
1467 const void **value);
1471 * Destroy a 32-bit multihashmap iterator.
1473 * @param iter the iterator to destroy
1476 GNUNET_CONTAINER_multihashmap32_iterator_destroy (struct GNUNET_CONTAINER_MultiHashMapIterator *iter);
1479 /* ******************** doubly-linked list *************** */
1480 /* To avoid mistakes: head->prev == tail->next == NULL */
1484 * Insert an element at the head of a DLL. Assumes that head, tail and
1485 * element are structs with prev and next fields.
1487 * @param head pointer to the head of the DLL
1488 * @param tail pointer to the tail of the DLL
1489 * @param element element to insert
1491 #define GNUNET_CONTAINER_DLL_insert(head,tail,element) do { \
1492 GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1493 GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1494 (element)->next = (head); \
1495 (element)->prev = NULL; \
1496 if ((tail) == NULL) \
1499 (head)->prev = element; \
1500 (head) = (element); } while (0)
1505 * Insert an element at the tail of a DLL. Assumes that head, tail and
1506 * element are structs with prev and next fields.
1508 * @param head pointer to the head of the DLL
1509 * @param tail pointer to the tail of the DLL
1510 * @param element element to insert
1512 #define GNUNET_CONTAINER_DLL_insert_tail(head,tail,element) do { \
1513 GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1514 GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1515 (element)->prev = (tail); \
1516 (element)->next = NULL; \
1517 if ((head) == NULL) \
1520 (tail)->next = element; \
1521 (tail) = (element); } while (0)
1526 * Insert an element into a DLL after the given other element. Insert
1527 * at the head if the other element is NULL.
1529 * @param head pointer to the head of the DLL
1530 * @param tail pointer to the tail of the DLL
1531 * @param other prior element, NULL for insertion at head of DLL
1532 * @param element element to insert
1534 #define GNUNET_CONTAINER_DLL_insert_after(head,tail,other,element) do { \
1535 GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1536 GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1537 (element)->prev = (other); \
1538 if (NULL == other) \
1540 (element)->next = (head); \
1541 (head) = (element); \
1545 (element)->next = (other)->next; \
1546 (other)->next = (element); \
1548 if (NULL == (element)->next) \
1549 (tail) = (element); \
1551 (element)->next->prev = (element); } while (0)
1556 * Insert an element into a DLL before the given other element. Insert
1557 * at the tail if the other element is NULL.
1559 * @param head pointer to the head of the DLL
1560 * @param tail pointer to the tail of the DLL
1561 * @param other prior element, NULL for insertion at head of DLL
1562 * @param element element to insert
1564 #define GNUNET_CONTAINER_DLL_insert_before(head,tail,other,element) do { \
1565 GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1566 GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1567 (element)->next = (other); \
1568 if (NULL == other) \
1570 (element)->prev = (tail); \
1571 (tail) = (element); \
1575 (element)->prev = (other)->prev; \
1576 (other)->prev = (element); \
1578 if (NULL == (element)->prev) \
1579 (head) = (element); \
1581 (element)->prev->next = (element); } while (0)
1586 * Remove an element from a DLL. Assumes that head, tail and
1587 * element point to structs with prev and next fields.
1589 * Using the head or tail pointer as the element
1590 * argument does NOT work with this macro.
1591 * Make sure to store head/tail in another pointer
1592 * and use it to remove the head or tail of the list.
1594 * @param head pointer to the head of the DLL
1595 * @param tail pointer to the tail of the DLL
1596 * @param element element to remove
1598 #define GNUNET_CONTAINER_DLL_remove(head,tail,element) do { \
1599 GNUNET_assert ( ( (element)->prev != NULL) || ((head) == (element))); \
1600 GNUNET_assert ( ( (element)->next != NULL) || ((tail) == (element))); \
1601 if ((element)->prev == NULL) \
1602 (head) = (element)->next; \
1604 (element)->prev->next = (element)->next; \
1605 if ((element)->next == NULL) \
1606 (tail) = (element)->prev; \
1608 (element)->next->prev = (element)->prev; \
1609 (element)->next = NULL; \
1610 (element)->prev = NULL; } while (0)
1613 /* ************ Multi-DLL interface, allows DLL elements to be
1614 in multiple lists at the same time *********************** */
1618 * Insert an element at the head of a MDLL. Assumes that head, tail and
1619 * element are structs with prev and next fields.
1621 * @param mdll suffix name for the next and prev pointers in the element
1622 * @param head pointer to the head of the MDLL
1623 * @param tail pointer to the tail of the MDLL
1624 * @param element element to insert
1626 #define GNUNET_CONTAINER_MDLL_insert(mdll,head,tail,element) do { \
1627 GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1628 GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1629 (element)->next_##mdll = (head); \
1630 (element)->prev_##mdll = NULL; \
1631 if ((tail) == NULL) \
1634 (head)->prev_##mdll = element; \
1635 (head) = (element); } while (0)
1640 * Insert an element at the tail of a MDLL. Assumes that head, tail and
1641 * element are structs with prev and next fields.
1643 * @param mdll suffix name for the next and prev pointers in the element
1644 * @param head pointer to the head of the MDLL
1645 * @param tail pointer to the tail of the MDLL
1646 * @param element element to insert
1648 #define GNUNET_CONTAINER_MDLL_insert_tail(mdll,head,tail,element) do { \
1649 GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1650 GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1651 (element)->prev_##mdll = (tail); \
1652 (element)->next_##mdll = NULL; \
1653 if ((head) == NULL) \
1656 (tail)->next_##mdll = element; \
1657 (tail) = (element); } while (0)
1662 * Insert an element into a MDLL after the given other element. Insert
1663 * at the head if the other element is NULL.
1665 * @param mdll suffix name for the next and prev pointers in the element
1666 * @param head pointer to the head of the MDLL
1667 * @param tail pointer to the tail of the MDLL
1668 * @param other prior element, NULL for insertion at head of MDLL
1669 * @param element element to insert
1671 #define GNUNET_CONTAINER_MDLL_insert_after(mdll,head,tail,other,element) do { \
1672 GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1673 GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1674 (element)->prev_##mdll = (other); \
1675 if (NULL == other) \
1677 (element)->next_##mdll = (head); \
1678 (head) = (element); \
1682 (element)->next_##mdll = (other)->next_##mdll; \
1683 (other)->next_##mdll = (element); \
1685 if (NULL == (element)->next_##mdll) \
1686 (tail) = (element); \
1688 (element)->next->prev_##mdll = (element); } while (0)
1693 * Insert an element into a MDLL before the given other element. Insert
1694 * at the tail if the other element is NULL.
1696 * @param mdll suffix name for the next and prev pointers in the element
1697 * @param head pointer to the head of the MDLL
1698 * @param tail pointer to the tail of the MDLL
1699 * @param other prior element, NULL for insertion at head of MDLL
1700 * @param element element to insert
1702 #define GNUNET_CONTAINER_MDLL_insert_before(mdll,head,tail,other,element) do { \
1703 GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1704 GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1705 (element)->next_##mdll = (other); \
1706 if (NULL == other) \
1708 (element)->prev = (tail); \
1709 (tail) = (element); \
1713 (element)->prev_##mdll = (other)->prev_##mdll; \
1714 (other)->prev_##mdll = (element); \
1716 if (NULL == (element)->prev_##mdll) \
1717 (head) = (element); \
1719 (element)->prev_##mdll->next_##mdll = (element); } while (0)
1724 * Remove an element from a MDLL. Assumes
1725 * that head, tail and element are structs
1726 * with prev and next fields.
1728 * @param mdll suffix name for the next and prev pointers in the element
1729 * @param head pointer to the head of the MDLL
1730 * @param tail pointer to the tail of the MDLL
1731 * @param element element to remove
1733 #define GNUNET_CONTAINER_MDLL_remove(mdll,head,tail,element) do { \
1734 GNUNET_assert ( ( (element)->prev_##mdll != NULL) || ((head) == (element))); \
1735 GNUNET_assert ( ( (element)->next_##mdll != NULL) || ((tail) == (element))); \
1736 if ((element)->prev_##mdll == NULL) \
1737 (head) = (element)->next_##mdll; \
1739 (element)->prev_##mdll->next_##mdll = (element)->next_##mdll; \
1740 if ((element)->next_##mdll == NULL) \
1741 (tail) = (element)->prev_##mdll; \
1743 (element)->next_##mdll->prev_##mdll = (element)->prev_##mdll; \
1744 (element)->next_##mdll = NULL; \
1745 (element)->prev_##mdll = NULL; } while (0)
1749 /* ******************** Heap *************** */
1754 * Cost by which elements in a heap can be ordered.
1756 typedef uint64_t GNUNET_CONTAINER_HeapCostType;
1761 * Heap type, either max or min.
1763 enum GNUNET_CONTAINER_HeapOrder
1767 * Heap with the maximum cost at the root.
1769 GNUNET_CONTAINER_HEAP_ORDER_MAX,
1773 * Heap with the minimum cost at the root.
1775 GNUNET_CONTAINER_HEAP_ORDER_MIN
1783 struct GNUNET_CONTAINER_Heap;
1788 * Handle to a node in a heap.
1790 struct GNUNET_CONTAINER_HeapNode;
1795 * Create a new heap.
1797 * @param order how should the heap be sorted?
1798 * @return handle to the heap
1800 struct GNUNET_CONTAINER_Heap *
1801 GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order);
1806 * Destroys the heap. Only call on a heap that
1809 * @param heap heap to destroy
1812 GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap);
1817 * Get element stored at the root of @a heap.
1819 * @param heap Heap to inspect.
1820 * @return Element at the root, or NULL if heap is empty.
1823 GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap);
1827 * Get @a element and @a cost stored at the root of @a heap.
1829 * @param[in] heap Heap to inspect.
1830 * @param[out] element Root element is returned here.
1831 * @param[out] cost Cost of @a element is returned here.
1832 * @return #GNUNET_YES if an element is returned,
1833 * #GNUNET_NO if the heap is empty.
1836 GNUNET_CONTAINER_heap_peek2 (const struct GNUNET_CONTAINER_Heap *heap,
1838 GNUNET_CONTAINER_HeapCostType *cost);
1843 * Get the current size of the heap
1845 * @param heap the heap to get the size of
1846 * @return number of elements stored
1849 GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap);
1854 * Get the current cost of the node
1856 * @param node the node to get the cost of
1857 * @return cost of the node
1859 GNUNET_CONTAINER_HeapCostType
1860 GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode
1867 * @param cls closure
1868 * @param node internal node of the heap
1869 * @param element value stored at the node
1870 * @param cost cost associated with the node
1871 * @return #GNUNET_YES if we should continue to iterate,
1872 * #GNUNET_NO if not.
1875 (*GNUNET_CONTAINER_HeapIterator) (void *cls,
1876 struct GNUNET_CONTAINER_HeapNode *node,
1878 GNUNET_CONTAINER_HeapCostType cost);
1883 * Iterate over all entries in the heap.
1885 * @param heap the heap
1886 * @param iterator function to call on each entry
1887 * @param iterator_cls closure for @a iterator
1890 GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
1891 GNUNET_CONTAINER_HeapIterator iterator,
1892 void *iterator_cls);
1896 * Perform a random walk of the tree. The walk is biased
1897 * towards elements closer to the root of the tree (since
1898 * each walk starts at the root and ends at a random leaf).
1899 * The heap internally tracks the current position of the
1902 * @param heap heap to walk
1903 * @return data stored at the next random node in the walk;
1904 * NULL if the tree is empty.
1907 GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap);
1912 * Inserts a new element into the heap.
1914 * @param heap heap to modify
1915 * @param element element to insert
1916 * @param cost cost for the element
1917 * @return node for the new element
1919 struct GNUNET_CONTAINER_HeapNode *
1920 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap,
1922 GNUNET_CONTAINER_HeapCostType cost);
1927 * Remove root of the heap.
1929 * @param heap heap to modify
1930 * @return element data stored at the root node
1933 GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap);
1938 * Removes a node from the heap.
1940 * @param node node to remove
1941 * @return element data stored at the node, NULL if heap is empty
1944 GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node);
1949 * Updates the cost of any node in the tree
1951 * @param heap heap to modify
1952 * @param node node for which the cost is to be changed
1953 * @param new_cost new cost for the node
1956 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
1957 struct GNUNET_CONTAINER_HeapNode *node,
1958 GNUNET_CONTAINER_HeapCostType new_cost);
1961 #if 0 /* keep Emacsens' auto-indent happy */
1969 /* ifndef GNUNET_CONTAINER_LIB_H */
1971 /* end of gnunet_container_lib.h */