src/include/gnunet_container_lib.h

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