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