src/include/gnunet_container_lib.h

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