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 it
   6      under the terms of the GNU Affero General Public License as published
   7      by the Free Software Foundation, either version 3 of the License,
   8      or (at your 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      Affero General Public License for more details.
  14
  15      You should have received a copy of the GNU Affero General Public License
  16      along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17
  18      SPDX-License-Identifier: AGPL3.0-or-later
  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, size_t input_size, size_t output_size);
  88
  89
  90 #if HAVE_EXTRACTOR_H
  91
  92 #include <extractor.h>
  93
  94 #else
  95
  96 /* definitions from extractor.h we need for the build */
  97
  98 /**
  99  * Enumeration defining various sources of keywords.  See also
 100  * http://dublincore.org/documents/1998/09/dces/
 101  */
 102 enum EXTRACTOR_MetaType
 103 {
 104   EXTRACTOR_METATYPE_RESERVED = 0,
 105   EXTRACTOR_METATYPE_MIMETYPE = 1,
 106   EXTRACTOR_METATYPE_FILENAME = 2,
 107   EXTRACTOR_METATYPE_COMMENT = 3,
 108   EXTRACTOR_METATYPE_TITLE = 4,
 109   EXTRACTOR_METATYPE_BOOK_TITLE = 5,
 110   EXTRACTOR_METATYPE_JOURNAL_NAME = 8,
 111   EXTRACTOR_METATYPE_AUTHOR_NAME = 13,
 112   EXTRACTOR_METATYPE_PUBLICATION_DATE = 24,
 113   EXTRACTOR_METATYPE_URL = 29,
 114   EXTRACTOR_METATYPE_URI = 30,
 115   EXTRACTOR_METATYPE_ISRC = 31,
 116   EXTRACTOR_METATYPE_UNKNOWN = 45,
 117   EXTRACTOR_METATYPE_DESCRIPTION = 46,
 118   EXTRACTOR_METATYPE_KEYWORDS = 49,
 119   EXTRACTOR_METATYPE_SUBJECT = 52,
 120   EXTRACTOR_METATYPE_PACKAGE_NAME = 69,
 121   EXTRACTOR_METATYPE_THUMBNAIL = 114,
 122   EXTRACTOR_METATYPE_ALBUM = 129,
 123   EXTRACTOR_METATYPE_ARTIST = 130,
 124   EXTRACTOR_METATYPE_ORIGINAL_TITLE = 162,
 125   EXTRACTOR_METATYPE_GNUNET_FULL_DATA = 174,
 126   EXTRACTOR_METATYPE_GNUNET_ORIGINAL_FILENAME = 180,
 127 };
 128
 129 /**
 130  * Format in which the extracted meta data is presented.
 131  */
 132 enum EXTRACTOR_MetaFormat
 133 {
 134   /**
 135    * Format is unknown.
 136    */
 137   EXTRACTOR_METAFORMAT_UNKNOWN = 0,
 138
 139   /**
 140    * 0-terminated, UTF-8 encoded string.  "data_len"
 141    * is strlen(data)+1.
 142    */
 143   EXTRACTOR_METAFORMAT_UTF8 = 1,
 144
 145   /**
 146    * Some kind of binary format, see given Mime type.
 147    */
 148   EXTRACTOR_METAFORMAT_BINARY = 2,
 149
 150   /**
 151    * 0-terminated string.  The specific encoding is unknown.
 152    * "data_len" is strlen (data)+1.
 153    */
 154   EXTRACTOR_METAFORMAT_C_STRING = 3
 155 };
 156
 157
 158 /**
 159  * Type of a function that libextractor calls for each
 160  * meta data item found.
 161  *
 162  * @param cls closure (user-defined)
 163  * @param plugin_name name of the plugin that produced this value;
 164  *        special values can be used (i.e. '&lt;zlib&gt;' for zlib being
 165  *        used in the main libextractor library and yielding
 166  *        meta data).
 167  * @param type libextractor-type describing the meta data
 168  * @param format basic format information about @a data
 169  * @param data_mime_type mime-type of @a data (not of the original file);
 170  *        can be NULL (if mime-type is not known)
 171  * @param data actual meta-data found
 172  * @param data_len number of bytes in @a data
 173  * @return 0 to continue extracting, 1 to abort
 174  */
 175 typedef int (*EXTRACTOR_MetaDataProcessor) (void *cls,
 176                                             const char *plugin_name,
 177                                             enum EXTRACTOR_MetaType type,
 178                                             enum EXTRACTOR_MetaFormat format,
 179                                             const char *data_mime_type,
 180                                             const char *data,
 181                                             size_t data_len);
 182
 183 #endif
 184
 185 #ifndef EXTRACTOR_METATYPE_GNUNET_ORIGINAL_FILENAME
 186 /* hack for LE < 0.6.3 */
 187 #define EXTRACTOR_METATYPE_GNUNET_ORIGINAL_FILENAME 180
 188 #endif
 189
 190 #ifdef __cplusplus
 191 extern "C" {
 192 #if 0 /* keep Emacsens' auto-indent happy */
 193 }
 194 #endif
 195 #endif
 196
 197
 198 /* ******************* bloomfilter ***************** */
 199
 200 /**
 201  * @brief bloomfilter representation (opaque)
 202  * @ingroup bloomfilter
 203  */
 204 struct GNUNET_CONTAINER_BloomFilter;
 205
 206
 207 /**
 208  * @ingroup bloomfilter
 209  * Iterator over `struct GNUNET_HashCode`.
 210  *
 211  * @param cls closure
 212  * @param next set to the next hash code
 213  * @return #GNUNET_YES if next was updated
 214  *         #GNUNET_NO if there are no more entries
 215  */
 216 typedef int (*GNUNET_CONTAINER_HashCodeIterator) (void *cls,
 217                                                   struct GNUNET_HashCode *next);
 218
 219
 220 /**
 221  * @ingroup bloomfilter
 222  * Load a Bloom filter from a file.
 223  *
 224  * @param filename the name of the file (or the prefix)
 225  * @param size the size of the bloom-filter (number of
 226  *        bytes of storage space to use); will be rounded up
 227  *        to next power of 2
 228  * @param k the number of #GNUNET_CRYPTO_hash-functions to apply per
 229  *        element (number of bits set per element in the set)
 230  * @return the bloomfilter
 231  */
 232 struct GNUNET_CONTAINER_BloomFilter *
 233 GNUNET_CONTAINER_bloomfilter_load (const char *filename,
 234                                    size_t size,
 235                                    unsigned int k);
 236
 237
 238 /**
 239  * @ingroup bloomfilter
 240  * Create a Bloom filter from raw bits.
 241  *
 242  * @param data the raw bits in memory (maybe NULL,
 243  *        in which case all bits should be considered
 244  *        to be zero).
 245  * @param size the size of the bloom-filter (number of
 246  *        bytes of storage space to use); also size of @a data
 247  *        -- unless data is NULL.  Must be a power of 2.
 248  * @param k the number of #GNUNET_CRYPTO_hash-functions to apply per
 249  *        element (number of bits set per element in the set)
 250  * @return the bloomfilter
 251  */
 252 struct GNUNET_CONTAINER_BloomFilter *
 253 GNUNET_CONTAINER_bloomfilter_init (const char *data,
 254                                    size_t size,
 255                                    unsigned int k);
 256
 257
 258 /**
 259  * @ingroup bloomfilter
 260  * Copy the raw data of this Bloom filter into
 261  * the given data array.
 262  *
 263  * @param data where to write the data
 264  * @param size the size of the given @a data array
 265  * @return #GNUNET_SYSERR if the data array of the wrong size
 266  */
 267 int
 268 GNUNET_CONTAINER_bloomfilter_get_raw_data (
 269   const struct GNUNET_CONTAINER_BloomFilter *bf,
 270   char *data,
 271   size_t size);
 272
 273
 274 /**
 275  * @ingroup bloomfilter
 276  * Test if an element is in the filter.
 277  *
 278  * @param e the element
 279  * @param bf the filter
 280  * @return #GNUNET_YES if the element is in the filter, #GNUNET_NO if not
 281  */
 282 int
 283 GNUNET_CONTAINER_bloomfilter_test (
 284   const struct GNUNET_CONTAINER_BloomFilter *bf,
 285   const struct GNUNET_HashCode *e);
 286
 287
 288 /**
 289  * @ingroup bloomfilter
 290  * Add an element to the filter.
 291  *
 292  * @param bf the filter
 293  * @param e the element
 294  */
 295 void
 296 GNUNET_CONTAINER_bloomfilter_add (struct GNUNET_CONTAINER_BloomFilter *bf,
 297                                   const struct GNUNET_HashCode *e);
 298
 299
 300 /**
 301  * @ingroup bloomfilter
 302  * Remove an element from the filter.
 303  *
 304  * @param bf the filter
 305  * @param e the element to remove
 306  */
 307 void
 308 GNUNET_CONTAINER_bloomfilter_remove (struct GNUNET_CONTAINER_BloomFilter *bf,
 309                                      const struct GNUNET_HashCode *e);
 310
 311
 312 /**
 313  * @ingroup bloomfilter
 314  * Create a copy of a bloomfilter.
 315  *
 316  * @param bf the filter
 317  * @return copy of bf
 318  */
 319 struct GNUNET_CONTAINER_BloomFilter *
 320 GNUNET_CONTAINER_bloomfilter_copy (
 321   const struct GNUNET_CONTAINER_BloomFilter *bf);
 322
 323
 324 /**
 325  * @ingroup bloomfilter
 326  * Free the space associcated with a filter
 327  * in memory, flush to drive if needed (do not
 328  * free the space on the drive).
 329  *
 330  * @param bf the filter
 331  */
 332 void
 333 GNUNET_CONTAINER_bloomfilter_free (struct GNUNET_CONTAINER_BloomFilter *bf);
 334
 335
 336 /**
 337  * Get the number of the addresses set per element in the bloom filter.
 338  *
 339  * @param bf the filter
 340  * @return addresses set per element in the bf
 341  */
 342 size_t
 343 GNUNET_CONTAINER_bloomfilter_get_element_addresses (
 344   const struct GNUNET_CONTAINER_BloomFilter *bf);
 345
 346
 347 /**
 348  * @ingroup bloomfilter
 349  * Get size of the bloom filter.
 350  *
 351  * @param bf the filter
 352  * @return number of bytes used for the data of the bloom filter
 353  */
 354 size_t
 355 GNUNET_CONTAINER_bloomfilter_get_size (
 356   const struct GNUNET_CONTAINER_BloomFilter *bf);
 357
 358
 359 /**
 360  * @ingroup bloomfilter
 361  * Reset a Bloom filter to empty.
 362  *
 363  * @param bf the filter
 364  */
 365 void
 366 GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter *bf);
 367
 368
 369 /**
 370  * @ingroup bloomfilter
 371  * "or" the entries of the given raw data array with the
 372  * data of the given Bloom filter.  Assumes that
 373  * the @a size of the @a data array and the current filter
 374  * match.
 375  *
 376  * @param bf the filter
 377  * @param data data to OR-in
 378  * @param size size of @a data
 379  * @return #GNUNET_OK on success
 380  */
 381 int
 382 GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf,
 383                                  const char *data,
 384                                  size_t size);
 385
 386
 387 /**
 388  * @ingroup bloomfilter
 389  * "or" the entries of the given raw data array with the
 390  * data of the given Bloom filter.  Assumes that
 391  * the size of the two filters matches.
 392  *
 393  * @param bf the filter
 394  * @param to_or the bloomfilter to or-in
 395  * @return #GNUNET_OK on success
 396  */
 397 int
 398 GNUNET_CONTAINER_bloomfilter_or2 (
 399   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 (
 451   const struct GNUNET_CONTAINER_MetaData *md);
 452
 453
 454 /**
 455  * @ingroup metadata
 456  * Free meta data.
 457  *
 458  * @param md what to free
 459  */
 460 void
 461 GNUNET_CONTAINER_meta_data_destroy (struct GNUNET_CONTAINER_MetaData *md);
 462
 463
 464 /**
 465  * @ingroup metadata
 466  * Test if two MDs are equal. We consider them equal if
 467  * the meta types, formats and content match (we do not
 468  * include the mime types and plugins names in this
 469  * consideration).
 470  *
 471  * @param md1 first value to check
 472  * @param md2 other value to check
 473  * @return #GNUNET_YES if they are equal
 474  */
 475 int
 476 GNUNET_CONTAINER_meta_data_test_equal (
 477   const struct GNUNET_CONTAINER_MetaData *md1,
 478   const struct GNUNET_CONTAINER_MetaData *md2);
 479
 480
 481 /**
 482  * @ingroup metadata
 483  * Extend metadata.
 484  *
 485  * @param md metadata to extend
 486  * @param plugin_name name of the plugin that produced this value;
 487  *        special values can be used (i.e. '&lt;zlib&gt;' for zlib being
 488  *        used in the main libextractor library and yielding
 489  *        meta data).
 490  * @param type libextractor-type describing the meta data
 491  * @param format basic format information about data
 492  * @param data_mime_type mime-type of data (not of the original file);
 493  *        can be NULL (if mime-type is not known)
 494  * @param data actual meta-data found
 495  * @param data_size number of bytes in data
 496  * @return #GNUNET_OK on success, #GNUNET_SYSERR if this entry already exists
 497  *         data_mime_type and plugin_name are not considered for "exists" checks
 498  */
 499 int
 500 GNUNET_CONTAINER_meta_data_insert (struct GNUNET_CONTAINER_MetaData *md,
 501                                    const char *plugin_name,
 502                                    enum EXTRACTOR_MetaType type,
 503                                    enum EXTRACTOR_MetaFormat format,
 504                                    const char *data_mime_type,
 505                                    const char *data,
 506                                    size_t data_size);
 507
 508
 509 /**
 510  * @ingroup metadata
 511  * Extend metadata.  Merges the meta data from the second argument
 512  * into the first, discarding duplicate key-value pairs.
 513  *
 514  * @param md metadata to extend
 515  * @param in metadata to merge
 516  */
 517 void
 518 GNUNET_CONTAINER_meta_data_merge (struct GNUNET_CONTAINER_MetaData *md,
 519                                   const struct GNUNET_CONTAINER_MetaData *in);
 520
 521
 522 /**
 523  * @ingroup metadata
 524  * Remove an item.
 525  *
 526  * @param md metadata to manipulate
 527  * @param type type of the item to remove
 528  * @param data specific value to remove, NULL to remove all
 529  *        entries of the given type
 530  * @param data_size number of bytes in data
 531  * @return #GNUNET_OK on success, #GNUNET_SYSERR if the item does not exist in md
 532  */
 533 int
 534 GNUNET_CONTAINER_meta_data_delete (struct GNUNET_CONTAINER_MetaData *md,
 535                                    enum EXTRACTOR_MetaType type,
 536                                    const char *data,
 537                                    size_t data_size);
 538
 539
 540 /**
 541  * @ingroup metadata
 542  * Remove all items in the container.
 543  *
 544  * @param md metadata to manipulate
 545  */
 546 void
 547 GNUNET_CONTAINER_meta_data_clear (struct GNUNET_CONTAINER_MetaData *md);
 548
 549
 550 /**
 551  * @ingroup metadata
 552  * Add the current time as the publication date
 553  * to the meta-data.
 554  *
 555  * @param md metadata to modify
 556  */
 557 void
 558 GNUNET_CONTAINER_meta_data_add_publication_date (
 559   struct GNUNET_CONTAINER_MetaData *md);
 560
 561
 562 /**
 563  * @ingroup metadata
 564  * Iterate over MD entries.
 565  *
 566  * @param md metadata to inspect
 567  * @param iter function to call on each entry, return 0 to continue to iterate
 568  *             and 1 to abort iteration in this function (GNU libextractor API!)
 569  * @param iter_cls closure for @a iter
 570  * @return number of entries
 571  */
 572 int
 573 GNUNET_CONTAINER_meta_data_iterate (const struct GNUNET_CONTAINER_MetaData *md,
 574                                     EXTRACTOR_MetaDataProcessor iter,
 575                                     void *iter_cls);
 576
 577
 578 /**
 579  * @ingroup metadata
 580  * Get the first MD entry of the given type.  Caller
 581  * is responsible for freeing the return value.
 582  * Also, only meta data items that are strings (0-terminated)
 583  * are returned by this function.
 584  *
 585  * @param md metadata to inspect
 586  * @param type type to look for
 587  * @return NULL if no entry was found
 588  */
 589 char *
 590 GNUNET_CONTAINER_meta_data_get_by_type (
 591   const struct GNUNET_CONTAINER_MetaData *md,
 592   enum EXTRACTOR_MetaType type);
 593
 594
 595 /**
 596  * @ingroup metadata
 597  * Get the first matching MD entry of the given types. Caller is
 598  * responsible for freeing the return value.  Also, only meta data
 599  * items that are strings (0-terminated) are returned by this
 600  * function.
 601  *
 602  * @param md metadata to inspect
 603  * @param ... -1-terminated list of types
 604  * @return NULL if we do not have any such entry,
 605  *  otherwise client is responsible for freeing the value!
 606  */
 607 char *
 608 GNUNET_CONTAINER_meta_data_get_first_by_types (
 609   const struct GNUNET_CONTAINER_MetaData *md,
 610   ...);
 611
 612 /**
 613  * @ingroup metadata
 614  * Get a thumbnail from the meta-data (if present).  Only matches meta
 615  * data with mime type "image" and binary format.
 616  *
 617  * @param md metadata to inspect
 618  * @param thumb will be set to the thumbnail data.  Must be
 619  *        freed by the caller!
 620  * @return number of bytes in thumbnail, 0 if not available
 621  */
 622 size_t
 623 GNUNET_CONTAINER_meta_data_get_thumbnail (
 624   const struct GNUNET_CONTAINER_MetaData *md,
 625   unsigned char **thumb);
 626
 627
 628 /**
 629  * @ingroup metadata
 630  * Options for metadata serialization.
 631  */
 632 enum GNUNET_CONTAINER_MetaDataSerializationOptions
 633 {
 634   /**
 635    * @ingroup metadata
 636    * Serialize all of the data.
 637    */
 638   GNUNET_CONTAINER_META_DATA_SERIALIZE_FULL = 0,
 639
 640   /**
 641    * @ingroup metadata
 642    * If not enough space is available, it is acceptable
 643    * to only serialize some of the metadata.
 644    */
 645   GNUNET_CONTAINER_META_DATA_SERIALIZE_PART = 1,
 646
 647   /**
 648    * @ingroup metadata
 649    * Speed is of the essence, do not allow compression.
 650    */
 651   GNUNET_CONTAINER_META_DATA_SERIALIZE_NO_COMPRESS = 2
 652 };
 653
 654
 655 /**
 656  * @ingroup metadata
 657  * Serialize meta-data to target.
 658  *
 659  * @param md metadata to serialize
 660  * @param target where to write the serialized metadata;
 661  *         *target can be NULL, in which case memory is allocated
 662  * @param max maximum number of bytes available
 663  * @param opt is it ok to just write SOME of the
 664  *        meta-data to match the size constraint,
 665  *        possibly discarding some data?
 666  * @return number of bytes written on success,
 667  *         -1 on error (typically: not enough
 668  *         space)
 669  */
 670 ssize_t
 671 GNUNET_CONTAINER_meta_data_serialize (
 672   const struct GNUNET_CONTAINER_MetaData *md,
 673   char **target,
 674   size_t max,
 675   enum GNUNET_CONTAINER_MetaDataSerializationOptions opt);
 676
 677
 678 /**
 679  * @ingroup metadata
 680  * Get the size of the full meta-data in serialized form.
 681  *
 682  * @param md metadata to inspect
 683  * @return number of bytes needed for serialization, -1 on error
 684  */
 685 ssize_t
 686 GNUNET_CONTAINER_meta_data_get_serialized_size (
 687   const struct GNUNET_CONTAINER_MetaData *md);
 688
 689
 690 /**
 691  * @ingroup metadata
 692  * Deserialize meta-data.  Initializes md.
 693  *
 694  * @param input serialized meta-data.
 695  * @param size number of bytes available
 696  * @return MD on success, NULL on error (i.e.
 697  *         bad format)
 698  */
 699 struct GNUNET_CONTAINER_MetaData *
 700 GNUNET_CONTAINER_meta_data_deserialize (const char *input, size_t size);
 701
 702
 703 /* ******************************* HashMap **************************** */
 704
 705 /**
 706  * @ingroup hashmap
 707  * Opaque handle for a HashMap.
 708  */
 709 struct GNUNET_CONTAINER_MultiHashMap;
 710
 711 /**
 712  * @ingroup hashmap
 713  * Opaque handle to an iterator over
 714  * a multihashmap.
 715  */
 716 struct GNUNET_CONTAINER_MultiHashMapIterator;
 717
 718 /**
 719  * @ingroup hashmap
 720  * Options for storing values in the HashMap.
 721  */
 722 enum GNUNET_CONTAINER_MultiHashMapOption
 723 {
 724   /**
 725    * @ingroup hashmap
 726    * If a value with the given key exists, replace it.  Note that the
 727    * old value would NOT be freed by replace (the application has to
 728    * make sure that this happens if required).
 729    */
 730   GNUNET_CONTAINER_MULTIHASHMAPOPTION_REPLACE,
 731
 732   /**
 733    * @ingroup hashmap
 734    * Allow multiple values with the same key.
 735    */
 736   GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE,
 737
 738   /**
 739    * @ingroup hashmap
 740    * There must only be one value per key; storing a value should fail
 741    * if a value under the same key already exists.
 742    */
 743   GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY,
 744
 745   /**
 746    * @ingroup hashmap There must only be one value per key, but don't
 747    * bother checking if a value already exists (faster than
 748    * #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY; implemented
 749    * just like #GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE but this
 750    * option documents better what is intended if
 751    * #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY is what is
 752    * desired).
 753    */
 754   GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST
 755 };
 756
 757
 758 /**
 759  * @ingroup hashmap
 760  * Iterator over hash map entries.
 761  *
 762  * @param cls closure
 763  * @param key current key code
 764  * @param value value in the hash map
 765  * @return #GNUNET_YES if we should continue to
 766  *         iterate,
 767  *         #GNUNET_NO if not.
 768  */
 769 typedef int (*GNUNET_CONTAINER_MulitHashMapIteratorCallback) (
 770   void *cls,
 771   const struct GNUNET_HashCode *key,
 772   void *value);
 773
 774
 775 /**
 776  * @ingroup hashmap
 777  * Create a multi hash map.
 778  *
 779  * @param len initial size (map will grow as needed)
 780  * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default;
 781  *                         #GNUNET_YES means that on 'put', the 'key' does not have
 782  *                         to be copied as the destination of the pointer is
 783  *                         guaranteed to be life as long as the value is stored in
 784  *                         the hashmap.  This can significantly reduce memory
 785  *                         consumption, but of course is also a recipie for
 786  *                         heap corruption if the assumption is not true.  Only
 787  *                         use this if (1) memory use is important in this case and
 788  *                         (2) you have triple-checked that the invariant holds
 789  * @return NULL on error
 790  */
 791 struct GNUNET_CONTAINER_MultiHashMap *
 792 GNUNET_CONTAINER_multihashmap_create (unsigned int len, int do_not_copy_keys);
 793
 794
 795 /**
 796  * @ingroup hashmap
 797  * Destroy a hash map.  Will not free any values
 798  * stored in the hash map!
 799  *
 800  * @param map the map
 801  */
 802 void
 803 GNUNET_CONTAINER_multihashmap_destroy (
 804   struct GNUNET_CONTAINER_MultiHashMap *map);
 805
 806
 807 /**
 808  * @ingroup hashmap
 809  * Given a key find a value in the map matching the key.
 810  *
 811  * @param map the map
 812  * @param key what to look for
 813  * @return NULL if no value was found; note that
 814  *   this is indistinguishable from values that just
 815  *   happen to be NULL; use "contains" to test for
 816  *   key-value pairs with value NULL
 817  */
 818 void *
 819 GNUNET_CONTAINER_multihashmap_get (
 820   const struct GNUNET_CONTAINER_MultiHashMap *map,
 821   const struct GNUNET_HashCode *key);
 822
 823
 824 /**
 825  * @ingroup hashmap
 826  * Remove the given key-value pair from the map.  Note that if the
 827  * key-value pair is in the map multiple times, only one of the pairs
 828  * will be removed.
 829  *
 830  * @param map the map
 831  * @param key key of the key-value pair
 832  * @param value value of the key-value pair
 833  * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
 834  *  is not in the map
 835  */
 836 int
 837 GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map,
 838                                       const struct GNUNET_HashCode *key,
 839                                       const void *value);
 840
 841 /**
 842  * @ingroup hashmap
 843  * Remove all entries for the given key from the map.
 844  * Note that the values would not be "freed".
 845  *
 846  * @param map the map
 847  * @param key identifies values to be removed
 848  * @return number of values removed
 849  */
 850 int
 851 GNUNET_CONTAINER_multihashmap_remove_all (
 852   struct GNUNET_CONTAINER_MultiHashMap *map,
 853   const struct GNUNET_HashCode *key);
 854
 855
 856 /**
 857  * @ingroup hashmap
 858  * Remove all entries from the map.
 859  * Note that the values would not be "freed".
 860  *
 861  * @param map the map
 862  * @return number of values removed
 863  */
 864 unsigned int
 865 GNUNET_CONTAINER_multihashmap_clear (struct GNUNET_CONTAINER_MultiHashMap *map);
 866
 867
 868 /**
 869  * @ingroup hashmap
 870  * Check if the map contains any value under the given
 871  * key (including values that are NULL).
 872  *
 873  * @param map the map
 874  * @param key the key to test if a value exists for it
 875  * @return #GNUNET_YES if such a value exists,
 876  *         #GNUNET_NO if not
 877  */
 878 int
 879 GNUNET_CONTAINER_multihashmap_contains (
 880   const struct GNUNET_CONTAINER_MultiHashMap *map,
 881   const struct GNUNET_HashCode *key);
 882
 883
 884 /**
 885  * @ingroup hashmap
 886  * Check if the map contains the given value under the given
 887  * key.
 888  *
 889  * @param map the map
 890  * @param key the key to test if a value exists for it
 891  * @param value value to test for
 892  * @return #GNUNET_YES if such a value exists,
 893  *         #GNUNET_NO if not
 894  */
 895 int
 896 GNUNET_CONTAINER_multihashmap_contains_value (
 897   const struct GNUNET_CONTAINER_MultiHashMap *map,
 898   const struct GNUNET_HashCode *key,
 899   const void *value);
 900
 901
 902 /**
 903  * @ingroup hashmap
 904  * Store a key-value pair in the map.
 905  *
 906  * @param map the map
 907  * @param key key to use
 908  * @param value value to use
 909  * @param opt options for put
 910  * @return #GNUNET_OK on success,
 911  *         #GNUNET_NO if a value was replaced (with REPLACE)
 912  *         #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
 913  *                       value already exists
 914  */
 915 int
 916 GNUNET_CONTAINER_multihashmap_put (
 917   struct GNUNET_CONTAINER_MultiHashMap *map,
 918   const struct GNUNET_HashCode *key,
 919   void *value,
 920   enum GNUNET_CONTAINER_MultiHashMapOption opt);
 921
 922 /**
 923  * @ingroup hashmap
 924  * Get the number of key-value pairs in the map.
 925  *
 926  * @param map the map
 927  * @return the number of key value pairs
 928  */
 929 unsigned int
 930 GNUNET_CONTAINER_multihashmap_size (
 931   const struct GNUNET_CONTAINER_MultiHashMap *map);
 932
 933
 934 /**
 935  * @ingroup hashmap
 936  * Iterate over all entries in the map.
 937  *
 938  * @param map the map
 939  * @param it function to call on each entry
 940  * @param it_cls extra argument to @a it
 941  * @return the number of key value pairs processed,
 942  *         #GNUNET_SYSERR if it aborted iteration
 943  */
 944 int
 945 GNUNET_CONTAINER_multihashmap_iterate (
 946   struct GNUNET_CONTAINER_MultiHashMap *map,
 947   GNUNET_CONTAINER_MulitHashMapIteratorCallback it,
 948   void *it_cls);
 949
 950
 951 /**
 952  * @ingroup hashmap
 953  * Create an iterator for a multihashmap.
 954  * The iterator can be used to retrieve all the elements in the multihashmap
 955  * one by one, without having to handle all elements at once (in contrast to
 956  * #GNUNET_CONTAINER_multihashmap_iterate).  Note that the iterator can not be
 957  * used anymore if elements have been removed from 'map' after the creation of
 958  * the iterator, or 'map' has been destroyed.  Adding elements to 'map' may
 959  * result in skipped or repeated elements.
 960  *
 961  * @param map the map to create an iterator for
 962  * @return an iterator over the given multihashmap @a map
 963  */
 964 struct GNUNET_CONTAINER_MultiHashMapIterator *
 965 GNUNET_CONTAINER_multihashmap_iterator_create (
 966   const struct GNUNET_CONTAINER_MultiHashMap *map);
 967
 968
 969 /**
 970  * @ingroup hashmap
 971  * Retrieve the next element from the hash map at the iterator's
 972  * position.  If there are no elements left, #GNUNET_NO is returned,
 973  * and @a key and @a value are not modified.  This operation is only
 974  * allowed if no elements have been removed from the multihashmap
 975  * since the creation of @a iter, and the map has not been destroyed.
 976  * Adding elements may result in repeating or skipping elements.
 977  *
 978  * @param iter the iterator to get the next element from
 979  * @param key pointer to store the key in, can be NULL
 980  * @param value pointer to store the value in, can be NULL
 981  * @return #GNUNET_YES we returned an element,
 982  *         #GNUNET_NO if we are out of elements
 983  */
 984 int
 985 GNUNET_CONTAINER_multihashmap_iterator_next (
 986   struct GNUNET_CONTAINER_MultiHashMapIterator *iter,
 987   struct GNUNET_HashCode *key,
 988   const void **value);
 989
 990
 991 /**
 992  * @ingroup hashmap
 993  * Destroy a multihashmap iterator.
 994  *
 995  * @param iter the iterator to destroy
 996  */
 997 void
 998 GNUNET_CONTAINER_multihashmap_iterator_destroy (
 999   struct GNUNET_CONTAINER_MultiHashMapIterator *iter);
