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