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
 402  * @param iter_cls closure for @a iter
 403  * @return number of entries
 404  */
 405 int
 406 GNUNET_CONTAINER_meta_data_iterate (const struct GNUNET_CONTAINER_MetaData *md,
 407                                     EXTRACTOR_MetaDataProcessor iter,
 408                                     void *iter_cls);
 409
 410 /**
 411  * @ingroup metadata
 412  * Get the first MD entry of the given type.  Caller
 413  * is responsible for freeing the return value.
 414  * Also, only meta data items that are strings (0-terminated)
 415  * are returned by this function.
 416  *
 417  * @param md metadata to inspect
 418  * @param type type to look for
 419  * @return NULL if no entry was found
 420  */
 421 char *
 422 GNUNET_CONTAINER_meta_data_get_by_type (const struct GNUNET_CONTAINER_MetaData
 423                                         *md, enum EXTRACTOR_MetaType type);
 424
 425
 426 /**
 427  * @ingroup metadata
 428  * Get the first matching MD entry of the given types. Caller is
 429  * responsible for freeing the return value.  Also, only meta data
 430  * items that are strings (0-terminated) are returned by this
 431  * function.
 432  *
 433  * @param md metadata to inspect
 434  * @param ... -1-terminated list of types
 435  * @return NULL if we do not have any such entry,
 436  *  otherwise client is responsible for freeing the value!
 437  */
 438 char *
 439 GNUNET_CONTAINER_meta_data_get_first_by_types (const struct
 440                                                GNUNET_CONTAINER_MetaData *md,
 441                                                ...);
 442
 443 /**
 444  * @ingroup metadata
 445  * Get a thumbnail from the meta-data (if present).  Only matches meta
 446  * data with mime type "image" and binary format.
 447  *
 448  * @param md metadata to inspect
 449  * @param thumb will be set to the thumbnail data.  Must be
 450  *        freed by the caller!
 451  * @return number of bytes in thumbnail, 0 if not available
 452  */
 453 size_t
 454 GNUNET_CONTAINER_meta_data_get_thumbnail (const struct GNUNET_CONTAINER_MetaData
 455                                           *md, unsigned char **thumb);
 456
 457
 458
 459 /**
 460  * @ingroup metadata
 461  * Options for metadata serialization.
 462  */
 463 enum GNUNET_CONTAINER_MetaDataSerializationOptions
 464 {
 465   /**
 466    * @ingroup metadata
 467    * Serialize all of the data.
 468    */
 469   GNUNET_CONTAINER_META_DATA_SERIALIZE_FULL = 0,
 470
 471   /**
 472    * @ingroup metadata
 473    * If not enough space is available, it is acceptable
 474    * to only serialize some of the metadata.
 475    */
 476   GNUNET_CONTAINER_META_DATA_SERIALIZE_PART = 1,
 477
 478   /**
 479    * @ingroup metadata
 480    * Speed is of the essence, do not allow compression.
 481    */
 482   GNUNET_CONTAINER_META_DATA_SERIALIZE_NO_COMPRESS = 2
 483 };
 484
 485
 486 /**
 487  * @ingroup metadata
 488  * Serialize meta-data to target.
 489  *
 490  * @param md metadata to serialize
 491  * @param target where to write the serialized metadata;
 492  *         *target can be NULL, in which case memory is allocated
 493  * @param max maximum number of bytes available
 494  * @param opt is it ok to just write SOME of the
 495  *        meta-data to match the size constraint,
 496  *        possibly discarding some data?
 497  * @return number of bytes written on success,
 498  *         -1 on error (typically: not enough
 499  *         space)
 500  */
 501 ssize_t
 502 GNUNET_CONTAINER_meta_data_serialize (const struct GNUNET_CONTAINER_MetaData
 503                                       *md, char **target, size_t max,
 504                                       enum
 505                                       GNUNET_CONTAINER_MetaDataSerializationOptions
 506                                       opt);
 507
 508
 509 /**
 510  * @ingroup metadata
 511  * Get the size of the full meta-data in serialized form.
 512  *
 513  * @param md metadata to inspect
 514  * @return number of bytes needed for serialization, -1 on error
 515  */
 516 ssize_t
 517 GNUNET_CONTAINER_meta_data_get_serialized_size (const struct
 518                                                 GNUNET_CONTAINER_MetaData *md);
 519
 520
 521 /**
 522  * @ingroup metadata
 523  * Deserialize meta-data.  Initializes md.
 524  *
 525  * @param input serialized meta-data.
 526  * @param size number of bytes available
 527  * @return MD on success, NULL on error (i.e.
 528  *         bad format)
 529  */
 530 struct GNUNET_CONTAINER_MetaData *
 531 GNUNET_CONTAINER_meta_data_deserialize (const char *input, size_t size);
 532
 533
 534 /* ******************************* HashMap **************************** */
 535
 536 /**
 537  * @ingroup hashmap
 538  * Opaque handle for a HashMap.
 539  */
 540 struct GNUNET_CONTAINER_MultiHashMap;
 541
 542 /**
 543  * @ingroup hashmap
 544  * Opaque handle to an iterator over
 545  * a multihashmap.
 546  */
 547 struct GNUNET_CONTAINER_MultiHashMapIterator;
 548
 549 /**
 550  * @ingroup hashmap
 551  * Options for storing values in the HashMap.
 552  */
 553 enum GNUNET_CONTAINER_MultiHashMapOption
 554 {
 555
 556   /**
 557    * @ingroup hashmap
 558    * If a value with the given key exists, replace it.  Note that the
 559    * old value would NOT be freed by replace (the application has to
 560    * make sure that this happens if required).
 561    */
 562   GNUNET_CONTAINER_MULTIHASHMAPOPTION_REPLACE,
 563
 564   /**
 565    * @ingroup hashmap
 566    * Allow multiple values with the same key.
 567    */
 568   GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE,
 569
 570   /**
 571    * @ingroup hashmap
 572    * There must only be one value per key; storing a value should fail
 573    * if a value under the same key already exists.
 574    */
 575   GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY,
 576
 577   /**
 578    * @ingroup hashmap There must only be one value per key, but don't
 579    * bother checking if a value already exists (faster than
 580    * #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY; implemented
 581    * just like #GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE but this
 582    * option documents better what is intended if
 583    * #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY is what is
 584    * desired).
 585    */
 586   GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST
 587 };
 588
 589
 590 /**
 591  * @ingroup hashmap
 592  * Iterator over hash map entries.
 593  *
 594  * @param cls closure
 595  * @param key current key code
 596  * @param value value in the hash map
 597  * @return #GNUNET_YES if we should continue to
 598  *         iterate,
 599  *         #GNUNET_NO if not.
 600  */
 601 typedef int (*GNUNET_CONTAINER_HashMapIterator) (void *cls,
 602                                                  const struct GNUNET_HashCode *key,
 603                                                  void *value);
 604
 605
 606 /**
 607  * @ingroup hashmap
 608  * Create a multi hash map.
 609  *
 610  * @param len initial size (map will grow as needed)
 611  * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default;
 612  *                         #GNUNET_YES means that on 'put', the 'key' does not have
 613  *                         to be copied as the destination of the pointer is
 614  *                         guaranteed to be life as long as the value is stored in
 615  *                         the hashmap.  This can significantly reduce memory
 616  *                         consumption, but of course is also a recipie for
 617  *                         heap corruption if the assumption is not true.  Only
 618  *                         use this if (1) memory use is important in this case and
 619  *                         (2) you have triple-checked that the invariant holds
 620  * @return NULL on error
 621  */
 622 struct GNUNET_CONTAINER_MultiHashMap *
 623 GNUNET_CONTAINER_multihashmap_create (unsigned int len,
 624                                       int do_not_copy_keys);
 625
 626
 627 /**
 628  * @ingroup hashmap
 629  * Destroy a hash map.  Will not free any values
 630  * stored in the hash map!
 631  *
 632  * @param map the map
 633  */
 634 void
 635 GNUNET_CONTAINER_multihashmap_destroy (struct GNUNET_CONTAINER_MultiHashMap
 636                                        *map);
 637
 638
 639 /**
 640  * @ingroup hashmap
 641  * Given a key find a value in the map matching the key.
 642  *
 643  * @param map the map
 644  * @param key what to look for
 645  * @return NULL if no value was found; note that
 646  *   this is indistinguishable from values that just
 647  *   happen to be NULL; use "contains" to test for
 648  *   key-value pairs with value NULL
 649  */
 650 void *
 651 GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap
 652                                    *map, const struct GNUNET_HashCode * key);
 653
 654
 655 /**
 656  * @ingroup hashmap
 657  * Remove the given key-value pair from the map.  Note that if the
 658  * key-value pair is in the map multiple times, only one of the pairs
 659  * will be removed.
 660  *
 661  * @param map the map
 662  * @param key key of the key-value pair
 663  * @param value value of the key-value pair
 664  * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
 665  *  is not in the map
 666  */
 667 int
 668 GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map,
 669                                       const struct GNUNET_HashCode * key,
 670                                       const void *value);
 671
 672 /**
 673  * @ingroup hashmap
 674  * Remove all entries for the given key from the map.
 675  * Note that the values would not be "freed".
 676  *
 677  * @param map the map
 678  * @param key identifies values to be removed
 679  * @return number of values removed
 680  */
 681 int
 682 GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap
 683                                           *map, const struct GNUNET_HashCode * key);
 684
 685
 686 /**
 687  * @ingroup hashmap
 688  * Check if the map contains any value under the given
 689  * key (including values that are NULL).
 690  *
 691  * @param map the map
 692  * @param key the key to test if a value exists for it
 693  * @return #GNUNET_YES if such a value exists,
 694  *         #GNUNET_NO if not
 695  */
 696 int
 697 GNUNET_CONTAINER_multihashmap_contains (const struct
 698                                         GNUNET_CONTAINER_MultiHashMap *map,
 699                                         const struct GNUNET_HashCode * key);
 700
 701
 702 /**
 703  * @ingroup hashmap
 704  * Check if the map contains the given value under the given
 705  * key.
 706  *
 707  * @param map the map
 708  * @param key the key to test if a value exists for it
 709  * @param value value to test for
 710  * @return #GNUNET_YES if such a value exists,
 711  *         #GNUNET_NO if not
 712  */
 713 int
 714 GNUNET_CONTAINER_multihashmap_contains_value (const struct
 715                                               GNUNET_CONTAINER_MultiHashMap
 716                                               *map, const struct GNUNET_HashCode * key,
 717                                               const void *value);
 718
 719
 720 /**
 721  * @ingroup hashmap
 722  * Store a key-value pair in the map.
 723  *
 724  * @param map the map
 725  * @param key key to use
 726  * @param value value to use
 727  * @param opt options for put
 728  * @return #GNUNET_OK on success,
 729  *         #GNUNET_NO if a value was replaced (with REPLACE)
 730  *         #GNUNET_SYSERR if UNIQUE_ONLY was the option and the
 731  *                       value already exists
 732  */
 733 int
 734 GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map,
 735                                    const struct GNUNET_HashCode * key, void *value,
 736                                    enum GNUNET_CONTAINER_MultiHashMapOption
 737                                    opt);
 738
 739 /**
 740  * @ingroup hashmap
 741  * Get the number of key-value pairs in the map.
 742  *
 743  * @param map the map
 744  * @return the number of key value pairs
 745  */
 746 unsigned int
 747 GNUNET_CONTAINER_multihashmap_size (const struct GNUNET_CONTAINER_MultiHashMap
 748                                     *map);
 749
 750
 751 /**
 752  * @ingroup hashmap
 753  * Iterate over all entries in the map.
 754  *
 755  * @param map the map
 756  * @param it function to call on each entry
 757  * @param it_cls extra argument to @a it
 758  * @return the number of key value pairs processed,
 759  *         #GNUNET_SYSERR if it aborted iteration
 760  */
 761 int
 762 GNUNET_CONTAINER_multihashmap_iterate (const struct
 763                                        GNUNET_CONTAINER_MultiHashMap *map,
 764                                        GNUNET_CONTAINER_HashMapIterator it,
 765                                        void *it_cls);
 766
 767
 768 /**
 769  * @ingroup hashmap
 770  * Create an iterator for a multihashmap.
 771  * The iterator can be used to retrieve all the elements in the multihashmap
 772  * one by one, without having to handle all elements at once (in contrast to
 773  * 'GNUNET_CONTAINER_multihashmap_iterate').  Note that the iterator can not be
 774  * used anymore if elements have been removed from 'map' after the creation of
 775  * the iterator, or 'map' has been destroyed.  Adding elements to 'map' may
 776  * result in skipped or repeated elements.
 777  *
 778  * @param map the map to create an iterator for
 779  * @return an iterator over the given multihashmap @a map
 780  */
 781 struct GNUNET_CONTAINER_MultiHashMapIterator *
 782 GNUNET_CONTAINER_multihashmap_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap *map);
 783
 784
 785 /**
 786  * @ingroup hashmap
 787  * Retrieve the next element from the hash map at the iterator's
 788  * position.  If there are no elements left, #GNUNET_NO is returned,
 789  * and @a key and @a value are not modified.  This operation is only
 790  * allowed if no elements have been removed from the multihashmap
 791  * since the creation of @a iter, and the map has not been destroyed.
 792  * Adding elements may result in repeating or skipping elements.
 793  *
 794  * @param iter the iterator to get the next element from
 795  * @param key pointer to store the key in, can be NULL
 796  * @param value pointer to store the value in, can be NULL
 797  * @return #GNUNET_YES we returned an element,
 798  *         #GNUNET_NO if we are out of elements
 799  */
 800 int
 801 GNUNET_CONTAINER_multihashmap_iterator_next (struct GNUNET_CONTAINER_MultiHashMapIterator *iter,
 802                                              struct GNUNET_HashCode *key, const void **value);
 803
 804
 805 /**
 806  * @ingroup hashmap
 807  * Destroy a multihashmap iterator.
 808  *
 809  * @param iter the iterator to destroy
 810  */
 811 void
 812 GNUNET_CONTAINER_multihashmap_iterator_destroy (struct GNUNET_CONTAINER_MultiHashMapIterator *iter);
 813
 814
 815 /**
 816  * @ingroup hashmap
 817  * Iterate over all entries in the map that match a particular key.
 818  *
 819  * @param map the map
 820  * @param key key that the entries must correspond to
 821  * @param it function to call on each entry
 822  * @param it_cls extra argument to @a it
 823  * @return the number of key value pairs processed,
 824  *         #GNUNET_SYSERR if it aborted iteration
 825  */
 826 int
 827 GNUNET_CONTAINER_multihashmap_get_multiple (const struct
 828                                             GNUNET_CONTAINER_MultiHashMap *map,
 829                                             const struct GNUNET_HashCode * key,
 830                                             GNUNET_CONTAINER_HashMapIterator it,
 831                                             void *it_cls);
 832
 833 /* Version of multihashmap with 32 bit keys */
 834
 835 /**
 836  * @ingroup hashmap
 837  * Opaque handle for the 32-bit key HashMap.
 838  */
 839 struct GNUNET_CONTAINER_MultiHashMap32;
 840
 841
 842 /**
 843  * @ingroup hashmap
 844  * Iterator over hash map entries.
 845  *
 846  * @param cls closure
 847  * @param key current key code
 848  * @param value value in the hash map
 849  * @return #GNUNET_YES if we should continue to
 850  *         iterate,
 851  *         #GNUNET_NO if not.
 852  */
 853 typedef int (*GNUNET_CONTAINER_HashMapIterator32) (void *cls,
 854                                                    uint32_t key,
 855                                                    void *value);
 856
 857
 858 /**
 859  * @ingroup hashmap
 860  * Create a 32-bit key multi hash map.
 861  *
 862  * @param len initial size (map will grow as needed)
 863  * @return NULL on error
 864  */
 865 struct GNUNET_CONTAINER_MultiHashMap32 *
 866 GNUNET_CONTAINER_multihashmap32_create (unsigned int len);
 867
 868
 869 /**
 870  * @ingroup hashmap
 871  * Destroy a 32-bit key hash map.  Will not free any values
 872  * stored in the hash map!
 873  *
 874  * @param map the map
 875  */
 876 void
 877 GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32
 878                                          *map);
 879
 880
 881 /**
 882  * @ingroup hashmap
 883  * Get the number of key-value pairs in the map.
 884  *
 885  * @param map the map
 886  * @return the number of key value pairs
 887  */
 888 unsigned int
 889 GNUNET_CONTAINER_multihashmap32_size (const struct
 890                                       GNUNET_CONTAINER_MultiHashMap32 *map);
 891
 892
 893 /**
 894  * @ingroup hashmap
 895  * Given a key find a value in the map matching the key.
 896  *
 897  * @param map the map
 898  * @param key what to look for
 899  * @return NULL if no value was found; note that
 900  *   this is indistinguishable from values that just
 901  *   happen to be NULL; use "contains" to test for
 902  *   key-value pairs with value NULL
 903  */
 904 void *
 905 GNUNET_CONTAINER_multihashmap32_get (const struct
 906                                      GNUNET_CONTAINER_MultiHashMap32 *map,
 907                                      uint32_t key);
 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_multihashmap32_iterate (const struct
 922                                          GNUNET_CONTAINER_MultiHashMap32 *map,
 923                                          GNUNET_CONTAINER_HashMapIterator32 it,
 924                                          void *it_cls);
 925
 926
 927 /**
 928  * @ingroup hashmap
 929  * Remove the given key-value pair from the map.  Note that if the
 930  * key-value pair is in the map multiple times, only one of the pairs
 931  * will be removed.
 932  *
 933  * @param map the map
 934  * @param key key of the key-value pair
 935  * @param value value of the key-value pair
 936  * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
 937  *  is not in the map
 938  */
 939 int
 940 GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32
 941                                         *map,
 942                                         uint32_t key,
 943                                         const void *value);
 944
 945
 946 /**
 947  * @ingroup hashmap
 948  * Remove all entries for the given key from the map.
 949  * Note that the values would not be "freed".
 950  *
 951  * @param map the map
 952  * @param key identifies values to be removed
 953  * @return number of values removed
 954  */
 955 int
 956 GNUNET_CONTAINER_multihashmap32_remove_all (struct
 957                                             GNUNET_CONTAINER_MultiHashMap32
 958                                             *map,
 959                                             uint32_t key);
 960
 961
 962 /**
 963  * @ingroup hashmap
 964  * Check if the map contains any value under the given
 965  * key (including values that are NULL).
 966  *
 967  * @param map the map
 968  * @param key the key to test if a value exists for it
 969  * @return #GNUNET_YES if such a value exists,
 970  *         #GNUNET_NO if not
 971  */
 972 int
 973 GNUNET_CONTAINER_multihashmap32_contains (const struct
 974                                           GNUNET_CONTAINER_MultiHashMap32 *map,
 975                                           uint32_t key);
 976
 977
 978 /**
 979  * @ingroup hashmap
 980  * Check if the map contains the given value under the given
 981  * key.
 982  *
 983  * @param map the map
 984  * @param key the key to test if a value exists for it
 985  * @param value value to test for
 986  * @return #GNUNET_YES if such a value exists,
 987  *         #GNUNET_NO if not
 988  */
 989 int
 990 GNUNET_CONTAINER_multihashmap32_contains_value (const struct
 991                                                 GNUNET_CONTAINER_MultiHashMap32
 992                                                 *map,
 993                                                 uint32_t key,
 994                                                 const void *value);
 995
 996
 997 /**
 998  * @ingroup hashmap
 999  * Store a key-value pair in the map.
1000  *
1001  * @param map the map
1002  * @param key key to use
1003  * @param value value to use
1004  * @param opt options for put
1005  * @return #GNUNET_OK on success,
1006  *         #GNUNET_NO if a value was replaced (with REPLACE)
1007  *         #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
1008  *                       value already exists
1009  */
1010 int
1011 GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32
1012                                      *map, uint32_t key, void *value,
1013                                      enum GNUNET_CONTAINER_MultiHashMapOption
1014                                      opt);
1015
1016
1017 /**
1018  * @ingroup hashmap
1019  * Iterate over all entries in the map that match a particular key.
1020  *
1021  * @param map the map
1022  * @param key key that the entries must correspond to
1023  * @param it function to call on each entry
1024  * @param it_cls extra argument to @a it
1025  * @return the number of key value pairs processed,
1026  *         #GNUNET_SYSERR if it aborted iteration
1027  */
1028 int
1029 GNUNET_CONTAINER_multihashmap32_get_multiple (const struct
1030                                               GNUNET_CONTAINER_MultiHashMap32
1031                                               *map, uint32_t key,
1032                                               GNUNET_CONTAINER_HashMapIterator32
1033                                               it, void *it_cls);
1034
1035
1036
1037
1038 /* ******************** doubly-linked list *************** */
1039 /* To avoid mistakes: head->prev == tail->next == NULL     */
1040
1041 /**
1042  * @ingroup dll
1043  * Insert an element at the head of a DLL. Assumes that head, tail and
1044  * element are structs with prev and next fields.
1045  *
1046  * @param head pointer to the head of the DLL
1047  * @param tail pointer to the tail of the DLL
1048  * @param element element to insert
1049  */
1050 #define GNUNET_CONTAINER_DLL_insert(head,tail,element) do { \
1051   GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1052   GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1053   (element)->next = (head); \
1054   (element)->prev = NULL; \
1055   if ((tail) == NULL) \
1056     (tail) = element; \
1057   else \
1058     (head)->prev = element; \
1059   (head) = (element); } while (0)
1060
1061
1062 /**
1063  * @ingroup dll
1064  * Insert an element at the tail of a DLL. Assumes that head, tail and
1065  * element are structs with prev and next fields.
1066  *
1067  * @param head pointer to the head of the DLL
1068  * @param tail pointer to the tail of the DLL
1069  * @param element element to insert
1070  */
1071 #define GNUNET_CONTAINER_DLL_insert_tail(head,tail,element) do { \
1072   GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1073   GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1074   (element)->prev = (tail); \
1075   (element)->next = NULL; \
1076   if ((head) == NULL) \
1077     (head) = element; \
1078   else \
1079     (tail)->next = element; \
1080   (tail) = (element); } while (0)
1081
1082
1083 /**
1084  * @ingroup dll
1085  * Insert an element into a DLL after the given other element.  Insert
1086  * at the head if the other element is NULL.
1087  *
1088  * @param head pointer to the head of the DLL
1089  * @param tail pointer to the tail of the DLL
1090  * @param other prior element, NULL for insertion at head of DLL
1091  * @param element element to insert
1092  */
1093 #define GNUNET_CONTAINER_DLL_insert_after(head,tail,other,element) do { \
1094   GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1095   GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1096   (element)->prev = (other); \
1097   if (NULL == other) \
1098     { \
1099       (element)->next = (head); \
1100       (head) = (element); \
1101     } \
1102   else \
1103     { \
1104       (element)->next = (other)->next; \
1105       (other)->next = (element); \
1106     } \
1107   if (NULL == (element)->next) \
1108     (tail) = (element); \
1109   else \
1110     (element)->next->prev = (element); } while (0)
1111
1112
1113 /**
1114  * @ingroup dll
1115  * Insert an element into a DLL before the given other element.  Insert
1116  * at the tail if the other element is NULL.
1117  *
1118  * @param head pointer to the head of the DLL
1119  * @param tail pointer to the tail of the DLL
1120  * @param other prior element, NULL for insertion at head of DLL
1121  * @param element element to insert
1122  */
1123 #define GNUNET_CONTAINER_DLL_insert_before(head,tail,other,element) do { \
1124   GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1125   GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1126   (element)->next = (other); \
1127   if (NULL == other) \
1128     { \
1129       (element)->prev = (tail); \
1130       (tail) = (element); \
1131     } \
1132   else \
1133     { \
1134       (element)->prev = (other)->prev; \
1135       (other)->prev = (element); \
1136     } \
1137   if (NULL == (element)->prev) \
1138     (head) = (element); \
1139   else \
1140     (element)->prev->next = (element); } while (0)
1141
1142
1143 /**
1144  * @ingroup dll
1145  * Remove an element from a DLL. Assumes that head, tail and
1146  * element point to structs with prev and next fields.
1147  *
1148  * Using the head or tail pointer as the element
1149  * argument does NOT work with this macro.
1150  * Make sure to store head/tail in another pointer
1151  * and use it to remove the head or tail of the list.
1152  *
1153  * @param head pointer to the head of the DLL
1154  * @param tail pointer to the tail of the DLL
1155  * @param element element to remove
1156  */
1157 #define GNUNET_CONTAINER_DLL_remove(head,tail,element) do { \
1158   GNUNET_assert ( ( (element)->prev != NULL) || ((head) == (element))); \
1159   GNUNET_assert ( ( (element)->next != NULL) || ((tail) == (element))); \
1160   if ((element)->prev == NULL) \
1161     (head) = (element)->next;  \
1162   else \
1163     (element)->prev->next = (element)->next; \
1164   if ((element)->next == NULL) \
1165     (tail) = (element)->prev;  \
1166   else \
1167     (element)->next->prev = (element)->prev; \
1168   (element)->next = NULL; \
1169   (element)->prev = NULL; } while (0)
1170
1171
1172 /* ************ Multi-DLL interface, allows DLL elements to be
1173    in multiple lists at the same time *********************** */
1174
1175 /**
1176  * @ingroup dll
1177  * Insert an element at the head of a MDLL. Assumes that head, tail and
1178  * element are structs with prev and next fields.
1179  *
1180  * @param mdll suffix name for the next and prev pointers in the element
1181  * @param head pointer to the head of the MDLL
1182  * @param tail pointer to the tail of the MDLL
1183  * @param element element to insert
1184  */
1185 #define GNUNET_CONTAINER_MDLL_insert(mdll,head,tail,element) do {       \
1186   GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1187   GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1188   (element)->next_##mdll = (head); \
1189   (element)->prev_##mdll = NULL; \
1190   if ((tail) == NULL) \
1191     (tail) = element; \
1192   else \
1193     (head)->prev_##mdll = element; \
1194   (head) = (element); } while (0)
1195
1196
1197 /**
1198  * @ingroup dll
1199  * Insert an element at the tail of a MDLL. Assumes that head, tail and
1200  * element are structs with prev and next fields.
1201  *
1202  * @param mdll suffix name for the next and prev pointers in the element
1203  * @param head pointer to the head of the MDLL
1204  * @param tail pointer to the tail of the MDLL
1205  * @param element element to insert
1206  */
1207 #define GNUNET_CONTAINER_MDLL_insert_tail(mdll,head,tail,element) do {  \
1208   GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1209   GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1210   (element)->prev_##mdll = (tail); \
1211   (element)->next_##mdll = NULL; \
1212   if ((head) == NULL) \
1213     (head) = element; \
1214   else \
1215     (tail)->next_##mdll = element; \
1216   (tail) = (element); } while (0)
1217
1218
1219 /**
1220  * @ingroup dll
1221  * Insert an element into a MDLL after the given other element.  Insert
1222  * at the head if the other element is NULL.
1223  *
1224  * @param mdll suffix name for the next and prev pointers in the element
1225  * @param head pointer to the head of the MDLL
1226  * @param tail pointer to the tail of the MDLL
1227  * @param other prior element, NULL for insertion at head of MDLL
1228  * @param element element to insert
1229  */
1230 #define GNUNET_CONTAINER_MDLL_insert_after(mdll,head,tail,other,element) do { \
1231   GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1232   GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1233   (element)->prev_##mdll = (other); \
1234   if (NULL == other) \
1235     { \
1236       (element)->next_##mdll = (head); \
1237       (head) = (element); \
1238     } \
1239   else \
1240     { \
1241       (element)->next_##mdll = (other)->next_##mdll; \
1242       (other)->next_##mdll = (element); \
1243     } \
1244   if (NULL == (element)->next_##mdll) \
1245     (tail) = (element); \
1246   else \
1247     (element)->next->prev_##mdll = (element); } while (0)
1248
1249
1250 /**
1251  * @ingroup dll
1252  * Insert an element into a MDLL before the given other element.  Insert
1253  * at the tail if the other element is NULL.
1254  *
1255  * @param mdll suffix name for the next and prev pointers in the element
1256  * @param head pointer to the head of the MDLL
1257  * @param tail pointer to the tail of the MDLL
1258  * @param other prior element, NULL for insertion at head of MDLL
1259  * @param element element to insert
1260  */
1261 #define GNUNET_CONTAINER_MDLL_insert_before(mdll,head,tail,other,element) do { \
1262   GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1263   GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1264   (element)->next_##mdll = (other); \
1265   if (NULL == other) \
1266     { \
1267       (element)->prev = (tail); \
1268       (tail) = (element); \
1269     } \
1270   else \
1271     { \
1272       (element)->prev_##mdll = (other)->prev_##mdll; \
1273       (other)->prev_##mdll = (element); \
1274     } \
1275   if (NULL == (element)->prev_##mdll) \
1276     (head) = (element); \
1277   else \
1278     (element)->prev_##mdll->next_##mdll = (element); } while (0)
1279
1280
1281 /**
1282  * @ingroup dll
1283  * Remove an element from a MDLL. Assumes
1284  * that head, tail and element are structs
1285  * with prev and next fields.
1286  *
1287  * @param mdll suffix name for the next and prev pointers in the element
1288  * @param head pointer to the head of the MDLL
1289  * @param tail pointer to the tail of the MDLL
1290  * @param element element to remove
1291  */
1292 #define GNUNET_CONTAINER_MDLL_remove(mdll,head,tail,element) do {       \
1293   GNUNET_assert ( ( (element)->prev_##mdll != NULL) || ((head) == (element))); \
1294   GNUNET_assert ( ( (element)->next_##mdll != NULL) || ((tail) == (element))); \
1295   if ((element)->prev_##mdll == NULL) \
1296     (head) = (element)->next_##mdll;  \
1297   else \
1298     (element)->prev_##mdll->next_##mdll = (element)->next_##mdll; \
1299   if ((element)->next_##mdll == NULL) \
1300     (tail) = (element)->prev_##mdll;  \
1301   else \
1302     (element)->next_##mdll->prev_##mdll = (element)->prev_##mdll; \
1303   (element)->next_##mdll = NULL; \
1304   (element)->prev_##mdll = NULL; } while (0)
1305
1306
1307
1308 /* ******************** Heap *************** */
1309
1310
1311 /**
1312  * @ingroup heap
1313  * Cost by which elements in a heap can be ordered.
1314  */
1315 typedef uint64_t GNUNET_CONTAINER_HeapCostType;
1316
1317
1318 /**
1319  * @ingroup heap
1320  * Heap type, either max or min.
1321  */
1322 enum GNUNET_CONTAINER_HeapOrder
1323 {
1324   /**
1325    * @ingroup heap
1326    * Heap with the maximum cost at the root.
1327    */
1328   GNUNET_CONTAINER_HEAP_ORDER_MAX,
1329
1330   /**
1331    * @ingroup heap
1332    * Heap with the minimum cost at the root.
1333    */
1334   GNUNET_CONTAINER_HEAP_ORDER_MIN
1335 };
1336
1337
1338 /**
1339  * @ingroup heap
1340  * Handle to a Heap.
1341  */
1342 struct GNUNET_CONTAINER_Heap;
1343
1344
1345 /**
1346  * @ingroup heap
1347  * Handle to a node in a heap.
1348  */
1349 struct GNUNET_CONTAINER_HeapNode;
1350
1351
1352 /**
1353  * @ingroup heap
1354  * Create a new heap.
1355  *
1356  * @param order how should the heap be sorted?
1357  * @return handle to the heap
1358  */
1359 struct GNUNET_CONTAINER_Heap *
1360 GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order);
1361
1362
1363 /**
1364  * @ingroup heap
1365  * Destroys the heap.  Only call on a heap that
1366  * is already empty.
1367  *
1368  * @param heap heap to destroy
1369  */
1370 void
1371 GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap);
1372
1373
1374 /**
1375  * @ingroup heap
1376  * Get element stored at root of heap.
1377  *
1378  * @param heap heap to inspect
1379  * @return NULL if heap is empty
1380  */
1381 void *
1382 GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap);
1383
1384
1385 /**
1386  * @ingroup heap
1387  * Get the current size of the heap
1388  *
1389  * @param heap the heap to get the size of
1390  * @return number of elements stored
1391  */
1392 unsigned int
1393 GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap);
1394
1395
1396 /**
1397  * @ingroup heap
1398  * Get the current cost of the node
1399  *
1400  * @param node the node to get the cost of
1401  * @return cost of the node
1402  */
1403 GNUNET_CONTAINER_HeapCostType
1404 GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode
1405                                      *node);
1406
1407 /**
1408  * @ingroup heap
1409  * Iterator for heap
1410  *
1411  * @param cls closure
1412  * @param node internal node of the heap
1413  * @param element value stored at the node
1414  * @param cost cost associated with the node
1415  * @return #GNUNET_YES if we should continue to iterate,
1416  *         #GNUNET_NO if not.
1417  */
1418 typedef int (*GNUNET_CONTAINER_HeapIterator) (void *cls,
1419                                               struct GNUNET_CONTAINER_HeapNode *
1420                                               node, void *element,
1421                                               GNUNET_CONTAINER_HeapCostType
1422                                               cost);
1423
1424
1425 /**
1426  * @ingroup heap
1427  * Iterate over all entries in the heap.
1428  *
1429  * @param heap the heap
1430  * @param iterator function to call on each entry
1431  * @param iterator_cls closure for @a iterator
1432  */
1433 void
1434 GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
1435                                GNUNET_CONTAINER_HeapIterator iterator,
1436                                void *iterator_cls);
1437
1438 /**
1439  * @ingroup heap
1440  * Perform a random walk of the tree.  The walk is biased
1441  * towards elements closer to the root of the tree (since
1442  * each walk starts at the root and ends at a random leaf).
1443  * The heap internally tracks the current position of the
1444  * walk.
1445  *
1446  * @param heap heap to walk
1447  * @return data stored at the next random node in the walk;
1448  *         NULL if the tree is empty.
1449  */
1450 void *
1451 GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap);
1452
1453
1454 /**
1455  * @ingroup heap
1456  * Inserts a new element into the heap.
1457  *
1458  * @param heap heap to modify
1459  * @param element element to insert
1460  * @param cost cost for the element
1461  * @return node for the new element
1462  */
1463 struct GNUNET_CONTAINER_HeapNode *
1464 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, void *element,
1465                               GNUNET_CONTAINER_HeapCostType cost);
1466
1467
1468 /**
1469  * @ingroup heap
1470  * Remove root of the heap.
1471  *
1472  * @param heap heap to modify
1473  * @return element data stored at the root node
1474  */
1475 void *
1476 GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap);
1477
1478
1479 /**
1480  * @ingroup heap
1481  * Removes a node from the heap.
1482  *
1483  * @param node node to remove
1484  * @return element data stored at the node, NULL if heap is empty
1485  */
1486 void *
1487 GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node);
1488
1489
1490 /**
1491  * @ingroup heap
1492  * Updates the cost of any node in the tree
1493  *
1494  * @param heap heap to modify
1495  * @param node node for which the cost is to be changed
1496  * @param new_cost new cost for the node
1497  */
1498 void
1499 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
1500                                    struct GNUNET_CONTAINER_HeapNode *node,
1501                                    GNUNET_CONTAINER_HeapCostType new_cost);
1502
1503
1504 /* ******************** Singly linked list *************** */
1505
1506 /**
1507  * Possible ways for how data stored in the linked list
1508  * might be allocated.
1509  * @deprecated use DLL macros
1510  */
1511 enum GNUNET_CONTAINER_SListDisposition
1512 {
1513   /**
1514    * Single-linked list must copy the buffer.
1515    * @deprecated use DLL macros
1516    */
1517   GNUNET_CONTAINER_SLIST_DISPOSITION_TRANSIENT = 0,
1518
1519   /**
1520    * Data is static, no need to copy or free.
1521    * @deprecated use DLL macros
1522    */
1523   GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC = 2,
1524
1525   /**
1526    * Data is dynamic, do not copy but free when done.
1527    * @deprecated use DLL macros
1528    */
1529   GNUNET_CONTAINER_SLIST_DISPOSITION_DYNAMIC = 4
1530 };
1531
1532
1533
1534 /**
1535  * Handle to a singly linked list
1536  * @deprecated use DLL macros
1537  */
1538 struct GNUNET_CONTAINER_SList;
1539
1540 /**
1541  * Handle to a singly linked list iterator
1542  * @deprecated use DLL macros
1543  */
1544 struct GNUNET_CONTAINER_SList_Iterator
1545 {
1546   /**
1547    * Linked list that we are iterating over.
1548    */
1549   struct GNUNET_CONTAINER_SList *list;
1550
1551   /**
1552    * Last element accessed.
1553    */
1554   struct GNUNET_CONTAINER_SList_Elem *last;
1555
1556   /**
1557    * Current list element.
1558    */
1559   struct GNUNET_CONTAINER_SList_Elem *elem;
1560 };
1561
1562
1563
1564 /**
1565  * Add a new element to the list
1566  * @param l list
1567  * @param disp memory disposition
1568  * @param buf payload buffer
1569  * @param len length of the buffer
1570  * @deprecated use DLL macros
1571  */
1572 void
1573 GNUNET_CONTAINER_slist_add (struct GNUNET_CONTAINER_SList *l,
1574                             enum GNUNET_CONTAINER_SListDisposition disp,
1575                             const void *buf, size_t len);
1576
1577
1578 /**
1579  * Add a new element to the end of the list
1580  * @param l list
1581  * @param disp memory disposition
1582  * @param buf payload buffer
1583  * @param len length of the buffer
1584  * @deprecated use DLL macros
1585  */
1586 void
1587 GNUNET_CONTAINER_slist_add_end (struct GNUNET_CONTAINER_SList *l,
1588                                 enum GNUNET_CONTAINER_SListDisposition disp,
1589                                 const void *buf, size_t len);
1590
1591
1592 /**
1593  * Append a singly linked list to another
1594  * @param dst list to append to
1595  * @param src source
1596  * @deprecated use DLL macros
1597  */
1598 void
1599 GNUNET_CONTAINER_slist_append (struct GNUNET_CONTAINER_SList *dst,
1600                                struct GNUNET_CONTAINER_SList *src);
1601
1602
1603 /**
1604  * Create a new singly linked list
1605  * @return the new list
1606  * @deprecated use DLL macros
1607  */
1608 struct GNUNET_CONTAINER_SList *
1609 GNUNET_CONTAINER_slist_create (void);
1610
1611
1612 /**
1613  * Destroy a singly linked list
1614  * @param l the list to be destroyed
1615  * @deprecated use DLL macros
1616  */
1617 void
1618 GNUNET_CONTAINER_slist_destroy (struct GNUNET_CONTAINER_SList *l);
1619
1620
1621 /**
1622  * Return the beginning of a list
1623  *
1624  * @param l list
1625  * @return iterator pointing to the beginning (by value! Either allocate the
1626  *   structure on the stack, or use GNUNET_malloc() yourself! All other
1627  *   functions do take pointer to this struct though)
1628  * @deprecated use DLL macros
1629  */
1630 struct GNUNET_CONTAINER_SList_Iterator
1631 GNUNET_CONTAINER_slist_begin (struct GNUNET_CONTAINER_SList *l);
1632
1633
1634 /**
1635  * Clear a list
1636  *
1637  * @param l list
1638  * @deprecated use DLL macros
1639  */
1640 void
1641 GNUNET_CONTAINER_slist_clear (struct GNUNET_CONTAINER_SList *l);
1642
1643
1644 /**
1645  * Check if a list contains a certain element
1646  * @param l list
1647  * @param buf payload buffer to find
1648  * @param len length of the payload (number of bytes in buf)
1649  * @return GNUNET_YES if found, GNUNET_NO otherwise
1650  * @deprecated use DLL macros
1651  */
1652 int
1653 GNUNET_CONTAINER_slist_contains (const struct GNUNET_CONTAINER_SList *l,
1654                                  const void *buf, size_t len);
1655
1656 /**
1657  * Check if a list contains a certain element using 'compare' function
1658  *
1659  * @param l list
1660  * @param buf payload buffer to find
1661  * @param len length of the payload (number of bytes in buf)
1662  * @param compare comparison function
1663  *
1664  * @return NULL if the 'buf' could not be found, pointer to the
1665  *         list element, if found
1666  * @deprecated use DLL macros
1667  */
1668 void *
1669 GNUNET_CONTAINER_slist_contains2 (const struct GNUNET_CONTAINER_SList *l,
1670                                   const void *buf, size_t len,
1671                                   int (*compare)(const void *, const size_t, const void *, const size_t));
1672 /**
1673  * Count the elements of a list
1674  * @param l list
1675  * @return number of elements in the list
1676  * @deprecated use DLL macros
1677  */
1678 int
1679 GNUNET_CONTAINER_slist_count (const struct GNUNET_CONTAINER_SList *l);
1680
1681
1682 /**
1683  * Remove an element from the list
1684  * @param i iterator that points to the element to be removed
1685  * @deprecated use DLL macros
1686  */
1687 void
1688 GNUNET_CONTAINER_slist_erase (struct GNUNET_CONTAINER_SList_Iterator *i);
1689
1690
1691 /**
1692  * Insert an element into a list at a specific position
1693  * @param before where to insert the new element
1694  * @param disp memory disposition
1695  * @param buf payload buffer
1696  * @param len length of the payload
1697  * @deprecated use DLL macros
1698  */
1699 void
1700 GNUNET_CONTAINER_slist_insert (struct GNUNET_CONTAINER_SList_Iterator *before,
1701                                enum GNUNET_CONTAINER_SListDisposition disp,
1702                                const void *buf, size_t len);
1703
1704
1705 /**
1706  * Advance an iterator to the next element
1707  * @param i iterator
1708  * @return GNUNET_YES on success, GNUNET_NO if the end has been reached
1709  * @deprecated use DLL macros
1710  */
1711 int
1712 GNUNET_CONTAINER_slist_next (struct GNUNET_CONTAINER_SList_Iterator *i);
1713
1714
1715 /**
1716  * Check if an iterator points beyond the end of a list
1717  * @param i iterator
1718  * @return GNUNET_YES if the end has been reached, GNUNET_NO if the iterator
1719  *         points to a valid element
1720  * @deprecated use DLL macros
1721  */
1722 int
1723 GNUNET_CONTAINER_slist_end (struct GNUNET_CONTAINER_SList_Iterator *i);
1724
1725
1726 /**
1727  * Retrieve the element at a specific position in a list
1728  *
1729  * @param i iterator
1730  * @param len set to the payload length
1731  * @return payload
1732  * @deprecated use DLL macros
1733  */
1734 void *
1735 GNUNET_CONTAINER_slist_get (const struct GNUNET_CONTAINER_SList_Iterator *i,
1736                             size_t *len);
1737
1738
1739 /**
1740  * Release an iterator
1741  * @param i iterator
1742  * @deprecated use DLL macros
1743  */
1744 void
1745 GNUNET_CONTAINER_slist_iter_destroy (struct GNUNET_CONTAINER_SList_Iterator *i);
1746
1747
1748 #if 0                           /* keep Emacsens' auto-indent happy */
1749 {
1750 #endif
1751 #ifdef __cplusplus
1752 }
1753 #endif
1754
1755
1756 /* ifndef GNUNET_CONTAINER_LIB_H */
1757 #endif
1758 /* end of gnunet_container_lib.h */