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