src/include/gnunet_container_lib.h

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2001, 2002, 2003, 2004, 2005, 2006, 2008, 2009, 2010 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 2, 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  *
  25  * @author Christian Grothoff
  26  * @author Nils Durner
  27  */
  28
  29 #ifndef GNUNET_CONTAINER_LIB_H
  30 #define GNUNET_CONTAINER_LIB_H
  31
  32 /* add error and config prototypes */
  33 #include "gnunet_crypto_lib.h"
  34 #include <extractor.h>
  35
  36 #ifndef EXTRACTOR_METATYPE_GNUNET_ORIGINAL_FILENAME
  37 /* hack for LE < 0.6.3 */
  38 #define EXTRACTOR_METATYPE_GNUNET_ORIGINAL_FILENAME 180
  39 #endif
  40
  41 #ifdef __cplusplus
  42 extern "C"
  43 {
  44 #if 0                           /* keep Emacsens' auto-indent happy */
  45 }
  46 #endif
  47 #endif
  48
  49
  50 /* ******************* bloomfilter ***************** */
  51
  52 /**
  53  * @brief bloomfilter representation (opaque)
  54  */
  55 struct GNUNET_CONTAINER_BloomFilter;
  56
  57 /**
  58  * Iterator over HashCodes.
  59  *
  60  * @param cls closure
  61  * @param next set to the next hash code
  62  * @return GNUNET_YES if next was updated
  63  *         GNUNET_NO if there are no more entries
  64  */
  65 typedef int (*GNUNET_HashCodeIterator) (void *cls, GNUNET_HashCode * next);
  66
  67
  68 /**
  69  * Load a bloom-filter from a file.
  70  *
  71  * @param filename the name of the file (or the prefix)
  72  * @param size the size of the bloom-filter (number of
  73  *        bytes of storage space to use)
  74  * @param k the number of GNUNET_CRYPTO_hash-functions to apply per
  75  *        element (number of bits set per element in the set)
  76  * @return the bloomfilter
  77  */
  78 struct GNUNET_CONTAINER_BloomFilter *GNUNET_CONTAINER_bloomfilter_load (const
  79                                                                         char
  80                                                                         *filename,
  81                                                                         size_t
  82                                                                         size,
  83                                                                         unsigned
  84                                                                         int k);
  85
  86
  87 /**
  88  * Create a bloom filter from raw bits.
  89  *
  90  * @param data the raw bits in memory (maybe NULL,
  91  *        in which case all bits should be considered
  92  *        to be zero).
  93  * @param size the size of the bloom-filter (number of
  94  *        bytes of storage space to use); also size of data
  95  *        -- unless data is NULL.  Must be a power of 2.
  96  * @param k the number of GNUNET_CRYPTO_hash-functions to apply per
  97  *        element (number of bits set per element in the set)
  98  * @return the bloomfilter
  99  */
 100 struct GNUNET_CONTAINER_BloomFilter *GNUNET_CONTAINER_bloomfilter_init (const
 101                                                                         char
 102                                                                         *data,
 103                                                                         size_t
 104                                                                         size,
 105                                                                         unsigned
 106                                                                         int k);
 107
 108
 109 /**
 110  * Copy the raw data of this bloomfilter into
 111  * the given data array.
 112  *
 113  * @param data where to write the data
 114  * @param size the size of the given data array
 115  * @return GNUNET_SYSERR if the data array of the wrong size
 116  */
 117 int GNUNET_CONTAINER_bloomfilter_get_raw_data (const struct
 118                                                GNUNET_CONTAINER_BloomFilter
 119                                                *bf, char *data, size_t size);
 120
 121
 122 /**
 123  * Test if an element is in the filter.
 124  * @param e the element
 125  * @param bf the filter
 126  * @return GNUNET_YES if the element is in the filter, GNUNET_NO if not
 127  */
 128 int GNUNET_CONTAINER_bloomfilter_test (const struct GNUNET_CONTAINER_BloomFilter
 129                                        *bf, const GNUNET_HashCode * e);
 130
 131
 132 /**
 133  * Add an element to the filter
 134  * @param bf the filter
 135  * @param e the element
 136  */
 137 void GNUNET_CONTAINER_bloomfilter_add (struct GNUNET_CONTAINER_BloomFilter
 138                                        *bf, const GNUNET_HashCode * e);
 139
 140
 141 /**
 142  * Remove an element from the filter.
 143  * @param bf the filter
 144  * @param e the element to remove
 145  */
 146 void GNUNET_CONTAINER_bloomfilter_remove (struct GNUNET_CONTAINER_BloomFilter
 147                                           *bf, const GNUNET_HashCode * e);
 148
 149
 150 /**
 151  * Create a copy of a bloomfilter.
 152  *
 153  * @param bf the filter
 154  * @return copy of bf
 155  */
 156 struct GNUNET_CONTAINER_BloomFilter *GNUNET_CONTAINER_bloomfilter_copy (const
 157                                                                         struct
 158                                                                         GNUNET_CONTAINER_BloomFilter
 159                                                                         *bf);
 160
 161
 162
 163 /**
 164  * Free the space associcated with a filter
 165  * in memory, flush to drive if needed (do not
 166  * free the space on the drive)
 167  * @param bf the filter
 168  */
 169 void GNUNET_CONTAINER_bloomfilter_free (struct GNUNET_CONTAINER_BloomFilter
 170                                         *bf);
 171
 172
 173 /**
 174  * Get size of the bloom filter.
 175  *
 176  * @param bf the filter
 177  * @return number of bytes used for the data of the bloom filter
 178  */
 179 size_t
 180
 181
 182
 183
 184
 185
 186
 187
 188
 189
 190
 191 GNUNET_CONTAINER_bloomfilter_get_size (const struct GNUNET_CONTAINER_BloomFilter
 192                                        *bf);
 193
 194
 195 /**
 196  * Reset a bloom filter to empty.
 197  * @param bf the filter
 198  */
 199 void GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter
 200                                          *bf);
 201
 202 /**
 203  * Or the entries of the given raw data array with the
 204  * data of the given bloom filter.  Assumes that
 205  * the size of the data array and the current filter
 206  * match.
 207  *
 208  * @param bf the filter
 209  * @param data data to OR-in
 210  * @param size size of data
 211  * @return GNUNET_OK on success
 212  */
 213 int GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf,
 214                                      const char *data, size_t size);
 215
 216 /**
 217  * Or the entries of the given raw data array with the
 218  * data of the given bloom filter.  Assumes that
 219  * the size of the data array and the current filter
 220  * match.
 221  *
 222  * @param bf the filter
 223  * @param to_or the bloomfilter to or-in
 224  * @param size number of bytes in data
 225  */
 226 int
 227 GNUNET_CONTAINER_bloomfilter_or2 (struct GNUNET_CONTAINER_BloomFilter *bf,
 228                                   const struct GNUNET_CONTAINER_BloomFilter
 229                                   *to_or, size_t size);
 230
 231 /**
 232  * Resize a bloom filter.  Note that this operation
 233  * is pretty costly.  Essentially, the bloom filter
 234  * needs to be completely re-build.
 235  *
 236  * @param bf the filter
 237  * @param iterator an iterator over all elements stored in the BF
 238  * @param iterator_cls closure for iterator
 239  * @param size the new size for the filter
 240  * @param k the new number of GNUNET_CRYPTO_hash-function to apply per element
 241  */
 242 void GNUNET_CONTAINER_bloomfilter_resize (struct GNUNET_CONTAINER_BloomFilter
 243                                           *bf,
 244                                           GNUNET_HashCodeIterator iterator,
 245                                           void *iterator_cls,
 246                                           size_t size, unsigned int k);
 247
 248 /* ****************** metadata ******************* */
 249
 250 /**
 251  * Meta data to associate with a file, directory or namespace.
 252  */
 253 struct GNUNET_CONTAINER_MetaData;
 254
 255 /**
 256  * Create a fresh MetaData token.
 257  *
 258  * @return empty meta-data container
 259  */
 260 struct GNUNET_CONTAINER_MetaData *GNUNET_CONTAINER_meta_data_create (void);
 261
 262 /**
 263  * Duplicate a MetaData token.
 264  *
 265  * @param md what to duplicate
 266  * @return duplicate meta-data container
 267  */
 268 struct GNUNET_CONTAINER_MetaData *GNUNET_CONTAINER_meta_data_duplicate (const
 269                                                                         struct
 270                                                                         GNUNET_CONTAINER_MetaData
 271                                                                         *md);
 272
 273 /**
 274  * Free meta data.
 275  *
 276  * @param md what to free
 277  */
 278 void GNUNET_CONTAINER_meta_data_destroy (struct GNUNET_CONTAINER_MetaData *md);
 279
 280 /**
 281  * Test if two MDs are equal. We consider them equal if
 282  * the meta types, formats and content match (we do not
 283  * include the mime types and plugins names in this
 284  * consideration).
 285  *
 286  * @param md1 first value to check
 287  * @param md2 other value to check
 288  * @return GNUNET_YES if they are equal
 289  */
 290 int
 291 GNUNET_CONTAINER_meta_data_test_equal (const struct
 292                                        GNUNET_CONTAINER_MetaData *md1,
 293                                        const struct
 294                                        GNUNET_CONTAINER_MetaData *md2);
 295
 296
 297 /**
 298  * Extend metadata.
 299  *
 300  * @param md metadata to extend
 301  * @param plugin_name name of the plugin that produced this value;
 302  *        special values can be used (i.e. '&lt;zlib&gt;' for zlib being
 303  *        used in the main libextractor library and yielding
 304  *        meta data).
 305  * @param type libextractor-type describing the meta data
 306  * @param format basic format information about data
 307  * @param data_mime_type mime-type of data (not of the original file);
 308  *        can be NULL (if mime-type is not known)
 309  * @param data actual meta-data found
 310  * @param data_len number of bytes in data
 311  * @return GNUNET_OK on success, GNUNET_SYSERR if this entry already exists
 312  *         data_mime_type and plugin_name are not considered for "exists" checks
 313  */
 314 int
 315 GNUNET_CONTAINER_meta_data_insert (struct GNUNET_CONTAINER_MetaData *md,
 316                                    const char *plugin_name,
 317                                    enum EXTRACTOR_MetaType type,
 318                                    enum EXTRACTOR_MetaFormat format,
 319                                    const char *data_mime_type,
 320                                    const char *data, size_t data_len);
 321
 322
 323 /**
 324  * Extend metadata.  Merges the meta data from the second argument
 325  * into the first, discarding duplicate key-value pairs.
 326  *
 327  * @param md metadata to extend
 328  * @param in metadata to merge
 329  */
 330 void
 331 GNUNET_CONTAINER_meta_data_merge (struct GNUNET_CONTAINER_MetaData *md,
 332                                   const struct GNUNET_CONTAINER_MetaData *in);
 333
 334
 335 /**
 336  * Remove an item.
 337  *
 338  * @param md metadata to manipulate
 339  * @param type type of the item to remove
 340  * @param data specific value to remove, NULL to remove all
 341  *        entries of the given type
 342  * @param data_len number of bytes in data
 343  * @return GNUNET_OK on success, GNUNET_SYSERR if the item does not exist in md
 344  */
 345 int
 346 GNUNET_CONTAINER_meta_data_delete (struct GNUNET_CONTAINER_MetaData *md,
 347                                    enum EXTRACTOR_MetaType type,
 348                                    const char *data, size_t data_len);
 349
 350
 351 /**
 352  * Remove all items in the container.
 353  *
 354  * @param md metadata to manipulate
 355  */
 356 void GNUNET_CONTAINER_meta_data_clear (struct GNUNET_CONTAINER_MetaData *md);
 357
 358
 359 /**
 360  * Add the current time as the publication date
 361  * to the meta-data.
 362  *
 363  * @param md metadata to modify
 364  */
 365 void
 366 GNUNET_CONTAINER_meta_data_add_publication_date (struct
 367                                                  GNUNET_CONTAINER_MetaData *md);
 368
 369
 370 /**
 371  * Iterate over MD entries.
 372  *
 373  * @param md metadata to inspect
 374  * @param iter function to call on each entry
 375  * @param iter_cls closure for iterator
 376  * @return number of entries
 377  */
 378 int GNUNET_CONTAINER_meta_data_iterate (const struct
 379                                         GNUNET_CONTAINER_MetaData *md,
 380                                         EXTRACTOR_MetaDataProcessor
 381                                         iter, void *iter_cls);
 382
 383 /**
 384  * Get the first MD entry of the given type.  Caller
 385  * is responsible for freeing the return value.
 386  * Also, only meta data items that are strings (0-terminated)
 387  * are returned by this function.
 388  *
 389  * @param md metadata to inspect
 390  * @param type type to look for
 391  * @return NULL if no entry was found
 392  */
 393 char *GNUNET_CONTAINER_meta_data_get_by_type (const struct
 394                                               GNUNET_CONTAINER_MetaData *md,
 395                                               enum EXTRACTOR_MetaType type);
 396
 397
 398 /**
 399  * Get the first matching MD entry of the given types. Caller is
 400  * responsible for freeing the return value.  Also, only meta data
 401  * items that are strings (0-terminated) are returned by this
 402  * function.
 403  *
 404  * @param md metadata to inspect
 405  * @param ... -1-terminated list of types
 406  * @return NULL if we do not have any such entry,
 407  *  otherwise client is responsible for freeing the value!
 408  */
 409 char *GNUNET_CONTAINER_meta_data_get_first_by_types (const struct
 410                                                      GNUNET_CONTAINER_MetaData
 411                                                      *md, ...);
 412
 413 /**
 414  * Get a thumbnail from the meta-data (if present).  Only matches meta
 415  * data with mime type "image" and binary format.
 416  *
 417  * @param md metadata to inspect
 418  * @param thumb will be set to the thumbnail data.  Must be
 419  *        freed by the caller!
 420  * @return number of bytes in thumbnail, 0 if not available
 421  */
 422 size_t
 423 GNUNET_CONTAINER_meta_data_get_thumbnail (const struct
 424                                           GNUNET_CONTAINER_MetaData
 425                                           *md, unsigned char **thumb);
 426
 427
 428
 429 /**
 430  * Options for metadata serialization.
 431  */
 432 enum GNUNET_CONTAINER_MetaDataSerializationOptions
 433 {
 434   /**
 435    * Serialize all of the data.
 436    */
 437   GNUNET_CONTAINER_META_DATA_SERIALIZE_FULL = 0,
 438
 439   /**
 440    * If not enough space is available, it is acceptable
 441    * to only serialize some of the metadata.
 442    */
 443   GNUNET_CONTAINER_META_DATA_SERIALIZE_PART = 1,
 444
 445   /**
 446    * Speed is of the essence, do not allow compression.
 447    */
 448   GNUNET_CONTAINER_META_DATA_SERIALIZE_NO_COMPRESS = 2
 449 };
 450
 451
 452 /**
 453  * Serialize meta-data to target.
 454  *
 455  * @param md metadata to serialize
 456  * @param target where to write the serialized metadata;
 457  *         *target can be NULL, in which case memory is allocated
 458  * @param max maximum number of bytes available
 459  * @param opt is it ok to just write SOME of the
 460  *        meta-data to match the size constraint,
 461  *        possibly discarding some data?
 462  * @return number of bytes written on success,
 463  *         -1 on error (typically: not enough
 464  *         space)
 465  */
 466 ssize_t
 467
 468
 469
 470
 471
 472
 473
 474
 475
 476
 477
 478
 479
 480
 481
 482
 483
 484
 485
 486 GNUNET_CONTAINER_meta_data_serialize (const struct
 487                                       GNUNET_CONTAINER_MetaData *md,
 488                                       char **target,
 489                                       size_t max,
 490                                       enum
 491                                       GNUNET_CONTAINER_MetaDataSerializationOptions
 492                                       opt);
 493
 494
 495 /**
 496  * Get the size of the full meta-data in serialized form.
 497  *
 498  * @param md metadata to inspect
 499  * @return number of bytes needed for serialization, -1 on error
 500  */
 501 ssize_t
 502
 503
 504
 505
 506
 507
 508
 509
 510
 511
 512
 513
 514
 515
 516
 517
 518
 519
 520
 521 GNUNET_CONTAINER_meta_data_get_serialized_size (const struct
 522                                                 GNUNET_CONTAINER_MetaData *md);
 523
 524
 525 /**
 526  * Deserialize meta-data.  Initializes md.
 527  *
 528  * @param input serialized meta-data.
 529  * @param size number of bytes available
 530  * @return MD on success, NULL on error (i.e.
 531  *         bad format)
 532  */
 533 struct GNUNET_CONTAINER_MetaData *GNUNET_CONTAINER_meta_data_deserialize (const
 534                                                                           char
 535                                                                           *input,
 536                                                                           size_t
 537                                                                           size);
 538
 539
 540 /* ******************************* HashMap **************************** */
 541
 542 /**
 543  * Opaque handle for a HashMap.
 544  */
 545 struct GNUNET_CONTAINER_MultiHashMap;
 546
 547 /**
 548  * Options for storing values in the HashMap.
 549  */
 550 enum GNUNET_CONTAINER_MultiHashMapOption
 551 {
 552
 553   /**
 554    * If a value with the given key exists, replace it.  Note that the
 555    * old value would NOT be freed by replace (the application has to
 556    * make sure that this happens if required).
 557    */
 558   GNUNET_CONTAINER_MULTIHASHMAPOPTION_REPLACE,
 559
 560   /**
 561    * Allow multiple values with the same key.
 562    */
 563   GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE,
 564
 565   /**
 566    * There must only be one value per key; storing a value should fail
 567    * if a value under the same key already exists.
 568    */
 569   GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY,
 570
 571   /**
 572    * There must only be one value per key, but don't bother checking
 573    * if a value already exists (faster than UNIQUE_ONLY; implemented
 574    * just like MULTIPLE but this option documents better what is
 575    * intended if UNIQUE is what is desired).
 576    */
 577   GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST
 578 };
 579
 580
 581 /**
 582  * Iterator over hash map entries.
 583  *
 584  * @param cls closure
 585  * @param key current key code
 586  * @param value value in the hash map
 587  * @return GNUNET_YES if we should continue to
 588  *         iterate,
 589  *         GNUNET_NO if not.
 590  */
 591 typedef int (*GNUNET_CONTAINER_HashMapIterator) (void *cls,
 592                                                  const GNUNET_HashCode * key,
 593                                                  void *value);
 594
 595
 596 /**
 597  * Create a multi hash map.
 598  *
 599  * @param len initial size (map will grow as needed)
 600  * @return NULL on error
 601  */
 602 struct GNUNET_CONTAINER_MultiHashMap
 603     *GNUNET_CONTAINER_multihashmap_create (unsigned int len);
 604
 605
 606 /**
 607  * Destroy a hash map.  Will not free any values
 608  * stored in the hash map!
 609  *
 610  * @param map the map
 611  */
 612 void GNUNET_CONTAINER_multihashmap_destroy (struct
 613                                             GNUNET_CONTAINER_MultiHashMap *map);
 614
 615
 616 /**
 617  * Given a key find a value in the map matching the key.
 618  *
 619  * @param map the map
 620  * @param key what to look for
 621  * @return NULL if no value was found; note that
 622  *   this is indistinguishable from values that just
 623  *   happen to be NULL; use "contains" to test for
 624  *   key-value pairs with value NULL
 625  */
 626 void *GNUNET_CONTAINER_multihashmap_get (const struct
 627                                          GNUNET_CONTAINER_MultiHashMap *map,
 628                                          const GNUNET_HashCode * key);
 629
 630
 631 /**
 632  * Remove the given key-value pair from the map.  Note that if the
 633  * key-value pair is in the map multiple times, only one of the pairs
 634  * will be removed.
 635  *
 636  * @param map the map
 637  * @param key key of the key-value pair
 638  * @param value value of the key-value pair
 639  * @return GNUNET_YES on success, GNUNET_NO if the key-value pair
 640  *  is not in the map
 641  */
 642 int GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap
 643                                           *map, const GNUNET_HashCode * key,
 644                                           void *value);
 645
 646 /**
 647  * Remove all entries for the given key from the map.
 648  * Note that the values would not be "freed".
 649  *
 650  * @param map the map
 651  * @param key identifies values to be removed
 652  * @return number of values removed
 653  */
 654 int GNUNET_CONTAINER_multihashmap_remove_all (struct
 655                                               GNUNET_CONTAINER_MultiHashMap
 656                                               *map,
 657                                               const GNUNET_HashCode * key);
 658
 659
 660 /**
 661  * Check if the map contains any value under the given
 662  * key (including values that are NULL).
 663  *
 664  * @param map the map
 665  * @param key the key to test if a value exists for it
 666  * @return GNUNET_YES if such a value exists,
 667  *         GNUNET_NO if not
 668  */
 669 int GNUNET_CONTAINER_multihashmap_contains (const struct
 670                                             GNUNET_CONTAINER_MultiHashMap
 671                                             *map, const GNUNET_HashCode * key);
 672
 673
 674 /**
 675  * Check if the map contains the given value under the given
 676  * key.
 677  *
 678  * @param map the map
 679  * @param key the key to test if a value exists for it
 680  * @param value value to test for
 681  * @return GNUNET_YES if such a value exists,
 682  *         GNUNET_NO if not
 683  */
 684 int GNUNET_CONTAINER_multihashmap_contains_value (const struct
 685                                                   GNUNET_CONTAINER_MultiHashMap
 686                                                   *map,
 687                                                   const GNUNET_HashCode * key,
 688                                                   const void *value);
 689
 690
 691 /**
 692  * Store a key-value pair in the map.
 693  *
 694  * @param map the map
 695  * @param key key to use
 696  * @param value value to use
 697  * @param opt options for put
 698  * @return GNUNET_OK on success,
 699  *         GNUNET_NO if a value was replaced (with REPLACE)
 700  *         GNUNET_SYSERR if UNIQUE_ONLY was the option and the
 701  *                       value already exists
 702  */
 703 int GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap
 704                                        *map, const GNUNET_HashCode * key,
 705                                        void *value,
 706                                        enum
 707                                        GNUNET_CONTAINER_MultiHashMapOption opt);
 708
 709 /**
 710  * Get the number of key-value pairs in the map.
 711  *
 712  * @param map the map
 713  * @return the number of key value pairs
 714  */
 715 unsigned int GNUNET_CONTAINER_multihashmap_size (const struct
 716                                                  GNUNET_CONTAINER_MultiHashMap
 717                                                  *map);
 718
 719
 720 /**
 721  * Iterate over all entries in the map.
 722  *
 723  * @param map the map
 724  * @param it function to call on each entry
 725  * @param it_cls extra argument to it
 726  * @return the number of key value pairs processed,
 727  *         GNUNET_SYSERR if it aborted iteration
 728  */
 729 int GNUNET_CONTAINER_multihashmap_iterate (const struct
 730                                            GNUNET_CONTAINER_MultiHashMap *map,
 731                                            GNUNET_CONTAINER_HashMapIterator
 732                                            it, void *it_cls);
 733
 734
 735 /**
 736  * Iterate over all entries in the map that match a particular key.
 737  *
 738  * @param map the map
 739  * @param key key that the entries must correspond to
 740  * @param it function to call on each entry
 741  * @param it_cls extra argument to it
 742  * @return the number of key value pairs processed,
 743  *         GNUNET_SYSERR if it aborted iteration
 744  */
 745 int GNUNET_CONTAINER_multihashmap_get_multiple (const struct
 746                                                 GNUNET_CONTAINER_MultiHashMap
 747                                                 *map,
 748                                                 const GNUNET_HashCode * key,
 749                                                 GNUNET_CONTAINER_HashMapIterator
 750                                                 it, void *it_cls);
 751
 752
 753 /* ******************** doubly-linked list *************** */
 754 /* To avoid mistakes: head->prev == tail->next == NULL     */
 755
 756 /**
 757  * Insert an element at the head of a DLL. Assumes that head, tail and
 758  * element are structs with prev and next fields.
 759  *
 760  * @param head pointer to the head of the DLL
 761  * @param tail pointer to the tail of the DLL
 762  * @param element element to insert
 763  */
 764 #define GNUNET_CONTAINER_DLL_insert(head,tail,element) do { \
 765   GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
 766   GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
 767   (element)->next = (head); \
 768   (element)->prev = NULL; \
 769   if ((tail) == NULL) \
 770     (tail) = element; \
 771   else \
 772     (head)->prev = element; \
 773   (head) = (element); } while (0)
 774
 775
 776 /**
 777  * Insert an element at the tail of a DLL. Assumes that head, tail and
 778  * element are structs with prev and next fields.
 779  *
 780  * @param head pointer to the head of the DLL
 781  * @param tail pointer to the tail of the DLL
 782  * @param element element to insert
 783  */
 784 #define GNUNET_CONTAINER_DLL_insert_tail(head,tail,element) do { \
 785   GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
 786   GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
 787   (element)->prev = (tail); \
 788   (element)->next = NULL; \
 789   if ((head) == NULL) \
 790     (head) = element; \
 791   else \
 792     (tail)->next = element; \
 793   (tail) = (element); } while (0)
 794
 795
 796 /**
 797  * Insert an element into a DLL after the given other element.  Insert
 798  * at the head if the other element is NULL.
 799  *
 800  * @param head pointer to the head of the DLL
 801  * @param tail pointer to the tail of the DLL
 802  * @param other prior element, NULL for insertion at head of DLL
 803  * @param element element to insert
 804  */
 805 #define GNUNET_CONTAINER_DLL_insert_after(head,tail,other,element) do { \
 806   GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
 807   GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
 808   (element)->prev = (other); \
 809   if (NULL == other) \
 810     { \
 811       (element)->next = (head); \
 812       (head) = (element); \
 813     } \
 814   else \
 815     { \
 816       (element)->next = (other)->next; \
 817       (other)->next = (element); \
 818     } \
 819   if (NULL == (element)->next) \
 820     (tail) = (element); \
 821   else \
 822     (element)->next->prev = (element); } while (0)
 823
 824
 825 /**
 826  * Insert an element into a DLL before the given other element.  Insert
 827  * at the tail if the other element is NULL.
 828  *
 829  * @param head pointer to the head of the DLL
 830  * @param tail pointer to the tail of the DLL
 831  * @param other prior element, NULL for insertion at head of DLL
 832  * @param element element to insert
 833  */
 834 #define GNUNET_CONTAINER_DLL_insert_before(head,tail,other,element) do { \
 835   GNUNET_assert ( ( (element)->prev == NULL) && ((head) != (element))); \
 836   GNUNET_assert ( ( (element)->next == NULL) && ((tail) != (element))); \
 837   (element)->next = (other); \
 838   if (NULL == other) \
 839     { \
 840       (element)->prev = (tail); \
 841       (tail) = (element); \
 842     } \
 843   else \
 844     { \
 845       (element)->prev = (other)->prev; \
 846       (other)->prev = (element); \
 847     } \
 848   if (NULL == (element)->prev) \
 849     (head) = (element); \
 850   else \
 851     (element)->prev->next = (element); } while (0)
 852
 853
 854 /**
 855  * Remove an element from a DLL. Assumes
 856  * that head, tail and element are structs
 857  * with prev and next fields.
 858  *
 859  * @param head pointer to the head of the DLL
 860  * @param tail pointer to the tail of the DLL
 861  * @param element element to remove
 862  */
 863 #define GNUNET_CONTAINER_DLL_remove(head,tail,element) do { \
 864   GNUNET_assert ( ( (element)->prev != NULL) || ((head) == (element))); \
 865   GNUNET_assert ( ( (element)->next != NULL) || ((tail) == (element))); \
 866   if ((element)->prev == NULL) \
 867     (head) = (element)->next;  \
 868   else \
 869     (element)->prev->next = (element)->next; \
 870   if ((element)->next == NULL) \
 871     (tail) = (element)->prev;  \
 872   else \
 873     (element)->next->prev = (element)->prev; \
 874   (element)->next = NULL; \
 875   (element)->prev = NULL; } while (0)
 876
 877
 878
 879 /* ******************** Heap *************** */
 880
 881
 882 /**
 883  * Cost by which elements in a heap can be ordered.
 884  */
 885 typedef uint64_t GNUNET_CONTAINER_HeapCostType;
 886
 887
 888 /*
 889  * Heap type, either max or min.  Hopefully makes the
 890  * implementation more useful.
 891  */
 892 enum GNUNET_CONTAINER_HeapOrder
 893 {
 894   /**
 895    * Heap with the maximum cost at the root.
 896    */
 897   GNUNET_CONTAINER_HEAP_ORDER_MAX,
 898
 899   /**
 900    * Heap with the minimum cost at the root.
 901    */
 902   GNUNET_CONTAINER_HEAP_ORDER_MIN
 903 };
 904
 905
 906 /**
 907  * Handle to a Heap.
 908  */
 909 struct GNUNET_CONTAINER_Heap;
 910
 911
 912
 913 /**
 914  * Handle to a node in a heap.
 915  */
 916 struct GNUNET_CONTAINER_HeapNode;
 917
 918
 919 /**
 920  * Create a new heap.
 921  *
 922  * @param order how should the heap be sorted?
 923  * @return handle to the heap
 924  */
 925 struct GNUNET_CONTAINER_Heap *GNUNET_CONTAINER_heap_create (enum
 926                                                             GNUNET_CONTAINER_HeapOrder
 927                                                             order);
 928
 929
 930 /**
 931  * Destroys the heap.  Only call on a heap that
 932  * is already empty.
 933  *
 934  * @param heap heap to destroy
 935  */
 936 void GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap);
 937
 938
 939 /**
 940  * Get element stored at root of heap.
 941  *
 942  * @param heap heap to inspect
 943  * @return NULL if heap is empty
 944  */
 945 void *GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap);
 946
 947
 948 /**
 949  * Get the current size of the heap
 950  *
 951  * @param heap the heap to get the size of
 952  * @return number of elements stored
 953  */
 954 unsigned int
 955 GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap);
 956
 957
 958 /**
 959  * Get the current cost of the node
 960  *
 961  * @param node the node to get the cost of
 962  * @return cost of the node
 963  */
 964 GNUNET_CONTAINER_HeapCostType
 965 GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode
 966                                      *node);
 967
 968 /**
 969  * Iterator for heap
 970  *
 971  * @param cls closure
 972  * @param node internal node of the heap
 973  * @param element value stored at the node
 974  * @param cost cost associated with the node
 975  * @return GNUNET_YES if we should continue to iterate,
 976  *         GNUNET_NO if not.
 977  */
 978 typedef int (*GNUNET_CONTAINER_HeapIterator) (void *cls,
 979                                               struct GNUNET_CONTAINER_HeapNode *
 980                                               node, void *element,
 981                                               GNUNET_CONTAINER_HeapCostType
 982                                               cost);
 983
 984
 985 /**
 986  * Iterate over all entries in the heap.
 987  *
 988  * @param heap the heap
 989  * @param iterator function to call on each entry
 990  * @param iterator_cls closure for iterator
 991  */
 992 void
 993 GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
 994                                GNUNET_CONTAINER_HeapIterator iterator,
 995                                void *iterator_cls);
 996
 997
 998 /**
 999  * Return a *uniform* random element from the heap.  Choose a random
1000  * number between 0 and heap size and then walk directly to it.
1001  * This cost can be between 0 and n, amortized cost of logN.
1002  *
1003  * @param heap heap to choose random element from
1004  * @param max how many nodes from the heap to choose from
1005  *
1006  * @return data stored at the chosen random node,
1007  *         NULL if the heap is empty.
1008  *
1009  */
1010 void *GNUNET_CONTAINER_heap_get_random (struct GNUNET_CONTAINER_Heap *heap,
1011                                         uint32_t max);
1012
1013
1014 /**
1015  * Perform a random walk of the tree.  The walk is biased
1016  * towards elements closer to the root of the tree (since
1017  * each walk starts at the root and ends at a random leaf).
1018  * The heap internally tracks the current position of the
1019  * walk.
1020  *
1021  * @param heap heap to walk
1022  * @return data stored at the next random node in the walk;
1023  *         NULL if the tree is empty.
1024  */
1025 void *GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap);
1026
1027
1028 /**
1029  * Inserts a new element into the heap.
1030  *
1031  * @param heap heap to modify
1032  * @param element element to insert
1033  * @param cost cost for the element
1034  * @return node for the new element
1035  */
1036 struct GNUNET_CONTAINER_HeapNode *GNUNET_CONTAINER_heap_insert (struct
1037                                                                 GNUNET_CONTAINER_Heap
1038                                                                 *heap,
1039                                                                 void *element,
1040                                                                 GNUNET_CONTAINER_HeapCostType
1041                                                                 cost);
1042
1043
1044 /**
1045  * Remove root of the heap.
1046  *
1047  * @param heap heap to modify
1048  * @return element data stored at the root node
1049  */
1050 void *GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap);
1051
1052
1053 /**
1054  * Removes a node from the heap.
1055  *
1056  * @param node node to remove
1057  * @return element data stored at the node, NULL if heap is empty
1058  */
1059 void *GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode
1060                                          *node);
1061
1062
1063 /**
1064  * Updates the cost of any node in the tree
1065  *
1066  * @param heap heap to modify
1067  * @param node node for which the cost is to be changed
1068  * @param new_cost new cost for the node
1069  */
1070 void
1071 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
1072                                    struct GNUNET_CONTAINER_HeapNode *node,
1073                                    GNUNET_CONTAINER_HeapCostType new_cost);
1074
1075
1076 /* ******************** Singly linked list *************** */
1077
1078 /**
1079  * Possible ways for how data stored in the linked list
1080  * might be allocated.
1081  */
1082 enum GNUNET_CONTAINER_SListDisposition
1083 {
1084     /**
1085      * Single-linked list must copy the buffer.
1086      */
1087   GNUNET_CONTAINER_SLIST_DISPOSITION_TRANSIENT = 0,
1088
1089     /**
1090      * Data is static, no need to copy or free.
1091      */
1092   GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC = 2,
1093
1094     /**
1095      * Data is dynamic, do not copy but free when done.
1096      */
1097   GNUNET_CONTAINER_SLIST_DISPOSITION_DYNAMIC = 4
1098 };
1099
1100
1101
1102 /**
1103  * Handle to a singly linked list
1104  */
1105 struct GNUNET_CONTAINER_SList;
1106
1107 /**
1108  * Handle to a singly linked list iterator
1109  */
1110 struct GNUNET_CONTAINER_SList_Iterator;
1111
1112
1113 /**
1114  * Add a new element to the list
1115  * @param l list
1116  * @param disp memory disposition
1117  * @param buf payload buffer
1118  * @param len length of the buffer
1119  */
1120 void GNUNET_CONTAINER_slist_add (struct GNUNET_CONTAINER_SList *l,
1121                                  enum GNUNET_CONTAINER_SListDisposition disp,
1122                                  const void *buf, size_t len);
1123
1124
1125 /**
1126  * Add a new element to the end of the list
1127  * @param l list
1128  * @param disp memory disposition
1129  * @param buf payload buffer
1130  * @param len length of the buffer
1131  */
1132 void GNUNET_CONTAINER_slist_add_end (struct GNUNET_CONTAINER_SList *l,
1133                                      enum GNUNET_CONTAINER_SListDisposition
1134                                      disp, const void *buf, size_t len);
1135
1136
1137 /**
1138  * Append a singly linked list to another
1139  * @param dst list to append to
1140  * @param src source
1141  */
1142 void
1143 GNUNET_CONTAINER_slist_append (struct GNUNET_CONTAINER_SList *dst,
1144                                struct GNUNET_CONTAINER_SList *src);
1145
1146
1147 /**
1148  * Create a new singly linked list
1149  * @return the new list
1150  */
1151 struct GNUNET_CONTAINER_SList *GNUNET_CONTAINER_slist_create (void);
1152
1153
1154 /**
1155  * Destroy a singly linked list
1156  * @param l the list to be destroyed
1157  */
1158 void GNUNET_CONTAINER_slist_destroy (struct GNUNET_CONTAINER_SList *l);
1159
1160
1161 /**
1162  * Return the beginning of a list
1163  *
1164  * @param l list
1165  * @return iterator pointing to the beginning, free using "GNUNET_free"
1166  */
1167 struct GNUNET_CONTAINER_SList_Iterator *GNUNET_CONTAINER_slist_begin (struct
1168                                                                       GNUNET_CONTAINER_SList
1169                                                                       *l);
1170
1171
1172 /**
1173  * Clear a list
1174  *
1175  * @param l list
1176  */
1177 void GNUNET_CONTAINER_slist_clear (struct GNUNET_CONTAINER_SList *l);
1178
1179
1180 /**
1181  * Check if a list contains a certain element
1182  * @param l list
1183  * @param buf payload buffer to find
1184  * @param len length of the payload (number of bytes in buf)
1185  */
1186 int GNUNET_CONTAINER_slist_contains (const struct GNUNET_CONTAINER_SList *l,
1187                                      const void *buf, size_t len);
1188
1189
1190 /**
1191  * Count the elements of a list
1192  * @param l list
1193  * @return number of elements in the list
1194  */
1195 int GNUNET_CONTAINER_slist_count (const struct GNUNET_CONTAINER_SList *l);
1196
1197
1198 /**
1199  * Remove an element from the list
1200  * @param i iterator that points to the element to be removed
1201  */
1202 void GNUNET_CONTAINER_slist_erase (struct GNUNET_CONTAINER_SList_Iterator *i);
1203
1204
1205 /**
1206  * Insert an element into a list at a specific position
1207  * @param before where to insert the new element
1208  * @param disp memory disposition
1209  * @param buf payload buffer
1210  * @param len length of the payload
1211  */
1212 void GNUNET_CONTAINER_slist_insert (struct GNUNET_CONTAINER_SList_Iterator
1213                                     *before,
1214                                     enum GNUNET_CONTAINER_SListDisposition disp,
1215                                     const void *buf, size_t len);
1216
1217
1218 /**
1219  * Advance an iterator to the next element
1220  * @param i iterator
1221  * @return GNUNET_YES on success, GNUNET_NO if the end has been reached
1222  */
1223 int GNUNET_CONTAINER_slist_next (struct GNUNET_CONTAINER_SList_Iterator *i);
1224
1225
1226 /**
1227  * Check if an iterator points beyond the end of a list
1228  * @param i iterator
1229  * @return GNUNET_YES if the end has been reached, GNUNET_NO if the iterator
1230  *         points to a valid element
1231  */
1232 int GNUNET_CONTAINER_slist_end (struct GNUNET_CONTAINER_SList_Iterator *i);
1233
1234
1235 /**
1236  * Retrieve the element at a specific position in a list
1237  *
1238  * @param i iterator
1239  * @param len set to the payload length
1240  * @return payload
1241  */
1242 void *GNUNET_CONTAINER_slist_get (const struct GNUNET_CONTAINER_SList_Iterator
1243                                   *i, size_t * len);
1244
1245
1246 /**
1247  * Release an iterator
1248  * @param i iterator
1249  */
1250 void GNUNET_CONTAINER_slist_iter_destroy (struct GNUNET_CONTAINER_SList_Iterator
1251                                           *i);
1252
1253
1254 #if 0                           /* keep Emacsens' auto-indent happy */
1255 {
1256 #endif
1257 #ifdef __cplusplus
1258 }
1259 #endif
1260
1261
1262 /* ifndef GNUNET_CONTAINER_LIB_H */
1263 #endif
1264 /* end of gnunet_container_lib.h */