src/include/gnunet_container_lib.h

   1 /*
   2      This file is part of GNUnet.
   3      Copyright (C) 2001-2015 GNUnet e.V.
   4
   5      GNUnet is free software; you can redistribute it and/or modify
   6      it under the terms of the GNU General Public License as published
   7      by the Free Software Foundation; either version 3, or (at your
   8      option) any later version.
   9
  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.
  14
  15      You should have received a copy of the GNU General Public License
  16      along with GNUnet; see the file COPYING.  If not, write to the
  17      Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  18      Boston, MA 02110-1301, USA.
  19 */
  20
  21 /**
  22  * @author Christian Grothoff
  23  * @author Nils Durner
  24  *
  25  * @file
  26  * Container classes for GNUnet
  27  *
  28  * @defgroup hashmap  Container library: MultiHashMap
  29  * Hash map with multiple values per key.
  30  *
  31  * @see [Documentation](https://gnunet.org/util_multihashmap)
  32  *
  33  * @defgroup heap  Container library: Heap
  34  * Min- or max-heap with arbitrary element removal
  35  *
  36  * @defgroup bloomfilter  Container library: Bloom filter
  37  * Probabilistic set tests
  38  *
  39  * @defgroup dll  Container library: Doubly-linked list
  40  *
  41  * @see [Documentation](https://gnunet.org/mdll-api)
  42  *
  43  * @defgroup metadata  Container library: Metadata
  44  * GNU libextractor key-value pairs
  45  */
  46
  47 #ifndef GNUNET_CONTAINER_LIB_H
  48 #define GNUNET_CONTAINER_LIB_H
  49
  50 /* add error and config prototypes */
  51 #include "gnunet_crypto_lib.h"
  52
  53
  54 /**
  55  * Try to compress the given block of data using libz.  Only returns
  56  * the compressed block if compression worked and the new block is
  57  * actually smaller.  Decompress using #GNUNET_decompress().
  58  *
  59  * @param data block to compress; if compression
  60  *        resulted in a smaller block, the first
  61  *        bytes of data are updated to the compressed
  62  *        data
  63  * @param old_size number of bytes in data
  64  * @param[out] result set to the compressed data, if compression worked
  65  * @param[out] new_size set to size of result, if compression worked
  66  * @return #GNUNET_YES if compression reduce the size,
  67  *         #GNUNET_NO if compression did not help
  68  */
  69 int
  70 GNUNET_try_compression (const char *data,
  71                         size_t old_size,
  72                         char **result,
  73                         size_t *new_size);
  74
  75
  76 /**
  77  * Decompress input, return the decompressed data as output.  Dual to
  78  * #GNUNET_try_compression(). Caller must set @a output_size to the
  79  * number of bytes that were originally compressed.
  80  *
  81  * @param input compressed data
  82  * @param input_size number of bytes in input
  83  * @param output_size expected size of the output
  84  * @return NULL on error, buffer of @a output_size decompressed bytes otherwise
  85  */
  86 char *
  87 GNUNET_decompress (const char *input,
  88                    size_t input_size,
  89                    size_t output_size);
  90
  91
  92 #if HAVE_EXTRACTOR_H && HAVE_LIBEXTRACTOR
  93
  94 #include <extractor.h>
  95
  96
  97
  98 #else
  99
 100 /* definitions from extractor.h we need for the build */
 101
 102 /**
 103  * Enumeration defining various sources of keywords.  See also
 104  * http://dublincore.org/documents/1998/09/dces/
 105  */
 106 enum EXTRACTOR_MetaType {
 107   EXTRACTOR_METATYPE_RESERVED = 0,
 108   EXTRACTOR_METATYPE_MIMETYPE = 1,
 109   EXTRACTOR_METATYPE_FILENAME = 2,
 110   EXTRACTOR_METATYPE_COMMENT = 3,
 111   EXTRACTOR_METATYPE_TITLE = 4,
 112   EXTRACTOR_METATYPE_BOOK_TITLE = 5,
 113   EXTRACTOR_METATYPE_JOURNAL_NAME = 8,
 114   EXTRACTOR_METATYPE_AUTHOR_NAME = 13,
 115   EXTRACTOR_METATYPE_PUBLICATION_DATE = 24,
 116   EXTRACTOR_METATYPE_URL = 29,
 117   EXTRACTOR_METATYPE_URI = 30,
 118   EXTRACTOR_METATYPE_ISRC = 31,
 119   EXTRACTOR_METATYPE_UNKNOWN = 45,
 120   EXTRACTOR_METATYPE_DESCRIPTION = 46,
 121   EXTRACTOR_METATYPE_KEYWORDS = 49,
 122   EXTRACTOR_METATYPE_SUBJECT = 52,
 123   EXTRACTOR_METATYPE_PACKAGE_NAME = 69,
 124   EXTRACTOR_METATYPE_THUMBNAIL = 114,
 125   EXTRACTOR_METATYPE_ALBUM = 129,
 126   EXTRACTOR_METATYPE_ARTIST = 130,
 127   EXTRACTOR_METATYPE_ORIGINAL_TITLE = 162,
 128   EXTRACTOR_METATYPE_GNUNET_FULL_DATA = 174,
 129   EXTRACTOR_METATYPE_GNUNET_ORIGINAL_FILENAME = 180,
 130
 131 };
 132
 133 /**
 134  * Format in which the extracted meta data is presented.
 135  */
 136 enum EXTRACTOR_MetaFormat {
 137   /**
 138    * Format is unknown.
 139    */
 140   EXTRACTOR_METAFORMAT_UNKNOWN = 0,
 141
 142   /**
 143    * 0-terminated, UTF-8 encoded string.  "data_len"
 144    * is strlen(data)+1.
 145    */
 146   EXTRACTOR_METAFORMAT_UTF8 = 1,
 147
 148   /**
 149    * Some kind of binary format, see given Mime type.
 150    */
 151   EXTRACTOR_METAFORMAT_BINARY = 2,
 152
 153   /**
 154    * 0-terminated string.  The specific encoding is unknown.
 155    * "data_len" is strlen (data)+1.
 156    */
 157   EXTRACTOR_METAFORMAT_C_STRING = 3
 158 };
 159
 160
 161 /**
 162  * Type of a function that libextractor calls for each
 163  * meta data item found.
 164  *
 165  * @param cls closure (user-defined)
 166  * @param plugin_name name of the plugin that produced this value;
 167  *        special values can be used (i.e. '&lt;zlib&gt;' for zlib being
 168  *        used in the main libextractor library and yielding
 169  *        meta data).
 170  * @param type libextractor-type describing the meta data
 171  * @param format basic format information about @a data
 172  * @param data_mime_type mime-type of @a data (not of the original file);
 173  *        can be NULL (if mime-type is not known)
 174  * @param data actual meta-data found
 175  * @param data_len number of bytes in @a data
 176  * @return 0 to continue extracting, 1 to abort
 177  */
 178 typedef int
 179 (*EXTRACTOR_MetaDataProcessor) (void *cls,
 180                                 const char *plugin_name,
 181                                 enum EXTRACTOR_MetaType type,
 182                                 enum EXTRACTOR_MetaFormat format,
 183                                 const char *data_mime_type,
 184                                 const char *data,
 185                                 size_t data_len);
 186
 187 #endif
 188
 189 #ifndef EXTRACTOR_METATYPE_GNUNET_ORIGINAL_FILENAME
 190 /* hack for LE < 0.6.3 */
 191 #define EXTRACTOR_METATYPE_GNUNET_ORIGINAL_FILENAME 180
 192 #endif
 193
 194 #ifdef __cplusplus
 195 extern "C"
 196 {
 197 #if 0                           /* keep Emacsens' auto-indent happy */
 198 }
 199 #endif
 200 #endif
 201
 202
 203 /* ******************* bloomfilter ***************** */
 204
 205 /**
 206  * @brief bloomfilter representation (opaque)
 207  * @ingroup bloomfilter
 208  */
 209 struct GNUNET_CONTAINER_BloomFilter;
 210
 211
 212 /**
 213  * @ingroup bloomfilter
 214  * Iterator over `struct GNUNET_HashCode`.
 215  *
 216  * @param cls closure
 217  * @param next set to the next hash code
 218  * @return #GNUNET_YES if next was updated
 219  *         #GNUNET_NO if there are no more entries
 220  */
 221 typedef int
 222 (*GNUNET_CONTAINER_HashCodeIterator) (void *cls,
 223                                       struct GNUNET_HashCode *next);
 224
 225
 226 /**
 227  * @ingroup bloomfilter
 228  * Load a Bloom filter from a file.
 229  *
 230  * @param filename the name of the file (or the prefix)
 231  * @param size the size of the bloom-filter (number of
 232  *        bytes of storage space to use); will be rounded up
 233  *        to next power of 2
 234  * @param k the number of #GNUNET_CRYPTO_hash-functions to apply per
 235  *        element (number of bits set per element in the set)
 236  * @return the bloomfilter
 237  */
 238 struct GNUNET_CONTAINER_BloomFilter *
 239 GNUNET_CONTAINER_bloomfilter_load (const char *filename,
 240                                    size_t size,
 241                                    unsigned int k);
 242
 243
 244 /**
 245  * @ingroup bloomfilter
 246  * Create a Bloom filter from raw bits.
 247  *
 248  * @param data the raw bits in memory (maybe NULL,
 249  *        in which case all bits should be considered
 250  *        to be zero).
 251  * @param size the size of the bloom-filter (number of
 252  *        bytes of storage space to use); also size of @a data
 253  *        -- unless data is NULL.  Must be a power of 2.
 254  * @param k the number of #GNUNET_CRYPTO_hash-functions to apply per
 255  *        element (number of bits set per element in the set)
 256  * @return the bloomfilter
 257  */
 258 struct GNUNET_CONTAINER_BloomFilter *
 259 GNUNET_CONTAINER_bloomfilter_init (const char *data,
 260                                    size_t size,
 261                                    unsigned int k);
 262
 263
 264 /**
 265  * @ingroup bloomfilter
 266  * Copy the raw data of this Bloom filter into
 267  * the given data array.
 268  *
 269  * @param data where to write the data
 270  * @param size the size of the given @a data array
 271  * @return #GNUNET_SYSERR if the data array of the wrong size
 272  */
 273 int
 274 GNUNET_CONTAINER_bloomfilter_get_raw_data (const struct GNUNET_CONTAINER_BloomFilter *bf,
 275                                            char *data,
 276                                            size_t size);
 277
 278
 279 /**
 280  * @ingroup bloomfilter
 281  * Test if an element is in the filter.
 282  *
 283  * @param e the element
 284  * @param bf the filter
 285  * @return #GNUNET_YES if the element is in the filter, #GNUNET_NO if not
 286  */
 287 int
 288 GNUNET_CONTAINER_bloomfilter_test (const struct GNUNET_CONTAINER_BloomFilter *bf,
 289                                    const struct GNUNET_HashCode *e);
 290
 291
 292 /**
 293  * @ingroup bloomfilter
 294  * Add an element to the filter.
 295  *
 296  * @param bf the filter
 297  * @param e the element
 298  */
 299 void
 300 GNUNET_CONTAINER_bloomfilter_add (struct GNUNET_CONTAINER_BloomFilter *bf,
 301                                   const struct GNUNET_HashCode *e);
 302
 303
 304 /**
 305  * @ingroup bloomfilter
 306  * Remove an element from the filter.
 307  *
 308  * @param bf the filter
 309  * @param e the element to remove
 310  */
 311 void
 312 GNUNET_CONTAINER_bloomfilter_remove (struct GNUNET_CONTAINER_BloomFilter *bf,
 313                                      const struct GNUNET_HashCode *e);
 314
 315
 316 /**
 317  * @ingroup bloomfilter
 318  * Create a copy of a bloomfilter.
 319  *
 320  * @param bf the filter
 321  * @return copy of bf
 322  */
 323 struct GNUNET_CONTAINER_BloomFilter *
 324 GNUNET_CONTAINER_bloomfilter_copy (const struct GNUNET_CONTAINER_BloomFilter *bf);
 325
 326
 327
 328 /**
 329  * @ingroup bloomfilter
 330  * Free the space associcated with a filter
 331  * in memory, flush to drive if needed (do not
 332  * free the space on the drive).
 333  *
 334  * @param bf the filter
 335  */
 336 void
 337 GNUNET_CONTAINER_bloomfilter_free (struct GNUNET_CONTAINER_BloomFilter *bf);
 338
 339
 340 /**
 341  * Get the number of the addresses set per element in the bloom filter.
 342  *
 343  * @param bf the filter
 344  * @return addresses set per element in the bf
 345  */
 346 size_t
 347 GNUNET_CONTAINER_bloomfilter_get_element_addresses (const struct GNUNET_CONTAINER_BloomFilter *bf);
 348
 349
 350 /**
 351  * @ingroup bloomfilter
 352  * Get size of the bloom filter.
 353  *
 354  * @param bf the filter
 355  * @return number of bytes used for the data of the bloom filter
 356  */
 357 size_t
 358 GNUNET_CONTAINER_bloomfilter_get_size (const struct GNUNET_CONTAINER_BloomFilter *bf);
 359
 360
 361 /**
 362  * @ingroup bloomfilter
 363  * Reset a Bloom filter to empty.
 364  *
 365  * @param bf the filter
 366  */
 367 void
 368 GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter *bf);
 369
 370
 371 /**
 372  * @ingroup bloomfilter
 373  * "or" the entries of the given raw data array with the
 374  * data of the given Bloom filter.  Assumes that
 375  * the @a size of the @a data array and the current filter
 376  * match.
 377  *
 378  * @param bf the filter
 379  * @param data data to OR-in
 380  * @param size size of @a data
 381  * @return #GNUNET_OK on success
 382  */
 383 int
 384 GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf,
 385                                  const char *data, size_t size);
 386
 387
 388 /**
 389  * @ingroup bloomfilter
 390  * "or" the entries of the given raw data array with the
 391  * data of the given Bloom filter.  Assumes that
 392  * the size of the two filters matches.
 393  *
 394  * @param bf the filter
 395  * @param to_or the bloomfilter to or-in
 396  * @return #GNUNET_OK on success
 397  */
 398 int
 399 GNUNET_CONTAINER_bloomfilter_or2 (struct GNUNET_CONTAINER_BloomFilter *bf,
 400                                   const struct GNUNET_CONTAINER_BloomFilter *to_or);
 401
 402
 403 /**
 404  * @ingroup bloomfilter
 405  * Resize a bloom filter.  Note that this operation
 406  * is pretty costly.  Essentially, the Bloom filter
 407  * needs to be completely re-build.
 408  *
 409  * @param bf the filter
 410  * @param iterator an iterator over all elements stored in the BF
 411  * @param iterator_cls closure for @a iterator
 412  * @param size the new size for the filter
 413  * @param k the new number of #GNUNET_CRYPTO_hash-function to apply per element
 414  */
 415 void
 416 GNUNET_CONTAINER_bloomfilter_resize (struct GNUNET_CONTAINER_BloomFilter *bf,
 417                                      GNUNET_CONTAINER_HashCodeIterator iterator,
 418                                      void *iterator_cls,
 419                                      size_t size,
 420                                      unsigned int k);
 421
 422
 423 /* ****************** metadata ******************* */
 424
 425 /**
 426  * @ingroup metadata
 427  * Meta data to associate with a file, directory or namespace.
 428  */
 429 struct GNUNET_CONTAINER_MetaData;
 430
 431
 432 /**
 433  * @ingroup metadata
 434  * Create a fresh meta data container.
 435  *
 436  * @return empty meta-data container
 437  */
 438 struct GNUNET_CONTAINER_MetaData *
 439 GNUNET_CONTAINER_meta_data_create (void);
 440
 441
 442 /**
 443  * @ingroup metadata
 444  * Duplicate a MetaData token.
 445  *
 446  * @param md what to duplicate
 447  * @return duplicate meta-data container
 448  */
 449 struct GNUNET_CONTAINER_MetaData *
 450 GNUNET_CONTAINER_meta_data_duplicate (const struct GNUNET_CONTAINER_MetaData *md);
 451
 452
 453 /**
 454  * @ingroup metadata
 455  * Free meta data.
 456  *
 457  * @param md what to free
 458  */
 459 void
 460 GNUNET_CONTAINER_meta_data_destroy (struct GNUNET_CONTAINER_MetaData *md);
 461
 462
 463 /**
 464  * @ingroup metadata
 465  * Test if two MDs are equal. We consider them equal if
 466  * the meta types, formats and content match (we do not
 467  * include the mime types and plugins names in this
 468  * consideration).
 469  *
 470  * @param md1 first value to check
 471  * @param md2 other value to check
 472  * @return #GNUNET_YES if they are equal
 473  */
 474 int
 475 GNUNET_CONTAINER_meta_data_test_equal (const struct GNUNET_CONTAINER_MetaData *md1,
 476                                        const struct GNUNET_CONTAINER_MetaData *md2);
 477
 478
 479 /**
 480  * @ingroup metadata
 481  * Extend metadata.
 482  *
 483  * @param md metadata to extend
 484  * @param plugin_name name of the plugin that produced this value;
 485  *        special values can be used (i.e. '&lt;zlib&gt;' for zlib being
 486  *        used in the main libextractor library and yielding
 487  *        meta data).
 488  * @param type libextractor-type describing the meta data
 489  * @param format basic format information about data
 490  * @param data_mime_type mime-type of data (not of the original file);
 491  *        can be NULL (if mime-type is not known)
 492  * @param data actual meta-data found
 493  * @param data_size number of bytes in data
 494  * @return #GNUNET_OK on success, #GNUNET_SYSERR if this entry already exists
 495  *         data_mime_type and plugin_name are not considered for "exists" checks
 496  */
 497 int
 498 GNUNET_CONTAINER_meta_data_insert (struct GNUNET_CONTAINER_MetaData *md,
 499                                    const char *plugin_name,
 500                                    enum EXTRACTOR_MetaType type,
 501                                    enum EXTRACTOR_MetaFormat format,
 502                                    const char *data_mime_type,
 503                                    const char *data,
 504                                    size_t data_size);
 505
 506
 507 /**
 508  * @ingroup metadata
 509  * Extend metadata.  Merges the meta data from the second argument
 510  * into the first, discarding duplicate key-value pairs.
 511  *
 512  * @param md metadata to extend
 513  * @param in metadata to merge
 514  */
 515 void
 516 GNUNET_CONTAINER_meta_data_merge (struct GNUNET_CONTAINER_MetaData *md,
 517                                   const struct GNUNET_CONTAINER_MetaData *in);
 518
 519
 520 /**
 521  * @ingroup metadata
 522  * Remove an item.
 523  *
 524  * @param md metadata to manipulate
 525  * @param type type of the item to remove
 526  * @param data specific value to remove, NULL to remove all
 527  *        entries of the given type
 528  * @param data_size number of bytes in data
 529  * @return #GNUNET_OK on success, #GNUNET_SYSERR if the item does not exist in md
 530  */
 531 int
 532 GNUNET_CONTAINER_meta_data_delete (struct GNUNET_CONTAINER_MetaData *md,
 533                                    enum EXTRACTOR_MetaType type,
 534                                    const char *data,
 535                                    size_t data_size);
 536
 537
 538 /**
 539  * @ingroup metadata
 540  * Remove all items in the container.
 541  *
 542  * @param md metadata to manipulate
 543  */
 544 void
 545 GNUNET_CONTAINER_meta_data_clear (struct GNUNET_CONTAINER_MetaData *md);
 546
 547
 548 /**
 549  * @ingroup metadata
 550  * Add the current time as the publication date
 551  * to the meta-data.
 552  *
 553  * @param md metadata to modify
 554  */
 555 void
 556 GNUNET_CONTAINER_meta_data_add_publication_date (struct GNUNET_CONTAINER_MetaData *md);
 557
 558
 559 /**
 560  * @ingroup metadata
 561  * Iterate over MD entries.
 562  *
 563  * @param md metadata to inspect
 564  * @param iter function to call on each entry, return 0 to continue to iterate
 565  *             and 1 to abort iteration in this function (GNU libextractor API!)
 566  * @param iter_cls closure for @a iter
 567  * @return number of entries
 568  */
 569 int
 570 GNUNET_CONTAINER_meta_data_iterate (const struct GNUNET_CONTAINER_MetaData *md,
 571                                     EXTRACTOR_MetaDataProcessor iter,
 572                                     void *iter_cls);
 573
 574
 575 /**
 576  * @ingroup metadata
 577  * Get the first MD entry of the given type.  Caller
 578  * is responsible for freeing the return value.
 579  * Also, only meta data items that are strings (0-terminated)
 580  * are returned by this function.
 581  *
 582  * @param md metadata to inspect
 583  * @param type type to look for
 584  * @return NULL if no entry was found
 585  */
 586 char *
 587 GNUNET_CONTAINER_meta_data_get_by_type (const struct GNUNET_CONTAINER_MetaData *md,
 588                                         enum EXTRACTOR_MetaType type);
 589
 590
 591 /**
 592  * @ingroup metadata
 593  * Get the first matching MD entry of the given types. Caller is
 594  * responsible for freeing the return value.  Also, only meta data
 595  * items that are strings (0-terminated) are returned by this
 596  * function.
 597  *
 598  * @param md metadata to inspect
 599  * @param ... -1-terminated list of types
 600  * @return NULL if we do not have any such entry,
 601  *  otherwise client is responsible for freeing the value!
 602  */
 603 char *
 604 GNUNET_CONTAINER_meta_data_get_first_by_types (const struct GNUNET_CONTAINER_MetaData *md,
 605                                                ...);
 606
 607 /**
 608  * @ingroup metadata
 609  * Get a thumbnail from the meta-data (if present).  Only matches meta
 610  * data with mime type "image" and binary format.
 611  *
 612  * @param md metadata to inspect
 613  * @param thumb will be set to the thumbnail data.  Must be
 614  *        freed by the caller!
 615  * @return number of bytes in thumbnail, 0 if not available
 616  */
 617 size_t
 618 GNUNET_CONTAINER_meta_data_get_thumbnail (const struct GNUNET_CONTAINER_MetaData *md,
 619                                           unsigned char **thumb);
 620
 621
 622
 623 /**
 624  * @ingroup metadata
 625  * Options for metadata serialization.
 626  */
 627 enum GNUNET_CONTAINER_MetaDataSerializationOptions
 628 {
 629   /**
 630    * @ingroup metadata
 631    * Serialize all of the data.
 632    */
 633   GNUNET_CONTAINER_META_DATA_SERIALIZE_FULL = 0,
 634
 635   /**
 636    * @ingroup metadata
 637    * If not enough space is available, it is acceptable
 638    * to only serialize some of the metadata.
 639    */
 640   GNUNET_CONTAINER_META_DATA_SERIALIZE_PART = 1,
 641
 642   /**
 643    * @ingroup metadata
 644    * Speed is of the essence, do not allow compression.
 645    */
 646   GNUNET_CONTAINER_META_DATA_SERIALIZE_NO_COMPRESS = 2
 647 };
 648
 649
 650 /**
 651  * @ingroup metadata
 652  * Serialize meta-data to target.
 653  *
 654  * @param md metadata to serialize
 655  * @param target where to write the serialized metadata;
 656  *         *target can be NULL, in which case memory is allocated
 657  * @param max maximum number of bytes available
 658  * @param opt is it ok to just write SOME of the
 659  *        meta-data to match the size constraint,
 660  *        possibly discarding some data?
 661  * @return number of bytes written on success,
 662  *         -1 on error (typically: not enough
 663  *         space)
 664  */
 665 ssize_t
 666 GNUNET_CONTAINER_meta_data_serialize (const struct GNUNET_CONTAINER_MetaData *md,
 667                                       char **target,
 668                                       size_t max,
 669                                       enum GNUNET_CONTAINER_MetaDataSerializationOptions opt);
 670
 671
 672 /**
 673  * @ingroup metadata
 674  * Get the size of the full meta-data in serialized form.
 675  *
 676  * @param md metadata to inspect
 677  * @return number of bytes needed for serialization, -1 on error
 678  */
 679 ssize_t
 680 GNUNET_CONTAINER_meta_data_get_serialized_size (const struct GNUNET_CONTAINER_MetaData *md);
 681
 682
 683 /**
 684  * @ingroup metadata
 685  * Deserialize meta-data.  Initializes md.
 686  *
 687  * @param input serialized meta-data.
 688  * @param size number of bytes available
 689  * @return MD on success, NULL on error (i.e.
 690  *         bad format)
 691  */
 692 struct GNUNET_CONTAINER_MetaData *
 693 GNUNET_CONTAINER_meta_data_deserialize (const char *input,
 694                                         size_t size);
 695
 696
 697 /* ******************************* HashMap **************************** */
 698
 699 /**
 700  * @ingroup hashmap
 701  * Opaque handle for a HashMap.
 702  */
 703 struct GNUNET_CONTAINER_MultiHashMap;
 704
 705 /**
 706  * @ingroup hashmap
 707  * Opaque handle to an iterator over
 708  * a multihashmap.
 709  */
 710 struct GNUNET_CONTAINER_MultiHashMapIterator;
 711
 712 /**
 713  * @ingroup hashmap
 714  * Options for storing values in the HashMap.
 715  */
 716 enum GNUNET_CONTAINER_MultiHashMapOption
 717 {
 718
 719   /**
 720    * @ingroup hashmap
 721    * If a value with the given key exists, replace it.  Note that the
 722    * old value would NOT be freed by replace (the application has to
 723    * make sure that this happens if required).
 724    */
 725   GNUNET_CONTAINER_MULTIHASHMAPOPTION_REPLACE,
 726
 727   /**
 728    * @ingroup hashmap
 729    * Allow multiple values with the same key.
 730    */
 731   GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE,
 732
 733   /**
 734    * @ingroup hashmap
 735    * There must only be one value per key; storing a value should fail
 736    * if a value under the same key already exists.
 737    */
 738   GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY,
 739
 740   /**
 741    * @ingroup hashmap There must only be one value per key, but don't
 742    * bother checking if a value already exists (faster than
 743    * #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY; implemented
 744    * just like #GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE but this
 745    * option documents better what is intended if
 746    * #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY is what is
 747    * desired).
 748    */
 749   GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST
 750 };
 751
 752
 753 /**
 754  * @ingroup hashmap
 755  * Iterator over hash map entries.
 756  *
 757  * @param cls closure
 758  * @param key current key code
 759  * @param value value in the hash map
 760  * @return #GNUNET_YES if we should continue to
 761  *         iterate,
 762  *         #GNUNET_NO if not.
 763  */
 764 typedef int
 765 (*GNUNET_CONTAINER_HashMapIterator) (void *cls,
 766                                      const struct GNUNET_HashCode *key,
 767                                      void *value);
 768
 769
 770 /**
 771  * @ingroup hashmap
 772  * Create a multi hash map.
 773  *
 774  * @param len initial size (map will grow as needed)
 775  * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default;
 776  *                         #GNUNET_YES means that on 'put', the 'key' does not have
 777  *                         to be copied as the destination of the pointer is
 778  *                         guaranteed to be life as long as the value is stored in
 779  *                         the hashmap.  This can significantly reduce memory
 780  *                         consumption, but of course is also a recipie for
 781  *                         heap corruption if the assumption is not true.  Only
 782  *                         use this if (1) memory use is important in this case and
 783  *                         (2) you have triple-checked that the invariant holds
 784  * @return NULL on error
 785  */
 786 struct GNUNET_CONTAINER_MultiHashMap *
 787 GNUNET_CONTAINER_multihashmap_create (unsigned int len,
 788                                       int do_not_copy_keys);
 789
 790
 791 /**
 792  * @ingroup hashmap
 793  * Destroy a hash map.  Will not free any values
 794  * stored in the hash map!
 795  *
 796  * @param map the map
 797  */
 798 void
 799 GNUNET_CONTAINER_multihashmap_destroy (struct GNUNET_CONTAINER_MultiHashMap *map);
 800
 801
 802 /**
 803  * @ingroup hashmap
 804  * Given a key find a value in the map matching the key.
 805  *
 806  * @param map the map
 807  * @param key what to look for
 808  * @return NULL if no value was found; note that
 809  *   this is indistinguishable from values that just
 810  *   happen to be NULL; use "contains" to test for
 811  *   key-value pairs with value NULL
 812  */
 813 void *
 814 GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap *map,
 815                                    const struct GNUNET_HashCode *key);
 816
 817
 818 /**
 819  * @ingroup hashmap
 820  * Remove the given key-value pair from the map.  Note that if the
 821  * key-value pair is in the map multiple times, only one of the pairs
 822  * will be removed.
 823  *
 824  * @param map the map
 825  * @param key key of the key-value pair
 826  * @param value value of the key-value pair
 827  * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
 828  *  is not in the map
 829  */
 830 int
 831 GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map,
 832                                       const struct GNUNET_HashCode *key,
 833                                       const void *value);
 834
 835 /**
 836  * @ingroup hashmap
 837  * Remove all entries for the given key from the map.
 838  * Note that the values would not be "freed".
 839  *
 840  * @param map the map
 841  * @param key identifies values to be removed
 842  * @return number of values removed
 843  */
 844 int
 845 GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap *map,
 846                                           const struct GNUNET_HashCode *key);
 847
 848
 849 /**
 850  * @ingroup hashmap
 851  * Remove all entries from the map.
 852  * Note that the values would not be "freed".
 853  *
 854  * @param map the map
 855  * @return number of values removed
 856  */
 857 unsigned int
 858 GNUNET_CONTAINER_multihashmap_clear (struct GNUNET_CONTAINER_MultiHashMap *map);
 859
 860
 861 /**
 862  * @ingroup hashmap
 863  * Check if the map contains any value under the given
 864  * key (including values that are NULL).
 865  *
 866  * @param map the map
 867  * @param key the key to test if a value exists for it
 868  * @return #GNUNET_YES if such a value exists,
 869  *         #GNUNET_NO if not
 870  */
 871 int
 872 GNUNET_CONTAINER_multihashmap_contains (const struct GNUNET_CONTAINER_MultiHashMap *map,
 873                                         const struct GNUNET_HashCode * key);
 874
 875
 876 /**
 877  * @ingroup hashmap
 878  * Check if the map contains the given value under the given
 879  * key.
 880  *
 881  * @param map the map
 882  * @param key the key to test if a value exists for it
 883  * @param value value to test for
 884  * @return #GNUNET_YES if such a value exists,
 885  *         #GNUNET_NO if not
 886  */
 887 int
 888 GNUNET_CONTAINER_multihashmap_contains_value (const struct GNUNET_CONTAINER_MultiHashMap *map,
 889                                               const struct GNUNET_HashCode *key,
 890                                               const void *value);
 891
 892
 893 /**
 894  * @ingroup hashmap
 895  * Store a key-value pair in the map.
 896  *
 897  * @param map the map
 898  * @param key key to use
 899  * @param value value to use
 900  * @param opt options for put
 901  * @return #GNUNET_OK on success,
 902  *         #GNUNET_NO if a value was replaced (with REPLACE)
 903  *         #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
 904  *                       value already exists
 905  */
 906 int
 907 GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map,
 908                                    const struct GNUNET_HashCode *key,
 909                                    void *value,
 910                                    enum GNUNET_CONTAINER_MultiHashMapOption
 911                                    opt);
 912
 913 /**
 914  * @ingroup hashmap
 915  * Get the number of key-value pairs in the map.
 916  *
 917  * @param map the map
 918  * @return the number of key value pairs
 919  */
 920 unsigned int
 921 GNUNET_CONTAINER_multihashmap_size (const struct GNUNET_CONTAINER_MultiHashMap *map);
 922
 923
 924 /**
 925  * @ingroup hashmap
 926  * Iterate over all entries in the map.
 927  *
 928  * @param map the map
 929  * @param it function to call on each entry
 930  * @param it_cls extra argument to @a it
 931  * @return the number of key value pairs processed,
 932  *         #GNUNET_SYSERR if it aborted iteration
 933  */
 934 int
 935 GNUNET_CONTAINER_multihashmap_iterate (const struct GNUNET_CONTAINER_MultiHashMap *map,
 936                                        GNUNET_CONTAINER_HashMapIterator it,
 937                                        void *it_cls);
 938
 939
 940 /**
 941  * @ingroup hashmap
 942  * Create an iterator for a multihashmap.
 943  * The iterator can be used to retrieve all the elements in the multihashmap
 944  * one by one, without having to handle all elements at once (in contrast to
 945  * #GNUNET_CONTAINER_multihashmap_iterate).  Note that the iterator can not be
 946  * used anymore if elements have been removed from 'map' after the creation of
 947  * the iterator, or 'map' has been destroyed.  Adding elements to 'map' may
 948  * result in skipped or repeated elements.
 949  *
 950  * @param map the map to create an iterator for
 951  * @return an iterator over the given multihashmap @a map
 952  */
 953 struct GNUNET_CONTAINER_MultiHashMapIterator *
 954 GNUNET_CONTAINER_multihashmap_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap *map);
 955
 956
 957 /**
 958  * @ingroup hashmap
 959  * Retrieve the next element from the hash map at the iterator's
 960  * position.  If there are no elements left, #GNUNET_NO is returned,
 961  * and @a key and @a value are not modified.  This operation is only
 962  * allowed if no elements have been removed from the multihashmap
 963  * since the creation of @a iter, and the map has not been destroyed.
 964  * Adding elements may result in repeating or skipping elements.
 965  *
 966  * @param iter the iterator to get the next element from
 967  * @param key pointer to store the key in, can be NULL
 968  * @param value pointer to store the value in, can be NULL
 969  * @return #GNUNET_YES we returned an element,
 970  *         #GNUNET_NO if we are out of elements
 971  */
 972 int
 973 GNUNET_CONTAINER_multihashmap_iterator_next (struct GNUNET_CONTAINER_MultiHashMapIterator *iter,
 974                                              struct GNUNET_HashCode *key,
 975                                              const void **value);
 976
 977
 978 /**
 979  * @ingroup hashmap
 980  * Destroy a multihashmap iterator.
 981  *
 982  * @param iter the iterator to destroy
 983  */
 984 void
 985 GNUNET_CONTAINER_multihashmap_iterator_destroy (struct GNUNET_CONTAINER_MultiHashMapIterator *iter);
 986
 987
 988 /**
 989  * @ingroup hashmap
 990  * Iterate over all entries in the map that match a particular key.
 991  *
 992  * @param map the map
 993  * @param key key that the entries must correspond to
 994  * @param it function to call on each entry
 995  * @param it_cls extra argument to @a it
 996  * @return the number of key value pairs processed,
 997  *         #GNUNET_SYSERR if it aborted iteration
 998  */
 999 int
