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