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