1000 GNUNET_CONTAINER_multihashmap_get_multiple (const struct GNUNET_CONTAINER_MultiHashMap *map,
1001                                             const struct GNUNET_HashCode *key,
1002                                             GNUNET_CONTAINER_HashMapIterator it,
1003                                             void *it_cls);
1004
1005
1006 /**
1007  * @ingroup hashmap
1008  * Call @a it on a random value from the map, or not at all
1009  * if the map is empty.  Note that this function has linear
1010  * complexity (in the size of the map).
1011  *
1012  * @param map the map
1013  * @param it function to call on a random entry
1014  * @param it_cls extra argument to @a it
1015  * @return the number of key value pairs processed, zero or one.
1016  */
1017 unsigned int
1018 GNUNET_CONTAINER_multihashmap_get_random (const struct GNUNET_CONTAINER_MultiHashMap *map,
1019                                           GNUNET_CONTAINER_HashMapIterator it,
1020                                           void *it_cls);
1021
1022
1023 /* ***************** Version of Multihashmap for peer identities ****************** */
1024
1025 /**
1026  * @ingroup hashmap
1027  * Iterator over hash map entries.
1028  *
1029  * @param cls closure
1030  * @param key current public key
1031  * @param value value in the hash map
1032  * @return #GNUNET_YES if we should continue to
1033  *         iterate,
1034  *         #GNUNET_NO if not.
1035  */
1036 typedef int
1037 (*GNUNET_CONTAINER_PeerMapIterator) (void *cls,
1038                                      const struct GNUNET_PeerIdentity *key,
1039                                      void *value);
1040
1041
1042 /**
1043  * Hash map from peer identities to values.
1044  */
1045 struct GNUNET_CONTAINER_MultiPeerMap;
1046
1047
1048 /**
1049  * @ingroup hashmap
1050  * Create a multi peer map (hash map for public keys of peers).
1051  *
1052  * @param len initial size (map will grow as needed)
1053  * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default;
1054  *                         #GNUNET_YES means that on 'put', the 'key' does not have
1055  *                         to be copied as the destination of the pointer is
1056  *                         guaranteed to be life as long as the value is stored in
1057  *                         the hashmap.  This can significantly reduce memory
1058  *                         consumption, but of course is also a recipie for
1059  *                         heap corruption if the assumption is not true.  Only
1060  *                         use this if (1) memory use is important in this case and
1061  *                         (2) you have triple-checked that the invariant holds
1062  * @return NULL on error
1063  */
1064 struct GNUNET_CONTAINER_MultiPeerMap *
1065 GNUNET_CONTAINER_multipeermap_create (unsigned int len,
1066                                       int do_not_copy_keys);
1067
1068
1069 /**
1070  * @ingroup hashmap
1071  * Destroy a hash map.  Will not free any values
1072  * stored in the hash map!
1073  *
1074  * @param map the map
1075  */
1076 void
1077 GNUNET_CONTAINER_multipeermap_destroy (struct GNUNET_CONTAINER_MultiPeerMap *map);
1078
1079
1080 /**
1081  * @ingroup hashmap
1082  * Given a key find a value in the map matching the key.
1083  *
1084  * @param map the map
1085  * @param key what to look for
1086  * @return NULL if no value was found; note that
1087  *   this is indistinguishable from values that just
1088  *   happen to be NULL; use "contains" to test for
1089  *   key-value pairs with value NULL
1090  */
1091 void *
1092 GNUNET_CONTAINER_multipeermap_get (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1093                                    const struct GNUNET_PeerIdentity *key);
1094
1095
1096 /**
1097  * @ingroup hashmap
1098  * Remove the given key-value pair from the map.  Note that if the
1099  * key-value pair is in the map multiple times, only one of the pairs
1100  * will be removed.
1101  *
1102  * @param map the map
1103  * @param key key of the key-value pair
1104  * @param value value of the key-value pair
1105  * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
1106  *  is not in the map
1107  */
1108 int
1109 GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map,
1110                                       const struct GNUNET_PeerIdentity * key,
1111                                       const void *value);
1112
1113 /**
1114  * @ingroup hashmap
1115  * Remove all entries for the given key from the map.
1116  * Note that the values would not be "freed".
1117  *
1118  * @param map the map
1119  * @param key identifies values to be removed
1120  * @return number of values removed
1121  */
1122 int
1123 GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap *map,
1124                                           const struct GNUNET_PeerIdentity *key);
1125
1126
1127 /**
1128  * @ingroup hashmap
1129  * Check if the map contains any value under the given
1130  * key (including values that are NULL).
1131  *
1132  * @param map the map
1133  * @param key the key to test if a value exists for it
1134  * @return #GNUNET_YES if such a value exists,
1135  *         #GNUNET_NO if not
1136  */
1137 int
1138 GNUNET_CONTAINER_multipeermap_contains (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1139                                         const struct GNUNET_PeerIdentity *key);
1140
1141
1142 /**
1143  * @ingroup hashmap
1144  * Check if the map contains the given value under the given
1145  * key.
1146  *
1147  * @param map the map
1148  * @param key the key to test if a value exists for it
1149  * @param value value to test for
1150  * @return #GNUNET_YES if such a value exists,
1151  *         #GNUNET_NO if not
1152  */
1153 int
1154 GNUNET_CONTAINER_multipeermap_contains_value (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1155                                               const struct GNUNET_PeerIdentity * key,
1156                                               const void *value);
1157
1158
1159 /**
1160  * @ingroup hashmap
1161  * Store a key-value pair in the map.
1162  *
1163  * @param map the map
1164  * @param key key to use
1165  * @param value value to use
1166  * @param opt options for put
1167  * @return #GNUNET_OK on success,
1168  *         #GNUNET_NO if a value was replaced (with REPLACE)
1169  *         #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
1170  *                       value already exists
1171  */
1172 int
1173 GNUNET_CONTAINER_multipeermap_put (struct GNUNET_CONTAINER_MultiPeerMap *map,
1174                                    const struct GNUNET_PeerIdentity *key,
1175                                    void *value,
1176                                    enum GNUNET_CONTAINER_MultiHashMapOption opt);
1177
1178
1179 /**
1180  * @ingroup hashmap
1181  * Get the number of key-value pairs in the map.
1182  *
1183  * @param map the map
1184  * @return the number of key value pairs
1185  */
1186 unsigned int
1187 GNUNET_CONTAINER_multipeermap_size (const struct GNUNET_CONTAINER_MultiPeerMap *map);
1188
1189
1190 /**
1191  * @ingroup hashmap
1192  * Iterate over all entries in the map.
1193  *
1194  * @param map the map
1195  * @param it function to call on each entry
1196  * @param it_cls extra argument to @a it
1197  * @return the number of key value pairs processed,
1198  *         #GNUNET_SYSERR if it aborted iteration
1199  */
1200 int
1201 GNUNET_CONTAINER_multipeermap_iterate (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1202                                        GNUNET_CONTAINER_PeerMapIterator it,
1203                                        void *it_cls);
1204
1205
1206 struct GNUNET_CONTAINER_MultiPeerMapIterator;
1207 /**
1208  * @ingroup hashmap
1209  * Create an iterator for a multihashmap.
1210  * The iterator can be used to retrieve all the elements in the multihashmap
1211  * one by one, without having to handle all elements at once (in contrast to
1212  * #GNUNET_CONTAINER_multipeermap_iterate).  Note that the iterator can not be
1213  * used anymore if elements have been removed from @a map after the creation of
1214  * the iterator, or 'map' has been destroyed.  Adding elements to @a map may
1215  * result in skipped or repeated elements.
1216  *
1217  * @param map the map to create an iterator for
1218  * @return an iterator over the given multihashmap @a map
1219  */
1220 struct GNUNET_CONTAINER_MultiPeerMapIterator *
1221 GNUNET_CONTAINER_multipeermap_iterator_create (const struct GNUNET_CONTAINER_MultiPeerMap *map);
1222
1223
1224 /**
1225  * @ingroup hashmap
1226  * Retrieve the next element from the hash map at the iterator's
1227  * position.  If there are no elements left, #GNUNET_NO is returned,
1228  * and @a key and @a value are not modified.  This operation is only
1229  * allowed if no elements have been removed from the multihashmap
1230  * since the creation of @a iter, and the map has not been destroyed.
1231  * Adding elements may result in repeating or skipping elements.
1232  *
1233  * @param iter the iterator to get the next element from
1234  * @param key pointer to store the key in, can be NULL
1235  * @param value pointer to store the value in, can be NULL
1236  * @return #GNUNET_YES we returned an element,
1237  *         #GNUNET_NO if we are out of elements
1238  */
1239 int
1240 GNUNET_CONTAINER_multipeermap_iterator_next (struct GNUNET_CONTAINER_MultiPeerMapIterator *iter,
1241                                              struct GNUNET_PeerIdentity *key,
1242                                              const void **value);
1243
1244
1245 /**
1246  * @ingroup hashmap
1247  * Destroy a multipeermap iterator.
1248  *
1249  * @param iter the iterator to destroy
1250  */
1251 void
1252 GNUNET_CONTAINER_multipeermap_iterator_destroy (struct GNUNET_CONTAINER_MultiPeerMapIterator *iter);
1253
1254
1255 /**
1256  * @ingroup hashmap
1257  * Iterate over all entries in the map that match a particular key.
1258  *
1259  * @param map the map
1260  * @param key public key that the entries must correspond to
1261  * @param it function to call on each entry
1262  * @param it_cls extra argument to @a it
1263  * @return the number of key value pairs processed,
1264  *         #GNUNET_SYSERR if it aborted iteration
1265  */
1266 int
1267 GNUNET_CONTAINER_multipeermap_get_multiple (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1268                                             const struct GNUNET_PeerIdentity *key,
1269                                             GNUNET_CONTAINER_PeerMapIterator it,
1270                                             void *it_cls);
1271
1272
1273 /**
1274  * @ingroup hashmap
1275  * Call @a it on a random value from the map, or not at all
1276  * if the map is empty.  Note that this function has linear
1277  * complexity (in the size of the map).
1278  *
1279  * @param map the map
1280  * @param it function to call on a random entry
1281  * @param it_cls extra argument to @a it
1282  * @return the number of key value pairs processed, zero or one.
1283  */
1284 unsigned int
1285 GNUNET_CONTAINER_multipeermap_get_random (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1286                                           GNUNET_CONTAINER_PeerMapIterator it,
1287                                           void *it_cls);
1288
1289
1290 /* Version of multihashmap with 32 bit keys */
1291
1292 /**
1293  * @ingroup hashmap
1294  * Opaque handle for the 32-bit key HashMap.
1295  */
1296 struct GNUNET_CONTAINER_MultiHashMap32;
1297
1298
1299 /**
1300  * @ingroup hashmap
1301  * Opaque handle to an iterator over
1302  * a 32-bit key multihashmap.
1303  */
1304 struct GNUNET_CONTAINER_MultiHashMap32Iterator;
1305
1306
1307 /**
1308  * @ingroup hashmap
1309  * Iterator over hash map entries.
1310  *
1311  * @param cls closure
1312  * @param key current key code
1313  * @param value value in the hash map
1314  * @return #GNUNET_YES if we should continue to
1315  *         iterate,
1316  *         #GNUNET_NO if not.
1317  */
1318 typedef int (*GNUNET_CONTAINER_HashMapIterator32) (void *cls,
1319                                                    uint32_t key,
1320                                                    void *value);
1321
1322
1323 /**
1324  * @ingroup hashmap
1325  * Create a 32-bit key multi hash map.
1326  *
1327  * @param len initial size (map will grow as needed)
1328  * @return NULL on error
1329  */
1330 struct GNUNET_CONTAINER_MultiHashMap32 *
1331 GNUNET_CONTAINER_multihashmap32_create (unsigned int len);
1332
1333
1334 /**
1335  * @ingroup hashmap
1336  * Destroy a 32-bit key hash map.  Will not free any values
1337  * stored in the hash map!
1338  *
1339  * @param map the map
1340  */
1341 void
1342 GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32
1343                                          *map);
1344
1345
1346 /**
1347  * @ingroup hashmap
1348  * Get the number of key-value pairs in the map.
1349  *
1350  * @param map the map
1351  * @return the number of key value pairs
1352  */
1353 unsigned int
1354 GNUNET_CONTAINER_multihashmap32_size (const struct
1355                                       GNUNET_CONTAINER_MultiHashMap32 *map);
1356
1357
1358 /**
1359  * @ingroup hashmap
1360  * Given a key find a value in the map matching the key.
1361  *
1362  * @param map the map
1363  * @param key what to look for
1364  * @return NULL if no value was found; note that
1365  *   this is indistinguishable from values that just
1366  *   happen to be NULL; use "contains" to test for
1367  *   key-value pairs with value NULL
1368  */
1369 void *
1370 GNUNET_CONTAINER_multihashmap32_get (const struct
1371                                      GNUNET_CONTAINER_MultiHashMap32 *map,
1372                                      uint32_t key);
1373
1374
1375 /**
1376  * @ingroup hashmap
1377  * Iterate over all entries in the map.
1378  *
1379  * @param map the map
1380  * @param it function to call on each entry
1381  * @param it_cls extra argument to @a it
1382  * @return the number of key value pairs processed,
1383  *         #GNUNET_SYSERR if it aborted iteration
1384  */
1385 int
1386 GNUNET_CONTAINER_multihashmap32_iterate (const struct
1387                                          GNUNET_CONTAINER_MultiHashMap32 *map,
1388                                          GNUNET_CONTAINER_HashMapIterator32 it,
1389                                          void *it_cls);
1390
1391
1392 /**
1393  * @ingroup hashmap
1394  * Remove the given key-value pair from the map.  Note that if the
1395  * key-value pair is in the map multiple times, only one of the pairs
1396  * will be removed.
1397  *
1398  * @param map the map
1399  * @param key key of the key-value pair
1400  * @param value value of the key-value pair
1401  * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
1402  *  is not in the map
1403  */
1404 int
1405 GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 *map,
1406                                         uint32_t key,
1407                                         const void *value);
1408
1409
1410 /**
1411  * @ingroup hashmap
1412  * Remove all entries for the given key from the map.
1413  * Note that the values would not be "freed".
1414  *
1415  * @param map the map
1416  * @param key identifies values to be removed
1417  * @return number of values removed
1418  */
1419 int
1420 GNUNET_CONTAINER_multihashmap32_remove_all (struct GNUNET_CONTAINER_MultiHashMap32 *map,
1421                                             uint32_t key);
1422
1423
1424 /**
1425  * @ingroup hashmap
1426  * Check if the map contains any value under the given
1427  * key (including values that are NULL).
1428  *
1429  * @param map the map
1430  * @param key the key to test if a value exists for it
1431  * @return #GNUNET_YES if such a value exists,
1432  *         #GNUNET_NO if not
1433  */
1434 int
1435 GNUNET_CONTAINER_multihashmap32_contains (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
1436                                           uint32_t key);
1437
1438
1439 /**
1440  * @ingroup hashmap
1441  * Check if the map contains the given value under the given
1442  * key.
1443  *
1444  * @param map the map
1445  * @param key the key to test if a value exists for it
1446  * @param value value to test for
1447  * @return #GNUNET_YES if such a value exists,
1448  *         #GNUNET_NO if not
1449  */
1450 int
1451 GNUNET_CONTAINER_multihashmap32_contains_value (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
1452                                                 uint32_t key,
1453                                                 const void *value);
1454
1455
1456 /**
1457  * @ingroup hashmap
1458  * Store a key-value pair in the map.
1459  *
1460  * @param map the map
1461  * @param key key to use
1462  * @param value value to use
1463  * @param opt options for put
1464  * @return #GNUNET_OK on success,
1465  *         #GNUNET_NO if a value was replaced (with REPLACE)
1466  *         #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
1467  *                       value already exists
1468  */
1469 int
1470 GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32 *map,
1471                                      uint32_t key,
1472                                      void *value,
1473                                      enum GNUNET_CONTAINER_MultiHashMapOption opt);
1474
1475
1476 /**
1477  * @ingroup hashmap
1478  * Iterate over all entries in the map that match a particular key.
1479  *
1480  * @param map the map
1481  * @param key key that the entries must correspond to
1482  * @param it function to call on each entry
1483  * @param it_cls extra argument to @a it
1484  * @return the number of key value pairs processed,
1485  *         #GNUNET_SYSERR if it aborted iteration
1486  */
1487 int
1488 GNUNET_CONTAINER_multihashmap32_get_multiple (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
1489                                               uint32_t key,
1490                                               GNUNET_CONTAINER_HashMapIterator32 it,
1491                                               void *it_cls);
1492
1493
1494 /**
1495  * Create an iterator for a 32-bit multihashmap.
1496  * The iterator can be used to retrieve all the elements in the multihashmap
1497  * one by one, without having to handle all elements at once (in contrast to
1498  * #GNUNET_CONTAINER_multihashmap32_iterate).  Note that the iterator can not be
1499  * used anymore if elements have been removed from 'map' after the creation of
1500  * the iterator, or 'map' has been destroyed.  Adding elements to 'map' may
1501  * result in skipped or repeated elements.
1502  *
1503  * @param map the map to create an iterator for
1504  * @return an iterator over the given multihashmap map
1505  */
1506 struct GNUNET_CONTAINER_MultiHashMap32Iterator *
1507 GNUNET_CONTAINER_multihashmap32_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap32 *map);
1508
1509
1510 /**
1511  * Retrieve the next element from the hash map at the iterator's position.
1512  * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
1513  * are not modified.
1514  * This operation is only allowed if no elements have been removed from the
1515  * multihashmap since the creation of 'iter', and the map has not been destroyed.
1516  * Adding elements may result in repeating or skipping elements.
1517  *
1518  * @param iter the iterator to get the next element from
1519  * @param key pointer to store the key in, can be NULL
1520  * @param value pointer to store the value in, can be NULL
1521  * @return #GNUNET_YES we returned an element,
1522  *         #GNUNET_NO if we are out of elements
1523  */
1524 int
1525 GNUNET_CONTAINER_multihashmap32_iterator_next (struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter,
1526                                                uint32_t *key,
1527                                                const void **value);
1528
1529
1530 /**
1531  * Destroy a 32-bit multihashmap iterator.
1532  *
1533  * @param iter the iterator to destroy
1534  */
1535 void
1536 GNUNET_CONTAINER_multihashmap32_iterator_destroy (struct GNUNET_CONTAINER_MultiHashMapIterator *iter);
1537
1538
1539 /* ******************** doubly-linked list *************** */
1540 /* To avoid mistakes: head->prev == tail->next == NULL     */
1541
1542 /**
1543  * @ingroup dll
1544  * Insert an element at the head of a DLL. Assumes that head, tail and
1545  * element are structs with prev and next fields.
1546  *
1547  * @param head pointer to the head of the DLL
1548  * @param tail pointer to the tail of the DLL
1549  * @param element element to insert
1550  */
1551 #define GNUNET_CONTAINER_DLL_insert(head,tail,element) do { \
1552   GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1553   GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1554   (element)->next = (head); \
1555   (element)->prev = NULL; \
1556   if ((tail) == NULL) \
1557     (tail) = element; \
1558   else \
1559     (head)->prev = element; \
1560   (head) = (element); } while (0)
1561
1562
1563 /**
1564  * @ingroup dll
1565  * Insert an element at the tail of a DLL. Assumes that head, tail and
1566  * element are structs with prev and next fields.
1567  *
1568  * @param head pointer to the head of the DLL
1569  * @param tail pointer to the tail of the DLL
1570  * @param element element to insert
1571  */
1572 #define GNUNET_CONTAINER_DLL_insert_tail(head,tail,element) do { \
1573   GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1574   GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1575   (element)->prev = (tail); \
1576   (element)->next = NULL; \
1577   if ((head) == NULL) \
1578     (head) = element; \
1579   else \
1580     (tail)->next = element; \
1581   (tail) = (element); } while (0)
1582
1583
1584 /**
1585  * @ingroup dll
1586  * Insert an element into a DLL after the given other element.  Insert
1587  * at the head if the other element is NULL.
1588  *
1589  * @param head pointer to the head of the DLL
1590  * @param tail pointer to the tail of the DLL
1591  * @param other prior element, NULL for insertion at head of DLL
1592  * @param element element to insert
1593  */
1594 #define GNUNET_CONTAINER_DLL_insert_after(head,tail,other,element) do { \
1595   GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1596   GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1597   (element)->prev = (other); \
1598   if (NULL == other) \
1599     { \
1600       (element)->next = (head); \
1601       (head) = (element); \
1602     } \
1603   else \
1604     { \
1605       (element)->next = (other)->next; \
1606       (other)->next = (element); \
1607     } \
1608   if (NULL == (element)->next) \
1609     (tail) = (element); \
1610   else \
1611     (element)->next->prev = (element); } while (0)
1612
1613
1614 /**
1615  * @ingroup dll
1616  * Insert an element into a DLL before the given other element.  Insert
1617  * at the tail if the other element is NULL.
1618  *
1619  * @param head pointer to the head of the DLL
1620  * @param tail pointer to the tail of the DLL
1621  * @param other prior element, NULL for insertion at head of DLL
1622  * @param element element to insert
1623  */
1624 #define GNUNET_CONTAINER_DLL_insert_before(head,tail,other,element) do { \
1625   GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1626   GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1627   (element)->next = (other); \
1628   if (NULL == other) \
1629     { \
1630       (element)->prev = (tail); \
1631       (tail) = (element); \
1632     } \
1633   else \
1634     { \
1635       (element)->prev = (other)->prev; \
1636       (other)->prev = (element); \
1637     } \
1638   if (NULL == (element)->prev) \
1639     (head) = (element); \
1640   else \
1641     (element)->prev->next = (element); } while (0)
1642
1643
1644 /**
1645  * @ingroup dll
1646  * Remove an element from a DLL. Assumes that head, tail and
1647  * element point to structs with prev and next fields.
1648  *
1649  * Using the head or tail pointer as the element
1650  * argument does NOT work with this macro.
1651  * Make sure to store head/tail in another pointer
1652  * and use it to remove the head or tail of the list.
1653  *
1654  * @param head pointer to the head of the DLL
1655  * @param tail pointer to the tail of the DLL
1656  * @param element element to remove
1657  */
1658 #define GNUNET_CONTAINER_DLL_remove(head,tail,element) do { \
1659   GNUNET_assert ( ( (element)->prev != NULL) || ((head) == (element))); \
1660   GNUNET_assert ( ( (element)->next != NULL) || ((tail) == (element))); \
1661   if ((element)->prev == NULL) \
1662     (head) = (element)->next;  \
1663   else \
1664     (element)->prev->next = (element)->next; \
1665   if ((element)->next == NULL) \
1666     (tail) = (element)->prev;  \
1667   else \
1668     (element)->next->prev = (element)->prev; \
1669   (element)->next = NULL; \
1670   (element)->prev = NULL; } while (0)
1671
1672
1673 /* ************ Multi-DLL interface, allows DLL elements to be
1674    in multiple lists at the same time *********************** */
1675
1676 /**
1677  * @ingroup dll
1678  * Insert an element at the head of a MDLL. Assumes that head, tail and
1679  * element are structs with prev and next fields.
1680  *
1681  * @param mdll suffix name for the next and prev pointers in the element
1682  * @param head pointer to the head of the MDLL
1683  * @param tail pointer to the tail of the MDLL
1684  * @param element element to insert
1685  */
1686 #define GNUNET_CONTAINER_MDLL_insert(mdll,head,tail,element) do {       \
1687   GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1688   GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1689   (element)->next_##mdll = (head); \
1690   (element)->prev_##mdll = NULL; \
1691   if ((tail) == NULL) \
1692     (tail) = element; \
1693   else \
1694     (head)->prev_##mdll = element; \
1695   (head) = (element); } while (0)
1696
1697
1698 /**
1699  * @ingroup dll
1700  * Insert an element at the tail of a MDLL. Assumes that head, tail and
1701  * element are structs with prev and next fields.
1702  *
1703  * @param mdll suffix name for the next and prev pointers in the element
1704  * @param head pointer to the head of the MDLL
1705  * @param tail pointer to the tail of the MDLL
1706  * @param element element to insert
1707  */
1708 #define GNUNET_CONTAINER_MDLL_insert_tail(mdll,head,tail,element) do {  \
1709   GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1710   GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1711   (element)->prev_##mdll = (tail); \
1712   (element)->next_##mdll = NULL; \
1713   if ((head) == NULL) \
1714     (head) = element; \
1715   else \
1716     (tail)->next_##mdll = element; \
1717   (tail) = (element); } while (0)
1718
1719
1720 /**
1721  * @ingroup dll
1722  * Insert an element into a MDLL after the given other element.  Insert
1723  * at the head if the other element is NULL.
1724  *
1725  * @param mdll suffix name for the next and prev pointers in the element
1726  * @param head pointer to the head of the MDLL
1727  * @param tail pointer to the tail of the MDLL
1728  * @param other prior element, NULL for insertion at head of MDLL
1729  * @param element element to insert
1730  */
1731 #define GNUNET_CONTAINER_MDLL_insert_after(mdll,head,tail,other,element) do { \
1732   GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1733   GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1734   (element)->prev_##mdll = (other); \
1735   if (NULL == other) \
1736     { \
1737       (element)->next_##mdll = (head); \
1738       (head) = (element); \
1739     } \
1740   else \
1741     { \
1742       (element)->next_##mdll = (other)->next_##mdll; \
1743       (other)->next_##mdll = (element); \
1744     } \
1745   if (NULL == (element)->next_##mdll) \
1746     (tail) = (element); \
1747   else \
1748     (element)->next->prev_##mdll = (element); } while (0)
1749
1750
1751 /**
1752  * @ingroup dll
1753  * Insert an element into a MDLL before the given other element.  Insert
1754  * at the tail if the other element is NULL.
1755  *
1756  * @param mdll suffix name for the next and prev pointers in the element
1757  * @param head pointer to the head of the MDLL
1758  * @param tail pointer to the tail of the MDLL
1759  * @param other prior element, NULL for insertion at head of MDLL
1760  * @param element element to insert
1761  */
1762 #define GNUNET_CONTAINER_MDLL_insert_before(mdll,head,tail,other,element) do { \
1763   GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1764   GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1765   (element)->next_##mdll = (other); \
1766   if (NULL == other) \
1767     { \
1768       (element)->prev = (tail); \
1769       (tail) = (element); \
1770     } \
1771   else \
1772     { \
1773       (element)->prev_##mdll = (other)->prev_##mdll; \
1774       (other)->prev_##mdll = (element); \
1775     } \
1776   if (NULL == (element)->prev_##mdll) \
1777     (head) = (element); \
1778   else \
1779     (element)->prev_##mdll->next_##mdll = (element); } while (0)
1780
1781
1782 /**
1783  * @ingroup dll
1784  * Remove an element from a MDLL. Assumes
1785  * that head, tail and element are structs
1786  * with prev and next fields.
1787  *
1788  * @param mdll suffix name for the next and prev pointers in the element
1789  * @param head pointer to the head of the MDLL
1790  * @param tail pointer to the tail of the MDLL
1791  * @param element element to remove
1792  */
1793 #define GNUNET_CONTAINER_MDLL_remove(mdll,head,tail,element) do {       \
1794   GNUNET_assert ( ( (element)->prev_##mdll != NULL) || ((head) == (element))); \
1795   GNUNET_assert ( ( (element)->next_##mdll != NULL) || ((tail) == (element))); \
1796   if ((element)->prev_##mdll == NULL) \
1797     (head) = (element)->next_##mdll;  \
1798   else \
1799     (element)->prev_##mdll->next_##mdll = (element)->next_##mdll; \
1800   if ((element)->next_##mdll == NULL) \
1801     (tail) = (element)->prev_##mdll;  \
1802   else \
1803     (element)->next_##mdll->prev_##mdll = (element)->prev_##mdll; \
1804   (element)->next_##mdll = NULL; \
1805   (element)->prev_##mdll = NULL; } while (0)
1806
1807
1808
1809 /* ******************** Heap *************** */
1810
1811
1812 /**
1813  * @ingroup heap
1814  * Cost by which elements in a heap can be ordered.
1815  */
1816 typedef uint64_t GNUNET_CONTAINER_HeapCostType;
1817
1818
1819 /**
1820  * @ingroup heap
1821  * Heap type, either max or min.
1822  */
1823 enum GNUNET_CONTAINER_HeapOrder
1824 {
1825   /**
1826    * @ingroup heap
1827    * Heap with the maximum cost at the root.
1828    */
1829   GNUNET_CONTAINER_HEAP_ORDER_MAX,
1830
1831   /**
1832    * @ingroup heap
1833    * Heap with the minimum cost at the root.
1834    */
1835   GNUNET_CONTAINER_HEAP_ORDER_MIN
1836 };
1837
1838
1839 /**
1840  * @ingroup heap
1841  * Handle to a Heap.
1842  */
1843 struct GNUNET_CONTAINER_Heap;
1844
1845
1846 /**
1847  * @ingroup heap
1848  * Handle to a node in a heap.
1849  */
1850 struct GNUNET_CONTAINER_HeapNode;
1851
1852
1853 /**
1854  * @ingroup heap
1855  * Create a new heap.
1856  *
1857  * @param order how should the heap be sorted?
1858  * @return handle to the heap
1859  */
1860 struct GNUNET_CONTAINER_Heap *
1861 GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order);
1862
1863
1864 /**
1865  * @ingroup heap
1866  * Destroys the heap.  Only call on a heap that
1867  * is already empty.
1868  *
1869  * @param heap heap to destroy
1870  */
1871 void
1872 GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap);
1873
1874
1875 /**
1876  * @ingroup heap
1877  * Get element stored at the root of @a heap.
1878  *
1879  * @param heap  Heap to inspect.
1880  * @return Element at the root, or NULL if heap is empty.
1881  */
1882 void *
1883 GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap);
1884
1885
1886 /**
1887  * Get @a element and @a cost stored at the root of @a heap.
1888  *
1889  * @param[in]  heap     Heap to inspect.
1890  * @param[out] element  Root element is returned here.
1891  * @param[out] cost     Cost of @a element is returned here.
1892  * @return #GNUNET_YES if an element is returned,
1893  *         #GNUNET_NO  if the heap is empty.
1894  */
1895 int
1896 GNUNET_CONTAINER_heap_peek2 (const struct GNUNET_CONTAINER_Heap *heap,
1897                              void **element,
1898                              GNUNET_CONTAINER_HeapCostType *cost);
1899
1900
1901 /**
1902  * @ingroup heap
1903  * Get the current size of the heap
1904  *
1905  * @param heap the heap to get the size of
1906  * @return number of elements stored
1907  */
1908 unsigned int
1909 GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap);
1910
1911
1912 /**
1913  * @ingroup heap
1914  * Get the current cost of the node
1915  *
1916  * @param node the node to get the cost of
1917  * @return cost of the node
1918  */
1919 GNUNET_CONTAINER_HeapCostType
1920 GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode
1921                                      *node);
1922
1923 /**
1924  * @ingroup heap
1925  * Iterator for heap
1926  *
1927  * @param cls closure
1928  * @param node internal node of the heap
1929  * @param element value stored at the node
1930  * @param cost cost associated with the node
1931  * @return #GNUNET_YES if we should continue to iterate,
1932  *         #GNUNET_NO if not.
1933  */
1934 typedef int
1935 (*GNUNET_CONTAINER_HeapIterator) (void *cls,
1936                                   struct GNUNET_CONTAINER_HeapNode *node,
1937                                   void *element,
1938                                   GNUNET_CONTAINER_HeapCostType cost);
1939
1940
1941 /**
1942  * @ingroup heap
1943  * Iterate over all entries in the heap.
1944  *
1945  * @param heap the heap
1946  * @param iterator function to call on each entry
1947  * @param iterator_cls closure for @a iterator
1948  */
1949 void
1950 GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
1951                                GNUNET_CONTAINER_HeapIterator iterator,
1952                                void *iterator_cls);
1953
1954 /**
1955  * @ingroup heap
1956  * Perform a random walk of the tree.  The walk is biased
1957  * towards elements closer to the root of the tree (since
1958  * each walk starts at the root and ends at a random leaf).
1959  * The heap internally tracks the current position of the
1960  * walk.
1961  *
1962  * @param heap heap to walk
1963  * @return data stored at the next random node in the walk;
1964  *         NULL if the tree is empty.
1965  */
1966 void *
1967 GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap);
1968
1969
1970 /**
1971  * @ingroup heap
1972  * Inserts a new element into the heap.
1973  *
1974  * @param heap heap to modify
1975  * @param element element to insert
1976  * @param cost cost for the element
1977  * @return node for the new element
1978  */
1979 struct GNUNET_CONTAINER_HeapNode *
1980 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap,
1981                               void *element,
1982                               GNUNET_CONTAINER_HeapCostType cost);
1983
1984
1985 /**
1986  * @ingroup heap
1987  * Remove root of the heap.
1988  *
1989  * @param heap heap to modify
1990  * @return element data stored at the root node
1991  */
1992 void *
1993 GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap);
1994
1995
1996 /**
1997  * @ingroup heap
1998  * Removes a node from the heap.
1999  *
2000  * @param node node to remove
2001  * @return element data stored at the node, NULL if heap is empty
2002  */
2003 void *
2004 GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node);
2005
2006
2007 /**
2008  * @ingroup heap
2009  * Updates the cost of any node in the tree
2010  *
2011  * @param heap heap to modify
2012  * @param node node for which the cost is to be changed
2013  * @param new_cost new cost for the node
2014  */
2015 void
2016 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
2017                                    struct GNUNET_CONTAINER_HeapNode *node,
2018                                    GNUNET_CONTAINER_HeapCostType new_cost);
2019
2020
2021 #if 0                           /* keep Emacsens' auto-indent happy */
2022 {
2023 #endif
2024 #ifdef __cplusplus
2025 }
2026 #endif
2027
2028
2029 /* ifndef GNUNET_CONTAINER_LIB_H */
2030 #endif
2031 /* end of gnunet_container_lib.h */