src/include/gnunet_container_lib.h

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2001, 2002, 2003, 2004, 2005, 2006, 2008, 2009, 2010 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 (const 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 (const 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 /**
 155  * Get size of the bloom filter.
 156  *
 157  * @param bf the filter
 158  * @return number of bytes used for the data of the bloom filter
 159  */
 160 size_t
 161 GNUNET_CONTAINER_bloomfilter_get_size (const struct GNUNET_CONTAINER_BloomFilter
 162                                        *bf);
 163
 164
 165 /**
 166  * Reset a bloom filter to empty.
 167  * @param bf the filter
 168  */
 169 void GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter
 170                                          *bf);
 171
 172 /**
 173  * Or the entries of the given raw data array with the
 174  * data of the given bloom filter.  Assumes that
 175  * the size of the data array and the current filter
 176  * match.
 177  *
 178  * @param bf the filter
 179  * @param data data to OR-in
 180  * @param size size of data
 181  * @return GNUNET_OK on success
 182  */
 183 int GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf,
 184                                      const char *data, size_t size);
 185
 186 /**
 187  * Or the entries of the given raw data array with the
 188  * data of the given bloom filter.  Assumes that
 189  * the size of the data array and the current filter
 190  * match.
 191  *
 192  * @param bf the filter
 193  * @param to_or the bloomfilter to or-in
 194  * @param size number of bytes in data
 195  */
 196 int
 197 GNUNET_CONTAINER_bloomfilter_or2 (struct GNUNET_CONTAINER_BloomFilter *bf,
 198                                   const struct GNUNET_CONTAINER_BloomFilter *to_or,
 199                                   size_t size);
 200
 201 /**
 202  * Resize a bloom filter.  Note that this operation
 203  * is pretty costly.  Essentially, the bloom filter
 204  * needs to be completely re-build.
 205  *
 206  * @param bf the filter
 207  * @param iterator an iterator over all elements stored in the BF
 208  * @param iterator_cls closure for iterator
 209  * @param size the new size for the filter
 210  * @param k the new number of GNUNET_CRYPTO_hash-function to apply per element
 211  */
 212 void GNUNET_CONTAINER_bloomfilter_resize (struct GNUNET_CONTAINER_BloomFilter
 213                                           *bf,
 214                                           GNUNET_HashCodeIterator iterator,
 215                                           void *iterator_cls,
 216                                           size_t size, unsigned int k);
 217
 218 /* ****************** metadata ******************* */
 219
 220 /**
 221  * Meta data to associate with a file, directory or namespace.
 222  */
 223 struct GNUNET_CONTAINER_MetaData;
 224
 225 /**
 226  * Create a fresh MetaData token.
 227  *
 228  * @return empty meta-data container
 229  */
 230 struct GNUNET_CONTAINER_MetaData *
 231 GNUNET_CONTAINER_meta_data_create (void);
 232
 233 /**
 234  * Duplicate a MetaData token.
 235  *
 236  * @param md what to duplicate
 237  * @return duplicate meta-data container
 238  */
 239 struct GNUNET_CONTAINER_MetaData *
 240 GNUNET_CONTAINER_meta_data_duplicate (const struct
 241                                       GNUNET_CONTAINER_MetaData *md);
 242
 243 /**
 244  * Free meta data.
 245  *
 246  * @param md what to free
 247  */
 248 void
 249 GNUNET_CONTAINER_meta_data_destroy (struct GNUNET_CONTAINER_MetaData *md);
 250
 251 /**
 252  * Test if two MDs are equal. We consider them equal if
 253  * the meta types, formats and content match (we do not
 254  * include the mime types and plugins names in this
 255  * consideration).
 256  *
 257  * @param md1 first value to check
 258  * @param md2 other value to check
 259  * @return GNUNET_YES if they are equal
 260  */
 261 int
 262 GNUNET_CONTAINER_meta_data_test_equal (const struct
 263                                        GNUNET_CONTAINER_MetaData *md1,
 264                                        const struct
 265                                        GNUNET_CONTAINER_MetaData *md2);
 266
 267
 268 /**
 269  * Extend metadata.
 270  *
 271  * @param md metadata to extend
 272  * @param plugin_name name of the plugin that produced this value;
 273  *        special values can be used (i.e. '&lt;zlib&gt;' for zlib being
 274  *        used in the main libextractor library and yielding
 275  *        meta data).
 276  * @param type libextractor-type describing the meta data
 277  * @param format basic format information about data
 278  * @param data_mime_type mime-type of data (not of the original file);
 279  *        can be NULL (if mime-type is not known)
 280  * @param data actual meta-data found
 281  * @param data_len number of bytes in data
 282  * @return GNUNET_OK on success, GNUNET_SYSERR if this entry already exists
 283  *         data_mime_type and plugin_name are not considered for "exists" checks
 284  */
 285 int
 286 GNUNET_CONTAINER_meta_data_insert (struct GNUNET_CONTAINER_MetaData *md,
 287                                    const char *plugin_name,
 288                                    enum EXTRACTOR_MetaType type,
 289                                    enum EXTRACTOR_MetaFormat format,
 290                                    const char *data_mime_type,
 291                                    const char *data,
 292                                    size_t data_len);
 293
 294
 295 /**
 296  * Extend metadata.  Merges the meta data from the second argument
 297  * into the first, discarding duplicate key-value pairs.
 298  *
 299  * @param md metadata to extend
 300  * @param in metadata to merge
 301  */
 302 void
 303 GNUNET_CONTAINER_meta_data_merge (struct GNUNET_CONTAINER_MetaData *md,
 304                                   const struct GNUNET_CONTAINER_MetaData *in);
 305
 306
 307 /**
 308  * Remove an item.
 309  *
 310  * @param md metadata to manipulate
 311  * @param type type of the item to remove
 312  * @param data specific value to remove, NULL to remove all
 313  *        entries of the given type
 314  * @param data_len number of bytes in data
 315  * @return GNUNET_OK on success, GNUNET_SYSERR if the item does not exist in md
 316  */
 317 int
 318 GNUNET_CONTAINER_meta_data_delete (struct GNUNET_CONTAINER_MetaData *md,
 319                                    enum EXTRACTOR_MetaType type,
 320                                    const char *data,
 321                                    size_t data_len);
 322
 323
 324 /**
 325  * Remove all items in the container.
 326  *
 327  * @param md metadata to manipulate
 328  */
 329 void
 330 GNUNET_CONTAINER_meta_data_clear (struct GNUNET_CONTAINER_MetaData *md);
 331
 332
 333 /**
 334  * Add the current time as the publication date
 335  * to the meta-data.
 336  *
 337  * @param md metadata to modify
 338  */
 339 void
 340 GNUNET_CONTAINER_meta_data_add_publication_date (struct
 341                                                  GNUNET_CONTAINER_MetaData
 342                                                  *md);
 343
 344
 345 /**
 346  * Iterate over MD entries.
 347  *
 348  * @param md metadata to inspect
 349  * @param iter function to call on each entry
 350  * @param iter_cls closure for iterator
 351  * @return number of entries
 352  */
 353 int GNUNET_CONTAINER_meta_data_iterate (const struct
 354                                         GNUNET_CONTAINER_MetaData *md,
 355                                         EXTRACTOR_MetaDataProcessor
 356                                         iter, void *iter_cls);
 357
 358 /**
 359  * Get the first MD entry of the given type.  Caller
 360  * is responsible for freeing the return value.
 361  * Also, only meta data items that are strings (0-terminated)
 362  * are returned by this function.
 363  *
 364  * @param md metadata to inspect
 365  * @param type type to look for
 366  * @return NULL if no entry was found
 367  */
 368 char *
 369 GNUNET_CONTAINER_meta_data_get_by_type (const struct
 370                                         GNUNET_CONTAINER_MetaData *md,
 371                                         enum EXTRACTOR_MetaType type);
 372
 373
 374 /**
 375  * Get the first matching MD entry of the given types. Caller is
 376  * responsible for freeing the return value.  Also, only meta data
 377  * items that are strings (0-terminated) are returned by this
 378  * function.
 379  *
 380  * @param md metadata to inspect
 381  * @param ... -1-terminated list of types
 382  * @return NULL if we do not have any such entry,
 383  *  otherwise client is responsible for freeing the value!
 384  */
 385 char *
 386 GNUNET_CONTAINER_meta_data_get_first_by_types (const struct
 387                                                GNUNET_CONTAINER_MetaData
 388                                                *md, ...);
 389
 390 /**
 391  * Get a thumbnail from the meta-data (if present).  Only matches meta
 392  * data with mime type "image" and binary format.
 393  *
 394  * @param md metadata to inspect
 395  * @param thumb will be set to the thumbnail data.  Must be
 396  *        freed by the caller!
 397  * @return number of bytes in thumbnail, 0 if not available
 398  */
 399 size_t
 400 GNUNET_CONTAINER_meta_data_get_thumbnail (const struct
 401                                           GNUNET_CONTAINER_MetaData
 402                                           *md, unsigned char **thumb);
 403
 404
 405
 406 /**
 407  * Options for metadata serialization.
 408  */
 409 enum GNUNET_CONTAINER_MetaDataSerializationOptions
 410 {
 411   /**
 412    * Serialize all of the data.
 413    */
 414   GNUNET_CONTAINER_META_DATA_SERIALIZE_FULL = 0,
 415
 416   /**
 417    * If not enough space is available, it is acceptable
 418    * to only serialize some of the metadata.
 419    */
 420   GNUNET_CONTAINER_META_DATA_SERIALIZE_PART = 1,
 421
 422   /**
 423    * Speed is of the essence, do not allow compression.
 424    */
 425   GNUNET_CONTAINER_META_DATA_SERIALIZE_NO_COMPRESS = 2
 426 };
 427
 428
 429 /**
 430  * Serialize meta-data to target.
 431  *
 432  * @param md metadata to serialize
 433  * @param target where to write the serialized metadata;
 434  *         *target can be NULL, in which case memory is allocated
 435  * @param max maximum number of bytes available
 436  * @param opt is it ok to just write SOME of the
 437  *        meta-data to match the size constraint,
 438  *        possibly discarding some data?
 439  * @return number of bytes written on success,
 440  *         -1 on error (typically: not enough
 441  *         space)
 442  */
 443 ssize_t
 444 GNUNET_CONTAINER_meta_data_serialize (const struct
 445                                       GNUNET_CONTAINER_MetaData *md,
 446                                       char **target,
 447                                       size_t max,
 448                                       enum
 449                                       GNUNET_CONTAINER_MetaDataSerializationOptions
 450                                       opt);
 451
 452
 453 /**
 454  * Get the size of the full meta-data in serialized form.
 455  *
 456  * @param md metadata to inspect
 457  * @return number of bytes needed for serialization, -1 on error
 458  */
 459 ssize_t
 460 GNUNET_CONTAINER_meta_data_get_serialized_size (const struct
 461                                                 GNUNET_CONTAINER_MetaData
 462                                                 *md);
 463
 464
 465 /**
 466  * Deserialize meta-data.  Initializes md.
 467  *
 468  * @param input serialized meta-data.
 469  * @param size number of bytes available
 470  * @return MD on success, NULL on error (i.e.
 471  *         bad format)
 472  */
 473 struct GNUNET_CONTAINER_MetaData *
 474 GNUNET_CONTAINER_meta_data_deserialize (const char *input,
 475                                         size_t size);
 476
 477
 478 /* ******************************* HashMap **************************** */
 479
 480 /**
 481  * Opaque handle for a HashMap.
 482  */
 483 struct GNUNET_CONTAINER_MultiHashMap;
 484
 485 /**
 486  * Options for storing values in the HashMap.
 487  */
 488 enum GNUNET_CONTAINER_MultiHashMapOption
 489 {
 490
 491   /**
 492    * If a value with the given key exists, replace it.  Note that the
 493    * old value would NOT be freed by replace (the application has to
 494    * make sure that this happens if required).
 495    */
 496   GNUNET_CONTAINER_MULTIHASHMAPOPTION_REPLACE,
 497
 498   /**
 499    * Allow multiple values with the same key.
 500    */
 501   GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE,
 502
 503   /**
 504    * There must only be one value per key; storing a value should fail
 505    * if a value under the same key already exists.
 506    */
 507   GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY,
 508
 509   /**
 510    * There must only be one value per key, but don't bother checking
 511    * if a value already exists (faster than UNIQUE_ONLY; implemented
 512    * just like MULTIPLE but this option documents better what is
 513    * intended if UNIQUE is what is desired).
 514    */
 515   GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST
 516 };
 517
 518
 519 /**
 520  * Iterator over hash map entries.
 521  *
 522  * @param cls closure
 523  * @param key current key code
 524  * @param value value in the hash map
 525  * @return GNUNET_YES if we should continue to
 526  *         iterate,
 527  *         GNUNET_NO if not.
 528  */
 529 typedef int (*GNUNET_CONTAINER_HashMapIterator) (void *cls,
 530                                                  const GNUNET_HashCode * key,
 531                                                  void *value);
 532
 533
 534 /**
 535  * Create a multi hash map.
 536  *
 537  * @param len initial size (map will grow as needed)
 538  * @return NULL on error
 539  */
 540 struct GNUNET_CONTAINER_MultiHashMap
 541   *GNUNET_CONTAINER_multihashmap_create (unsigned int len);
 542
 543
 544 /**
 545  * Destroy a hash map.  Will not free any values
 546  * stored in the hash map!
 547  *
 548  * @param map the map
 549  */
 550 void GNUNET_CONTAINER_multihashmap_destroy (struct
 551                                             GNUNET_CONTAINER_MultiHashMap
 552                                             *map);
 553
 554
 555 /**
 556  * Given a key find a value in the map matching the key.
 557  *
 558  * @param map the map
 559  * @param key what to look for
 560  * @return NULL if no value was found; note that
 561  *   this is indistinguishable from values that just
 562  *   happen to be NULL; use "contains" to test for
 563  *   key-value pairs with value NULL
 564  */
 565 void *GNUNET_CONTAINER_multihashmap_get (const struct
 566                                          GNUNET_CONTAINER_MultiHashMap *map,
 567                                          const GNUNET_HashCode * key);
 568
 569
 570 /**
 571  * Remove the given key-value pair from the map.  Note that if the
 572  * key-value pair is in the map multiple times, only one of the pairs
 573  * will be removed.
 574  *
 575  * @param map the map
 576  * @param key key of the key-value pair
 577  * @param value value of the key-value pair
 578  * @return GNUNET_YES on success, GNUNET_NO if the key-value pair
 579  *  is not in the map
 580  */
 581 int GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap
 582                                           *map, const GNUNET_HashCode * key,
 583                                           void *value);
 584
 585 /**
 586  * Remove all entries for the given key from the map.
 587  * Note that the values would not be "freed".
 588  *
 589  * @param map the map
 590  * @param key identifies values to be removed
 591  * @return number of values removed
 592  */
 593 int GNUNET_CONTAINER_multihashmap_remove_all (struct
 594                                               GNUNET_CONTAINER_MultiHashMap
 595                                               *map,
 596                                               const GNUNET_HashCode * key);
 597
 598
 599 /**
 600  * Check if the map contains any value under the given
 601  * key (including values that are NULL).
 602  *
 603  * @param map the map
 604  * @param key the key to test if a value exists for it
 605  * @return GNUNET_YES if such a value exists,
 606  *         GNUNET_NO if not
 607  */
 608 int GNUNET_CONTAINER_multihashmap_contains (const struct
 609                                             GNUNET_CONTAINER_MultiHashMap
 610                                             *map,
 611                                             const GNUNET_HashCode * key);
 612
 613
 614 /**
 615  * Store a key-value pair in the map.
 616  *
 617  * @param map the map
 618  * @param key key to use
 619  * @param value value to use
 620  * @param opt options for put
 621  * @return GNUNET_OK on success,
 622  *         GNUNET_NO if a value was replaced (with REPLACE)
 623  *         GNUNET_SYSERR if UNIQUE_ONLY was the option and the
 624  *                       value already exists
 625  */
 626 int GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap
 627                                        *map, const GNUNET_HashCode * key,
 628                                        void *value,
 629                                        enum
 630                                        GNUNET_CONTAINER_MultiHashMapOption
 631                                        opt);
 632
 633 /**
 634  * Get the number of key-value pairs in the map.
 635  *
 636  * @param map the map
 637  * @return the number of key value pairs
 638  */
 639 unsigned int GNUNET_CONTAINER_multihashmap_size (const struct
 640                                                  GNUNET_CONTAINER_MultiHashMap
 641                                                  *map);
 642
 643
 644 /**
 645  * Iterate over all entries in the map.
 646  *
 647  * @param map the map
 648  * @param it function to call on each entry
 649  * @param it_cls extra argument to it
 650  * @return the number of key value pairs processed,
 651  *         GNUNET_SYSERR if it aborted iteration
 652  */
 653 int GNUNET_CONTAINER_multihashmap_iterate (const struct
 654                                            GNUNET_CONTAINER_MultiHashMap *map,
 655                                            GNUNET_CONTAINER_HashMapIterator
 656                                            it, void *it_cls);
 657
 658
 659 /**
 660  * Iterate over all entries in the map that match a particular key.
 661  *
 662  * @param map the map
 663  * @param key key that the entries must correspond to
 664  * @param it function to call on each entry
 665  * @param it_cls extra argument to it
 666  * @return the number of key value pairs processed,
 667  *         GNUNET_SYSERR if it aborted iteration
 668  */
 669 int GNUNET_CONTAINER_multihashmap_get_multiple (const struct
 670                                                 GNUNET_CONTAINER_MultiHashMap
 671                                                 *map,
 672                                                 const GNUNET_HashCode * key,
 673                                                 GNUNET_CONTAINER_HashMapIterator
 674                                                 it, void *it_cls);
 675
 676
 677 /* ******************** doubly-linked list *************** */
 678
 679 /**
 680  * Insert an element at the head of a DLL. Assumes that head, tail and
 681  * element are structs with prev and next fields.
 682  *
 683  * @param head pointer to the head of the DLL
 684  * @param tail pointer to the tail of the DLL
 685  * @param element element to insert
 686  */
 687 #define GNUNET_CONTAINER_DLL_insert(head,tail,element) do { \
 688   (element)->next = (head); \
 689   (element)->prev = NULL; \
 690   if ((tail) == NULL) \
 691     (tail) = element; \
 692   else \
 693     (head)->prev = element; \
 694   (head) = (element); } while (0)
 695
 696 /**
 697  * Insert an element at the tail of a DLL. Assumes that head, tail and
 698  * element are structs with prev and next fields.
 699  *
 700  * @param head pointer to the head of the DLL
 701  * @param tail pointer to the tail of the DLL
 702  * @param element element to insert
 703  */
 704 #define GNUNET_CONTAINER_DLL_insert_tail(head,tail,element) do { \
 705   (element)->prev = (tail); \
 706   (element)->next = NULL; \
 707   if ((head) == NULL) \
 708     (head) = element; \
 709   else \
 710     (tail)->next = element; \
 711   (tail) = (element); } while (0)
 712
 713 /**
 714  * Insert an element into a DLL after the given other element.  Insert
 715  * at the head if the other element is NULL.
 716  *
 717  * @param head pointer to the head of the DLL
 718  * @param tail pointer to the tail of the DLL
 719  * @param other prior element, NULL for insertion at head of DLL
 720  * @param element element to insert
 721  */
 722 #define GNUNET_CONTAINER_DLL_insert_after(head,tail,other,element) do { \
 723   (element)->prev = (other); \
 724   if (NULL == other) \
 725     { \
 726       (element)->next = (head); \
 727       (head) = (element); \
 728     } \
 729   else \
 730     { \
 731       (element)->next = (other)->next; \
 732       (other)->next = (element); \
 733     } \
 734   if (NULL == (element)->next) \
 735     (tail) = (element); \
 736   else \
 737     (element)->next->prev = (element); } while (0)
 738
 739 /**
 740  * Insert an element into a DLL before the given other element.  Insert
 741  * at the tail if the other element is NULL.
 742  *
 743  * @param head pointer to the head of the DLL
 744  * @param tail pointer to the tail of the DLL
 745  * @param other prior element, NULL for insertion at head of DLL
 746  * @param element element to insert
 747  */
 748 #define GNUNET_CONTAINER_DLL_insert_before(head,tail,other,element) do { \
 749   (element)->next = (other); \
 750   if (NULL == other) \
 751     { \
 752       (element)->prev = (tail); \
 753       (tail) = (element); \
 754     } \
 755   else \
 756     { \
 757       (element)->prev = (other)->prev; \
 758       (other)->prev = (element); \
 759     } \
 760   if (NULL == (element)->prev) \
 761     (head) = (element); \
 762   else \
 763     (element)->prev->next = (element); } while (0)
 764
 765
 766 /**
 767  * Remove an element from a DLL. Assumes
 768  * that head, tail and element are structs
 769  * with prev and next fields.
 770  *
 771  * @param head pointer to the head of the DLL
 772  * @param tail pointer to the tail of the DLL
 773  * @param element element to remove
 774  */
 775 #define GNUNET_CONTAINER_DLL_remove(head,tail,element) do { \
 776   if ((element)->prev == NULL) \
 777     (head) = (element)->next;  \
 778   else \
 779     (element)->prev->next = (element)->next; \
 780   if ((element)->next == NULL) \
 781     (tail) = (element)->prev;  \
 782   else \
 783     (element)->next->prev = (element)->prev; \
 784   (element)->next = NULL; \
 785   (element)->prev = NULL; } while (0)
 786
 787
 788
 789 /* ******************** Heap *************** */
 790
 791
 792 /**
 793  * Cost by which elements in a heap can be ordered.
 794  */
 795 typedef uint64_t GNUNET_CONTAINER_HeapCostType;
 796
 797
 798 /*
 799  * Heap type, either max or min.  Hopefully makes the
 800  * implementation more useful.
 801  */
 802 enum GNUNET_CONTAINER_HeapOrder
 803 {
 804   /**
 805    * Heap with the maximum cost at the root.
 806    */
 807   GNUNET_CONTAINER_HEAP_ORDER_MAX,
 808
 809   /**
 810    * Heap with the minimum cost at the root.
 811    */
 812   GNUNET_CONTAINER_HEAP_ORDER_MIN
 813 };
 814
 815
 816 /**
 817  * Handle to a Heap.
 818  */
 819 struct GNUNET_CONTAINER_Heap;
 820
 821
 822
 823 /**
 824  * Handle to a node in a heap.
 825  */
 826 struct GNUNET_CONTAINER_HeapNode;
 827
 828
 829 /**
 830  * Create a new heap.
 831  *
 832  * @param order how should the heap be sorted?
 833  * @return handle to the heap
 834  */
 835 struct GNUNET_CONTAINER_Heap *
 836 GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order);
 837
 838
 839 /**
 840  * Destroys the heap.  Only call on a heap that
 841  * is already empty.
 842  *
 843  * @param heap heap to destroy
 844  */
 845 void GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap);
 846
 847
 848 /**
 849  * Get element stored at root of heap.
 850  *
 851  * @param heap heap to inspect
 852  * @return NULL if heap is empty
 853  */
 854 void *
 855 GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap);
 856
 857
 858 /**
 859  * Get the current size of the heap
 860  *
 861  * @param heap the heap to get the size of
 862  * @return number of elements stored
 863  */
 864 unsigned int
 865 GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap);
 866
 867
 868 /**
 869  * Iterator for heap
 870  *
 871  * @param cls closure
 872  * @param node internal node of the heap
 873  * @param element value stored at the node
 874  * @param cost cost associated with the node
 875  * @return GNUNET_YES if we should continue to iterate,
 876  *         GNUNET_NO if not.
 877  */
 878 typedef int (*GNUNET_CONTAINER_HeapIterator) (void *cls,
 879                                               struct GNUNET_CONTAINER_HeapNode *node,
 880                                               void *element,
 881                                               GNUNET_CONTAINER_HeapCostType cost);
 882
 883
 884 /**
 885  * Iterate over all entries in the heap.
 886  *
 887  * @param heap the heap
 888  * @param iterator function to call on each entry
 889  * @param iterator_cls closure for iterator
 890  */
 891 void
 892 GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
 893                                GNUNET_CONTAINER_HeapIterator iterator,
 894                                void *iterator_cls);
 895
 896
 897 /**
 898  * Return a *uniform* random element from the heap.  Choose a random
 899  * number between 0 and heap size and then walk directly to it.
 900  * This cost can be between 0 and n, amortized cost of logN.
 901  *
 902  * @param heap heap to choose random element from
 903  * @param max how many nodes from the heap to choose from
 904  *
 905  * @return data stored at the chosen random node,
 906  *         NULL if the heap is empty.
 907  *
 908  */
 909 void *
 910 GNUNET_CONTAINER_heap_get_random (struct GNUNET_CONTAINER_Heap *heap, uint32_t max);
 911
 912 /**
 913  * Perform a random walk of the tree.  The walk is biased
 914  * towards elements closer to the root of the tree (since
 915  * each walk starts at the root and ends at a random leaf).
 916  * The heap internally tracks the current position of the
 917  * walk.
 918  *
 919  * @param heap heap to walk
 920  * @return data stored at the next random node in the walk;
 921  *         NULL if the tree is empty.
 922  */
 923 void *
 924 GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap);
 925
 926
 927 /**
 928  * Inserts a new element into the heap.
 929  *
 930  * @param heap heap to modify
 931  * @param element element to insert
 932  * @param cost cost for the element
 933  * @return node for the new element
 934  */
 935 struct GNUNET_CONTAINER_HeapNode *
 936 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap,
 937                               void *element,
 938                               GNUNET_CONTAINER_HeapCostType cost);
 939
 940
 941 /**
 942  * Remove root of the heap.
 943  *
 944  * @param heap heap to modify
 945  * @return element data stored at the root node
 946  */
 947 void *
 948 GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap);
 949
 950
 951 /**
 952  * Removes a node from the heap.
 953  *
 954  * @param heap heap to modify
 955  * @param node node to remove
 956  * @return element data stored at the node, NULL if heap is empty
 957  */
 958 void *
 959 GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *heap,
 960                                    struct GNUNET_CONTAINER_HeapNode *node);
 961
 962
 963 /**
 964  * Updates the cost of any node in the tree
 965  *
 966  * @param heap heap to modify
 967  * @param node node for which the cost is to be changed
 968  * @param new_cost new cost for the node
 969  */
 970 void
 971 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
 972                                    struct GNUNET_CONTAINER_HeapNode *node,
 973                                    GNUNET_CONTAINER_HeapCostType new_cost);
 974
 975
 976 /* ******************** Singly linked list *************** */
 977
 978 /**
 979  * Possible ways for how data stored in the linked list
 980  * might be allocated.
 981  */
 982 enum GNUNET_CONTAINER_SListDisposition
 983   {
 984     /**
 985      * Single-linked list must copy the buffer.
 986      */
 987     GNUNET_CONTAINER_SLIST_DISPOSITION_TRANSIENT = 0,
 988
 989     /**
 990      * Data is static, no need to copy or free.
 991      */
 992     GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC = 2,
 993
 994     /**
 995      * Data is dynamic, do not copy but free when done.
 996      */
 997     GNUNET_CONTAINER_SLIST_DISPOSITION_DYNAMIC = 4
 998   };
 999