1000
1001
1002 /**
1003  * @ingroup hashmap
1004  * Iterate over all entries in the map that match a particular key.
1005  *
1006  * @param map the map
1007  * @param key key that the entries must correspond to
1008  * @param it function to call on each entry
1009  * @param it_cls extra argument to @a it
1010  * @return the number of key value pairs processed,
1011  *         #GNUNET_SYSERR if it aborted iteration
1012  */
1013 int
1014 GNUNET_CONTAINER_multihashmap_get_multiple (
1015   struct GNUNET_CONTAINER_MultiHashMap *map,
1016   const struct GNUNET_HashCode *key,
1017   GNUNET_CONTAINER_MulitHashMapIteratorCallback it,
1018   void *it_cls);
1019
1020
1021 /**
1022  * @ingroup hashmap
1023  * Call @a it on a random value from the map, or not at all
1024  * if the map is empty.  Note that this function has linear
1025  * complexity (in the size of the map).
1026  *
1027  * @param map the map
1028  * @param it function to call on a random entry
1029  * @param it_cls extra argument to @a it
1030  * @return the number of key value pairs processed, zero or one.
1031  */
1032 unsigned int
1033 GNUNET_CONTAINER_multihashmap_get_random (
1034   const struct GNUNET_CONTAINER_MultiHashMap *map,
1035   GNUNET_CONTAINER_MulitHashMapIteratorCallback it,
1036   void *it_cls);
1037
1038
1039 /* ***************** Version of Multihashmap for peer identities ****************** */
1040
1041 /**
1042  * @ingroup hashmap
1043  * Iterator over hash map entries.
1044  *
1045  * @param cls closure
1046  * @param key current public key
1047  * @param value value in the hash map
1048  * @return #GNUNET_YES if we should continue to
1049  *         iterate,
1050  *         #GNUNET_NO if not.
1051  */
1052 typedef int (*GNUNET_CONTAINER_PeerMapIterator) (
1053   void *cls,
1054   const struct GNUNET_PeerIdentity *key,
1055   void *value);
1056
1057
1058 /**
1059  * Hash map from peer identities to values.
1060  */
1061 struct GNUNET_CONTAINER_MultiPeerMap;
1062
1063
1064 /**
1065  * @ingroup hashmap
1066  * Create a multi peer map (hash map for public keys of peers).
1067  *
1068  * @param len initial size (map will grow as needed)
1069  * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default;
1070  *                         #GNUNET_YES means that on 'put', the 'key' does not have
1071  *                         to be copied as the destination of the pointer is
1072  *                         guaranteed to be life as long as the value is stored in
1073  *                         the hashmap.  This can significantly reduce memory
1074  *                         consumption, but of course is also a recipie for
1075  *                         heap corruption if the assumption is not true.  Only
1076  *                         use this if (1) memory use is important in this case and
1077  *                         (2) you have triple-checked that the invariant holds
1078  * @return NULL on error
1079  */
1080 struct GNUNET_CONTAINER_MultiPeerMap *
1081 GNUNET_CONTAINER_multipeermap_create (unsigned int len, int do_not_copy_keys);
1082
1083
1084 /**
1085  * @ingroup hashmap
1086  * Destroy a hash map.  Will not free any values
1087  * stored in the hash map!
1088  *
1089  * @param map the map
1090  */
1091 void
1092 GNUNET_CONTAINER_multipeermap_destroy (
1093   struct GNUNET_CONTAINER_MultiPeerMap *map);
1094
1095
1096 /**
1097  * @ingroup hashmap
1098  * Given a key find a value in the map matching the key.
1099  *
1100  * @param map the map
1101  * @param key what to look for
1102  * @return NULL if no value was found; note that
1103  *   this is indistinguishable from values that just
1104  *   happen to be NULL; use "contains" to test for
1105  *   key-value pairs with value NULL
1106  */
1107 void *
1108 GNUNET_CONTAINER_multipeermap_get (
1109   const struct GNUNET_CONTAINER_MultiPeerMap *map,
1110   const struct GNUNET_PeerIdentity *key);
1111
1112
1113 /**
1114  * @ingroup hashmap
1115  * Remove the given key-value pair from the map.  Note that if the
1116  * key-value pair is in the map multiple times, only one of the pairs
1117  * will be removed.
1118  *
1119  * @param map the map
1120  * @param key key of the key-value pair
1121  * @param value value of the key-value pair
1122  * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
1123  *  is not in the map
1124  */
1125 int
1126 GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map,
1127                                       const struct GNUNET_PeerIdentity *key,
1128                                       const void *value);
1129
1130 /**
1131  * @ingroup hashmap
1132  * Remove all entries for the given key from the map.
1133  * Note that the values would not be "freed".
1134  *
1135  * @param map the map
1136  * @param key identifies values to be removed
1137  * @return number of values removed
1138  */
1139 int
1140 GNUNET_CONTAINER_multipeermap_remove_all (
1141   struct GNUNET_CONTAINER_MultiPeerMap *map,
1142   const struct GNUNET_PeerIdentity *key);
1143
1144
1145 /**
1146  * @ingroup hashmap
1147  * Check if the map contains any value under the given
1148  * key (including values that are NULL).
1149  *
1150  * @param map the map
1151  * @param key the key to test if a value exists for it
1152  * @return #GNUNET_YES if such a value exists,
1153  *         #GNUNET_NO if not
1154  */
1155 int
1156 GNUNET_CONTAINER_multipeermap_contains (
1157   const struct GNUNET_CONTAINER_MultiPeerMap *map,
1158   const struct GNUNET_PeerIdentity *key);
1159
1160
1161 /**
1162  * @ingroup hashmap
1163  * Check if the map contains the given value under the given
1164  * key.
1165  *
1166  * @param map the map
1167  * @param key the key to test if a value exists for it
1168  * @param value value to test for
1169  * @return #GNUNET_YES if such a value exists,
1170  *         #GNUNET_NO if not
1171  */
1172 int
1173 GNUNET_CONTAINER_multipeermap_contains_value (
1174   const struct GNUNET_CONTAINER_MultiPeerMap *map,
1175   const struct GNUNET_PeerIdentity *key,
1176   const void *value);
1177
1178
1179 /**
1180  * @ingroup hashmap
1181  * Store a key-value pair in the map.
1182  *
1183  * @param map the map
1184  * @param key key to use
1185  * @param value value to use
1186  * @param opt options for put
1187  * @return #GNUNET_OK on success,
1188  *         #GNUNET_NO if a value was replaced (with REPLACE)
1189  *         #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
1190  *                       value already exists
1191  */
1192 int
1193 GNUNET_CONTAINER_multipeermap_put (
1194   struct GNUNET_CONTAINER_MultiPeerMap *map,
1195   const struct GNUNET_PeerIdentity *key,
1196   void *value,
1197   enum GNUNET_CONTAINER_MultiHashMapOption opt);
1198
1199
1200 /**
1201  * @ingroup hashmap
1202  * Get the number of key-value pairs in the map.
1203  *
1204  * @param map the map
1205  * @return the number of key value pairs
1206  */
1207 unsigned int
1208 GNUNET_CONTAINER_multipeermap_size (
1209   const struct GNUNET_CONTAINER_MultiPeerMap *map);
1210
1211
1212 /**
1213  * @ingroup hashmap
1214  * Iterate over all entries in the map.
1215  *
1216  * @param map the map
1217  * @param it function to call on each entry
1218  * @param it_cls extra argument to @a it
1219  * @return the number of key value pairs processed,
1220  *         #GNUNET_SYSERR if it aborted iteration
1221  */
1222 int
1223 GNUNET_CONTAINER_multipeermap_iterate (
1224   struct GNUNET_CONTAINER_MultiPeerMap *map,
1225   GNUNET_CONTAINER_PeerMapIterator it,
1226   void *it_cls);
1227
1228
1229 struct GNUNET_CONTAINER_MultiPeerMapIterator;
1230 /**
1231  * @ingroup hashmap
1232  * Create an iterator for a multihashmap.
1233  * The iterator can be used to retrieve all the elements in the multihashmap
1234  * one by one, without having to handle all elements at once (in contrast to
1235  * #GNUNET_CONTAINER_multipeermap_iterate).  Note that the iterator can not be
1236  * used anymore if elements have been removed from @a map after the creation of
1237  * the iterator, or 'map' has been destroyed.  Adding elements to @a map may
1238  * result in skipped or repeated elements.
1239  *
1240  * @param map the map to create an iterator for
1241  * @return an iterator over the given multihashmap @a map
1242  */
1243 struct GNUNET_CONTAINER_MultiPeerMapIterator *
1244 GNUNET_CONTAINER_multipeermap_iterator_create (
1245   const struct GNUNET_CONTAINER_MultiPeerMap *map);
1246
1247
1248 /**
1249  * @ingroup hashmap
1250  * Retrieve the next element from the hash map at the iterator's
1251  * position.  If there are no elements left, #GNUNET_NO is returned,
1252  * and @a key and @a value are not modified.  This operation is only
1253  * allowed if no elements have been removed from the multihashmap
1254  * since the creation of @a iter, and the map has not been destroyed.
1255  * Adding elements may result in repeating or skipping elements.
1256  *
1257  * @param iter the iterator to get the next element from
1258  * @param key pointer to store the key in, can be NULL
1259  * @param value pointer to store the value in, can be NULL
1260  * @return #GNUNET_YES we returned an element,
1261  *         #GNUNET_NO if we are out of elements
1262  */
1263 int
1264 GNUNET_CONTAINER_multipeermap_iterator_next (
1265   struct GNUNET_CONTAINER_MultiPeerMapIterator *iter,
1266   struct GNUNET_PeerIdentity *key,
1267   const void **value);
1268
1269
1270 /**
1271  * @ingroup hashmap
1272  * Destroy a multipeermap iterator.
1273  *
1274  * @param iter the iterator to destroy
1275  */
1276 void
1277 GNUNET_CONTAINER_multipeermap_iterator_destroy (
1278   struct GNUNET_CONTAINER_MultiPeerMapIterator *iter);
1279
1280
1281 /**
1282  * @ingroup hashmap
1283  * Iterate over all entries in the map that match a particular key.
1284  *
1285  * @param map the map
1286  * @param key public key that the entries must correspond to
1287  * @param it function to call on each entry
1288  * @param it_cls extra argument to @a it
1289  * @return the number of key value pairs processed,
1290  *         #GNUNET_SYSERR if it aborted iteration
1291  */
1292 int
1293 GNUNET_CONTAINER_multipeermap_get_multiple (
1294   struct GNUNET_CONTAINER_MultiPeerMap *map,
1295   const struct GNUNET_PeerIdentity *key,
1296   GNUNET_CONTAINER_PeerMapIterator it,
1297   void *it_cls);
1298
1299
1300 /**
1301  * @ingroup hashmap
1302  * Call @a it on a random value from the map, or not at all
1303  * if the map is empty.  Note that this function has linear
1304  * complexity (in the size of the map).
1305  *
1306  * @param map the map
1307  * @param it function to call on a random entry
1308  * @param it_cls extra argument to @a it
1309  * @return the number of key value pairs processed, zero or one.
1310  */
1311 unsigned int
1312 GNUNET_CONTAINER_multipeermap_get_random (
1313   const struct GNUNET_CONTAINER_MultiPeerMap *map,
1314   GNUNET_CONTAINER_PeerMapIterator it,
1315   void *it_cls);
1316
1317
1318 /* ***************** Version of Multihashmap for short hashes ****************** */
1319
1320 /**
1321  * @ingroup hashmap
1322  * Iterator over hash map entries.
1323  *
1324  * @param cls closure
1325  * @param key current public key
1326  * @param value value in the hash map
1327  * @return #GNUNET_YES if we should continue to
1328  *         iterate,
1329  *         #GNUNET_NO if not.
1330  */
1331 typedef int (*GNUNET_CONTAINER_ShortmapIterator) (
1332   void *cls,
1333   const struct GNUNET_ShortHashCode *key,
1334   void *value);
1335
1336
1337 /**
1338  * Hash map from peer identities to values.
1339  */
1340 struct GNUNET_CONTAINER_MultiShortmap;
1341
1342
1343 /**
1344  * @ingroup hashmap
1345  * Create a multi peer map (hash map for public keys of peers).
1346  *
1347  * @param len initial size (map will grow as needed)
1348  * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default;
1349  *                         #GNUNET_YES means that on 'put', the 'key' does not have
1350  *                         to be copied as the destination of the pointer is
1351  *                         guaranteed to be life as long as the value is stored in
1352  *                         the hashmap.  This can significantly reduce memory
1353  *                         consumption, but of course is also a recipie for
1354  *                         heap corruption if the assumption is not true.  Only
1355  *                         use this if (1) memory use is important in this case and
1356  *                         (2) you have triple-checked that the invariant holds
1357  * @return NULL on error
1358  */
1359 struct GNUNET_CONTAINER_MultiShortmap *
1360 GNUNET_CONTAINER_multishortmap_create (unsigned int len, int do_not_copy_keys);
1361
1362
1363 /**
1364  * @ingroup hashmap
1365  * Destroy a hash map.  Will not free any values
1366  * stored in the hash map!
1367  *
1368  * @param map the map
1369  */
1370 void
1371 GNUNET_CONTAINER_multishortmap_destroy (
1372   struct GNUNET_CONTAINER_MultiShortmap *map);
1373
1374
1375 /**
1376  * @ingroup hashmap
1377  * Given a key find a value in the map matching the key.
1378  *
1379  * @param map the map
1380  * @param key what to look for
1381  * @return NULL if no value was found; note that
1382  *   this is indistinguishable from values that just
1383  *   happen to be NULL; use "contains" to test for
1384  *   key-value pairs with value NULL
1385  */
1386 void *
1387 GNUNET_CONTAINER_multishortmap_get (
1388   const struct GNUNET_CONTAINER_MultiShortmap *map,
1389   const struct GNUNET_ShortHashCode *key);
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_multishortmap_remove (
1406   struct GNUNET_CONTAINER_MultiShortmap *map,
1407   const struct GNUNET_ShortHashCode *key,
1408   const void *value);
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_multishortmap_remove_all (
1421   struct GNUNET_CONTAINER_MultiShortmap *map,
1422   const struct GNUNET_ShortHashCode *key);
1423
1424
1425 /**
1426  * @ingroup hashmap
1427  * Check if the map contains any value under the given
1428  * key (including values that are NULL).
1429  *
1430  * @param map the map
1431  * @param key the key to test if a value exists for it
1432  * @return #GNUNET_YES if such a value exists,
1433  *         #GNUNET_NO if not
1434  */
1435 int
1436 GNUNET_CONTAINER_multishortmap_contains (
1437   const struct GNUNET_CONTAINER_MultiShortmap *map,
1438   const struct GNUNET_ShortHashCode *key);
1439
1440
1441 /**
1442  * @ingroup hashmap
1443  * Check if the map contains the given value under the given
1444  * key.
1445  *
1446  * @param map the map
1447  * @param key the key to test if a value exists for it
1448  * @param value value to test for
1449  * @return #GNUNET_YES if such a value exists,
1450  *         #GNUNET_NO if not
1451  */
1452 int
1453 GNUNET_CONTAINER_multishortmap_contains_value (
1454   const struct GNUNET_CONTAINER_MultiShortmap *map,
1455   const struct GNUNET_ShortHashCode *key,
1456   const void *value);
1457
1458
1459 /**
1460  * @ingroup hashmap
1461  * Store a key-value pair in the map.
1462  *
1463  * @param map the map
1464  * @param key key to use
1465  * @param value value to use
1466  * @param opt options for put
1467  * @return #GNUNET_OK on success,
1468  *         #GNUNET_NO if a value was replaced (with REPLACE)
1469  *         #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
1470  *                       value already exists
1471  */
1472 int
1473 GNUNET_CONTAINER_multishortmap_put (
1474   struct GNUNET_CONTAINER_MultiShortmap *map,
1475   const struct GNUNET_ShortHashCode *key,
1476   void *value,
1477   enum GNUNET_CONTAINER_MultiHashMapOption opt);
1478
1479
1480 /**
1481  * @ingroup hashmap
1482  * Get the number of key-value pairs in the map.
1483  *
1484  * @param map the map
1485  * @return the number of key value pairs
1486  */
1487 unsigned int
1488 GNUNET_CONTAINER_multishortmap_size (
1489   const struct GNUNET_CONTAINER_MultiShortmap *map);
1490
1491
1492 /**
1493  * @ingroup hashmap
1494  * Iterate over all entries in the map.
1495  *
1496  * @param map the map
1497  * @param it function to call on each entry
1498  * @param it_cls extra argument to @a it
1499  * @return the number of key value pairs processed,
1500  *         #GNUNET_SYSERR if it aborted iteration
1501  */
1502 int
1503 GNUNET_CONTAINER_multishortmap_iterate (
1504   struct GNUNET_CONTAINER_MultiShortmap *map,
1505   GNUNET_CONTAINER_ShortmapIterator it,
1506   void *it_cls);
1507
1508
1509 struct GNUNET_CONTAINER_MultiShortmapIterator;
1510
1511
1512 /**
1513  * @ingroup hashmap
1514  * Create an iterator for a multihashmap.
1515  * The iterator can be used to retrieve all the elements in the multihashmap
1516  * one by one, without having to handle all elements at once (in contrast to
1517  * #GNUNET_CONTAINER_multishortmap_iterate).  Note that the iterator can not be
1518  * used anymore if elements have been removed from @a map after the creation of
1519  * the iterator, or 'map' has been destroyed.  Adding elements to @a map may
1520  * result in skipped or repeated elements.
1521  *
1522  * @param map the map to create an iterator for
1523  * @return an iterator over the given multihashmap @a map
1524  */
1525 struct GNUNET_CONTAINER_MultiShortmapIterator *
1526 GNUNET_CONTAINER_multishortmap_iterator_create (
1527   const struct GNUNET_CONTAINER_MultiShortmap *map);
1528
1529
1530 /**
1531  * @ingroup hashmap
1532  * Retrieve the next element from the hash map at the iterator's
1533  * position.  If there are no elements left, #GNUNET_NO is returned,
1534  * and @a key and @a value are not modified.  This operation is only
1535  * allowed if no elements have been removed from the multihashmap
1536  * since the creation of @a iter, and the map has not been destroyed.
1537  * Adding elements may result in repeating or skipping elements.
1538  *
1539  * @param iter the iterator to get the next element from
1540  * @param key pointer to store the key in, can be NULL
1541  * @param value pointer to store the value in, can be NULL
1542  * @return #GNUNET_YES we returned an element,
1543  *         #GNUNET_NO if we are out of elements
1544  */
1545 int
1546 GNUNET_CONTAINER_multishortmap_iterator_next (
1547   struct GNUNET_CONTAINER_MultiShortmapIterator *iter,
1548   struct GNUNET_ShortHashCode *key,
1549   const void **value);
1550
1551
1552 /**
1553  * @ingroup hashmap
1554  * Destroy a multishortmap iterator.
1555  *
1556  * @param iter the iterator to destroy
1557  */
1558 void
1559 GNUNET_CONTAINER_multishortmap_iterator_destroy (
1560   struct GNUNET_CONTAINER_MultiShortmapIterator *iter);
1561
1562
1563 /**
1564  * @ingroup hashmap
1565  * Iterate over all entries in the map that match a particular key.
1566  *
1567  * @param map the map
1568  * @param key public key that the entries must correspond to
1569  * @param it function to call on each entry
1570  * @param it_cls extra argument to @a it
1571  * @return the number of key value pairs processed,
1572  *         #GNUNET_SYSERR if it aborted iteration
1573  */
1574 int
1575 GNUNET_CONTAINER_multishortmap_get_multiple (
1576   struct GNUNET_CONTAINER_MultiShortmap *map,
1577   const struct GNUNET_ShortHashCode *key,
1578   GNUNET_CONTAINER_ShortmapIterator it,
1579   void *it_cls);
1580
1581
1582 /**
1583  * @ingroup hashmap
1584  * Call @a it on a random value from the map, or not at all
1585  * if the map is empty.  Note that this function has linear
1586  * complexity (in the size of the map).
1587  *
1588  * @param map the map
1589  * @param it function to call on a random entry
1590  * @param it_cls extra argument to @a it
1591  * @return the number of key value pairs processed, zero or one.
1592  */
1593 unsigned int
1594 GNUNET_CONTAINER_multishortmap_get_random (
1595   const struct GNUNET_CONTAINER_MultiShortmap *map,
1596   GNUNET_CONTAINER_ShortmapIterator it,
1597   void *it_cls);
1598
1599
1600 /* ***************** Version of Multihashmap for UUIDs ****************** */
1601
1602
1603 /**
1604  * @ingroup hashmap
1605  * Iterator over uuid map entries.
1606  *
1607  * @param cls closure
1608  * @param key current public key
1609  * @param value value in the hash map
1610  * @return #GNUNET_YES if we should continue to
1611  *         iterate,
1612  *         #GNUNET_NO if not.
1613  */
1614 typedef int (*GNUNET_CONTAINER_MultiUuidmapIteratorCallback) (
1615   void *cls,
1616   const struct GNUNET_Uuid *key,
1617   void *value);
1618
1619
1620 /**
1621  * Hash map from peer identities to values.
1622  */
1623 struct GNUNET_CONTAINER_MultiUuidmap;
1624
1625
1626 /**
1627  * @ingroup hashmap
1628  * Create a multi peer map (hash map for public keys of peers).
1629  *
1630  * @param len initial size (map will grow as needed)
1631  * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default;
1632  *                         #GNUNET_YES means that on 'put', the 'key' does not have
1633  *                         to be copied as the destination of the pointer is
1634  *                         guaranteed to be life as long as the value is stored in
1635  *                         the hashmap.  This can significantly reduce memory
1636  *                         consumption, but of course is also a recipie for
1637  *                         heap corruption if the assumption is not true.  Only
1638  *                         use this if (1) memory use is important in this case and
1639  *                         (2) you have triple-checked that the invariant holds
1640  * @return NULL on error
1641  */
1642 struct GNUNET_CONTAINER_MultiUuidmap *
1643 GNUNET_CONTAINER_multiuuidmap_create (unsigned int len, int do_not_copy_keys);
1644
1645
1646 /**
1647  * @ingroup hashmap
1648  * Destroy a hash map.  Will not free any values
1649  * stored in the hash map!
1650  *
1651  * @param map the map
1652  */
1653 void
1654 GNUNET_CONTAINER_multiuuidmap_destroy (
1655   struct GNUNET_CONTAINER_MultiUuidmap *map);
1656
1657
1658 /**
1659  * @ingroup hashmap
1660  * Given a key find a value in the map matching the key.
1661  *
1662  * @param map the map
1663  * @param key what to look for
1664  * @return NULL if no value was found; note that
1665  *   this is indistinguishable from values that just
1666  *   happen to be NULL; use "contains" to test for
1667  *   key-value pairs with value NULL
1668  */
1669 void *
1670 GNUNET_CONTAINER_multiuuidmap_get (
1671   const struct GNUNET_CONTAINER_MultiUuidmap *map,
1672   const struct GNUNET_Uuid *key);
1673
1674
1675 /**
1676  * @ingroup hashmap
1677  * Remove the given key-value pair from the map.  Note that if the
1678  * key-value pair is in the map multiple times, only one of the pairs
1679  * will be removed.
1680  *
1681  * @param map the map
1682  * @param key key of the key-value pair
1683  * @param value value of the key-value pair
1684  * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
1685  *  is not in the map
1686  */
1687 int
1688 GNUNET_CONTAINER_multiuuidmap_remove (struct GNUNET_CONTAINER_MultiUuidmap *map,
1689                                       const struct GNUNET_Uuid *key,
1690                                       const void *value);
1691
1692 /**
1693  * @ingroup hashmap
1694  * Remove all entries for the given key from the map.
1695  * Note that the values would not be "freed".
1696  *
1697  * @param map the map
1698  * @param key identifies values to be removed
1699  * @return number of values removed
1700  */
1701 int
1702 GNUNET_CONTAINER_multiuuidmap_remove_all (
1703   struct GNUNET_CONTAINER_MultiUuidmap *map,
1704   const struct GNUNET_Uuid *key);
1705
1706
1707 /**
1708  * @ingroup hashmap
1709  * Check if the map contains any value under the given
1710  * key (including values that are NULL).
1711  *
1712  * @param map the map
1713  * @param key the key to test if a value exists for it
1714  * @return #GNUNET_YES if such a value exists,
1715  *         #GNUNET_NO if not
1716  */
1717 int
1718 GNUNET_CONTAINER_multiuuidmap_contains (
1719   const struct GNUNET_CONTAINER_MultiUuidmap *map,
1720   const struct GNUNET_Uuid *key);
1721
1722
1723 /**
1724  * @ingroup hashmap
1725  * Check if the map contains the given value under the given
1726  * key.
1727  *
1728  * @param map the map
1729  * @param key the key to test if a value exists for it
1730  * @param value value to test for
1731  * @return #GNUNET_YES if such a value exists,
1732  *         #GNUNET_NO if not
1733  */
1734 int
1735 GNUNET_CONTAINER_multiuuidmap_contains_value (
1736   const struct GNUNET_CONTAINER_MultiUuidmap *map,
1737   const struct GNUNET_Uuid *key,
1738   const void *value);
1739
1740
1741 /**
1742  * @ingroup hashmap
1743  * Store a key-value pair in the map.
1744  *
1745  * @param map the map
1746  * @param key key to use
1747  * @param value value to use
1748  * @param opt options for put
1749  * @return #GNUNET_OK on success,
1750  *         #GNUNET_NO if a value was replaced (with REPLACE)
1751  *         #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
1752  *                       value already exists
1753  */
1754 int
1755 GNUNET_CONTAINER_multiuuidmap_put (
1756   struct GNUNET_CONTAINER_MultiUuidmap *map,
1757   const struct GNUNET_Uuid *key,
1758   void *value,
1759   enum GNUNET_CONTAINER_MultiHashMapOption opt);
1760
1761
1762 /**
1763  * @ingroup hashmap
1764  * Get the number of key-value pairs in the map.
1765  *
1766  * @param map the map
1767  * @return the number of key value pairs
1768  */
1769 unsigned int
1770 GNUNET_CONTAINER_multiuuidmap_size (
1771   const struct GNUNET_CONTAINER_MultiUuidmap *map);
1772
1773
1774 /**
1775  * @ingroup hashmap
1776  * Iterate over all entries in the map.
1777  *
1778  * @param map the map
1779  * @param it function to call on each entry
1780  * @param it_cls extra argument to @a it
1781  * @return the number of key value pairs processed,
1782  *         #GNUNET_SYSERR if it aborted iteration
1783  */
1784 int
1785 GNUNET_CONTAINER_multiuuidmap_iterate (
1786   struct GNUNET_CONTAINER_MultiUuidmap *map,
1787   GNUNET_CONTAINER_MultiUuidmapIteratorCallback it,
1788   void *it_cls);
1789
1790
1791 struct GNUNET_CONTAINER_MultiUuidmapIterator;
1792
1793
1794 /**
1795  * @ingroup hashmap
1796  * Create an iterator for a multihashmap.
1797  * The iterator can be used to retrieve all the elements in the multihashmap
1798  * one by one, without having to handle all elements at once (in contrast to
1799  * #GNUNET_CONTAINER_multiuuidmap_iterate).  Note that the iterator can not be
1800  * used anymore if elements have been removed from @a map after the creation of
1801  * the iterator, or 'map' has been destroyed.  Adding elements to @a map may
1802  * result in skipped or repeated elements.
1803  *
1804  * @param map the map to create an iterator for
1805  * @return an iterator over the given multihashmap @a map
1806  */
1807 struct GNUNET_CONTAINER_MultiUuidmapIterator *
1808 GNUNET_CONTAINER_multiuuidmap_iterator_create (
1809   const struct GNUNET_CONTAINER_MultiUuidmap *map);
1810
1811
1812 /**
1813  * @ingroup hashmap
1814  * Retrieve the next element from the hash map at the iterator's
1815  * position.  If there are no elements left, #GNUNET_NO is returned,
1816  * and @a key and @a value are not modified.  This operation is only
1817  * allowed if no elements have been removed from the multihashmap
1818  * since the creation of @a iter, and the map has not been destroyed.
1819  * Adding elements may result in repeating or skipping elements.
1820  *
1821  * @param iter the iterator to get the next element from
1822  * @param key pointer to store the key in, can be NULL
1823  * @param value pointer to store the value in, can be NULL
1824  * @return #GNUNET_YES we returned an element,
1825  *         #GNUNET_NO if we are out of elements
1826  */
1827 int
1828 GNUNET_CONTAINER_multiuuidmap_iterator_next (
1829   struct GNUNET_CONTAINER_MultiUuidmapIterator *iter,
1830   struct GNUNET_Uuid *key,
1831   const void **value);
1832
1833
1834 /**
1835  * @ingroup hashmap
1836  * Destroy a multiuuidmap iterator.
1837  *
1838  * @param iter the iterator to destroy
1839  */
1840 void
1841 GNUNET_CONTAINER_multiuuidmap_iterator_destroy (
1842   struct GNUNET_CONTAINER_MultiUuidmapIterator *iter);
1843
1844
1845 /**
1846  * @ingroup hashmap
1847  * Iterate over all entries in the map that match a particular key.
1848  *
1849  * @param map the map
1850  * @param key public key that the entries must correspond to
1851  * @param it function to call on each entry
1852  * @param it_cls extra argument to @a it
1853  * @return the number of key value pairs processed,
1854  *         #GNUNET_SYSERR if it aborted iteration
1855  */
1856 int
1857 GNUNET_CONTAINER_multiuuidmap_get_multiple (
1858   struct GNUNET_CONTAINER_MultiUuidmap *map,
1859   const struct GNUNET_Uuid *key,
1860   GNUNET_CONTAINER_MultiUuidmapIteratorCallback it,
1861   void *it_cls);
1862
1863
1864 /**
1865  * @ingroup hashmap
1866  * Call @a it on a random value from the map, or not at all
1867  * if the map is empty.  Note that this function has linear
1868  * complexity (in the size of the map).
1869  *
1870  * @param map the map
1871  * @param it function to call on a random entry
1872  * @param it_cls extra argument to @a it
1873  * @return the number of key value pairs processed, zero or one.
1874  */
1875 unsigned int
1876 GNUNET_CONTAINER_multiuuidmap_get_random (
1877   const struct GNUNET_CONTAINER_MultiUuidmap *map,
1878   GNUNET_CONTAINER_MultiUuidmapIteratorCallback it,
1879   void *it_cls);
1880
1881
1882 /* Version of multihashmap with 32 bit keys */
1883
1884 /**
1885  * @ingroup hashmap
1886  * Opaque handle for the 32-bit key HashMap.
1887  */
1888 struct GNUNET_CONTAINER_MultiHashMap32;
1889
1890
1891 /**
1892  * @ingroup hashmap
1893  * Opaque handle to an iterator over
1894  * a 32-bit key multihashmap.
1895  */
1896 struct GNUNET_CONTAINER_MultiHashMap32Iterator;
1897
1898
1899 /**
1900  * @ingroup hashmap
1901  * Iterator over hash map entries.
1902  *
1903  * @param cls closure
1904  * @param key current key code
1905  * @param value value in the hash map
1906  * @return #GNUNET_YES if we should continue to
1907  *         iterate,
1908  *         #GNUNET_NO if not.
1909  */
1910 typedef int (*GNUNET_CONTAINER_MulitHashMapIterator32Callback) (void *cls,
1911                                                                 uint32_t key,
1912                                                                 void *value);
1913
1914
1915 /**
1916  * @ingroup hashmap
1917  * Create a 32-bit key multi hash map.
1918  *
1919  * @param len initial size (map will grow as needed)
1920  * @return NULL on error
1921  */
1922 struct GNUNET_CONTAINER_MultiHashMap32 *
1923 GNUNET_CONTAINER_multihashmap32_create (unsigned int len);
1924
1925
1926 /**
1927  * @ingroup hashmap
1928  * Destroy a 32-bit key hash map.  Will not free any values
1929  * stored in the hash map!
1930  *
1931  * @param map the map
1932  */
1933 void
1934 GNUNET_CONTAINER_multihashmap32_destroy (
1935   struct GNUNET_CONTAINER_MultiHashMap32 *map);
1936
1937
1938 /**
1939  * @ingroup hashmap
1940  * Get the number of key-value pairs in the map.
1941  *
1942  * @param map the map
1943  * @return the number of key value pairs
1944  */
1945 unsigned int
1946 GNUNET_CONTAINER_multihashmap32_size (
1947   const struct GNUNET_CONTAINER_MultiHashMap32 *map);
1948
1949
1950 /**
1951  * @ingroup hashmap
1952  * Given a key find a value in the map matching the key.
1953  *
1954  * @param map the map
1955  * @param key what to look for
1956  * @return NULL if no value was found; note that
1957  *   this is indistinguishable from values that just
1958  *   happen to be NULL; use "contains" to test for
1959  *   key-value pairs with value NULL
1960  */
1961 void *
1962 GNUNET_CONTAINER_multihashmap32_get (
1963   const struct GNUNET_CONTAINER_MultiHashMap32 *map,
1964   uint32_t key);
1965
1966
1967 /**
1968  * @ingroup hashmap
1969  * Iterate over all entries in the map.
1970  *
1971  * @param map the map
1972  * @param it function to call on each entry
1973  * @param it_cls extra argument to @a it
1974  * @return the number of key value pairs processed,
1975  *         #GNUNET_SYSERR if it aborted iteration
1976  */
1977 int
1978 GNUNET_CONTAINER_multihashmap32_iterate (
1979   struct GNUNET_CONTAINER_MultiHashMap32 *map,
1980   GNUNET_CONTAINER_MulitHashMapIterator32Callback it,
1981   void *it_cls);
1982
1983
1984 /**
1985  * @ingroup hashmap
1986  * Remove the given key-value pair from the map.  Note that if the
1987  * key-value pair is in the map multiple times, only one of the pairs
1988  * will be removed.
1989  *
1990  * @param map the map
1991  * @param key key of the key-value pair
1992  * @param value value of the key-value pair
1993  * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
1994  *  is not in the map
1995  */
1996 int
1997 GNUNET_CONTAINER_multihashmap32_remove (
1998   struct GNUNET_CONTAINER_MultiHashMap32 *map,
1999   uint32_t key,
2000   const void *value);
2001
2002
2003 /**
2004  * @ingroup hashmap
2005  * Remove all entries for the given key from the map.
2006  * Note that the values would not be "freed".
2007  *
2008  * @param map the map
2009  * @param key identifies values to be removed
2010  * @return number of values removed
2011  */
2012 int
2013 GNUNET_CONTAINER_multihashmap32_remove_all (
2014   struct GNUNET_CONTAINER_MultiHashMap32 *map,
2015   uint32_t key);
2016
2017
2018 /**
2019  * @ingroup hashmap
2020  * Check if the map contains any value under the given
2021  * key (including values that are NULL).
2022  *
2023  * @param map the map
2024  * @param key the key to test if a value exists for it
2025  * @return #GNUNET_YES if such a value exists,
2026  *         #GNUNET_NO if not
2027  */
2028 int
2029 GNUNET_CONTAINER_multihashmap32_contains (
2030   const struct GNUNET_CONTAINER_MultiHashMap32 *map,
2031   uint32_t key);
2032
2033
2034 /**
2035  * @ingroup hashmap
2036  * Check if the map contains the given value under the given
2037  * key.
2038  *
2039  * @param map the map
2040  * @param key the key to test if a value exists for it
2041  * @param value value to test for
2042  * @return #GNUNET_YES if such a value exists,
2043  *         #GNUNET_NO if not
2044  */
2045 int
2046 GNUNET_CONTAINER_multihashmap32_contains_value (
2047   const struct GNUNET_CONTAINER_MultiHashMap32 *map,
2048   uint32_t key,
2049   const void *value);
2050
2051
2052 /**
2053  * @ingroup hashmap
2054  * Store a key-value pair in the map.
2055  *
2056  * @param map the map
2057  * @param key key to use
2058  * @param value value to use
2059  * @param opt options for put
2060  * @return #GNUNET_OK on success,
2061  *         #GNUNET_NO if a value was replaced (with REPLACE)
2062  *         #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
2063  *                       value already exists
2064  */
2065 int
2066 GNUNET_CONTAINER_multihashmap32_put (
2067   struct GNUNET_CONTAINER_MultiHashMap32 *map,
2068   uint32_t key,
2069   void *value,
2070   enum GNUNET_CONTAINER_MultiHashMapOption opt);
2071
2072
2073 /**
2074  * @ingroup hashmap
2075  * Iterate over all entries in the map that match a particular key.
2076  *
2077  * @param map the map
2078  * @param key key that the entries must correspond to
2079  * @param it function to call on each entry
2080  * @param it_cls extra argument to @a it
2081  * @return the number of key value pairs processed,
2082  *         #GNUNET_SYSERR if it aborted iteration
2083  */
2084 int
2085 GNUNET_CONTAINER_multihashmap32_get_multiple (
2086   struct GNUNET_CONTAINER_MultiHashMap32 *map,
2087   uint32_t key,
2088   GNUNET_CONTAINER_MulitHashMapIterator32Callback it,
2089   void *it_cls);
2090
2091
2092 /**
2093  * Create an iterator for a 32-bit multihashmap.
2094  * The iterator can be used to retrieve all the elements in the multihashmap
2095  * one by one, without having to handle all elements at once (in contrast to
2096  * #GNUNET_CONTAINER_multihashmap32_iterate).  Note that the iterator can not be
2097  * used anymore if elements have been removed from 'map' after the creation of
2098  * the iterator, or 'map' has been destroyed.  Adding elements to 'map' may
2099  * result in skipped or repeated elements.
2100  *
2101  * @param map the map to create an iterator for
2102  * @return an iterator over the given multihashmap map
2103  */
2104 struct GNUNET_CONTAINER_MultiHashMap32Iterator *
2105 GNUNET_CONTAINER_multihashmap32_iterator_create (
2106   const struct GNUNET_CONTAINER_MultiHashMap32 *map);
2107
2108
2109 /**
2110  * Retrieve the next element from the hash map at the iterator's position.
2111  * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
2112  * are not modified.
2113  * This operation is only allowed if no elements have been removed from the
2114  * multihashmap since the creation of 'iter', and the map has not been destroyed.
2115  * Adding elements may result in repeating or skipping elements.
2116  *
2117  * @param iter the iterator to get the next element from
2118  * @param key pointer to store the key in, can be NULL
2119  * @param value pointer to store the value in, can be NULL
2120  * @return #GNUNET_YES we returned an element,
2121  *         #GNUNET_NO if we are out of elements
2122  */
2123 int
2124 GNUNET_CONTAINER_multihashmap32_iterator_next (
2125   struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter,
2126   uint32_t *key,
2127   const void **value);
2128
2129
2130 /**
2131  * Destroy a 32-bit multihashmap iterator.
2132  *
2133  * @param iter the iterator to destroy
2134  */
2135 void
2136 GNUNET_CONTAINER_multihashmap32_iterator_destroy (
2137   struct GNUNET_CONTAINER_MultiHashMapIterator *iter);
2138
2139
2140 /* ******************** doubly-linked list *************** */
2141 /* To avoid mistakes: head->prev == tail->next == NULL     */
2142
2143 /**
2144  * @ingroup dll
2145  * Insert an element at the head of a DLL. Assumes that head, tail and
2146  * element are structs with prev and next fields.
2147  *
2148  * @param head pointer to the head of the DLL
2149  * @param tail pointer to the tail of the DLL
2150  * @param element element to insert
2151  */
2152 #define GNUNET_CONTAINER_DLL_insert(head, tail, element)                \
2153   do                                                                    \
2154   {                                                                     \
2155     GNUNET_assert (((element)->prev == NULL) && ((head) != (element))); \
2156     GNUNET_assert (((element)->next == NULL) && ((tail) != (element))); \
2157     (element)->next = (head);                                           \
2158     (element)->prev = NULL;                                             \
2159     if ((tail) == NULL)                                                 \
2160       (tail) = element;                                                 \
2161     else                                                                \
2162       (head)->prev = element;                                           \
2163     (head) = (element);                                                 \
2164   } while (0)
2165
2166
2167 /**
2168  * @ingroup dll
2169  * Insert an element at the tail of a DLL. Assumes that head, tail and
2170  * element are structs with prev and next fields.
2171  *
2172  * @param head pointer to the head of the DLL
2173  * @param tail pointer to the tail of the DLL
2174  * @param element element to insert
2175  */
2176 #define GNUNET_CONTAINER_DLL_insert_tail(head, tail, element)           \
2177   do                                                                    \
2178   {                                                                     \
2179     GNUNET_assert (((element)->prev == NULL) && ((head) != (element))); \
2180     GNUNET_assert (((element)->next == NULL) && ((tail) != (element))); \
2181     (element)->prev = (tail);                                           \
2182     (element)->next = NULL;                                             \
2183     if ((head) == NULL)                                                 \
2184       (head) = element;                                                 \
2185     else                                                                \
2186       (tail)->next = element;                                           \
2187     (tail) = (element);                                                 \
2188   } while (0)
2189
2190
2191 /**
2192  * @ingroup dll
2193  * Insert an element into a DLL after the given other element.  Insert
2194  * at the head if the other element is NULL.
2195  *
2196  * @param head pointer to the head of the DLL
2197  * @param tail pointer to the tail of the DLL
2198  * @param other prior element, NULL for insertion at head of DLL
2199  * @param element element to insert
2200  */
2201 #define GNUNET_CONTAINER_DLL_insert_after(head, tail, other, element)   \
2202   do                                                                    \
2203   {                                                                     \
2204     GNUNET_assert (((element)->prev == NULL) && ((head) != (element))); \
2205     GNUNET_assert (((element)->next == NULL) && ((tail) != (element))); \
2206     (element)->prev = (other);                                          \
2207     if (NULL == other)                                                  \
2208     {                                                                   \
2209       (element)->next = (head);                                         \
2210       (head) = (element);                                               \
2211     }                                                                   \
2212     else                                                                \
2213     {                                                                   \
2214       (element)->next = (other)->next;                                  \
2215       (other)->next = (element);                                        \
2216     }                                                                   \
2217     if (NULL == (element)->next)                                        \
2218       (tail) = (element);                                               \
2219     else                                                                \
2220       (element)->next->prev = (element);                                \
2221   } while (0)
2222
2223
2224 /**
2225  * @ingroup dll
2226  * Insert an element into a DLL before the given other element.  Insert
2227  * at the tail if the other element is NULL.
2228  *
2229  * @param head pointer to the head of the DLL
2230  * @param tail pointer to the tail of the DLL
2231  * @param other prior element, NULL for insertion at head of DLL
2232  * @param element element to insert
2233  */
2234 #define GNUNET_CONTAINER_DLL_insert_before(head, tail, other, element)  \
2235   do                                                                    \
2236   {                                                                     \
2237     GNUNET_assert (((element)->prev == NULL) && ((head) != (element))); \
2238     GNUNET_assert (((element)->next == NULL) && ((tail) != (element))); \
2239     (element)->next = (other);                                          \
2240     if (NULL == other)                                                  \
2241     {                                                                   \
2242       (element)->prev = (tail);                                         \
2243       (tail) = (element);                                               \
2244     }                                                                   \
2245     else                                                                \
2246     {                                                                   \
2247       (element)->prev = (other)->prev;                                  \
2248       (other)->prev = (element);                                        \
2249     }                                                                   \
2250     if (NULL == (element)->prev)                                        \
2251       (head) = (element);                                               \
2252     else                                                                \
2253       (element)->prev->next = (element);                                \
2254   } while (0)
2255
2256
2257 /**
2258  * @ingroup dll
2259  * Remove an element from a DLL. Assumes that head, tail and
2260  * element point to structs with prev and next fields.
2261  *
2262  * Using the head or tail pointer as the element
2263  * argument does NOT work with this macro.
2264  * Make sure to store head/tail in another pointer
2265  * and use it to remove the head or tail of the list.
2266  *
2267  * @param head pointer to the head of the DLL
2268  * @param tail pointer to the tail of the DLL
2269  * @param element element to remove
2270  */
2271 #define GNUNET_CONTAINER_DLL_remove(head, tail, element)                \
2272   do                                                                    \
2273   {                                                                     \
2274     GNUNET_assert (((element)->prev != NULL) || ((head) == (element))); \
2275     GNUNET_assert (((element)->next != NULL) || ((tail) == (element))); \
2276     if ((element)->prev == NULL)                                        \
2277       (head) = (element)->next;                                         \
2278     else                                                                \
2279       (element)->prev->next = (element)->next;                          \
2280     if ((element)->next == NULL)                                        \
2281       (tail) = (element)->prev;                                         \
2282     else                                                                \
2283       (element)->next->prev = (element)->prev;                          \
2284     (element)->next = NULL;                                             \
2285     (element)->prev = NULL;                                             \
2286   } while (0)
2287
2288
2289 /* ************ Multi-DLL interface, allows DLL elements to be
2290    in multiple lists at the same time *********************** */
2291
2292 /**
2293  * @ingroup dll
2294  * Insert an element at the head of a MDLL. Assumes that head, tail and
2295  * element are structs with prev and next fields.
2296  *
2297  * @param mdll suffix name for the next and prev pointers in the element
2298  * @param head pointer to the head of the MDLL
2299  * @param tail pointer to the tail of the MDLL
2300  * @param element element to insert
2301  */
2302 #define GNUNET_CONTAINER_MDLL_insert(mdll, head, tail, element)                \
2303   do                                                                           \
2304   {                                                                            \
2305     GNUNET_assert (((element)->prev_ ## mdll == NULL) && ((head) != (element))); \
2306     GNUNET_assert (((element)->next_ ## mdll == NULL) && ((tail) != (element))); \
2307     (element)->next_ ## mdll = (head);                                           \
2308     (element)->prev_ ## mdll = NULL;                                             \
2309     if ((tail) == NULL)                                                        \
2310       (tail) = element;                                                        \
2311     else                                                                       \
2312       (head)->prev_ ## mdll = element;                                           \
2313     (head) = (element);                                                        \
2314   } while (0)
2315
2316
2317 /**
2318  * @ingroup dll
2319  * Insert an element at the tail of a MDLL. Assumes that head, tail and
2320  * element are structs with prev and next fields.
2321  *
2322  * @param mdll suffix name for the next and prev pointers in the element
2323  * @param head pointer to the head of the MDLL
2324  * @param tail pointer to the tail of the MDLL
2325  * @param element element to insert
2326  */
2327 #define GNUNET_CONTAINER_MDLL_insert_tail(mdll, head, tail, element)           \
2328   do                                                                           \
2329   {                                                                            \
2330     GNUNET_assert (((element)->prev_ ## mdll == NULL) && ((head) != (element))); \
2331     GNUNET_assert (((element)->next_ ## mdll == NULL) && ((tail) != (element))); \
2332     (element)->prev_ ## mdll = (tail);                                           \
2333     (element)->next_ ## mdll = NULL;                                             \
2334     if ((head) == NULL)                                                        \
2335       (head) = element;                                                        \
2336     else                                                                       \
2337       (tail)->next_ ## mdll = element;                                           \
2338     (tail) = (element);                                                        \
2339   } while (0)
2340
2341
2342 /**
2343  * @ingroup dll
2344  * Insert an element into a MDLL after the given other element.  Insert
2345  * at the head if the other element is NULL.
2346  *
2347  * @param mdll suffix name for the next and prev pointers in the element
2348  * @param head pointer to the head of the MDLL
2349  * @param tail pointer to the tail of the MDLL
2350  * @param other prior element, NULL for insertion at head of MDLL
2351  * @param element element to insert
2352  */
2353 #define GNUNET_CONTAINER_MDLL_insert_after(mdll, head, tail, other, element)   \
2354   do                                                                           \
2355   {                                                                            \
2356     GNUNET_assert (((element)->prev_ ## mdll == NULL) && ((head) != (element))); \
2357     GNUNET_assert (((element)->next_ ## mdll == NULL) && ((tail) != (element))); \
2358     (element)->prev_ ## mdll = (other);                                          \
2359     if (NULL == other)                                                         \
2360     {                                                                          \
2361       (element)->next_ ## mdll = (head);                                         \
2362       (head) = (element);                                                      \
2363     }                                                                          \
2364     else                                                                       \
2365     {                                                                          \
2366       (element)->next_ ## mdll = (other)->next_ ## mdll;                           \
2367       (other)->next_ ## mdll = (element);                                        \
2368     }                                                                          \
2369     if (NULL == (element)->next_ ## mdll)                                        \
2370       (tail) = (element);                                                      \
2371     else                                                                       \
2372       (element)->next_ ## mdll->prev_ ## mdll = (element);                         \
2373   } while (0)
2374
2375
2376 /**
2377  * @ingroup dll
2378  * Insert an element into a MDLL before the given other element.  Insert
2379  * at the tail if the other element is NULL.
2380  *
2381  * @param mdll suffix name for the next and prev pointers in the element
2382  * @param head pointer to the head of the MDLL
2383  * @param tail pointer to the tail of the MDLL
2384  * @param other prior element, NULL for insertion at head of MDLL
2385  * @param element element to insert
2386  */
2387 #define GNUNET_CONTAINER_MDLL_insert_before(mdll, head, tail, other, element)  \
2388   do                                                                           \
2389   {                                                                            \
2390     GNUNET_assert (((element)->prev_ ## mdll == NULL) && ((head) != (element))); \
2391     GNUNET_assert (((element)->next_ ## mdll == NULL) && ((tail) != (element))); \
2392     (element)->next_ ## mdll = (other);                                          \
2393     if (NULL == other)                                                         \
2394     {                                                                          \
2395       (element)->prev = (tail);                                                \
2396       (tail) = (element);                                                      \
2397     }                                                                          \
2398     else                                                                       \
2399     {                                                                          \
2400       (element)->prev_ ## mdll = (other)->prev_ ## mdll;                           \
2401       (other)->prev_ ## mdll = (element);                                        \
2402     }                                                                          \
2403     if (NULL == (element)->prev_ ## mdll)                                        \
2404       (head) = (element);                                                      \
2405     else                                                                       \
2406       (element)->prev_ ## mdll->next_ ## mdll = (element);                         \
2407   } while (0)
2408
2409
2410 /**
2411  * @ingroup dll
2412  * Remove an element from a MDLL. Assumes
2413  * that head, tail and element are structs
2414  * with prev and next fields.
2415  *
2416  * @param mdll suffix name for the next and prev pointers in the element
2417  * @param head pointer to the head of the MDLL
2418  * @param tail pointer to the tail of the MDLL
2419  * @param element element to remove
2420  */
2421 #define GNUNET_CONTAINER_MDLL_remove(mdll, head, tail, element)                \
2422   do                                                                           \
2423   {                                                                            \
2424     GNUNET_assert (((element)->prev_ ## mdll != NULL) || ((head) == (element))); \
2425     GNUNET_assert (((element)->next_ ## mdll != NULL) || ((tail) == (element))); \
2426     if ((element)->prev_ ## mdll == NULL)                                        \
2427       (head) = (element)->next_ ## mdll;                                         \
2428     else                                                                       \
2429       (element)->prev_ ## mdll->next_ ## mdll = (element)->next_ ## mdll;            \
2430     if ((element)->next_ ## mdll == NULL)                                        \
2431       (tail) = (element)->prev_ ## mdll;                                         \
2432     else                                                                       \
2433       (element)->next_ ## mdll->prev_ ## mdll = (element)->prev_ ## mdll;            \
2434     (element)->next_ ## mdll = NULL;                                             \
2435     (element)->prev_ ## mdll = NULL;                                             \
2436   } while (0)
2437
2438
2439 /**
2440  * Insertion sort of @a element into DLL from @a head to @a tail
2441  * sorted by @a comparator.
2442  *
2443  * @param TYPE element type of the elements, i.e. `struct ListElement`
2444  * @param comparator function like memcmp() to compare elements; takes
2445  *                   three arguments, the @a comparator_cls and two elements,
2446  *                   returns an `int` (-1, 0 or 1)
2447  * @param comparator_cls closure for @a comparator
2448  * @param[in,out] head head of DLL
2449  * @param[in,out] tail tail of DLL
2450  * @param element element to insert
2451  */
2452 #define GNUNET_CONTAINER_DLL_insert_sorted(TYPE,                            \
2453                                            comparator,                      \
2454                                            comparator_cls,                  \
2455                                            head,                            \
2456                                            tail,                            \
2457                                            element)                         \
2458   do                                                                        \
2459   {                                                                         \
2460     if ((NULL == head) || (0 < comparator (comparator_cls, element, head))) \
2461     {                                                                       \
2462       /* insert at head, element < head */                                  \
2463       GNUNET_CONTAINER_DLL_insert (head, tail, element);                    \
2464     }                                                                       \
2465     else                                                                    \
2466     {                                                                       \
2467       TYPE *pos;                                                            \
2468                                                                             \
2469       for (pos = head; NULL != pos; pos = pos->next)                        \
2470         if (0 < comparator (comparator_cls, element, pos))                  \
2471           break; /* element < pos */                                        \
2472       if (NULL == pos)     /* => element > tail */                              \
2473       {                                                                     \
2474         GNUNET_CONTAINER_DLL_insert_tail (head, tail, element);             \
2475       }                                                                     \
2476       else     /* prev < element < pos */                                       \
2477       {                                                                     \
2478         GNUNET_CONTAINER_DLL_insert_after (head, tail, pos->prev, element); \
2479       }                                                                     \
2480     }                                                                       \
2481   } while (0)
2482
2483
2484 /* ******************** Heap *************** */
2485
2486
2487 /**
2488  * @ingroup heap
2489  * Cost by which elements in a heap can be ordered.
2490  */
2491 typedef uint64_t GNUNET_CONTAINER_HeapCostType;
2492
2493
2494 /**
2495  * @ingroup heap
2496  * Heap type, either max or min.
2497  */
2498 enum GNUNET_CONTAINER_HeapOrder
2499 {
2500   /**
2501    * @ingroup heap
2502    * Heap with the maximum cost at the root.
2503    */
2504   GNUNET_CONTAINER_HEAP_ORDER_MAX,
2505
2506   /**
2507    * @ingroup heap
2508    * Heap with the minimum cost at the root.
2509    */
2510   GNUNET_CONTAINER_HEAP_ORDER_MIN
2511 };
2512
2513
2514 /**
2515  * @ingroup heap
2516  * Handle to a Heap.
2517  */
2518 struct GNUNET_CONTAINER_Heap;
2519
2520
2521 /**
2522  * @ingroup heap
2523  * Handle to a node in a heap.
2524  */
2525 struct GNUNET_CONTAINER_HeapNode;
2526
2527
2528 /**
2529  * @ingroup heap
2530  * Create a new heap.
2531  *
2532  * @param order how should the heap be sorted?
2533  * @return handle to the heap
2534  */
2535 struct GNUNET_CONTAINER_Heap *
2536 GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order);
2537
2538
2539 /**
2540  * @ingroup heap
2541  * Destroys the heap.  Only call on a heap that
2542  * is already empty.
2543  *
2544  * @param heap heap to destroy
2545  */
2546 void
2547 GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap);
2548
2549
2550 /**
2551  * @ingroup heap
2552  * Get element stored at the root of @a heap.
2553  *
2554  * @param heap  Heap to inspect.
2555  * @return Element at the root, or NULL if heap is empty.
2556  */
2557 void *
2558 GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap);
2559
2560
2561 /**
2562  * Get @a element and @a cost stored at the root of @a heap.
2563  *
2564  * @param[in]  heap     Heap to inspect.
2565  * @param[out] element  Root element is returned here.
2566  * @param[out] cost     Cost of @a element is returned here.
2567  * @return #GNUNET_YES if an element is returned,
2568  *         #GNUNET_NO  if the heap is empty.
2569  */
2570 int
2571 GNUNET_CONTAINER_heap_peek2 (const struct GNUNET_CONTAINER_Heap *heap,
2572                              void **element,
2573                              GNUNET_CONTAINER_HeapCostType *cost);
2574
2575
2576 /**
2577  * @ingroup heap
2578  * Get the current size of the heap
2579  *
2580  * @param heap the heap to get the size of
2581  * @return number of elements stored
2582  */
2583 unsigned int
2584 GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap);
2585
2586
2587 /**
2588  * @ingroup heap
2589  * Get the current cost of the node
2590  *
2591  * @param node the node to get the cost of
2592  * @return cost of the node
2593  */
2594 GNUNET_CONTAINER_HeapCostType
2595 GNUNET_CONTAINER_heap_node_get_cost (
2596   const struct GNUNET_CONTAINER_HeapNode *node);
2597
2598
2599 /**
2600  * @ingroup heap
2601  * Iterator for heap
2602  *
2603  * @param cls closure
2604  * @param node internal node of the heap
2605  * @param element value stored at the node
2606  * @param cost cost associated with the node
2607  * @return #GNUNET_YES if we should continue to iterate,
2608  *         #GNUNET_NO if not.
2609  */
2610 typedef int (*GNUNET_CONTAINER_HeapIterator) (
2611   void *cls,
2612   struct GNUNET_CONTAINER_HeapNode *node,
2613   void *element,
2614   GNUNET_CONTAINER_HeapCostType cost);
2615
2616
2617 /**
2618  * @ingroup heap
2619  * Iterate over all entries in the heap.
2620  *
2621  * @param heap the heap
2622  * @param iterator function to call on each entry
2623  * @param iterator_cls closure for @a iterator
2624  */
2625 void
2626 GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
2627                                GNUNET_CONTAINER_HeapIterator iterator,
2628                                void *iterator_cls);
2629
2630 /**
2631  * @ingroup heap
2632  * Perform a random walk of the tree.  The walk is biased
2633  * towards elements closer to the root of the tree (since
2634  * each walk starts at the root and ends at a random leaf).
2635  * The heap internally tracks the current position of the
2636  * walk.
2637  *
2638  * @param heap heap to walk
2639  * @return data stored at the next random node in the walk;
2640  *         NULL if the tree is empty.
2641  */
2642 void *
2643 GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap);
2644
2645
2646 /**
2647  * @ingroup heap
2648  * Inserts a new element into the heap.
2649  *
2650  * @param heap heap to modify
2651  * @param element element to insert
2652  * @param cost cost for the element
2653  * @return node for the new element
2654  */
2655 struct GNUNET_CONTAINER_HeapNode *
2656 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap,
2657                               void *element,
2658                               GNUNET_CONTAINER_HeapCostType cost);
2659
2660
2661 /**
2662  * @ingroup heap
2663  * Remove root of the heap.
2664  *
2665  * @param heap heap to modify
2666  * @return element data stored at the root node
2667  */
2668 void *
2669 GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap);
2670
2671
2672 /**
2673  * @ingroup heap
2674  * Removes a node from the heap.
2675  *
2676  * @param node node to remove
2677  * @return element data stored at the node, NULL if heap is empty
2678  */
2679 void *
2680 GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node);
2681
2682
2683 /**
2684  * @ingroup heap
2685  * Updates the cost of any node in the tree
2686  *
2687  * @param node node for which the cost is to be changed
2688  * @param new_cost new cost for the node
2689  */
2690 void
2691 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_HeapNode *node,
2692                                    GNUNET_CONTAINER_HeapCostType new_cost);
2693
2694
2695 #if 0 /* keep Emacsens' auto-indent happy */
2696 {
2697 #endif
2698 #ifdef __cplusplus
2699 }
2700 #endif
2701
2702
2703 /* ifndef GNUNET_CONTAINER_LIB_H */
2704 #endif
2705 /* end of gnunet_container_lib.h */