src/include/gnunet_container_lib.h

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