GNUnet 0.29.1-19-g7e0f9c364
 
Loading...
Searching...
No Matches
gnunet_container_lib.h
Go to the documentation of this file.
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
56#include "gnunet_common.h"
57#if ! defined (__GNUNET_UTIL_LIB_H_INSIDE__)
58#error "Only <gnunet_util_lib.h> can be included directly."
59#endif
60
61#ifndef GNUNET_CONTAINER_LIB_H
62#define GNUNET_CONTAINER_LIB_H
63
64#ifdef __cplusplus
65extern "C" {
66#if 0 /* keep Emacsens' auto-indent happy */
67}
68#endif
69#endif
70
71
72/* add error and config prototypes */
73
74#include "gnunet_crypto_lib.h"
75
76
92int
93GNUNET_try_compression (const char *data,
94 size_t old_size,
95 char **result,
96 size_t *new_size);
97
98
109char *
110GNUNET_decompress (const char *input, size_t input_size, size_t output_size);
111
112
113/* ******************* bloomfilter ***************** */
114
120
121
131typedef int (*GNUNET_CONTAINER_HashCodeIterator) (void *cls,
132 struct GNUNET_HashCode *next);
133
134
149 size_t size,
150 unsigned int k);
151
152
169 size_t size,
170 unsigned int k);
171
172
184 const struct GNUNET_CONTAINER_BloomFilter *bf,
185 char *data,
186 size_t size);
187
188
197bool
199 const struct GNUNET_CONTAINER_BloomFilter *bf,
200 const struct GNUNET_HashCode *e);
201
202
210void
212 const struct GNUNET_HashCode *e);
213
214
222void
224 const struct GNUNET_HashCode *e);
225
226
236 const struct GNUNET_CONTAINER_BloomFilter *bf);
237
238
247void
249
250
257size_t
259 const struct GNUNET_CONTAINER_BloomFilter *bf);
260
261
269size_t
271 const struct GNUNET_CONTAINER_BloomFilter *bf);
272
273
280void
282
283
298 const char *data,
299 size_t size);
300
301
315 const struct GNUNET_CONTAINER_BloomFilter *to_or);
316
317
330void
333 void *iterator_cls,
334 size_t size,
335 unsigned int k);
336
337
338/* ******************************* HashMap **************************** */
339
340#include "gnunet_hashmap_lib.h"
341
342
343/* ******************** doubly-linked list *************** */
344/* To avoid mistakes: head->prev == tail->next == NULL */
345
355#define GNUNET_CONTAINER_DLL_insert(head, tail, element) \
356 do \
357 { \
358 GNUNET_assert ((NULL == (head)) == (NULL == (tail))); \
359 GNUNET_assert ((NULL == (element)->prev) && ((head) != (element))); \
360 GNUNET_assert ((NULL == (element)->next) && ((tail) != (element))); \
361 (element)->next = (head); \
362 (element)->prev = NULL; \
363 if (NULL == (tail)) \
364 { \
365 (tail) = element; \
366 } \
367 else \
368 { \
369 (head)->prev = element; \
370 } \
371 (head) = (element); \
372 } while (0)
373
374
384#define GNUNET_CONTAINER_DLL_insert_tail(head, tail, element) \
385 do \
386 { \
387 GNUNET_assert ((NULL == (head)) == (NULL == (tail))); \
388 GNUNET_assert ((NULL == (element)->prev) && ((head) != (element))); \
389 GNUNET_assert ((NULL == (element)->next) && ((tail) != (element))); \
390 (element)->prev = (tail); \
391 (element)->next = NULL; \
392 if (NULL == (head)) \
393 { \
394 (head) = element; \
395 } \
396 else \
397 { \
398 (tail)->next = element; \
399 } \
400 (tail) = (element); \
401 } while (0)
402
403
414#define GNUNET_CONTAINER_DLL_insert_after(head, tail, other, element) \
415 do \
416 { \
417 GNUNET_assert ((NULL == (head)) == (NULL == (tail))); \
418 GNUNET_assert ((NULL == (element)->prev) && ((head) != (element))); \
419 GNUNET_assert ((NULL == (element)->next) && ((tail) != (element))); \
420 (element)->prev = (other); \
421 if (NULL == other) \
422 { \
423 (element)->next = (head); \
424 (head) = (element); \
425 } \
426 else \
427 { \
428 (element)->next = (other)->next; \
429 (other)->next = (element); \
430 } \
431 if (NULL == (element)->next) \
432 { \
433 (tail) = (element); \
434 } \
435 else \
436 { \
437 (element)->next->prev = (element); \
438 } \
439 } while (0)
440
441
452#define GNUNET_CONTAINER_DLL_insert_before(head, tail, other, element) \
453 do \
454 { \
455 GNUNET_assert ((NULL == (head)) == (NULL == (tail))); \
456 GNUNET_assert ((NULL == (element)->prev) && ((head) != (element))); \
457 GNUNET_assert ((NULL == (element)->next) && ((tail) != (element))); \
458 (element)->next = (other); \
459 if (NULL == other) \
460 { \
461 (element)->prev = (tail); \
462 (tail) = (element); \
463 } \
464 else \
465 { \
466 (element)->prev = (other)->prev; \
467 (other)->prev = (element); \
468 } \
469 if (NULL == (element)->prev) \
470 { \
471 (head) = (element); \
472 } \
473 else \
474 { \
475 (element)->prev->next = (element); \
476 } \
477 } while (0)
478
479
494#define GNUNET_CONTAINER_DLL_remove(head, tail, element) \
495 do \
496 { \
497 GNUNET_assert ((NULL != (element)->prev) || ((head) == (element))); \
498 GNUNET_assert ((NULL != (element)->next) || ((tail) == (element))); \
499 if (NULL == (element)->prev) \
500 { \
501 (head) = (element)->next; \
502 } \
503 else \
504 { \
505 (element)->prev->next = (element)->next; \
506 } \
507 if (NULL == (element)->next) \
508 { \
509 (tail) = (element)->prev; \
510 } \
511 else \
512 { \
513 (element)->next->prev = (element)->prev; \
514 } \
515 (element)->next = NULL; \
516 (element)->prev = NULL; \
517 } while (0)
518
519
520/* ************ Multi-DLL interface, allows DLL elements to be
521 in multiple lists at the same time *********************** */
522
533#define GNUNET_CONTAINER_MDLL_insert(mdll, head, tail, element) \
534 do \
535 { \
536 GNUNET_assert ((NULL == (head)) == (NULL == (tail))); \
537 GNUNET_assert ((NULL == (element)->prev_ ## mdll) && \
538 ((head) != (element))); \
539 GNUNET_assert ((NULL == (element)->next_ ## mdll) && \
540 ((tail) != (element))); \
541 (element)->next_ ## mdll = (head); \
542 (element)->prev_ ## mdll = NULL; \
543 if (NULL == (tail)) \
544 { \
545 (tail) = element; \
546 } \
547 else \
548 { \
549 (head)->prev_ ## mdll = element; \
550 } \
551 (head) = (element); \
552 } while (0)
553
554
565#define GNUNET_CONTAINER_MDLL_insert_tail(mdll, head, tail, element) \
566 do \
567 { \
568 GNUNET_assert ((NULL == (head)) == (NULL == (tail))); \
569 GNUNET_assert ((NULL == (element)->prev_ ## mdll) && \
570 ((head) != (element))); \
571 GNUNET_assert ((NULL == (element)->next_ ## mdll) && \
572 ((tail) != (element))); \
573 (element)->prev_ ## mdll = (tail); \
574 (element)->next_ ## mdll = NULL; \
575 if (NULL == (head)) \
576 { \
577 (head) = element; \
578 } \
579 else \
580 { \
581 (tail)->next_ ## mdll = element; \
582 } \
583 (tail) = (element); \
584 } while (0)
585
586
598#define GNUNET_CONTAINER_MDLL_insert_after(mdll, head, tail, other, element) \
599 do \
600 { \
601 GNUNET_assert ((NULL == (head)) == (NULL == (tail))); \
602 GNUNET_assert ((NULL == (element)->prev_ ## mdll) && \
603 ((head) != (element))); \
604 GNUNET_assert ((NULL == (element)->next_ ## mdll) && \
605 ((tail) != (element))); \
606 (element)->prev_ ## mdll = (other); \
607 if (NULL == other) \
608 { \
609 (element)->next_ ## mdll = (head); \
610 (head) = (element); \
611 } \
612 else \
613 { \
614 (element)->next_ ## mdll = (other)->next_ ## mdll; \
615 (other)->next_ ## mdll = (element); \
616 } \
617 if (NULL == (element)->next_ ## mdll) \
618 { \
619 (tail) = (element); \
620 } \
621 else \
622 { \
623 (element)->next_ ## mdll->prev_ ## mdll = (element); \
624 } \
625 } while (0)
626
627
639#define GNUNET_CONTAINER_MDLL_insert_before(mdll, head, tail, other, element) \
640 do \
641 { \
642 GNUNET_assert ((NULL == (head)) == (NULL == (tail))); \
643 GNUNET_assert (((element)->prev_ ## mdll == NULL) && \
644 ((head) != (element))); \
645 GNUNET_assert (((element)->next_ ## mdll == NULL) && \
646 ((tail) != (element))); \
647 (element)->next_ ## mdll = (other); \
648 if (NULL == other) \
649 { \
650 (element)->prev_ ## mdll = (tail); \
651 (tail) = (element); \
652 } \
653 else \
654 { \
655 (element)->prev_ ## mdll = (other)->prev_ ## mdll; \
656 (other)->prev_ ## mdll = (element); \
657 } \
658 if (NULL == (element)->prev_ ## mdll) \
659 { \
660 (head) = (element); \
661 } \
662 else \
663 { \
664 (element)->prev_ ## mdll->next_ ## mdll = (element); \
665 } \
666 } while (0)
667
668
680#define GNUNET_CONTAINER_MDLL_remove(mdll, head, tail, element) \
681 do \
682 { \
683 GNUNET_assert ((NULL != (element)->prev_ ## mdll) || \
684 ((head) == (element))); \
685 GNUNET_assert ((NULL != (element)->next_ ## mdll) || \
686 ((tail) == (element))); \
687 if (NULL == (element)->prev_ ## mdll) \
688 { \
689 (head) = (element)->next_ ## mdll; \
690 } \
691 else \
692 { \
693 (element)->prev_ ## mdll->next_ ## mdll = \
694 (element)->next_ ## mdll; \
695 } \
696 if (NULL == (element)->next_ ## mdll) \
697 { \
698 (tail) = (element)->prev_ ## mdll; \
699 } \
700 else \
701 { \
702 (element)->next_ ## mdll->prev_ ## mdll = \
703 (element)->prev_ ## mdll; \
704 } \
705 (element)->next_ ## mdll = NULL; \
706 (element)->prev_ ## mdll = NULL; \
707 } while (0)
708
709
723#define GNUNET_CONTAINER_DLL_insert_sorted(TYPE, \
724 comparator, \
725 comparator_cls, \
726 head, \
727 tail, \
728 element) \
729 do \
730 { \
731 if ((NULL == head) || \
732 (0 < comparator (comparator_cls, element, head))) \
733 { \
734 /* insert at head, element < head */ \
735 GNUNET_CONTAINER_DLL_insert (head, tail, element); \
736 } \
737 else \
738 { \
739 TYPE *pos; \
740 \
741 for (pos = head; NULL != pos; pos = pos->next) \
742 { \
743 if (0 < comparator (comparator_cls, element, pos)) \
744 { \
745 break; /* element < pos */ \
746 } \
747 } \
748 if (NULL == pos) /* => element > tail */ \
749 { \
750 GNUNET_CONTAINER_DLL_insert_tail (head, tail, element); \
751 } \
752 else /* prev < element < pos */ \
753 { \
754 GNUNET_CONTAINER_DLL_insert_after (head, \
755 tail, \
756 pos->prev, \
757 element); \
758 } \
759 } \
760 } while (0)
761
762
763/* ******************** Heap *************** */
764
765
771
772
791
792
798
799
805
806
816
817
825void
827
828
836void *
838
839
851 void **element,
853
854
862unsigned int
864
865
875 const struct GNUNET_CONTAINER_HeapNode *node);
876
877
889typedef enum GNUNET_GenericReturnValue
891 void *cls,
892 struct GNUNET_CONTAINER_HeapNode *node,
893 void *element,
895
896
906void
909 void *iterator_cls);
910
923void *
925
926
938 void *element,
940
941
949void *
951
952
960void *
962
963
971void
974
975
976#if 0 /* keep Emacsens' auto-indent happy */
977{
978#endif
979#ifdef __cplusplus
980}
981#endif
982
983
984/* ifndef GNUNET_CONTAINER_LIB_H */
985#endif
986
/* end of group addition */
988
989/* end of gnunet_container_lib.h */
static char * data
The data to insert into the dht.
static char * filename
static int result
Global testing status.
commonly used definitions; globals in this file are exempt from the rule that the module name ("commo...
cryptographic primitives for GNUnet
Hash maps with multiple values per key.
void GNUNET_CONTAINER_bloomfilter_resize(struct GNUNET_CONTAINER_BloomFilter *bf, GNUNET_CONTAINER_HashCodeIterator iterator, void *iterator_cls, size_t size, unsigned int k)
Resize a bloom filter.
struct GNUNET_CONTAINER_BloomFilter * GNUNET_CONTAINER_bloomfilter_init(const char *data, size_t size, unsigned int k)
Create a Bloom filter from raw bits.
void GNUNET_CONTAINER_bloomfilter_add(struct GNUNET_CONTAINER_BloomFilter *bf, const struct GNUNET_HashCode *e)
Add an element to the filter.
bool GNUNET_CONTAINER_bloomfilter_test(const struct GNUNET_CONTAINER_BloomFilter *bf, const struct GNUNET_HashCode *e)
Test if an element is in the filter.
struct GNUNET_CONTAINER_BloomFilter * GNUNET_CONTAINER_bloomfilter_copy(const struct GNUNET_CONTAINER_BloomFilter *bf)
Create a copy of a bloomfilter.
void GNUNET_CONTAINER_bloomfilter_clear(struct GNUNET_CONTAINER_BloomFilter *bf)
Reset a Bloom filter to empty.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_bloomfilter_get_raw_data(const struct GNUNET_CONTAINER_BloomFilter *bf, char *data, size_t size)
Copy the raw data of this Bloom filter into the given data array.
int(* GNUNET_CONTAINER_HashCodeIterator)(void *cls, struct GNUNET_HashCode *next)
Iterator over struct GNUNET_HashCode.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_bloomfilter_or2(struct GNUNET_CONTAINER_BloomFilter *bf, const struct GNUNET_CONTAINER_BloomFilter *to_or)
"or" the entries of the given raw data array with the data of the given Bloom filter.
struct GNUNET_CONTAINER_BloomFilter * GNUNET_CONTAINER_bloomfilter_load(const char *filename, size_t size, unsigned int k)
Load a Bloom filter from a file.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_bloomfilter_or(struct GNUNET_CONTAINER_BloomFilter *bf, const char *data, size_t size)
"or" the entries of the given raw data array with the data of the given Bloom filter.
size_t GNUNET_CONTAINER_bloomfilter_get_size(const struct GNUNET_CONTAINER_BloomFilter *bf)
Get size of the bloom filter.
void GNUNET_CONTAINER_bloomfilter_remove(struct GNUNET_CONTAINER_BloomFilter *bf, const struct GNUNET_HashCode *e)
Remove an element from the filter.
void GNUNET_CONTAINER_bloomfilter_free(struct GNUNET_CONTAINER_BloomFilter *bf)
Free the space associated with a filter in memory, flush to drive if needed (do not free the space on...
void * GNUNET_CONTAINER_heap_remove_node(struct GNUNET_CONTAINER_HeapNode *node)
Removes a node from the heap.
void * GNUNET_CONTAINER_heap_peek(const struct GNUNET_CONTAINER_Heap *heap)
Get element stored at the root of heap.
GNUNET_CONTAINER_HeapOrder
Heap type, either max or min.
GNUNET_CONTAINER_HeapCostType GNUNET_CONTAINER_heap_node_get_cost(const struct GNUNET_CONTAINER_HeapNode *node)
Get the current cost of the node.
void * GNUNET_CONTAINER_heap_remove_root(struct GNUNET_CONTAINER_Heap *heap)
Remove root of the heap.
void GNUNET_CONTAINER_heap_update_cost(struct GNUNET_CONTAINER_HeapNode *node, GNUNET_CONTAINER_HeapCostType new_cost)
Updates the cost of any node in the tree.
struct GNUNET_CONTAINER_HeapNode * GNUNET_CONTAINER_heap_insert(struct GNUNET_CONTAINER_Heap *heap, void *element, GNUNET_CONTAINER_HeapCostType cost)
Inserts a new element into the heap.
enum GNUNET_GenericReturnValue(* GNUNET_CONTAINER_HeapIterator)(void *cls, struct GNUNET_CONTAINER_HeapNode *node, void *element, GNUNET_CONTAINER_HeapCostType cost)
Iterator for heap.
unsigned int GNUNET_CONTAINER_heap_get_size(const struct GNUNET_CONTAINER_Heap *heap)
Get the current size of the heap.
void GNUNET_CONTAINER_heap_iterate(const struct GNUNET_CONTAINER_Heap *heap, GNUNET_CONTAINER_HeapIterator iterator, void *iterator_cls)
Iterate over all entries in the heap, in no particular order.
uint64_t GNUNET_CONTAINER_HeapCostType
Cost by which elements in a heap can be ordered.
struct GNUNET_CONTAINER_Heap * GNUNET_CONTAINER_heap_create(enum GNUNET_CONTAINER_HeapOrder order)
Create a new heap.
void GNUNET_CONTAINER_heap_destroy(struct GNUNET_CONTAINER_Heap *heap)
Destroys the heap.
void * GNUNET_CONTAINER_heap_walk_get_next(struct GNUNET_CONTAINER_Heap *heap)
Perform a random walk of the tree.
@ GNUNET_CONTAINER_HEAP_ORDER_MIN
Heap with the minimum cost at the root.
@ GNUNET_CONTAINER_HEAP_ORDER_MAX
Heap with the maximum cost at the root.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_heap_peek2(const struct GNUNET_CONTAINER_Heap *heap, void **element, GNUNET_CONTAINER_HeapCostType *cost)
Get element and cost stored at the root of heap.
char * GNUNET_decompress(const char *input, size_t input_size, size_t output_size)
Decompress input, return the decompressed data as output.
Definition compress.c:70
int GNUNET_try_compression(const char *data, size_t old_size, char **result, size_t *new_size)
Try to compress the given block of data using libz.
Definition compress.c:33
size_t GNUNET_CONTAINER_bloomfilter_get_element_addresses(const struct GNUNET_CONTAINER_BloomFilter *bf)
Get the number of the addresses set per element in the bloom filter.
GNUNET_GenericReturnValue
Named constants for return values.
static unsigned int size
Size of the "table".
Definition peer.c:68
Handle to an element in a heap.
void * element
Our element.
struct GNUNET_CONTAINER_Heap * heap
Heap this node belongs to.
Handle to a heap.
enum GNUNET_CONTAINER_HeapOrder order
How is the heap sorted?
A 512-bit hashcode.