src/include/gnunet_container_lib.h

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