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 /* ******************* 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 *GNUNET_CONTAINER_bloomfilter_load (const
  74                                                                         char
  75                                                                         *filename,
  76                                                                         unsigned
  77                                                                         int
  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 *GNUNET_CONTAINER_bloomfilter_init (const
  97                                                                         char
  98                                                                         *data,
  99                                                                         unsigned
 100                                                                         int
 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                                                unsigned int 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, unsigned int 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                                           unsigned int 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  * Iterator over meta data.
 200  *
 201  * @param cls closure
 202  * @param type type of the meta data
 203  * @param data value of the meta data
 204  * @return GNUNET_OK to continue to iterate, GNUNET_SYSERR to abort
 205  */
 206 typedef int (*GNUNET_CONTAINER_MetaDataProcessor) (void *cls,
 207                                                    EXTRACTOR_KeywordType type,
 208                                                    const char *data);
 209
 210 /**
 211  * Create a fresh MetaData token.
 212  *
 213  * @return empty meta-data container
 214  */
 215 struct GNUNET_CONTAINER_MetaData *GNUNET_CONTAINER_meta_data_create (void);
 216
 217 /**
 218  * Duplicate a MetaData token.
 219  *
 220  * @param meta what to duplicate
 221  * @return duplicate meta-data container
 222  */
 223 struct GNUNET_CONTAINER_MetaData *GNUNET_CONTAINER_meta_data_duplicate (const
 224                                                                         struct
 225                                                                         GNUNET_CONTAINER_MetaData
 226                                                                         *meta);
 227
 228 /**
 229  * Free meta data.
 230  *
 231  * @param md what to free
 232  */
 233 void GNUNET_CONTAINER_meta_data_destroy (struct GNUNET_CONTAINER_MetaData
 234                                          *md);
 235
 236 /**
 237  * Test if two MDs are equal.
 238  *
 239  * @param md1 first value to check
 240  * @param md2 other value to check
 241  * @return GNUNET_YES if they are equal
 242  */
 243 int GNUNET_CONTAINER_meta_data_test_equal (const struct
 244                                            GNUNET_CONTAINER_MetaData *md1,
 245                                            const struct
 246                                            GNUNET_CONTAINER_MetaData *md2);
 247
 248
 249 /**
 250  * Extend metadata.
 251  *
 252  * @param md metadata to extend
 253  * @param type type of the new entry
 254  * @param data value for the entry
 255  * @return GNUNET_OK on success, GNUNET_SYSERR if this entry already exists
 256  */
 257 int GNUNET_CONTAINER_meta_data_insert (struct GNUNET_CONTAINER_MetaData *md,
 258                                        EXTRACTOR_KeywordType type,
 259                                        const char *data);
 260
 261 /**
 262  * Remove an item.
 263  *
 264  * @param type type of the item to remove
 265  * @param data specific value to remove, NULL to remove all
 266  *        entries of the given type
 267  * @return GNUNET_OK on success, GNUNET_SYSERR if the item does not exist in md
 268  */
 269 int GNUNET_CONTAINER_meta_data_delete (struct GNUNET_CONTAINER_MetaData *md,
 270                                        EXTRACTOR_KeywordType type,
 271                                        const char *data);
 272
 273 /**
 274  * Add the current time as the publication date
 275  * to the meta-data.
 276  *
 277  * @param md metadata to modify
 278  */
 279 void GNUNET_CONTAINER_meta_data_add_publication_date (struct
 280                                                       GNUNET_CONTAINER_MetaData
 281                                                       *md);
 282
 283 /**
 284  * Iterate over MD entries, excluding thumbnails.
 285  *
 286  * @param md metadata to inspect
 287  * @param iter function to call on each entry
 288  * @param iter_cls closure for iterator
 289  * @return number of entries
 290  */
 291 int GNUNET_CONTAINER_meta_data_get_contents (const struct
 292                                              GNUNET_CONTAINER_MetaData *md,
 293                                              GNUNET_CONTAINER_MetaDataProcessor
 294                                              iter, void *iter_cls);
 295
 296 /**
 297  * Get the first MD entry of the given type.
 298  *
 299  * @param md metadata to inspect
 300  * @param type type to look for
 301  * @return NULL if we do not have any such entry,
 302  *  otherwise client is responsible for freeing the value!
 303  */
 304 char *GNUNET_CONTAINER_meta_data_get_by_type (const struct
 305                                              GNUNET_CONTAINER_MetaData *md,
 306                                               EXTRACTOR_KeywordType type);
 307
 308 /**
 309  * Get the first matching MD entry of the given types.
 310  *
 311  * @param md metadata to inspect
 312  * @param ... -1-terminated list of types
 313  * @return NULL if we do not have any such entry,
 314  *  otherwise client is responsible for freeing the value!
 315  */
 316 char *GNUNET_CONTAINER_meta_data_get_first_by_types (const struct
 317                                                      GNUNET_CONTAINER_MetaData
 318                                                      *md, ...);
 319
 320 /**
 321  * Get a thumbnail from the meta-data (if present).
 322  *
 323  * @param md metadata to inspect
 324  * @param thumb will be set to the thumbnail data.  Must be
 325  *        freed by the caller!
 326  * @return number of bytes in thumbnail, 0 if not available
 327  */
 328 size_t GNUNET_CONTAINER_meta_data_get_thumbnail (const struct
 329                                                  GNUNET_CONTAINER_MetaData
 330                                                  *md, unsigned char **thumb);
 331
 332 /**
 333  * Extract meta-data from a file.
 334  *
 335  * @param md metadata to set
 336  * @param filename name of file to inspect
 337  * @param extractors plugins to use
 338  * @return GNUNET_SYSERR on error, otherwise the number
 339  *   of meta-data items obtained
 340  */
 341 int GNUNET_CONTAINER_meta_data_extract_from_file (struct
 342                                                   GNUNET_CONTAINER_MetaData
 343                                                   *md, const char *filename,
 344                                                   EXTRACTOR_ExtractorList *
 345                                                   extractors);
 346
 347 enum GNUNET_CONTAINER_MetaDataSerializationOptions
 348 {
 349   GNUNET_CONTAINER_META_DATA_SERIALIZE_FULL = 0,
 350   GNUNET_CONTAINER_META_DATA_SERIALIZE_PART = 1,
 351   GNUNET_CONTAINER_META_DATA_SERIALIZE_NO_COMPRESS = 2
 352 };
 353
 354
 355
 356 /**
 357  * Serialize meta-data to target.
 358  *
 359  * @param md metadata to serialize
 360  * @param size maximum number of bytes available
 361  * @param opt is it ok to just write SOME of the
 362  *        meta-data to match the size constraint,
 363  *        possibly discarding some data?
 364  * @return number of bytes written on success,
 365  *         -1 on error (typically: not enough
 366  *         space)
 367  */
 368 ssize_t GNUNET_CONTAINER_meta_data_serialize (const struct
 369                                               GNUNET_CONTAINER_MetaData *md,
 370                                               char *target,
 371                                               size_t size,
 372                                               enum
 373                                           GNUNET_CONTAINER_MetaDataSerializationOptions
 374                                           opt);
 375
 376 /**
 377  * Compute size of the meta-data in
 378  * serialized form.
 379  *
 380  * @param md metadata to inspect
 381  * @param opt is it ok to just write SOME of the
 382  *        meta-data to match the size constraint,
 383  *        possibly discarding some data?
 384  * @return number of bytes needed for serialization, -1 on error
 385  */
 386 ssize_t GNUNET_CONTAINER_meta_data_get_serialized_size (const struct
 387                                                         GNUNET_CONTAINER_MetaData
 388                                                         *md,
 389                                                         enum
 390                                                         GNUNET_CONTAINER_MetaDataSerializationOptions
 391                                                         opt);
 392
 393 /**
 394  * Deserialize meta-data.  Initializes md.
 395  *
 396  * @param input serialized meta-data.
 397  * @param size number of bytes available
 398  * @return MD on success, NULL on error (i.e.
 399  *         bad format)
 400  */
 401 struct GNUNET_CONTAINER_MetaData
 402   *GNUNET_CONTAINER_meta_data_deserialize (const char *input,
 403                                            size_t size);
 404
 405 /**
 406  * Does the meta-data claim that this is a directory?
 407  * Checks if the mime-type is that of a GNUnet directory.
 408  *
 409  * @param md metadata to inspect
 410  * @return GNUNET_YES if it is, GNUNET_NO if it is not, GNUNET_SYSERR if
 411  *  we have no mime-type information (treat as 'GNUNET_NO')
 412  */
 413 int GNUNET_CONTAINER_meta_data_test_for_directory (const struct
 414                                                    GNUNET_CONTAINER_MetaData
 415                                                    *md);
 416
 417
 418 /* ******************************* HashMap **************************** */
 419
 420 /**
 421  * Opaque handle for a HashMap.
 422  */
 423 struct GNUNET_CONTAINER_MultiHashMap;
 424
 425 /**
 426  * Options for storing values in the HashMap.
 427  */
 428 enum GNUNET_CONTAINER_MultiHashMapOption
 429 {
 430   /**
 431    * If a value with the given key exists, replace it.
 432    * Note that the old value would NOT be freed
 433    * by replace (the application has to make sure that
 434    * this happens if required).
 435    */
 436   GNUNET_CONTAINER_MULTIHASHMAPOPTION_REPLACE,
 437
 438   /**
 439    * Allow multiple values with the same key.
 440    */
 441   GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE,
 442
 443   /**
 444    * There must only be one value per key; storing
 445    * a value should fail if a value under the same
 446    * key already exists.
 447    */
 448   GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY,
 449
 450   /**
 451    * There must only be one value per key, but don't
 452    * bother checking if a value already exists
 453    * (faster than UNIQUE_ONLY; implemented just like
 454    * MULTIPLE but this option documents better what
 455    * is intended if UNIQUE is what is desired).
 456    */
 457   GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST
 458 };
 459
 460 /**
 461  * Iterator over HashCodes.
 462  *
 463  * @param cls closure
 464  * @param key current key code
 465  * @param value value in the hash map
 466  * @return GNUNET_YES if we should continue to
 467  *         iterate,
 468  *         GNUNET_NO if not.
 469  */
 470 typedef int (*GNUNET_CONTAINER_HashMapIterator) (void *cls,
 471                                                  const GNUNET_HashCode * key,
 472                                                  void *value);
 473
 474
 475 /**
 476  * Create a multi hash map.
 477  *
 478  * @param map the map
 479  * @param len initial size (map will grow as needed)
 480  * @return NULL on error
 481  */
 482 struct GNUNET_CONTAINER_MultiHashMap
 483   *GNUNET_CONTAINER_multihashmap_create (unsigned int len);
 484
 485 /**
 486  * Destroy a hash map.  Will not free any values
 487  * stored in the hash map!
 488  *
 489  * @param map the map
 490  */
 491 void GNUNET_CONTAINER_multihashmap_destroy (struct
 492                                             GNUNET_CONTAINER_MultiHashMap
 493                                             *map);
 494
 495 /**
 496  * Given a key find a value in the
 497  * map matching the key.
 498  *
 499  * @param map the map
 500  * @param key what to look for
 501  * @return NULL if no value was found; note that
 502  *   this is indistinguishable from values that just
 503  *   happen to be NULL; use "contains" to test for
 504  *   key-value pairs with value NULL
 505  */
 506 void *GNUNET_CONTAINER_multihashmap_get (const struct
 507                                          GNUNET_CONTAINER_MultiHashMap *map,
 508                                          const GNUNET_HashCode * key);
 509
 510 /**
 511  * Remove the given key-value pair from the map.
 512  * Note that if the key-value pair is in the map
 513  * multiple times, only one of the pairs will be
 514  * removed.
 515  *
 516  * @param map the map
 517  * @param key key of the key-value pair
 518  * @param value value of the key-value pair
 519  * @return GNUNET_YES on success, GNUNET_NO if the key-value pair
 520  *  is not in the map
 521  */
 522 int GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap
 523                                           *map, const GNUNET_HashCode * key,
 524                                           void *value);
 525
 526 /**
 527  * Remove all entries for the given key from the map.
 528  * Note that the values would not be "freed".
 529  *
 530  * @param map the map
 531  * @param key identifies values to be removed
 532  * @return number of values removed
 533  */
 534 int GNUNET_CONTAINER_multihashmap_remove_all (struct
 535                                               GNUNET_CONTAINER_MultiHashMap
 536                                               *map,
 537                                               const GNUNET_HashCode * key);
 538
 539 /**
 540  * Check if the map contains any value under the given
 541  * key (including values that are NULL).
 542  *
 543  * @param map the map
 544  * @param key the key to test if a value exists for it
 545  * @return GNUNET_YES if such a value exists,
 546  *         GNUNET_NO if not
 547  */
 548 int GNUNET_CONTAINER_multihashmap_contains (const struct
 549                                             GNUNET_CONTAINER_MultiHashMap
 550                                             *map,
 551                                             const GNUNET_HashCode * key);
 552
 553 /**
 554  * Store a key-value pair in the map.
 555  *
 556  * @param map the map
 557  * @param key key to use
 558  * @param value value to use
 559  * @param opt options for put
 560  * @return GNUNET_OK on success,
 561  *         GNUNET_NO if a value was replaced (with REPLACE)
 562  *         GNUNET_SYSERR if UNIQUE_ONLY was the option and the
 563  *                       value already exists
 564  */
 565 int GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap
 566                                        *map, const GNUNET_HashCode * key,
 567                                        void *value,
 568                                        enum
 569                                        GNUNET_CONTAINER_MultiHashMapOption
 570                                        opt);
 571
 572 /**
 573  * Get the number of key-value pairs in the map.
 574  *
 575  * @param map the map
 576  * @return the number of key value pairs
 577  */
 578 unsigned int GNUNET_CONTAINER_multihashmap_size (const struct
 579                                                  GNUNET_CONTAINER_MultiHashMap
 580                                                  *map);
 581
 582
 583 /**
 584  * Iterate over all entries in the map.
 585  *
 586  * @param map the map
 587  * @param iterator function to call on each entry
 588  * @param cls extra argument to it
 589  * @return the number of key value pairs processed,
 590  *         GNUNET_SYSERR if it aborted iteration
 591  */
 592 int GNUNET_CONTAINER_multihashmap_iterate (const struct
 593                                            GNUNET_CONTAINER_MultiHashMap *map,
 594                                            GNUNET_CONTAINER_HashMapIterator
 595                                            iterator, void *cls);
 596
 597 /**
 598  * Iterate over all entries in the map
 599  * that match a particular key.
 600  *
 601  * @param map the map
 602  * @param key key that the entries must correspond to
 603  * @param iterator function to call on each entry
 604  * @param cls extra argument to it
 605  * @return the number of key value pairs processed,
 606  *         GNUNET_SYSERR if it aborted iteration
 607  */
 608 int GNUNET_CONTAINER_multihashmap_get_multiple (const struct
 609                                                 GNUNET_CONTAINER_MultiHashMap
 610                                                 *map,
 611                                                 const GNUNET_HashCode * key,
 612                                                 GNUNET_CONTAINER_HashMapIterator
 613                                                 iterator, void *cls);
 614 /**
 615  * Returns the stored value of a random non-null entry
 616  * in the hash table.  Returns only the first value, does
 617  * not go inside bucket linked list (yet).  Runs with a
 618  * worst case time of N, so it's not efficient in any way
 619  * shape or form!!!!.
 620  */
 621 void *GNUNET_CONTAINER_multihashmap_get_random (const struct
 622                                                 GNUNET_CONTAINER_MultiHashMap
 623                                                 *map);
 624
 625
 626
 627
 628 /* ******************** doubly-linked list *************** */
 629
 630 /**
 631  * Insert an element into a DLL. Assumes
 632  * that head, tail and element are structs
 633  * with prev and next fields.
 634  */
 635 #define GNUNET_CONTAINER_DLL_insert(head,tail,element) \
 636   (element)->next = (head); \
 637   (element)->prev = NULL; \
 638   if ((tail) == NULL) \
 639     (tail) = element; \
 640   else \
 641     (head)->prev = element; \
 642   (head) = (element);
 643
 644 /**
 645  * Insert an element into a DLL after the given other
 646  * element.  Insert at the head if the other
 647  * element is NULL.
 648  */
 649 #define GNUNET_CONTAINER_DLL_insert_after(head,tail,other,element) \
 650   (element)->prev = (other); \
 651   if (NULL == other) \
 652     { \
 653       (element)->next = (head); \
 654       (head) = (element); \
 655     } \
 656   else \
 657     { \
 658       (element)->next = (other)->next; \
 659       (other)->next = (element); \
 660     } \
 661   if (NULL == (element)->next) \
 662     (tail) = (element); \
 663   else \
 664     (element)->next->prev = (element);
 665
 666
 667
 668
 669 /**
 670  * Remove an element from a DLL. Assumes
 671  * that head, tail and element are structs
 672  * with prev and next fields.
 673  */
 674 #define GNUNET_CONTAINER_DLL_remove(head,tail,element) \
 675   if ((element)->prev == NULL) \
 676     (head) = (element)->next;  \
 677   else \
 678     (element)->prev->next = (element)->next; \
 679   if ((element)->next == NULL) \
 680     (tail) = (element)->prev;  \
 681   else \
 682     (element)->next->prev = (element)->prev;
 683
 684
 685
 686 /* ******************** Heap *************** */
 687
 688
 689 /**
 690  * Cost by which elements in a heap can be ordered.
 691  */
 692 typedef unsigned int GNUNET_CONTAINER_HeapCost;
 693
 694 /*
 695  * Heap type, either max or min.  Hopefully makes the
 696  * implementation more useful.
 697  */
 698 enum GNUNET_CONTAINER_HeapOrder
 699 {
 700   /**
 701    * Heap with the maximum cost at the root.
 702    */
 703   GNUNET_CONTAINER_HEAP_ORDER_MAX,
 704
 705   /**
 706    * Heap with the minimum cost at the root.
 707    */
 708   GNUNET_CONTAINER_HEAP_ORDER_MIN
 709 };
 710
 711 /**
 712  * Handle to a Heap.
 713  */
 714 struct GNUNET_CONTAINER_Heap;
 715
 716 /**
 717  * Create a new heap.
 718  *
 719  * @param type should the minimum or the maximum element be the root
 720  * @return NULL on error, otherwise a fresh heap
 721  */
 722 struct GNUNET_CONTAINER_Heap *GNUNET_CONTAINER_heap_create (enum
 723                                                             GNUNET_CONTAINER_HeapOrder
 724                                                             type);
 725
 726 /**
 727  * Free a heap
 728  *
 729  * @param h heap to free.
 730  */
 731 void GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *h);
 732
 733 /**
 734  * Function called on elements of a heap.
 735  *
 736  * @param cls closure
 737  * @param element obj stored in heap
 738  * @param cost cost of the element
 739  * @return GNUNET_YES if we should continue to iterate,
 740  *         GNUNET_NO if not.
 741  */
 742 typedef int (*GNUNET_CONTAINER_HeapIterator) (void *cls,
 743                                               void *element,
 744                                               GNUNET_CONTAINER_HeapCost cost);
 745 /**
 746  * Iterate over all entries in the map.
 747  *
 748  * @param heap the heap
 749  * @param iterator function to call on each entry
 750  * @param iterator_cls closure for iterator
 751  * @return number of items handled
 752  *         GNUNET_SYSERR if iteration was aborted by iterator
 753  */
 754 int GNUNET_CONTAINER_heap_iterate (struct GNUNET_CONTAINER_Heap *heap,
 755                                    GNUNET_CONTAINER_HeapIterator iterator,
 756                                    void *iterator_cls);
 757
 758
 759 /**
 760  * Inserts a new item into the heap, item is always neighbor now.
 761  * @param heap the heap
 762  */
 763 int
 764 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap,
 765                               void *element, GNUNET_CONTAINER_HeapCost cost);
 766
 767 /**
 768  * Removes root of the tree, is remove max if a max heap and remove min
 769  * if a min heap, returns the data stored at the node.
 770  *
 771  * @param heap the heap
 772  * @return NULL if the heap is empty
 773  */
 774 void *GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap);
 775
 776 /**
 777  * Returns element stored at root of tree, doesn't effect anything
 778  *
 779  * @param heap the heap
 780  * @return NULL if the heap is empty
 781  */
 782 void *GNUNET_CONTAINER_heap_peek (struct GNUNET_CONTAINER_Heap *heap);
 783
 784 /**
 785  * Removes any node from the tree based on the neighbor given, does
 786  * not traverse the tree (backpointers) but may take more time due to
 787  * percolation of nodes.
 788  * @param heap the heap
 789  */
 790 void *GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *heap,
 791                                          void *element);
 792
 793 /**
 794  * Updates the cost of any node in the tree
 795  *
 796  * @param heap the heap
 797  * @param element the element for which the cost is updated
 798  * @param new_cost new cost for the element
 799  * @return WHAT?
 800  */
 801 int
 802 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
 803                                    void *element,
 804                                    GNUNET_CONTAINER_HeapCost new_cost);
 805
 806 /**
 807  * Random walk of the tree, returns the data stored at the next random node
 808  * in the walk.  Calls callee with the data, or NULL if the tree is empty
 809  * or some other problem crops up.
 810  *
 811  * @param heap the heap
 812  * @return the next element from the random walk
 813  */
 814 void *GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap
 815                                            *heap);
 816
 817 /**
 818  * Returns the current size of the heap
 819  *
 820  * @param heap the heap to get the size of
 821  * @return number of elements in the heap
 822  */
 823 unsigned int
 824 GNUNET_CONTAINER_heap_get_size (struct GNUNET_CONTAINER_Heap *heap);
 825
 826
 827 /* ******************** Vector *************** */
 828
 829 /**
 830  * Handle to a vector
 831  */
 832 struct GNUNET_CONTAINER_Vector;
 833
 834 /**
 835  * A debug function that traverses the linked list and prints the
 836  * sizes of the segments.
 837  */
 838 void GNUNET_CONTAINER_vector_dump(struct GNUNET_CONTAINER_Vector *v);
 839
 840 /**
 841  * Allocate a new vector structure with a single empty data segment.
 842  */
 843 struct GNUNET_CONTAINER_Vector * GNUNET_CONTAINER_vector_create(unsigned int vss);
 844
 845 /**
 846  * Free vector structure including its data segments, but _not_ including the
 847  * stored void pointers. It is the user's responsibility to empty the vector
 848  * when necessary to avoid memory leakage.
 849  */
 850 void GNUNET_CONTAINER_vector_destroy(struct GNUNET_CONTAINER_Vector *v);
 851
 852 /**
 853  * Return the size of the vector.
 854  */
 855 size_t GNUNET_CONTAINER_vector_size(struct GNUNET_CONTAINER_Vector *v);
 856
 857 /**
 858  * Insert a new element in the vector at given index. The return value is
 859  * OK on success, SYSERR if the index is out of bounds.
 860  */
 861 int GNUNET_CONTAINER_vector_insert_at(struct GNUNET_CONTAINER_Vector *v,
 862                    void *object,
 863                    unsigned int index);
 864
 865 /**
 866  * Insert a new element at the end of the vector.
 867  */
 868 void GNUNET_CONTAINER_vector_insert_last(struct GNUNET_CONTAINER_Vector *v, void *object);
 869
 870 /**
 871  * Return the element at given index in the vector or NULL if the index is out
 872  * of bounds. The iterator is set to point to the returned element.
 873  */
 874 void * GNUNET_CONTAINER_vector_get_at(struct GNUNET_CONTAINER_Vector *v,
 875                    unsigned int index);
 876
 877 /**
 878  * Return the first element in the vector, whose index is 0, or NULL if the
 879  * vector is empty. The iterator of the vector is set to point to the first
 880  * element.
 881  */
 882 void * GNUNET_CONTAINER_vector_get_first(struct GNUNET_CONTAINER_Vector *v);
 883
 884 /**
 885  * Return the last element in the vector or NULL if the vector is
 886  * empty. The iterator of the vector is set to the last element.
 887  */
 888 void * GNUNET_CONTAINER_vector_get_last(struct GNUNET_CONTAINER_Vector *v);
 889
 890 /**
 891  * Return the next element in the vector, as called after vector_get_at() or
 892  * vector_get_first(). The return value is NULL if there are no more elements
 893  * in the vector or if the iterator has not been set.
 894  */
 895 void * GNUNET_CONTAINER_vector_get_next(struct GNUNET_CONTAINER_Vector *v);
 896
 897 /**
 898  * Return the previous element in the vector, as called after vector_get_at()
 899  * or vector_get_last(). The return value is NULL if there are no more
 900  * elements in the vector or if the iterator has not been set.
 901  */
 902 void * GNUNET_CONTAINER_vector_get_previous(struct GNUNET_CONTAINER_Vector * v);
 903
 904 /**
 905  * Delete and return the element at given index. NULL is returned if index is
 906  * out of bounds.
 907  */
 908 void * GNUNET_CONTAINER_vector_remove_at(struct GNUNET_CONTAINER_Vector *v,
 909                       unsigned int index);
 910
 911 /**
 912  * Delete and return the last element in the vector, or NULL if the vector
 913  * is empty.
 914  */
 915 void *GNUNET_CONTAINER_vector_remove_last (struct GNUNET_CONTAINER_Vector *v);
 916
 917 /**
 918  * Delete and return given object from the vector, or return NULL if the object
 919  * is not found.
 920  */
 921 void * GNUNET_CONTAINER_vector_remove_object(struct GNUNET_CONTAINER_Vector *v, void *object);
 922
 923 /**
 924  * Set the given index in the vector. The old value of the index is
 925  * returned, or NULL if the index is out of bounds.
 926  */
 927 void *GNUNET_CONTAINER_vector_set_at (struct GNUNET_CONTAINER_Vector *v,
 928                    void *object,
 929                    unsigned int index);
 930
 931 /**
 932  * Set the index occupied by the given object to point to the new object.
 933  * The old object is returned, or NULL if it's not found.
 934  */
 935 void *GNUNET_CONTAINER_vector_set_object(struct GNUNET_CONTAINER_Vector *v,
 936                       void *object,
 937                       void *oldObject);
 938
 939 /**
 940  * Swaps the contents of index1 and index2. Return value is OK
 941  * on success, SYSERR if either index is out of bounds.
 942  */
 943 int GNUNET_CONTAINER_vector_swap(struct GNUNET_CONTAINER_Vector *v,
 944                unsigned int index1,
 945                unsigned int index2);
 946
 947 /**
 948  * Return the index of given element or -1 if the element is not found.
 949  */
 950 unsigned int GNUNET_CONTAINER_vector_index_of(struct GNUNET_CONTAINER_Vector *v,
 951                            void *object);
 952
 953 /*
 954  * Return the data stored in the vector as a single dynamically allocated
 955  * array of (void *), which must be free(3)d by the user. Use the functions
 956  * get_{at,first,last,next,previous} instead, unless you really need to access
 957  * everything in the vector as fast as possible.
 958  */
 959 void ** GNUNET_CONTAINER_vector_elements (struct GNUNET_CONTAINER_Vector *v);
 960
 961
 962 #if 0                           /* keep Emacsens' auto-indent happy */
 963 {
 964 #endif
 965 #ifdef __cplusplus
 966 }
 967 #endif
 968
 969
 970 /* ifndef GNUNET_CONTAINER_LIB_H */
 971 #endif
 972 /* end of gnunet_container_lib.h */