1000
1001
1002 /**
1003  * Handle to a singly linked list
1004  */
1005 struct GNUNET_CONTAINER_SList;
1006
1007 /**
1008  * Handle to a singly linked list iterator
1009  */
1010 struct GNUNET_CONTAINER_SList_Iterator;
1011
1012
1013 /**
1014  * Add a new element to the list
1015  * @param l list
1016  * @param disp memory disposition
1017  * @param buf payload buffer
1018  * @param len length of the buffer
1019  */
1020 void GNUNET_CONTAINER_slist_add (struct GNUNET_CONTAINER_SList *l,
1021                                  enum GNUNET_CONTAINER_SListDisposition disp,
1022                                  const void *buf, size_t len);
1023
1024
1025 /**
1026  * Add a new element to the end of the list
1027  * @param l list
1028  * @param disp memory disposition
1029  * @param buf payload buffer
1030  * @param len length of the buffer
1031  */
1032 void GNUNET_CONTAINER_slist_add_end (struct GNUNET_CONTAINER_SList *l,
1033                                  enum GNUNET_CONTAINER_SListDisposition disp,
1034                                  const void *buf, size_t len);
1035
1036
1037 /**
1038  * Append a singly linked list to another
1039  * @param dst list to append to
1040  * @param src source
1041  */
1042 void
1043 GNUNET_CONTAINER_slist_append (struct GNUNET_CONTAINER_SList *dst, struct GNUNET_CONTAINER_SList *src);
1044
1045
1046 /**
1047  * Create a new singly linked list
1048  * @return the new list
1049  */
1050 struct GNUNET_CONTAINER_SList *GNUNET_CONTAINER_slist_create (void);
1051
1052
1053 /**
1054  * Destroy a singly linked list
1055  * @param l the list to be destroyed
1056  */
1057 void GNUNET_CONTAINER_slist_destroy (struct GNUNET_CONTAINER_SList *l);
1058
1059
1060 /**
1061  * Return the beginning of a list
1062  *
1063  * @param l list
1064  * @return iterator pointing to the beginning, free using "GNUNET_free"
1065  */
1066 struct GNUNET_CONTAINER_SList_Iterator *
1067 GNUNET_CONTAINER_slist_begin(struct GNUNET_CONTAINER_SList *l);
1068
1069
1070 /**
1071  * Clear a list
1072  *
1073  * @param l list
1074  */
1075 void GNUNET_CONTAINER_slist_clear (struct GNUNET_CONTAINER_SList *l);
1076
1077
1078 /**
1079  * Check if a list contains a certain element
1080  * @param l list
1081  * @param buf payload buffer to find
1082  * @param len length of the payload (number of bytes in buf)
1083  */
1084 int GNUNET_CONTAINER_slist_contains (const struct GNUNET_CONTAINER_SList *l, const void *buf, size_t len);
1085
1086
1087 /**
1088  * Count the elements of a list
1089  * @param l list
1090  * @return number of elements in the list
1091  */
1092 int GNUNET_CONTAINER_slist_count (const struct GNUNET_CONTAINER_SList *l);
1093
1094
1095 /**
1096  * Remove an element from the list
1097  * @param i iterator that points to the element to be removed
1098  */
1099 void GNUNET_CONTAINER_slist_erase (struct GNUNET_CONTAINER_SList_Iterator *i);
1100
1101
1102 /**
1103  * Insert an element into a list at a specific position
1104  * @param before where to insert the new element
1105  * @param disp memory disposition
1106  * @param buf payload buffer
1107  * @param len length of the payload
1108  */
1109 void GNUNET_CONTAINER_slist_insert (struct GNUNET_CONTAINER_SList_Iterator *before,
1110                                     enum GNUNET_CONTAINER_SListDisposition disp,
1111                                     const void *buf,
1112                                     size_t len);
1113
1114
1115 /**
1116  * Advance an iterator to the next element
1117  * @param i iterator
1118  * @return GNUNET_YES on success, GNUNET_NO if the end has been reached
1119  */
1120 int GNUNET_CONTAINER_slist_next (struct GNUNET_CONTAINER_SList_Iterator *i);
1121
1122
1123 /**
1124  * Check if an iterator points beyond the end of a list
1125  * @param i iterator
1126  * @return GNUNET_YES if the end has been reached, GNUNET_NO if the iterator
1127  *         points to a valid element
1128  */
1129 int GNUNET_CONTAINER_slist_end (struct GNUNET_CONTAINER_SList_Iterator *i);
1130
1131
1132 /**
1133  * Retrieve the element at a specific position in a list
1134  *
1135  * @param i iterator
1136  * @param len set to the payload length
1137  * @return payload
1138  */
1139 const void *
1140 GNUNET_CONTAINER_slist_get (const struct GNUNET_CONTAINER_SList_Iterator *i,
1141                             size_t *len);
1142
1143
1144 /**
1145  * Release an iterator
1146  * @param i iterator
1147  */
1148 void GNUNET_CONTAINER_slist_iter_destroy (struct GNUNET_CONTAINER_SList_Iterator *i);
1149
1150
1151 #if 0                           /* keep Emacsens' auto-indent happy */
1152 {
1153 #endif
1154 #ifdef __cplusplus
1155 }
1156 #endif
1157
1158
1159 /* ifndef GNUNET_CONTAINER_LIB_H */
1160 #endif
1161 /* end of gnunet_container_lib.h */