2 This file is part of GNUnet.
3 (C) 2001, 2002, 2003, 2004, 2005, 2006, 2008 Christian Grothoff (and other contributing authors)
5 GNUnet is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 2, or (at your
8 option) any later version.
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
22 * @file include/gnunet_container_lib.h
23 * @brief container classes for GNUnet
25 * @author Christian Grothoff
29 #ifndef GNUNET_CONTAINER_LIB_H
30 #define GNUNET_CONTAINER_LIB_H
32 /* add error and config prototypes */
33 #include "gnunet_crypto_lib.h"
34 #include <extractor.h>
39 #if 0 /* keep Emacsens' auto-indent happy */
45 /* ******************* bloomfilter ***************** */
48 * @brief bloomfilter representation (opaque)
50 struct GNUNET_CONTAINER_BloomFilter;
53 * Iterator over HashCodes.
55 * @return GNUNET_YES if next was updated
56 * GNUNET_NO if there are no more entries
58 typedef int (*GNUNET_HashCodeIterator) (GNUNET_HashCode * next, void *arg);
61 * Load a bloom-filter from a file.
62 * @param filename the name of the file (or the prefix)
63 * @param size the size of the bloom-filter (number of
64 * bytes of storage space to use)
65 * @param k the number of GNUNET_CRYPTO_hash-functions to apply per
66 * element (number of bits set per element in the set)
67 * @return the bloomfilter
69 struct GNUNET_CONTAINER_BloomFilter *GNUNET_CONTAINER_bloomfilter_load (const
80 * Create a bloom filter from raw bits.
82 * @param data the raw bits in memory (maybe NULL,
83 * in which case all bits should be considered
85 * @param size the size of the bloom-filter (number of
86 * bytes of storage space to use); also size of data
87 * -- unless data is NULL. Must be a power of 2.
88 * @param k the number of GNUNET_CRYPTO_hash-functions to apply per
89 * element (number of bits set per element in the set)
90 * @return the bloomfilter
92 struct GNUNET_CONTAINER_BloomFilter *GNUNET_CONTAINER_bloomfilter_init (const
103 * Copy the raw data of this bloomfilter into
104 * the given data array.
106 * @param data where to write the data
107 * @param size the size of the given data array
108 * @return GNUNET_SYSERR if the data array of the wrong size
110 int GNUNET_CONTAINER_bloomfilter_get_raw_data (struct
111 GNUNET_CONTAINER_BloomFilter
116 * Test if an element is in the filter.
117 * @param e the element
118 * @param bf the filter
119 * @return GNUNET_YES if the element is in the filter, GNUNET_NO if not
121 int GNUNET_CONTAINER_bloomfilter_test (struct GNUNET_CONTAINER_BloomFilter
122 *bf, const GNUNET_HashCode * e);
125 * Add an element to the filter
126 * @param bf the filter
127 * @param e the element
129 void GNUNET_CONTAINER_bloomfilter_add (struct GNUNET_CONTAINER_BloomFilter
130 *bf, const GNUNET_HashCode * e);
133 * Remove an element from the filter.
134 * @param bf the filter
135 * @param e the element to remove
137 void GNUNET_CONTAINER_bloomfilter_remove (struct GNUNET_CONTAINER_BloomFilter
138 *bf, const GNUNET_HashCode * e);
141 * Free the space associcated with a filter
142 * in memory, flush to drive if needed (do not
143 * free the space on the drive)
144 * @param bf the filter
146 void GNUNET_CONTAINER_bloomfilter_free (struct GNUNET_CONTAINER_BloomFilter
150 * Reset a bloom filter to empty.
151 * @param bf the filter
153 void GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter
157 * Or the entries of the given raw data array with the
158 * data of the given bloom filter. Assumes that
159 * the size of the data array and the current filter
161 * @param bf the filter
163 int GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf,
164 const char *data, unsigned int size);
167 * Resize a bloom filter. Note that this operation
168 * is pretty costly. Essentially, the bloom filter
169 * needs to be completely re-build.
171 * @param bf the filter
172 * @param iterator an iterator over all elements stored in the BF
173 * @param iterator_arg argument to the iterator function
174 * @param size the new size for the filter
175 * @param k the new number of GNUNET_CRYPTO_hash-function to apply per element
177 void GNUNET_CONTAINER_bloomfilter_resize (struct GNUNET_CONTAINER_BloomFilter
179 GNUNET_HashCodeIterator iterator,
181 unsigned int size, unsigned int k);
183 /* ****************** metadata ******************* */
186 * Meta data to associate with a file, directory or namespace.
188 struct GNUNET_CONTAINER_MetaData;
191 * Iterator over meta data.
192 * @return GNUNET_OK to continue to iterate, GNUNET_SYSERR to abort
194 typedef int (*GNUNET_CONTAINER_MetaDataProcessor) (EXTRACTOR_KeywordType type,
199 * Create a fresh MetaData token.
201 struct GNUNET_CONTAINER_MetaData *GNUNET_CONTAINER_meta_data_create (void);
204 * Duplicate a MetaData token.
206 struct GNUNET_CONTAINER_MetaData *GNUNET_CONTAINER_meta_data_duplicate (const
208 GNUNET_CONTAINER_MetaData
214 void GNUNET_CONTAINER_meta_data_destroy (struct GNUNET_CONTAINER_MetaData
218 * Test if two MDs are equal.
220 int GNUNET_CONTAINER_meta_data_test_equal (const struct
221 GNUNET_CONTAINER_MetaData *md1,
223 GNUNET_CONTAINER_MetaData *md2);
228 * @return GNUNET_OK on success, GNUNET_SYSERR if this entry already exists
230 int GNUNET_CONTAINER_meta_data_insert (struct GNUNET_CONTAINER_MetaData *md,
231 EXTRACTOR_KeywordType type,
236 * @return GNUNET_OK on success, GNUNET_SYSERR if the item does not exist in md
238 int GNUNET_CONTAINER_meta_data_delete (struct GNUNET_CONTAINER_MetaData *md,
239 EXTRACTOR_KeywordType type,
243 * Add the current time as the publication date
246 void GNUNET_CONTAINER_meta_data_add_publication_date (struct
247 GNUNET_CONTAINER_MetaData
251 * Iterate over MD entries, excluding thumbnails.
253 * @return number of entries
255 int GNUNET_CONTAINER_meta_data_get_contents (const struct
256 GNUNET_CONTAINER_MetaData *md,
257 GNUNET_CONTAINER_MetaDataProcessor
258 iterator, void *closure);
261 * Get the first MD entry of the given type.
262 * @return NULL if we do not have any such entry,
263 * otherwise client is responsible for freeing the value!
265 char *GNUNET_CONTAINER_meta_data_get_by_type (const struct
266 GNUNET_CONTAINER_MetaData *md,
267 EXTRACTOR_KeywordType type);
270 * Get the first matching MD entry of the given types.
271 * @paarm ... -1-terminated list of types
272 * @return NULL if we do not have any such entry,
273 * otherwise client is responsible for freeing the value!
275 char *GNUNET_CONTAINER_meta_data_get_first_by_types (const struct
276 GNUNET_CONTAINER_MetaData
280 * Get a thumbnail from the meta-data (if present).
282 * @param thumb will be set to the thumbnail data. Must be
283 * freed by the caller!
284 * @return number of bytes in thumbnail, 0 if not available
286 size_t GNUNET_CONTAINER_meta_data_get_thumbnail (const struct
287 GNUNET_CONTAINER_MetaData
288 *md, unsigned char **thumb);
291 * Extract meta-data from a file.
293 * @return GNUNET_SYSERR on error, otherwise the number
294 * of meta-data items obtained
296 int GNUNET_CONTAINER_meta_data_extract_from_file (struct
297 GNUNET_CONTAINER_MetaData
298 *md, const char *filename,
299 EXTRACTOR_ExtractorList *
302 enum GNUNET_CONTAINER_MetaDataSerializationOptions
304 GNUNET_CONTAINER_META_DATA_SERIALIZE_FULL = GNUNET_NO,
305 GNUNET_CONTAINER_META_DATA_SERIALIZE_PART = GNUNET_YES,
306 GNUNET_CONTAINER_META_DATA_SERIALIZE_NO_COMPRESS = 2
312 * Serialize meta-data to target.
314 * @param size maximum number of bytes available
315 * @param opt is it ok to just write SOME of the
316 * meta-data to match the size constraint,
317 * possibly discarding some data?
318 * @return number of bytes written on success,
319 * GNUNET_SYSERR on error (typically: not enough
322 int GNUNET_CONTAINER_meta_data_serialize (const struct
323 GNUNET_CONTAINER_MetaData *md,
324 char *target, unsigned int size,
326 GNUNET_CONTAINER_MetaDataSerializationOptions
330 * Compute size of the meta-data in
332 * @param opt is it ok to just write SOME of the
333 * meta-data to match the size constraint,
334 * possibly discarding some data?
336 unsigned int GNUNET_CONTAINER_meta_data_get_serialized_size (const struct
337 GNUNET_CONTAINER_MetaData
340 GNUNET_CONTAINER_MetaDataSerializationOptions
344 * Deserialize meta-data. Initializes md.
345 * @param size number of bytes available
346 * @return MD on success, NULL on error (i.e.
349 struct GNUNET_CONTAINER_MetaData
350 *GNUNET_CONTAINER_meta_data_deserialize (const char *input,
354 * Does the meta-data claim that this is a directory?
355 * Checks if the mime-type is that of a GNUnet directory.
357 * @return GNUNET_YES if it is, GNUNET_NO if it is not, GNUNET_SYSERR if
358 * we have no mime-type information (treat as 'GNUNET_NO')
360 int GNUNET_CONTAINER_meta_data_test_for_directory (const struct
361 GNUNET_CONTAINER_MetaData
365 /* ******************************* HashMap **************************** */
368 * Opaque handle for a HashMap.
370 struct GNUNET_CONTAINER_MultiHashMap;
373 * Options for storing values in the HashMap.
375 enum GNUNET_CONTAINER_MultiHashMapOption
378 * If a value with the given key exists, replace it.
379 * Note that the old value would NOT be freed
380 * by replace (the application has to make sure that
381 * this happens if required).
383 GNUNET_CONTAINER_MULTIHASHMAPOPTION_REPLACE,
386 * Allow multiple values with the same key.
388 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE,
391 * There must only be one value per key; storing
392 * a value should fail if a value under the same
393 * key already exists.
395 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY,
398 * There must only be one value per key, but don't
399 * bother checking if a value already exists
400 * (faster than UNIQUE_ONLY; implemented just like
401 * MULTIPLE but this option documents better what
402 * is intended if UNIQUE is what is desired).
404 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST
408 * Iterator over HashCodes.
410 * @param key current key code
411 * @param value value in the hash map
412 * @param cls client-defined argument
413 * @return GNUNET_YES if we should continue to
417 typedef int (*GNUNET_CONTAINER_HashMapIterator) (const GNUNET_HashCode * key,
418 void *value, void *cls);
422 * Create a multi hash map.
425 * @param len initial size (map will grow as needed)
426 * @return NULL on error
428 struct GNUNET_CONTAINER_MultiHashMap
429 *GNUNET_CONTAINER_multihashmap_create (unsigned int len);
432 * Destroy a hash map. Will not free any values
433 * stored in the hash map!
437 void GNUNET_CONTAINER_multihashmap_destroy (struct
438 GNUNET_CONTAINER_MultiHashMap
442 * Given a key find a value in the
443 * map matching the key.
446 * @param key what to look for
447 * @return NULL if no value was found; note that
448 * this is indistinguishable from values that just
449 * happen to be NULL; use "contains" to test for
450 * key-value pairs with value NULL
452 void *GNUNET_CONTAINER_multihashmap_get (const struct
453 GNUNET_CONTAINER_MultiHashMap *map,
454 const GNUNET_HashCode * key);
457 * Remove the given key-value pair from the map.
458 * Note that if the key-value pair is in the map
459 * multiple times, only one of the pairs will be
463 * @param key key of the key-value pair
464 * @param value value of the key-value pair
465 * @return GNUNET_YES on success, GNUNET_NO if the key-value pair
468 int GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap
469 *map, const GNUNET_HashCode * key,
473 * Remove all entries for the given key from the map.
474 * Note that the values would not be "freed".
477 * @param key identifies values to be removed
478 * @return number of values removed
480 int GNUNET_CONTAINER_multihashmap_remove_all (struct
481 GNUNET_CONTAINER_MultiHashMap
483 const GNUNET_HashCode * key);
486 * Check if the map contains any value under the given
487 * key (including values that are NULL).
490 * @param key the key to test if a value exists for it
491 * @return GNUNET_YES if such a value exists,
494 int GNUNET_CONTAINER_multihashmap_contains (const struct
495 GNUNET_CONTAINER_MultiHashMap
497 const GNUNET_HashCode * key);
500 * Store a key-value pair in the map.
503 * @param key key to use
504 * @param value value to use
505 * @param opt options for put
506 * @return GNUNET_OK on success,
507 * GNUNET_NO if a value was replaced (with REPLACE)
508 * GNUNET_SYSERR if UNIQUE_ONLY was the option and the
509 * value already exists
511 int GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap
512 *map, const GNUNET_HashCode * key,
515 GNUNET_CONTAINER_MultiHashMapOption
519 * Get the number of key-value pairs in the map.
522 * @return the number of key value pairs
524 unsigned int GNUNET_CONTAINER_multihashmap_size (const struct
525 GNUNET_CONTAINER_MultiHashMap
530 * Iterate over all entries in the map.
533 * @param iterator function to call on each entry
534 * @param cls extra argument to it
535 * @return the number of key value pairs processed,
536 * GNUNET_SYSERR if it aborted iteration
538 int GNUNET_CONTAINER_multihashmap_iterate (const struct
539 GNUNET_CONTAINER_MultiHashMap *map,
540 GNUNET_CONTAINER_HashMapIterator
541 iterator, void *cls);
544 * Iterate over all entries in the map
545 * that match a particular key.
548 * @param key key that the entries must correspond to
549 * @param iterator function to call on each entry
550 * @param cls extra argument to it
551 * @return the number of key value pairs processed,
552 * GNUNET_SYSERR if it aborted iteration
554 int GNUNET_CONTAINER_multihashmap_get_multiple (const struct
555 GNUNET_CONTAINER_MultiHashMap
557 const GNUNET_HashCode * key,
558 GNUNET_CONTAINER_HashMapIterator
559 iterator, void *cls);
561 * Returns the stored value of a random non-null entry
562 * in the hash table. Returns only the first value, does
563 * not go inside bucket linked list (yet). Runs with a
564 * worst case time of N, so it's not efficient in any way
567 void *GNUNET_CONTAINER_multihashmap_get_random (const struct
568 GNUNET_CONTAINER_MultiHashMap
574 /* ******************** doubly-linked list *************** */
577 * Insert an element into a DLL. Assumes
578 * that head, tail and element are structs
579 * with prev and next fields.
581 #define GNUNET_CONTAINER_DLL_insert(head,tail,element) \
582 (element)->next = (head); \
583 (element)->prev = NULL; \
584 if ((tail) == NULL) \
587 (head)->prev = element; \
591 * Insert an element into a DLL after the given other
592 * element. Insert at the head if the other
595 #define GNUNET_CONTAINER_DLL_insert_after(head,tail,other,element) \
596 (element)->prev = (other); \
599 (element)->next = (head); \
600 (head) = (element); \
604 (element)->next = (other)->next; \
605 (other)->next = (element); \
607 if (NULL == (element)->next) \
608 (tail) = (element); \
610 (element)->next->prev = (element);
616 * Remove an element from a DLL. Assumes
617 * that head, tail and element are structs
618 * with prev and next fields.
620 #define GNUNET_CONTAINER_DLL_remove(head,tail,element) \
621 if ((element)->prev == NULL) \
622 (head) = (element)->next; \
624 (element)->prev->next = (element)->next; \
625 if ((element)->next == NULL) \
626 (tail) = (element)->prev; \
628 (element)->next->prev = (element)->prev;
632 /* ******************** Heap *************** */
636 * Cost by which elements in a heap can be ordered.
638 typedef unsigned int GNUNET_CONTAINER_HeapCost;
641 * Heap type, either max or min. Hopefully makes the
642 * implementation more useful.
644 enum GNUNET_CONTAINER_HeapOrder
647 * Heap with the maximum cost at the root.
649 GNUNET_CONTAINER_HEAP_ORDER_MAX,
652 * Heap with the minimum cost at the root.
654 GNUNET_CONTAINER_HEAP_ORDER_MIN
660 struct GNUNET_CONTAINER_Heap;
665 * @param type should the minimum or the maximum element be the root
666 * @return NULL on error, otherwise a fresh heap
668 struct GNUNET_CONTAINER_Heap *GNUNET_CONTAINER_heap_create (enum
669 GNUNET_CONTAINER_HeapOrder
675 * @param h heap to free.
677 void GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *h);
680 * Function called on elements of a heap.
683 * @param element obj stored in heap
684 * @param cost cost of the element
685 * @return GNUNET_YES if we should continue to iterate,
688 typedef int (*GNUNET_CONTAINER_HeapIterator) (void *cls,
690 GNUNET_CONTAINER_HeapCost cost);
692 * Iterate over all entries in the map.
694 * @param heap the heap
695 * @param iterator function to call on each entry
696 * @param iterator_cls closure for iterator
697 * @return number of items handled
698 * GNUNET_SYSERR if iteration was aborted by iterator
700 int GNUNET_CONTAINER_heap_iterate (struct GNUNET_CONTAINER_Heap *heap,
701 GNUNET_CONTAINER_HeapIterator iterator,
706 * Inserts a new item into the heap, item is always neighbor now.
707 * @param heap the heap
710 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap,
711 void *element, GNUNET_CONTAINER_HeapCost cost);
714 * Removes root of the tree, is remove max if a max heap and remove min
715 * if a min heap, returns the data stored at the node.
717 * @param heap the heap
718 * @return NULL if the heap is empty
720 void *GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap);
723 * Returns element stored at root of tree, doesn't effect anything
725 * @param heap the heap
726 * @return NULL if the heap is empty
728 void *GNUNET_CONTAINER_heap_peek (struct GNUNET_CONTAINER_Heap *heap);
731 * Removes any node from the tree based on the neighbor given, does
732 * not traverse the tree (backpointers) but may take more time due to
733 * percolation of nodes.
734 * @param heap the heap
736 void *GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *heap,
740 * Updates the cost of any node in the tree
742 * @param heap the heap
743 * @param element the element for which the cost is updated
744 * @param new_cost new cost for the element
748 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
750 GNUNET_CONTAINER_HeapCost new_cost);
753 * Random walk of the tree, returns the data stored at the next random node
754 * in the walk. Calls callee with the data, or NULL if the tree is empty
755 * or some other problem crops up.
757 * @param heap the heap
758 * @return the next element from the random walk
760 void *GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap
764 * Returns the current size of the heap
766 * @param heap the heap to get the size of
767 * @return number of elements in the heap
770 GNUNET_CONTAINER_heap_get_size (struct GNUNET_CONTAINER_Heap *heap);
774 #if 0 /* keep Emacsens' auto-indent happy */
782 /* ifndef GNUNET_CONTAINER_LIB_H */
784 /* end of gnunet_container_lib.h */