src/include/gnunet_container_lib.h

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2001, 2002, 2003, 2004, 2005, 2006, 2008, 2009 Christian Grothoff (and other contributing authors)
   4
   5      GNUnet is free software; you can redistribute it and/or modify
   6      it under the terms of the GNU General Public License as published
   7      by the Free Software Foundation; either version 2, or (at your
   8      option) any later version.
   9
  10      GNUnet is distributed in the hope that it will be useful, but
  11      WITHOUT ANY WARRANTY; without even the implied warranty of
  12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13      General Public License for more details.
  14
  15      You should have received a copy of the GNU General Public License
  16      along with GNUnet; see the file COPYING.  If not, write to the
  17      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18      Boston, MA 02111-1307, USA.
  19 */
  20
  21 /**
  22  * @file include/gnunet_container_lib.h
  23  * @brief container classes for GNUnet
  24  *
  25  * @author Christian Grothoff
  26  * @author Nils Durner
  27  */
  28
  29 #ifndef GNUNET_CONTAINER_LIB_H
  30 #define GNUNET_CONTAINER_LIB_H
  31
  32 /* add error and config prototypes */
  33 #include "gnunet_crypto_lib.h"
  34 #include <extractor.h>
  35
  36 #ifdef __cplusplus
  37 extern "C"
  38 {
  39 #if 0                           /* keep Emacsens' auto-indent happy */
  40 }
  41 #endif
  42 #endif
  43
  44
  45 /* ******************* bloomfilter ***************** */
  46
  47 /**
  48  * @brief bloomfilter representation (opaque)
  49  */
  50 struct GNUNET_CONTAINER_BloomFilter;
  51
  52 /**
  53  * Iterator over HashCodes.
  54  *
  55  * @param cls closure
  56  * @param next set to the next hash code
  57  * @return GNUNET_YES if next was updated
  58  *         GNUNET_NO if there are no more entries
  59  */
  60 typedef int (*GNUNET_HashCodeIterator) (void *cls,
  61                                         GNUNET_HashCode * next);
  62
  63 /**
  64  * Load a bloom-filter from a file.
  65  *
  66  * @param filename the name of the file (or the prefix)
  67  * @param size the size of the bloom-filter (number of
  68  *        bytes of storage space to use)
  69  * @param k the number of GNUNET_CRYPTO_hash-functions to apply per
  70  *        element (number of bits set per element in the set)
  71  * @return the bloomfilter
  72  */
  73 struct GNUNET_CONTAINER_BloomFilter *
  74 GNUNET_CONTAINER_bloomfilter_load (const
  75                                    char
  76                                    *filename,
  77                                    size_t
  78                                    size,
  79                                    unsigned
  80                                    int
  81                                    k);
  82
  83 /**
  84  * Create a bloom filter from raw bits.
  85  *
  86  * @param data the raw bits in memory (maybe NULL,
  87  *        in which case all bits should be considered
  88  *        to be zero).
  89  * @param size the size of the bloom-filter (number of
  90  *        bytes of storage space to use); also size of data
  91  *        -- unless data is NULL.  Must be a power of 2.
  92  * @param k the number of GNUNET_CRYPTO_hash-functions to apply per
  93  *        element (number of bits set per element in the set)
  94  * @return the bloomfilter
  95  */
  96 struct GNUNET_CONTAINER_BloomFilter *
  97 GNUNET_CONTAINER_bloomfilter_init (const
  98                                    char
  99                                    *data,
 100                                    size_t
 101                                    size,
 102                                    unsigned
 103                                    int
 104                                    k);
 105
 106 /**
 107  * Copy the raw data of this bloomfilter into
 108  * the given data array.
 109  *
 110  * @param data where to write the data
 111  * @param size the size of the given data array
 112  * @return GNUNET_SYSERR if the data array of the wrong size
 113  */
 114 int GNUNET_CONTAINER_bloomfilter_get_raw_data (struct
 115                                                GNUNET_CONTAINER_BloomFilter
 116                                                *bf, char *data,
 117                                                size_t size);
 118
 119 /**
 120  * Test if an element is in the filter.
 121  * @param e the element
 122  * @param bf the filter
 123  * @return GNUNET_YES if the element is in the filter, GNUNET_NO if not
 124  */
 125 int GNUNET_CONTAINER_bloomfilter_test (struct GNUNET_CONTAINER_BloomFilter
 126                                        *bf, const GNUNET_HashCode * e);
 127
 128 /**
 129  * Add an element to the filter
 130  * @param bf the filter
 131  * @param e the element
 132  */
 133 void GNUNET_CONTAINER_bloomfilter_add (struct GNUNET_CONTAINER_BloomFilter
 134                                        *bf, const GNUNET_HashCode * e);
 135
 136 /**
 137  * Remove an element from the filter.
 138  * @param bf the filter
 139  * @param e the element to remove
 140  */
 141 void GNUNET_CONTAINER_bloomfilter_remove (struct GNUNET_CONTAINER_BloomFilter
 142                                           *bf, const GNUNET_HashCode * e);
 143
 144 /**
 145  * Free the space associcated with a filter
 146  * in memory, flush to drive if needed (do not
 147  * free the space on the drive)
 148  * @param bf the filter
 149  */
 150 void GNUNET_CONTAINER_bloomfilter_free (struct GNUNET_CONTAINER_BloomFilter
 151                                         *bf);
 152
 153 /**
 154  * Reset a bloom filter to empty.
 155  * @param bf the filter
 156  */
 157 void GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter
 158                                          *bf);
 159
 160 /**
 161  * Or the entries of the given raw data array with the
 162  * data of the given bloom filter.  Assumes that
 163  * the size of the data array and the current filter
 164  * match.
 165  *
 166  * @param bf the filter
 167  * @param data data to OR-in
 168  * @param size size of data
 169  * @return GNUNET_OK on success
 170  */
 171 int GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf,
 172                                      const char *data, size_t size);
 173
 174 /**
 175  * Resize a bloom filter.  Note that this operation
 176  * is pretty costly.  Essentially, the bloom filter
 177  * needs to be completely re-build.
 178  *
 179  * @param bf the filter
 180  * @param iterator an iterator over all elements stored in the BF
 181  * @param iterator_cls closure for iterator
 182  * @param size the new size for the filter
 183  * @param k the new number of GNUNET_CRYPTO_hash-function to apply per element
 184  */
 185 void GNUNET_CONTAINER_bloomfilter_resize (struct GNUNET_CONTAINER_BloomFilter
 186                                           *bf,
 187                                           GNUNET_HashCodeIterator iterator,
 188                                           void *iterator_cls,
 189                                           size_t size, unsigned int k);
 190
 191 /* ****************** metadata ******************* */
 192
 193 /**
 194  * Meta data to associate with a file, directory or namespace.
 195  */
 196 struct GNUNET_CONTAINER_MetaData;
 197
 198 /**
 199  * Iterator over meta data.
 200  *
 201  * @param cls closure
 202  * @param type type of the meta data
 203  * @param data value of the meta data
 204  * @return GNUNET_OK to continue to iterate, GNUNET_SYSERR to abort
 205  */
 206 typedef int (*GNUNET_CONTAINER_MetaDataProcessor) (void *cls,
 207                                                    EXTRACTOR_KeywordType type,
 208                                                    const char *data);
 209
 210 /**
 211  * Create a fresh MetaData token.
 212  *
 213  * @return empty meta-data container
 214  */
 215 struct GNUNET_CONTAINER_MetaData *GNUNET_CONTAINER_meta_data_create (void);
 216
 217 /**
 218  * Duplicate a MetaData token.
 219  *
 220  * @param md what to duplicate
 221  * @return duplicate meta-data container
 222  */
 223 struct GNUNET_CONTAINER_MetaData *GNUNET_CONTAINER_meta_data_duplicate (const
 224                                                                         struct
 225                                                                         GNUNET_CONTAINER_MetaData
 226                                                                         *md);
 227
 228 /**
 229  * Free meta data.
 230  *
 231  * @param md what to free
 232  */
 233 void GNUNET_CONTAINER_meta_data_destroy (struct GNUNET_CONTAINER_MetaData
 234                                          *md);
 235
 236 /**
 237  * Test if two MDs are equal.
 238  *
 239  * @param md1 first value to check
 240  * @param md2 other value to check
 241  * @return GNUNET_YES if they are equal
 242  */
 243 int GNUNET_CONTAINER_meta_data_test_equal (const struct
 244                                            GNUNET_CONTAINER_MetaData *md1,
 245                                            const struct
 246                                            GNUNET_CONTAINER_MetaData *md2);
 247
 248
 249 /**
 250  * Extend metadata.
 251  *
 252  * @param md metadata to extend
 253  * @param type type of the new entry
 254  * @param data value for the entry
 255  * @return GNUNET_OK on success, GNUNET_SYSERR if this entry already exists
 256  */
 257 int GNUNET_CONTAINER_meta_data_insert (struct GNUNET_CONTAINER_MetaData *md,
 258                                        EXTRACTOR_KeywordType type,
 259                                        const char *data);
 260
 261 /**
 262  * Remove an item.
 263  *
 264  * @param md metadata to manipulate
 265  * @param type type of the item to remove
 266  * @param data specific value to remove, NULL to remove all
 267  *        entries of the given type
 268  * @return GNUNET_OK on success, GNUNET_SYSERR if the item does not exist in md
 269  */
 270 int GNUNET_CONTAINER_meta_data_delete (struct GNUNET_CONTAINER_MetaData *md,
 271                                        EXTRACTOR_KeywordType type,
 272                                        const char *data);
 273
 274 /**
 275  * Add the current time as the publication date
 276  * to the meta-data.
 277  *
 278  * @param md metadata to modify
 279  */
 280 void GNUNET_CONTAINER_meta_data_add_publication_date (struct
 281                                                       GNUNET_CONTAINER_MetaData
 282                                                       *md);
 283
 284 /**
 285  * Iterate over MD entries, excluding thumbnails.
 286  *
 287  * @param md metadata to inspect
 288  * @param iter function to call on each entry
 289  * @param iter_cls closure for iterator
 290  * @return number of entries
 291  */
 292 int GNUNET_CONTAINER_meta_data_get_contents (const struct
 293                                              GNUNET_CONTAINER_MetaData *md,
 294                                              GNUNET_CONTAINER_MetaDataProcessor
 295                                              iter, void *iter_cls);
 296
 297 /**
 298  * Get the first MD entry of the given type.
 299  *
 300  * @param md metadata to inspect
 301  * @param type type to look for
 302  * @return NULL if we do not have any such entry,
 303  *  otherwise client is responsible for freeing the value!
 304  */
 305 char *GNUNET_CONTAINER_meta_data_get_by_type (const struct
 306                                              GNUNET_CONTAINER_MetaData *md,
 307                                               EXTRACTOR_KeywordType type);
 308
 309 /**
 310  * Get the first matching MD entry of the given types.
 311  *
 312  * @param md metadata to inspect
 313  * @param ... -1-terminated list of types
 314  * @return NULL if we do not have any such entry,
 315  *  otherwise client is responsible for freeing the value!
 316  */
 317 char *GNUNET_CONTAINER_meta_data_get_first_by_types (const struct
 318                                                      GNUNET_CONTAINER_MetaData
 319                                                      *md, ...);
 320
 321 /**
 322  * Get a thumbnail from the meta-data (if present).
 323  *
 324  * @param md metadata to inspect
 325  * @param thumb will be set to the thumbnail data.  Must be
 326  *        freed by the caller!
 327  * @return number of bytes in thumbnail, 0 if not available
 328  */
 329 size_t GNUNET_CONTAINER_meta_data_get_thumbnail (const struct
 330                                                  GNUNET_CONTAINER_MetaData
 331                                                  *md, unsigned char **thumb);
 332
 333 /**
 334  * Extract meta-data from a file.
 335  *
 336  * @param md metadata to set
 337  * @param filename name of file to inspect
 338  * @param extractors plugins to use
 339  * @return GNUNET_SYSERR on error, otherwise the number
 340  *   of meta-data items obtained
 341  */
 342 int GNUNET_CONTAINER_meta_data_extract_from_file (struct
 343                                                   GNUNET_CONTAINER_MetaData
 344                                                   *md, const char *filename,
 345                                                   EXTRACTOR_ExtractorList *
 346                                                   extractors);
 347
 348
 349 /**
 350  * Options for metadata serialization.
 351  */
 352 enum GNUNET_CONTAINER_MetaDataSerializationOptions
 353 {
 354   /**
 355    * Serialize all of the data.
 356    */
 357   GNUNET_CONTAINER_META_DATA_SERIALIZE_FULL = 0,
 358
 359   /**
 360    * If not enough space is available, it is acceptable
 361    * to only serialize some of the metadata.
 362    */
 363   GNUNET_CONTAINER_META_DATA_SERIALIZE_PART = 1,
 364
 365   /**
 366    * Speed is of the essence, do not allow compression.
 367    */
 368   GNUNET_CONTAINER_META_DATA_SERIALIZE_NO_COMPRESS = 2
 369 };
 370
 371
 372 /**
 373  * Serialize meta-data to target.
 374  *
 375  * @param md metadata to serialize
 376  * @param target where to write the serialized metadata
 377  * @param max maximum number of bytes available
 378  * @param opt is it ok to just write SOME of the
 379  *        meta-data to match the size constraint,
 380  *        possibly discarding some data?
 381  * @return number of bytes written on success,
 382  *         -1 on error (typically: not enough
 383  *         space)
 384  */
 385 ssize_t GNUNET_CONTAINER_meta_data_serialize (const struct
 386                                               GNUNET_CONTAINER_MetaData *md,
 387                                               char *target,
 388                                               size_t max,
 389                                               enum
 390                                           GNUNET_CONTAINER_MetaDataSerializationOptions
 391                                           opt);
 392
 393
 394 /**
 395  * Estimate (!) the size of the meta-data in
 396  * serialized form.  The estimate MAY be higher
 397  * than what is strictly needed.
 398  *
 399  * @param md metadata to inspect
 400  * @param opt is it ok to just write SOME of the
 401  *        meta-data to match the size constraint,
 402  *        possibly discarding some data?
 403  * @return number of bytes needed for serialization, -1 on error
 404  */
 405 ssize_t GNUNET_CONTAINER_meta_data_get_serialized_size (const struct
 406                                                         GNUNET_CONTAINER_MetaData
 407                                                         *md,
 408                                                         enum
 409                                                         GNUNET_CONTAINER_MetaDataSerializationOptions
 410                                                         opt);
 411
 412 /**
 413  * Deserialize meta-data.  Initializes md.
 414  *
 415  * @param input serialized meta-data.
 416  * @param size number of bytes available
 417  * @return MD on success, NULL on error (i.e.
 418  *         bad format)
 419  */
 420 struct GNUNET_CONTAINER_MetaData
 421   *GNUNET_CONTAINER_meta_data_deserialize (const char *input,
 422                                            size_t size);
 423
 424 /**
 425  * Does the meta-data claim that this is a directory?
 426  * Checks if the mime-type is that of a GNUnet directory.
 427  *
 428  * @param md metadata to inspect
 429  * @return GNUNET_YES if it is, GNUNET_NO if it is not, GNUNET_SYSERR if
 430  *  we have no mime-type information (treat as 'GNUNET_NO')
 431  */
 432 int GNUNET_CONTAINER_meta_data_test_for_directory (const struct
 433                                                    GNUNET_CONTAINER_MetaData
 434                                                    *md);
 435
 436
 437 /* ******************************* HashMap **************************** */
 438
 439 /**
 440  * Opaque handle for a HashMap.
 441  */
 442 struct GNUNET_CONTAINER_MultiHashMap;
 443
 444 /**
 445  * Options for storing values in the HashMap.
 446  */
 447 enum GNUNET_CONTAINER_MultiHashMapOption
 448 {
 449
 450   /**
 451    * If a value with the given key exists, replace it.  Note that the
 452    * old value would NOT be freed by replace (the application has to
 453    * make sure that this happens if required).
 454    */
 455   GNUNET_CONTAINER_MULTIHASHMAPOPTION_REPLACE,
 456
 457   /**
 458    * Allow multiple values with the same key.
 459    */
 460   GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE,
 461
 462   /**
 463    * There must only be one value per key; storing a value should fail
 464    * if a value under the same key already exists.
 465    */
 466   GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY,
 467
 468   /**
 469    * There must only be one value per key, but don't bother checking
 470    * if a value already exists (faster than UNIQUE_ONLY; implemented
 471    * just like MULTIPLE but this option documents better what is
 472    * intended if UNIQUE is what is desired).
 473    */
 474   GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST
 475 };
 476
 477
 478 /**
 479  * Iterator over HashCodes.
 480  *
 481  * @param cls closure
 482  * @param key current key code
 483  * @param value value in the hash map
 484  * @return GNUNET_YES if we should continue to
 485  *         iterate,
 486  *         GNUNET_NO if not.
 487  */
 488 typedef int (*GNUNET_CONTAINER_HashMapIterator) (void *cls,
 489                                                  const GNUNET_HashCode * key,
 490                                                  void *value);
 491
 492
 493 /**
 494  * Create a multi hash map.
 495  *
 496  * @param len initial size (map will grow as needed)
 497  * @return NULL on error
 498  */
 499 struct GNUNET_CONTAINER_MultiHashMap
 500   *GNUNET_CONTAINER_multihashmap_create (unsigned int len);
 501
 502
 503 /**
 504  * Destroy a hash map.  Will not free any values
 505  * stored in the hash map!
 506  *
 507  * @param map the map
 508  */
 509 void GNUNET_CONTAINER_multihashmap_destroy (struct
 510                                             GNUNET_CONTAINER_MultiHashMap
 511                                             *map);
 512
 513
 514 /**
 515  * Given a key find a value in the map matching the key.
 516  *
 517  * @param map the map
 518  * @param key what to look for
 519  * @return NULL if no value was found; note that
 520  *   this is indistinguishable from values that just
 521  *   happen to be NULL; use "contains" to test for
 522  *   key-value pairs with value NULL
 523  */
 524 void *GNUNET_CONTAINER_multihashmap_get (const struct
 525                                          GNUNET_CONTAINER_MultiHashMap *map,
 526                                          const GNUNET_HashCode * key);
 527
 528
 529 /**
 530  * Remove the given key-value pair from the map.  Note that if the
 531  * key-value pair is in the map multiple times, only one of the pairs
 532  * will be removed.
 533  *
 534  * @param map the map
 535  * @param key key of the key-value pair
 536  * @param value value of the key-value pair
 537  * @return GNUNET_YES on success, GNUNET_NO if the key-value pair
 538  *  is not in the map
 539  */
 540 int GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap
 541                                           *map, const GNUNET_HashCode * key,
 542                                           void *value);
 543
 544 /**
 545  * Remove all entries for the given key from the map.
 546  * Note that the values would not be "freed".
 547  *
 548  * @param map the map
 549  * @param key identifies values to be removed
 550  * @return number of values removed
 551  */
 552 int GNUNET_CONTAINER_multihashmap_remove_all (struct
 553                                               GNUNET_CONTAINER_MultiHashMap
 554                                               *map,
 555                                               const GNUNET_HashCode * key);
 556
 557
 558 /**
 559  * Check if the map contains any value under the given
 560  * key (including values that are NULL).
 561  *
 562  * @param map the map
 563  * @param key the key to test if a value exists for it
 564  * @return GNUNET_YES if such a value exists,
 565  *         GNUNET_NO if not
 566  */
 567 int GNUNET_CONTAINER_multihashmap_contains (const struct
 568                                             GNUNET_CONTAINER_MultiHashMap
 569                                             *map,
 570                                             const GNUNET_HashCode * key);
 571
 572
 573 /**
 574  * Store a key-value pair in the map.
 575  *
 576  * @param map the map
 577  * @param key key to use
 578  * @param value value to use
 579  * @param opt options for put
 580  * @return GNUNET_OK on success,
 581  *         GNUNET_NO if a value was replaced (with REPLACE)
 582  *         GNUNET_SYSERR if UNIQUE_ONLY was the option and the
 583  *                       value already exists
 584  */
 585 int GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap
 586                                        *map, const GNUNET_HashCode * key,
 587                                        void *value,
 588                                        enum
 589                                        GNUNET_CONTAINER_MultiHashMapOption
 590                                        opt);
 591
 592 /**
 593  * Get the number of key-value pairs in the map.
 594  *
 595  * @param map the map
 596  * @return the number of key value pairs
 597  */
 598 unsigned int GNUNET_CONTAINER_multihashmap_size (const struct
 599                                                  GNUNET_CONTAINER_MultiHashMap
 600                                                  *map);
 601
 602
 603 /**
 604  * Iterate over all entries in the map.
 605  *
 606  * @param map the map
 607  * @param it function to call on each entry
 608  * @param it_cls extra argument to it
 609  * @return the number of key value pairs processed,
 610  *         GNUNET_SYSERR if it aborted iteration
 611  */
 612 int GNUNET_CONTAINER_multihashmap_iterate (const struct
 613                                            GNUNET_CONTAINER_MultiHashMap *map,
 614                                            GNUNET_CONTAINER_HashMapIterator
 615                                            it, void *it_cls);
 616
 617
 618 /**
 619  * Iterate over all entries in the map that match a particular key.
 620  *
 621  * @param map the map
 622  * @param key key that the entries must correspond to
 623  * @param it function to call on each entry
 624  * @param it_cls extra argument to it
 625  * @return the number of key value pairs processed,
 626  *         GNUNET_SYSERR if it aborted iteration
 627  */
 628 int GNUNET_CONTAINER_multihashmap_get_multiple (const struct
 629                                                 GNUNET_CONTAINER_MultiHashMap
 630                                                 *map,
 631                                                 const GNUNET_HashCode * key,
 632                                                 GNUNET_CONTAINER_HashMapIterator
 633                                                 it, void *it_cls);
 634
 635
 636 /* ******************** doubly-linked list *************** */
 637
 638 /**
 639  * Insert an element into a DLL. Assumes
 640  * that head, tail and element are structs
 641  * with prev and next fields.
 642  *
 643  * @param head pointer to the head of the DLL
 644  * @param tail pointer to the tail of the DLL
 645  * @param element element to insert
 646  */
 647 #define GNUNET_CONTAINER_DLL_insert(head,tail,element) \
 648   (element)->next = (head); \
 649   (element)->prev = NULL; \
 650   if ((tail) == NULL) \
 651     (tail) = element; \
 652   else \
 653     (head)->prev = element; \
 654   (head) = (element);
 655
 656 /**
 657  * Insert an element into a DLL after the given other
 658  * element.  Insert at the head if the other
 659  * element is NULL.
 660  *
 661  * @param head pointer to the head of the DLL
 662  * @param tail pointer to the tail of the DLL
 663  * @param other prior element, NULL for insertion at head of DLL
 664  * @param element element to insert
 665  */
 666 #define GNUNET_CONTAINER_DLL_insert_after(head,tail,other,element) \
 667   (element)->prev = (other); \
 668   if (NULL == other) \
 669     { \
 670       (element)->next = (head); \
 671       (head) = (element); \
 672     } \
 673   else \
 674     { \
 675       (element)->next = (other)->next; \
 676       (other)->next = (element); \
 677     } \
 678   if (NULL == (element)->next) \
 679     (tail) = (element); \
 680   else \
 681     (element)->next->prev = (element);
 682
 683
 684
 685
 686 /**
 687  * Remove an element from a DLL. Assumes
 688  * that head, tail and element are structs
 689  * with prev and next fields.
 690  *
 691  * @param head pointer to the head of the DLL
 692  * @param tail pointer to the tail of the DLL
 693  * @param element element to remove
 694  */
 695 #define GNUNET_CONTAINER_DLL_remove(head,tail,element) \
 696   if ((element)->prev == NULL) \
 697     (head) = (element)->next;  \
 698   else \
 699     (element)->prev->next = (element)->next; \
 700   if ((element)->next == NULL) \
 701     (tail) = (element)->prev;  \
 702   else \
 703     (element)->next->prev = (element)->prev;
 704
 705
 706
 707 /* ******************** Heap *************** */
 708
 709
 710 /**
 711  * Cost by which elements in a heap can be ordered.
 712  */
 713 typedef uint64_t GNUNET_CONTAINER_HeapCostType;
 714
 715
 716 /*
 717  * Heap type, either max or min.  Hopefully makes the
 718  * implementation more useful.
 719  */
 720 enum GNUNET_CONTAINER_HeapOrder
 721 {
 722   /**
 723    * Heap with the maximum cost at the root.
 724    */
 725   GNUNET_CONTAINER_HEAP_ORDER_MAX,
 726
 727   /**
 728    * Heap with the minimum cost at the root.
 729    */
 730   GNUNET_CONTAINER_HEAP_ORDER_MIN
 731 };
 732
 733
 734 /**
 735  * Handle to a Heap.
 736  */
 737 struct GNUNET_CONTAINER_Heap;
 738
 739
 740
 741 /**
 742  * Handle to a node in a heap.
 743  */
 744 struct GNUNET_CONTAINER_HeapNode;
 745
 746
 747 /**
 748  * Create a new heap.
 749  *
 750  * @param order how should the heap be sorted?
 751  * @return handle to the heap
 752  */
 753 struct GNUNET_CONTAINER_Heap *
 754 GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order);
 755
 756
 757 /**
 758  * Destroys the heap.  Only call on a heap that
 759  * is already empty.
 760  *
 761  * @param heap heap to destroy
 762  */
 763 void GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap);
 764
 765
 766 /**
 767  * Get element stored at root of heap.
 768  *
 769  * @param heap heap to inspect
 770  * @return NULL if heap is empty
 771  */
 772 void *
 773 GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap);
 774
 775
 776 /**
 777  * Get the current size of the heap
 778  *
 779  * @param heap the heap to get the size of
 780  * @return number of elements stored
 781  */
 782 unsigned int
 783 GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap);
 784
 785
 786 /**
 787  * Iterator for heap
 788  *
 789  * @param cls closure
 790  * @param node internal node of the heap
 791  * @param element value stored at the node
 792  * @param cost cost associated with the node
 793  * @return GNUNET_YES if we should continue to iterate,
 794  *         GNUNET_NO if not.
 795  */
 796 typedef int (*GNUNET_CONTAINER_HeapIterator) (void *cls,
 797                                               struct GNUNET_CONTAINER_HeapNode *node,
 798                                               void *element,
 799                                               GNUNET_CONTAINER_HeapCostType cost);
 800
 801
 802 /**
 803  * Iterate over all entries in the heap.
 804  *
 805  * @param heap the heap
 806  * @param iterator function to call on each entry
 807  * @param iterator_cls closure for iterator
 808  */
 809 void
 810 GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
 811                                GNUNET_CONTAINER_HeapIterator iterator,
 812                                void *iterator_cls);
 813
 814
 815 /**
 816  * Perform a random walk of the tree.  The walk is biased
 817  * towards elements closer to the root of the tree (since
 818  * each walk starts at the root and ends at a random leaf).
 819  * The heap internally tracks the current position of the
 820  * walk.
 821  *
 822  * @param heap heap to walk
 823  * @return data stored at the next random node in the walk;
 824  *         NULL if the tree is empty.
 825  */
 826 void *
 827 GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap);
 828
 829
 830 /**
 831  * Inserts a new element into the heap.
 832  *
 833  * @param heap heap to modify
 834  * @param element element to insert
 835  * @param cost cost for the element
 836  * @return node for the new element
 837  */
 838 struct GNUNET_CONTAINER_HeapNode *
 839 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap,
 840                               void *element,
 841                               GNUNET_CONTAINER_HeapCostType cost);
 842
 843
 844 /**
 845  * Remove root of the heap.
 846  *
 847  * @param heap heap to modify
 848  * @return element data stored at the root node
 849  */
 850 void *
 851 GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap);
 852
 853
 854 /**
 855  * Removes a node from the heap.
 856  *
 857  * @param heap heap to modify
 858  * @param node node to remove
 859  * @return element data stored at the node, NULL if heap is empty
 860  */
 861 void *
 862 GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *heap,
 863                                    struct GNUNET_CONTAINER_HeapNode *node);
 864
 865
 866 /**
 867  * Updates the cost of any node in the tree
 868  *
 869  * @param heap heap to modify
 870  * @param node node for which the cost is to be changed
 871  * @param new_cost new cost for the node
 872  */
 873 void
 874 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
 875                                    struct GNUNET_CONTAINER_HeapNode *node,
 876                                    GNUNET_CONTAINER_HeapCostType new_cost);
 877
 878
 879 /* ******************** Singly linked list *************** */
 880
 881 /**
 882  * Possible ways for how data stored in the linked list
 883  * might be allocated.
 884  */
 885 enum GNUNET_CONTAINER_SListDisposition
 886   {
 887     /**
 888      * Single-linked list must copy the buffer.
 889      */
 890     GNUNET_CONTAINER_SLIST_DISPOSITION_TRANSIENT = 0,
 891
 892     /**
 893      * Data is static, no need to copy or free.
 894      */
 895     GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC = 2,
 896
 897     /**
 898      * Data is dynamic, do not copy but free when done.
 899      */
 900     GNUNET_CONTAINER_SLIST_DISPOSITION_DYNAMIC = 4
 901   };
 902
 903
 904
 905 /**
 906  * Handle to a singly linked list
 907  */
 908 struct GNUNET_CONTAINER_SList;
 909
 910 /**
 911  * Handle to a singly linked list iterator
 912  */
 913 struct GNUNET_CONTAINER_SList_Iterator;
 914
 915
 916 /**
 917  * Add a new element to the list
 918  * @param l list
 919  * @param disp memory disposition
 920  * @param buf payload buffer
 921  * @param len length of the buffer
 922  */
 923 void GNUNET_CONTAINER_slist_add (struct GNUNET_CONTAINER_SList *l,
 924                                  enum GNUNET_CONTAINER_SListDisposition disp,
 925                                  const void *buf, size_t len);
 926
 927
 928 /**
 929  * Append a singly linked list to another
 930  * @param dst list to append to
 931  * @param src source
 932  */
 933 void
 934 GNUNET_CONTAINER_slist_append (struct GNUNET_CONTAINER_SList *dst, struct GNUNET_CONTAINER_SList *src);
 935
 936
 937 /**
 938  * Create a new singly linked list
 939  * @return the new list
 940  */
 941 struct GNUNET_CONTAINER_SList *GNUNET_CONTAINER_slist_create (void);
 942
 943
 944 /**
 945  * Destroy a singly linked list
 946  * @param l the list to be destroyed
 947  */
 948 void GNUNET_CONTAINER_slist_destroy (struct GNUNET_CONTAINER_SList *l);
 949
 950
 951 /**
 952  * Return the beginning of a list
 953  *
 954  * @param l list
 955  * @return iterator pointing to the beginning, free using "GNUNET_free"
 956  */
 957 struct GNUNET_CONTAINER_SList_Iterator *
 958 GNUNET_CONTAINER_slist_begin(struct GNUNET_CONTAINER_SList *l);
 959
 960
 961 /**
 962  * Clear a list
 963  *
 964  * @param l list
 965  */
 966 void GNUNET_CONTAINER_slist_clear (struct GNUNET_CONTAINER_SList *l);
 967
 968
 969 /**
 970  * Check if a list contains a certain element
 971  * @param l list
 972  * @param buf payload buffer to find
 973  * @param len length of the payload (number of bytes in buf)
 974  */
 975 int GNUNET_CONTAINER_slist_contains (const struct GNUNET_CONTAINER_SList *l, const void *buf, size_t len);
 976
 977
 978 /**
 979  * Count the elements of a list
 980  * @param l list
 981  * @return number of elements in the list
 982  */
 983 int GNUNET_CONTAINER_slist_count (const struct GNUNET_CONTAINER_SList *l);
 984
 985
 986 /**
 987  * Remove an element from the list
 988  * @param i iterator that points to the element to be removed
 989  */
 990 void GNUNET_CONTAINER_slist_erase (struct GNUNET_CONTAINER_SList_Iterator *i);
 991
 992
 993 /**
 994  * Insert an element into a list at a specific position
 995  * @param before where to insert the new element
 996  * @param disp memory disposition
 997  * @param buf payload buffer
 998  * @param len length of the payload
 999  */
