X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=src%2Finclude%2Fgnunet_container_lib.h;h=c77d82fd37a6874c092dc4ae80e7fd27a789f7d6;hb=a67bd3630046d3a52195a13cbd4b4631c283d68d;hp=bec0405969c439906c07cb1d5a0732e30cac2cb7;hpb=5491c6356965f9c20ef64f2c63f7a14989930bf3;p=oweals%2Fgnunet.git diff --git a/src/include/gnunet_container_lib.h b/src/include/gnunet_container_lib.h index bec040596..c77d82fd3 100644 --- a/src/include/gnunet_container_lib.h +++ b/src/include/gnunet_container_lib.h @@ -1,10 +1,10 @@ /* This file is part of GNUnet. - (C) 2001, 2002, 2003, 2004, 2005, 2006, 2008, 2009, 2010 Christian Grothoff (and other contributing authors) + Copyright (C) 2001-2015 GNUnet e.V. GNUnet is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published - by the Free Software Foundation; either version 2, or (at your + by the Free Software Foundation; either version 3, or (at your option) any later version. GNUnet is distributed in the hope that it will be useful, but @@ -14,16 +14,34 @@ You should have received a copy of the GNU General Public License along with GNUnet; see the file COPYING. If not, write to the - Free Software Foundation, Inc., 59 Temple Place - Suite 330, - Boston, MA 02111-1307, USA. + Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, + Boston, MA 02110-1301, USA. */ /** - * @file include/gnunet_container_lib.h - * @brief container classes for GNUnet - * * @author Christian Grothoff * @author Nils Durner + * + * @file + * Container classes for GNUnet + * + * @defgroup hashmap Container library: MultiHashMap + * Hash map with multiple values per key. + * + * @see [Documentation](https://gnunet.org/util_multihashmap) + * + * @defgroup heap Container library: Heap + * Min- or max-heap with arbitrary element removal + * + * @defgroup bloomfilter Container library: Bloom filter + * Probabilistic set tests + * + * @defgroup dll Container library: Doubly-linked list + * + * @see [Documentation](https://gnunet.org/mdll-api) + * + * @defgroup metadata Container library: Metadata + * GNU libextractor key-value pairs */ #ifndef GNUNET_CONTAINER_LIB_H @@ -31,8 +49,146 @@ /* add error and config prototypes */ #include "gnunet_crypto_lib.h" + + +/** + * Try to compress the given block of data using libz. Only returns + * the compressed block if compression worked and the new block is + * actually smaller. Decompress using #GNUNET_decompress(). + * + * @param data block to compress; if compression + * resulted in a smaller block, the first + * bytes of data are updated to the compressed + * data + * @param old_size number of bytes in data + * @param[out] result set to the compressed data, if compression worked + * @param[out] new_size set to size of result, if compression worked + * @return #GNUNET_YES if compression reduce the size, + * #GNUNET_NO if compression did not help + */ +int +GNUNET_try_compression (const char *data, + size_t old_size, + char **result, + size_t *new_size); + + +/** + * Decompress input, return the decompressed data as output. Dual to + * #GNUNET_try_compression(). Caller must set @a output_size to the + * number of bytes that were originally compressed. + * + * @param input compressed data + * @param input_size number of bytes in input + * @param output_size expected size of the output + * @return NULL on error, buffer of @a output_size decompressed bytes otherwise + */ +char * +GNUNET_decompress (const char *input, + size_t input_size, + size_t output_size); + + +#if HAVE_EXTRACTOR_H + #include +#else + +/* definitions from extractor.h we need for the build */ + +/** + * Enumeration defining various sources of keywords. See also + * http://dublincore.org/documents/1998/09/dces/ + */ +enum EXTRACTOR_MetaType { + EXTRACTOR_METATYPE_RESERVED = 0, + EXTRACTOR_METATYPE_MIMETYPE = 1, + EXTRACTOR_METATYPE_FILENAME = 2, + EXTRACTOR_METATYPE_COMMENT = 3, + EXTRACTOR_METATYPE_TITLE = 4, + EXTRACTOR_METATYPE_BOOK_TITLE = 5, + EXTRACTOR_METATYPE_JOURNAL_NAME = 8, + EXTRACTOR_METATYPE_AUTHOR_NAME = 13, + EXTRACTOR_METATYPE_PUBLICATION_DATE = 24, + EXTRACTOR_METATYPE_URL = 29, + EXTRACTOR_METATYPE_URI = 30, + EXTRACTOR_METATYPE_ISRC = 31, + EXTRACTOR_METATYPE_UNKNOWN = 45, + EXTRACTOR_METATYPE_DESCRIPTION = 46, + EXTRACTOR_METATYPE_KEYWORDS = 49, + EXTRACTOR_METATYPE_SUBJECT = 52, + EXTRACTOR_METATYPE_PACKAGE_NAME = 69, + EXTRACTOR_METATYPE_THUMBNAIL = 114, + EXTRACTOR_METATYPE_ALBUM = 129, + EXTRACTOR_METATYPE_ARTIST = 130, + EXTRACTOR_METATYPE_ORIGINAL_TITLE = 162, + EXTRACTOR_METATYPE_GNUNET_FULL_DATA = 174, + EXTRACTOR_METATYPE_GNUNET_ORIGINAL_FILENAME = 180, + +}; + +/** + * Format in which the extracted meta data is presented. + */ +enum EXTRACTOR_MetaFormat { + /** + * Format is unknown. + */ + EXTRACTOR_METAFORMAT_UNKNOWN = 0, + + /** + * 0-terminated, UTF-8 encoded string. "data_len" + * is strlen(data)+1. + */ + EXTRACTOR_METAFORMAT_UTF8 = 1, + + /** + * Some kind of binary format, see given Mime type. + */ + EXTRACTOR_METAFORMAT_BINARY = 2, + + /** + * 0-terminated string. The specific encoding is unknown. + * "data_len" is strlen (data)+1. + */ + EXTRACTOR_METAFORMAT_C_STRING = 3 +}; + + +/** + * Type of a function that libextractor calls for each + * meta data item found. + * + * @param cls closure (user-defined) + * @param plugin_name name of the plugin that produced this value; + * special values can be used (i.e. '<zlib>' for zlib being + * used in the main libextractor library and yielding + * meta data). + * @param type libextractor-type describing the meta data + * @param format basic format information about @a data + * @param data_mime_type mime-type of @a data (not of the original file); + * can be NULL (if mime-type is not known) + * @param data actual meta-data found + * @param data_len number of bytes in @a data + * @return 0 to continue extracting, 1 to abort + */ +typedef int +(*EXTRACTOR_MetaDataProcessor) (void *cls, + const char *plugin_name, + enum EXTRACTOR_MetaType type, + enum EXTRACTOR_MetaFormat format, + const char *data_mime_type, + const char *data, + size_t data_len); + +#endif + +#ifndef EXTRACTOR_METATYPE_GNUNET_ORIGINAL_FILENAME +/* hack for LE < 0.6.3 */ +#define EXTRACTOR_METATYPE_GNUNET_ORIGINAL_FILENAME 180 +#endif + #ifdef __cplusplus extern "C" { @@ -46,182 +202,264 @@ extern "C" /** * @brief bloomfilter representation (opaque) + * @ingroup bloomfilter */ struct GNUNET_CONTAINER_BloomFilter; + /** - * Iterator over HashCodes. + * @ingroup bloomfilter + * Iterator over `struct GNUNET_HashCode`. * * @param cls closure * @param next set to the next hash code - * @return GNUNET_YES if next was updated - * GNUNET_NO if there are no more entries + * @return #GNUNET_YES if next was updated + * #GNUNET_NO if there are no more entries */ -typedef int (*GNUNET_HashCodeIterator) (void *cls, - GNUNET_HashCode * next); +typedef int +(*GNUNET_CONTAINER_HashCodeIterator) (void *cls, + struct GNUNET_HashCode *next); + /** - * Load a bloom-filter from a file. + * @ingroup bloomfilter + * Load a Bloom filter from a file. * * @param filename the name of the file (or the prefix) * @param size the size of the bloom-filter (number of - * bytes of storage space to use) - * @param k the number of GNUNET_CRYPTO_hash-functions to apply per + * bytes of storage space to use); will be rounded up + * to next power of 2 + * @param k the number of #GNUNET_CRYPTO_hash-functions to apply per * element (number of bits set per element in the set) * @return the bloomfilter */ struct GNUNET_CONTAINER_BloomFilter * -GNUNET_CONTAINER_bloomfilter_load (const - char - *filename, - size_t - size, - unsigned - int - k); +GNUNET_CONTAINER_bloomfilter_load (const char *filename, + size_t size, + unsigned int k); + /** - * Create a bloom filter from raw bits. + * @ingroup bloomfilter + * Create a Bloom filter from raw bits. * * @param data the raw bits in memory (maybe NULL, * in which case all bits should be considered * to be zero). * @param size the size of the bloom-filter (number of - * bytes of storage space to use); also size of data + * bytes of storage space to use); also size of @a data * -- unless data is NULL. Must be a power of 2. - * @param k the number of GNUNET_CRYPTO_hash-functions to apply per + * @param k the number of #GNUNET_CRYPTO_hash-functions to apply per * element (number of bits set per element in the set) * @return the bloomfilter */ struct GNUNET_CONTAINER_BloomFilter * -GNUNET_CONTAINER_bloomfilter_init (const - char - *data, - size_t - size, - unsigned - int - k); +GNUNET_CONTAINER_bloomfilter_init (const char *data, + size_t size, + unsigned int k); + /** - * Copy the raw data of this bloomfilter into + * @ingroup bloomfilter + * Copy the raw data of this Bloom filter into * the given data array. * * @param data where to write the data - * @param size the size of the given data array - * @return GNUNET_SYSERR if the data array of the wrong size + * @param size the size of the given @a data array + * @return #GNUNET_SYSERR if the data array of the wrong size */ -int GNUNET_CONTAINER_bloomfilter_get_raw_data (struct - GNUNET_CONTAINER_BloomFilter - *bf, char *data, - size_t size); +int +GNUNET_CONTAINER_bloomfilter_get_raw_data (const struct GNUNET_CONTAINER_BloomFilter *bf, + char *data, + size_t size); + /** + * @ingroup bloomfilter * Test if an element is in the filter. + * * @param e the element * @param bf the filter - * @return GNUNET_YES if the element is in the filter, GNUNET_NO if not + * @return #GNUNET_YES if the element is in the filter, #GNUNET_NO if not */ -int GNUNET_CONTAINER_bloomfilter_test (struct GNUNET_CONTAINER_BloomFilter - *bf, const GNUNET_HashCode * e); +int +GNUNET_CONTAINER_bloomfilter_test (const struct GNUNET_CONTAINER_BloomFilter *bf, + const struct GNUNET_HashCode *e); + /** - * Add an element to the filter + * @ingroup bloomfilter + * Add an element to the filter. + * * @param bf the filter * @param e the element */ -void GNUNET_CONTAINER_bloomfilter_add (struct GNUNET_CONTAINER_BloomFilter - *bf, const GNUNET_HashCode * e); +void +GNUNET_CONTAINER_bloomfilter_add (struct GNUNET_CONTAINER_BloomFilter *bf, + const struct GNUNET_HashCode *e); + /** + * @ingroup bloomfilter * Remove an element from the filter. + * * @param bf the filter * @param e the element to remove */ -void GNUNET_CONTAINER_bloomfilter_remove (struct GNUNET_CONTAINER_BloomFilter - *bf, const GNUNET_HashCode * e); +void +GNUNET_CONTAINER_bloomfilter_remove (struct GNUNET_CONTAINER_BloomFilter *bf, + const struct GNUNET_HashCode *e); + + +/** + * @ingroup bloomfilter + * Create a copy of a bloomfilter. + * + * @param bf the filter + * @return copy of bf + */ +struct GNUNET_CONTAINER_BloomFilter * +GNUNET_CONTAINER_bloomfilter_copy (const struct GNUNET_CONTAINER_BloomFilter *bf); + + /** + * @ingroup bloomfilter * Free the space associcated with a filter * in memory, flush to drive if needed (do not - * free the space on the drive) + * free the space on the drive). + * + * @param bf the filter + */ +void +GNUNET_CONTAINER_bloomfilter_free (struct GNUNET_CONTAINER_BloomFilter *bf); + + +/** + * Get the number of the addresses set per element in the bloom filter. + * + * @param bf the filter + * @return addresses set per element in the bf + */ +size_t +GNUNET_CONTAINER_bloomfilter_get_element_addresses (const struct GNUNET_CONTAINER_BloomFilter *bf); + + +/** + * @ingroup bloomfilter + * Get size of the bloom filter. + * * @param bf the filter + * @return number of bytes used for the data of the bloom filter */ -void GNUNET_CONTAINER_bloomfilter_free (struct GNUNET_CONTAINER_BloomFilter - *bf); +size_t +GNUNET_CONTAINER_bloomfilter_get_size (const struct GNUNET_CONTAINER_BloomFilter *bf); + /** - * Reset a bloom filter to empty. + * @ingroup bloomfilter + * Reset a Bloom filter to empty. + * * @param bf the filter */ -void GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter - *bf); +void +GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter *bf); + /** - * Or the entries of the given raw data array with the - * data of the given bloom filter. Assumes that - * the size of the data array and the current filter + * @ingroup bloomfilter + * "or" the entries of the given raw data array with the + * data of the given Bloom filter. Assumes that + * the @a size of the @a data array and the current filter * match. * * @param bf the filter * @param data data to OR-in - * @param size size of data - * @return GNUNET_OK on success + * @param size size of @a data + * @return #GNUNET_OK on success + */ +int +GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf, + const char *data, size_t size); + + +/** + * @ingroup bloomfilter + * "or" the entries of the given raw data array with the + * data of the given Bloom filter. Assumes that + * the size of the two filters matches. + * + * @param bf the filter + * @param to_or the bloomfilter to or-in + * @return #GNUNET_OK on success */ -int GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf, - const char *data, size_t size); +int +GNUNET_CONTAINER_bloomfilter_or2 (struct GNUNET_CONTAINER_BloomFilter *bf, + const struct GNUNET_CONTAINER_BloomFilter *to_or); + /** + * @ingroup bloomfilter * Resize a bloom filter. Note that this operation - * is pretty costly. Essentially, the bloom filter + * is pretty costly. Essentially, the Bloom filter * needs to be completely re-build. * * @param bf the filter * @param iterator an iterator over all elements stored in the BF - * @param iterator_cls closure for iterator + * @param iterator_cls closure for @a iterator * @param size the new size for the filter - * @param k the new number of GNUNET_CRYPTO_hash-function to apply per element + * @param k the new number of #GNUNET_CRYPTO_hash-function to apply per element */ -void GNUNET_CONTAINER_bloomfilter_resize (struct GNUNET_CONTAINER_BloomFilter - *bf, - GNUNET_HashCodeIterator iterator, - void *iterator_cls, - size_t size, unsigned int k); +void +GNUNET_CONTAINER_bloomfilter_resize (struct GNUNET_CONTAINER_BloomFilter *bf, + GNUNET_CONTAINER_HashCodeIterator iterator, + void *iterator_cls, + size_t size, + unsigned int k); + /* ****************** metadata ******************* */ /** + * @ingroup metadata * Meta data to associate with a file, directory or namespace. */ struct GNUNET_CONTAINER_MetaData; + /** - * Create a fresh MetaData token. - * + * @ingroup metadata + * Create a fresh meta data container. + * * @return empty meta-data container */ struct GNUNET_CONTAINER_MetaData * GNUNET_CONTAINER_meta_data_create (void); + /** + * @ingroup metadata * Duplicate a MetaData token. - * + * * @param md what to duplicate * @return duplicate meta-data container */ struct GNUNET_CONTAINER_MetaData * -GNUNET_CONTAINER_meta_data_duplicate (const struct - GNUNET_CONTAINER_MetaData *md); +GNUNET_CONTAINER_meta_data_duplicate (const struct GNUNET_CONTAINER_MetaData *md); + /** + * @ingroup metadata * Free meta data. * * @param md what to free */ -void +void GNUNET_CONTAINER_meta_data_destroy (struct GNUNET_CONTAINER_MetaData *md); + /** + * @ingroup metadata * Test if two MDs are equal. We consider them equal if * the meta types, formats and content match (we do not * include the mime types and plugins names in this @@ -229,16 +467,15 @@ GNUNET_CONTAINER_meta_data_destroy (struct GNUNET_CONTAINER_MetaData *md); * * @param md1 first value to check * @param md2 other value to check - * @return GNUNET_YES if they are equal + * @return #GNUNET_YES if they are equal */ -int -GNUNET_CONTAINER_meta_data_test_equal (const struct - GNUNET_CONTAINER_MetaData *md1, - const struct - GNUNET_CONTAINER_MetaData *md2); +int +GNUNET_CONTAINER_meta_data_test_equal (const struct GNUNET_CONTAINER_MetaData *md1, + const struct GNUNET_CONTAINER_MetaData *md2); /** + * @ingroup metadata * Extend metadata. * * @param md metadata to extend @@ -247,67 +484,94 @@ GNUNET_CONTAINER_meta_data_test_equal (const struct * used in the main libextractor library and yielding * meta data). * @param type libextractor-type describing the meta data - * @param format basic format information about data + * @param format basic format information about data * @param data_mime_type mime-type of data (not of the original file); * can be NULL (if mime-type is not known) * @param data actual meta-data found - * @param data_len number of bytes in data - * @return GNUNET_OK on success, GNUNET_SYSERR if this entry already exists + * @param data_size number of bytes in data + * @return #GNUNET_OK on success, #GNUNET_SYSERR if this entry already exists * data_mime_type and plugin_name are not considered for "exists" checks */ -int +int GNUNET_CONTAINER_meta_data_insert (struct GNUNET_CONTAINER_MetaData *md, - const char *plugin_name, - enum EXTRACTOR_MetaType type, - enum EXTRACTOR_MetaFormat format, - const char *data_mime_type, - const char *data, - size_t data_len); + const char *plugin_name, + enum EXTRACTOR_MetaType type, + enum EXTRACTOR_MetaFormat format, + const char *data_mime_type, + const char *data, + size_t data_size); + + +/** + * @ingroup metadata + * Extend metadata. Merges the meta data from the second argument + * into the first, discarding duplicate key-value pairs. + * + * @param md metadata to extend + * @param in metadata to merge + */ +void +GNUNET_CONTAINER_meta_data_merge (struct GNUNET_CONTAINER_MetaData *md, + const struct GNUNET_CONTAINER_MetaData *in); /** + * @ingroup metadata * Remove an item. * * @param md metadata to manipulate * @param type type of the item to remove * @param data specific value to remove, NULL to remove all * entries of the given type - * @param data_len number of bytes in data - * @return GNUNET_OK on success, GNUNET_SYSERR if the item does not exist in md + * @param data_size number of bytes in data + * @return #GNUNET_OK on success, #GNUNET_SYSERR if the item does not exist in md */ -int +int GNUNET_CONTAINER_meta_data_delete (struct GNUNET_CONTAINER_MetaData *md, - enum EXTRACTOR_MetaType type, - const char *data, - size_t data_len); + enum EXTRACTOR_MetaType type, + const char *data, + size_t data_size); + + +/** + * @ingroup metadata + * Remove all items in the container. + * + * @param md metadata to manipulate + */ +void +GNUNET_CONTAINER_meta_data_clear (struct GNUNET_CONTAINER_MetaData *md); /** + * @ingroup metadata * Add the current time as the publication date * to the meta-data. * * @param md metadata to modify */ -void -GNUNET_CONTAINER_meta_data_add_publication_date (struct - GNUNET_CONTAINER_MetaData - *md); +void +GNUNET_CONTAINER_meta_data_add_publication_date (struct GNUNET_CONTAINER_MetaData *md); /** + * @ingroup metadata * Iterate over MD entries. * * @param md metadata to inspect - * @param iter function to call on each entry - * @param iter_cls closure for iterator + * @param iter function to call on each entry, return 0 to continue to iterate + * and 1 to abort iteration in this function (GNU libextractor API!) + * @param iter_cls closure for @a iter * @return number of entries */ -int GNUNET_CONTAINER_meta_data_iterate (const struct - GNUNET_CONTAINER_MetaData *md, - EXTRACTOR_MetaDataProcessor - iter, void *iter_cls); +int +GNUNET_CONTAINER_meta_data_iterate (const struct GNUNET_CONTAINER_MetaData *md, + EXTRACTOR_MetaDataProcessor iter, + void *iter_cls); + /** + * @ingroup metadata * Get the first MD entry of the given type. Caller * is responsible for freeing the return value. * Also, only meta data items that are strings (0-terminated) @@ -318,12 +582,12 @@ int GNUNET_CONTAINER_meta_data_iterate (const struct * @return NULL if no entry was found */ char * -GNUNET_CONTAINER_meta_data_get_by_type (const struct - GNUNET_CONTAINER_MetaData *md, - enum EXTRACTOR_MetaType type); +GNUNET_CONTAINER_meta_data_get_by_type (const struct GNUNET_CONTAINER_MetaData *md, + enum EXTRACTOR_MetaType type); /** + * @ingroup metadata * Get the first matching MD entry of the given types. Caller is * responsible for freeing the return value. Also, only meta data * items that are strings (0-terminated) are returned by this @@ -335,11 +599,11 @@ GNUNET_CONTAINER_meta_data_get_by_type (const struct * otherwise client is responsible for freeing the value! */ char * -GNUNET_CONTAINER_meta_data_get_first_by_types (const struct - GNUNET_CONTAINER_MetaData - *md, ...); +GNUNET_CONTAINER_meta_data_get_first_by_types (const struct GNUNET_CONTAINER_MetaData *md, + ...); /** + * @ingroup metadata * Get a thumbnail from the meta-data (if present). Only matches meta * data with mime type "image" and binary format. * @@ -348,45 +612,33 @@ GNUNET_CONTAINER_meta_data_get_first_by_types (const struct * freed by the caller! * @return number of bytes in thumbnail, 0 if not available */ -size_t -GNUNET_CONTAINER_meta_data_get_thumbnail (const struct - GNUNET_CONTAINER_MetaData - *md, unsigned char **thumb); +size_t +GNUNET_CONTAINER_meta_data_get_thumbnail (const struct GNUNET_CONTAINER_MetaData *md, + unsigned char **thumb); -/** - * Extract meta-data from a file. - * - * @param md metadata to set - * @param filename name of file to inspect - * @param extractors plugins to use - * @return GNUNET_SYSERR on error, otherwise the number - * of meta-data items obtained - */ -int -GNUNET_CONTAINER_meta_data_extract_from_file (struct - GNUNET_CONTAINER_MetaData - *md, const char *filename, - struct EXTRACTOR_PluginList * - extractors); /** + * @ingroup metadata * Options for metadata serialization. */ enum GNUNET_CONTAINER_MetaDataSerializationOptions { /** + * @ingroup metadata * Serialize all of the data. */ GNUNET_CONTAINER_META_DATA_SERIALIZE_FULL = 0, /** + * @ingroup metadata * If not enough space is available, it is acceptable * to only serialize some of the metadata. */ GNUNET_CONTAINER_META_DATA_SERIALIZE_PART = 1, /** + * @ingroup metadata * Speed is of the essence, do not allow compression. */ GNUNET_CONTAINER_META_DATA_SERIALIZE_NO_COMPRESS = 2 @@ -394,6 +646,7 @@ enum GNUNET_CONTAINER_MetaDataSerializationOptions /** + * @ingroup metadata * Serialize meta-data to target. * * @param md metadata to serialize @@ -407,27 +660,26 @@ enum GNUNET_CONTAINER_MetaDataSerializationOptions * -1 on error (typically: not enough * space) */ -ssize_t GNUNET_CONTAINER_meta_data_serialize (const struct - GNUNET_CONTAINER_MetaData *md, - char **target, - size_t max, - enum - GNUNET_CONTAINER_MetaDataSerializationOptions - opt); +ssize_t +GNUNET_CONTAINER_meta_data_serialize (const struct GNUNET_CONTAINER_MetaData *md, + char **target, + size_t max, + enum GNUNET_CONTAINER_MetaDataSerializationOptions opt); /** + * @ingroup metadata * Get the size of the full meta-data in serialized form. * * @param md metadata to inspect * @return number of bytes needed for serialization, -1 on error */ -ssize_t GNUNET_CONTAINER_meta_data_get_serialized_size (const struct - GNUNET_CONTAINER_MetaData - *md); +ssize_t +GNUNET_CONTAINER_meta_data_get_serialized_size (const struct GNUNET_CONTAINER_MetaData *md); /** + * @ingroup metadata * Deserialize meta-data. Initializes md. * * @param input serialized meta-data. @@ -435,37 +687,35 @@ ssize_t GNUNET_CONTAINER_meta_data_get_serialized_size (const struct * @return MD on success, NULL on error (i.e. * bad format) */ -struct GNUNET_CONTAINER_MetaData - *GNUNET_CONTAINER_meta_data_deserialize (const char *input, - size_t size); - -/** - * Does the meta-data claim that this is a directory? - * Checks if the mime-type is that of a GNUnet directory. - * - * @param md metadata to inspect - * @return GNUNET_YES if it is, GNUNET_NO if it is not, GNUNET_SYSERR if - * we have no mime-type information (treat as 'GNUNET_NO') - */ -int GNUNET_CONTAINER_meta_data_test_for_directory (const struct - GNUNET_CONTAINER_MetaData - *md); +struct GNUNET_CONTAINER_MetaData * +GNUNET_CONTAINER_meta_data_deserialize (const char *input, + size_t size); /* ******************************* HashMap **************************** */ /** + * @ingroup hashmap * Opaque handle for a HashMap. */ struct GNUNET_CONTAINER_MultiHashMap; /** + * @ingroup hashmap + * Opaque handle to an iterator over + * a multihashmap. + */ +struct GNUNET_CONTAINER_MultiHashMapIterator; + +/** + * @ingroup hashmap * Options for storing values in the HashMap. */ enum GNUNET_CONTAINER_MultiHashMapOption { /** + * @ingroup hashmap * If a value with the given key exists, replace it. Note that the * old value would NOT be freed by replace (the application has to * make sure that this happens if required). @@ -473,63 +723,82 @@ enum GNUNET_CONTAINER_MultiHashMapOption GNUNET_CONTAINER_MULTIHASHMAPOPTION_REPLACE, /** + * @ingroup hashmap * Allow multiple values with the same key. */ GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE, /** + * @ingroup hashmap * There must only be one value per key; storing a value should fail * if a value under the same key already exists. */ GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY, /** - * There must only be one value per key, but don't bother checking - * if a value already exists (faster than UNIQUE_ONLY; implemented - * just like MULTIPLE but this option documents better what is - * intended if UNIQUE is what is desired). + * @ingroup hashmap There must only be one value per key, but don't + * bother checking if a value already exists (faster than + * #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY; implemented + * just like #GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE but this + * option documents better what is intended if + * #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY is what is + * desired). */ GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST }; /** + * @ingroup hashmap * Iterator over hash map entries. * * @param cls closure * @param key current key code * @param value value in the hash map - * @return GNUNET_YES if we should continue to + * @return #GNUNET_YES if we should continue to * iterate, - * GNUNET_NO if not. + * #GNUNET_NO if not. */ -typedef int (*GNUNET_CONTAINER_HashMapIterator) (void *cls, - const GNUNET_HashCode * key, - void *value); +typedef int +(*GNUNET_CONTAINER_HashMapIterator) (void *cls, + const struct GNUNET_HashCode *key, + void *value); /** + * @ingroup hashmap * Create a multi hash map. * * @param len initial size (map will grow as needed) + * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default; + * #GNUNET_YES means that on 'put', the 'key' does not have + * to be copied as the destination of the pointer is + * guaranteed to be life as long as the value is stored in + * the hashmap. This can significantly reduce memory + * consumption, but of course is also a recipie for + * heap corruption if the assumption is not true. Only + * use this if (1) memory use is important in this case and + * (2) you have triple-checked that the invariant holds * @return NULL on error */ -struct GNUNET_CONTAINER_MultiHashMap - *GNUNET_CONTAINER_multihashmap_create (unsigned int len); +struct GNUNET_CONTAINER_MultiHashMap * +GNUNET_CONTAINER_multihashmap_create (unsigned int len, + int do_not_copy_keys); /** + * @ingroup hashmap * Destroy a hash map. Will not free any values * stored in the hash map! * * @param map the map */ -void GNUNET_CONTAINER_multihashmap_destroy (struct - GNUNET_CONTAINER_MultiHashMap - *map); +void +GNUNET_CONTAINER_multihashmap_destroy (struct GNUNET_CONTAINER_MultiHashMap *map); /** + * @ingroup hashmap * Given a key find a value in the map matching the key. * * @param map the map @@ -539,12 +808,13 @@ void GNUNET_CONTAINER_multihashmap_destroy (struct * happen to be NULL; use "contains" to test for * key-value pairs with value NULL */ -void *GNUNET_CONTAINER_multihashmap_get (const struct - GNUNET_CONTAINER_MultiHashMap *map, - const GNUNET_HashCode * key); +void * +GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap *map, + const struct GNUNET_HashCode *key); /** + * @ingroup hashmap * Remove the given key-value pair from the map. Note that if the * key-value pair is in the map multiple times, only one of the pairs * will be removed. @@ -552,14 +822,16 @@ void *GNUNET_CONTAINER_multihashmap_get (const struct * @param map the map * @param key key of the key-value pair * @param value value of the key-value pair - * @return GNUNET_YES on success, GNUNET_NO if the key-value pair + * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair * is not in the map */ -int GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap - *map, const GNUNET_HashCode * key, - void *value); +int +GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map, + const struct GNUNET_HashCode *key, + const void *value); /** + * @ingroup hashmap * Remove all entries for the given key from the map. * Note that the values would not be "freed". * @@ -567,507 +839,1501 @@ int GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap * @param key identifies values to be removed * @return number of values removed */ -int GNUNET_CONTAINER_multihashmap_remove_all (struct - GNUNET_CONTAINER_MultiHashMap - *map, - const GNUNET_HashCode * key); +int +GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap *map, + const struct GNUNET_HashCode *key); + + +/** + * @ingroup hashmap + * Remove all entries from the map. + * Note that the values would not be "freed". + * + * @param map the map + * @return number of values removed + */ +unsigned int +GNUNET_CONTAINER_multihashmap_clear (struct GNUNET_CONTAINER_MultiHashMap *map); /** + * @ingroup hashmap * Check if the map contains any value under the given * key (including values that are NULL). * * @param map the map * @param key the key to test if a value exists for it - * @return GNUNET_YES if such a value exists, - * GNUNET_NO if not + * @return #GNUNET_YES if such a value exists, + * #GNUNET_NO if not + */ +int +GNUNET_CONTAINER_multihashmap_contains (const struct GNUNET_CONTAINER_MultiHashMap *map, + const struct GNUNET_HashCode * key); + + +/** + * @ingroup hashmap + * Check if the map contains the given value under the given + * key. + * + * @param map the map + * @param key the key to test if a value exists for it + * @param value value to test for + * @return #GNUNET_YES if such a value exists, + * #GNUNET_NO if not */ -int GNUNET_CONTAINER_multihashmap_contains (const struct - GNUNET_CONTAINER_MultiHashMap - *map, - const GNUNET_HashCode * key); +int +GNUNET_CONTAINER_multihashmap_contains_value (const struct GNUNET_CONTAINER_MultiHashMap *map, + const struct GNUNET_HashCode *key, + const void *value); /** + * @ingroup hashmap * Store a key-value pair in the map. * * @param map the map * @param key key to use * @param value value to use * @param opt options for put - * @return GNUNET_OK on success, - * GNUNET_NO if a value was replaced (with REPLACE) - * GNUNET_SYSERR if UNIQUE_ONLY was the option and the + * @return #GNUNET_OK on success, + * #GNUNET_NO if a value was replaced (with REPLACE) + * #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the * value already exists */ -int GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap - *map, const GNUNET_HashCode * key, - void *value, - enum - GNUNET_CONTAINER_MultiHashMapOption - opt); +int +GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map, + const struct GNUNET_HashCode *key, + void *value, + enum GNUNET_CONTAINER_MultiHashMapOption + opt); /** + * @ingroup hashmap * Get the number of key-value pairs in the map. * * @param map the map * @return the number of key value pairs */ -unsigned int GNUNET_CONTAINER_multihashmap_size (const struct - GNUNET_CONTAINER_MultiHashMap - *map); +unsigned int +GNUNET_CONTAINER_multihashmap_size (const struct GNUNET_CONTAINER_MultiHashMap *map); /** + * @ingroup hashmap * Iterate over all entries in the map. * * @param map the map * @param it function to call on each entry - * @param it_cls extra argument to it + * @param it_cls extra argument to @a it * @return the number of key value pairs processed, - * GNUNET_SYSERR if it aborted iteration + * #GNUNET_SYSERR if it aborted iteration */ -int GNUNET_CONTAINER_multihashmap_iterate (const struct - GNUNET_CONTAINER_MultiHashMap *map, - GNUNET_CONTAINER_HashMapIterator - it, void *it_cls); +int +GNUNET_CONTAINER_multihashmap_iterate (const struct GNUNET_CONTAINER_MultiHashMap *map, + GNUNET_CONTAINER_HashMapIterator it, + void *it_cls); /** - * Iterate over all entries in the map that match a particular key. + * @ingroup hashmap + * Create an iterator for a multihashmap. + * The iterator can be used to retrieve all the elements in the multihashmap + * one by one, without having to handle all elements at once (in contrast to + * #GNUNET_CONTAINER_multihashmap_iterate). Note that the iterator can not be + * used anymore if elements have been removed from 'map' after the creation of + * the iterator, or 'map' has been destroyed. Adding elements to 'map' may + * result in skipped or repeated elements. * - * @param map the map - * @param key key that the entries must correspond to - * @param it function to call on each entry - * @param it_cls extra argument to it - * @return the number of key value pairs processed, - * GNUNET_SYSERR if it aborted iteration + * @param map the map to create an iterator for + * @return an iterator over the given multihashmap @a map */ -int GNUNET_CONTAINER_multihashmap_get_multiple (const struct - GNUNET_CONTAINER_MultiHashMap - *map, - const GNUNET_HashCode * key, - GNUNET_CONTAINER_HashMapIterator - it, void *it_cls); - +struct GNUNET_CONTAINER_MultiHashMapIterator * +GNUNET_CONTAINER_multihashmap_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap *map); -/* ******************** doubly-linked list *************** */ /** - * Insert an element at the head of a DLL. Assumes that head, tail and - * element are structs with prev and next fields. + * @ingroup hashmap + * Retrieve the next element from the hash map at the iterator's + * position. If there are no elements left, #GNUNET_NO is returned, + * and @a key and @a value are not modified. This operation is only + * allowed if no elements have been removed from the multihashmap + * since the creation of @a iter, and the map has not been destroyed. + * Adding elements may result in repeating or skipping elements. * - * @param head pointer to the head of the DLL - * @param tail pointer to the tail of the DLL - * @param element element to insert + * @param iter the iterator to get the next element from + * @param key pointer to store the key in, can be NULL + * @param value pointer to store the value in, can be NULL + * @return #GNUNET_YES we returned an element, + * #GNUNET_NO if we are out of elements */ -#define GNUNET_CONTAINER_DLL_insert(head,tail,element) do { \ - (element)->next = (head); \ - (element)->prev = NULL; \ - if ((tail) == NULL) \ - (tail) = element; \ - else \ - (head)->prev = element; \ - (head) = (element); } while (0) +int +GNUNET_CONTAINER_multihashmap_iterator_next (struct GNUNET_CONTAINER_MultiHashMapIterator *iter, + struct GNUNET_HashCode *key, + const void **value); + /** - * Insert an element into a DLL after the given other element. Insert - * at the head if the other element is NULL. + * @ingroup hashmap + * Destroy a multihashmap iterator. * - * @param head pointer to the head of the DLL - * @param tail pointer to the tail of the DLL - * @param other prior element, NULL for insertion at head of DLL - * @param element element to insert + * @param iter the iterator to destroy */ -#define GNUNET_CONTAINER_DLL_insert_after(head,tail,other,element) do { \ - (element)->prev = (other); \ - if (NULL == other) \ - { \ - (element)->next = (head); \ - (head) = (element); \ - } \ - else \ - { \ - (element)->next = (other)->next; \ - (other)->next = (element); \ - } \ - if (NULL == (element)->next) \ - (tail) = (element); \ - else \ - (element)->next->prev = (element); } while (0) - - +void +GNUNET_CONTAINER_multihashmap_iterator_destroy (struct GNUNET_CONTAINER_MultiHashMapIterator *iter); /** - * Remove an element from a DLL. Assumes - * that head, tail and element are structs - * with prev and next fields. + * @ingroup hashmap + * Iterate over all entries in the map that match a particular key. * - * @param head pointer to the head of the DLL - * @param tail pointer to the tail of the DLL - * @param element element to remove + * @param map the map + * @param key key that the entries must correspond to + * @param it function to call on each entry + * @param it_cls extra argument to @a it + * @return the number of key value pairs processed, + * #GNUNET_SYSERR if it aborted iteration */ -#define GNUNET_CONTAINER_DLL_remove(head,tail,element) do { \ - if ((element)->prev == NULL) \ - (head) = (element)->next; \ - else \ - (element)->prev->next = (element)->next; \ - if ((element)->next == NULL) \ - (tail) = (element)->prev; \ - else \ - (element)->next->prev = (element)->prev; } while (0) - - - -/* ******************** Heap *************** */ +int +GNUNET_CONTAINER_multihashmap_get_multiple (const struct GNUNET_CONTAINER_MultiHashMap *map, + const struct GNUNET_HashCode *key, + GNUNET_CONTAINER_HashMapIterator it, + void *it_cls); /** - * Cost by which elements in a heap can be ordered. - */ -typedef uint64_t GNUNET_CONTAINER_HeapCostType; - - -/* - * Heap type, either max or min. Hopefully makes the - * implementation more useful. + * @ingroup hashmap + * Call @a it on a random value from the map, or not at all + * if the map is empty. Note that this function has linear + * complexity (in the size of the map). + * + * @param map the map + * @param it function to call on a random entry + * @param it_cls extra argument to @a it + * @return the number of key value pairs processed, zero or one. */ -enum GNUNET_CONTAINER_HeapOrder -{ - /** - * Heap with the maximum cost at the root. - */ - GNUNET_CONTAINER_HEAP_ORDER_MAX, +unsigned int +GNUNET_CONTAINER_multihashmap_get_random (const struct GNUNET_CONTAINER_MultiHashMap *map, + GNUNET_CONTAINER_HashMapIterator it, + void *it_cls); - /** - * Heap with the minimum cost at the root. - */ - GNUNET_CONTAINER_HEAP_ORDER_MIN -}; +/* ***************** Version of Multihashmap for peer identities ****************** */ /** - * Handle to a Heap. + * @ingroup hashmap + * Iterator over hash map entries. + * + * @param cls closure + * @param key current public key + * @param value value in the hash map + * @return #GNUNET_YES if we should continue to + * iterate, + * #GNUNET_NO if not. */ -struct GNUNET_CONTAINER_Heap; - +typedef int +(*GNUNET_CONTAINER_PeerMapIterator) (void *cls, + const struct GNUNET_PeerIdentity *key, + void *value); /** - * Handle to a node in a heap. + * Hash map from peer identities to values. */ -struct GNUNET_CONTAINER_HeapNode; +struct GNUNET_CONTAINER_MultiPeerMap; /** - * Create a new heap. + * @ingroup hashmap + * Create a multi peer map (hash map for public keys of peers). * - * @param order how should the heap be sorted? - * @return handle to the heap + * @param len initial size (map will grow as needed) + * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default; + * #GNUNET_YES means that on 'put', the 'key' does not have + * to be copied as the destination of the pointer is + * guaranteed to be life as long as the value is stored in + * the hashmap. This can significantly reduce memory + * consumption, but of course is also a recipie for + * heap corruption if the assumption is not true. Only + * use this if (1) memory use is important in this case and + * (2) you have triple-checked that the invariant holds + * @return NULL on error */ -struct GNUNET_CONTAINER_Heap * -GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order); +struct GNUNET_CONTAINER_MultiPeerMap * +GNUNET_CONTAINER_multipeermap_create (unsigned int len, + int do_not_copy_keys); /** - * Destroys the heap. Only call on a heap that - * is already empty. + * @ingroup hashmap + * Destroy a hash map. Will not free any values + * stored in the hash map! * - * @param heap heap to destroy + * @param map the map */ -void GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap); +void +GNUNET_CONTAINER_multipeermap_destroy (struct GNUNET_CONTAINER_MultiPeerMap *map); /** - * Get element stored at root of heap. + * @ingroup hashmap + * Given a key find a value in the map matching the key. * - * @param heap heap to inspect - * @return NULL if heap is empty + * @param map the map + * @param key what to look for + * @return NULL if no value was found; note that + * this is indistinguishable from values that just + * happen to be NULL; use "contains" to test for + * key-value pairs with value NULL */ void * -GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap); +GNUNET_CONTAINER_multipeermap_get (const struct GNUNET_CONTAINER_MultiPeerMap *map, + const struct GNUNET_PeerIdentity *key); /** - * Get the current size of the heap + * @ingroup hashmap + * Remove the given key-value pair from the map. Note that if the + * key-value pair is in the map multiple times, only one of the pairs + * will be removed. * - * @param heap the heap to get the size of - * @return number of elements stored + * @param map the map + * @param key key of the key-value pair + * @param value value of the key-value pair + * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair + * is not in the map */ -unsigned int -GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap); +int +GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map, + const struct GNUNET_PeerIdentity * key, + const void *value); + +/** + * @ingroup hashmap + * Remove all entries for the given key from the map. + * Note that the values would not be "freed". + * + * @param map the map + * @param key identifies values to be removed + * @return number of values removed + */ +int +GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap *map, + const struct GNUNET_PeerIdentity *key); /** - * Iterator for heap + * @ingroup hashmap + * Check if the map contains any value under the given + * key (including values that are NULL). * - * @param cls closure - * @param node internal node of the heap - * @param element value stored at the node - * @param cost cost associated with the node - * @return GNUNET_YES if we should continue to iterate, - * GNUNET_NO if not. + * @param map the map + * @param key the key to test if a value exists for it + * @return #GNUNET_YES if such a value exists, + * #GNUNET_NO if not */ -typedef int (*GNUNET_CONTAINER_HeapIterator) (void *cls, - struct GNUNET_CONTAINER_HeapNode *node, - void *element, - GNUNET_CONTAINER_HeapCostType cost); +int +GNUNET_CONTAINER_multipeermap_contains (const struct GNUNET_CONTAINER_MultiPeerMap *map, + const struct GNUNET_PeerIdentity *key); /** - * Iterate over all entries in the heap. + * @ingroup hashmap + * Check if the map contains the given value under the given + * key. * - * @param heap the heap - * @param iterator function to call on each entry - * @param iterator_cls closure for iterator + * @param map the map + * @param key the key to test if a value exists for it + * @param value value to test for + * @return #GNUNET_YES if such a value exists, + * #GNUNET_NO if not */ -void -GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap, - GNUNET_CONTAINER_HeapIterator iterator, - void *iterator_cls); +int +GNUNET_CONTAINER_multipeermap_contains_value (const struct GNUNET_CONTAINER_MultiPeerMap *map, + const struct GNUNET_PeerIdentity * key, + const void *value); + + +/** + * @ingroup hashmap + * Store a key-value pair in the map. + * + * @param map the map + * @param key key to use + * @param value value to use + * @param opt options for put + * @return #GNUNET_OK on success, + * #GNUNET_NO if a value was replaced (with REPLACE) + * #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the + * value already exists + */ +int +GNUNET_CONTAINER_multipeermap_put (struct GNUNET_CONTAINER_MultiPeerMap *map, + const struct GNUNET_PeerIdentity *key, + void *value, + enum GNUNET_CONTAINER_MultiHashMapOption opt); /** - * Return a *uniform* random element from the heap. Choose a random - * number between 0 and heap size and then walk directly to it. - * This cost can be between 0 and n, amortized cost of logN. + * @ingroup hashmap + * Get the number of key-value pairs in the map. * - * @param heap heap to choose random element from - * @param max how many nodes from the heap to choose from + * @param map the map + * @return the number of key value pairs + */ +unsigned int +GNUNET_CONTAINER_multipeermap_size (const struct GNUNET_CONTAINER_MultiPeerMap *map); + + +/** + * @ingroup hashmap + * Iterate over all entries in the map. * - * @return data stored at the chosen random node, - * NULL if the heap is empty. + * @param map the map + * @param it function to call on each entry + * @param it_cls extra argument to @a it + * @return the number of key value pairs processed, + * #GNUNET_SYSERR if it aborted iteration + */ +int +GNUNET_CONTAINER_multipeermap_iterate (const struct GNUNET_CONTAINER_MultiPeerMap *map, + GNUNET_CONTAINER_PeerMapIterator it, + void *it_cls); + + +struct GNUNET_CONTAINER_MultiPeerMapIterator; +/** + * @ingroup hashmap + * Create an iterator for a multihashmap. + * The iterator can be used to retrieve all the elements in the multihashmap + * one by one, without having to handle all elements at once (in contrast to + * #GNUNET_CONTAINER_multipeermap_iterate). Note that the iterator can not be + * used anymore if elements have been removed from @a map after the creation of + * the iterator, or 'map' has been destroyed. Adding elements to @a map may + * result in skipped or repeated elements. * + * @param map the map to create an iterator for + * @return an iterator over the given multihashmap @a map */ -void * -GNUNET_CONTAINER_heap_get_random (struct GNUNET_CONTAINER_Heap *heap, uint32_t max); +struct GNUNET_CONTAINER_MultiPeerMapIterator * +GNUNET_CONTAINER_multipeermap_iterator_create (const struct GNUNET_CONTAINER_MultiPeerMap *map); + /** - * Perform a random walk of the tree. The walk is biased - * towards elements closer to the root of the tree (since - * each walk starts at the root and ends at a random leaf). - * The heap internally tracks the current position of the - * walk. + * @ingroup hashmap + * Retrieve the next element from the hash map at the iterator's + * position. If there are no elements left, #GNUNET_NO is returned, + * and @a key and @a value are not modified. This operation is only + * allowed if no elements have been removed from the multihashmap + * since the creation of @a iter, and the map has not been destroyed. + * Adding elements may result in repeating or skipping elements. * - * @param heap heap to walk - * @return data stored at the next random node in the walk; - * NULL if the tree is empty. + * @param iter the iterator to get the next element from + * @param key pointer to store the key in, can be NULL + * @param value pointer to store the value in, can be NULL + * @return #GNUNET_YES we returned an element, + * #GNUNET_NO if we are out of elements */ -void * -GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap); +int +GNUNET_CONTAINER_multipeermap_iterator_next (struct GNUNET_CONTAINER_MultiPeerMapIterator *iter, + struct GNUNET_PeerIdentity *key, + const void **value); /** - * Inserts a new element into the heap. + * @ingroup hashmap + * Destroy a multipeermap iterator. * - * @param heap heap to modify - * @param element element to insert - * @param cost cost for the element - * @return node for the new element + * @param iter the iterator to destroy */ -struct GNUNET_CONTAINER_HeapNode * -GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, - void *element, - GNUNET_CONTAINER_HeapCostType cost); +void +GNUNET_CONTAINER_multipeermap_iterator_destroy (struct GNUNET_CONTAINER_MultiPeerMapIterator *iter); /** - * Remove root of the heap. + * @ingroup hashmap + * Iterate over all entries in the map that match a particular key. * - * @param heap heap to modify - * @return element data stored at the root node + * @param map the map + * @param key public key that the entries must correspond to + * @param it function to call on each entry + * @param it_cls extra argument to @a it + * @return the number of key value pairs processed, + * #GNUNET_SYSERR if it aborted iteration */ -void * -GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap); +int +GNUNET_CONTAINER_multipeermap_get_multiple (const struct GNUNET_CONTAINER_MultiPeerMap *map, + const struct GNUNET_PeerIdentity *key, + GNUNET_CONTAINER_PeerMapIterator it, + void *it_cls); /** - * Removes a node from the heap. - * - * @param heap heap to modify - * @param node node to remove - * @return element data stored at the node, NULL if heap is empty + * @ingroup hashmap + * Call @a it on a random value from the map, or not at all + * if the map is empty. Note that this function has linear + * complexity (in the size of the map). + * + * @param map the map + * @param it function to call on a random entry + * @param it_cls extra argument to @a it + * @return the number of key value pairs processed, zero or one. */ -void * -GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *heap, - struct GNUNET_CONTAINER_HeapNode *node); +unsigned int +GNUNET_CONTAINER_multipeermap_get_random (const struct GNUNET_CONTAINER_MultiPeerMap *map, + GNUNET_CONTAINER_PeerMapIterator it, + void *it_cls); +/* ***************** Version of Multihashmap for short hashes ****************** */ + /** - * Updates the cost of any node in the tree + * @ingroup hashmap + * Iterator over hash map entries. * - * @param heap heap to modify - * @param node node for which the cost is to be changed - * @param new_cost new cost for the node + * @param cls closure + * @param key current public key + * @param value value in the hash map + * @return #GNUNET_YES if we should continue to + * iterate, + * #GNUNET_NO if not. + */ +typedef int +(*GNUNET_CONTAINER_ShortmapIterator) (void *cls, + const struct GNUNET_ShortHashCode *key, + void *value); + + +/** + * Hash map from peer identities to values. + */ +struct GNUNET_CONTAINER_MultiShortmap; + + +/** + * @ingroup hashmap + * Create a multi peer map (hash map for public keys of peers). + * + * @param len initial size (map will grow as needed) + * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default; + * #GNUNET_YES means that on 'put', the 'key' does not have + * to be copied as the destination of the pointer is + * guaranteed to be life as long as the value is stored in + * the hashmap. This can significantly reduce memory + * consumption, but of course is also a recipie for + * heap corruption if the assumption is not true. Only + * use this if (1) memory use is important in this case and + * (2) you have triple-checked that the invariant holds + * @return NULL on error + */ +struct GNUNET_CONTAINER_MultiShortmap * +GNUNET_CONTAINER_multishortmap_create (unsigned int len, + int do_not_copy_keys); + + +/** + * @ingroup hashmap + * Destroy a hash map. Will not free any values + * stored in the hash map! + * + * @param map the map */ void -GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap, - struct GNUNET_CONTAINER_HeapNode *node, - GNUNET_CONTAINER_HeapCostType new_cost); +GNUNET_CONTAINER_multishortmap_destroy (struct GNUNET_CONTAINER_MultiShortmap *map); + + +/** + * @ingroup hashmap + * Given a key find a value in the map matching the key. + * + * @param map the map + * @param key what to look for + * @return NULL if no value was found; note that + * this is indistinguishable from values that just + * happen to be NULL; use "contains" to test for + * key-value pairs with value NULL + */ +void * +GNUNET_CONTAINER_multishortmap_get (const struct GNUNET_CONTAINER_MultiShortmap *map, + const struct GNUNET_ShortHashCode *key); -/* ******************** Singly linked list *************** */ +/** + * @ingroup hashmap + * Remove the given key-value pair from the map. Note that if the + * key-value pair is in the map multiple times, only one of the pairs + * will be removed. + * + * @param map the map + * @param key key of the key-value pair + * @param value value of the key-value pair + * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair + * is not in the map + */ +int +GNUNET_CONTAINER_multishortmap_remove (struct GNUNET_CONTAINER_MultiShortmap *map, + const struct GNUNET_ShortHashCode * key, + const void *value); /** - * Possible ways for how data stored in the linked list - * might be allocated. - */ -enum GNUNET_CONTAINER_SListDisposition - { - /** - * Single-linked list must copy the buffer. - */ - GNUNET_CONTAINER_SLIST_DISPOSITION_TRANSIENT = 0, + * @ingroup hashmap + * Remove all entries for the given key from the map. + * Note that the values would not be "freed". + * + * @param map the map + * @param key identifies values to be removed + * @return number of values removed + */ +int +GNUNET_CONTAINER_multishortmap_remove_all (struct GNUNET_CONTAINER_MultiShortmap *map, + const struct GNUNET_ShortHashCode *key); - /** - * Data is static, no need to copy or free. - */ - GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC = 2, - /** - * Data is dynamic, do not copy but free when done. - */ - GNUNET_CONTAINER_SLIST_DISPOSITION_DYNAMIC = 4 - }; +/** + * @ingroup hashmap + * Check if the map contains any value under the given + * key (including values that are NULL). + * + * @param map the map + * @param key the key to test if a value exists for it + * @return #GNUNET_YES if such a value exists, + * #GNUNET_NO if not + */ +int +GNUNET_CONTAINER_multishortmap_contains (const struct GNUNET_CONTAINER_MultiShortmap *map, + const struct GNUNET_ShortHashCode *key); + +/** + * @ingroup hashmap + * Check if the map contains the given value under the given + * key. + * + * @param map the map + * @param key the key to test if a value exists for it + * @param value value to test for + * @return #GNUNET_YES if such a value exists, + * #GNUNET_NO if not + */ +int +GNUNET_CONTAINER_multishortmap_contains_value (const struct GNUNET_CONTAINER_MultiShortmap *map, + const struct GNUNET_ShortHashCode * key, + const void *value); /** - * Handle to a singly linked list + * @ingroup hashmap + * Store a key-value pair in the map. + * + * @param map the map + * @param key key to use + * @param value value to use + * @param opt options for put + * @return #GNUNET_OK on success, + * #GNUNET_NO if a value was replaced (with REPLACE) + * #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the + * value already exists */ -struct GNUNET_CONTAINER_SList; +int +GNUNET_CONTAINER_multishortmap_put (struct GNUNET_CONTAINER_MultiShortmap *map, + const struct GNUNET_ShortHashCode *key, + void *value, + enum GNUNET_CONTAINER_MultiHashMapOption opt); + /** - * Handle to a singly linked list iterator + * @ingroup hashmap + * Get the number of key-value pairs in the map. + * + * @param map the map + * @return the number of key value pairs */ -struct GNUNET_CONTAINER_SList_Iterator; +unsigned int +GNUNET_CONTAINER_multishortmap_size (const struct GNUNET_CONTAINER_MultiShortmap *map); /** - * Add a new element to the list - * @param l list - * @param disp memory disposition - * @param buf payload buffer - * @param len length of the buffer + * @ingroup hashmap + * Iterate over all entries in the map. + * + * @param map the map + * @param it function to call on each entry + * @param it_cls extra argument to @a it + * @return the number of key value pairs processed, + * #GNUNET_SYSERR if it aborted iteration */ -void GNUNET_CONTAINER_slist_add (struct GNUNET_CONTAINER_SList *l, - enum GNUNET_CONTAINER_SListDisposition disp, - const void *buf, size_t len); +int +GNUNET_CONTAINER_multishortmap_iterate (const struct GNUNET_CONTAINER_MultiShortmap *map, + GNUNET_CONTAINER_ShortmapIterator it, + void *it_cls); + + +struct GNUNET_CONTAINER_MultiShortmapIterator; /** - * Append a singly linked list to another - * @param dst list to append to - * @param src source + * @ingroup hashmap + * Create an iterator for a multihashmap. + * The iterator can be used to retrieve all the elements in the multihashmap + * one by one, without having to handle all elements at once (in contrast to + * #GNUNET_CONTAINER_multishortmap_iterate). Note that the iterator can not be + * used anymore if elements have been removed from @a map after the creation of + * the iterator, or 'map' has been destroyed. Adding elements to @a map may + * result in skipped or repeated elements. + * + * @param map the map to create an iterator for + * @return an iterator over the given multihashmap @a map */ -void -GNUNET_CONTAINER_slist_append (struct GNUNET_CONTAINER_SList *dst, struct GNUNET_CONTAINER_SList *src); +struct GNUNET_CONTAINER_MultiShortmapIterator * +GNUNET_CONTAINER_multishortmap_iterator_create (const struct GNUNET_CONTAINER_MultiShortmap *map); /** - * Create a new singly linked list - * @return the new list + * @ingroup hashmap + * Retrieve the next element from the hash map at the iterator's + * position. If there are no elements left, #GNUNET_NO is returned, + * and @a key and @a value are not modified. This operation is only + * allowed if no elements have been removed from the multihashmap + * since the creation of @a iter, and the map has not been destroyed. + * Adding elements may result in repeating or skipping elements. + * + * @param iter the iterator to get the next element from + * @param key pointer to store the key in, can be NULL + * @param value pointer to store the value in, can be NULL + * @return #GNUNET_YES we returned an element, + * #GNUNET_NO if we are out of elements */ -struct GNUNET_CONTAINER_SList *GNUNET_CONTAINER_slist_create (void); +int +GNUNET_CONTAINER_multishortmap_iterator_next (struct GNUNET_CONTAINER_MultiShortmapIterator *iter, + struct GNUNET_ShortHashCode *key, + const void **value); /** - * Destroy a singly linked list - * @param l the list to be destroyed + * @ingroup hashmap + * Destroy a multishortmap iterator. + * + * @param iter the iterator to destroy */ -void GNUNET_CONTAINER_slist_destroy (struct GNUNET_CONTAINER_SList *l); +void +GNUNET_CONTAINER_multishortmap_iterator_destroy (struct GNUNET_CONTAINER_MultiShortmapIterator *iter); /** - * Return the beginning of a list + * @ingroup hashmap + * Iterate over all entries in the map that match a particular key. * - * @param l list - * @return iterator pointing to the beginning, free using "GNUNET_free" + * @param map the map + * @param key public key that the entries must correspond to + * @param it function to call on each entry + * @param it_cls extra argument to @a it + * @return the number of key value pairs processed, + * #GNUNET_SYSERR if it aborted iteration */ -struct GNUNET_CONTAINER_SList_Iterator * -GNUNET_CONTAINER_slist_begin(struct GNUNET_CONTAINER_SList *l); +int +GNUNET_CONTAINER_multishortmap_get_multiple (const struct GNUNET_CONTAINER_MultiShortmap *map, + const struct GNUNET_ShortHashCode *key, + GNUNET_CONTAINER_ShortmapIterator it, + void *it_cls); /** - * Clear a list + * @ingroup hashmap + * Call @a it on a random value from the map, or not at all + * if the map is empty. Note that this function has linear + * complexity (in the size of the map). * - * @param l list + * @param map the map + * @param it function to call on a random entry + * @param it_cls extra argument to @a it + * @return the number of key value pairs processed, zero or one. */ -void GNUNET_CONTAINER_slist_clear (struct GNUNET_CONTAINER_SList *l); +unsigned int +GNUNET_CONTAINER_multishortmap_get_random (const struct GNUNET_CONTAINER_MultiShortmap *map, + GNUNET_CONTAINER_ShortmapIterator it, + void *it_cls); +/* Version of multihashmap with 32 bit keys */ + /** - * Check if a list contains a certain element - * @param l list - * @param buf payload buffer to find - * @param len length of the payload (number of bytes in buf) + * @ingroup hashmap + * Opaque handle for the 32-bit key HashMap. */ -int GNUNET_CONTAINER_slist_contains (const struct GNUNET_CONTAINER_SList *l, const void *buf, size_t len); +struct GNUNET_CONTAINER_MultiHashMap32; /** - * Count the elements of a list - * @param l list - * @return number of elements in the list + * @ingroup hashmap + * Opaque handle to an iterator over + * a 32-bit key multihashmap. */ -int GNUNET_CONTAINER_slist_count (const struct GNUNET_CONTAINER_SList *l); +struct GNUNET_CONTAINER_MultiHashMap32Iterator; /** - * Remove an element from the list - * @param i iterator that points to the element to be removed + * @ingroup hashmap + * Iterator over hash map entries. + * + * @param cls closure + * @param key current key code + * @param value value in the hash map + * @return #GNUNET_YES if we should continue to + * iterate, + * #GNUNET_NO if not. */ -void GNUNET_CONTAINER_slist_erase (struct GNUNET_CONTAINER_SList_Iterator *i); +typedef int (*GNUNET_CONTAINER_HashMapIterator32) (void *cls, + uint32_t key, + void *value); /** - * Insert an element into a list at a specific position - * @param before where to insert the new element - * @param disp memory disposition - * @param buf payload buffer - * @param len length of the payload + * @ingroup hashmap + * Create a 32-bit key multi hash map. + * + * @param len initial size (map will grow as needed) + * @return NULL on error */ -void GNUNET_CONTAINER_slist_insert (struct GNUNET_CONTAINER_SList_Iterator *before, - enum GNUNET_CONTAINER_SListDisposition disp, - const void *buf, - size_t len); +struct GNUNET_CONTAINER_MultiHashMap32 * +GNUNET_CONTAINER_multihashmap32_create (unsigned int len); /** - * Advance an iterator to the next element - * @param i iterator - * @return GNUNET_YES on success, GNUNET_NO if the end has been reached + * @ingroup hashmap + * Destroy a 32-bit key hash map. Will not free any values + * stored in the hash map! + * + * @param map the map */ -int GNUNET_CONTAINER_slist_next (struct GNUNET_CONTAINER_SList_Iterator *i); +void +GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32 + *map); /** - * Check if an iterator points beyond the end of a list - * @param i iterator - * @return GNUNET_YES if the end has been reached, GNUNET_NO if the iterator - * points to a valid element + * @ingroup hashmap + * Get the number of key-value pairs in the map. + * + * @param map the map + * @return the number of key value pairs */ -int GNUNET_CONTAINER_slist_end (struct GNUNET_CONTAINER_SList_Iterator *i); +unsigned int +GNUNET_CONTAINER_multihashmap32_size (const struct + GNUNET_CONTAINER_MultiHashMap32 *map); /** - * Retrieve the element at a specific position in a list + * @ingroup hashmap + * Given a key find a value in the map matching the key. * - * @param i iterator - * @param len set to the payload length - * @return payload + * @param map the map + * @param key what to look for + * @return NULL if no value was found; note that + * this is indistinguishable from values that just + * happen to be NULL; use "contains" to test for + * key-value pairs with value NULL */ -const void * -GNUNET_CONTAINER_slist_get (const struct GNUNET_CONTAINER_SList_Iterator *i, - size_t *len); +void * +GNUNET_CONTAINER_multihashmap32_get (const struct + GNUNET_CONTAINER_MultiHashMap32 *map, + uint32_t key); /** - * Release an iterator - * @param i iterator + * @ingroup hashmap + * Iterate over all entries in the map. + * + * @param map the map + * @param it function to call on each entry + * @param it_cls extra argument to @a it + * @return the number of key value pairs processed, + * #GNUNET_SYSERR if it aborted iteration */ -void GNUNET_CONTAINER_slist_iter_destroy (struct GNUNET_CONTAINER_SList_Iterator *i); +int +GNUNET_CONTAINER_multihashmap32_iterate (const struct + GNUNET_CONTAINER_MultiHashMap32 *map, + GNUNET_CONTAINER_HashMapIterator32 it, + void *it_cls); + + +/** + * @ingroup hashmap + * Remove the given key-value pair from the map. Note that if the + * key-value pair is in the map multiple times, only one of the pairs + * will be removed. + * + * @param map the map + * @param key key of the key-value pair + * @param value value of the key-value pair + * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair + * is not in the map + */ +int +GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 *map, + uint32_t key, + const void *value); + + +/** + * @ingroup hashmap + * Remove all entries for the given key from the map. + * Note that the values would not be "freed". + * + * @param map the map + * @param key identifies values to be removed + * @return number of values removed + */ +int +GNUNET_CONTAINER_multihashmap32_remove_all (struct GNUNET_CONTAINER_MultiHashMap32 *map, + uint32_t key); + + +/** + * @ingroup hashmap + * Check if the map contains any value under the given + * key (including values that are NULL). + * + * @param map the map + * @param key the key to test if a value exists for it + * @return #GNUNET_YES if such a value exists, + * #GNUNET_NO if not + */ +int +GNUNET_CONTAINER_multihashmap32_contains (const struct GNUNET_CONTAINER_MultiHashMap32 *map, + uint32_t key); + + +/** + * @ingroup hashmap + * Check if the map contains the given value under the given + * key. + * + * @param map the map + * @param key the key to test if a value exists for it + * @param value value to test for + * @return #GNUNET_YES if such a value exists, + * #GNUNET_NO if not + */ +int +GNUNET_CONTAINER_multihashmap32_contains_value (const struct GNUNET_CONTAINER_MultiHashMap32 *map, + uint32_t key, + const void *value); + + +/** + * @ingroup hashmap + * Store a key-value pair in the map. + * + * @param map the map + * @param key key to use + * @param value value to use + * @param opt options for put + * @return #GNUNET_OK on success, + * #GNUNET_NO if a value was replaced (with REPLACE) + * #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the + * value already exists + */ +int +GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32 *map, + uint32_t key, + void *value, + enum GNUNET_CONTAINER_MultiHashMapOption opt); + + +/** + * @ingroup hashmap + * Iterate over all entries in the map that match a particular key. + * + * @param map the map + * @param key key that the entries must correspond to + * @param it function to call on each entry + * @param it_cls extra argument to @a it + * @return the number of key value pairs processed, + * #GNUNET_SYSERR if it aborted iteration + */ +int +GNUNET_CONTAINER_multihashmap32_get_multiple (const struct GNUNET_CONTAINER_MultiHashMap32 *map, + uint32_t key, + GNUNET_CONTAINER_HashMapIterator32 it, + void *it_cls); + + +/** + * Create an iterator for a 32-bit multihashmap. + * The iterator can be used to retrieve all the elements in the multihashmap + * one by one, without having to handle all elements at once (in contrast to + * #GNUNET_CONTAINER_multihashmap32_iterate). Note that the iterator can not be + * used anymore if elements have been removed from 'map' after the creation of + * the iterator, or 'map' has been destroyed. Adding elements to 'map' may + * result in skipped or repeated elements. + * + * @param map the map to create an iterator for + * @return an iterator over the given multihashmap map + */ +struct GNUNET_CONTAINER_MultiHashMap32Iterator * +GNUNET_CONTAINER_multihashmap32_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap32 *map); + + +/** + * Retrieve the next element from the hash map at the iterator's position. + * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value' + * are not modified. + * This operation is only allowed if no elements have been removed from the + * multihashmap since the creation of 'iter', and the map has not been destroyed. + * Adding elements may result in repeating or skipping elements. + * + * @param iter the iterator to get the next element from + * @param key pointer to store the key in, can be NULL + * @param value pointer to store the value in, can be NULL + * @return #GNUNET_YES we returned an element, + * #GNUNET_NO if we are out of elements + */ +int +GNUNET_CONTAINER_multihashmap32_iterator_next (struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter, + uint32_t *key, + const void **value); + + +/** + * Destroy a 32-bit multihashmap iterator. + * + * @param iter the iterator to destroy + */ +void +GNUNET_CONTAINER_multihashmap32_iterator_destroy (struct GNUNET_CONTAINER_MultiHashMapIterator *iter); + + +/* ******************** doubly-linked list *************** */ +/* To avoid mistakes: head->prev == tail->next == NULL */ + +/** + * @ingroup dll + * Insert an element at the head of a DLL. Assumes that head, tail and + * element are structs with prev and next fields. + * + * @param head pointer to the head of the DLL + * @param tail pointer to the tail of the DLL + * @param element element to insert + */ +#define GNUNET_CONTAINER_DLL_insert(head,tail,element) do { \ + GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \ + GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \ + (element)->next = (head); \ + (element)->prev = NULL; \ + if ((tail) == NULL) \ + (tail) = element; \ + else \ + (head)->prev = element; \ + (head) = (element); } while (0) + + +/** + * @ingroup dll + * Insert an element at the tail of a DLL. Assumes that head, tail and + * element are structs with prev and next fields. + * + * @param head pointer to the head of the DLL + * @param tail pointer to the tail of the DLL + * @param element element to insert + */ +#define GNUNET_CONTAINER_DLL_insert_tail(head,tail,element) do { \ + GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \ + GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \ + (element)->prev = (tail); \ + (element)->next = NULL; \ + if ((head) == NULL) \ + (head) = element; \ + else \ + (tail)->next = element; \ + (tail) = (element); } while (0) + + +/** + * @ingroup dll + * Insert an element into a DLL after the given other element. Insert + * at the head if the other element is NULL. + * + * @param head pointer to the head of the DLL + * @param tail pointer to the tail of the DLL + * @param other prior element, NULL for insertion at head of DLL + * @param element element to insert + */ +#define GNUNET_CONTAINER_DLL_insert_after(head,tail,other,element) do { \ + GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \ + GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \ + (element)->prev = (other); \ + if (NULL == other) \ + { \ + (element)->next = (head); \ + (head) = (element); \ + } \ + else \ + { \ + (element)->next = (other)->next; \ + (other)->next = (element); \ + } \ + if (NULL == (element)->next) \ + (tail) = (element); \ + else \ + (element)->next->prev = (element); } while (0) + + +/** + * @ingroup dll + * Insert an element into a DLL before the given other element. Insert + * at the tail if the other element is NULL. + * + * @param head pointer to the head of the DLL + * @param tail pointer to the tail of the DLL + * @param other prior element, NULL for insertion at head of DLL + * @param element element to insert + */ +#define GNUNET_CONTAINER_DLL_insert_before(head,tail,other,element) do { \ + GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \ + GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \ + (element)->next = (other); \ + if (NULL == other) \ + { \ + (element)->prev = (tail); \ + (tail) = (element); \ + } \ + else \ + { \ + (element)->prev = (other)->prev; \ + (other)->prev = (element); \ + } \ + if (NULL == (element)->prev) \ + (head) = (element); \ + else \ + (element)->prev->next = (element); } while (0) + + +/** + * @ingroup dll + * Remove an element from a DLL. Assumes that head, tail and + * element point to structs with prev and next fields. + * + * Using the head or tail pointer as the element + * argument does NOT work with this macro. + * Make sure to store head/tail in another pointer + * and use it to remove the head or tail of the list. + * + * @param head pointer to the head of the DLL + * @param tail pointer to the tail of the DLL + * @param element element to remove + */ +#define GNUNET_CONTAINER_DLL_remove(head,tail,element) do { \ + GNUNET_assert ( ( (element)->prev != NULL) || ((head) == (element))); \ + GNUNET_assert ( ( (element)->next != NULL) || ((tail) == (element))); \ + if ((element)->prev == NULL) \ + (head) = (element)->next; \ + else \ + (element)->prev->next = (element)->next; \ + if ((element)->next == NULL) \ + (tail) = (element)->prev; \ + else \ + (element)->next->prev = (element)->prev; \ + (element)->next = NULL; \ + (element)->prev = NULL; } while (0) + + +/* ************ Multi-DLL interface, allows DLL elements to be + in multiple lists at the same time *********************** */ + +/** + * @ingroup dll + * Insert an element at the head of a MDLL. Assumes that head, tail and + * element are structs with prev and next fields. + * + * @param mdll suffix name for the next and prev pointers in the element + * @param head pointer to the head of the MDLL + * @param tail pointer to the tail of the MDLL + * @param element element to insert + */ +#define GNUNET_CONTAINER_MDLL_insert(mdll,head,tail,element) do { \ + GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \ + GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \ + (element)->next_##mdll = (head); \ + (element)->prev_##mdll = NULL; \ + if ((tail) == NULL) \ + (tail) = element; \ + else \ + (head)->prev_##mdll = element; \ + (head) = (element); } while (0) + + +/** + * @ingroup dll + * Insert an element at the tail of a MDLL. Assumes that head, tail and + * element are structs with prev and next fields. + * + * @param mdll suffix name for the next and prev pointers in the element + * @param head pointer to the head of the MDLL + * @param tail pointer to the tail of the MDLL + * @param element element to insert + */ +#define GNUNET_CONTAINER_MDLL_insert_tail(mdll,head,tail,element) do { \ + GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \ + GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \ + (element)->prev_##mdll = (tail); \ + (element)->next_##mdll = NULL; \ + if ((head) == NULL) \ + (head) = element; \ + else \ + (tail)->next_##mdll = element; \ + (tail) = (element); } while (0) + + +/** + * @ingroup dll + * Insert an element into a MDLL after the given other element. Insert + * at the head if the other element is NULL. + * + * @param mdll suffix name for the next and prev pointers in the element + * @param head pointer to the head of the MDLL + * @param tail pointer to the tail of the MDLL + * @param other prior element, NULL for insertion at head of MDLL + * @param element element to insert + */ +#define GNUNET_CONTAINER_MDLL_insert_after(mdll,head,tail,other,element) do { \ + GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \ + GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \ + (element)->prev_##mdll = (other); \ + if (NULL == other) \ + { \ + (element)->next_##mdll = (head); \ + (head) = (element); \ + } \ + else \ + { \ + (element)->next_##mdll = (other)->next_##mdll; \ + (other)->next_##mdll = (element); \ + } \ + if (NULL == (element)->next_##mdll) \ + (tail) = (element); \ + else \ + (element)->next->prev_##mdll = (element); } while (0) + + +/** + * @ingroup dll + * Insert an element into a MDLL before the given other element. Insert + * at the tail if the other element is NULL. + * + * @param mdll suffix name for the next and prev pointers in the element + * @param head pointer to the head of the MDLL + * @param tail pointer to the tail of the MDLL + * @param other prior element, NULL for insertion at head of MDLL + * @param element element to insert + */ +#define GNUNET_CONTAINER_MDLL_insert_before(mdll,head,tail,other,element) do { \ + GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \ + GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \ + (element)->next_##mdll = (other); \ + if (NULL == other) \ + { \ + (element)->prev = (tail); \ + (tail) = (element); \ + } \ + else \ + { \ + (element)->prev_##mdll = (other)->prev_##mdll; \ + (other)->prev_##mdll = (element); \ + } \ + if (NULL == (element)->prev_##mdll) \ + (head) = (element); \ + else \ + (element)->prev_##mdll->next_##mdll = (element); } while (0) + + +/** + * @ingroup dll + * Remove an element from a MDLL. Assumes + * that head, tail and element are structs + * with prev and next fields. + * + * @param mdll suffix name for the next and prev pointers in the element + * @param head pointer to the head of the MDLL + * @param tail pointer to the tail of the MDLL + * @param element element to remove + */ +#define GNUNET_CONTAINER_MDLL_remove(mdll,head,tail,element) do { \ + GNUNET_assert ( ( (element)->prev_##mdll != NULL) || ((head) == (element))); \ + GNUNET_assert ( ( (element)->next_##mdll != NULL) || ((tail) == (element))); \ + if ((element)->prev_##mdll == NULL) \ + (head) = (element)->next_##mdll; \ + else \ + (element)->prev_##mdll->next_##mdll = (element)->next_##mdll; \ + if ((element)->next_##mdll == NULL) \ + (tail) = (element)->prev_##mdll; \ + else \ + (element)->next_##mdll->prev_##mdll = (element)->prev_##mdll; \ + (element)->next_##mdll = NULL; \ + (element)->prev_##mdll = NULL; } while (0) + + + +/** + * Insertion sort of @a element into DLL from @a head to @a tail + * sorted by @a comparator. + * + * @param TYPE element type of the elements, i.e. `struct ListElement` + * @param comparator function like memcmp() to compare elements; takes + * three arguments, the @a comparator_cls and two elements, + * returns an `int` (-1, 0 or 1) + * @param comparator_cls closure for @a comparator + * @param[in,out] head head of DLL + * @param[in,out] tail tail of DLL + * @param element element to insert + */ +#define GNUNET_CONTAINER_DLL_insert_sorted(TYPE,comparator,comparator_cls,head,tail,element) do { \ + if ( (NULL == head) || \ + (0 < comparator (comparator_cls, \ + element, \ + head)) ) \ + { \ + /* insert at head, element < head */ \ + GNUNET_CONTAINER_DLL_insert (head, \ + tail, \ + element); \ + } \ + else \ + { \ + TYPE *pos; \ + \ + for (pos = head; \ + NULL != pos; \ + pos = pos->next) \ + if (0 < \ + comparator (comparator_cls, \ + element, \ + pos)) \ + break; /* element < pos */ \ + if (NULL == pos) /* => element > tail */ \ + { \ + GNUNET_CONTAINER_DLL_insert_tail (head, \ + tail, \ + element); \ + } \ + else /* prev < element < pos */ \ + { \ + GNUNET_CONTAINER_DLL_insert_after (head, \ + tail, \ + pos->prev, \ + element); \ + } \ + } \ +} while (0) + + +/* ******************** Heap *************** */ + + +/** + * @ingroup heap + * Cost by which elements in a heap can be ordered. + */ +typedef uint64_t GNUNET_CONTAINER_HeapCostType; + + +/** + * @ingroup heap + * Heap type, either max or min. + */ +enum GNUNET_CONTAINER_HeapOrder +{ + /** + * @ingroup heap + * Heap with the maximum cost at the root. + */ + GNUNET_CONTAINER_HEAP_ORDER_MAX, + + /** + * @ingroup heap + * Heap with the minimum cost at the root. + */ + GNUNET_CONTAINER_HEAP_ORDER_MIN +}; + + +/** + * @ingroup heap + * Handle to a Heap. + */ +struct GNUNET_CONTAINER_Heap; + + +/** + * @ingroup heap + * Handle to a node in a heap. + */ +struct GNUNET_CONTAINER_HeapNode; + + +/** + * @ingroup heap + * Create a new heap. + * + * @param order how should the heap be sorted? + * @return handle to the heap + */ +struct GNUNET_CONTAINER_Heap * +GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order); + + +/** + * @ingroup heap + * Destroys the heap. Only call on a heap that + * is already empty. + * + * @param heap heap to destroy + */ +void +GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap); + + +/** + * @ingroup heap + * Get element stored at the root of @a heap. + * + * @param heap Heap to inspect. + * @return Element at the root, or NULL if heap is empty. + */ +void * +GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap); + + +/** + * Get @a element and @a cost stored at the root of @a heap. + * + * @param[in] heap Heap to inspect. + * @param[out] element Root element is returned here. + * @param[out] cost Cost of @a element is returned here. + * @return #GNUNET_YES if an element is returned, + * #GNUNET_NO if the heap is empty. + */ +int +GNUNET_CONTAINER_heap_peek2 (const struct GNUNET_CONTAINER_Heap *heap, + void **element, + GNUNET_CONTAINER_HeapCostType *cost); + + +/** + * @ingroup heap + * Get the current size of the heap + * + * @param heap the heap to get the size of + * @return number of elements stored + */ +unsigned int +GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap); + + +/** + * @ingroup heap + * Get the current cost of the node + * + * @param node the node to get the cost of + * @return cost of the node + */ +GNUNET_CONTAINER_HeapCostType +GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode *node); + + +/** + * @ingroup heap + * Iterator for heap + * + * @param cls closure + * @param node internal node of the heap + * @param element value stored at the node + * @param cost cost associated with the node + * @return #GNUNET_YES if we should continue to iterate, + * #GNUNET_NO if not. + */ +typedef int +(*GNUNET_CONTAINER_HeapIterator) (void *cls, + struct GNUNET_CONTAINER_HeapNode *node, + void *element, + GNUNET_CONTAINER_HeapCostType cost); + + +/** + * @ingroup heap + * Iterate over all entries in the heap. + * + * @param heap the heap + * @param iterator function to call on each entry + * @param iterator_cls closure for @a iterator + */ +void +GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap, + GNUNET_CONTAINER_HeapIterator iterator, + void *iterator_cls); + +/** + * @ingroup heap + * Perform a random walk of the tree. The walk is biased + * towards elements closer to the root of the tree (since + * each walk starts at the root and ends at a random leaf). + * The heap internally tracks the current position of the + * walk. + * + * @param heap heap to walk + * @return data stored at the next random node in the walk; + * NULL if the tree is empty. + */ +void * +GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap); + + +/** + * @ingroup heap + * Inserts a new element into the heap. + * + * @param heap heap to modify + * @param element element to insert + * @param cost cost for the element + * @return node for the new element + */ +struct GNUNET_CONTAINER_HeapNode * +GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, + void *element, + GNUNET_CONTAINER_HeapCostType cost); + + +/** + * @ingroup heap + * Remove root of the heap. + * + * @param heap heap to modify + * @return element data stored at the root node + */ +void * +GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap); + + +/** + * @ingroup heap + * Removes a node from the heap. + * + * @param node node to remove + * @return element data stored at the node, NULL if heap is empty + */ +void * +GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node); + + +/** + * @ingroup heap + * Updates the cost of any node in the tree + * + * @param node node for which the cost is to be changed + * @param new_cost new cost for the node + */ +void +GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_HeapNode *node, + GNUNET_CONTAINER_HeapCostType new_cost); #if 0 /* keep Emacsens' auto-indent happy */