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