gnunet_container_lib.h (77014B)
1 /* 2 This file is part of GNUnet. 3 Copyright (C) 2001-2015 GNUnet e.V. 4 5 GNUnet is free software: you can redistribute it and/or modify it 6 under the terms of the GNU Affero General Public License as published 7 by the Free Software Foundation, either version 3 of the License, 8 or (at your 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 Affero General Public License for more details. 14 15 You should have received a copy of the GNU Affero General Public License 16 along with this program. If not, see <http://www.gnu.org/licenses/>. 17 18 SPDX-License-Identifier: AGPL3.0-or-later 19 */ 20 21 /** 22 * @addtogroup libgnunetutil 23 * Multi-function utilities library for GNUnet programs 24 * @{ 25 * 26 * @author Christian Grothoff 27 * @author Nils Durner 28 * 29 * @file 30 * Container classes for GNUnet 31 * 32 * @addtogroup container 33 * Common data structures in GNUnet programs 34 * @{ 35 * 36 * @defgroup hashmap MultiHashMap 37 * Hash map with multiple values per key. 38 * 39 * @see [Documentation](https://gnunet.org/util_multihashmap) 40 * 41 * @defgroup heap Heap 42 * Min- or max-heap with arbitrary element removal 43 * 44 * @defgroup bloomfilter Bloom filter 45 * Probabilistic set tests 46 * 47 * @defgroup dll Doubly-linked list 48 * 49 * @see [Documentation](https://gnunet.org/mdll-api) 50 * 51 * 52 * @} 53 */ 54 55 #include "gnunet_common.h" 56 #if !defined (__GNUNET_UTIL_LIB_H_INSIDE__) 57 #error "Only <gnunet_util_lib.h> can be included directly." 58 #endif 59 60 #ifndef GNUNET_CONTAINER_LIB_H 61 #define GNUNET_CONTAINER_LIB_H 62 63 #ifdef __cplusplus 64 extern "C" { 65 #if 0 /* keep Emacsens' auto-indent happy */ 66 } 67 #endif 68 #endif 69 70 71 /* add error and config prototypes */ 72 73 #include "gnunet_crypto_lib.h" 74 75 76 /** 77 * Try to compress the given block of data using libz. Only returns 78 * the compressed block if compression worked and the new block is 79 * actually smaller. Decompress using #GNUNET_decompress(). 80 * 81 * @param data block to compress; if compression 82 * resulted in a smaller block, the first 83 * bytes of data are updated to the compressed 84 * data 85 * @param old_size number of bytes in data 86 * @param[out] result set to the compressed data, if compression worked 87 * @param[out] new_size set to size of result, if compression worked 88 * @return #GNUNET_YES if compression reduce the size, 89 * #GNUNET_NO if compression did not help 90 */ 91 int 92 GNUNET_try_compression (const char *data, 93 size_t old_size, 94 char **result, 95 size_t *new_size); 96 97 98 /** 99 * Decompress input, return the decompressed data as output. Dual to 100 * #GNUNET_try_compression(). Caller must set @a output_size to the 101 * number of bytes that were originally compressed. 102 * 103 * @param input compressed data 104 * @param input_size number of bytes in input 105 * @param output_size expected size of the output 106 * @return NULL on error, buffer of @a output_size decompressed bytes otherwise 107 */ 108 char * 109 GNUNET_decompress (const char *input, size_t input_size, size_t output_size); 110 111 112 /* ******************* bloomfilter ***************** */ 113 114 /** 115 * @brief bloomfilter representation (opaque) 116 * @ingroup bloomfilter 117 */ 118 struct GNUNET_CONTAINER_BloomFilter; 119 120 121 /** 122 * @ingroup bloomfilter 123 * Iterator over `struct GNUNET_HashCode`. 124 * 125 * @param cls closure 126 * @param next set to the next hash code 127 * @return #GNUNET_YES if next was updated 128 * #GNUNET_NO if there are no more entries 129 */ 130 typedef int (*GNUNET_CONTAINER_HashCodeIterator) (void *cls, 131 struct GNUNET_HashCode *next); 132 133 134 /** 135 * @ingroup bloomfilter 136 * Load a Bloom filter from a file. 137 * 138 * @param filename the name of the file (or the prefix) 139 * @param size the size of the bloom-filter (number of 140 * bytes of storage space to use); will be rounded up 141 * to next power of 2 142 * @param k the number of #GNUNET_CRYPTO_hash-functions to apply per 143 * element (number of bits set per element in the set) 144 * @return the bloomfilter 145 */ 146 struct GNUNET_CONTAINER_BloomFilter * 147 GNUNET_CONTAINER_bloomfilter_load (const char *filename, 148 size_t size, 149 unsigned int k); 150 151 152 /** 153 * @ingroup bloomfilter 154 * Create a Bloom filter from raw bits. 155 * 156 * @param data the raw bits in memory (maybe NULL, 157 * in which case all bits should be considered 158 * to be zero). 159 * @param size the size of the bloom-filter (number of 160 * bytes of storage space to use); also size of @a data 161 * -- unless data is NULL. Must be a power of 2. 162 * @param k the number of #GNUNET_CRYPTO_hash-functions to apply per 163 * element (number of bits set per element in the set) 164 * @return the bloomfilter 165 */ 166 struct GNUNET_CONTAINER_BloomFilter * 167 GNUNET_CONTAINER_bloomfilter_init (const char *data, 168 size_t size, 169 unsigned int k); 170 171 172 /** 173 * @ingroup bloomfilter 174 * Copy the raw data of this Bloom filter into 175 * the given data array. 176 * 177 * @param data where to write the data 178 * @param size the size of the given @a data array 179 * @return #GNUNET_SYSERR if the data array of the wrong size 180 */ 181 enum GNUNET_GenericReturnValue 182 GNUNET_CONTAINER_bloomfilter_get_raw_data ( 183 const struct GNUNET_CONTAINER_BloomFilter *bf, 184 char *data, 185 size_t size); 186 187 188 /** 189 * @ingroup bloomfilter 190 * Test if an element is in the filter. 191 * 192 * @param e the element 193 * @param bf the filter 194 * @return true if the element is in the filter, false if not 195 */ 196 bool 197 GNUNET_CONTAINER_bloomfilter_test ( 198 const struct GNUNET_CONTAINER_BloomFilter *bf, 199 const struct GNUNET_HashCode *e); 200 201 202 /** 203 * @ingroup bloomfilter 204 * Add an element to the filter. 205 * 206 * @param bf the filter 207 * @param e the element 208 */ 209 void 210 GNUNET_CONTAINER_bloomfilter_add (struct GNUNET_CONTAINER_BloomFilter *bf, 211 const struct GNUNET_HashCode *e); 212 213 214 /** 215 * @ingroup bloomfilter 216 * Remove an element from the filter. 217 * 218 * @param bf the filter 219 * @param e the element to remove 220 */ 221 void 222 GNUNET_CONTAINER_bloomfilter_remove (struct GNUNET_CONTAINER_BloomFilter *bf, 223 const struct GNUNET_HashCode *e); 224 225 226 /** 227 * @ingroup bloomfilter 228 * Create a copy of a bloomfilter. 229 * 230 * @param bf the filter 231 * @return copy of bf 232 */ 233 struct GNUNET_CONTAINER_BloomFilter * 234 GNUNET_CONTAINER_bloomfilter_copy ( 235 const struct GNUNET_CONTAINER_BloomFilter *bf); 236 237 238 /** 239 * @ingroup bloomfilter 240 * Free the space associated with a filter 241 * in memory, flush to drive if needed (do not 242 * free the space on the drive). 243 * 244 * @param bf the filter 245 */ 246 void 247 GNUNET_CONTAINER_bloomfilter_free (struct GNUNET_CONTAINER_BloomFilter *bf); 248 249 250 /** 251 * Get the number of the addresses set per element in the bloom filter. 252 * 253 * @param bf the filter 254 * @return addresses set per element in the bf 255 */ 256 size_t 257 GNUNET_CONTAINER_bloomfilter_get_element_addresses ( 258 const struct GNUNET_CONTAINER_BloomFilter *bf); 259 260 261 /** 262 * @ingroup bloomfilter 263 * Get size of the bloom filter. 264 * 265 * @param bf the filter 266 * @return number of bytes used for the data of the bloom filter 267 */ 268 size_t 269 GNUNET_CONTAINER_bloomfilter_get_size ( 270 const struct GNUNET_CONTAINER_BloomFilter *bf); 271 272 273 /** 274 * @ingroup bloomfilter 275 * Reset a Bloom filter to empty. 276 * 277 * @param bf the filter 278 */ 279 void 280 GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter *bf); 281 282 283 /** 284 * @ingroup bloomfilter 285 * "or" the entries of the given raw data array with the 286 * data of the given Bloom filter. Assumes that 287 * the @a size of the @a data array and the current filter 288 * match. 289 * 290 * @param bf the filter 291 * @param data data to OR-in 292 * @param size size of @a data 293 * @return #GNUNET_OK on success 294 */ 295 enum GNUNET_GenericReturnValue 296 GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf, 297 const char *data, 298 size_t size); 299 300 301 /** 302 * @ingroup bloomfilter 303 * "or" the entries of the given raw data array with the 304 * data of the given Bloom filter. Assumes that 305 * the size of the two filters matches. 306 * 307 * @param bf the filter 308 * @param to_or the bloomfilter to or-in 309 * @return #GNUNET_OK on success 310 */ 311 enum GNUNET_GenericReturnValue 312 GNUNET_CONTAINER_bloomfilter_or2 ( 313 struct GNUNET_CONTAINER_BloomFilter *bf, 314 const struct GNUNET_CONTAINER_BloomFilter *to_or); 315 316 317 /** 318 * @ingroup bloomfilter 319 * Resize a bloom filter. Note that this operation 320 * is pretty costly. Essentially, the Bloom filter 321 * needs to be completely re-build. 322 * 323 * @param bf the filter 324 * @param iterator an iterator over all elements stored in the BF 325 * @param iterator_cls closure for @a iterator 326 * @param size the new size for the filter 327 * @param k the new number of #GNUNET_CRYPTO_hash-function to apply per element 328 */ 329 void 330 GNUNET_CONTAINER_bloomfilter_resize (struct GNUNET_CONTAINER_BloomFilter *bf, 331 GNUNET_CONTAINER_HashCodeIterator iterator, 332 void *iterator_cls, 333 size_t size, 334 unsigned int k); 335 336 337 338 /* ******************************* HashMap **************************** */ 339 340 /** 341 * @ingroup hashmap 342 * Opaque handle for a HashMap. 343 */ 344 struct GNUNET_CONTAINER_MultiHashMap; 345 346 /** 347 * @ingroup hashmap 348 * Opaque handle to an iterator over 349 * a multihashmap. 350 */ 351 struct GNUNET_CONTAINER_MultiHashMapIterator; 352 353 /** 354 * @ingroup hashmap 355 * Options for storing values in the HashMap. 356 */ 357 enum GNUNET_CONTAINER_MultiHashMapOption 358 { 359 /** 360 * @ingroup hashmap 361 * If a value with the given key exists, replace it. Note that the 362 * old value would NOT be freed by replace (the application has to 363 * make sure that this happens if required). 364 */ 365 GNUNET_CONTAINER_MULTIHASHMAPOPTION_REPLACE, 366 367 /** 368 * @ingroup hashmap 369 * Allow multiple values with the same key. 370 */ 371 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE, 372 373 /** 374 * @ingroup hashmap 375 * There must only be one value per key; storing a value should fail 376 * if a value under the same key already exists. 377 */ 378 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY, 379 380 /** 381 * @ingroup hashmap There must only be one value per key, but don't 382 * bother checking if a value already exists (faster than 383 * #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY; implemented 384 * just like #GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE but this 385 * option documents better what is intended if 386 * #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY is what is 387 * desired). 388 */ 389 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST 390 }; 391 392 393 /** 394 * @ingroup hashmap 395 * Iterator over hash map entries. 396 * 397 * @param cls closure 398 * @param key current key code 399 * @param value value in the hash map 400 * @return #GNUNET_YES if we should continue to 401 * iterate, 402 * #GNUNET_NO if not. 403 */ 404 typedef enum GNUNET_GenericReturnValue 405 (*GNUNET_CONTAINER_MultiHashMapIteratorCallback)( 406 void *cls, 407 const struct GNUNET_HashCode *key, 408 void *value); 409 410 411 /** 412 * @ingroup hashmap 413 * Create a multi hash map. 414 * 415 * @param len initial size (map will grow as needed) 416 * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default; 417 * #GNUNET_YES means that on 'put', the 'key' does not have 418 * to be copied as the destination of the pointer is 419 * guaranteed to be life as long as the value is stored in 420 * the hashmap. This can significantly reduce memory 421 * consumption, but of course is also a recipe for 422 * heap corruption if the assumption is not true. Only 423 * use this if (1) memory use is important in this case and 424 * (2) you have triple-checked that the invariant holds 425 * @return NULL on error 426 */ 427 struct GNUNET_CONTAINER_MultiHashMap * 428 GNUNET_CONTAINER_multihashmap_create (unsigned int len, 429 int do_not_copy_keys); 430 431 432 /** 433 * @ingroup hashmap 434 * Destroy a hash map. Will not free any values 435 * stored in the hash map! 436 * 437 * @param map the map 438 */ 439 void 440 GNUNET_CONTAINER_multihashmap_destroy (struct 441 GNUNET_CONTAINER_MultiHashMap *map); 442 443 444 /** 445 * @ingroup hashmap 446 * Given a key find a value in the map matching the key. 447 * 448 * @param map the map 449 * @param key what to look for 450 * @return NULL if no value was found; note that 451 * this is indistinguishable from values that just 452 * happen to be NULL; use "contains" to test for 453 * key-value pairs with value NULL 454 */ 455 void * 456 GNUNET_CONTAINER_multihashmap_get ( 457 const struct GNUNET_CONTAINER_MultiHashMap *map, 458 const struct GNUNET_HashCode *key); 459 460 461 /** 462 * @ingroup hashmap 463 * Remove the given key-value pair from the map. Note that if the 464 * key-value pair is in the map multiple times, only one of the pairs 465 * will be removed. 466 * 467 * @param map the map 468 * @param key key of the key-value pair 469 * @param value value of the key-value pair 470 * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair 471 * is not in the map 472 */ 473 enum GNUNET_GenericReturnValue 474 GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map, 475 const struct GNUNET_HashCode *key, 476 const void *value); 477 478 /** 479 * @ingroup hashmap 480 * Remove all entries for the given key from the map. 481 * Note that the values would not be "freed". 482 * 483 * @param map the map 484 * @param key identifies values to be removed 485 * @return number of values removed 486 */ 487 int 488 GNUNET_CONTAINER_multihashmap_remove_all ( 489 struct GNUNET_CONTAINER_MultiHashMap *map, 490 const struct GNUNET_HashCode *key); 491 492 493 /** 494 * @ingroup hashmap 495 * Remove all entries from the map. 496 * Note that the values would not be "freed". 497 * 498 * @param map the map 499 * @return number of values removed 500 */ 501 unsigned int 502 GNUNET_CONTAINER_multihashmap_clear (struct GNUNET_CONTAINER_MultiHashMap *map); 503 504 505 /** 506 * @ingroup hashmap 507 * Check if the map contains any value under the given 508 * key (including values that are NULL). 509 * 510 * @param map the map 511 * @param key the key to test if a value exists for it 512 * @return #GNUNET_YES if such a value exists, 513 * #GNUNET_NO if not 514 */ 515 enum GNUNET_GenericReturnValue 516 GNUNET_CONTAINER_multihashmap_contains ( 517 const struct GNUNET_CONTAINER_MultiHashMap *map, 518 const struct GNUNET_HashCode *key); 519 520 521 /** 522 * @ingroup hashmap 523 * Check if the map contains the given value under the given 524 * key. 525 * 526 * @param map the map 527 * @param key the key to test if a value exists for it 528 * @param value value to test for 529 * @return #GNUNET_YES if such a value exists, 530 * #GNUNET_NO if not 531 */ 532 enum GNUNET_GenericReturnValue 533 GNUNET_CONTAINER_multihashmap_contains_value ( 534 const struct GNUNET_CONTAINER_MultiHashMap *map, 535 const struct GNUNET_HashCode *key, 536 const void *value); 537 538 539 /** 540 * @ingroup hashmap 541 * Store a key-value pair in the map. 542 * 543 * @param map the map 544 * @param key key to use 545 * @param value value to use 546 * @param opt options for put 547 * @return #GNUNET_OK on success, 548 * #GNUNET_NO if a value was replaced (with REPLACE) 549 * #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the 550 * value already exists 551 */ 552 enum GNUNET_GenericReturnValue 553 GNUNET_CONTAINER_multihashmap_put ( 554 struct GNUNET_CONTAINER_MultiHashMap *map, 555 const struct GNUNET_HashCode *key, 556 void *value, 557 enum GNUNET_CONTAINER_MultiHashMapOption opt); 558 559 /** 560 * @ingroup hashmap 561 * Get the number of key-value pairs in the map. 562 * 563 * @param map the map 564 * @return the number of key value pairs 565 */ 566 unsigned int 567 GNUNET_CONTAINER_multihashmap_size ( 568 const struct GNUNET_CONTAINER_MultiHashMap *map); 569 570 571 /** 572 * @ingroup hashmap 573 * Iterate over all entries in the map. 574 * 575 * @param map the map 576 * @param it function to call on each entry 577 * @param it_cls extra argument to @a it 578 * @return the number of key value pairs processed, 579 * #GNUNET_SYSERR if it aborted iteration 580 */ 581 int 582 GNUNET_CONTAINER_multihashmap_iterate ( 583 struct GNUNET_CONTAINER_MultiHashMap *map, 584 GNUNET_CONTAINER_MultiHashMapIteratorCallback it, 585 void *it_cls); 586 587 588 /** 589 * @ingroup hashmap 590 * Create an iterator for a multihashmap. 591 * The iterator can be used to retrieve all the elements in the multihashmap 592 * one by one, without having to handle all elements at once (in contrast to 593 * #GNUNET_CONTAINER_multihashmap_iterate). Note that the iterator can not be 594 * used anymore if elements have been removed from 'map' after the creation of 595 * the iterator, or 'map' has been destroyed. Adding elements to 'map' may 596 * result in skipped or repeated elements. 597 * 598 * @param map the map to create an iterator for 599 * @return an iterator over the given multihashmap @a map 600 */ 601 struct GNUNET_CONTAINER_MultiHashMapIterator * 602 GNUNET_CONTAINER_multihashmap_iterator_create ( 603 const struct GNUNET_CONTAINER_MultiHashMap *map); 604 605 606 /** 607 * @ingroup hashmap 608 * Retrieve the next element from the hash map at the iterator's 609 * position. If there are no elements left, #GNUNET_NO is returned, 610 * and @a key and @a value are not modified. This operation is only 611 * allowed if no elements have been removed from the multihashmap 612 * since the creation of @a iter, and the map has not been destroyed. 613 * Adding elements may result in repeating or skipping elements. 614 * 615 * @param iter the iterator to get the next element from 616 * @param key pointer to store the key in, can be NULL 617 * @param value pointer to store the value in, can be NULL 618 * @return #GNUNET_YES we returned an element, 619 * #GNUNET_NO if we are out of elements 620 */ 621 enum GNUNET_GenericReturnValue 622 GNUNET_CONTAINER_multihashmap_iterator_next ( 623 struct GNUNET_CONTAINER_MultiHashMapIterator *iter, 624 struct GNUNET_HashCode *key, 625 const void **value); 626 627 628 /** 629 * @ingroup hashmap 630 * Destroy a multihashmap iterator. 631 * 632 * @param iter the iterator to destroy 633 */ 634 void 635 GNUNET_CONTAINER_multihashmap_iterator_destroy ( 636 struct GNUNET_CONTAINER_MultiHashMapIterator *iter); 637 638 639 /** 640 * @ingroup hashmap 641 * Iterate over all entries in the map that match a particular key. 642 * 643 * @param map the map 644 * @param key key that the entries must correspond to 645 * @param it function to call on each entry 646 * @param it_cls extra argument to @a it 647 * @return the number of key value pairs processed, 648 * #GNUNET_SYSERR if it aborted iteration 649 */ 650 enum GNUNET_GenericReturnValue 651 GNUNET_CONTAINER_multihashmap_get_multiple ( 652 struct GNUNET_CONTAINER_MultiHashMap *map, 653 const struct GNUNET_HashCode *key, 654 GNUNET_CONTAINER_MultiHashMapIteratorCallback it, 655 void *it_cls); 656 657 658 /** 659 * @ingroup hashmap 660 * Call @a it on a random value from the map, or not at all 661 * if the map is empty. Note that this function has linear 662 * complexity (in the size of the map). 663 * 664 * @param map the map 665 * @param it function to call on a random entry 666 * @param it_cls extra argument to @a it 667 * @return the number of key value pairs processed, zero or one. 668 */ 669 unsigned int 670 GNUNET_CONTAINER_multihashmap_get_random ( 671 const struct GNUNET_CONTAINER_MultiHashMap *map, 672 GNUNET_CONTAINER_MultiHashMapIteratorCallback it, 673 void *it_cls); 674 675 676 /* ***************** Version of Multihashmap for peer identities ****************** */ 677 678 /** 679 * @ingroup hashmap 680 * Iterator over hash map entries. 681 * 682 * @param cls closure 683 * @param key current public key 684 * @param value value in the hash map 685 * @return #GNUNET_YES if we should continue to 686 * iterate, 687 * #GNUNET_NO if not. 688 */ 689 typedef enum GNUNET_GenericReturnValue 690 (*GNUNET_CONTAINER_PeerMapIterator)( 691 void *cls, 692 const struct GNUNET_PeerIdentity *key, 693 void *value); 694 695 696 /** 697 * Hash map from peer identities to values. 698 */ 699 struct GNUNET_CONTAINER_MultiPeerMap; 700 701 702 /** 703 * @ingroup hashmap 704 * Create a multi peer map (hash map for public keys of peers). 705 * 706 * @param len initial size (map will grow as needed) 707 * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default; 708 * #GNUNET_YES means that on 'put', the 'key' does not have 709 * to be copied as the destination of the pointer is 710 * guaranteed to be life as long as the value is stored in 711 * the hashmap. This can significantly reduce memory 712 * consumption, but of course is also a recipe for 713 * heap corruption if the assumption is not true. Only 714 * use this if (1) memory use is important in this case and 715 * (2) you have triple-checked that the invariant holds 716 * @return NULL on error 717 */ 718 struct GNUNET_CONTAINER_MultiPeerMap * 719 GNUNET_CONTAINER_multipeermap_create (unsigned int len, int do_not_copy_keys); 720 721 722 /** 723 * @ingroup hashmap 724 * Destroy a hash map. Will not free any values 725 * stored in the hash map! 726 * 727 * @param map the map 728 */ 729 void 730 GNUNET_CONTAINER_multipeermap_destroy ( 731 struct GNUNET_CONTAINER_MultiPeerMap *map); 732 733 734 /** 735 * @ingroup hashmap 736 * Given a key find a value in the map matching the key. 737 * 738 * @param map the map 739 * @param key what to look for 740 * @return NULL if no value was found; note that 741 * this is indistinguishable from values that just 742 * happen to be NULL; use "contains" to test for 743 * key-value pairs with value NULL 744 */ 745 void * 746 GNUNET_CONTAINER_multipeermap_get ( 747 const struct GNUNET_CONTAINER_MultiPeerMap *map, 748 const struct GNUNET_PeerIdentity *key); 749 750 751 /** 752 * @ingroup hashmap 753 * Remove the given key-value pair from the map. Note that if the 754 * key-value pair is in the map multiple times, only one of the pairs 755 * will be removed. 756 * 757 * @param map the map 758 * @param key key of the key-value pair 759 * @param value value of the key-value pair 760 * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair 761 * is not in the map 762 */ 763 enum GNUNET_GenericReturnValue 764 GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map, 765 const struct GNUNET_PeerIdentity *key, 766 const void *value); 767 768 /** 769 * @ingroup hashmap 770 * Remove all entries for the given key from the map. 771 * Note that the values would not be "freed". 772 * 773 * @param map the map 774 * @param key identifies values to be removed 775 * @return number of values removed 776 */ 777 int 778 GNUNET_CONTAINER_multipeermap_remove_all ( 779 struct GNUNET_CONTAINER_MultiPeerMap *map, 780 const struct GNUNET_PeerIdentity *key); 781 782 783 /** 784 * @ingroup hashmap 785 * Check if the map contains any value under the given 786 * key (including values that are NULL). 787 * 788 * @param map the map 789 * @param key the key to test if a value exists for it 790 * @return #GNUNET_YES if such a value exists, 791 * #GNUNET_NO if not 792 */ 793 enum GNUNET_GenericReturnValue 794 GNUNET_CONTAINER_multipeermap_contains ( 795 const struct GNUNET_CONTAINER_MultiPeerMap *map, 796 const struct GNUNET_PeerIdentity *key); 797 798 799 /** 800 * @ingroup hashmap 801 * Check if the map contains the given value under the given 802 * key. 803 * 804 * @param map the map 805 * @param key the key to test if a value exists for it 806 * @param value value to test for 807 * @return #GNUNET_YES if such a value exists, 808 * #GNUNET_NO if not 809 */ 810 enum GNUNET_GenericReturnValue 811 GNUNET_CONTAINER_multipeermap_contains_value ( 812 const struct GNUNET_CONTAINER_MultiPeerMap *map, 813 const struct GNUNET_PeerIdentity *key, 814 const void *value); 815 816 817 /** 818 * @ingroup hashmap 819 * Store a key-value pair in the map. 820 * 821 * @param map the map 822 * @param key key to use 823 * @param value value to use 824 * @param opt options for put 825 * @return #GNUNET_OK on success, 826 * #GNUNET_NO if a value was replaced (with REPLACE) 827 * #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the 828 * value already exists 829 */ 830 int 831 GNUNET_CONTAINER_multipeermap_put ( 832 struct GNUNET_CONTAINER_MultiPeerMap *map, 833 const struct GNUNET_PeerIdentity *key, 834 void *value, 835 enum GNUNET_CONTAINER_MultiHashMapOption opt); 836 837 838 /** 839 * @ingroup hashmap 840 * Get the number of key-value pairs in the map. 841 * 842 * @param map the map 843 * @return the number of key value pairs 844 */ 845 unsigned int 846 GNUNET_CONTAINER_multipeermap_size ( 847 const struct GNUNET_CONTAINER_MultiPeerMap *map); 848 849 850 /** 851 * @ingroup hashmap 852 * Iterate over all entries in the map. 853 * 854 * @param map the map 855 * @param it function to call on each entry 856 * @param it_cls extra argument to @a it 857 * @return the number of key value pairs processed, 858 * #GNUNET_SYSERR if it aborted iteration 859 */ 860 int 861 GNUNET_CONTAINER_multipeermap_iterate ( 862 struct GNUNET_CONTAINER_MultiPeerMap *map, 863 GNUNET_CONTAINER_PeerMapIterator it, 864 void *it_cls); 865 866 867 struct GNUNET_CONTAINER_MultiPeerMapIterator; 868 /** 869 * @ingroup hashmap 870 * Create an iterator for a multihashmap. 871 * The iterator can be used to retrieve all the elements in the multihashmap 872 * one by one, without having to handle all elements at once (in contrast to 873 * #GNUNET_CONTAINER_multipeermap_iterate). Note that the iterator can not be 874 * used anymore if elements have been removed from @a map after the creation of 875 * the iterator, or 'map' has been destroyed. Adding elements to @a map may 876 * result in skipped or repeated elements. 877 * 878 * @param map the map to create an iterator for 879 * @return an iterator over the given multihashmap @a map 880 */ 881 struct GNUNET_CONTAINER_MultiPeerMapIterator * 882 GNUNET_CONTAINER_multipeermap_iterator_create ( 883 const struct GNUNET_CONTAINER_MultiPeerMap *map); 884 885 886 /** 887 * @ingroup hashmap 888 * Retrieve the next element from the hash map at the iterator's 889 * position. If there are no elements left, #GNUNET_NO is returned, 890 * and @a key and @a value are not modified. 891 * 892 * This operation is only allowed if no elements have been removed 893 * from the multihashmap since the creation of @a iter, and the map 894 * has not been destroyed. 895 * 896 * Adding elements may result in repeating or skipping elements. 897 * 898 * @param iter the iterator to get the next element from 899 * @param key pointer to store the key in, can be NULL 900 * @param value pointer to store the value in, can be NULL 901 * @return #GNUNET_YES we returned an element, 902 * #GNUNET_NO if we are out of elements 903 */ 904 enum GNUNET_GenericReturnValue 905 GNUNET_CONTAINER_multipeermap_iterator_next ( 906 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter, 907 struct GNUNET_PeerIdentity *key, 908 const void **value); 909 910 911 /** 912 * @ingroup hashmap 913 * Destroy a multipeermap iterator. 914 * 915 * @param iter the iterator to destroy 916 */ 917 void 918 GNUNET_CONTAINER_multipeermap_iterator_destroy ( 919 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter); 920 921 922 /** 923 * @ingroup hashmap 924 * Iterate over all entries in the map that match a particular key. 925 * 926 * @param map the map 927 * @param key public key that the entries must correspond to 928 * @param it function to call on each entry 929 * @param it_cls extra argument to @a it 930 * @return the number of key value pairs processed, 931 * #GNUNET_SYSERR if it aborted iteration 932 */ 933 int 934 GNUNET_CONTAINER_multipeermap_get_multiple ( 935 struct GNUNET_CONTAINER_MultiPeerMap *map, 936 const struct GNUNET_PeerIdentity *key, 937 GNUNET_CONTAINER_PeerMapIterator it, 938 void *it_cls); 939 940 941 /** 942 * @ingroup hashmap 943 * Call @a it on a random value from the map, or not at all 944 * if the map is empty. Note that this function has linear 945 * complexity (in the size of the map). 946 * 947 * @param map the map 948 * @param it function to call on a random entry 949 * @param it_cls extra argument to @a it 950 * @return the number of key value pairs processed, zero or one. 951 */ 952 unsigned int 953 GNUNET_CONTAINER_multipeermap_get_random ( 954 const struct GNUNET_CONTAINER_MultiPeerMap *map, 955 GNUNET_CONTAINER_PeerMapIterator it, 956 void *it_cls); 957 958 959 /* ***************** Version of Multihashmap for short hashes ****************** */ 960 961 /** 962 * @ingroup hashmap 963 * Iterator over hash map entries. 964 * 965 * @param cls closure 966 * @param key current public key 967 * @param value value in the hash map 968 * @return #GNUNET_YES if we should continue to 969 * iterate, 970 * #GNUNET_NO if not. 971 */ 972 typedef enum GNUNET_GenericReturnValue 973 (*GNUNET_CONTAINER_ShortmapIterator)( 974 void *cls, 975 const struct GNUNET_ShortHashCode *key, 976 void *value); 977 978 979 /** 980 * Hash map from peer identities to values. 981 */ 982 struct GNUNET_CONTAINER_MultiShortmap; 983 984 985 /** 986 * @ingroup hashmap 987 * Create a multi peer map (hash map for public keys of peers). 988 * 989 * @param len initial size (map will grow as needed) 990 * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default; 991 * #GNUNET_YES means that on 'put', the 'key' does not have 992 * to be copied as the destination of the pointer is 993 * guaranteed to be life as long as the value is stored in 994 * the hashmap. This can significantly reduce memory 995 * consumption, but of course is also a recipe for 996 * heap corruption if the assumption is not true. Only 997 * use this if (1) memory use is important in this case and 998 * (2) you have triple-checked that the invariant holds 999 * @return NULL on error 1000 */ 1001 struct GNUNET_CONTAINER_MultiShortmap * 1002 GNUNET_CONTAINER_multishortmap_create (unsigned int len, int do_not_copy_keys); 1003 1004 1005 /** 1006 * @ingroup hashmap 1007 * Destroy a hash map. Will not free any values 1008 * stored in the hash map! 1009 * 1010 * @param map the map 1011 */ 1012 void 1013 GNUNET_CONTAINER_multishortmap_destroy ( 1014 struct GNUNET_CONTAINER_MultiShortmap *map); 1015 1016 1017 /** 1018 * @ingroup hashmap 1019 * Given a key find a value in the map matching the key. 1020 * 1021 * @param map the map 1022 * @param key what to look for 1023 * @return NULL if no value was found; note that 1024 * this is indistinguishable from values that just 1025 * happen to be NULL; use "contains" to test for 1026 * key-value pairs with value NULL 1027 */ 1028 void * 1029 GNUNET_CONTAINER_multishortmap_get ( 1030 const struct GNUNET_CONTAINER_MultiShortmap *map, 1031 const struct GNUNET_ShortHashCode *key); 1032 1033 1034 /** 1035 * @ingroup hashmap 1036 * Remove the given key-value pair from the map. Note that if the 1037 * key-value pair is in the map multiple times, only one of the pairs 1038 * will be removed. 1039 * 1040 * @param map the map 1041 * @param key key of the key-value pair 1042 * @param value value of the key-value pair 1043 * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair 1044 * is not in the map 1045 */ 1046 int 1047 GNUNET_CONTAINER_multishortmap_remove ( 1048 struct GNUNET_CONTAINER_MultiShortmap *map, 1049 const struct GNUNET_ShortHashCode *key, 1050 const void *value); 1051 1052 /** 1053 * @ingroup hashmap 1054 * Remove all entries for the given key from the map. 1055 * Note that the values would not be "freed". 1056 * 1057 * @param map the map 1058 * @param key identifies values to be removed 1059 * @return number of values removed 1060 */ 1061 int 1062 GNUNET_CONTAINER_multishortmap_remove_all ( 1063 struct GNUNET_CONTAINER_MultiShortmap *map, 1064 const struct GNUNET_ShortHashCode *key); 1065 1066 1067 /** 1068 * @ingroup hashmap 1069 * Check if the map contains any value under the given 1070 * key (including values that are NULL). 1071 * 1072 * @param map the map 1073 * @param key the key to test if a value exists for it 1074 * @return #GNUNET_YES if such a value exists, 1075 * #GNUNET_NO if not 1076 */ 1077 int 1078 GNUNET_CONTAINER_multishortmap_contains ( 1079 const struct GNUNET_CONTAINER_MultiShortmap *map, 1080 const struct GNUNET_ShortHashCode *key); 1081 1082 1083 /** 1084 * @ingroup hashmap 1085 * Check if the map contains the given value under the given 1086 * key. 1087 * 1088 * @param map the map 1089 * @param key the key to test if a value exists for it 1090 * @param value value to test for 1091 * @return #GNUNET_YES if such a value exists, 1092 * #GNUNET_NO if not 1093 */ 1094 int 1095 GNUNET_CONTAINER_multishortmap_contains_value ( 1096 const struct GNUNET_CONTAINER_MultiShortmap *map, 1097 const struct GNUNET_ShortHashCode *key, 1098 const void *value); 1099 1100 1101 /** 1102 * @ingroup hashmap 1103 * Store a key-value pair in the map. 1104 * 1105 * @param map the map 1106 * @param key key to use 1107 * @param value value to use 1108 * @param opt options for put 1109 * @return #GNUNET_OK on success, 1110 * #GNUNET_NO if a value was replaced (with REPLACE) 1111 * #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the 1112 * value already exists 1113 */ 1114 enum GNUNET_GenericReturnValue 1115 GNUNET_CONTAINER_multishortmap_put ( 1116 struct GNUNET_CONTAINER_MultiShortmap *map, 1117 const struct GNUNET_ShortHashCode *key, 1118 void *value, 1119 enum GNUNET_CONTAINER_MultiHashMapOption opt); 1120 1121 1122 /** 1123 * @ingroup hashmap 1124 * Get the number of key-value pairs in the map. 1125 * 1126 * @param map the map 1127 * @return the number of key value pairs 1128 */ 1129 unsigned int 1130 GNUNET_CONTAINER_multishortmap_size ( 1131 const struct GNUNET_CONTAINER_MultiShortmap *map); 1132 1133 1134 /** 1135 * @ingroup hashmap 1136 * Iterate over all entries in the map. 1137 * 1138 * @param map the map 1139 * @param it function to call on each entry 1140 * @param it_cls extra argument to @a it 1141 * @return the number of key value pairs processed, 1142 * #GNUNET_SYSERR if it aborted iteration 1143 */ 1144 int 1145 GNUNET_CONTAINER_multishortmap_iterate ( 1146 struct GNUNET_CONTAINER_MultiShortmap *map, 1147 GNUNET_CONTAINER_ShortmapIterator it, 1148 void *it_cls); 1149 1150 1151 struct GNUNET_CONTAINER_MultiShortmapIterator; 1152 1153 1154 /** 1155 * @ingroup hashmap 1156 * Create an iterator for a multihashmap. 1157 * The iterator can be used to retrieve all the elements in the multihashmap 1158 * one by one, without having to handle all elements at once (in contrast to 1159 * #GNUNET_CONTAINER_multishortmap_iterate). Note that the iterator can not be 1160 * used anymore if elements have been removed from @a map after the creation of 1161 * the iterator, or 'map' has been destroyed. Adding elements to @a map may 1162 * result in skipped or repeated elements. 1163 * 1164 * @param map the map to create an iterator for 1165 * @return an iterator over the given multihashmap @a map 1166 */ 1167 struct GNUNET_CONTAINER_MultiShortmapIterator * 1168 GNUNET_CONTAINER_multishortmap_iterator_create ( 1169 const struct GNUNET_CONTAINER_MultiShortmap *map); 1170 1171 1172 /** 1173 * @ingroup hashmap 1174 * Retrieve the next element from the hash map at the iterator's 1175 * position. If there are no elements left, #GNUNET_NO is returned, 1176 * and @a key and @a value are not modified. This operation is only 1177 * allowed if no elements have been removed from the multihashmap 1178 * since the creation of @a iter, and the map has not been destroyed. 1179 * Adding elements may result in repeating or skipping elements. 1180 * 1181 * @param iter the iterator to get the next element from 1182 * @param key pointer to store the key in, can be NULL 1183 * @param value pointer to store the value in, can be NULL 1184 * @return #GNUNET_YES we returned an element, 1185 * #GNUNET_NO if we are out of elements 1186 */ 1187 enum GNUNET_GenericReturnValue 1188 GNUNET_CONTAINER_multishortmap_iterator_next ( 1189 struct GNUNET_CONTAINER_MultiShortmapIterator *iter, 1190 struct GNUNET_ShortHashCode *key, 1191 const void **value); 1192 1193 1194 /** 1195 * @ingroup hashmap 1196 * Destroy a multishortmap iterator. 1197 * 1198 * @param iter the iterator to destroy 1199 */ 1200 void 1201 GNUNET_CONTAINER_multishortmap_iterator_destroy ( 1202 struct GNUNET_CONTAINER_MultiShortmapIterator *iter); 1203 1204 1205 /** 1206 * @ingroup hashmap 1207 * Iterate over all entries in the map that match a particular key. 1208 * 1209 * @param map the map 1210 * @param key public key that the entries must correspond to 1211 * @param it function to call on each entry 1212 * @param it_cls extra argument to @a it 1213 * @return the number of key value pairs processed, 1214 * #GNUNET_SYSERR if it aborted iteration 1215 */ 1216 int 1217 GNUNET_CONTAINER_multishortmap_get_multiple ( 1218 struct GNUNET_CONTAINER_MultiShortmap *map, 1219 const struct GNUNET_ShortHashCode *key, 1220 GNUNET_CONTAINER_ShortmapIterator it, 1221 void *it_cls); 1222 1223 1224 /** 1225 * @ingroup hashmap 1226 * Call @a it on a random value from the map, or not at all 1227 * if the map is empty. Note that this function has linear 1228 * complexity (in the size of the map). 1229 * 1230 * @param map the map 1231 * @param it function to call on a random entry 1232 * @param it_cls extra argument to @a it 1233 * @return the number of key value pairs processed, zero or one. 1234 */ 1235 unsigned int 1236 GNUNET_CONTAINER_multishortmap_get_random ( 1237 const struct GNUNET_CONTAINER_MultiShortmap *map, 1238 GNUNET_CONTAINER_ShortmapIterator it, 1239 void *it_cls); 1240 1241 1242 /* ***************** Version of Multihashmap for UUIDs ****************** */ 1243 1244 1245 /** 1246 * @ingroup hashmap 1247 * Iterator over uuid map entries. 1248 * 1249 * @param cls closure 1250 * @param key current public key 1251 * @param value value in the hash map 1252 * @return #GNUNET_YES if we should continue to 1253 * iterate, 1254 * #GNUNET_NO if not. 1255 */ 1256 typedef enum GNUNET_GenericReturnValue 1257 (*GNUNET_CONTAINER_MultiUuidmapIteratorCallback)( 1258 void *cls, 1259 const struct GNUNET_Uuid *key, 1260 void *value); 1261 1262 1263 /** 1264 * Hash map from peer identities to values. 1265 */ 1266 struct GNUNET_CONTAINER_MultiUuidmap; 1267 1268 1269 /** 1270 * @ingroup hashmap 1271 * Create a multi peer map (hash map for public keys of peers). 1272 * 1273 * @param len initial size (map will grow as needed) 1274 * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default; 1275 * #GNUNET_YES means that on 'put', the 'key' does not have 1276 * to be copied as the destination of the pointer is 1277 * guaranteed to be life as long as the value is stored in 1278 * the hashmap. This can significantly reduce memory 1279 * consumption, but of course is also a recipe for 1280 * heap corruption if the assumption is not true. Only 1281 * use this if (1) memory use is important in this case and 1282 * (2) you have triple-checked that the invariant holds 1283 * @return NULL on error 1284 */ 1285 struct GNUNET_CONTAINER_MultiUuidmap * 1286 GNUNET_CONTAINER_multiuuidmap_create (unsigned int len, int do_not_copy_keys); 1287 1288 1289 /** 1290 * @ingroup hashmap 1291 * Destroy a hash map. Will not free any values 1292 * stored in the hash map! 1293 * 1294 * @param map the map 1295 */ 1296 void 1297 GNUNET_CONTAINER_multiuuidmap_destroy ( 1298 struct GNUNET_CONTAINER_MultiUuidmap *map); 1299 1300 1301 /** 1302 * @ingroup hashmap 1303 * Given a key find a value in the map matching the key. 1304 * 1305 * @param map the map 1306 * @param key what to look for 1307 * @return NULL if no value was found; note that 1308 * this is indistinguishable from values that just 1309 * happen to be NULL; use "contains" to test for 1310 * key-value pairs with value NULL 1311 */ 1312 void * 1313 GNUNET_CONTAINER_multiuuidmap_get ( 1314 const struct GNUNET_CONTAINER_MultiUuidmap *map, 1315 const struct GNUNET_Uuid *key); 1316 1317 1318 /** 1319 * @ingroup hashmap 1320 * Remove the given key-value pair from the map. Note that if the 1321 * key-value pair is in the map multiple times, only one of the pairs 1322 * will be removed. 1323 * 1324 * @param map the map 1325 * @param key key of the key-value pair 1326 * @param value value of the key-value pair 1327 * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair 1328 * is not in the map 1329 */ 1330 enum GNUNET_GenericReturnValue 1331 GNUNET_CONTAINER_multiuuidmap_remove (struct GNUNET_CONTAINER_MultiUuidmap *map, 1332 const struct GNUNET_Uuid *key, 1333 const void *value); 1334 1335 /** 1336 * @ingroup hashmap 1337 * Remove all entries for the given key from the map. 1338 * Note that the values would not be "freed". 1339 * 1340 * @param map the map 1341 * @param key identifies values to be removed 1342 * @return number of values removed 1343 */ 1344 int 1345 GNUNET_CONTAINER_multiuuidmap_remove_all ( 1346 struct GNUNET_CONTAINER_MultiUuidmap *map, 1347 const struct GNUNET_Uuid *key); 1348 1349 1350 /** 1351 * @ingroup hashmap 1352 * Check if the map contains any value under the given 1353 * key (including values that are NULL). 1354 * 1355 * @param map the map 1356 * @param key the key to test if a value exists for it 1357 * @return #GNUNET_YES if such a value exists, 1358 * #GNUNET_NO if not 1359 */ 1360 enum GNUNET_GenericReturnValue 1361 GNUNET_CONTAINER_multiuuidmap_contains ( 1362 const struct GNUNET_CONTAINER_MultiUuidmap *map, 1363 const struct GNUNET_Uuid *key); 1364 1365 1366 /** 1367 * @ingroup hashmap 1368 * Check if the map contains the given value under the given 1369 * key. 1370 * 1371 * @param map the map 1372 * @param key the key to test if a value exists for it 1373 * @param value value to test for 1374 * @return #GNUNET_YES if such a value exists, 1375 * #GNUNET_NO if not 1376 */ 1377 enum GNUNET_GenericReturnValue 1378 GNUNET_CONTAINER_multiuuidmap_contains_value ( 1379 const struct GNUNET_CONTAINER_MultiUuidmap *map, 1380 const struct GNUNET_Uuid *key, 1381 const void *value); 1382 1383 1384 /** 1385 * @ingroup hashmap 1386 * Store a key-value pair in the map. 1387 * 1388 * @param map the map 1389 * @param key key to use 1390 * @param value value to use 1391 * @param opt options for put 1392 * @return #GNUNET_OK on success, 1393 * #GNUNET_NO if a value was replaced (with REPLACE) 1394 * #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the 1395 * value already exists 1396 */ 1397 enum GNUNET_GenericReturnValue 1398 GNUNET_CONTAINER_multiuuidmap_put ( 1399 struct GNUNET_CONTAINER_MultiUuidmap *map, 1400 const struct GNUNET_Uuid *key, 1401 void *value, 1402 enum GNUNET_CONTAINER_MultiHashMapOption opt); 1403 1404 1405 /** 1406 * @ingroup hashmap 1407 * Get the number of key-value pairs in the map. 1408 * 1409 * @param map the map 1410 * @return the number of key value pairs 1411 */ 1412 unsigned int 1413 GNUNET_CONTAINER_multiuuidmap_size ( 1414 const struct GNUNET_CONTAINER_MultiUuidmap *map); 1415 1416 1417 /** 1418 * @ingroup hashmap 1419 * Iterate over all entries in the map. 1420 * 1421 * @param map the map 1422 * @param it function to call on each entry 1423 * @param it_cls extra argument to @a it 1424 * @return the number of key value pairs processed, 1425 * #GNUNET_SYSERR if it aborted iteration 1426 */ 1427 enum GNUNET_GenericReturnValue 1428 GNUNET_CONTAINER_multiuuidmap_iterate ( 1429 struct GNUNET_CONTAINER_MultiUuidmap *map, 1430 GNUNET_CONTAINER_MultiUuidmapIteratorCallback it, 1431 void *it_cls); 1432 1433 1434 struct GNUNET_CONTAINER_MultiUuidmapIterator; 1435 1436 1437 /** 1438 * @ingroup hashmap 1439 * Create an iterator for a multihashmap. 1440 * The iterator can be used to retrieve all the elements in the multihashmap 1441 * one by one, without having to handle all elements at once (in contrast to 1442 * #GNUNET_CONTAINER_multiuuidmap_iterate). Note that the iterator can not be 1443 * used anymore if elements have been removed from @a map after the creation of 1444 * the iterator, or 'map' has been destroyed. Adding elements to @a map may 1445 * result in skipped or repeated elements. 1446 * 1447 * @param map the map to create an iterator for 1448 * @return an iterator over the given multihashmap @a map 1449 */ 1450 struct GNUNET_CONTAINER_MultiUuidmapIterator * 1451 GNUNET_CONTAINER_multiuuidmap_iterator_create ( 1452 const struct GNUNET_CONTAINER_MultiUuidmap *map); 1453 1454 1455 /** 1456 * @ingroup hashmap 1457 * Retrieve the next element from the hash map at the iterator's 1458 * position. If there are no elements left, #GNUNET_NO is returned, 1459 * and @a key and @a value are not modified. This operation is only 1460 * allowed if no elements have been removed from the multihashmap 1461 * since the creation of @a iter, and the map has not been destroyed. 1462 * Adding elements may result in repeating or skipping elements. 1463 * 1464 * @param iter the iterator to get the next element from 1465 * @param key pointer to store the key in, can be NULL 1466 * @param value pointer to store the value in, can be NULL 1467 * @return #GNUNET_YES we returned an element, 1468 * #GNUNET_NO if we are out of elements 1469 */ 1470 enum GNUNET_GenericReturnValue 1471 GNUNET_CONTAINER_multiuuidmap_iterator_next ( 1472 struct GNUNET_CONTAINER_MultiUuidmapIterator *iter, 1473 struct GNUNET_Uuid *key, 1474 const void **value); 1475 1476 1477 /** 1478 * @ingroup hashmap 1479 * Destroy a multiuuidmap iterator. 1480 * 1481 * @param iter the iterator to destroy 1482 */ 1483 void 1484 GNUNET_CONTAINER_multiuuidmap_iterator_destroy ( 1485 struct GNUNET_CONTAINER_MultiUuidmapIterator *iter); 1486 1487 1488 /** 1489 * @ingroup hashmap 1490 * Iterate over all entries in the map that match a particular key. 1491 * 1492 * @param map the map 1493 * @param key public key that the entries must correspond to 1494 * @param it function to call on each entry 1495 * @param it_cls extra argument to @a it 1496 * @return the number of key value pairs processed, 1497 * #GNUNET_SYSERR if it aborted iteration 1498 */ 1499 int 1500 GNUNET_CONTAINER_multiuuidmap_get_multiple ( 1501 struct GNUNET_CONTAINER_MultiUuidmap *map, 1502 const struct GNUNET_Uuid *key, 1503 GNUNET_CONTAINER_MultiUuidmapIteratorCallback it, 1504 void *it_cls); 1505 1506 1507 /** 1508 * @ingroup hashmap 1509 * Call @a it on a random value from the map, or not at all 1510 * if the map is empty. Note that this function has linear 1511 * complexity (in the size of the map). 1512 * 1513 * @param map the map 1514 * @param it function to call on a random entry 1515 * @param it_cls extra argument to @a it 1516 * @return the number of key value pairs processed, zero or one. 1517 */ 1518 unsigned int 1519 GNUNET_CONTAINER_multiuuidmap_get_random ( 1520 const struct GNUNET_CONTAINER_MultiUuidmap *map, 1521 GNUNET_CONTAINER_MultiUuidmapIteratorCallback it, 1522 void *it_cls); 1523 1524 1525 /* Version of multihashmap with 32 bit keys */ 1526 1527 /** 1528 * @ingroup hashmap 1529 * Opaque handle for the 32-bit key HashMap. 1530 */ 1531 struct GNUNET_CONTAINER_MultiHashMap32; 1532 1533 1534 /** 1535 * @ingroup hashmap 1536 * Opaque handle to an iterator over 1537 * a 32-bit key multihashmap. 1538 */ 1539 struct GNUNET_CONTAINER_MultiHashMap32Iterator; 1540 1541 1542 /** 1543 * @ingroup hashmap 1544 * Iterator over hash map entries. 1545 * 1546 * @param cls closure 1547 * @param key current key code 1548 * @param value value in the hash map 1549 * @return #GNUNET_YES if we should continue to 1550 * iterate, 1551 * #GNUNET_NO if not. 1552 */ 1553 typedef enum GNUNET_GenericReturnValue 1554 (*GNUNET_CONTAINER_MultiHashMapIterator32Callback)( 1555 void *cls, 1556 uint32_t key, 1557 void *value); 1558 1559 1560 /** 1561 * @ingroup hashmap 1562 * Create a 32-bit key multi hash map. 1563 * 1564 * @param len initial size (map will grow as needed) 1565 * @return NULL on error 1566 */ 1567 struct GNUNET_CONTAINER_MultiHashMap32 * 1568 GNUNET_CONTAINER_multihashmap32_create (unsigned int len); 1569 1570 1571 /** 1572 * @ingroup hashmap 1573 * Destroy a 32-bit key hash map. Will not free any values 1574 * stored in the hash map! 1575 * 1576 * @param map the map 1577 */ 1578 void 1579 GNUNET_CONTAINER_multihashmap32_destroy ( 1580 struct GNUNET_CONTAINER_MultiHashMap32 *map); 1581 1582 1583 /** 1584 * @ingroup hashmap 1585 * Get the number of key-value pairs in the map. 1586 * 1587 * @param map the map 1588 * @return the number of key value pairs 1589 */ 1590 unsigned int 1591 GNUNET_CONTAINER_multihashmap32_size ( 1592 const struct GNUNET_CONTAINER_MultiHashMap32 *map); 1593 1594 1595 /** 1596 * @ingroup hashmap 1597 * Given a key find a value in the map matching the key. 1598 * 1599 * @param map the map 1600 * @param key what to look for 1601 * @return NULL if no value was found; note that 1602 * this is indistinguishable from values that just 1603 * happen to be NULL; use "contains" to test for 1604 * key-value pairs with value NULL 1605 */ 1606 void * 1607 GNUNET_CONTAINER_multihashmap32_get ( 1608 const struct GNUNET_CONTAINER_MultiHashMap32 *map, 1609 uint32_t key); 1610 1611 1612 /** 1613 * @ingroup hashmap 1614 * Iterate over all entries in the map. 1615 * 1616 * @param map the map 1617 * @param it function to call on each entry 1618 * @param it_cls extra argument to @a it 1619 * @return the number of key value pairs processed, 1620 * #GNUNET_SYSERR if it aborted iteration 1621 */ 1622 int 1623 GNUNET_CONTAINER_multihashmap32_iterate ( 1624 struct GNUNET_CONTAINER_MultiHashMap32 *map, 1625 GNUNET_CONTAINER_MultiHashMapIterator32Callback it, 1626 void *it_cls); 1627 1628 1629 /** 1630 * @ingroup hashmap 1631 * Remove the given key-value pair from the map. Note that if the 1632 * key-value pair is in the map multiple times, only one of the pairs 1633 * will be removed. 1634 * 1635 * @param map the map 1636 * @param key key of the key-value pair 1637 * @param value value of the key-value pair 1638 * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair 1639 * is not in the map 1640 */ 1641 enum GNUNET_GenericReturnValue 1642 GNUNET_CONTAINER_multihashmap32_remove ( 1643 struct GNUNET_CONTAINER_MultiHashMap32 *map, 1644 uint32_t key, 1645 const void *value); 1646 1647 1648 /** 1649 * @ingroup hashmap 1650 * Remove all entries for the given key from the map. 1651 * Note that the values would not be "freed". 1652 * 1653 * @param map the map 1654 * @param key identifies values to be removed 1655 * @return number of values removed 1656 */ 1657 int 1658 GNUNET_CONTAINER_multihashmap32_remove_all ( 1659 struct GNUNET_CONTAINER_MultiHashMap32 *map, 1660 uint32_t key); 1661 1662 1663 /** 1664 * @ingroup hashmap 1665 * Check if the map contains any value under the given 1666 * key (including values that are NULL). 1667 * 1668 * @param map the map 1669 * @param key the key to test if a value exists for it 1670 * @return #GNUNET_YES if such a value exists, 1671 * #GNUNET_NO if not 1672 */ 1673 enum GNUNET_GenericReturnValue 1674 GNUNET_CONTAINER_multihashmap32_contains ( 1675 const struct GNUNET_CONTAINER_MultiHashMap32 *map, 1676 uint32_t key); 1677 1678 1679 /** 1680 * @ingroup hashmap 1681 * Check if the map contains the given value under the given 1682 * key. 1683 * 1684 * @param map the map 1685 * @param key the key to test if a value exists for it 1686 * @param value value to test for 1687 * @return #GNUNET_YES if such a value exists, 1688 * #GNUNET_NO if not 1689 */ 1690 enum GNUNET_GenericReturnValue 1691 GNUNET_CONTAINER_multihashmap32_contains_value ( 1692 const struct GNUNET_CONTAINER_MultiHashMap32 *map, 1693 uint32_t key, 1694 const void *value); 1695 1696 1697 /** 1698 * @ingroup hashmap 1699 * Store a key-value pair in the map. 1700 * 1701 * @param map the map 1702 * @param key key to use 1703 * @param value value to use 1704 * @param opt options for put 1705 * @return #GNUNET_OK on success, 1706 * #GNUNET_NO if a value was replaced (with REPLACE) 1707 * #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the 1708 * value already exists 1709 */ 1710 enum GNUNET_GenericReturnValue 1711 GNUNET_CONTAINER_multihashmap32_put ( 1712 struct GNUNET_CONTAINER_MultiHashMap32 *map, 1713 uint32_t key, 1714 void *value, 1715 enum GNUNET_CONTAINER_MultiHashMapOption opt); 1716 1717 1718 /** 1719 * @ingroup hashmap 1720 * Iterate over all entries in the map that match a particular key. 1721 * 1722 * @param map the map 1723 * @param key key that the entries must correspond to 1724 * @param it function to call on each entry 1725 * @param it_cls extra argument to @a it 1726 * @return the number of key value pairs processed, 1727 * #GNUNET_SYSERR if it aborted iteration 1728 */ 1729 int 1730 GNUNET_CONTAINER_multihashmap32_get_multiple ( 1731 struct GNUNET_CONTAINER_MultiHashMap32 *map, 1732 uint32_t key, 1733 GNUNET_CONTAINER_MultiHashMapIterator32Callback it, 1734 void *it_cls); 1735 1736 1737 /** 1738 * Create an iterator for a 32-bit multihashmap. 1739 * The iterator can be used to retrieve all the elements in the multihashmap 1740 * one by one, without having to handle all elements at once (in contrast to 1741 * #GNUNET_CONTAINER_multihashmap32_iterate). Note that the iterator can not be 1742 * used anymore if elements have been removed from 'map' after the creation of 1743 * the iterator, or 'map' has been destroyed. Adding elements to 'map' may 1744 * result in skipped or repeated elements. 1745 * 1746 * @param map the map to create an iterator for 1747 * @return an iterator over the given multihashmap map 1748 */ 1749 struct GNUNET_CONTAINER_MultiHashMap32Iterator * 1750 GNUNET_CONTAINER_multihashmap32_iterator_create ( 1751 const struct GNUNET_CONTAINER_MultiHashMap32 *map); 1752 1753 1754 /** 1755 * Retrieve the next element from the hash map at the iterator's position. 1756 * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value' 1757 * are not modified. 1758 * This operation is only allowed if no elements have been removed from the 1759 * multihashmap since the creation of 'iter', and the map has not been destroyed. 1760 * Adding elements may result in repeating or skipping elements. 1761 * 1762 * @param iter the iterator to get the next element from 1763 * @param key pointer to store the key in, can be NULL 1764 * @param value pointer to store the value in, can be NULL 1765 * @return #GNUNET_YES we returned an element, 1766 * #GNUNET_NO if we are out of elements 1767 */ 1768 enum GNUNET_GenericReturnValue 1769 GNUNET_CONTAINER_multihashmap32_iterator_next ( 1770 struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter, 1771 uint32_t *key, 1772 const void **value); 1773 1774 1775 /** 1776 * Destroy a 32-bit multihashmap iterator. 1777 * 1778 * @param iter the iterator to destroy 1779 */ 1780 void 1781 GNUNET_CONTAINER_multihashmap32_iterator_destroy ( 1782 struct GNUNET_CONTAINER_MultiHashMapIterator *iter); 1783 1784 1785 /* ******************** doubly-linked list *************** */ 1786 /* To avoid mistakes: head->prev == tail->next == NULL */ 1787 1788 /** 1789 * @ingroup dll 1790 * Insert an element at the head of a DLL. Assumes that head, tail and 1791 * element are structs with prev and next fields. 1792 * 1793 * @param head pointer to the head of the DLL 1794 * @param tail pointer to the tail of the DLL 1795 * @param element element to insert 1796 */ 1797 #define GNUNET_CONTAINER_DLL_insert(head, tail, element) \ 1798 do \ 1799 { \ 1800 GNUNET_assert ((NULL == (head)) == (NULL == (tail))); \ 1801 GNUNET_assert ((NULL == (element)->prev) && ((head) != (element))); \ 1802 GNUNET_assert ((NULL == (element)->next) && ((tail) != (element))); \ 1803 (element)->next = (head); \ 1804 (element)->prev = NULL; \ 1805 if (NULL == (tail)) \ 1806 (tail) = element; \ 1807 else \ 1808 (head)->prev = element; \ 1809 (head) = (element); \ 1810 } while (0) 1811 1812 1813 /** 1814 * @ingroup dll 1815 * Insert an element at the tail of a DLL. Assumes that head, tail and 1816 * element are structs with prev and next fields. 1817 * 1818 * @param head pointer to the head of the DLL 1819 * @param tail pointer to the tail of the DLL 1820 * @param element element to insert 1821 */ 1822 #define GNUNET_CONTAINER_DLL_insert_tail(head, tail, element) \ 1823 do \ 1824 { \ 1825 GNUNET_assert ((NULL == (head)) == (NULL == (tail))); \ 1826 GNUNET_assert ((NULL == (element)->prev) && ((head) != (element))); \ 1827 GNUNET_assert ((NULL == (element)->next) && ((tail) != (element))); \ 1828 (element)->prev = (tail); \ 1829 (element)->next = NULL; \ 1830 if (NULL == (head)) \ 1831 (head) = element; \ 1832 else \ 1833 (tail)->next = element; \ 1834 (tail) = (element); \ 1835 } while (0) 1836 1837 1838 /** 1839 * @ingroup dll 1840 * Insert an element into a DLL after the given other element. Insert 1841 * at the head if the other element is NULL. 1842 * 1843 * @param head pointer to the head of the DLL 1844 * @param tail pointer to the tail of the DLL 1845 * @param other prior element, NULL for insertion at head of DLL 1846 * @param element element to insert 1847 */ 1848 #define GNUNET_CONTAINER_DLL_insert_after(head, tail, other, element) \ 1849 do \ 1850 { \ 1851 GNUNET_assert ((NULL == (head)) == (NULL == (tail))); \ 1852 GNUNET_assert ((NULL == (element)->prev) && ((head) != (element))); \ 1853 GNUNET_assert ((NULL == (element)->next) && ((tail) != (element))); \ 1854 (element)->prev = (other); \ 1855 if (NULL == other) \ 1856 { \ 1857 (element)->next = (head); \ 1858 (head) = (element); \ 1859 } \ 1860 else \ 1861 { \ 1862 (element)->next = (other)->next; \ 1863 (other)->next = (element); \ 1864 } \ 1865 if (NULL == (element)->next) \ 1866 (tail) = (element); \ 1867 else \ 1868 (element)->next->prev = (element); \ 1869 } while (0) 1870 1871 1872 /** 1873 * @ingroup dll 1874 * Insert an element into a DLL before the given other element. Insert 1875 * at the tail if the other element is NULL. 1876 * 1877 * @param head pointer to the head of the DLL 1878 * @param tail pointer to the tail of the DLL 1879 * @param other prior element, NULL for insertion at head of DLL 1880 * @param element element to insert 1881 */ 1882 #define GNUNET_CONTAINER_DLL_insert_before(head, tail, other, element) \ 1883 do \ 1884 { \ 1885 GNUNET_assert ((NULL == (head)) == (NULL == (tail))); \ 1886 GNUNET_assert ((NULL == (element)->prev) && ((head) != (element))); \ 1887 GNUNET_assert ((NULL == (element)->next) && ((tail) != (element))); \ 1888 (element)->next = (other); \ 1889 if (NULL == other) \ 1890 { \ 1891 (element)->prev = (tail); \ 1892 (tail) = (element); \ 1893 } \ 1894 else \ 1895 { \ 1896 (element)->prev = (other)->prev; \ 1897 (other)->prev = (element); \ 1898 } \ 1899 if (NULL == (element)->prev) \ 1900 (head) = (element); \ 1901 else \ 1902 (element)->prev->next = (element); \ 1903 } while (0) 1904 1905 1906 /** 1907 * @ingroup dll 1908 * Remove an element from a DLL. Assumes that head, tail and 1909 * element point to structs with prev and next fields. 1910 * 1911 * Using the head or tail pointer as the element 1912 * argument does NOT work with this macro. 1913 * Make sure to store head/tail in another pointer 1914 * and use it to remove the head or tail of the list. 1915 * 1916 * @param head pointer to the head of the DLL 1917 * @param tail pointer to the tail of the DLL 1918 * @param element element to remove 1919 */ 1920 #define GNUNET_CONTAINER_DLL_remove(head, tail, element) \ 1921 do \ 1922 { \ 1923 GNUNET_assert ((NULL != (element)->prev) || ((head) == (element))); \ 1924 GNUNET_assert ((NULL != (element)->next) || ((tail) == (element))); \ 1925 if (NULL == (element)->prev) \ 1926 (head) = (element)->next; \ 1927 else \ 1928 (element)->prev->next = (element)->next; \ 1929 if (NULL == (element)->next) \ 1930 (tail) = (element)->prev; \ 1931 else \ 1932 (element)->next->prev = (element)->prev; \ 1933 (element)->next = NULL; \ 1934 (element)->prev = NULL; \ 1935 } while (0) 1936 1937 1938 /* ************ Multi-DLL interface, allows DLL elements to be 1939 in multiple lists at the same time *********************** */ 1940 1941 /** 1942 * @ingroup dll 1943 * Insert an element at the head of a MDLL. Assumes that head, tail and 1944 * element are structs with prev and next fields. 1945 * 1946 * @param mdll suffix name for the next and prev pointers in the element 1947 * @param head pointer to the head of the MDLL 1948 * @param tail pointer to the tail of the MDLL 1949 * @param element element to insert 1950 */ 1951 #define GNUNET_CONTAINER_MDLL_insert(mdll, head, tail, element) \ 1952 do \ 1953 { \ 1954 GNUNET_assert ((NULL == (head)) == (NULL == (tail))); \ 1955 GNUNET_assert ((NULL == (element)->prev_ ## mdll) && ((head) != (element))); \ 1956 GNUNET_assert ((NULL == (element)->next_ ## mdll) && ((tail) != (element))); \ 1957 (element)->next_ ## mdll = (head); \ 1958 (element)->prev_ ## mdll = NULL; \ 1959 if (NULL == (tail)) \ 1960 (tail) = element; \ 1961 else \ 1962 (head)->prev_ ## mdll = element; \ 1963 (head) = (element); \ 1964 } while (0) 1965 1966 1967 /** 1968 * @ingroup dll 1969 * Insert an element at the tail of a MDLL. Assumes that head, tail and 1970 * element are structs with prev and next fields. 1971 * 1972 * @param mdll suffix name for the next and prev pointers in the element 1973 * @param head pointer to the head of the MDLL 1974 * @param tail pointer to the tail of the MDLL 1975 * @param element element to insert 1976 */ 1977 #define GNUNET_CONTAINER_MDLL_insert_tail(mdll, head, tail, element) \ 1978 do \ 1979 { \ 1980 GNUNET_assert ((NULL == (head)) == (NULL == (tail))); \ 1981 GNUNET_assert ((NULL == (element)->prev_ ## mdll) && ((head) != (element))); \ 1982 GNUNET_assert ((NULL == (element)->next_ ## mdll) && ((tail) != (element))); \ 1983 (element)->prev_ ## mdll = (tail); \ 1984 (element)->next_ ## mdll = NULL; \ 1985 if (NULL == (head)) \ 1986 (head) = element; \ 1987 else \ 1988 (tail)->next_ ## mdll = element; \ 1989 (tail) = (element); \ 1990 } while (0) 1991 1992 1993 /** 1994 * @ingroup dll 1995 * Insert an element into a MDLL after the given other element. Insert 1996 * at the head if the other element is NULL. 1997 * 1998 * @param mdll suffix name for the next and prev pointers in the element 1999 * @param head pointer to the head of the MDLL 2000 * @param tail pointer to the tail of the MDLL 2001 * @param other prior element, NULL for insertion at head of MDLL 2002 * @param element element to insert 2003 */ 2004 #define GNUNET_CONTAINER_MDLL_insert_after(mdll, head, tail, other, element) \ 2005 do \ 2006 { \ 2007 GNUNET_assert ((NULL == (head)) == (NULL == (tail))); \ 2008 GNUNET_assert ((NULL == (element)->prev_ ## mdll) && ((head) != (element))); \ 2009 GNUNET_assert ((NULL == (element)->next_ ## mdll) && ((tail) != (element))); \ 2010 (element)->prev_ ## mdll = (other); \ 2011 if (NULL == other) \ 2012 { \ 2013 (element)->next_ ## mdll = (head); \ 2014 (head) = (element); \ 2015 } \ 2016 else \ 2017 { \ 2018 (element)->next_ ## mdll = (other)->next_ ## mdll; \ 2019 (other)->next_ ## mdll = (element); \ 2020 } \ 2021 if (NULL == (element)->next_ ## mdll) \ 2022 (tail) = (element); \ 2023 else \ 2024 (element)->next_ ## mdll->prev_ ## mdll = (element); \ 2025 } while (0) 2026 2027 2028 /** 2029 * @ingroup dll 2030 * Insert an element into a MDLL before the given other element. Insert 2031 * at the tail if the other element is NULL. 2032 * 2033 * @param mdll suffix name for the next and prev pointers in the element 2034 * @param head pointer to the head of the MDLL 2035 * @param tail pointer to the tail of the MDLL 2036 * @param other prior element, NULL for insertion at head of MDLL 2037 * @param element element to insert 2038 */ 2039 #define GNUNET_CONTAINER_MDLL_insert_before(mdll, head, tail, other, element) \ 2040 do \ 2041 { \ 2042 GNUNET_assert ((NULL == (head)) == (NULL == (tail))); \ 2043 GNUNET_assert (((element)->prev_ ## mdll == NULL) && ((head) != (element))); \ 2044 GNUNET_assert (((element)->next_ ## mdll == NULL) && ((tail) != (element))); \ 2045 (element)->next_ ## mdll = (other); \ 2046 if (NULL == other) \ 2047 { \ 2048 (element)->prev = (tail); \ 2049 (tail) = (element); \ 2050 } \ 2051 else \ 2052 { \ 2053 (element)->prev_ ## mdll = (other)->prev_ ## mdll; \ 2054 (other)->prev_ ## mdll = (element); \ 2055 } \ 2056 if (NULL == (element)->prev_ ## mdll) \ 2057 (head) = (element); \ 2058 else \ 2059 (element)->prev_ ## mdll->next_ ## mdll = (element); \ 2060 } while (0) 2061 2062 2063 /** 2064 * @ingroup dll 2065 * Remove an element from a MDLL. Assumes 2066 * that head, tail and element are structs 2067 * with prev and next fields. 2068 * 2069 * @param mdll suffix name for the next and prev pointers in the element 2070 * @param head pointer to the head of the MDLL 2071 * @param tail pointer to the tail of the MDLL 2072 * @param element element to remove 2073 */ 2074 #define GNUNET_CONTAINER_MDLL_remove(mdll, head, tail, element) \ 2075 do \ 2076 { \ 2077 GNUNET_assert ((NULL != (element)->prev_ ## mdll) || ((head) == (element))); \ 2078 GNUNET_assert ((NULL != (element)->next_ ## mdll) || ((tail) == (element))); \ 2079 if (NULL == (element)->prev_ ## mdll) \ 2080 (head) = (element)->next_ ## mdll; \ 2081 else \ 2082 (element)->prev_ ## mdll->next_ ## mdll = (element)->next_ ## mdll; \ 2083 if (NULL == (element)->next_ ## mdll) \ 2084 (tail) = (element)->prev_ ## mdll; \ 2085 else \ 2086 (element)->next_ ## mdll->prev_ ## mdll = (element)->prev_ ## mdll; \ 2087 (element)->next_ ## mdll = NULL; \ 2088 (element)->prev_ ## mdll = NULL; \ 2089 } while (0) 2090 2091 2092 /** 2093 * Insertion sort of @a element into DLL from @a head to @a tail 2094 * sorted by @a comparator. 2095 * 2096 * @param TYPE element type of the elements, e.g. `struct ListElement` 2097 * @param comparator function like memcmp() to compare elements; takes 2098 * three arguments, the @a comparator_cls and two elements, 2099 * returns an `int` (-1, 0 or 1) 2100 * @param comparator_cls closure for @a comparator 2101 * @param[in,out] head head of DLL 2102 * @param[in,out] tail tail of DLL 2103 * @param element element to insert 2104 */ 2105 #define GNUNET_CONTAINER_DLL_insert_sorted(TYPE, \ 2106 comparator, \ 2107 comparator_cls, \ 2108 head, \ 2109 tail, \ 2110 element) \ 2111 do \ 2112 { \ 2113 if ((NULL == head) || (0 < comparator (comparator_cls, element, head))) \ 2114 { \ 2115 /* insert at head, element < head */ \ 2116 GNUNET_CONTAINER_DLL_insert (head, tail, element); \ 2117 } \ 2118 else \ 2119 { \ 2120 TYPE *pos; \ 2121 \ 2122 for (pos = head; NULL != pos; pos = pos->next) \ 2123 if (0 < comparator (comparator_cls, element, pos)) \ 2124 break; /* element < pos */ \ 2125 if (NULL == pos) /* => element > tail */ \ 2126 { \ 2127 GNUNET_CONTAINER_DLL_insert_tail (head, tail, element); \ 2128 } \ 2129 else /* prev < element < pos */ \ 2130 { \ 2131 GNUNET_CONTAINER_DLL_insert_after (head, tail, pos->prev, element); \ 2132 } \ 2133 } \ 2134 } while (0) 2135 2136 2137 /* ******************** Heap *************** */ 2138 2139 2140 /** 2141 * @ingroup heap 2142 * Cost by which elements in a heap can be ordered. 2143 */ 2144 typedef uint64_t GNUNET_CONTAINER_HeapCostType; 2145 2146 2147 /** 2148 * @ingroup heap 2149 * Heap type, either max or min. 2150 */ 2151 enum GNUNET_CONTAINER_HeapOrder 2152 { 2153 /** 2154 * @ingroup heap 2155 * Heap with the maximum cost at the root. 2156 */ 2157 GNUNET_CONTAINER_HEAP_ORDER_MAX, 2158 2159 /** 2160 * @ingroup heap 2161 * Heap with the minimum cost at the root. 2162 */ 2163 GNUNET_CONTAINER_HEAP_ORDER_MIN 2164 }; 2165 2166 2167 /** 2168 * @ingroup heap 2169 * Handle to a Heap. 2170 */ 2171 struct GNUNET_CONTAINER_Heap; 2172 2173 2174 /** 2175 * @ingroup heap 2176 * Handle to a node in a heap. 2177 */ 2178 struct GNUNET_CONTAINER_HeapNode; 2179 2180 2181 /** 2182 * @ingroup heap 2183 * Create a new heap. 2184 * 2185 * @param order how should the heap be sorted? 2186 * @return handle to the heap 2187 */ 2188 struct GNUNET_CONTAINER_Heap * 2189 GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order); 2190 2191 2192 /** 2193 * @ingroup heap 2194 * Destroys the heap. Only call on a heap that 2195 * is already empty. 2196 * 2197 * @param heap heap to destroy 2198 */ 2199 void 2200 GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap); 2201 2202 2203 /** 2204 * @ingroup heap 2205 * Get element stored at the root of @a heap. 2206 * 2207 * @param heap Heap to inspect. 2208 * @return Element at the root, or NULL if heap is empty. 2209 */ 2210 void * 2211 GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap); 2212 2213 2214 /** 2215 * Get @a element and @a cost stored at the root of @a heap. 2216 * 2217 * @param[in] heap Heap to inspect. 2218 * @param[out] element Root element is returned here. 2219 * @param[out] cost Cost of @a element is returned here. 2220 * @return #GNUNET_YES if an element is returned, 2221 * #GNUNET_NO if the heap is empty. 2222 */ 2223 enum GNUNET_GenericReturnValue 2224 GNUNET_CONTAINER_heap_peek2 (const struct GNUNET_CONTAINER_Heap *heap, 2225 void **element, 2226 GNUNET_CONTAINER_HeapCostType *cost); 2227 2228 2229 /** 2230 * @ingroup heap 2231 * Get the current size of the heap 2232 * 2233 * @param heap the heap to get the size of 2234 * @return number of elements stored 2235 */ 2236 unsigned int 2237 GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap); 2238 2239 2240 /** 2241 * @ingroup heap 2242 * Get the current cost of the node 2243 * 2244 * @param node the node to get the cost of 2245 * @return cost of the node 2246 */ 2247 GNUNET_CONTAINER_HeapCostType 2248 GNUNET_CONTAINER_heap_node_get_cost ( 2249 const struct GNUNET_CONTAINER_HeapNode *node); 2250 2251 2252 /** 2253 * @ingroup heap 2254 * Iterator for heap 2255 * 2256 * @param cls closure 2257 * @param node internal node of the heap 2258 * @param element value stored at the node 2259 * @param cost cost associated with the node 2260 * @return #GNUNET_YES if we should continue to iterate, 2261 * #GNUNET_NO if not. 2262 */ 2263 typedef enum GNUNET_GenericReturnValue 2264 (*GNUNET_CONTAINER_HeapIterator)( 2265 void *cls, 2266 struct GNUNET_CONTAINER_HeapNode *node, 2267 void *element, 2268 GNUNET_CONTAINER_HeapCostType cost); 2269 2270 2271 /** 2272 * @ingroup heap 2273 * Iterate over all entries in the heap. 2274 * 2275 * @param heap the heap 2276 * @param iterator function to call on each entry 2277 * @param iterator_cls closure for @a iterator 2278 */ 2279 void 2280 GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap, 2281 GNUNET_CONTAINER_HeapIterator iterator, 2282 void *iterator_cls); 2283 2284 /** 2285 * @ingroup heap 2286 * Perform a random walk of the tree. The walk is biased 2287 * towards elements closer to the root of the tree (since 2288 * each walk starts at the root and ends at a random leaf). 2289 * The heap internally tracks the current position of the 2290 * walk. 2291 * 2292 * @param heap heap to walk 2293 * @return data stored at the next random node in the walk; 2294 * NULL if the tree is empty. 2295 */ 2296 void * 2297 GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap); 2298 2299 2300 /** 2301 * @ingroup heap 2302 * Inserts a new element into the heap. 2303 * 2304 * @param heap heap to modify 2305 * @param element element to insert 2306 * @param cost cost for the element 2307 * @return node for the new element 2308 */ 2309 struct GNUNET_CONTAINER_HeapNode * 2310 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, 2311 void *element, 2312 GNUNET_CONTAINER_HeapCostType cost); 2313 2314 2315 /** 2316 * @ingroup heap 2317 * Remove root of the heap. 2318 * 2319 * @param heap heap to modify 2320 * @return element data stored at the root node 2321 */ 2322 void * 2323 GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap); 2324 2325 2326 /** 2327 * @ingroup heap 2328 * Removes a node from the heap. 2329 * 2330 * @param node node to remove 2331 * @return element data stored at the node, NULL if heap is empty 2332 */ 2333 void * 2334 GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node); 2335 2336 2337 /** 2338 * @ingroup heap 2339 * Updates the cost of any node in the tree 2340 * 2341 * @param node node for which the cost is to be changed 2342 * @param new_cost new cost for the node 2343 */ 2344 void 2345 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_HeapNode *node, 2346 GNUNET_CONTAINER_HeapCostType new_cost); 2347 2348 2349 #if 0 /* keep Emacsens' auto-indent happy */ 2350 { 2351 #endif 2352 #ifdef __cplusplus 2353 } 2354 #endif 2355 2356 2357 /* ifndef GNUNET_CONTAINER_LIB_H */ 2358 #endif 2359 2360 /** @} */ /* end of group addition */ 2361 2362 /* end of gnunet_container_lib.h */