1000 void GNUNET_CONTAINER_slist_insert (struct GNUNET_CONTAINER_SList_Iterator *before,
1001                                     enum GNUNET_CONTAINER_SListDisposition disp,
1002                                     const void *buf,
1003                                     size_t len);
1004
1005
1006 /**
1007  * Advance an iterator to the next element
1008  * @param i iterator
1009  * @return GNUNET_YES on success, GNUNET_NO if the end has been reached
1010  */
1011 int GNUNET_CONTAINER_slist_next (struct GNUNET_CONTAINER_SList_Iterator *i);
1012
1013
1014 /**
1015  * Check if an iterator points beyond the end of a list
1016  * @param i iterator
1017  * @return GNUNET_YES if the end has been reached, GNUNET_NO if the iterator
1018  *         points to a valid element
1019  */
1020 int GNUNET_CONTAINER_slist_end (struct GNUNET_CONTAINER_SList_Iterator *i);
1021
1022
1023 /**
1024  * Retrieve the element at a specific position in a list
1025  *
1026  * @param i iterator
1027  * @param len set to the payload length
1028  * @return payload
1029  */
1030 const void *
1031 GNUNET_CONTAINER_slist_get (const struct GNUNET_CONTAINER_SList_Iterator *i,
1032                             size_t *len);
1033
1034
1035 /**
1036  * Release an iterator
1037  * @param i iterator
1038  */
1039 void GNUNET_CONTAINER_slist_iter_destroy (struct GNUNET_CONTAINER_SList_Iterator *i);
1040
1041
1042 #if 0                           /* keep Emacsens' auto-indent happy */
1043 {
1044 #endif
1045 #ifdef __cplusplus
1046 }
1047 #endif
1048
1049
1050 /* ifndef GNUNET_CONTAINER_LIB_H */
1051 #endif
1052 /* end of gnunet_container_lib.h */