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  * Opaque handle to an iterator over
1086  * a 32-bit key multihashmap.
1087  */
1088 struct GNUNET_CONTAINER_MultiHashMap32Iterator;
1089
1090
1091 /**
1092  * @ingroup hashmap
1093  * Iterator over hash map entries.
1094  *
1095  * @param cls closure
1096  * @param key current key code
1097  * @param value value in the hash map
1098  * @return #GNUNET_YES if we should continue to
1099  *         iterate,
1100  *         #GNUNET_NO if not.
1101  */
1102 typedef int (*GNUNET_CONTAINER_HashMapIterator32) (void *cls,
1103                                                    uint32_t key,
1104                                                    void *value);
1105
1106
1107 /**
1108  * @ingroup hashmap
1109  * Create a 32-bit key multi hash map.
1110  *
1111  * @param len initial size (map will grow as needed)
1112  * @return NULL on error
1113  */
1114 struct GNUNET_CONTAINER_MultiHashMap32 *
1115 GNUNET_CONTAINER_multihashmap32_create (unsigned int len);
1116
1117
1118 /**
1119  * @ingroup hashmap
1120  * Destroy a 32-bit key hash map.  Will not free any values
1121  * stored in the hash map!
1122  *
1123  * @param map the map
1124  */
1125 void
1126 GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32
1127                                          *map);
1128
1129
1130 /**
1131  * @ingroup hashmap
1132  * Get the number of key-value pairs in the map.
1133  *
1134  * @param map the map
1135  * @return the number of key value pairs
1136  */
1137 unsigned int
1138 GNUNET_CONTAINER_multihashmap32_size (const struct
1139                                       GNUNET_CONTAINER_MultiHashMap32 *map);
1140
1141
1142 /**
1143  * @ingroup hashmap
1144  * Given a key find a value in the map matching the key.
1145  *
1146  * @param map the map
1147  * @param key what to look for
1148  * @return NULL if no value was found; note that
1149  *   this is indistinguishable from values that just
1150  *   happen to be NULL; use "contains" to test for
1151  *   key-value pairs with value NULL
1152  */
1153 void *
1154 GNUNET_CONTAINER_multihashmap32_get (const struct
1155                                      GNUNET_CONTAINER_MultiHashMap32 *map,
1156                                      uint32_t key);
1157
1158
1159 /**
1160  * @ingroup hashmap
1161  * Iterate over all entries in the map.
1162  *
1163  * @param map the map
1164  * @param it function to call on each entry
1165  * @param it_cls extra argument to @a it
1166  * @return the number of key value pairs processed,
1167  *         #GNUNET_SYSERR if it aborted iteration
1168  */
1169 int
1170 GNUNET_CONTAINER_multihashmap32_iterate (const struct
1171                                          GNUNET_CONTAINER_MultiHashMap32 *map,
1172                                          GNUNET_CONTAINER_HashMapIterator32 it,
1173                                          void *it_cls);
1174
1175
1176 /**
1177  * @ingroup hashmap
1178  * Remove the given key-value pair from the map.  Note that if the
1179  * key-value pair is in the map multiple times, only one of the pairs
1180  * will be removed.
1181  *
1182  * @param map the map
1183  * @param key key of the key-value pair
1184  * @param value value of the key-value pair
1185  * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
1186  *  is not in the map
1187  */
1188 int
1189 GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 *map,
1190                                         uint32_t key,
1191                                         const void *value);
1192
1193
1194 /**
1195  * @ingroup hashmap
1196  * Remove all entries for the given key from the map.
1197  * Note that the values would not be "freed".
1198  *
1199  * @param map the map
1200  * @param key identifies values to be removed
1201  * @return number of values removed
1202  */
1203 int
1204 GNUNET_CONTAINER_multihashmap32_remove_all (struct GNUNET_CONTAINER_MultiHashMap32 *map,
1205                                             uint32_t key);
1206
1207
1208 /**
1209  * @ingroup hashmap
1210  * Check if the map contains any value under the given
1211  * key (including values that are NULL).
1212  *
1213  * @param map the map
1214  * @param key the key to test if a value exists for it
1215  * @return #GNUNET_YES if such a value exists,
1216  *         #GNUNET_NO if not
1217  */
1218 int
1219 GNUNET_CONTAINER_multihashmap32_contains (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
1220                                           uint32_t key);
1221
1222
1223 /**
1224  * @ingroup hashmap
1225  * Check if the map contains the given value under the given
1226  * key.
1227  *
1228  * @param map the map
1229  * @param key the key to test if a value exists for it
1230  * @param value value to test for
1231  * @return #GNUNET_YES if such a value exists,
1232  *         #GNUNET_NO if not
1233  */
1234 int
1235 GNUNET_CONTAINER_multihashmap32_contains_value (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
1236                                                 uint32_t key,
1237                                                 const void *value);
1238
1239
1240 /**
1241  * @ingroup hashmap
1242  * Store a key-value pair in the map.
1243  *
1244  * @param map the map
1245  * @param key key to use
1246  * @param value value to use
1247  * @param opt options for put
1248  * @return #GNUNET_OK on success,
1249  *         #GNUNET_NO if a value was replaced (with REPLACE)
1250  *         #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the
1251  *                       value already exists
1252  */
1253 int
1254 GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32 *map,
1255                                      uint32_t key,
1256                                      void *value,
1257                                      enum GNUNET_CONTAINER_MultiHashMapOption opt);
1258
1259
1260 /**
1261  * @ingroup hashmap
1262  * Iterate over all entries in the map that match a particular key.
1263  *
1264  * @param map the map
1265  * @param key key that the entries must correspond to
1266  * @param it function to call on each entry
1267  * @param it_cls extra argument to @a it
1268  * @return the number of key value pairs processed,
1269  *         #GNUNET_SYSERR if it aborted iteration
1270  */
1271 int
1272 GNUNET_CONTAINER_multihashmap32_get_multiple (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
1273                                               uint32_t key,
1274                                               GNUNET_CONTAINER_HashMapIterator32 it,
1275                                               void *it_cls);
1276
1277
1278 /**
1279  * Create an iterator for a 32-bit multihashmap.
1280  * The iterator can be used to retrieve all the elements in the multihashmap
1281  * one by one, without having to handle all elements at once (in contrast to
1282  * #GNUNET_CONTAINER_multihashmap32_iterate).  Note that the iterator can not be
1283  * used anymore if elements have been removed from 'map' after the creation of
1284  * the iterator, or 'map' has been destroyed.  Adding elements to 'map' may
1285  * result in skipped or repeated elements.
1286  *
1287  * @param map the map to create an iterator for
1288  * @return an iterator over the given multihashmap map
1289  */
1290 struct GNUNET_CONTAINER_MultiHashMap32Iterator *
1291 GNUNET_CONTAINER_multihashmap32_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap32 *map);
1292
1293
1294 /**
1295  * Retrieve the next element from the hash map at the iterator's position.
1296  * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
1297  * are not modified.
1298  * This operation is only allowed if no elements have been removed from the
1299  * multihashmap since the creation of 'iter', and the map has not been destroyed.
1300  * Adding elements may result in repeating or skipping elements.
1301  *
1302  * @param iter the iterator to get the next element from
1303  * @param key pointer to store the key in, can be NULL
1304  * @param value pointer to store the value in, can be NULL
1305  * @return #GNUNET_YES we returned an element,
1306  *         #GNUNET_NO if we are out of elements
1307  */
1308 int
1309 GNUNET_CONTAINER_multihashmap32_iterator_next (struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter,
1310                                                uint32_t *key,
1311                                                const void **value);
1312
1313
1314 /**
1315  * Destroy a 32-bit multihashmap iterator.
1316  *
1317  * @param iter the iterator to destroy
1318  */
1319 void
1320 GNUNET_CONTAINER_multihashmap32_iterator_destroy (struct GNUNET_CONTAINER_MultiHashMapIterator *iter);
1321
1322
1323 /* ******************** doubly-linked list *************** */
1324 /* To avoid mistakes: head->prev == tail->next == NULL     */
1325
1326 /**
1327  * @ingroup dll
1328  * Insert an element at the head of a DLL. Assumes that head, tail and
1329  * element are structs with prev and next fields.
1330  *
1331  * @param head pointer to the head of the DLL
1332  * @param tail pointer to the tail of the DLL
1333  * @param element element to insert
1334  */
1335 #define GNUNET_CONTAINER_DLL_insert(head,tail,element) do { \
1336   GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1337   GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1338   (element)->next = (head); \
1339   (element)->prev = NULL; \
1340   if ((tail) == NULL) \
1341     (tail) = element; \
1342   else \
1343     (head)->prev = element; \
1344   (head) = (element); } while (0)
1345
1346
1347 /**
1348  * @ingroup dll
1349  * Insert an element at the tail of a DLL. Assumes that head, tail and
1350  * element are structs with prev and next fields.
1351  *
1352  * @param head pointer to the head of the DLL
1353  * @param tail pointer to the tail of the DLL
1354  * @param element element to insert
1355  */
1356 #define GNUNET_CONTAINER_DLL_insert_tail(head,tail,element) do { \
1357   GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1358   GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1359   (element)->prev = (tail); \
1360   (element)->next = NULL; \
1361   if ((head) == NULL) \
1362     (head) = element; \
1363   else \
1364     (tail)->next = element; \
1365   (tail) = (element); } while (0)
1366
1367
1368 /**
1369  * @ingroup dll
1370  * Insert an element into a DLL after the given other element.  Insert
1371  * at the head if the other element is NULL.
1372  *
1373  * @param head pointer to the head of the DLL
1374  * @param tail pointer to the tail of the DLL
1375  * @param other prior element, NULL for insertion at head of DLL
1376  * @param element element to insert
1377  */
1378 #define GNUNET_CONTAINER_DLL_insert_after(head,tail,other,element) do { \
1379   GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1380   GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1381   (element)->prev = (other); \
1382   if (NULL == other) \
1383     { \
1384       (element)->next = (head); \
1385       (head) = (element); \
1386     } \
1387   else \
1388     { \
1389       (element)->next = (other)->next; \
1390       (other)->next = (element); \
1391     } \
1392   if (NULL == (element)->next) \
1393     (tail) = (element); \
1394   else \
1395     (element)->next->prev = (element); } while (0)
1396
1397
1398 /**
1399  * @ingroup dll
1400  * Insert an element into a DLL before the given other element.  Insert
1401  * at the tail if the other element is NULL.
1402  *
1403  * @param head pointer to the head of the DLL
1404  * @param tail pointer to the tail of the DLL
1405  * @param other prior element, NULL for insertion at head of DLL
1406  * @param element element to insert
1407  */
1408 #define GNUNET_CONTAINER_DLL_insert_before(head,tail,other,element) do { \
1409   GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
1410   GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
1411   (element)->next = (other); \
1412   if (NULL == other) \
1413     { \
1414       (element)->prev = (tail); \
1415       (tail) = (element); \
1416     } \
1417   else \
1418     { \
1419       (element)->prev = (other)->prev; \
1420       (other)->prev = (element); \
1421     } \
1422   if (NULL == (element)->prev) \
1423     (head) = (element); \
1424   else \
1425     (element)->prev->next = (element); } while (0)
1426
1427
1428 /**
1429  * @ingroup dll
1430  * Remove an element from a DLL. Assumes that head, tail and
1431  * element point to structs with prev and next fields.
1432  *
1433  * Using the head or tail pointer as the element
1434  * argument does NOT work with this macro.
1435  * Make sure to store head/tail in another pointer
1436  * and use it to remove the head or tail of the list.
1437  *
1438  * @param head pointer to the head of the DLL
1439  * @param tail pointer to the tail of the DLL
1440  * @param element element to remove
1441  */
1442 #define GNUNET_CONTAINER_DLL_remove(head,tail,element) do { \
1443   GNUNET_assert ( ( (element)->prev != NULL) || ((head) == (element))); \
1444   GNUNET_assert ( ( (element)->next != NULL) || ((tail) == (element))); \
1445   if ((element)->prev == NULL) \
1446     (head) = (element)->next;  \
1447   else \
1448     (element)->prev->next = (element)->next; \
1449   if ((element)->next == NULL) \
1450     (tail) = (element)->prev;  \
1451   else \
1452     (element)->next->prev = (element)->prev; \
1453   (element)->next = NULL; \
1454   (element)->prev = NULL; } while (0)
1455
1456
1457 /* ************ Multi-DLL interface, allows DLL elements to be
1458    in multiple lists at the same time *********************** */
1459
1460 /**
1461  * @ingroup dll
1462  * Insert an element at the head of a MDLL. Assumes that head, tail and
1463  * element are structs with prev and next fields.
1464  *
1465  * @param mdll suffix name for the next and prev pointers in the element
1466  * @param head pointer to the head of the MDLL
1467  * @param tail pointer to the tail of the MDLL
1468  * @param element element to insert
1469  */
1470 #define GNUNET_CONTAINER_MDLL_insert(mdll,head,tail,element) do {       \
1471   GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1472   GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1473   (element)->next_##mdll = (head); \
1474   (element)->prev_##mdll = NULL; \
1475   if ((tail) == NULL) \
1476     (tail) = element; \
1477   else \
1478     (head)->prev_##mdll = element; \
1479   (head) = (element); } while (0)
1480
1481
1482 /**
1483  * @ingroup dll
1484  * Insert an element at the tail of a MDLL. Assumes that head, tail and
1485  * element are structs with prev and next fields.
1486  *
1487  * @param mdll suffix name for the next and prev pointers in the element
1488  * @param head pointer to the head of the MDLL
1489  * @param tail pointer to the tail of the MDLL
1490  * @param element element to insert
1491  */
1492 #define GNUNET_CONTAINER_MDLL_insert_tail(mdll,head,tail,element) do {  \
1493   GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1494   GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1495   (element)->prev_##mdll = (tail); \
1496   (element)->next_##mdll = NULL; \
1497   if ((head) == NULL) \
1498     (head) = element; \
1499   else \
1500     (tail)->next_##mdll = element; \
1501   (tail) = (element); } while (0)
1502
1503
1504 /**
1505  * @ingroup dll
1506  * Insert an element into a MDLL after the given other element.  Insert
1507  * at the head if the other element is NULL.
1508  *
1509  * @param mdll suffix name for the next and prev pointers in the element
1510  * @param head pointer to the head of the MDLL
1511  * @param tail pointer to the tail of the MDLL
1512  * @param other prior element, NULL for insertion at head of MDLL
1513  * @param element element to insert
1514  */
1515 #define GNUNET_CONTAINER_MDLL_insert_after(mdll,head,tail,other,element) do { \
1516   GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1517   GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1518   (element)->prev_##mdll = (other); \
1519   if (NULL == other) \
1520     { \
1521       (element)->next_##mdll = (head); \
1522       (head) = (element); \
1523     } \
1524   else \
1525     { \
1526       (element)->next_##mdll = (other)->next_##mdll; \
1527       (other)->next_##mdll = (element); \
1528     } \
1529   if (NULL == (element)->next_##mdll) \
1530     (tail) = (element); \
1531   else \
1532     (element)->next->prev_##mdll = (element); } while (0)
1533
1534
1535 /**
1536  * @ingroup dll
1537  * Insert an element into a MDLL before the given other element.  Insert
1538  * at the tail if the other element is NULL.
1539  *
1540  * @param mdll suffix name for the next and prev pointers in the element
1541  * @param head pointer to the head of the MDLL
1542  * @param tail pointer to the tail of the MDLL
1543  * @param other prior element, NULL for insertion at head of MDLL
1544  * @param element element to insert
1545  */
1546 #define GNUNET_CONTAINER_MDLL_insert_before(mdll,head,tail,other,element) do { \
1547   GNUNET_assert ( ( (element)->prev_##mdll == NULL) && ((head) != (element))); \
1548   GNUNET_assert ( ( (element)->next_##mdll == NULL) && ((tail) != (element))); \
1549   (element)->next_##mdll = (other); \
1550   if (NULL == other) \
1551     { \
1552       (element)->prev = (tail); \
1553       (tail) = (element); \
1554     } \
1555   else \
1556     { \
1557       (element)->prev_##mdll = (other)->prev_##mdll; \
1558       (other)->prev_##mdll = (element); \
1559     } \
1560   if (NULL == (element)->prev_##mdll) \
1561     (head) = (element); \
1562   else \
1563     (element)->prev_##mdll->next_##mdll = (element); } while (0)
1564
1565
1566 /**
1567  * @ingroup dll
1568  * Remove an element from a MDLL. Assumes
1569  * that head, tail and element are structs
1570  * with prev and next fields.
1571  *
1572  * @param mdll suffix name for the next and prev pointers in the element
1573  * @param head pointer to the head of the MDLL
1574  * @param tail pointer to the tail of the MDLL
1575  * @param element element to remove
1576  */
1577 #define GNUNET_CONTAINER_MDLL_remove(mdll,head,tail,element) do {       \
1578   GNUNET_assert ( ( (element)->prev_##mdll != NULL) || ((head) == (element))); \
1579   GNUNET_assert ( ( (element)->next_##mdll != NULL) || ((tail) == (element))); \
1580   if ((element)->prev_##mdll == NULL) \
1581     (head) = (element)->next_##mdll;  \
1582   else \
1583     (element)->prev_##mdll->next_##mdll = (element)->next_##mdll; \
1584   if ((element)->next_##mdll == NULL) \
1585     (tail) = (element)->prev_##mdll;  \
1586   else \
1587     (element)->next_##mdll->prev_##mdll = (element)->prev_##mdll; \
1588   (element)->next_##mdll = NULL; \
1589   (element)->prev_##mdll = NULL; } while (0)
1590
1591
1592
1593 /* ******************** Heap *************** */
1594
1595
1596 /**
1597  * @ingroup heap
1598  * Cost by which elements in a heap can be ordered.
1599  */
1600 typedef uint64_t GNUNET_CONTAINER_HeapCostType;
1601
1602
1603 /**
1604  * @ingroup heap
1605  * Heap type, either max or min.
1606  */
1607 enum GNUNET_CONTAINER_HeapOrder
1608 {
1609   /**
1610    * @ingroup heap
1611    * Heap with the maximum cost at the root.
1612    */
1613   GNUNET_CONTAINER_HEAP_ORDER_MAX,
1614
1615   /**
1616    * @ingroup heap
1617    * Heap with the minimum cost at the root.
1618    */
1619   GNUNET_CONTAINER_HEAP_ORDER_MIN
1620 };
1621
1622
1623 /**
1624  * @ingroup heap
1625  * Handle to a Heap.
1626  */
1627 struct GNUNET_CONTAINER_Heap;
1628
1629
1630 /**
1631  * @ingroup heap
1632  * Handle to a node in a heap.
1633  */
1634 struct GNUNET_CONTAINER_HeapNode;
1635
1636
1637 /**
1638  * @ingroup heap
1639  * Create a new heap.
1640  *
1641  * @param order how should the heap be sorted?
1642  * @return handle to the heap
1643  */
1644 struct GNUNET_CONTAINER_Heap *
1645 GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order);
1646
1647
1648 /**
1649  * @ingroup heap
1650  * Destroys the heap.  Only call on a heap that
1651  * is already empty.
1652  *
1653  * @param heap heap to destroy
1654  */
1655 void
1656 GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap);
1657
1658
1659 /**
1660  * @ingroup heap
1661  * Get element stored at root of heap.
1662  *
1663  * @param heap heap to inspect
1664  * @return NULL if heap is empty
1665  */
1666 void *
1667 GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap);
1668
1669
1670 /**
1671  * @ingroup heap
1672  * Get the current size of the heap
1673  *
1674  * @param heap the heap to get the size of
1675  * @return number of elements stored
1676  */
1677 unsigned int
1678 GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap);
1679
1680
1681 /**
1682  * @ingroup heap
1683  * Get the current cost of the node
1684  *
1685  * @param node the node to get the cost of
1686  * @return cost of the node
1687  */
1688 GNUNET_CONTAINER_HeapCostType
1689 GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode
1690                                      *node);
1691
1692 /**
1693  * @ingroup heap
1694  * Iterator for heap
1695  *
1696  * @param cls closure
1697  * @param node internal node of the heap
1698  * @param element value stored at the node
1699  * @param cost cost associated with the node
1700  * @return #GNUNET_YES if we should continue to iterate,
1701  *         #GNUNET_NO if not.
1702  */
1703 typedef int (*GNUNET_CONTAINER_HeapIterator) (void *cls,
1704                                               struct GNUNET_CONTAINER_HeapNode *
1705                                               node, void *element,
1706                                               GNUNET_CONTAINER_HeapCostType
1707                                               cost);
1708
1709
1710 /**
1711  * @ingroup heap
1712  * Iterate over all entries in the heap.
1713  *
1714  * @param heap the heap
1715  * @param iterator function to call on each entry
1716  * @param iterator_cls closure for @a iterator
1717  */
1718 void
1719 GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
1720                                GNUNET_CONTAINER_HeapIterator iterator,
1721                                void *iterator_cls);
1722
1723 /**
1724  * @ingroup heap
1725  * Perform a random walk of the tree.  The walk is biased
1726  * towards elements closer to the root of the tree (since
1727  * each walk starts at the root and ends at a random leaf).
1728  * The heap internally tracks the current position of the
1729  * walk.
1730  *
1731  * @param heap heap to walk
1732  * @return data stored at the next random node in the walk;
1733  *         NULL if the tree is empty.
1734  */
1735 void *
1736 GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap);
1737
1738
1739 /**
1740  * @ingroup heap
1741  * Inserts a new element into the heap.
1742  *
1743  * @param heap heap to modify
1744  * @param element element to insert
1745  * @param cost cost for the element
1746  * @return node for the new element
1747  */
1748 struct GNUNET_CONTAINER_HeapNode *
1749 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, void *element,
1750                               GNUNET_CONTAINER_HeapCostType cost);
1751
1752
1753 /**
1754  * @ingroup heap
1755  * Remove root of the heap.
1756  *
1757  * @param heap heap to modify
1758  * @return element data stored at the root node
1759  */
1760 void *
1761 GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap);
1762
1763
1764 /**
1765  * @ingroup heap
1766  * Removes a node from the heap.
1767  *
1768  * @param node node to remove
1769  * @return element data stored at the node, NULL if heap is empty
1770  */
1771 void *
1772 GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node);
1773
1774
1775 /**
1776  * @ingroup heap
1777  * Updates the cost of any node in the tree
1778  *
1779  * @param heap heap to modify
1780  * @param node node for which the cost is to be changed
1781  * @param new_cost new cost for the node
1782  */
1783 void
1784 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
1785                                    struct GNUNET_CONTAINER_HeapNode *node,
1786                                    GNUNET_CONTAINER_HeapCostType new_cost);
1787
1788
1789 /* ******************** Singly linked list *************** */
1790
1791 /**
1792  * Possible ways for how data stored in the linked list
1793  * might be allocated.
1794  * @deprecated use DLL macros
1795  */
1796 enum GNUNET_CONTAINER_SListDisposition
1797 {
1798   /**
1799    * Single-linked list must copy the buffer.
1800    * @deprecated use DLL macros
1801    */
1802   GNUNET_CONTAINER_SLIST_DISPOSITION_TRANSIENT = 0,
1803
1804   /**
1805    * Data is static, no need to copy or free.
1806    * @deprecated use DLL macros
1807    */
1808   GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC = 2,
1809
1810   /**
1811    * Data is dynamic, do not copy but free when done.
1812    * @deprecated use DLL macros
1813    */
1814   GNUNET_CONTAINER_SLIST_DISPOSITION_DYNAMIC = 4
1815 };
1816
1817
1818
1819 /**
1820  * Handle to a singly linked list
1821  * @deprecated use DLL macros
1822  */
1823 struct GNUNET_CONTAINER_SList;
1824
1825 /**
1826  * Handle to a singly linked list iterator
1827  * @deprecated use DLL macros
1828  */
1829 struct GNUNET_CONTAINER_SList_Iterator
1830 {
1831   /**
1832    * Linked list that we are iterating over.
1833    */
1834   struct GNUNET_CONTAINER_SList *list;
1835
1836   /**
1837    * Last element accessed.
1838    */
1839   struct GNUNET_CONTAINER_SList_Elem *last;
1840
1841   /**
1842    * Current list element.
1843    */
1844   struct GNUNET_CONTAINER_SList_Elem *elem;
1845 };
1846
1847
1848
1849 /**
1850  * Add a new element to the list
1851  * @param l list
1852  * @param disp memory disposition
1853  * @param buf payload buffer
1854  * @param len length of the buffer
1855  * @deprecated use DLL macros
1856  */
1857 void
1858 GNUNET_CONTAINER_slist_add (struct GNUNET_CONTAINER_SList *l,
1859                             enum GNUNET_CONTAINER_SListDisposition disp,
1860                             const void *buf, size_t len);
1861
1862
1863 /**
1864  * Add a new element to the end of the list
1865  * @param l list
1866  * @param disp memory disposition
1867  * @param buf payload buffer
1868  * @param len length of the buffer
1869  * @deprecated use DLL macros
1870  */
1871 void
1872 GNUNET_CONTAINER_slist_add_end (struct GNUNET_CONTAINER_SList *l,
1873                                 enum GNUNET_CONTAINER_SListDisposition disp,
1874                                 const void *buf, size_t len);
1875
1876
1877 /**
1878  * Append a singly linked list to another
1879  * @param dst list to append to
1880  * @param src source
1881  * @deprecated use DLL macros
1882  */
1883 void
1884 GNUNET_CONTAINER_slist_append (struct GNUNET_CONTAINER_SList *dst,
1885                                struct GNUNET_CONTAINER_SList *src);
1886
1887
1888 /**
1889  * Create a new singly linked list
1890  * @return the new list
1891  * @deprecated use DLL macros
1892  */
1893 struct GNUNET_CONTAINER_SList *
1894 GNUNET_CONTAINER_slist_create (void);
1895
1896
1897 /**
1898  * Destroy a singly linked list
1899  * @param l the list to be destroyed
1900  * @deprecated use DLL macros
1901  */
1902 void
1903 GNUNET_CONTAINER_slist_destroy (struct GNUNET_CONTAINER_SList *l);
1904
1905
1906 /**
1907  * Return the beginning of a list
1908  *
1909  * @param l list
1910  * @return iterator pointing to the beginning (by value! Either allocate the
1911  *   structure on the stack, or use GNUNET_malloc() yourself! All other
1912  *   functions do take pointer to this struct though)
1913  * @deprecated use DLL macros
1914  */
1915 struct GNUNET_CONTAINER_SList_Iterator
1916 GNUNET_CONTAINER_slist_begin (struct GNUNET_CONTAINER_SList *l);
1917
1918
1919 /**
1920  * Clear a list
1921  *
1922  * @param l list
1923  * @deprecated use DLL macros
1924  */
1925 void
1926 GNUNET_CONTAINER_slist_clear (struct GNUNET_CONTAINER_SList *l);
1927
1928
1929 /**
1930  * Check if a list contains a certain element
1931  * @param l list
1932  * @param buf payload buffer to find
1933  * @param len length of the payload (number of bytes in buf)
1934  * @return GNUNET_YES if found, GNUNET_NO otherwise
1935  * @deprecated use DLL macros
1936  */
1937 int
1938 GNUNET_CONTAINER_slist_contains (const struct GNUNET_CONTAINER_SList *l,
1939                                  const void *buf, size_t len);
1940
1941 /**
1942  * Check if a list contains a certain element using 'compare' function
1943  *
1944  * @param l list
1945  * @param buf payload buffer to find
1946  * @param len length of the payload (number of bytes in buf)
1947  * @param compare comparison function
1948  *
1949  * @return NULL if the 'buf' could not be found, pointer to the
1950  *         list element, if found
1951  * @deprecated use DLL macros
1952  */
1953 void *
1954 GNUNET_CONTAINER_slist_contains2 (const struct GNUNET_CONTAINER_SList *l,
1955                                   const void *buf, size_t len,
1956                                   int (*compare)(const void *, const size_t, const void *, const size_t));
1957 /**
1958  * Count the elements of a list
1959  * @param l list
1960  * @return number of elements in the list
1961  * @deprecated use DLL macros
1962  */
1963 int
1964 GNUNET_CONTAINER_slist_count (const struct GNUNET_CONTAINER_SList *l);
1965
1966
1967 /**
1968  * Remove an element from the list
1969  * @param i iterator that points to the element to be removed
1970  * @deprecated use DLL macros
1971  */
1972 void
1973 GNUNET_CONTAINER_slist_erase (struct GNUNET_CONTAINER_SList_Iterator *i);
1974
1975
1976 /**
1977  * Insert an element into a list at a specific position
1978  * @param before where to insert the new element
1979  * @param disp memory disposition
1980  * @param buf payload buffer
1981  * @param len length of the payload
1982  * @deprecated use DLL macros
1983  */
1984 void
1985 GNUNET_CONTAINER_slist_insert (struct GNUNET_CONTAINER_SList_Iterator *before,
1986                                enum GNUNET_CONTAINER_SListDisposition disp,
1987                                const void *buf, size_t len);
1988
1989
1990 /**
1991  * Advance an iterator to the next element
1992  * @param i iterator
1993  * @return GNUNET_YES on success, GNUNET_NO if the end has been reached
1994  * @deprecated use DLL macros
1995  */
1996 int
1997 GNUNET_CONTAINER_slist_next (struct GNUNET_CONTAINER_SList_Iterator *i);
1998
1999
2000 /**
2001  * Check if an iterator points beyond the end of a list
2002  * @param i iterator
2003  * @return GNUNET_YES if the end has been reached, GNUNET_NO if the iterator
2004  *         points to a valid element
2005  * @deprecated use DLL macros
2006  */
2007 int
2008 GNUNET_CONTAINER_slist_end (struct GNUNET_CONTAINER_SList_Iterator *i);
2009
2010
2011 /**
2012  * Retrieve the element at a specific position in a list
2013  *
2014  * @param i iterator
2015  * @param len set to the payload length
2016  * @return payload
2017  * @deprecated use DLL macros
2018  */
2019 void *
2020 GNUNET_CONTAINER_slist_get (const struct GNUNET_CONTAINER_SList_Iterator *i,
2021                             size_t *len);
2022
2023
2024 /**
2025  * Release an iterator
2026  * @param i iterator
2027  * @deprecated use DLL macros
2028  */
2029 void
2030 GNUNET_CONTAINER_slist_iter_destroy (struct GNUNET_CONTAINER_SList_Iterator *i);
2031
2032
2033 #if 0                           /* keep Emacsens' auto-indent happy */
2034 {
2035 #endif
2036 #ifdef __cplusplus
2037 }
2038 #endif
2039
2040
2041 /* ifndef GNUNET_CONTAINER_LIB_H */
2042 #endif
2043 /* end of gnunet_container_lib.h */