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