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