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