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