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 struct GNUNET_CONTAINER_MultiPeerMap;
 990 /**
 991  * @ingroup hashmap
 992  * Create a multi peer map (hash map for public keys of peers).
 993  *
 994  * @param len initial size (map will grow as needed)
 995  * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default;
 996  *                         #GNUNET_YES means that on 'put', the 'key' does not have
 997  *                         to be copied as the destination of the pointer is
 998  *                         guaranteed to be life as long as the value is stored in
 999  *                         the hashmap.  This can significantly reduce memory
1000  *                         consumption, but of course is also a recipie for
1001  *                         heap corruption if the assumption is not true.  Only
1002  *                         use this if (1) memory use is important in this case and
1003  *                         (2) you have triple-checked that the invariant holds
1004  * @return NULL on error
1005  */
1006 struct GNUNET_CONTAINER_MultiPeerMap *
1007 GNUNET_CONTAINER_multipeermap_create (unsigned int len,
1008                                       int do_not_copy_keys);
1009
1010
1011 /**
1012  * @ingroup hashmap
1013  * Destroy a hash map.  Will not free any values
1014  * stored in the hash map!
1015  *
1016  * @param map the map
1017  */
1018 void
1019 GNUNET_CONTAINER_multipeermap_destroy (struct GNUNET_CONTAINER_MultiPeerMap *map);
1020
1021
1022 /**
1023  * @ingroup hashmap
1024  * Given a key find a value in the map matching the key.
1025  *
1026  * @param map the map
1027  * @param key what to look for
1028  * @return NULL if no value was found; note that
1029  *   this is indistinguishable from values that just
1030  *   happen to be NULL; use "contains" to test for
1031  *   key-value pairs with value NULL
1032  */
1033 void *
1034 GNUNET_CONTAINER_multipeermap_get (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1035                                    const struct GNUNET_PeerIdentity *key);
1036
1037
1038 /**
1039  * @ingroup hashmap
1040  * Remove the given key-value pair from the map.  Note that if the
1041  * key-value pair is in the map multiple times, only one of the pairs
1042  * will be removed.
1043  *
1044  * @param map the map
1045  * @param key key of the key-value pair
1046  * @param value value of the key-value pair
1047  * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
1048  *  is not in the map
1049  */
1050 int
1051 GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map,
1052                                       const struct GNUNET_PeerIdentity * key,
1053                                       const void *value);
1054
1055 /**
1056  * @ingroup hashmap
1057  * Remove all entries for the given key from the map.
1058  * Note that the values would not be "freed".
1059  *
1060  * @param map the map
1061  * @param key identifies values to be removed
1062  * @return number of values removed
1063  */
1064 int
1065 GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap *map,
1066                                           const struct GNUNET_PeerIdentity *key);
1067
1068
1069 /**
1070  * @ingroup hashmap
1071  * Check if the map contains any value under the given
1072  * key (including values that are NULL).
1073  *
1074  * @param map the map
1075  * @param key the key to test if a value exists for it
1076  * @return #GNUNET_YES if such a value exists,
1077  *         #GNUNET_NO if not
1078  */
1079 int
1080 GNUNET_CONTAINER_multipeermap_contains (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1081                                         const struct GNUNET_PeerIdentity *key);
1082
1083
1084 /**
1085  * @ingroup hashmap
1086  * Check if the map contains the given value under the given
1087  * key.
1088  *
1089  * @param map the map
1090  * @param key the key to test if a value exists for it
1091  * @param value value to test for
1092  * @return #GNUNET_YES if such a value exists,
1093  *         #GNUNET_NO if not
1094  */
1095 int
1096 GNUNET_CONTAINER_multipeermap_contains_value (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1097                                               const struct GNUNET_PeerIdentity * key,
1098                                               const void *value);
1099
1100
1101 /**
1102  * @ingroup hashmap
1103  * Store a key-value pair in the map.
1104  *
1105  * @param map the map
1106  * @param key key to use
1107  * @param value value to use
1108  * @param opt options for put
1109  * @return #GNUNET_OK on success,
1110  *         #GNUNET_NO if a value was replaced (with REPLACE)
1111  *         #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
1112  *                       value already exists
1113  */
1114 int
1115 GNUNET_CONTAINER_multipeermap_put (struct GNUNET_CONTAINER_MultiPeerMap *map,
1116                                    const struct GNUNET_PeerIdentity *key,
1117                                    void *value,
1118                                    enum GNUNET_CONTAINER_MultiHashMapOption opt);
1119
1120
1121 /**
1122  * @ingroup hashmap
1123  * Get the number of key-value pairs in the map.
1124  *
1125  * @param map the map
1126  * @return the number of key value pairs
1127  */
1128 unsigned int
1129 GNUNET_CONTAINER_multipeermap_size (const struct GNUNET_CONTAINER_MultiPeerMap *map);
1130
1131
1132 /**
1133  * @ingroup hashmap
1134  * Iterate over all entries in the map.
1135  *
1136  * @param map the map
1137  * @param it function to call on each entry
1138  * @param it_cls extra argument to @a it
1139  * @return the number of key value pairs processed,
1140  *         #GNUNET_SYSERR if it aborted iteration
1141  */
1142 int
1143 GNUNET_CONTAINER_multipeermap_iterate (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1144                                        GNUNET_CONTAINER_PeerMapIterator it,
1145                                        void *it_cls);
1146
1147
1148 struct GNUNET_CONTAINER_MultiPeerMapIterator;
1149 /**
1150  * @ingroup hashmap
1151  * Create an iterator for a multihashmap.
1152  * The iterator can be used to retrieve all the elements in the multihashmap
1153  * one by one, without having to handle all elements at once (in contrast to
1154  * #GNUNET_CONTAINER_multipeermap_iterate).  Note that the iterator can not be
1155  * used anymore if elements have been removed from @a map after the creation of
1156  * the iterator, or 'map' has been destroyed.  Adding elements to @a map may
1157  * result in skipped or repeated elements.
1158  *
1159  * @param map the map to create an iterator for
1160  * @return an iterator over the given multihashmap @a map
1161  */
1162 struct GNUNET_CONTAINER_MultiPeerMapIterator *
1163 GNUNET_CONTAINER_multipeermap_iterator_create (const struct GNUNET_CONTAINER_MultiPeerMap *map);
1164
1165
1166 /**
1167  * @ingroup hashmap
1168  * Retrieve the next element from the hash map at the iterator's
1169  * position.  If there are no elements left, #GNUNET_NO is returned,
1170  * and @a key and @a value are not modified.  This operation is only
1171  * allowed if no elements have been removed from the multihashmap
1172  * since the creation of @a iter, and the map has not been destroyed.
1173  * Adding elements may result in repeating or skipping elements.
1174  *
1175  * @param iter the iterator to get the next element from
1176  * @param key pointer to store the key in, can be NULL
1177  * @param value pointer to store the value in, can be NULL
1178  * @return #GNUNET_YES we returned an element,
1179  *         #GNUNET_NO if we are out of elements
1180  */
1181 int
1182 GNUNET_CONTAINER_multipeermap_iterator_next (struct GNUNET_CONTAINER_MultiPeerMapIterator *iter,
1183                                              struct GNUNET_PeerIdentity *key,
1184                                              const void **value);
1185
1186
1187 /**
1188  * @ingroup hashmap
1189  * Destroy a multipeermap iterator.
1190  *
1191  * @param iter the iterator to destroy
1192  */
1193 void
1194 GNUNET_CONTAINER_multipeermap_iterator_destroy (struct GNUNET_CONTAINER_MultiPeerMapIterator *iter);
1195
1196
1197 /**
1198  * @ingroup hashmap
1199  * Iterate over all entries in the map that match a particular key.
1200  *
1201  * @param map the map
1202  * @param key public key that the entries must correspond to
1203  * @param it function to call on each entry
1204  * @param it_cls extra argument to @a it
1205  * @return the number of key value pairs processed,
1206  *         #GNUNET_SYSERR if it aborted iteration
1207  */
1208 int
1209 GNUNET_CONTAINER_multipeermap_get_multiple (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1210                                             const struct GNUNET_PeerIdentity *key,
1211                                             GNUNET_CONTAINER_PeerMapIterator it,
1212                                             void *it_cls);
1213
1214
1215 /**
1216  * @ingroup hashmap
1217  * Call @a it on a random value from the map, or not at all
1218  * if the map is empty.  Note that this function has linear
1219  * complexity (in the size of the map).
1220  *
1221  * @param map the map
1222  * @param it function to call on a random entry
1223  * @param it_cls extra argument to @a it
1224  * @return the number of key value pairs processed, zero or one.
1225  */
1226 unsigned int
1227 GNUNET_CONTAINER_multipeermap_get_random (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1228                                           GNUNET_CONTAINER_PeerMapIterator it,
1229                                           void *it_cls);
1230
1231
1232 /* Version of multihashmap with 32 bit keys */
1233
1234 /**
1235  * @ingroup hashmap
1236  * Opaque handle for the 32-bit key HashMap.
1237  */
1238 struct GNUNET_CONTAINER_MultiHashMap32;
1239
1240
1241 /**
1242  * @ingroup hashmap
1243  * Opaque handle to an iterator over
1244  * a 32-bit key multihashmap.
1245  */
1246 struct GNUNET_CONTAINER_MultiHashMap32Iterator;
1247
1248
1249 /**
1250  * @ingroup hashmap
1251  * Iterator over hash map entries.
1252  *
1253  * @param cls closure
1254  * @param key current key code
1255  * @param value value in the hash map
1256  * @return #GNUNET_YES if we should continue to
1257  *         iterate,
1258  *         #GNUNET_NO if not.
1259  */
1260 typedef int (*GNUNET_CONTAINER_HashMapIterator32) (void *cls,
1261                                                    uint32_t key,
1262                                                    void *value);
1263
1264
1265 /**
1266  * @ingroup hashmap
1267  * Create a 32-bit key multi hash map.
1268  *
1269  * @param len initial size (map will grow as needed)
1270  * @return NULL on error
1271  */
1272 struct GNUNET_CONTAINER_MultiHashMap32 *
1273 GNUNET_CONTAINER_multihashmap32_create (unsigned int len);
1274
1275
1276 /**
1277  * @ingroup hashmap
1278  * Destroy a 32-bit key hash map.  Will not free any values
1279  * stored in the hash map!
1280  *
1281  * @param map the map
1282  */
1283 void
1284 GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32
1285                                          *map);
1286
1287
1288 /**
1289  * @ingroup hashmap
1290  * Get the number of key-value pairs in the map.
1291  *
1292  * @param map the map
1293  * @return the number of key value pairs
1294  */
1295 unsigned int
1296 GNUNET_CONTAINER_multihashmap32_size (const struct
1297                                       GNUNET_CONTAINER_MultiHashMap32 *map);
1298
1299
1300 /**
1301  * @ingroup hashmap
1302  * Given a key find a value in the map matching the key.
1303  *
1304  * @param map the map
1305  * @param key what to look for
1306  * @return NULL if no value was found; note that
1307  *   this is indistinguishable from values that just
1308  *   happen to be NULL; use "contains" to test for
1309  *   key-value pairs with value NULL
1310  */
1311 void *
1312 GNUNET_CONTAINER_multihashmap32_get (const struct
1313                                      GNUNET_CONTAINER_MultiHashMap32 *map,
1314                                      uint32_t key);
1315
1316
1317 /**
1318  * @ingroup hashmap
1319  * Iterate over all entries in the map.
1320  *
1321  * @param map the map
1322  * @param it function to call on each entry
1323  * @param it_cls extra argument to @a it
1324  * @return the number of key value pairs processed,
1325  *         #GNUNET_SYSERR if it aborted iteration
1326  */
1327 int
1328 GNUNET_CONTAINER_multihashmap32_iterate (const struct
1329                                          GNUNET_CONTAINER_MultiHashMap32 *map,
1330                                          GNUNET_CONTAINER_HashMapIterator32 it,
1331                                          void *it_cls);
1332
1333
1334 /**
1335  * @ingroup hashmap
1336  * Remove the given key-value pair from the map.  Note that if the
1337  * key-value pair is in the map multiple times, only one of the pairs
1338  * will be removed.
1339  *
1340  * @param map the map
1341  * @param key key of the key-value pair
1342  * @param value value of the key-value pair
1343  * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
1344  *  is not in the map
1345  */
1346 int
1347 GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 *map,
1348                                         uint32_t key,
1349                                         const void *value);
1350
1351
1352 /**
1353  * @ingroup hashmap
1354  * Remove all entries for the given key from the map.
1355  * Note that the values would not be "freed".
1356  *
1357  * @param map the map
1358  * @param key identifies values to be removed
1359  * @return number of values removed
1360  */
1361 int
1362 GNUNET_CONTAINER_multihashmap32_remove_all (struct GNUNET_CONTAINER_MultiHashMap32 *map,
1363                                             uint32_t key);
1364
1365
1366 /**
1367  * @ingroup hashmap
1368  * Check if the map contains any value under the given
1369  * key (including values that are NULL).
1370  *
1371  * @param map the map
1372  * @param key the key to test if a value exists for it
1373  * @return #GNUNET_YES if such a value exists,
1374  *         #GNUNET_NO if not
1375  */
1376 int
1377 GNUNET_CONTAINER_multihashmap32_contains (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
1378                                           uint32_t key);
1379
1380
1381 /**
1382  * @ingroup hashmap
1383  * Check if the map contains the given value under the given
1384  * key.
1385  *
1386  * @param map the map
1387  * @param key the key to test if a value exists for it
1388  * @param value value to test for
1389  * @return #GNUNET_YES if such a value exists,
1390  *         #GNUNET_NO if not
1391  */
1392 int
1393 GNUNET_CONTAINER_multihashmap32_contains_value (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
1394                                                 uint32_t key,
1395                                                 const void *value);
1396
1397
1398 /**
1399  * @ingroup hashmap
1400  * Store a key-value pair in the map.
1401  *
1402  * @param map the map
1403  * @param key key to use
1404  * @param value value to use
1405  * @param opt options for put
1406  * @return #GNUNET_OK on success,
1407  *         #GNUNET_NO if a value was replaced (with REPLACE)
1408  *         #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
1409  *                       value already exists
1410  */
1411 int
1412 GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32 *map,
1413                                      uint32_t key,
1414                                      void *value,
1415                                      enum GNUNET_CONTAINER_MultiHashMapOption opt);
1416
1417
1418 /**
1419  * @ingroup hashmap
1420  * Iterate over all entries in the map that match a particular key.
1421  *
1422  * @param map the map
1423  * @param key key that the entries must correspond to
1424  * @param it function to call on each entry
1425  * @param it_cls extra argument to @a it
1426  * @return the number of key value pairs processed,
1427  *         #GNUNET_SYSERR if it aborted iteration
1428  */
1429 int
1430 GNUNET_CONTAINER_multihashmap32_get_multiple (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
1431                                               uint32_t key,
1432                                               GNUNET_CONTAINER_HashMapIterator32 it,
1433                                               void *it_cls);
1434
1435
1436 /**
1437  * Create an iterator for a 32-bit multihashmap.
1438  * The iterator can be used to retrieve all the elements in the multihashmap
1439  * one by one, without having to handle all elements at once (in contrast to
1440  * #GNUNET_CONTAINER_multihashmap32_iterate).  Note that the iterator can not be
1441  * used anymore if elements have been removed from 'map' after the creation of
1442  * the iterator, or 'map' has been destroyed.  Adding elements to 'map' may
1443  * result in skipped or repeated elements.
1444  *
1445  * @param map the map to create an iterator for
1446  * @return an iterator over the given multihashmap map
1447  */
1448 struct GNUNET_CONTAINER_MultiHashMap32Iterator *
1449 GNUNET_CONTAINER_multihashmap32_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap32 *map);
1450
1451
1452 /**
1453  * Retrieve the next element from the hash map at the iterator's position.
1454  * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
1455  * are not modified.
1456  * This operation is only allowed if no elements have been removed from the
1457  * multihashmap since the creation of 'iter', and the map has not been destroyed.
1458  * Adding elements may result in repeating or skipping elements.
1459  *
1460  * @param iter the iterator to get the next element from
1461  * @param key pointer to store the key in, can be NULL
1462  * @param value pointer to store the value in, can be NULL
1463  * @return #GNUNET_YES we returned an element,
1464  *         #GNUNET_NO if we are out of elements
1465  */
1466 int
1467 GNUNET_CONTAINER_multihashmap32_iterator_next (struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter,
1468                                                uint32_t *key,
1469                                                const void **value);
1470
1471
1472 /**
1473  * Destroy a 32-bit multihashmap iterator.
1474  *
1475  * @param iter the iterator to destroy
1476  */
1477 void
1478 GNUNET_CONTAINER_multihashmap32_iterator_destroy (struct GNUNET_CONTAINER_MultiHashMapIterator *iter);
1479
1480
1481 /* ******************** doubly-linked list *************** */
1482 /* To avoid mistakes: head->prev == tail->next == NULL     */
1483
1484 /**
1485  * @ingroup dll
1486  * Insert an element at the head of a DLL. Assumes that head, tail and
1487  * element are structs with prev and next fields.
1488  *
1489  * @param head pointer to the head of the DLL
1490  * @param tail pointer to the tail of the DLL
1491  * @param element element to insert
1492  */
1493 #define GNUNET_CONTAINER_DLL_insert(head,tail,element) do { \
1494   GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1495   GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1496   (element)->next = (head); \
1497   (element)->prev = NULL; \
1498   if ((tail) == NULL) \
1499     (tail) = element; \
1500   else \
1501     (head)->prev = element; \
1502   (head) = (element); } while (0)
1503
1504
1505 /**
1506  * @ingroup dll
1507  * Insert an element at the tail of a DLL. Assumes that head, tail and
1508  * element are structs with prev and next fields.
1509  *
1510  * @param head pointer to the head of the DLL
1511  * @param tail pointer to the tail of the DLL
1512  * @param element element to insert
1513  */
1514 #define GNUNET_CONTAINER_DLL_insert_tail(head,tail,element) do { \
1515   GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1516   GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1517   (element)->prev = (tail); \
1518   (element)->next = NULL; \
1519   if ((head) == NULL) \
1520     (head) = element; \
1521   else \
1522     (tail)->next = element; \
1523   (tail) = (element); } while (0)
1524
1525
1526 /**
1527  * @ingroup dll
1528  * Insert an element into a DLL after the given other element.  Insert
1529  * at the head if the other element is NULL.
1530  *
1531  * @param head pointer to the head of the DLL
1532  * @param tail pointer to the tail of the DLL
1533  * @param other prior element, NULL for insertion at head of DLL
1534  * @param element element to insert
1535  */
1536 #define GNUNET_CONTAINER_DLL_insert_after(head,tail,other,element) do { \
1537   GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1538   GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1539   (element)->prev = (other); \
1540   if (NULL == other) \
1541     { \
1542       (element)->next = (head); \
1543       (head) = (element); \
1544     } \
1545   else \
1546     { \
1547       (element)->next = (other)->next; \
1548       (other)->next = (element); \
1549     } \
1550   if (NULL == (element)->next) \
1551     (tail) = (element); \
1552   else \
1553     (element)->next->prev = (element); } while (0)
1554
1555
1556 /**
1557  * @ingroup dll
1558  * Insert an element into a DLL before the given other element.  Insert
1559  * at the tail if the other element is NULL.
1560  *
1561  * @param head pointer to the head of the DLL
1562  * @param tail pointer to the tail of the DLL
1563  * @param other prior element, NULL for insertion at head of DLL
1564  * @param element element to insert
1565  */
1566 #define GNUNET_CONTAINER_DLL_insert_before(head,tail,other,element) do { \
1567   GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1568   GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1569   (element)->next = (other); \
1570   if (NULL == other) \
1571     { \
1572       (element)->prev = (tail); \
1573       (tail) = (element); \
1574     } \
1575   else \
1576     { \
1577       (element)->prev = (other)->prev; \
1578       (other)->prev = (element); \
1579     } \
1580   if (NULL == (element)->prev) \
1581     (head) = (element); \
1582   else \
1583     (element)->prev->next = (element); } while (0)
1584
1585
1586 /**
1587  * @ingroup dll
1588  * Remove an element from a DLL. Assumes that head, tail and
1589  * element point to structs with prev and next fields.
1590  *
1591  * Using the head or tail pointer as the element
1592  * argument does NOT work with this macro.
1593  * Make sure to store head/tail in another pointer
1594  * and use it to remove the head or tail of the list.
1595  *
1596  * @param head pointer to the head of the DLL
1597  * @param tail pointer to the tail of the DLL
1598  * @param element element to remove
1599  */
1600 #define GNUNET_CONTAINER_DLL_remove(head,tail,element) do { \
1601   GNUNET_assert ( ( (element)->prev != NULL) || ((head) == (element))); \
1602   GNUNET_assert ( ( (element)->next != NULL) || ((tail) == (element))); \
1603   if ((element)->prev == NULL) \
1604     (head) = (element)->next;  \
1605   else \
1606     (element)->prev->next = (element)->next; \
1607   if ((element)->next == NULL) \
1608     (tail) = (element)->prev;  \
1609   else \
1610     (element)->next->prev = (element)->prev; \
1611   (element)->next = NULL; \
1612   (element)->prev = NULL; } while (0)
1613
1614
1615 /* ************ Multi-DLL interface, allows DLL elements to be
1616    in multiple lists at the same time *********************** */
1617
1618 /**
1619  * @ingroup dll
1620  * Insert an element at the head of a MDLL. Assumes that head, tail and
1621  * element are structs with prev and next fields.
1622  *
1623  * @param mdll suffix name for the next and prev pointers in the element
1624  * @param head pointer to the head of the MDLL
1625  * @param tail pointer to the tail of the MDLL
1626  * @param element element to insert
1627  */
1628 #define GNUNET_CONTAINER_MDLL_insert(mdll,head,tail,element) do {       \
1629   GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1630   GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1631   (element)->next_##mdll = (head); \
1632   (element)->prev_##mdll = NULL; \
1633   if ((tail) == NULL) \
1634     (tail) = element; \
1635   else \
1636     (head)->prev_##mdll = element; \
1637   (head) = (element); } while (0)
1638
1639
1640 /**
1641  * @ingroup dll
1642  * Insert an element at the tail of a MDLL. Assumes that head, tail and
1643  * element are structs with prev and next fields.
1644  *
1645  * @param mdll suffix name for the next and prev pointers in the element
1646  * @param head pointer to the head of the MDLL
1647  * @param tail pointer to the tail of the MDLL
1648  * @param element element to insert
1649  */
1650 #define GNUNET_CONTAINER_MDLL_insert_tail(mdll,head,tail,element) do {  \
1651   GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1652   GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1653   (element)->prev_##mdll = (tail); \
1654   (element)->next_##mdll = NULL; \
1655   if ((head) == NULL) \
1656     (head) = element; \
1657   else \
1658     (tail)->next_##mdll = element; \
1659   (tail) = (element); } while (0)
1660
1661
1662 /**
1663  * @ingroup dll
1664  * Insert an element into a MDLL after the given other element.  Insert
1665  * at the head if the other element is NULL.
1666  *
1667  * @param mdll suffix name for the next and prev pointers in the element
1668  * @param head pointer to the head of the MDLL
1669  * @param tail pointer to the tail of the MDLL
1670  * @param other prior element, NULL for insertion at head of MDLL
1671  * @param element element to insert
1672  */
1673 #define GNUNET_CONTAINER_MDLL_insert_after(mdll,head,tail,other,element) do { \
1674   GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1675   GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1676   (element)->prev_##mdll = (other); \
1677   if (NULL == other) \
1678     { \
1679       (element)->next_##mdll = (head); \
1680       (head) = (element); \
1681     } \
1682   else \
1683     { \
1684       (element)->next_##mdll = (other)->next_##mdll; \
1685       (other)->next_##mdll = (element); \
1686     } \
1687   if (NULL == (element)->next_##mdll) \
1688     (tail) = (element); \
1689   else \
1690     (element)->next->prev_##mdll = (element); } while (0)
1691
1692
1693 /**
1694  * @ingroup dll
1695  * Insert an element into a MDLL before the given other element.  Insert
1696  * at the tail if the other element is NULL.
1697  *
1698  * @param mdll suffix name for the next and prev pointers in the element
1699  * @param head pointer to the head of the MDLL
1700  * @param tail pointer to the tail of the MDLL
1701  * @param other prior element, NULL for insertion at head of MDLL
1702  * @param element element to insert
1703  */
1704 #define GNUNET_CONTAINER_MDLL_insert_before(mdll,head,tail,other,element) do { \
1705   GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1706   GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1707   (element)->next_##mdll = (other); \
1708   if (NULL == other) \
1709     { \
1710       (element)->prev = (tail); \
1711       (tail) = (element); \
1712     } \
1713   else \
1714     { \
1715       (element)->prev_##mdll = (other)->prev_##mdll; \
1716       (other)->prev_##mdll = (element); \
1717     } \
1718   if (NULL == (element)->prev_##mdll) \
1719     (head) = (element); \
1720   else \
1721     (element)->prev_##mdll->next_##mdll = (element); } while (0)
1722
1723
1724 /**
1725  * @ingroup dll
1726  * Remove an element from a MDLL. Assumes
1727  * that head, tail and element are structs
1728  * with prev and next fields.
1729  *
1730  * @param mdll suffix name for the next and prev pointers in the element
1731  * @param head pointer to the head of the MDLL
1732  * @param tail pointer to the tail of the MDLL
1733  * @param element element to remove
1734  */
1735 #define GNUNET_CONTAINER_MDLL_remove(mdll,head,tail,element) do {       \
1736   GNUNET_assert ( ( (element)->prev_##mdll != NULL) || ((head) == (element))); \
1737   GNUNET_assert ( ( (element)->next_##mdll != NULL) || ((tail) == (element))); \
1738   if ((element)->prev_##mdll == NULL) \
1739     (head) = (element)->next_##mdll;  \
1740   else \
1741     (element)->prev_##mdll->next_##mdll = (element)->next_##mdll; \
1742   if ((element)->next_##mdll == NULL) \
1743     (tail) = (element)->prev_##mdll;  \
1744   else \
1745     (element)->next_##mdll->prev_##mdll = (element)->prev_##mdll; \
1746   (element)->next_##mdll = NULL; \
1747   (element)->prev_##mdll = NULL; } while (0)
1748
1749
1750
1751 /* ******************** Heap *************** */
1752
1753
1754 /**
1755  * @ingroup heap
1756  * Cost by which elements in a heap can be ordered.
1757  */
1758 typedef uint64_t GNUNET_CONTAINER_HeapCostType;
1759
1760
1761 /**
1762  * @ingroup heap
1763  * Heap type, either max or min.
1764  */
1765 enum GNUNET_CONTAINER_HeapOrder
1766 {
1767   /**
1768    * @ingroup heap
1769    * Heap with the maximum cost at the root.
1770    */
1771   GNUNET_CONTAINER_HEAP_ORDER_MAX,
1772
1773   /**
1774    * @ingroup heap
1775    * Heap with the minimum cost at the root.
1776    */
1777   GNUNET_CONTAINER_HEAP_ORDER_MIN
1778 };
1779
1780
1781 /**
1782  * @ingroup heap
1783  * Handle to a Heap.
1784  */
1785 struct GNUNET_CONTAINER_Heap;
1786
1787
1788 /**
1789  * @ingroup heap
1790  * Handle to a node in a heap.
1791  */
1792 struct GNUNET_CONTAINER_HeapNode;
1793
1794
1795 /**
1796  * @ingroup heap
1797  * Create a new heap.
1798  *
1799  * @param order how should the heap be sorted?
1800  * @return handle to the heap
1801  */
1802 struct GNUNET_CONTAINER_Heap *
1803 GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order);
1804
1805
1806 /**
1807  * @ingroup heap
1808  * Destroys the heap.  Only call on a heap that
1809  * is already empty.
1810  *
1811  * @param heap heap to destroy
1812  */
1813 void
1814 GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap);
1815
1816
1817 /**
1818  * @ingroup heap
1819  * Get element stored at the root of @a heap.
1820  *
1821  * @param heap  Heap to inspect.
1822  * @return Element at the root, or NULL if heap is empty.
1823  */
1824 void *
1825 GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap);
1826
1827
1828 /**
1829  * Get @a element and @a cost stored at the root of @a heap.
1830  *
1831  * @param[in]  heap     Heap to inspect.
1832  * @param[out] element  Root element is returned here.
1833  * @param[out] cost     Cost of @a element is returned here.
1834  * @return #GNUNET_YES if an element is returned,
1835  *         #GNUNET_NO  if the heap is empty.
1836  */
1837 int
1838 GNUNET_CONTAINER_heap_peek2 (const struct GNUNET_CONTAINER_Heap *heap,
1839                              void **element,
1840                              GNUNET_CONTAINER_HeapCostType *cost);
1841
1842
1843 /**
1844  * @ingroup heap
1845  * Get the current size of the heap
1846  *
1847  * @param heap the heap to get the size of
1848  * @return number of elements stored
1849  */
1850 unsigned int
1851 GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap);
1852
1853
1854 /**
1855  * @ingroup heap
1856  * Get the current cost of the node
1857  *
1858  * @param node the node to get the cost of
1859  * @return cost of the node
1860  */
1861 GNUNET_CONTAINER_HeapCostType
1862 GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode
1863                                      *node);
1864
1865 /**
1866  * @ingroup heap
1867  * Iterator for heap
1868  *
1869  * @param cls closure
1870  * @param node internal node of the heap
1871  * @param element value stored at the node
1872  * @param cost cost associated with the node
1873  * @return #GNUNET_YES if we should continue to iterate,
1874  *         #GNUNET_NO if not.
1875  */
1876 typedef int
1877 (*GNUNET_CONTAINER_HeapIterator) (void *cls,
1878                                   struct GNUNET_CONTAINER_HeapNode *node,
1879                                   void *element,
1880                                   GNUNET_CONTAINER_HeapCostType cost);
1881
1882
1883 /**
1884  * @ingroup heap
1885  * Iterate over all entries in the heap.
1886  *
1887  * @param heap the heap
1888  * @param iterator function to call on each entry
1889  * @param iterator_cls closure for @a iterator
1890  */
1891 void
1892 GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
1893                                GNUNET_CONTAINER_HeapIterator iterator,
1894                                void *iterator_cls);
1895
1896 /**
1897  * @ingroup heap
1898  * Perform a random walk of the tree.  The walk is biased
1899  * towards elements closer to the root of the tree (since
1900  * each walk starts at the root and ends at a random leaf).
1901  * The heap internally tracks the current position of the
1902  * walk.
1903  *
1904  * @param heap heap to walk
1905  * @return data stored at the next random node in the walk;
1906  *         NULL if the tree is empty.
1907  */
1908 void *
1909 GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap);
1910
1911
1912 /**
1913  * @ingroup heap
1914  * Inserts a new element into the heap.
1915  *
1916  * @param heap heap to modify
1917  * @param element element to insert
1918  * @param cost cost for the element
1919  * @return node for the new element
1920  */
1921 struct GNUNET_CONTAINER_HeapNode *
1922 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap,
1923                               void *element,
1924                               GNUNET_CONTAINER_HeapCostType cost);
1925
1926
1927 /**
1928  * @ingroup heap
1929  * Remove root of the heap.
1930  *
1931  * @param heap heap to modify
1932  * @return element data stored at the root node
1933  */
1934 void *
1935 GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap);
1936
1937
1938 /**
1939  * @ingroup heap
1940  * Removes a node from the heap.
1941  *
1942  * @param node node to remove
1943  * @return element data stored at the node, NULL if heap is empty
1944  */
1945 void *
1946 GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node);
1947
1948
1949 /**
1950  * @ingroup heap
1951  * Updates the cost of any node in the tree
1952  *
1953  * @param heap heap to modify
1954  * @param node node for which the cost is to be changed
1955  * @param new_cost new cost for the node
1956  */
1957 void
1958 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
1959                                    struct GNUNET_CONTAINER_HeapNode *node,
1960                                    GNUNET_CONTAINER_HeapCostType new_cost);
1961
1962
1963 #if 0                           /* keep Emacsens' auto-indent happy */
1964 {
1965 #endif
1966 #ifdef __cplusplus
1967 }
1968 #endif
1969
1970
1971 /* ifndef GNUNET_CONTAINER_LIB_H */
1972 #endif
1973 /* end of gnunet_container_lib.h */