X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=src%2Finclude%2Fgnunet_container_lib.h;h=c77d82fd37a6874c092dc4ae80e7fd27a789f7d6;hb=a67bd3630046d3a52195a13cbd4b4631c283d68d;hp=1ecf4f52ac0de36bcb5cfad3d54400f197ab52b7;hpb=7581e114280c0c33f375b5d3ba49508b82680755;p=oweals%2Fgnunet.git diff --git a/src/include/gnunet_container_lib.h b/src/include/gnunet_container_lib.h index 1ecf4f52a..c77d82fd3 100644 --- a/src/include/gnunet_container_lib.h +++ b/src/include/gnunet_container_lib.h @@ -1,6 +1,6 @@ /* This file is part of GNUnet. - Copyright (C) 2001-2013 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 @@ -14,20 +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 - * @defgroup hashmap multi hash-map - * @defgroup heap min- or max-heap with arbitrary element removal - * @defgroup bloomfilter Bloom filter (probabilistic set tests) - * @defgroup dll Doubly-linked list - * @defgroup metadata Meta data (GNU libextractor key-value pairs) + * + * @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 @@ -35,8 +49,141 @@ /* 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 @@ -857,7 +1004,8 @@ GNUNET_CONTAINER_multihashmap_get_multiple (const struct GNUNET_CONTAINER_MultiH /** * @ingroup hashmap * Call @a it on a random value from the map, or not at all - * if the map is empty. + * 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 @@ -889,7 +1037,12 @@ typedef int void *value); +/** + * Hash map from peer identities to values. + */ struct GNUNET_CONTAINER_MultiPeerMap; + + /** * @ingroup hashmap * Create a multi peer map (hash map for public keys of peers). @@ -1115,6 +1268,291 @@ GNUNET_CONTAINER_multipeermap_get_multiple (const struct GNUNET_CONTAINER_MultiP void *it_cls); +/** + * @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. + */ +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 ****************** */ + +/** + * @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. + */ +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_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); + + +/** + * @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); + +/** + * @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); + + +/** + * @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); + + +/** + * @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_multishortmap_put (struct GNUNET_CONTAINER_MultiShortmap *map, + const struct GNUNET_ShortHashCode *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_multishortmap_size (const struct GNUNET_CONTAINER_MultiShortmap *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 @a it + * @return the number of key value pairs processed, + * #GNUNET_SYSERR if it aborted iteration + */ +int +GNUNET_CONTAINER_multishortmap_iterate (const struct GNUNET_CONTAINER_MultiShortmap *map, + GNUNET_CONTAINER_ShortmapIterator it, + void *it_cls); + + +struct GNUNET_CONTAINER_MultiShortmapIterator; + + +/** + * @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 + */ +struct GNUNET_CONTAINER_MultiShortmapIterator * +GNUNET_CONTAINER_multishortmap_iterator_create (const struct GNUNET_CONTAINER_MultiShortmap *map); + + +/** + * @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 + */ +int +GNUNET_CONTAINER_multishortmap_iterator_next (struct GNUNET_CONTAINER_MultiShortmapIterator *iter, + struct GNUNET_ShortHashCode *key, + const void **value); + + +/** + * @ingroup hashmap + * Destroy a multishortmap iterator. + * + * @param iter the iterator to destroy + */ +void +GNUNET_CONTAINER_multishortmap_iterator_destroy (struct GNUNET_CONTAINER_MultiShortmapIterator *iter); + + +/** + * @ingroup hashmap + * Iterate over all entries in the map that match a particular key. + * + * @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 + */ +int +GNUNET_CONTAINER_multishortmap_get_multiple (const struct GNUNET_CONTAINER_MultiShortmap *map, + const struct GNUNET_ShortHashCode *key, + GNUNET_CONTAINER_ShortmapIterator it, + void *it_cls); + + +/** + * @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. + */ +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 */ @@ -1635,6 +2073,59 @@ GNUNET_CONTAINER_multihashmap32_iterator_destroy (struct GNUNET_CONTAINER_MultiH +/** + * 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 *************** */ @@ -1746,8 +2237,8 @@ GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap); * @return cost of the node */ GNUNET_CONTAINER_HeapCostType -GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode - *node); +GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode *node); + /** * @ingroup heap @@ -1760,11 +2251,11 @@ GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode * @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); +typedef int +(*GNUNET_CONTAINER_HeapIterator) (void *cls, + struct GNUNET_CONTAINER_HeapNode *node, + void *element, + GNUNET_CONTAINER_HeapCostType cost); /** @@ -1806,7 +2297,8 @@ GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap); * @return node for the new element */ struct GNUNET_CONTAINER_HeapNode * -GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, void *element, +GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, + void *element, GNUNET_CONTAINER_HeapCostType cost); @@ -1836,13 +2328,11 @@ GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node); * @ingroup heap * Updates the cost of any node in the tree * - * @param heap heap to modify * @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_Heap *heap, - struct GNUNET_CONTAINER_HeapNode *node, +GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_HeapNode *node, GNUNET_CONTAINER_HeapCostType new_cost);