src/include/gnunet_container_lib.h

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