src/include/gnunet_container_lib.h

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