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 cls closure
 459  * @param key current key code
 460  * @param value value in the hash map
 461  * @return GNUNET_YES if we should continue to
 462  *         iterate,
 463  *         GNUNET_NO if not.
 464  */
 465 typedef int (*GNUNET_CONTAINER_HashMapIterator) (void *cls,
 466                                                  const GNUNET_HashCode * key,
 467                                                  void *value);
 468
 469
 470 /**
 471  * Create a multi hash map.
 472  *
 473  * @param map the map
 474  * @param len initial size (map will grow as needed)
 475  * @return NULL on error
 476  */
 477 struct GNUNET_CONTAINER_MultiHashMap
 478   *GNUNET_CONTAINER_multihashmap_create (unsigned int len);
 479
 480 /**
 481  * Destroy a hash map.  Will not free any values
 482  * stored in the hash map!
 483  *
 484  * @param map the map
 485  */
 486 void GNUNET_CONTAINER_multihashmap_destroy (struct
 487                                             GNUNET_CONTAINER_MultiHashMap
 488                                             *map);
 489
 490 /**
 491  * Given a key find a value in the
 492  * map matching the key.
 493  *
 494  * @param map the map
 495  * @param key what to look for
 496  * @return NULL if no value was found; note that
 497  *   this is indistinguishable from values that just
 498  *   happen to be NULL; use "contains" to test for
 499  *   key-value pairs with value NULL
 500  */
 501 void *GNUNET_CONTAINER_multihashmap_get (const struct
 502                                          GNUNET_CONTAINER_MultiHashMap *map,
 503                                          const GNUNET_HashCode * key);
 504
 505 /**
 506  * Remove the given key-value pair from the map.
 507  * Note that if the key-value pair is in the map
 508  * multiple times, only one of the pairs will be
 509  * removed.
 510  *
 511  * @param map the map
 512  * @param key key of the key-value pair
 513  * @param value value of the key-value pair
 514  * @return GNUNET_YES on success, GNUNET_NO if the key-value pair
 515  *  is not in the map
 516  */
 517 int GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap
 518                                           *map, const GNUNET_HashCode * key,
 519                                           void *value);
 520
 521 /**
 522  * Remove all entries for the given key from the map.
 523  * Note that the values would not be "freed".
 524  *
 525  * @param map the map
 526  * @param key identifies values to be removed
 527  * @return number of values removed
 528  */
 529 int GNUNET_CONTAINER_multihashmap_remove_all (struct
 530                                               GNUNET_CONTAINER_MultiHashMap
 531                                               *map,
 532                                               const GNUNET_HashCode * key);
 533
 534 /**
 535  * Check if the map contains any value under the given
 536  * key (including values that are NULL).
 537  *
 538  * @param map the map
 539  * @param key the key to test if a value exists for it
 540  * @return GNUNET_YES if such a value exists,
 541  *         GNUNET_NO if not
 542  */
 543 int GNUNET_CONTAINER_multihashmap_contains (const struct
 544                                             GNUNET_CONTAINER_MultiHashMap
 545                                             *map,
 546                                             const GNUNET_HashCode * key);
 547
 548 /**
 549  * Store a key-value pair in the map.
 550  *
 551  * @param map the map
 552  * @param key key to use
 553  * @param value value to use
 554  * @param opt options for put
 555  * @return GNUNET_OK on success,
 556  *         GNUNET_NO if a value was replaced (with REPLACE)
 557  *         GNUNET_SYSERR if UNIQUE_ONLY was the option and the
 558  *                       value already exists
 559  */
 560 int GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap
 561                                        *map, const GNUNET_HashCode * key,
 562                                        void *value,
 563                                        enum
 564                                        GNUNET_CONTAINER_MultiHashMapOption
 565                                        opt);
 566
 567 /**
 568  * Get the number of key-value pairs in the map.
 569  *
 570  * @param map the map
 571  * @return the number of key value pairs
 572  */
 573 unsigned int GNUNET_CONTAINER_multihashmap_size (const struct
 574                                                  GNUNET_CONTAINER_MultiHashMap
 575                                                  *map);
 576
 577
 578 /**
 579  * Iterate over all entries in the map.
 580  *
 581  * @param map the map
 582  * @param iterator function to call on each entry
 583  * @param cls extra argument to it
 584  * @return the number of key value pairs processed,
 585  *         GNUNET_SYSERR if it aborted iteration
 586  */
 587 int GNUNET_CONTAINER_multihashmap_iterate (const struct
 588                                            GNUNET_CONTAINER_MultiHashMap *map,
 589                                            GNUNET_CONTAINER_HashMapIterator
 590                                            iterator, void *cls);
 591
 592 /**
 593  * Iterate over all entries in the map
 594  * that match a particular key.
 595  *
 596  * @param map the map
 597  * @param key key that the entries must correspond to
 598  * @param iterator function to call on each entry
 599  * @param cls extra argument to it
 600  * @return the number of key value pairs processed,
 601  *         GNUNET_SYSERR if it aborted iteration
 602  */
 603 int GNUNET_CONTAINER_multihashmap_get_multiple (const struct
 604                                                 GNUNET_CONTAINER_MultiHashMap
 605                                                 *map,
 606                                                 const GNUNET_HashCode * key,
 607                                                 GNUNET_CONTAINER_HashMapIterator
 608                                                 iterator, void *cls);
 609 /**
 610  * Returns the stored value of a random non-null entry
 611  * in the hash table.  Returns only the first value, does
 612  * not go inside bucket linked list (yet).  Runs with a
 613  * worst case time of N, so it's not efficient in any way
 614  * shape or form!!!!.
 615  */
 616 void *GNUNET_CONTAINER_multihashmap_get_random (const struct
 617                                                 GNUNET_CONTAINER_MultiHashMap
 618                                                 *map);
 619
 620
 621
 622
 623 /* ******************** doubly-linked list *************** */
 624
 625 /**
 626  * Insert an element into a DLL. Assumes
 627  * that head, tail and element are structs
 628  * with prev and next fields.
 629  */
 630 #define GNUNET_CONTAINER_DLL_insert(head,tail,element) \
 631   (element)->next = (head); \
 632   (element)->prev = NULL; \
 633   if ((tail) == NULL) \
 634     (tail) = element; \
 635   else \
 636     (head)->prev = element; \
 637   (head) = (element);
 638
 639 /**
 640  * Insert an element into a DLL after the given other
 641  * element.  Insert at the head if the other
 642  * element is NULL.
 643  */
 644 #define GNUNET_CONTAINER_DLL_insert_after(head,tail,other,element) \
 645   (element)->prev = (other); \
 646   if (NULL == other) \
 647     { \
 648       (element)->next = (head); \
 649       (head) = (element); \
 650     } \
 651   else \
 652     { \
 653       (element)->next = (other)->next; \
 654       (other)->next = (element); \
 655     } \
 656   if (NULL == (element)->next) \
 657     (tail) = (element); \
 658   else \
 659     (element)->next->prev = (element);
 660
 661
 662
 663
 664 /**
 665  * Remove an element from a DLL. Assumes
 666  * that head, tail and element are structs
 667  * with prev and next fields.
 668  */
 669 #define GNUNET_CONTAINER_DLL_remove(head,tail,element) \
 670   if ((element)->prev == NULL) \
 671     (head) = (element)->next;  \
 672   else \
 673     (element)->prev->next = (element)->next; \
 674   if ((element)->next == NULL) \
 675     (tail) = (element)->prev;  \
 676   else \
 677     (element)->next->prev = (element)->prev;
 678
 679
 680
 681 /* ******************** Heap *************** */
 682
 683
 684 /**
 685  * Cost by which elements in a heap can be ordered.
 686  */
 687 typedef unsigned int GNUNET_CONTAINER_HeapCost;
 688
 689 /*
 690  * Heap type, either max or min.  Hopefully makes the
 691  * implementation more useful.
 692  */
 693 enum GNUNET_CONTAINER_HeapOrder
 694 {
 695   /**
 696    * Heap with the maximum cost at the root.
 697    */
 698   GNUNET_CONTAINER_HEAP_ORDER_MAX,
 699
 700   /**
 701    * Heap with the minimum cost at the root.
 702    */
 703   GNUNET_CONTAINER_HEAP_ORDER_MIN
 704 };
 705
 706 /**
 707  * Handle to a Heap.
 708  */
 709 struct GNUNET_CONTAINER_Heap;
 710
 711 /**
 712  * Create a new heap.
 713  *
 714  * @param type should the minimum or the maximum element be the root
 715  * @return NULL on error, otherwise a fresh heap
 716  */
 717 struct GNUNET_CONTAINER_Heap *GNUNET_CONTAINER_heap_create (enum
 718                                                             GNUNET_CONTAINER_HeapOrder
 719                                                             type);
 720
 721 /**
 722  * Free a heap
 723  *
 724  * @param h heap to free.
 725  */
 726 void GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *h);
 727
 728 /**
 729  * Function called on elements of a heap.
 730  *
 731  * @param cls closure
 732  * @param element obj stored in heap
 733  * @param cost cost of the element
 734  * @return GNUNET_YES if we should continue to iterate,
 735  *         GNUNET_NO if not.
 736  */
 737 typedef int (*GNUNET_CONTAINER_HeapIterator) (void *cls,
 738                                               void *element,
 739                                               GNUNET_CONTAINER_HeapCost cost);
 740 /**
 741  * Iterate over all entries in the map.
 742  *
 743  * @param heap the heap
 744  * @param iterator function to call on each entry
 745  * @param iterator_cls closure for iterator
 746  * @return number of items handled
 747  *         GNUNET_SYSERR if iteration was aborted by iterator
 748  */
 749 int GNUNET_CONTAINER_heap_iterate (struct GNUNET_CONTAINER_Heap *heap,
 750                                    GNUNET_CONTAINER_HeapIterator iterator,
 751                                    void *iterator_cls);
 752
 753
 754 /**
 755  * Inserts a new item into the heap, item is always neighbor now.
 756  * @param heap the heap
 757  */
 758 int
 759 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap,
 760                               void *element, GNUNET_CONTAINER_HeapCost cost);
 761
 762 /**
 763  * Removes root of the tree, is remove max if a max heap and remove min
 764  * if a min heap, returns the data stored at the node.
 765  *
 766  * @param heap the heap
 767  * @return NULL if the heap is empty
 768  */
 769 void *GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap);
 770
 771 /**
 772  * Returns element stored at root of tree, doesn't effect anything
 773  *
 774  * @param heap the heap
 775  * @return NULL if the heap is empty
 776  */
 777 void *GNUNET_CONTAINER_heap_peek (struct GNUNET_CONTAINER_Heap *heap);
 778
 779 /**
 780  * Removes any node from the tree based on the neighbor given, does
 781  * not traverse the tree (backpointers) but may take more time due to
 782  * percolation of nodes.
 783  * @param heap the heap
 784  */
 785 void *GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *heap,
 786                                          void *element);
 787
 788 /**
 789  * Updates the cost of any node in the tree
 790  *
 791  * @param heap the heap
 792  * @param element the element for which the cost is updated
 793  * @param new_cost new cost for the element
 794  * @return WHAT?
 795  */
 796 int
 797 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
 798                                    void *element,
 799                                    GNUNET_CONTAINER_HeapCost new_cost);
 800
 801 /**
 802  * Random walk of the tree, returns the data stored at the next random node
 803  * in the walk.  Calls callee with the data, or NULL if the tree is empty
 804  * or some other problem crops up.
 805  *
 806  * @param heap the heap
 807  * @return the next element from the random walk
 808  */
 809 void *GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap
 810                                            *heap);
 811
 812 /**
 813  * Returns the current size of the heap
 814  *
 815  * @param heap the heap to get the size of
 816  * @return number of elements in the heap
 817  */
 818 unsigned int
 819 GNUNET_CONTAINER_heap_get_size (struct GNUNET_CONTAINER_Heap *heap);
 820
 821
 822 /* ******************** Vector *************** */
 823
 824 /**
 825  * Handle to a vector
 826  */
 827 struct GNUNET_CONTAINER_Vector;
 828
 829 /**
 830  * A debug function that traverses the linked list and prints the
 831  * sizes of the segments.
 832  */
 833 void GNUNET_CONTAINER_vector_dump(struct GNUNET_CONTAINER_Vector *v);
 834
 835 /**
 836  * Allocate a new vector structure with a single empty data segment.
 837  */
 838 struct GNUNET_CONTAINER_Vector * GNUNET_CONTAINER_vector_create(unsigned int vss);
 839
 840 /**
 841  * Free vector structure including its data segments, but _not_ including the
 842  * stored void pointers. It is the user's responsibility to empty the vector
 843  * when necessary to avoid memory leakage.
 844  */
 845 void GNUNET_CONTAINER_vector_destroy(struct GNUNET_CONTAINER_Vector *v);
 846
 847 /**
 848  * Return the size of the vector.
 849  */
 850 size_t GNUNET_CONTAINER_vector_size(struct GNUNET_CONTAINER_Vector *v);
 851
 852 /**
 853  * Insert a new element in the vector at given index. The return value is
 854  * OK on success, SYSERR if the index is out of bounds.
 855  */
 856 int GNUNET_CONTAINER_vector_insert_at(struct GNUNET_CONTAINER_Vector *v,
 857                    void *object,
 858                    unsigned int index);
 859
 860 /**
 861  * Insert a new element at the end of the vector.
 862  */
 863 void GNUNET_CONTAINER_vector_insert_last(struct GNUNET_CONTAINER_Vector *v, void *object);
 864
 865 /**
 866  * Return the element at given index in the vector or NULL if the index is out
 867  * of bounds. The iterator is set to point to the returned element.
 868  */
 869 void * GNUNET_CONTAINER_vector_get_at(struct GNUNET_CONTAINER_Vector *v,
 870                    unsigned int index);
 871
 872 /**
 873  * Return the first element in the vector, whose index is 0, or NULL if the
 874  * vector is empty. The iterator of the vector is set to point to the first
 875  * element.
 876  */
 877 void * GNUNET_CONTAINER_vector_get_first(struct GNUNET_CONTAINER_Vector *v);
 878
 879 /**
 880  * Return the last element in the vector or NULL if the vector is
 881  * empty. The iterator of the vector is set to the last element.
 882  */
 883 void * GNUNET_CONTAINER_vector_get_last(struct GNUNET_CONTAINER_Vector *v);
 884
 885 /**
 886  * Return the next element in the vector, as called after vector_get_at() or
 887  * vector_get_first(). The return value is NULL if there are no more elements
 888  * in the vector or if the iterator has not been set.
 889  */
 890 void * GNUNET_CONTAINER_vector_get_next(struct GNUNET_CONTAINER_Vector *v);
 891
 892 /**
 893  * Return the previous element in the vector, as called after vector_get_at()
 894  * or vector_get_last(). The return value is NULL if there are no more
 895  * elements in the vector or if the iterator has not been set.
 896  */
 897 void * GNUNET_CONTAINER_vector_get_previous(struct GNUNET_CONTAINER_Vector * v);
 898
 899 /**
 900  * Delete and return the element at given index. NULL is returned if index is
 901  * out of bounds.
 902  */
 903 void * GNUNET_CONTAINER_vector_remove_at(struct GNUNET_CONTAINER_Vector *v,
 904                       unsigned int index);
 905
 906 /**
 907  * Delete and return the last element in the vector, or NULL if the vector
 908  * is empty.
 909  */
 910 void *GNUNET_CONTAINER_vector_remove_last (struct GNUNET_CONTAINER_Vector *v);
 911
 912 /**
 913  * Delete and return given object from the vector, or return NULL if the object
 914  * is not found.
 915  */
 916 void * GNUNET_CONTAINER_vector_remove_object(struct GNUNET_CONTAINER_Vector *v, void *object);
 917
 918 /**
 919  * Set the given index in the vector. The old value of the index is
 920  * returned, or NULL if the index is out of bounds.
 921  */
 922 void *GNUNET_CONTAINER_vector_set_at (struct GNUNET_CONTAINER_Vector *v,
 923                    void *object,
 924                    unsigned int index);
 925
 926 /**
 927  * Set the index occupied by the given object to point to the new object.
 928  * The old object is returned, or NULL if it's not found.
 929  */
 930 void *GNUNET_CONTAINER_vector_set_object(struct GNUNET_CONTAINER_Vector *v,
 931                       void *object,
 932                       void *oldObject);
 933
 934 /**
 935  * Swaps the contents of index1 and index2. Return value is OK
 936  * on success, SYSERR if either index is out of bounds.
 937  */
 938 int GNUNET_CONTAINER_vector_swap(struct GNUNET_CONTAINER_Vector *v,
 939                unsigned int index1,
 940                unsigned int index2);
 941
 942 /**
 943  * Return the index of given element or -1 if the element is not found.
 944  */
 945 unsigned int GNUNET_CONTAINER_vector_index_of(struct GNUNET_CONTAINER_Vector *v,
 946                            void *object);
 947
 948 /*
 949  * Return the data stored in the vector as a single dynamically allocated
 950  * array of (void *), which must be free(3)d by the user. Use the functions
 951  * get_{at,first,last,next,previous} instead, unless you really need to access
 952  * everything in the vector as fast as possible.
 953  */
 954 void ** GNUNET_CONTAINER_vector_elements (struct GNUNET_CONTAINER_Vector *v);
 955
 956
 957 #if 0                           /* keep Emacsens' auto-indent happy */
 958 {
 959 #endif
 960 #ifdef __cplusplus
 961 }
 962 #endif
 963
 964
 965 /* ifndef GNUNET_CONTAINER_LIB_H */
 966 #endif
 967 /* end of gnunet_container_lib.h */