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