src/include/gnunet_container_lib.h

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2001, 2002, 2003, 2004, 2005, 2006, 2008, 2009 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 #ifdef __cplusplus
  37 extern "C"
  38 {
  39 #if 0                           /* keep Emacsens' auto-indent happy */
  40 }
  41 #endif
  42 #endif
  43
  44
  45 #define GNUNET_MEM_DISP_TRANSIENT    0
  46 #define GNUNET_MEM_DISP_STATIC       2
  47 #define GNUNET_MEM_DISP_DYNAMIC      4
  48
  49 /* ******************* bloomfilter ***************** */
  50
  51 /**
  52  * @brief bloomfilter representation (opaque)
  53  */
  54 struct GNUNET_CONTAINER_BloomFilter;
  55
  56 /**
  57  * Iterator over HashCodes.
  58  *
  59  * @param cls closure
  60  * @param next set to the next hash code
  61  * @return GNUNET_YES if next was updated
  62  *         GNUNET_NO if there are no more entries
  63  */
  64 typedef int (*GNUNET_HashCodeIterator) (void *cls,
  65                                         GNUNET_HashCode * next);
  66
  67 /**
  68  * Load a bloom-filter from a file.
  69  *
  70  * @param filename the name of the file (or the prefix)
  71  * @param size the size of the bloom-filter (number of
  72  *        bytes of storage space to use)
  73  * @param k the number of GNUNET_CRYPTO_hash-functions to apply per
  74  *        element (number of bits set per element in the set)
  75  * @return the bloomfilter
  76  */
  77 struct GNUNET_CONTAINER_BloomFilter *
  78 GNUNET_CONTAINER_bloomfilter_load (const
  79                                    char
  80                                    *filename,
  81                                    size_t
  82                                    size,
  83                                    unsigned
  84                                    int
  85                                    k);
  86
  87 /**
  88  * Create a bloom filter from raw bits.
  89  *
  90  * @param data the raw bits in memory (maybe NULL,
  91  *        in which case all bits should be considered
  92  *        to be zero).
  93  * @param size the size of the bloom-filter (number of
  94  *        bytes of storage space to use); also size of data
  95  *        -- unless data is NULL.  Must be a power of 2.
  96  * @param k the number of GNUNET_CRYPTO_hash-functions to apply per
  97  *        element (number of bits set per element in the set)
  98  * @return the bloomfilter
  99  */
 100 struct GNUNET_CONTAINER_BloomFilter *
 101 GNUNET_CONTAINER_bloomfilter_init (const
 102                                    char
 103                                    *data,
 104                                    size_t
 105                                    size,
 106                                    unsigned
 107                                    int
 108                                    k);
 109
 110 /**
 111  * Copy the raw data of this bloomfilter into
 112  * the given data array.
 113  *
 114  * @param data where to write the data
 115  * @param size the size of the given data array
 116  * @return GNUNET_SYSERR if the data array of the wrong size
 117  */
 118 int GNUNET_CONTAINER_bloomfilter_get_raw_data (struct
 119                                                GNUNET_CONTAINER_BloomFilter
 120                                                *bf, char *data,
 121                                                size_t size);
 122
 123 /**
 124  * Test if an element is in the filter.
 125  * @param e the element
 126  * @param bf the filter
 127  * @return GNUNET_YES if the element is in the filter, GNUNET_NO if not
 128  */
 129 int GNUNET_CONTAINER_bloomfilter_test (struct GNUNET_CONTAINER_BloomFilter
 130                                        *bf, const GNUNET_HashCode * e);
 131
 132 /**
 133  * Add an element to the filter
 134  * @param bf the filter
 135  * @param e the element
 136  */
 137 void GNUNET_CONTAINER_bloomfilter_add (struct GNUNET_CONTAINER_BloomFilter
 138                                        *bf, const GNUNET_HashCode * e);
 139
 140 /**
 141  * Remove an element from the filter.
 142  * @param bf the filter
 143  * @param e the element to remove
 144  */
 145 void GNUNET_CONTAINER_bloomfilter_remove (struct GNUNET_CONTAINER_BloomFilter
 146                                           *bf, const GNUNET_HashCode * e);
 147
 148 /**
 149  * Free the space associcated with a filter
 150  * in memory, flush to drive if needed (do not
 151  * free the space on the drive)
 152  * @param bf the filter
 153  */
 154 void GNUNET_CONTAINER_bloomfilter_free (struct GNUNET_CONTAINER_BloomFilter
 155                                         *bf);
 156
 157 /**
 158  * Reset a bloom filter to empty.
 159  * @param bf the filter
 160  */
 161 void GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter
 162                                          *bf);
 163
 164 /**
 165  * Or the entries of the given raw data array with the
 166  * data of the given bloom filter.  Assumes that
 167  * the size of the data array and the current filter
 168  * match.
 169  *
 170  * @param bf the filter
 171  * @param data data to OR-in
 172  * @param size size of data
 173  * @return GNUNET_OK on success
 174  */
 175 int GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf,
 176                                      const char *data, size_t size);
 177
 178 /**
 179  * Resize a bloom filter.  Note that this operation
 180  * is pretty costly.  Essentially, the bloom filter
 181  * needs to be completely re-build.
 182  *
 183  * @param bf the filter
 184  * @param iterator an iterator over all elements stored in the BF
 185  * @param iterator_cls closure for iterator
 186  * @param size the new size for the filter
 187  * @param k the new number of GNUNET_CRYPTO_hash-function to apply per element
 188  */
 189 void GNUNET_CONTAINER_bloomfilter_resize (struct GNUNET_CONTAINER_BloomFilter
 190                                           *bf,
 191                                           GNUNET_HashCodeIterator iterator,
 192                                           void *iterator_cls,
 193                                           size_t size, unsigned int k);
 194
 195 /* ****************** metadata ******************* */
 196
 197 /**
 198  * Meta data to associate with a file, directory or namespace.
 199  */
 200 struct GNUNET_CONTAINER_MetaData;
 201
 202 /**
 203  * Iterator over meta data.
 204  *
 205  * @param cls closure
 206  * @param type type of the meta data
 207  * @param data value of the meta data
 208  * @return GNUNET_OK to continue to iterate, GNUNET_SYSERR to abort
 209  */
 210 typedef int (*GNUNET_CONTAINER_MetaDataProcessor) (void *cls,
 211                                                    EXTRACTOR_KeywordType type,
 212                                                    const char *data);
 213
 214 /**
 215  * Create a fresh MetaData token.
 216  *
 217  * @return empty meta-data container
 218  */
 219 struct GNUNET_CONTAINER_MetaData *GNUNET_CONTAINER_meta_data_create (void);
 220
 221 /**
 222  * Duplicate a MetaData token.
 223  *
 224  * @param meta what to duplicate
 225  * @return duplicate meta-data container
 226  */
 227 struct GNUNET_CONTAINER_MetaData *GNUNET_CONTAINER_meta_data_duplicate (const
 228                                                                         struct
 229                                                                         GNUNET_CONTAINER_MetaData
 230                                                                         *meta);
 231
 232 /**
 233  * Free meta data.
 234  *
 235  * @param md what to free
 236  */
 237 void GNUNET_CONTAINER_meta_data_destroy (struct GNUNET_CONTAINER_MetaData
 238                                          *md);
 239
 240 /**
 241  * Test if two MDs are equal.
 242  *
 243  * @param md1 first value to check
 244  * @param md2 other value to check
 245  * @return GNUNET_YES if they are equal
 246  */
 247 int GNUNET_CONTAINER_meta_data_test_equal (const struct
 248                                            GNUNET_CONTAINER_MetaData *md1,
 249                                            const struct
 250                                            GNUNET_CONTAINER_MetaData *md2);
 251
 252
 253 /**
 254  * Extend metadata.
 255  *
 256  * @param md metadata to extend
 257  * @param type type of the new entry
 258  * @param data value for the entry
 259  * @return GNUNET_OK on success, GNUNET_SYSERR if this entry already exists
 260  */
 261 int GNUNET_CONTAINER_meta_data_insert (struct GNUNET_CONTAINER_MetaData *md,
 262                                        EXTRACTOR_KeywordType type,
 263                                        const char *data);
 264
 265 /**
 266  * Remove an item.
 267  *
 268  * @param type type of the item to remove
 269  * @param data specific value to remove, NULL to remove all
 270  *        entries of the given type
 271  * @return GNUNET_OK on success, GNUNET_SYSERR if the item does not exist in md
 272  */
 273 int GNUNET_CONTAINER_meta_data_delete (struct GNUNET_CONTAINER_MetaData *md,
 274                                        EXTRACTOR_KeywordType type,
 275                                        const char *data);
 276
 277 /**
 278  * Add the current time as the publication date
 279  * to the meta-data.
 280  *
 281  * @param md metadata to modify
 282  */
 283 void GNUNET_CONTAINER_meta_data_add_publication_date (struct
 284                                                       GNUNET_CONTAINER_MetaData
 285                                                       *md);
 286
 287 /**
 288  * Iterate over MD entries, excluding thumbnails.
 289  *
 290  * @param md metadata to inspect
 291  * @param iter function to call on each entry
 292  * @param iter_cls closure for iterator
 293  * @return number of entries
 294  */
 295 int GNUNET_CONTAINER_meta_data_get_contents (const struct
 296                                              GNUNET_CONTAINER_MetaData *md,
 297                                              GNUNET_CONTAINER_MetaDataProcessor
 298                                              iter, void *iter_cls);
 299
 300 /**
 301  * Get the first MD entry of the given type.
 302  *
 303  * @param md metadata to inspect
 304  * @param type type to look for
 305  * @return NULL if we do not have any such entry,
 306  *  otherwise client is responsible for freeing the value!
 307  */
 308 char *GNUNET_CONTAINER_meta_data_get_by_type (const struct
 309                                              GNUNET_CONTAINER_MetaData *md,
 310                                               EXTRACTOR_KeywordType type);
 311
 312 /**
 313  * Get the first matching MD entry of the given types.
 314  *
 315  * @param md metadata to inspect
 316  * @param ... -1-terminated list of types
 317  * @return NULL if we do not have any such entry,
 318  *  otherwise client is responsible for freeing the value!
 319  */
 320 char *GNUNET_CONTAINER_meta_data_get_first_by_types (const struct
 321                                                      GNUNET_CONTAINER_MetaData
 322                                                      *md, ...);
 323
 324 /**
 325  * Get a thumbnail from the meta-data (if present).
 326  *
 327  * @param md metadata to inspect
 328  * @param thumb will be set to the thumbnail data.  Must be
 329  *        freed by the caller!
 330  * @return number of bytes in thumbnail, 0 if not available
 331  */
 332 size_t GNUNET_CONTAINER_meta_data_get_thumbnail (const struct
 333                                                  GNUNET_CONTAINER_MetaData
 334                                                  *md, unsigned char **thumb);
 335
 336 /**
 337  * Extract meta-data from a file.
 338  *
 339  * @param md metadata to set
 340  * @param filename name of file to inspect
 341  * @param extractors plugins to use
 342  * @return GNUNET_SYSERR on error, otherwise the number
 343  *   of meta-data items obtained
 344  */
 345 int GNUNET_CONTAINER_meta_data_extract_from_file (struct
 346                                                   GNUNET_CONTAINER_MetaData
 347                                                   *md, const char *filename,
 348                                                   EXTRACTOR_ExtractorList *
 349                                                   extractors);
 350
 351
 352 /**
 353  * Options for metadata serialization.
 354  */
 355 enum GNUNET_CONTAINER_MetaDataSerializationOptions
 356 {
 357   /**
 358    * Serialize all of the data.
 359    */
 360   GNUNET_CONTAINER_META_DATA_SERIALIZE_FULL = 0,
 361
 362   /**
 363    * If not enough space is available, it is acceptable
 364    * to only serialize some of the metadata.
 365    */
 366   GNUNET_CONTAINER_META_DATA_SERIALIZE_PART = 1,
 367
 368   /**
 369    * Speed is of the essence, do not allow compression.
 370    */
 371   GNUNET_CONTAINER_META_DATA_SERIALIZE_NO_COMPRESS = 2
 372 };
 373
 374
 375 /**
 376  * Serialize meta-data to target.
 377  *
 378  * @param md metadata to serialize
 379  * @param size maximum number of bytes available
 380  * @param opt is it ok to just write SOME of the
 381  *        meta-data to match the size constraint,
 382  *        possibly discarding some data?
 383  * @return number of bytes written on success,
 384  *         -1 on error (typically: not enough
 385  *         space)
 386  */
 387 ssize_t GNUNET_CONTAINER_meta_data_serialize (const struct
 388                                               GNUNET_CONTAINER_MetaData *md,
 389                                               char *target,
 390                                               size_t size,
 391                                               enum
 392                                           GNUNET_CONTAINER_MetaDataSerializationOptions
 393                                           opt);
 394
 395 /**
 396  * Compute size of the meta-data in
 397  * serialized form.
 398  *
 399  * @param md metadata to inspect
 400  * @param opt is it ok to just write SOME of the
 401  *        meta-data to match the size constraint,
 402  *        possibly discarding some data?
 403  * @return number of bytes needed for serialization, -1 on error
 404  */
 405 ssize_t GNUNET_CONTAINER_meta_data_get_serialized_size (const struct
 406                                                         GNUNET_CONTAINER_MetaData
 407                                                         *md,
 408                                                         enum
 409                                                         GNUNET_CONTAINER_MetaDataSerializationOptions
 410                                                         opt);
 411
 412 /**
 413  * Deserialize meta-data.  Initializes md.
 414  *
 415  * @param input serialized meta-data.
 416  * @param size number of bytes available
 417  * @return MD on success, NULL on error (i.e.
 418  *         bad format)
 419  */
 420 struct GNUNET_CONTAINER_MetaData
 421   *GNUNET_CONTAINER_meta_data_deserialize (const char *input,
 422                                            size_t size);
 423
 424 /**
 425  * Does the meta-data claim that this is a directory?
 426  * Checks if the mime-type is that of a GNUnet directory.
 427  *
 428  * @param md metadata to inspect
 429  * @return GNUNET_YES if it is, GNUNET_NO if it is not, GNUNET_SYSERR if
 430  *  we have no mime-type information (treat as 'GNUNET_NO')
 431  */
 432 int GNUNET_CONTAINER_meta_data_test_for_directory (const struct
 433                                                    GNUNET_CONTAINER_MetaData
 434                                                    *md);
 435
 436
 437 /* ******************************* HashMap **************************** */
 438
 439 /**
 440  * Opaque handle for a HashMap.
 441  */
 442 struct GNUNET_CONTAINER_MultiHashMap;
 443
 444 /**
 445  * Options for storing values in the HashMap.
 446  */
 447 enum GNUNET_CONTAINER_MultiHashMapOption
 448 {
 449   /**
 450    * If a value with the given key exists, replace it.
 451    * Note that the old value would NOT be freed
 452    * by replace (the application has to make sure that
 453    * this happens if required).
 454    */
 455   GNUNET_CONTAINER_MULTIHASHMAPOPTION_REPLACE,
 456
 457   /**
 458    * Allow multiple values with the same key.
 459    */
 460   GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE,
 461
 462   /**
 463    * There must only be one value per key; storing
 464    * a value should fail if a value under the same
 465    * key already exists.
 466    */
 467   GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY,
 468
 469   /**
 470    * There must only be one value per key, but don't
 471    * bother checking if a value already exists
 472    * (faster than UNIQUE_ONLY; implemented just like
 473    * MULTIPLE but this option documents better what
 474    * is intended if UNIQUE is what is desired).
 475    */
 476   GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST
 477 };
 478
 479
 480 /**
 481  * Iterator over HashCodes.
 482  *
 483  * @param cls closure
 484  * @param key current key code
 485  * @param value value in the hash map
 486  * @return GNUNET_YES if we should continue to
 487  *         iterate,
 488  *         GNUNET_NO if not.
 489  */
 490 typedef int (*GNUNET_CONTAINER_HashMapIterator) (void *cls,
 491                                                  const GNUNET_HashCode * key,
 492                                                  void *value);
 493
 494
 495 /**
 496  * Create a multi hash map.
 497  *
 498  * @param len initial size (map will grow as needed)
 499  * @return NULL on error
 500  */
 501 struct GNUNET_CONTAINER_MultiHashMap
 502   *GNUNET_CONTAINER_multihashmap_create (unsigned int len);
 503
 504 /**
 505  * Destroy a hash map.  Will not free any values
 506  * stored in the hash map!
 507  *
 508  * @param map the map
 509  */
 510 void GNUNET_CONTAINER_multihashmap_destroy (struct
 511                                             GNUNET_CONTAINER_MultiHashMap
 512                                             *map);
 513
 514 /**
 515  * Given a key find a value in the
 516  * map matching the key.
 517  *
 518  * @param map the map
 519  * @param key what to look for
 520  * @return NULL if no value was found; note that
 521  *   this is indistinguishable from values that just
 522  *   happen to be NULL; use "contains" to test for
 523  *   key-value pairs with value NULL
 524  */
 525 void *GNUNET_CONTAINER_multihashmap_get (const struct
 526                                          GNUNET_CONTAINER_MultiHashMap *map,
 527                                          const GNUNET_HashCode * key);
 528
 529 /**
 530  * Remove the given key-value pair from the map.
 531  * Note that if the key-value pair is in the map
 532  * multiple times, only one of the pairs will be
 533  * removed.
 534  *
 535  * @param map the map
 536  * @param key key of the key-value pair
 537  * @param value value of the key-value pair
 538  * @return GNUNET_YES on success, GNUNET_NO if the key-value pair
 539  *  is not in the map
 540  */
 541 int GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap
 542                                           *map, const GNUNET_HashCode * key,
 543                                           void *value);
 544
 545 /**
 546  * Remove all entries for the given key from the map.
 547  * Note that the values would not be "freed".
 548  *
 549  * @param map the map
 550  * @param key identifies values to be removed
 551  * @return number of values removed
 552  */
 553 int GNUNET_CONTAINER_multihashmap_remove_all (struct
 554                                               GNUNET_CONTAINER_MultiHashMap
 555                                               *map,
 556                                               const GNUNET_HashCode * key);
 557
 558 /**
 559  * Check if the map contains any value under the given
 560  * key (including values that are NULL).
 561  *
 562  * @param map the map
 563  * @param key the key to test if a value exists for it
 564  * @return GNUNET_YES if such a value exists,
 565  *         GNUNET_NO if not
 566  */
 567 int GNUNET_CONTAINER_multihashmap_contains (const struct
 568                                             GNUNET_CONTAINER_MultiHashMap
 569                                             *map,
 570                                             const GNUNET_HashCode * key);
 571
 572 /**
 573  * Store a key-value pair in the map.
 574  *
 575  * @param map the map
 576  * @param key key to use
 577  * @param value value to use
 578  * @param opt options for put
 579  * @return GNUNET_OK on success,
 580  *         GNUNET_NO if a value was replaced (with REPLACE)
 581  *         GNUNET_SYSERR if UNIQUE_ONLY was the option and the
 582  *                       value already exists
 583  */
 584 int GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap
 585                                        *map, const GNUNET_HashCode * key,
 586                                        void *value,
 587                                        enum
 588                                        GNUNET_CONTAINER_MultiHashMapOption
 589                                        opt);
 590
 591 /**
 592  * Get the number of key-value pairs in the map.
 593  *
 594  * @param map the map
 595  * @return the number of key value pairs
 596  */
 597 unsigned int GNUNET_CONTAINER_multihashmap_size (const struct
 598                                                  GNUNET_CONTAINER_MultiHashMap
 599                                                  *map);
 600
 601
 602 /**
 603  * Iterate over all entries in the map.
 604  *
 605  * @param map the map
 606  * @param iterator function to call on each entry
 607  * @param cls extra argument to it
 608  * @return the number of key value pairs processed,
 609  *         GNUNET_SYSERR if it aborted iteration
 610  */
 611 int GNUNET_CONTAINER_multihashmap_iterate (const struct
 612                                            GNUNET_CONTAINER_MultiHashMap *map,
 613                                            GNUNET_CONTAINER_HashMapIterator
 614                                            iterator, void *cls);
 615
 616 /**
 617  * Iterate over all entries in the map
 618  * that match a particular key.
 619  *
 620  * @param map the map
 621  * @param key key that the entries must correspond to
 622  * @param iterator function to call on each entry
 623  * @param cls extra argument to it
 624  * @return the number of key value pairs processed,
 625  *         GNUNET_SYSERR if it aborted iteration
 626  */
 627 int GNUNET_CONTAINER_multihashmap_get_multiple (const struct
 628                                                 GNUNET_CONTAINER_MultiHashMap
 629                                                 *map,
 630                                                 const GNUNET_HashCode * key,
 631                                                 GNUNET_CONTAINER_HashMapIterator
 632                                                 iterator, void *cls);
 633 /**
 634  * Returns the stored value of a random non-null entry
 635  * in the hash table.  Returns only the first value, does
 636  * not go inside bucket linked list (yet).  Runs with a
 637  * worst case time of N, so it's not efficient in any way
 638  * shape or form!!!!.
 639  */
 640 void *GNUNET_CONTAINER_multihashmap_get_random (const struct
 641                                                 GNUNET_CONTAINER_MultiHashMap
 642                                                 *map);
 643
 644
 645
 646
 647 /* ******************** doubly-linked list *************** */
 648
 649 /**
 650  * Insert an element into a DLL. Assumes
 651  * that head, tail and element are structs
 652  * with prev and next fields.
 653  *
 654  * @param head pointer to the head of the DLL
 655  * @param tail pointer to the tail of the DLL
 656  * @param element element to insert
 657  */
 658 #define GNUNET_CONTAINER_DLL_insert(head,tail,element) \
 659   (element)->next = (head); \
 660   (element)->prev = NULL; \
 661   if ((tail) == NULL) \
 662     (tail) = element; \
 663   else \
 664     (head)->prev = element; \
 665   (head) = (element);
 666
 667 /**
 668  * Insert an element into a DLL after the given other
 669  * element.  Insert at the head if the other
 670  * element is NULL.
 671  *
 672  * @param head pointer to the head of the DLL
 673  * @param tail pointer to the tail of the DLL
 674  * @param other prior element, NULL for insertion at head of DLL
 675  * @param element element to insert
 676  */
 677 #define GNUNET_CONTAINER_DLL_insert_after(head,tail,other,element) \
 678   (element)->prev = (other); \
 679   if (NULL == other) \
 680     { \
 681       (element)->next = (head); \
 682       (head) = (element); \
 683     } \
 684   else \
 685     { \
 686       (element)->next = (other)->next; \
 687       (other)->next = (element); \
 688     } \
 689   if (NULL == (element)->next) \
 690     (tail) = (element); \
 691   else \
 692     (element)->next->prev = (element);
 693
 694
 695
 696
 697 /**
 698  * Remove an element from a DLL. Assumes
 699  * that head, tail and element are structs
 700  * with prev and next fields.
 701  *
 702  * @param head pointer to the head of the DLL
 703  * @param tail pointer to the tail of the DLL
 704  * @param element element to remove
 705  */
 706 #define GNUNET_CONTAINER_DLL_remove(head,tail,element) \
 707   if ((element)->prev == NULL) \
 708     (head) = (element)->next;  \
 709   else \
 710     (element)->prev->next = (element)->next; \
 711   if ((element)->next == NULL) \
 712     (tail) = (element)->prev;  \
 713   else \
 714     (element)->next->prev = (element)->prev;
 715
 716
 717
 718 /* ******************** Heap *************** */
 719
 720
 721 /**
 722  * Cost by which elements in a heap can be ordered.
 723  */
 724 typedef uint64_t GNUNET_CONTAINER_HeapCost;
 725
 726
 727 /*
 728  * Heap type, either max or min.  Hopefully makes the
 729  * implementation more useful.
 730  */
 731 enum GNUNET_CONTAINER_HeapOrder
 732 {
 733   /**
 734    * Heap with the maximum cost at the root.
 735    */
 736   GNUNET_CONTAINER_HEAP_ORDER_MAX,
 737
 738   /**
 739    * Heap with the minimum cost at the root.
 740    */
 741   GNUNET_CONTAINER_HEAP_ORDER_MIN
 742 };
 743
 744
 745 /**
 746  * Handle to a Heap.
 747  */
 748 struct GNUNET_CONTAINER_Heap;
 749
 750 /**
 751  * Create a new heap.
 752  *
 753  * @param type should the minimum or the maximum element be the root
 754  * @return NULL on error, otherwise a fresh heap
 755  */
 756 struct GNUNET_CONTAINER_Heap *GNUNET_CONTAINER_heap_create (enum
 757                                                             GNUNET_CONTAINER_HeapOrder
 758                                                             type);
 759
 760
 761 /**
 762  * Free a heap
 763  *
 764  * @param h heap to free.
 765  */
 766 void GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *h);
 767
 768
 769 /**
 770  * Function called on elements of a heap.
 771  *
 772  * @param cls closure
 773  * @param element obj stored in heap
 774  * @param cost cost of the element
 775  * @return GNUNET_YES if we should continue to iterate,
 776  *         GNUNET_NO if not.
 777  */
 778 typedef int (*GNUNET_CONTAINER_HeapIterator) (void *cls,
 779                                               void *element,
 780                                               GNUNET_CONTAINER_HeapCost cost);
 781
 782
 783 /**
 784  * Iterate over all entries in the map.
 785  *
 786  * @param heap the heap
 787  * @param iterator function to call on each entry
 788  * @param iterator_cls closure for iterator
 789  * @return number of items handled
 790  *         GNUNET_SYSERR if iteration was aborted by iterator
 791  */
 792 int GNUNET_CONTAINER_heap_iterate (struct GNUNET_CONTAINER_Heap *heap,
 793                                    GNUNET_CONTAINER_HeapIterator iterator,
 794                                    void *iterator_cls);
 795
 796
 797
 798 /**
 799  * Inserts a new item into the heap, item is always neighbor now.
 800  * @param heap the heap
 801  * @param element element to insert
 802  * @param cost cost of the element
 803  * @return FIXME
 804  */
 805 int
 806 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap,
 807                               void *element, GNUNET_CONTAINER_HeapCost cost);
 808
 809
 810 /**
 811  * Removes root of the tree, is remove max if a max heap and remove min
 812  * if a min heap, returns the data stored at the node.
 813  *
 814  * @param heap the heap
 815  * @return NULL if the heap is empty
 816  */
 817 void *GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap);
 818
 819
 820 /**
 821  * Returns element stored at root of tree, doesn't effect anything
 822  *
 823  * @param heap the heap
 824  * @return NULL if the heap is empty
 825  */
 826 void *GNUNET_CONTAINER_heap_peek (struct GNUNET_CONTAINER_Heap *heap);
 827
 828
 829 /**
 830  * Removes any node from the tree based on the neighbor given, does
 831  * not traverse the tree (backpointers) but may take more time due to
 832  * percolation of nodes.
 833  *
 834  * @param heap the heap
 835  * @param element the element to remove
 836  * @return NULL if "element" was not found in the heap, otherwise element
 837  */
 838 void *GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *heap,
 839                                          void *element);
 840
 841
 842 /**
 843  * Updates the cost of any node in the tree
 844  *
 845  * @param heap the heap
 846  * @param element the element for which the cost is updated
 847  * @param new_cost new cost for the element
 848  * @return FIXME
 849  */
 850 int
 851 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
 852                                    void *element,
 853                                    GNUNET_CONTAINER_HeapCost new_cost);
 854
 855
 856 /**
 857  * Random walk of the tree, returns the data stored at the next random node
 858  * in the walk.  Calls callee with the data, or NULL if the tree is empty
 859  * or some other problem crops up.
 860  *
 861  * @param heap the heap
 862  * @return the next element from the random walk
 863  */
 864 void *GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap
 865                                            *heap);
 866
 867
 868 /**
 869  * Returns the current size of the heap
 870  *
 871  * @param heap the heap to get the size of
 872  * @return number of elements in the heap
 873  */
 874 unsigned int
 875 GNUNET_CONTAINER_heap_get_size (struct GNUNET_CONTAINER_Heap *heap);
 876
 877 /* ******************** Singly linked list *************** */
 878
 879 /**
 880  * Handle to a singly linked list
 881  */
 882 struct GNUNET_CONTAINER_SList;
 883
 884 /**
 885  * Handle to a singly linked list iterator
 886  */
 887 struct GNUNET_CONTAINER_SList_Iterator;
 888
 889
 890 /**
 891  * Add a new element to the list
 892  * @param l list
 893  * @param disp memory disposition
 894  * @param buf payload buffer
 895  * @param len length of the buffer
 896  */
 897 void GNUNET_CONTAINER_slist_add (struct GNUNET_CONTAINER_SList *l, int disp, const void *buf, size_t len);
 898
 899
 900 /**
 901  * Create a new singly linked list
 902  * @return the new list
 903  */
 904 struct GNUNET_CONTAINER_SList *GNUNET_CONTAINER_slist_create (void);
 905
 906
 907 /**
 908  * Destroy a singly linked list
 909  * @param l the list to be destroyed
 910  */
 911 void GNUNET_CONTAINER_slist_destroy (struct GNUNET_CONTAINER_SList *l);
 912
 913
 914 /**
 915  * Return the beginning of a list
 916  *
 917  * @param l list
 918  * @return iterator pointing to the beginning, free using "GNUNET_free"
 919  */
 920 struct GNUNET_CONTAINER_SList_Iterator *
 921 GNUNET_CONTAINER_slist_begin(struct GNUNET_CONTAINER_SList *l);
 922
 923
 924 /**
 925  * Clear a list
 926  *
 927  * @param l list
 928  */
 929 void GNUNET_CONTAINER_slist_clear (struct GNUNET_CONTAINER_SList *l);
 930
 931
 932 /**
 933  * Check if a list contains a certain element
 934  * @param l list
 935  * @param buf payload buffer to find
 936  * @param lenght of the payload
 937  */
 938 int GNUNET_CONTAINER_slist_contains (const struct GNUNET_CONTAINER_SList *l, const void *buf, size_t len);
 939
 940
 941 /**
 942  * Count the elements of a list
 943  * @param l list
 944  * @return number of elements in the list
 945  */
 946 int GNUNET_CONTAINER_slist_count (const struct GNUNET_CONTAINER_SList *l);
 947
 948
 949 /**
 950  * Remove an element from the list
 951  * @param i iterator that points to the element to be removed
 952  */
 953 void GNUNET_CONTAINER_slist_erase (struct GNUNET_CONTAINER_SList_Iterator *i);
 954
 955
 956 /**
 957  * Insert an element into a list at a specific position
 958  * @param before where to insert the new element
 959  * @param disp memory disposition
 960  * @param buf payload buffer
 961  * @param len length of the payload
 962  */
 963 void GNUNET_CONTAINER_slist_insert (struct GNUNET_CONTAINER_SList_Iterator *before, int disp, const void *buf, size_t len);
 964
 965
 966 /**
 967  * Advance an iterator to the next element
 968  * @param i iterator
 969  * @return GNUNET_YES on success, GNUNET_NO if the end has been reached
 970  */
 971 int GNUNET_CONTAINER_slist_next (struct GNUNET_CONTAINER_SList_Iterator *i);
 972
 973
 974 /**
 975  * Check if an iterator points beyond the end of a list
 976  * @param i iterator
 977  * @return GNUNET_YES if the end has been reached, GNUNET_NO if the iterator
 978  *         points to a valid element
 979  */
 980 int GNUNET_CONTAINER_slist_end (struct GNUNET_CONTAINER_SList_Iterator *i);
 981
 982
 983 /**
 984  * Retrieve the element at a specific position in a list
 985  *
 986  * @param i iterator
 987  * @param len set to the payload length
 988  * @return payload
 989  */
 990 const void *
 991 GNUNET_CONTAINER_slist_get (const struct GNUNET_CONTAINER_SList_Iterator *i,
 992                             size_t *len);
 993
 994
 995 #if 0                           /* keep Emacsens' auto-indent happy */
 996 {
 997 #endif
 998 #ifdef __cplusplus
 999 }
1000 #endif
1001
1002
1003 /* ifndef GNUNET_CONTAINER_LIB_H */
1004 #endif
1005 /* end of gnunet_container_lib.h */