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 *map);
 638
 639
 640 /**
 641  * @ingroup hashmap
 642  * Given a key find a value in the map matching the key.
 643  *
 644  * @param map the map
 645  * @param key what to look for
 646  * @return NULL if no value was found; note that
 647  *   this is indistinguishable from values that just
 648  *   happen to be NULL; use "contains" to test for
 649  *   key-value pairs with value NULL
 650  */
 651 void *
 652 GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap *map,
 653                                    const struct GNUNET_HashCode *key);
 654
 655
 656 /**
 657  * @ingroup hashmap
 658  * Remove the given key-value pair from the map.  Note that if the
 659  * key-value pair is in the map multiple times, only one of the pairs
 660  * will be removed.
 661  *
 662  * @param map the map
 663  * @param key key of the key-value pair
 664  * @param value value of the key-value pair
 665  * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
 666  *  is not in the map
 667  */
 668 int
 669 GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map,
 670                                       const struct GNUNET_HashCode *key,
 671                                       const void *value);
 672
 673 /**
 674  * @ingroup hashmap
 675  * Remove all entries for the given key from the map.
 676  * Note that the values would not be "freed".
 677  *
 678  * @param map the map
 679  * @param key identifies values to be removed
 680  * @return number of values removed
 681  */
 682 int
 683 GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap *map,
 684                                           const struct GNUNET_HashCode *key);
 685
 686
 687 /**
 688  * @ingroup hashmap
 689  * Check if the map contains any value under the given
 690  * key (including values that are NULL).
 691  *
 692  * @param map the map
 693  * @param key the key to test if a value exists for it
 694  * @return #GNUNET_YES if such a value exists,
 695  *         #GNUNET_NO if not
 696  */
 697 int
 698 GNUNET_CONTAINER_multihashmap_contains (const struct 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 GNUNET_CONTAINER_MultiHashMap *map,
 715                                               const struct GNUNET_HashCode *key,
 716                                               const void *value);
 717
 718
 719 /**
 720  * @ingroup hashmap
 721  * Store a key-value pair in the map.
 722  *
 723  * @param map the map
 724  * @param key key to use
 725  * @param value value to use
 726  * @param opt options for put
 727  * @return #GNUNET_OK on success,
 728  *         #GNUNET_NO if a value was replaced (with REPLACE)
 729  *         #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
 730  *                       value already exists
 731  */
 732 int
 733 GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map,
 734                                    const struct GNUNET_HashCode * key, void *value,
 735                                    enum GNUNET_CONTAINER_MultiHashMapOption
 736                                    opt);
 737
 738 /**
 739  * @ingroup hashmap
 740  * Get the number of key-value pairs in the map.
 741  *
 742  * @param map the map
 743  * @return the number of key value pairs
 744  */
 745 unsigned int
 746 GNUNET_CONTAINER_multihashmap_size (const struct GNUNET_CONTAINER_MultiHashMap
 747                                     *map);
 748
 749
 750 /**
 751  * @ingroup hashmap
 752  * Iterate over all entries in the map.
 753  *
 754  * @param map the map
 755  * @param it function to call on each entry
 756  * @param it_cls extra argument to @a it
 757  * @return the number of key value pairs processed,
 758  *         #GNUNET_SYSERR if it aborted iteration
 759  */
 760 int
 761 GNUNET_CONTAINER_multihashmap_iterate (const struct
 762                                        GNUNET_CONTAINER_MultiHashMap *map,
 763                                        GNUNET_CONTAINER_HashMapIterator it,
 764                                        void *it_cls);
 765
 766
 767 /**
 768  * @ingroup hashmap
 769  * Create an iterator for a multihashmap.
 770  * The iterator can be used to retrieve all the elements in the multihashmap
 771  * one by one, without having to handle all elements at once (in contrast to
 772  * #GNUNET_CONTAINER_multihashmap_iterate).  Note that the iterator can not be
 773  * used anymore if elements have been removed from 'map' after the creation of
 774  * the iterator, or 'map' has been destroyed.  Adding elements to 'map' may
 775  * result in skipped or repeated elements.
 776  *
 777  * @param map the map to create an iterator for
 778  * @return an iterator over the given multihashmap @a map
 779  */
 780 struct GNUNET_CONTAINER_MultiHashMapIterator *
 781 GNUNET_CONTAINER_multihashmap_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap *map);
 782
 783
 784 /**
 785  * @ingroup hashmap
 786  * Retrieve the next element from the hash map at the iterator's
 787  * position.  If there are no elements left, #GNUNET_NO is returned,
 788  * and @a key and @a value are not modified.  This operation is only
 789  * allowed if no elements have been removed from the multihashmap
 790  * since the creation of @a iter, and the map has not been destroyed.
 791  * Adding elements may result in repeating or skipping elements.
 792  *
 793  * @param iter the iterator to get the next element from
 794  * @param key pointer to store the key in, can be NULL
 795  * @param value pointer to store the value in, can be NULL
 796  * @return #GNUNET_YES we returned an element,
 797  *         #GNUNET_NO if we are out of elements
 798  */
 799 int
 800 GNUNET_CONTAINER_multihashmap_iterator_next (struct GNUNET_CONTAINER_MultiHashMapIterator *iter,
 801                                              struct GNUNET_HashCode *key,
 802                                              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
 834 /* ***************** Version of Multihashmap for peer identities ****************** */
 835
 836 /**
 837  * @ingroup hashmap
 838  * Iterator over hash map entries.
 839  *
 840  * @param cls closure
 841  * @param key current public key
 842  * @param value value in the hash map
 843  * @return #GNUNET_YES if we should continue to
 844  *         iterate,
 845  *         #GNUNET_NO if not.
 846  */
 847 typedef int (*GNUNET_CONTAINER_PeerMapIterator) (void *cls,
 848                                                  const struct GNUNET_PeerIdentity *key,
 849                                                  void *value);
 850
 851
 852 /**
 853  * @ingroup hashmap
 854  * Create a multi peer map (hash map for public keys of peers).
 855  *
 856  * @param len initial size (map will grow as needed)
 857  * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default;
 858  *                         #GNUNET_YES means that on 'put', the 'key' does not have
 859  *                         to be copied as the destination of the pointer is
 860  *                         guaranteed to be life as long as the value is stored in
 861  *                         the hashmap.  This can significantly reduce memory
 862  *                         consumption, but of course is also a recipie for
 863  *                         heap corruption if the assumption is not true.  Only
 864  *                         use this if (1) memory use is important in this case and
 865  *                         (2) you have triple-checked that the invariant holds
 866  * @return NULL on error
 867  */
 868 struct GNUNET_CONTAINER_MultiPeerMap *
 869 GNUNET_CONTAINER_multipeermap_create (unsigned int len,
 870                                       int do_not_copy_keys);
 871
 872
 873 /**
 874  * @ingroup hashmap
 875  * Destroy a hash map.  Will not free any values
 876  * stored in the hash map!
 877  *
 878  * @param map the map
 879  */
 880 void
 881 GNUNET_CONTAINER_multipeermap_destroy (struct GNUNET_CONTAINER_MultiPeerMap *map);
 882
 883
 884 /**
 885  * @ingroup hashmap
 886  * Given a key find a value in the map matching the key.
 887  *
 888  * @param map the map
 889  * @param key what to look for
 890  * @return NULL if no value was found; note that
 891  *   this is indistinguishable from values that just
 892  *   happen to be NULL; use "contains" to test for
 893  *   key-value pairs with value NULL
 894  */
 895 void *
 896 GNUNET_CONTAINER_multipeermap_get (const struct GNUNET_CONTAINER_MultiPeerMap *map,
 897                                    const struct GNUNET_PeerIdentity *key);
 898
 899
 900 /**
 901  * @ingroup hashmap
 902  * Remove the given key-value pair from the map.  Note that if the
 903  * key-value pair is in the map multiple times, only one of the pairs
 904  * will be removed.
 905  *
 906  * @param map the map
 907  * @param key key of the key-value pair
 908  * @param value value of the key-value pair
 909  * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
 910  *  is not in the map
 911  */
 912 int
 913 GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map,
 914                                       const struct GNUNET_PeerIdentity * key,
 915                                       const void *value);
 916
 917 /**
 918  * @ingroup hashmap
 919  * Remove all entries for the given key from the map.
 920  * Note that the values would not be "freed".
 921  *
 922  * @param map the map
 923  * @param key identifies values to be removed
 924  * @return number of values removed
 925  */
 926 int
 927 GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap *map,
 928                                           const struct GNUNET_PeerIdentity *key);
 929
 930
 931 /**
 932  * @ingroup hashmap
 933  * Check if the map contains any value under the given
 934  * key (including values that are NULL).
 935  *
 936  * @param map the map
 937  * @param key the key to test if a value exists for it
 938  * @return #GNUNET_YES if such a value exists,
 939  *         #GNUNET_NO if not
 940  */
 941 int
 942 GNUNET_CONTAINER_multipeermap_contains (const struct GNUNET_CONTAINER_MultiPeerMap *map,
 943                                         const struct GNUNET_PeerIdentity *key);
 944
 945
 946 /**
 947  * @ingroup hashmap
 948  * Check if the map contains the given value under the given
 949  * key.
 950  *
 951  * @param map the map
 952  * @param key the key to test if a value exists for it
 953  * @param value value to test for
 954  * @return #GNUNET_YES if such a value exists,
 955  *         #GNUNET_NO if not
 956  */
 957 int
 958 GNUNET_CONTAINER_multipeermap_contains_value (const struct GNUNET_CONTAINER_MultiPeerMap *map,
 959                                               const struct GNUNET_PeerIdentity * key,
 960                                               const void *value);
 961
 962
 963 /**
 964  * @ingroup hashmap
 965  * Store a key-value pair in the map.
 966  *
 967  * @param map the map
 968  * @param key key to use
 969  * @param value value to use
 970  * @param opt options for put
 971  * @return #GNUNET_OK on success,
 972  *         #GNUNET_NO if a value was replaced (with REPLACE)
 973  *         #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
 974  *                       value already exists
 975  */
 976 int
 977 GNUNET_CONTAINER_multipeermap_put (struct GNUNET_CONTAINER_MultiPeerMap *map,
 978                                    const struct GNUNET_PeerIdentity *key,
 979                                    void *value,
 980                                    enum GNUNET_CONTAINER_MultiHashMapOption opt);
 981
 982
 983 /**
 984  * @ingroup hashmap
 985  * Get the number of key-value pairs in the map.
 986  *
 987  * @param map the map
 988  * @return the number of key value pairs
 989  */
 990 unsigned int
 991 GNUNET_CONTAINER_multipeermap_size (const struct GNUNET_CONTAINER_MultiPeerMap *map);
 992
 993
 994 /**
 995  * @ingroup hashmap
 996  * Iterate over all entries in the map.
 997  *
 998  * @param map the map
 999  * @param it function to call on each entry
1000  * @param it_cls extra argument to @a it
1001  * @return the number of key value pairs processed,
1002  *         #GNUNET_SYSERR if it aborted iteration
1003  */
1004 int
1005 GNUNET_CONTAINER_multipeermap_iterate (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1006                                        GNUNET_CONTAINER_PeerMapIterator it,
1007                                        void *it_cls);
1008
1009
1010 /**
1011  * @ingroup hashmap
1012  * Create an iterator for a multihashmap.
1013  * The iterator can be used to retrieve all the elements in the multihashmap
1014  * one by one, without having to handle all elements at once (in contrast to
1015  * #GNUNET_CONTAINER_multipeermap_iterate).  Note that the iterator can not be
1016  * used anymore if elements have been removed from @a map after the creation of
1017  * the iterator, or 'map' has been destroyed.  Adding elements to @a map may
1018  * result in skipped or repeated elements.
1019  *
1020  * @param map the map to create an iterator for
1021  * @return an iterator over the given multihashmap @a map
1022  */
1023 struct GNUNET_CONTAINER_MultiPeerMapIterator *
1024 GNUNET_CONTAINER_multipeermap_iterator_create (const struct GNUNET_CONTAINER_MultiPeerMap *map);
1025
1026
1027 /**
1028  * @ingroup hashmap
1029  * Retrieve the next element from the hash map at the iterator's
1030  * position.  If there are no elements left, #GNUNET_NO is returned,
1031  * and @a key and @a value are not modified.  This operation is only
1032  * allowed if no elements have been removed from the multihashmap
1033  * since the creation of @a iter, and the map has not been destroyed.
1034  * Adding elements may result in repeating or skipping elements.
1035  *
1036  * @param iter the iterator to get the next element from
1037  * @param key pointer to store the key in, can be NULL
1038  * @param value pointer to store the value in, can be NULL
1039  * @return #GNUNET_YES we returned an element,
1040  *         #GNUNET_NO if we are out of elements
1041  */
1042 int
1043 GNUNET_CONTAINER_multipeermap_iterator_next (struct GNUNET_CONTAINER_MultiPeerMapIterator *iter,
1044                                              struct GNUNET_PeerIdentity *key,
1045                                              const void **value);
1046
1047
1048 /**
1049  * @ingroup hashmap
1050  * Destroy a multipeermap iterator.
1051  *
1052  * @param iter the iterator to destroy
1053  */
1054 void
1055 GNUNET_CONTAINER_multipeermap_iterator_destroy (struct GNUNET_CONTAINER_MultiPeerMapIterator *iter);
1056
1057
1058 /**
1059  * @ingroup hashmap
1060  * Iterate over all entries in the map that match a particular key.
1061  *
1062  * @param map the map
1063  * @param key public key that the entries must correspond to
1064  * @param it function to call on each entry
1065  * @param it_cls extra argument to @a it
1066  * @return the number of key value pairs processed,
1067  *         #GNUNET_SYSERR if it aborted iteration
1068  */
1069 int
1070 GNUNET_CONTAINER_multipeermap_get_multiple (const struct GNUNET_CONTAINER_MultiPeerMap *map,
1071                                             const struct GNUNET_PeerIdentity *key,
1072                                             GNUNET_CONTAINER_PeerMapIterator it,
1073                                             void *it_cls);
1074
1075
1076
1077 /* Version of multihashmap with 32 bit keys */
1078
1079 /**
1080  * @ingroup hashmap
1081  * Opaque handle for the 32-bit key HashMap.
1082  */
1083 struct GNUNET_CONTAINER_MultiHashMap32;
1084
1085
1086 /**
1087  * @ingroup hashmap
1088  * Iterator over hash map entries.
1089  *
1090  * @param cls closure
1091  * @param key current key code
1092  * @param value value in the hash map
1093  * @return #GNUNET_YES if we should continue to
1094  *         iterate,
1095  *         #GNUNET_NO if not.
1096  */
1097 typedef int (*GNUNET_CONTAINER_HashMapIterator32) (void *cls,
1098                                                    uint32_t key,
1099                                                    void *value);
1100
1101
1102 /**
1103  * @ingroup hashmap
1104  * Create a 32-bit key multi hash map.
1105  *
1106  * @param len initial size (map will grow as needed)
1107  * @return NULL on error
1108  */
1109 struct GNUNET_CONTAINER_MultiHashMap32 *
1110 GNUNET_CONTAINER_multihashmap32_create (unsigned int len);
1111
1112
1113 /**
1114  * @ingroup hashmap
1115  * Destroy a 32-bit key hash map.  Will not free any values
1116  * stored in the hash map!
1117  *
1118  * @param map the map
1119  */
1120 void
1121 GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32
1122                                          *map);
1123
1124
1125 /**
1126  * @ingroup hashmap
1127  * Get the number of key-value pairs in the map.
1128  *
1129  * @param map the map
1130  * @return the number of key value pairs
1131  */
1132 unsigned int
1133 GNUNET_CONTAINER_multihashmap32_size (const struct
1134                                       GNUNET_CONTAINER_MultiHashMap32 *map);
1135
1136
1137 /**
1138  * @ingroup hashmap
1139  * Given a key find a value in the map matching the key.
1140  *
1141  * @param map the map
1142  * @param key what to look for
1143  * @return NULL if no value was found; note that
1144  *   this is indistinguishable from values that just
1145  *   happen to be NULL; use "contains" to test for
1146  *   key-value pairs with value NULL
1147  */
1148 void *
1149 GNUNET_CONTAINER_multihashmap32_get (const struct
1150                                      GNUNET_CONTAINER_MultiHashMap32 *map,
1151                                      uint32_t key);
1152
1153
1154 /**
1155  * @ingroup hashmap
1156  * Iterate over all entries in the map.
1157  *
1158  * @param map the map
1159  * @param it function to call on each entry
1160  * @param it_cls extra argument to @a it
1161  * @return the number of key value pairs processed,
1162  *         #GNUNET_SYSERR if it aborted iteration
1163  */
1164 int
1165 GNUNET_CONTAINER_multihashmap32_iterate (const struct
1166                                          GNUNET_CONTAINER_MultiHashMap32 *map,
1167                                          GNUNET_CONTAINER_HashMapIterator32 it,
1168                                          void *it_cls);
1169
1170
1171 /**
1172  * @ingroup hashmap
1173  * Remove the given key-value pair from the map.  Note that if the
1174  * key-value pair is in the map multiple times, only one of the pairs
1175  * will be removed.
1176  *
1177  * @param map the map
1178  * @param key key of the key-value pair
1179  * @param value value of the key-value pair
1180  * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
1181  *  is not in the map
1182  */
1183 int
1184 GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 *map,
1185                                         uint32_t key,
1186                                         const void *value);
1187
1188
1189 /**
1190  * @ingroup hashmap
1191  * Remove all entries for the given key from the map.
1192  * Note that the values would not be "freed".
1193  *
1194  * @param map the map
1195  * @param key identifies values to be removed
1196  * @return number of values removed
1197  */
1198 int
1199 GNUNET_CONTAINER_multihashmap32_remove_all (struct GNUNET_CONTAINER_MultiHashMap32 *map,
1200                                             uint32_t key);
1201
1202
1203 /**
1204  * @ingroup hashmap
1205  * Check if the map contains any value under the given
1206  * key (including values that are NULL).
1207  *
1208  * @param map the map
1209  * @param key the key to test if a value exists for it
1210  * @return #GNUNET_YES if such a value exists,
1211  *         #GNUNET_NO if not
1212  */
1213 int
1214 GNUNET_CONTAINER_multihashmap32_contains (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
1215                                           uint32_t key);
1216
1217
1218 /**
1219  * @ingroup hashmap
1220  * Check if the map contains the given value under the given
1221  * key.
1222  *
1223  * @param map the map
1224  * @param key the key to test if a value exists for it
1225  * @param value value to test for
1226  * @return #GNUNET_YES if such a value exists,
1227  *         #GNUNET_NO if not
1228  */
1229 int
1230 GNUNET_CONTAINER_multihashmap32_contains_value (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
1231                                                 uint32_t key,
1232                                                 const void *value);
1233
1234
1235 /**
1236  * @ingroup hashmap
1237  * Store a key-value pair in the map.
1238  *
1239  * @param map the map
1240  * @param key key to use
1241  * @param value value to use
1242  * @param opt options for put
1243  * @return #GNUNET_OK on success,
1244  *         #GNUNET_NO if a value was replaced (with REPLACE)
1245  *         #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
1246  *                       value already exists
1247  */
1248 int
1249 GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32 *map,
1250                                      uint32_t key,
1251                                      void *value,
1252                                      enum GNUNET_CONTAINER_MultiHashMapOption opt);
1253
1254
1255 /**
1256  * @ingroup hashmap
1257  * Iterate over all entries in the map that match a particular key.
1258  *
1259  * @param map the map
1260  * @param key key that the entries must correspond to
1261  * @param it function to call on each entry
1262  * @param it_cls extra argument to @a it
1263  * @return the number of key value pairs processed,
1264  *         #GNUNET_SYSERR if it aborted iteration
1265  */
1266 int
1267 GNUNET_CONTAINER_multihashmap32_get_multiple (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
1268                                               uint32_t key,
1269                                               GNUNET_CONTAINER_HashMapIterator32 it,
1270                                               void *it_cls);
1271
1272
1273
1274
1275 /* ******************** doubly-linked list *************** */
1276 /* To avoid mistakes: head->prev == tail->next == NULL     */
1277
1278 /**
1279  * @ingroup dll
1280  * Insert an element at the head of a DLL. Assumes that head, tail and
1281  * element are structs with prev and next fields.
1282  *
1283  * @param head pointer to the head of the DLL
1284  * @param tail pointer to the tail of the DLL
1285  * @param element element to insert
1286  */
1287 #define GNUNET_CONTAINER_DLL_insert(head,tail,element) do { \
1288   GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1289   GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1290   (element)->next = (head); \
1291   (element)->prev = NULL; \
1292   if ((tail) == NULL) \
1293     (tail) = element; \
1294   else \
1295     (head)->prev = element; \
1296   (head) = (element); } while (0)
1297
1298
1299 /**
1300  * @ingroup dll
1301  * Insert an element at the tail of a DLL. Assumes that head, tail and
1302  * element are structs with prev and next fields.
1303  *
1304  * @param head pointer to the head of the DLL
1305  * @param tail pointer to the tail of the DLL
1306  * @param element element to insert
1307  */
1308 #define GNUNET_CONTAINER_DLL_insert_tail(head,tail,element) do { \
1309   GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1310   GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1311   (element)->prev = (tail); \
1312   (element)->next = NULL; \
1313   if ((head) == NULL) \
1314     (head) = element; \
1315   else \
1316     (tail)->next = element; \
1317   (tail) = (element); } while (0)
1318
1319
1320 /**
1321  * @ingroup dll
1322  * Insert an element into a DLL after the given other element.  Insert
1323  * at the head if the other element is NULL.
1324  *
1325  * @param head pointer to the head of the DLL
1326  * @param tail pointer to the tail of the DLL
1327  * @param other prior element, NULL for insertion at head of DLL
1328  * @param element element to insert
1329  */
1330 #define GNUNET_CONTAINER_DLL_insert_after(head,tail,other,element) do { \
1331   GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1332   GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1333   (element)->prev = (other); \
1334   if (NULL == other) \
1335     { \
1336       (element)->next = (head); \
1337       (head) = (element); \
1338     } \
1339   else \
1340     { \
1341       (element)->next = (other)->next; \
1342       (other)->next = (element); \
1343     } \
1344   if (NULL == (element)->next) \
1345     (tail) = (element); \
1346   else \
1347     (element)->next->prev = (element); } while (0)
1348
1349
1350 /**
1351  * @ingroup dll
1352  * Insert an element into a DLL before the given other element.  Insert
1353  * at the tail if the other element is NULL.
1354  *
1355  * @param head pointer to the head of the DLL
1356  * @param tail pointer to the tail of the DLL
1357  * @param other prior element, NULL for insertion at head of DLL
1358  * @param element element to insert
1359  */
1360 #define GNUNET_CONTAINER_DLL_insert_before(head,tail,other,element) do { \
1361   GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1362   GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1363   (element)->next = (other); \
1364   if (NULL == other) \
1365     { \
1366       (element)->prev = (tail); \
1367       (tail) = (element); \
1368     } \
1369   else \
1370     { \
1371       (element)->prev = (other)->prev; \
1372       (other)->prev = (element); \
1373     } \
1374   if (NULL == (element)->prev) \
1375     (head) = (element); \
1376   else \
1377     (element)->prev->next = (element); } while (0)
1378
1379
1380 /**
1381  * @ingroup dll
1382  * Remove an element from a DLL. Assumes that head, tail and
1383  * element point to structs with prev and next fields.
1384  *
1385  * Using the head or tail pointer as the element
1386  * argument does NOT work with this macro.
1387  * Make sure to store head/tail in another pointer
1388  * and use it to remove the head or tail of the list.
1389  *
1390  * @param head pointer to the head of the DLL
1391  * @param tail pointer to the tail of the DLL
1392  * @param element element to remove
1393  */
1394 #define GNUNET_CONTAINER_DLL_remove(head,tail,element) do { \
1395   GNUNET_assert ( ( (element)->prev != NULL) || ((head) == (element))); \
1396   GNUNET_assert ( ( (element)->next != NULL) || ((tail) == (element))); \
1397   if ((element)->prev == NULL) \
1398     (head) = (element)->next;  \
1399   else \
1400     (element)->prev->next = (element)->next; \
1401   if ((element)->next == NULL) \
1402     (tail) = (element)->prev;  \
1403   else \
1404     (element)->next->prev = (element)->prev; \
1405   (element)->next = NULL; \
1406   (element)->prev = NULL; } while (0)
1407
1408
1409 /* ************ Multi-DLL interface, allows DLL elements to be
1410    in multiple lists at the same time *********************** */
1411
1412 /**
1413  * @ingroup dll
1414  * Insert an element at the head of a MDLL. Assumes that head, tail and
1415  * element are structs with prev and next fields.
1416  *
1417  * @param mdll suffix name for the next and prev pointers in the element
1418  * @param head pointer to the head of the MDLL
1419  * @param tail pointer to the tail of the MDLL
1420  * @param element element to insert
1421  */
1422 #define GNUNET_CONTAINER_MDLL_insert(mdll,head,tail,element) do {       \
1423   GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1424   GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1425   (element)->next_##mdll = (head); \
1426   (element)->prev_##mdll = NULL; \
1427   if ((tail) == NULL) \
1428     (tail) = element; \
1429   else \
1430     (head)->prev_##mdll = element; \
1431   (head) = (element); } while (0)
1432
1433
1434 /**
1435  * @ingroup dll
1436  * Insert an element at the tail of a MDLL. Assumes that head, tail and
1437  * element are structs with prev and next fields.
1438  *
1439  * @param mdll suffix name for the next and prev pointers in the element
1440  * @param head pointer to the head of the MDLL
1441  * @param tail pointer to the tail of the MDLL
1442  * @param element element to insert
1443  */
1444 #define GNUNET_CONTAINER_MDLL_insert_tail(mdll,head,tail,element) do {  \
1445   GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1446   GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1447   (element)->prev_##mdll = (tail); \
1448   (element)->next_##mdll = NULL; \
1449   if ((head) == NULL) \
1450     (head) = element; \
1451   else \
1452     (tail)->next_##mdll = element; \
1453   (tail) = (element); } while (0)
1454
1455
1456 /**
1457  * @ingroup dll
1458  * Insert an element into a MDLL after the given other element.  Insert
1459  * at the head if the other element is NULL.
1460  *
1461  * @param mdll suffix name for the next and prev pointers in the element
1462  * @param head pointer to the head of the MDLL
1463  * @param tail pointer to the tail of the MDLL
1464  * @param other prior element, NULL for insertion at head of MDLL
1465  * @param element element to insert
1466  */
1467 #define GNUNET_CONTAINER_MDLL_insert_after(mdll,head,tail,other,element) do { \
1468   GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1469   GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1470   (element)->prev_##mdll = (other); \
1471   if (NULL == other) \
1472     { \
1473       (element)->next_##mdll = (head); \
1474       (head) = (element); \
1475     } \
1476   else \
1477     { \
1478       (element)->next_##mdll = (other)->next_##mdll; \
1479       (other)->next_##mdll = (element); \
1480     } \
1481   if (NULL == (element)->next_##mdll) \
1482     (tail) = (element); \
1483   else \
1484     (element)->next->prev_##mdll = (element); } while (0)
1485
1486
1487 /**
1488  * @ingroup dll
1489  * Insert an element into a MDLL before the given other element.  Insert
1490  * at the tail if the other element is NULL.
1491  *
1492  * @param mdll suffix name for the next and prev pointers in the element
1493  * @param head pointer to the head of the MDLL
1494  * @param tail pointer to the tail of the MDLL
1495  * @param other prior element, NULL for insertion at head of MDLL
1496  * @param element element to insert
1497  */
1498 #define GNUNET_CONTAINER_MDLL_insert_before(mdll,head,tail,other,element) do { \
1499   GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1500   GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1501   (element)->next_##mdll = (other); \
1502   if (NULL == other) \
1503     { \
1504       (element)->prev = (tail); \
1505       (tail) = (element); \
1506     } \
1507   else \
1508     { \
1509       (element)->prev_##mdll = (other)->prev_##mdll; \
1510       (other)->prev_##mdll = (element); \
1511     } \
1512   if (NULL == (element)->prev_##mdll) \
1513     (head) = (element); \
1514   else \
1515     (element)->prev_##mdll->next_##mdll = (element); } while (0)
1516
1517
1518 /**
1519  * @ingroup dll
1520  * Remove an element from a MDLL. Assumes
1521  * that head, tail and element are structs
1522  * with prev and next fields.
1523  *
1524  * @param mdll suffix name for the next and prev pointers in the element
1525  * @param head pointer to the head of the MDLL
1526  * @param tail pointer to the tail of the MDLL
1527  * @param element element to remove
1528  */
1529 #define GNUNET_CONTAINER_MDLL_remove(mdll,head,tail,element) do {       \
1530   GNUNET_assert ( ( (element)->prev_##mdll != NULL) || ((head) == (element))); \
1531   GNUNET_assert ( ( (element)->next_##mdll != NULL) || ((tail) == (element))); \
1532   if ((element)->prev_##mdll == NULL) \
1533     (head) = (element)->next_##mdll;  \
1534   else \
1535     (element)->prev_##mdll->next_##mdll = (element)->next_##mdll; \
1536   if ((element)->next_##mdll == NULL) \
1537     (tail) = (element)->prev_##mdll;  \
1538   else \
1539     (element)->next_##mdll->prev_##mdll = (element)->prev_##mdll; \
1540   (element)->next_##mdll = NULL; \
1541   (element)->prev_##mdll = NULL; } while (0)
1542
1543
1544
1545 /* ******************** Heap *************** */
1546
1547
1548 /**
1549  * @ingroup heap
1550  * Cost by which elements in a heap can be ordered.
1551  */
1552 typedef uint64_t GNUNET_CONTAINER_HeapCostType;
1553
1554
1555 /**
1556  * @ingroup heap
1557  * Heap type, either max or min.
1558  */
1559 enum GNUNET_CONTAINER_HeapOrder
1560 {
1561   /**
1562    * @ingroup heap
1563    * Heap with the maximum cost at the root.
1564    */
1565   GNUNET_CONTAINER_HEAP_ORDER_MAX,
1566
1567   /**
1568    * @ingroup heap
1569    * Heap with the minimum cost at the root.
1570    */
1571   GNUNET_CONTAINER_HEAP_ORDER_MIN
1572 };
1573
1574
1575 /**
1576  * @ingroup heap
1577  * Handle to a Heap.
1578  */
1579 struct GNUNET_CONTAINER_Heap;
1580
1581
1582 /**
1583  * @ingroup heap
1584  * Handle to a node in a heap.
1585  */
1586 struct GNUNET_CONTAINER_HeapNode;
1587
1588
1589 /**
1590  * @ingroup heap
1591  * Create a new heap.
1592  *
1593  * @param order how should the heap be sorted?
1594  * @return handle to the heap
1595  */
1596 struct GNUNET_CONTAINER_Heap *
1597 GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order);
1598
1599
1600 /**
1601  * @ingroup heap
1602  * Destroys the heap.  Only call on a heap that
1603  * is already empty.
1604  *
1605  * @param heap heap to destroy
1606  */
1607 void
1608 GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap);
1609
1610
1611 /**
1612  * @ingroup heap
1613  * Get element stored at root of heap.
1614  *
1615  * @param heap heap to inspect
1616  * @return NULL if heap is empty
1617  */
1618 void *
1619 GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap);
1620
1621
1622 /**
1623  * @ingroup heap
1624  * Get the current size of the heap
1625  *
1626  * @param heap the heap to get the size of
1627  * @return number of elements stored
1628  */
1629 unsigned int
1630 GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap);
1631
1632
1633 /**
1634  * @ingroup heap
1635  * Get the current cost of the node
1636  *
1637  * @param node the node to get the cost of
1638  * @return cost of the node
1639  */
1640 GNUNET_CONTAINER_HeapCostType
1641 GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode
1642                                      *node);
1643
1644 /**
1645  * @ingroup heap
1646  * Iterator for heap
1647  *
1648  * @param cls closure
1649  * @param node internal node of the heap
1650  * @param element value stored at the node
1651  * @param cost cost associated with the node
1652  * @return #GNUNET_YES if we should continue to iterate,
1653  *         #GNUNET_NO if not.
1654  */
1655 typedef int (*GNUNET_CONTAINER_HeapIterator) (void *cls,
1656                                               struct GNUNET_CONTAINER_HeapNode *
1657                                               node, void *element,
1658                                               GNUNET_CONTAINER_HeapCostType
1659                                               cost);
1660
1661
1662 /**
1663  * @ingroup heap
1664  * Iterate over all entries in the heap.
1665  *
1666  * @param heap the heap
1667  * @param iterator function to call on each entry
1668  * @param iterator_cls closure for @a iterator
1669  */
1670 void
1671 GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
1672                                GNUNET_CONTAINER_HeapIterator iterator,
1673                                void *iterator_cls);
1674
1675 /**
1676  * @ingroup heap
1677  * Perform a random walk of the tree.  The walk is biased
1678  * towards elements closer to the root of the tree (since
1679  * each walk starts at the root and ends at a random leaf).
1680  * The heap internally tracks the current position of the
1681  * walk.
1682  *
1683  * @param heap heap to walk
1684  * @return data stored at the next random node in the walk;
1685  *         NULL if the tree is empty.
1686  */
1687 void *
1688 GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap);
1689
1690
1691 /**
1692  * @ingroup heap
1693  * Inserts a new element into the heap.
1694  *
1695  * @param heap heap to modify
1696  * @param element element to insert
1697  * @param cost cost for the element
1698  * @return node for the new element
1699  */
1700 struct GNUNET_CONTAINER_HeapNode *
1701 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, void *element,
1702                               GNUNET_CONTAINER_HeapCostType cost);
1703
1704
1705 /**
1706  * @ingroup heap
1707  * Remove root of the heap.
1708  *
1709  * @param heap heap to modify
1710  * @return element data stored at the root node
1711  */
1712 void *
1713 GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap);
1714
1715
1716 /**
1717  * @ingroup heap
1718  * Removes a node from the heap.
1719  *
1720  * @param node node to remove
1721  * @return element data stored at the node, NULL if heap is empty
1722  */
1723 void *
1724 GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node);
1725
1726
1727 /**
1728  * @ingroup heap
1729  * Updates the cost of any node in the tree
1730  *
1731  * @param heap heap to modify
1732  * @param node node for which the cost is to be changed
1733  * @param new_cost new cost for the node
1734  */
1735 void
1736 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
1737                                    struct GNUNET_CONTAINER_HeapNode *node,
1738                                    GNUNET_CONTAINER_HeapCostType new_cost);
1739
1740
1741 /* ******************** Singly linked list *************** */
1742
1743 /**
1744  * Possible ways for how data stored in the linked list
1745  * might be allocated.
1746  * @deprecated use DLL macros
1747  */
1748 enum GNUNET_CONTAINER_SListDisposition
1749 {
1750   /**
1751    * Single-linked list must copy the buffer.
1752    * @deprecated use DLL macros
1753    */
1754   GNUNET_CONTAINER_SLIST_DISPOSITION_TRANSIENT = 0,
1755
1756   /**
1757    * Data is static, no need to copy or free.
1758    * @deprecated use DLL macros
1759    */
1760   GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC = 2,
1761
1762   /**
1763    * Data is dynamic, do not copy but free when done.
1764    * @deprecated use DLL macros
1765    */
1766   GNUNET_CONTAINER_SLIST_DISPOSITION_DYNAMIC = 4
1767 };
1768
1769
1770
1771 /**
1772  * Handle to a singly linked list
1773  * @deprecated use DLL macros
1774  */
1775 struct GNUNET_CONTAINER_SList;
1776
1777 /**
1778  * Handle to a singly linked list iterator
1779  * @deprecated use DLL macros
1780  */
1781 struct GNUNET_CONTAINER_SList_Iterator
1782 {
1783   /**
1784    * Linked list that we are iterating over.
1785    */
1786   struct GNUNET_CONTAINER_SList *list;
1787
1788   /**
1789    * Last element accessed.
1790    */
1791   struct GNUNET_CONTAINER_SList_Elem *last;
1792
1793   /**
1794    * Current list element.
1795    */
1796   struct GNUNET_CONTAINER_SList_Elem *elem;
1797 };
1798
1799
1800
1801 /**
1802  * Add a new element to the list
1803  * @param l list
1804  * @param disp memory disposition
1805  * @param buf payload buffer
1806  * @param len length of the buffer
1807  * @deprecated use DLL macros
1808  */
1809 void
1810 GNUNET_CONTAINER_slist_add (struct GNUNET_CONTAINER_SList *l,
1811                             enum GNUNET_CONTAINER_SListDisposition disp,
1812                             const void *buf, size_t len);
1813
1814
1815 /**
1816  * Add a new element to the end of the list
1817  * @param l list
1818  * @param disp memory disposition
1819  * @param buf payload buffer
1820  * @param len length of the buffer
1821  * @deprecated use DLL macros
1822  */
1823 void
1824 GNUNET_CONTAINER_slist_add_end (struct GNUNET_CONTAINER_SList *l,
1825                                 enum GNUNET_CONTAINER_SListDisposition disp,
1826                                 const void *buf, size_t len);
1827
1828
1829 /**
1830  * Append a singly linked list to another
1831  * @param dst list to append to
1832  * @param src source
1833  * @deprecated use DLL macros
1834  */
1835 void
1836 GNUNET_CONTAINER_slist_append (struct GNUNET_CONTAINER_SList *dst,
1837                                struct GNUNET_CONTAINER_SList *src);
1838
1839
1840 /**
1841  * Create a new singly linked list
1842  * @return the new list
1843  * @deprecated use DLL macros
1844  */
1845 struct GNUNET_CONTAINER_SList *
1846 GNUNET_CONTAINER_slist_create (void);
1847
1848
1849 /**
1850  * Destroy a singly linked list
1851  * @param l the list to be destroyed
1852  * @deprecated use DLL macros
1853  */
1854 void
1855 GNUNET_CONTAINER_slist_destroy (struct GNUNET_CONTAINER_SList *l);
1856
1857
1858 /**
1859  * Return the beginning of a list
1860  *
1861  * @param l list
1862  * @return iterator pointing to the beginning (by value! Either allocate the
1863  *   structure on the stack, or use GNUNET_malloc() yourself! All other
1864  *   functions do take pointer to this struct though)
1865  * @deprecated use DLL macros
1866  */
1867 struct GNUNET_CONTAINER_SList_Iterator
1868 GNUNET_CONTAINER_slist_begin (struct GNUNET_CONTAINER_SList *l);
1869
1870
1871 /**
1872  * Clear a list
1873  *
1874  * @param l list
1875  * @deprecated use DLL macros
1876  */
1877 void
1878 GNUNET_CONTAINER_slist_clear (struct GNUNET_CONTAINER_SList *l);
1879
1880
1881 /**
1882  * Check if a list contains a certain element
1883  * @param l list
1884  * @param buf payload buffer to find
1885  * @param len length of the payload (number of bytes in buf)
1886  * @return GNUNET_YES if found, GNUNET_NO otherwise
1887  * @deprecated use DLL macros
1888  */
1889 int
1890 GNUNET_CONTAINER_slist_contains (const struct GNUNET_CONTAINER_SList *l,
1891                                  const void *buf, size_t len);
1892
1893 /**
1894  * Check if a list contains a certain element using 'compare' function
1895  *
1896  * @param l list
1897  * @param buf payload buffer to find
1898  * @param len length of the payload (number of bytes in buf)
1899  * @param compare comparison function
1900  *
1901  * @return NULL if the 'buf' could not be found, pointer to the
1902  *         list element, if found
1903  * @deprecated use DLL macros
1904  */
1905 void *
1906 GNUNET_CONTAINER_slist_contains2 (const struct GNUNET_CONTAINER_SList *l,
1907                                   const void *buf, size_t len,
1908                                   int (*compare)(const void *, const size_t, const void *, const size_t));
1909 /**
1910  * Count the elements of a list
1911  * @param l list
1912  * @return number of elements in the list
1913  * @deprecated use DLL macros
1914  */
1915 int
1916 GNUNET_CONTAINER_slist_count (const struct GNUNET_CONTAINER_SList *l);
1917
1918
1919 /**
1920  * Remove an element from the list
1921  * @param i iterator that points to the element to be removed
1922  * @deprecated use DLL macros
1923  */
1924 void
1925 GNUNET_CONTAINER_slist_erase (struct GNUNET_CONTAINER_SList_Iterator *i);
1926
1927
1928 /**
1929  * Insert an element into a list at a specific position
1930  * @param before where to insert the new element
1931  * @param disp memory disposition
1932  * @param buf payload buffer
1933  * @param len length of the payload
1934  * @deprecated use DLL macros
1935  */
1936 void
1937 GNUNET_CONTAINER_slist_insert (struct GNUNET_CONTAINER_SList_Iterator *before,
1938                                enum GNUNET_CONTAINER_SListDisposition disp,
1939                                const void *buf, size_t len);
1940
1941
1942 /**
1943  * Advance an iterator to the next element
1944  * @param i iterator
1945  * @return GNUNET_YES on success, GNUNET_NO if the end has been reached
1946  * @deprecated use DLL macros
1947  */
1948 int
1949 GNUNET_CONTAINER_slist_next (struct GNUNET_CONTAINER_SList_Iterator *i);
1950
1951
1952 /**
1953  * Check if an iterator points beyond the end of a list
1954  * @param i iterator
1955  * @return GNUNET_YES if the end has been reached, GNUNET_NO if the iterator
1956  *         points to a valid element
1957  * @deprecated use DLL macros
1958  */
1959 int
1960 GNUNET_CONTAINER_slist_end (struct GNUNET_CONTAINER_SList_Iterator *i);
1961
1962
1963 /**
1964  * Retrieve the element at a specific position in a list
1965  *
1966  * @param i iterator
1967  * @param len set to the payload length
1968  * @return payload
1969  * @deprecated use DLL macros
1970  */
1971 void *
1972 GNUNET_CONTAINER_slist_get (const struct GNUNET_CONTAINER_SList_Iterator *i,
1973                             size_t *len);
1974
1975
1976 /**
1977  * Release an iterator
1978  * @param i iterator
1979  * @deprecated use DLL macros
1980  */
1981 void
1982 GNUNET_CONTAINER_slist_iter_destroy (struct GNUNET_CONTAINER_SList_Iterator *i);
1983
1984
1985 #if 0                           /* keep Emacsens' auto-indent happy */
1986 {
1987 #endif
1988 #ifdef __cplusplus
1989 }
1990 #endif
1991
1992
1993 /* ifndef GNUNET_CONTAINER_LIB_H */
1994 #endif
1995 /* end of gnunet_container_lib.h */