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