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