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 (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 (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 (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 (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 (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 (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
1584 (*GNUNET_CONTAINER_HashMapIterator32) (void *cls,
1585                                        uint32_t key,
1586                                        void *value);
1587
1588
1589 /**
1590  * @ingroup hashmap
1591  * Create a 32-bit key multi hash map.
1592  *
1593  * @param len initial size (map will grow as needed)
1594  * @return NULL on error
1595  */
1596 struct GNUNET_CONTAINER_MultiHashMap32 *
1597 GNUNET_CONTAINER_multihashmap32_create (unsigned int len);
1598
1599
1600 /**
1601  * @ingroup hashmap
1602  * Destroy a 32-bit key hash map.  Will not free any values
1603  * stored in the hash map!
1604  *
1605  * @param map the map
1606  */
1607 void
1608 GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32 *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 (struct GNUNET_CONTAINER_MultiHashMap32 *map,
1652                                          GNUNET_CONTAINER_HashMapIterator32 it,
1653                                          void *it_cls);
1654
1655
1656 /**
1657  * @ingroup hashmap
1658  * Remove the given key-value pair from the map.  Note that if the
1659  * key-value pair is in the map multiple times, only one of the pairs
1660  * will be removed.
1661  *
1662  * @param map the map
1663  * @param key key of the key-value pair
1664  * @param value value of the key-value pair
1665  * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
1666  *  is not in the map
1667  */
1668 int
1669 GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 *map,
1670                                         uint32_t key,
1671                                         const void *value);
1672
1673
1674 /**
1675  * @ingroup hashmap
1676  * Remove all entries for the given key from the map.
1677  * Note that the values would not be "freed".
1678  *
1679  * @param map the map
1680  * @param key identifies values to be removed
1681  * @return number of values removed
1682  */
1683 int
1684 GNUNET_CONTAINER_multihashmap32_remove_all (struct GNUNET_CONTAINER_MultiHashMap32 *map,
1685                                             uint32_t key);
1686
1687
1688 /**
1689  * @ingroup hashmap
1690  * Check if the map contains any value under the given
1691  * key (including values that are NULL).
1692  *
1693  * @param map the map
1694  * @param key the key to test if a value exists for it
1695  * @return #GNUNET_YES if such a value exists,
1696  *         #GNUNET_NO if not
1697  */
1698 int
1699 GNUNET_CONTAINER_multihashmap32_contains (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
1700                                           uint32_t key);
1701
1702
1703 /**
1704  * @ingroup hashmap
1705  * Check if the map contains the given value under the given
1706  * key.
1707  *
1708  * @param map the map
1709  * @param key the key to test if a value exists for it
1710  * @param value value to test for
1711  * @return #GNUNET_YES if such a value exists,
1712  *         #GNUNET_NO if not
1713  */
1714 int
1715 GNUNET_CONTAINER_multihashmap32_contains_value (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
1716                                                 uint32_t key,
1717                                                 const void *value);
1718
1719
1720 /**
1721  * @ingroup hashmap
1722  * Store a key-value pair in the map.
1723  *
1724  * @param map the map
1725  * @param key key to use
1726  * @param value value to use
1727  * @param opt options for put
1728  * @return #GNUNET_OK on success,
1729  *         #GNUNET_NO if a value was replaced (with REPLACE)
1730  *         #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
1731  *                       value already exists
1732  */
1733 int
1734 GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32 *map,
1735                                      uint32_t key,
1736                                      void *value,
1737                                      enum GNUNET_CONTAINER_MultiHashMapOption opt);
1738
1739
1740 /**
1741  * @ingroup hashmap
1742  * Iterate over all entries in the map that match a particular key.
1743  *
1744  * @param map the map
1745  * @param key key that the entries must correspond to
1746  * @param it function to call on each entry
1747  * @param it_cls extra argument to @a it
1748  * @return the number of key value pairs processed,
1749  *         #GNUNET_SYSERR if it aborted iteration
1750  */
1751 int
1752 GNUNET_CONTAINER_multihashmap32_get_multiple (struct GNUNET_CONTAINER_MultiHashMap32 *map,
1753                                               uint32_t key,
1754                                               GNUNET_CONTAINER_HashMapIterator32 it,
1755                                               void *it_cls);
1756
1757
1758 /**
1759  * Create an iterator for a 32-bit multihashmap.
1760  * The iterator can be used to retrieve all the elements in the multihashmap
1761  * one by one, without having to handle all elements at once (in contrast to
1762  * #GNUNET_CONTAINER_multihashmap32_iterate).  Note that the iterator can not be
1763  * used anymore if elements have been removed from 'map' after the creation of
1764  * the iterator, or 'map' has been destroyed.  Adding elements to 'map' may
1765  * result in skipped or repeated elements.
1766  *
1767  * @param map the map to create an iterator for
1768  * @return an iterator over the given multihashmap map
1769  */
1770 struct GNUNET_CONTAINER_MultiHashMap32Iterator *
1771 GNUNET_CONTAINER_multihashmap32_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap32 *map);
1772
1773
1774 /**
1775  * Retrieve the next element from the hash map at the iterator's position.
1776  * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
1777  * are not modified.
1778  * This operation is only allowed if no elements have been removed from the
1779  * multihashmap since the creation of 'iter', and the map has not been destroyed.
1780  * Adding elements may result in repeating or skipping elements.
1781  *
1782  * @param iter the iterator to get the next element from
1783  * @param key pointer to store the key in, can be NULL
1784  * @param value pointer to store the value in, can be NULL
1785  * @return #GNUNET_YES we returned an element,
1786  *         #GNUNET_NO if we are out of elements
1787  */
1788 int
1789 GNUNET_CONTAINER_multihashmap32_iterator_next (struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter,
1790                                                uint32_t *key,
1791                                                const void **value);
1792
1793
1794 /**
1795  * Destroy a 32-bit multihashmap iterator.
1796  *
1797  * @param iter the iterator to destroy
1798  */
1799 void
1800 GNUNET_CONTAINER_multihashmap32_iterator_destroy (struct GNUNET_CONTAINER_MultiHashMapIterator *iter);
1801
1802
1803 /* ******************** doubly-linked list *************** */
1804 /* To avoid mistakes: head->prev == tail->next == NULL     */
1805
1806 /**
1807  * @ingroup dll
1808  * Insert an element at the head of a DLL. Assumes that head, tail and
1809  * element are structs with prev and next fields.
1810  *
1811  * @param head pointer to the head of the DLL
1812  * @param tail pointer to the tail of the DLL
1813  * @param element element to insert
1814  */
1815 #define GNUNET_CONTAINER_DLL_insert(head,tail,element) do { \
1816   GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1817   GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1818   (element)->next = (head); \
1819   (element)->prev = NULL; \
1820   if ((tail) == NULL) \
1821     (tail) = element; \
1822   else \
1823     (head)->prev = element; \
1824   (head) = (element); } while (0)
1825
1826
1827 /**
1828  * @ingroup dll
1829  * Insert an element at the tail of a DLL. Assumes that head, tail and
1830  * element are structs with prev and next fields.
1831  *
1832  * @param head pointer to the head of the DLL
1833  * @param tail pointer to the tail of the DLL
1834  * @param element element to insert
1835  */
1836 #define GNUNET_CONTAINER_DLL_insert_tail(head,tail,element) do { \
1837   GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1838   GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1839   (element)->prev = (tail); \
1840   (element)->next = NULL; \
1841   if ((head) == NULL) \
1842     (head) = element; \
1843   else \
1844     (tail)->next = element; \
1845   (tail) = (element); } while (0)
1846
1847
1848 /**
1849  * @ingroup dll
1850  * Insert an element into a DLL after the given other element.  Insert
1851  * at the head if the other element is NULL.
1852  *
1853  * @param head pointer to the head of the DLL
1854  * @param tail pointer to the tail of the DLL
1855  * @param other prior element, NULL for insertion at head of DLL
1856  * @param element element to insert
1857  */
1858 #define GNUNET_CONTAINER_DLL_insert_after(head,tail,other,element) do { \
1859   GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1860   GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1861   (element)->prev = (other); \
1862   if (NULL == other) \
1863     { \
1864       (element)->next = (head); \
1865       (head) = (element); \
1866     } \
1867   else \
1868     { \
1869       (element)->next = (other)->next; \
1870       (other)->next = (element); \
1871     } \
1872   if (NULL == (element)->next) \
1873     (tail) = (element); \
1874   else \
1875     (element)->next->prev = (element); } while (0)
1876
1877
1878 /**
1879  * @ingroup dll
1880  * Insert an element into a DLL before the given other element.  Insert
1881  * at the tail if the other element is NULL.
1882  *
1883  * @param head pointer to the head of the DLL
1884  * @param tail pointer to the tail of the DLL
1885  * @param other prior element, NULL for insertion at head of DLL
1886  * @param element element to insert
1887  */
1888 #define GNUNET_CONTAINER_DLL_insert_before(head,tail,other,element) do { \
1889   GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1890   GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1891   (element)->next = (other); \
1892   if (NULL == other) \
1893     { \
1894       (element)->prev = (tail); \
1895       (tail) = (element); \
1896     } \
1897   else \
1898     { \
1899       (element)->prev = (other)->prev; \
1900       (other)->prev = (element); \
1901     } \
1902   if (NULL == (element)->prev) \
1903     (head) = (element); \
1904   else \
1905     (element)->prev->next = (element); } while (0)
1906
1907
1908 /**
1909  * @ingroup dll
1910  * Remove an element from a DLL. Assumes that head, tail and
1911  * element point to structs with prev and next fields.
1912  *
1913  * Using the head or tail pointer as the element
1914  * argument does NOT work with this macro.
1915  * Make sure to store head/tail in another pointer
1916  * and use it to remove the head or tail of the list.
1917  *
1918  * @param head pointer to the head of the DLL
1919  * @param tail pointer to the tail of the DLL
1920  * @param element element to remove
1921  */
1922 #define GNUNET_CONTAINER_DLL_remove(head,tail,element) do { \
1923   GNUNET_assert ( ( (element)->prev != NULL) || ((head) == (element))); \
1924   GNUNET_assert ( ( (element)->next != NULL) || ((tail) == (element))); \
1925   if ((element)->prev == NULL) \
1926     (head) = (element)->next;  \
1927   else \
1928     (element)->prev->next = (element)->next; \
1929   if ((element)->next == NULL) \
1930     (tail) = (element)->prev;  \
1931   else \
1932     (element)->next->prev = (element)->prev; \
1933   (element)->next = NULL; \
1934   (element)->prev = NULL; } while (0)
1935
1936
1937 /* ************ Multi-DLL interface, allows DLL elements to be
1938    in multiple lists at the same time *********************** */
1939
1940 /**
1941  * @ingroup dll
1942  * Insert an element at the head of a MDLL. Assumes that head, tail and
1943  * element are structs with prev and next fields.
1944  *
1945  * @param mdll suffix name for the next and prev pointers in the element
1946  * @param head pointer to the head of the MDLL
1947  * @param tail pointer to the tail of the MDLL
1948  * @param element element to insert
1949  */
1950 #define GNUNET_CONTAINER_MDLL_insert(mdll,head,tail,element) do {       \
1951   GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1952   GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1953   (element)->next_##mdll = (head); \
1954   (element)->prev_##mdll = NULL; \
1955   if ((tail) == NULL) \
1956     (tail) = element; \
1957   else \
1958     (head)->prev_##mdll = element; \
1959   (head) = (element); } while (0)
1960
1961
1962 /**
1963  * @ingroup dll
1964  * Insert an element at the tail of a MDLL. Assumes that head, tail and
1965  * element are structs with prev and next fields.
1966  *
1967  * @param mdll suffix name for the next and prev pointers in the element
1968  * @param head pointer to the head of the MDLL
1969  * @param tail pointer to the tail of the MDLL
1970  * @param element element to insert
1971  */
1972 #define GNUNET_CONTAINER_MDLL_insert_tail(mdll,head,tail,element) do {  \
1973   GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1974   GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1975   (element)->prev_##mdll = (tail); \
1976   (element)->next_##mdll = NULL; \
1977   if ((head) == NULL) \
1978     (head) = element; \
1979   else \
1980     (tail)->next_##mdll = element; \
1981   (tail) = (element); } while (0)
1982
1983
1984 /**
1985  * @ingroup dll
1986  * Insert an element into a MDLL after the given other element.  Insert
1987  * at the head if the other element is NULL.
1988  *
1989  * @param mdll suffix name for the next and prev pointers in the element
1990  * @param head pointer to the head of the MDLL
1991  * @param tail pointer to the tail of the MDLL
1992  * @param other prior element, NULL for insertion at head of MDLL
1993  * @param element element to insert
1994  */
1995 #define GNUNET_CONTAINER_MDLL_insert_after(mdll,head,tail,other,element) do { \
1996   GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1997   GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1998   (element)->prev_##mdll = (other); \
1999   if (NULL == other) \
2000     { \
2001       (element)->next_##mdll = (head); \
2002       (head) = (element); \
2003     } \
2004   else \
2005     { \
2006       (element)->next_##mdll = (other)->next_##mdll; \
2007       (other)->next_##mdll = (element); \
2008     } \
2009   if (NULL == (element)->next_##mdll) \
2010     (tail) = (element); \
2011   else \
2012     (element)->next->prev_##mdll = (element); } while (0)
2013
2014
2015 /**
2016  * @ingroup dll
2017  * Insert an element into a MDLL before the given other element.  Insert
2018  * at the tail if the other element is NULL.
2019  *
2020  * @param mdll suffix name for the next and prev pointers in the element
2021  * @param head pointer to the head of the MDLL
2022  * @param tail pointer to the tail of the MDLL
2023  * @param other prior element, NULL for insertion at head of MDLL
2024  * @param element element to insert
2025  */
2026 #define GNUNET_CONTAINER_MDLL_insert_before(mdll,head,tail,other,element) do { \
2027   GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
2028   GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
2029   (element)->next_##mdll = (other); \
2030   if (NULL == other) \
2031     { \
2032       (element)->prev = (tail); \
2033       (tail) = (element); \
2034     } \
2035   else \
2036     { \
2037       (element)->prev_##mdll = (other)->prev_##mdll; \
2038       (other)->prev_##mdll = (element); \
2039     } \
2040   if (NULL == (element)->prev_##mdll) \
2041     (head) = (element); \
2042   else \
2043     (element)->prev_##mdll->next_##mdll = (element); } while (0)
2044
2045
2046 /**
2047  * @ingroup dll
2048  * Remove an element from a MDLL. Assumes
2049  * that head, tail and element are structs
2050  * with prev and next fields.
2051  *
2052  * @param mdll suffix name for the next and prev pointers in the element
2053  * @param head pointer to the head of the MDLL
2054  * @param tail pointer to the tail of the MDLL
2055  * @param element element to remove
2056  */
2057 #define GNUNET_CONTAINER_MDLL_remove(mdll,head,tail,element) do {       \
2058   GNUNET_assert ( ( (element)->prev_##mdll != NULL) || ((head) == (element))); \
2059   GNUNET_assert ( ( (element)->next_##mdll != NULL) || ((tail) == (element))); \
2060   if ((element)->prev_##mdll == NULL) \
2061     (head) = (element)->next_##mdll;  \
2062   else \
2063     (element)->prev_##mdll->next_##mdll = (element)->next_##mdll; \
2064   if ((element)->next_##mdll == NULL) \
2065     (tail) = (element)->prev_##mdll;  \
2066   else \
2067     (element)->next_##mdll->prev_##mdll = (element)->prev_##mdll; \
2068   (element)->next_##mdll = NULL; \
2069   (element)->prev_##mdll = NULL; } while (0)
2070
2071
2072
2073 /**
2074  * Insertion sort of @a element into DLL from @a head to @a tail
2075  * sorted by @a comparator.
2076  *
2077  * @param TYPE element type of the elements, i.e. `struct ListElement`
2078  * @param comparator function like memcmp() to compare elements; takes
2079  *                   three arguments, the @a comparator_cls and two elements,
2080  *                   returns an `int` (-1, 0 or 1)
2081  * @param comparator_cls closure for @a comparator
2082  * @param[in,out] head head of DLL
2083  * @param[in,out] tail tail of DLL
2084  * @param element element to insert
2085  */
2086 #define GNUNET_CONTAINER_DLL_insert_sorted(TYPE,comparator,comparator_cls,head,tail,element) do { \
2087   if ( (NULL == head) || \
2088        (0 < comparator (comparator_cls, \
2089                         element, \
2090                         head)) ) \
2091   { \
2092     /* insert at head, element < head */ \
2093     GNUNET_CONTAINER_DLL_insert (head,                                \
2094                                  tail, \
2095                                  element); \
2096   } \
2097   else \
2098   {          \
2099     TYPE *pos; \
2100     \
2101     for (pos = head; \
2102          NULL != pos; \
2103          pos = pos->next) \
2104       if (0 < \
2105           comparator (comparator_cls, \
2106                       element, \
2107                       pos)) \
2108         break; /* element < pos */ \
2109     if (NULL == pos) /* => element > tail */ \
2110     { \
2111       GNUNET_CONTAINER_DLL_insert_tail (head,                             \
2112                                         tail, \
2113                                         element); \
2114     } \
2115     else /* prev < element < pos */ \
2116     { \
2117       GNUNET_CONTAINER_DLL_insert_after (head, \
2118                                          tail, \
2119                                          pos->prev, \
2120                                          element); \
2121     } \
2122   } \
2123 } while (0)
2124
2125
2126 /* ******************** Heap *************** */
2127
2128
2129 /**
2130  * @ingroup heap
2131  * Cost by which elements in a heap can be ordered.
2132  */
2133 typedef uint64_t GNUNET_CONTAINER_HeapCostType;
2134
2135
2136 /**
2137  * @ingroup heap
2138  * Heap type, either max or min.
2139  */
2140 enum GNUNET_CONTAINER_HeapOrder
2141 {
2142   /**
2143    * @ingroup heap
2144    * Heap with the maximum cost at the root.
2145    */
2146   GNUNET_CONTAINER_HEAP_ORDER_MAX,
2147
2148   /**
2149    * @ingroup heap
2150    * Heap with the minimum cost at the root.
2151    */
2152   GNUNET_CONTAINER_HEAP_ORDER_MIN
2153 };
2154
2155
2156 /**
2157  * @ingroup heap
2158  * Handle to a Heap.
2159  */
2160 struct GNUNET_CONTAINER_Heap;
2161
2162
2163 /**
2164  * @ingroup heap
2165  * Handle to a node in a heap.
2166  */
2167 struct GNUNET_CONTAINER_HeapNode;
2168
2169
2170 /**
2171  * @ingroup heap
2172  * Create a new heap.
2173  *
2174  * @param order how should the heap be sorted?
2175  * @return handle to the heap
2176  */
2177 struct GNUNET_CONTAINER_Heap *
2178 GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order);
2179
2180
2181 /**
2182  * @ingroup heap
2183  * Destroys the heap.  Only call on a heap that
2184  * is already empty.
2185  *
2186  * @param heap heap to destroy
2187  */
2188 void
2189 GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap);
2190
2191
2192 /**
2193  * @ingroup heap
2194  * Get element stored at the root of @a heap.
2195  *
2196  * @param heap  Heap to inspect.
2197  * @return Element at the root, or NULL if heap is empty.
2198  */
2199 void *
2200 GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap);
2201
2202
2203 /**
2204  * Get @a element and @a cost stored at the root of @a heap.
2205  *
2206  * @param[in]  heap     Heap to inspect.
2207  * @param[out] element  Root element is returned here.
2208  * @param[out] cost     Cost of @a element is returned here.
2209  * @return #GNUNET_YES if an element is returned,
2210  *         #GNUNET_NO  if the heap is empty.
2211  */
2212 int
2213 GNUNET_CONTAINER_heap_peek2 (const struct GNUNET_CONTAINER_Heap *heap,
2214                              void **element,
2215                              GNUNET_CONTAINER_HeapCostType *cost);
2216
2217
2218 /**
2219  * @ingroup heap
2220  * Get the current size of the heap
2221  *
2222  * @param heap the heap to get the size of
2223  * @return number of elements stored
2224  */
2225 unsigned int
2226 GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap);
2227
2228
2229 /**
2230  * @ingroup heap
2231  * Get the current cost of the node
2232  *
2233  * @param node the node to get the cost of
2234  * @return cost of the node
2235  */
2236 GNUNET_CONTAINER_HeapCostType
2237 GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode *node);
2238
2239
2240 /**
2241  * @ingroup heap
2242  * Iterator for heap
2243  *
2244  * @param cls closure
2245  * @param node internal node of the heap
2246  * @param element value stored at the node
2247  * @param cost cost associated with the node
2248  * @return #GNUNET_YES if we should continue to iterate,
2249  *         #GNUNET_NO if not.
2250  */
2251 typedef int
2252 (*GNUNET_CONTAINER_HeapIterator) (void *cls,
2253                                   struct GNUNET_CONTAINER_HeapNode *node,
2254                                   void *element,
2255                                   GNUNET_CONTAINER_HeapCostType cost);
2256
2257
2258 /**
2259  * @ingroup heap
2260  * Iterate over all entries in the heap.
2261  *
2262  * @param heap the heap
2263  * @param iterator function to call on each entry
2264  * @param iterator_cls closure for @a iterator
2265  */
2266 void
2267 GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
2268                                GNUNET_CONTAINER_HeapIterator iterator,
2269                                void *iterator_cls);
2270
2271 /**
2272  * @ingroup heap
2273  * Perform a random walk of the tree.  The walk is biased
2274  * towards elements closer to the root of the tree (since
2275  * each walk starts at the root and ends at a random leaf).
2276  * The heap internally tracks the current position of the
2277  * walk.
2278  *
2279  * @param heap heap to walk
2280  * @return data stored at the next random node in the walk;
2281  *         NULL if the tree is empty.
2282  */
2283 void *
2284 GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap);
2285
2286
2287 /**
2288  * @ingroup heap
2289  * Inserts a new element into the heap.
2290  *
2291  * @param heap heap to modify
2292  * @param element element to insert
2293  * @param cost cost for the element
2294  * @return node for the new element
2295  */
2296 struct GNUNET_CONTAINER_HeapNode *
2297 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap,
2298                               void *element,
2299                               GNUNET_CONTAINER_HeapCostType cost);
2300
2301
2302 /**
2303  * @ingroup heap
2304  * Remove root of the heap.
2305  *
2306  * @param heap heap to modify
2307  * @return element data stored at the root node
2308  */
2309 void *
2310 GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap);
2311
2312
2313 /**
2314  * @ingroup heap
2315  * Removes a node from the heap.
2316  *
2317  * @param node node to remove
2318  * @return element data stored at the node, NULL if heap is empty
2319  */
2320 void *
2321 GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node);
2322
2323
2324 /**
2325  * @ingroup heap
2326  * Updates the cost of any node in the tree
2327  *
2328  * @param node node for which the cost is to be changed
2329  * @param new_cost new cost for the node
2330  */
2331 void
2332 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_HeapNode *node,
2333                                    GNUNET_CONTAINER_HeapCostType new_cost);
2334
2335
2336 #if 0                           /* keep Emacsens' auto-indent happy */
2337 {
2338 #endif
2339 #ifdef __cplusplus
2340 }
2341 #endif
2342
2343
2344 /* ifndef GNUNET_CONTAINER_LIB_H */
2345 #endif
2346 /* end of gnunet_container_lib.h */