aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/fs/gnunet-service-fs.c13
-rw-r--r--src/include/gnunet_container_lib.h161
-rw-r--r--src/util/container_heap.c856
-rw-r--r--src/util/test_container_heap.c97
4 files changed, 574 insertions, 553 deletions
diff --git a/src/fs/gnunet-service-fs.c b/src/fs/gnunet-service-fs.c
index bec69f6ec..ed68dcc4a 100644
--- a/src/fs/gnunet-service-fs.c
+++ b/src/fs/gnunet-service-fs.c
@@ -446,6 +446,11 @@ struct PendingRequest
446 GNUNET_HashCode *replies_seen; 446 GNUNET_HashCode *replies_seen;
447 447
448 /** 448 /**
449 * Node in the heap representing this entry.
450 */
451 struct GNUNET_CONTAINER_HeapNode *hnode;
452
453 /**
449 * When did we first see this request (form this peer), or, if our 454 * When did we first see this request (form this peer), or, if our
450 * client is initiating, when did we last initiate a search? 455 * client is initiating, when did we last initiate a search?
451 */ 456 */
@@ -2214,7 +2219,7 @@ destroy_pending_request (struct PendingRequest *pr)
2214 if (pr->client == NULL) 2219 if (pr->client == NULL)
2215 { 2220 {
2216 GNUNET_CONTAINER_heap_remove_node (requests_by_expiration, 2221 GNUNET_CONTAINER_heap_remove_node (requests_by_expiration,
2217 pr); 2222 pr->hnode);
2218 } 2223 }
2219 else 2224 else
2220 { 2225 {
@@ -2480,9 +2485,9 @@ forward_get_request (void *cls,
2480 &pgc->reply_to.hashPubKey, 2485 &pgc->reply_to.hashPubKey,
2481 pr, 2486 pr,
2482 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE); 2487 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
2483 GNUNET_CONTAINER_heap_insert (requests_by_expiration, 2488 pr->hnode = GNUNET_CONTAINER_heap_insert (requests_by_expiration,
2484 pr, 2489 pr,
2485 pr->start_time.value + pr->ttl); 2490 pr->start_time.value + pr->ttl);
2486 if (GNUNET_CONTAINER_heap_get_size (requests_by_expiration) > max_pending_requests) 2491 if (GNUNET_CONTAINER_heap_get_size (requests_by_expiration) > max_pending_requests)
2487 { 2492 {
2488 /* expire oldest request! */ 2493 /* expire oldest request! */
diff --git a/src/include/gnunet_container_lib.h b/src/include/gnunet_container_lib.h
index 1f707e44c..db9e10ef8 100644
--- a/src/include/gnunet_container_lib.h
+++ b/src/include/gnunet_container_lib.h
@@ -710,7 +710,7 @@ int GNUNET_CONTAINER_multihashmap_get_multiple (const struct
710/** 710/**
711 * Cost by which elements in a heap can be ordered. 711 * Cost by which elements in a heap can be ordered.
712 */ 712 */
713typedef uint64_t GNUNET_CONTAINER_HeapCost; 713typedef uint64_t GNUNET_CONTAINER_HeapCostType;
714 714
715 715
716/* 716/*
@@ -736,132 +736,145 @@ enum GNUNET_CONTAINER_HeapOrder
736 */ 736 */
737struct GNUNET_CONTAINER_Heap; 737struct GNUNET_CONTAINER_Heap;
738 738
739
740
741/**
742 * Handle to a node in a heap.
743 */
744struct GNUNET_CONTAINER_HeapNode;
745
746
739/** 747/**
740 * Create a new heap. 748 * Create a new heap.
741 * 749 *
742 * @param type should the minimum or the maximum element be the root 750 * @param order how should the heap be sorted?
743 * @return NULL on error, otherwise a fresh heap 751 * @return handle to the heap
744 */ 752 */
745struct GNUNET_CONTAINER_Heap *GNUNET_CONTAINER_heap_create (enum 753struct GNUNET_CONTAINER_Heap *
746 GNUNET_CONTAINER_HeapOrder 754GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order);
747 type);
748 755
749 756
750/** 757/**
751 * Free a heap 758 * Destroys the heap. Only call on a heap that
759 * is already empty.
752 * 760 *
753 * @param h heap to free. 761 * @param heap heap to destroy
754 */ 762 */
755void GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *h); 763void GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap);
756 764
757 765
758/** 766/**
759 * Function called on elements of a heap. 767 * Get element stored at root of heap.
760 * 768 *
761 * @param cls closure 769 * @param heap heap to inspect
762 * @param element obj stored in heap 770 * @return NULL if heap is empty
763 * @param cost cost of the element
764 * @return GNUNET_YES if we should continue to iterate,
765 * GNUNET_NO if not.
766 */ 771 */
767typedef int (*GNUNET_CONTAINER_HeapIterator) (void *cls, 772void *
768 void *element, 773GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap);
769 GNUNET_CONTAINER_HeapCost cost);
770 774
771 775
772/** 776/**
773 * Iterate over all entries in the map. 777 * Get the current size of the heap
774 * 778 *
775 * @param heap the heap 779 * @param heap the heap to get the size of
776 * @param iterator function to call on each entry 780 * @return number of elements stored
777 * @param iterator_cls closure for iterator
778 * @return number of items handled
779 * GNUNET_SYSERR if iteration was aborted by iterator
780 */ 781 */
781int GNUNET_CONTAINER_heap_iterate (struct GNUNET_CONTAINER_Heap *heap, 782unsigned int
782 GNUNET_CONTAINER_HeapIterator iterator, 783GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap);
783 void *iterator_cls);
784
785 784
786 785
787/** 786/**
788 * Inserts a new item into the heap, item is always neighbor now. 787 * Iterator for heap
789 * @param heap the heap 788 *
790 * @param element element to insert 789 * @param cls closure
791 * @param cost cost of the element 790 * @param node internal node of the heap
792 * @return FIXME 791 * @param element value stored at the node
792 * @param cost cost associated with the node
793 * @return GNUNET_YES if we should continue to iterate,
794 * GNUNET_NO if not.
793 */ 795 */
794int 796typedef int (*GNUNET_CONTAINER_HeapIterator) (void *cls,
795GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, 797 struct GNUNET_CONTAINER_HeapNode *node,
796 void *element, GNUNET_CONTAINER_HeapCost cost); 798 void *element,
799 GNUNET_CONTAINER_HeapCostType cost);
797 800
798 801
799/** 802/**
800 * Removes root of the tree, is remove max if a max heap and remove min 803 * Iterate over all entries in the heap.
801 * if a min heap, returns the data stored at the node.
802 * 804 *
803 * @param heap the heap 805 * @param heap the heap
804 * @return NULL if the heap is empty 806 * @param iterator function to call on each entry
807 * @param iterator_cls closure for iterator
805 */ 808 */
806void *GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap); 809void
810GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
811 GNUNET_CONTAINER_HeapIterator iterator,
812 void *iterator_cls);
807 813
808 814
809/** 815/**
810 * Returns element stored at root of tree, doesn't effect anything 816 * Perform a random walk of the tree. The walk is biased
817 * towards elements closer to the root of the tree (since
818 * each walk starts at the root and ends at a random leaf).
819 * The heap internally tracks the current position of the
820 * walk.
811 * 821 *
812 * @param heap the heap 822 * @param heap heap to walk
813 * @return NULL if the heap is empty 823 * @return data stored at the next random node in the walk;
824 * NULL if the tree is empty.
814 */ 825 */
815void *GNUNET_CONTAINER_heap_peek (struct GNUNET_CONTAINER_Heap *heap); 826void *
827GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap);
816 828
817 829
818/** 830/**
819 * Removes any node from the tree based on the neighbor given, does 831 * Inserts a new element into the heap.
820 * not traverse the tree (backpointers) but may take more time due to
821 * percolation of nodes.
822 * 832 *
823 * @param heap the heap 833 * @param heap heap to modify
824 * @param element the element to remove 834 * @param element element to insert
825 * @return NULL if "element" was not found in the heap, otherwise element 835 * @param cost cost for the element
836 * @return node for the new element
826 */ 837 */
827void *GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *heap, 838struct GNUNET_CONTAINER_HeapNode *
828 void *element); 839GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap,
840 void *element,
841 GNUNET_CONTAINER_HeapCostType cost);
829 842
830 843
831/** 844/**
832 * Updates the cost of any node in the tree 845 * Remove root of the heap.
833 * 846 *
834 * @param heap the heap 847 * @param heap heap to modify
835 * @param element the element for which the cost is updated 848 * @return element data stored at the root node
836 * @param new_cost new cost for the element
837 * @return FIXME
838 */ 849 */
839int 850void *
840GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap, 851GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap);
841 void *element,
842 GNUNET_CONTAINER_HeapCost new_cost);
843 852
844 853
845/** 854/**
846 * Random walk of the tree, returns the data stored at the next random node 855 * Removes a node from the heap.
847 * in the walk. Calls callee with the data, or NULL if the tree is empty 856 *
848 * or some other problem crops up. 857 * @param heap heap to modify
849 * 858 * @param node node to remove
850 * @param heap the heap 859 * @return element data stored at the node, NULL if heap is empty
851 * @return the next element from the random walk
852 */ 860 */
853void *GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap 861void *
854 *heap); 862GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *heap,
863 struct GNUNET_CONTAINER_HeapNode *node);
855 864
856 865
857/** 866/**
858 * Returns the current size of the heap 867 * Updates the cost of any node in the tree
859 * 868 *
860 * @param heap the heap to get the size of 869 * @param heap heap to modify
861 * @return number of elements in the heap 870 * @param node node for which the cost is to be changed
871 * @param new_cost new cost for the node
862 */ 872 */
863unsigned int 873void
864GNUNET_CONTAINER_heap_get_size (struct GNUNET_CONTAINER_Heap *heap); 874GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
875 struct GNUNET_CONTAINER_HeapNode *node,
876 GNUNET_CONTAINER_HeapCostType new_cost);
877
865 878
866/* ******************** Singly linked list *************** */ 879/* ******************** Singly linked list *************** */
867 880
diff --git a/src/util/container_heap.c b/src/util/container_heap.c
index 9c6005beb..dbb391ac4 100644
--- a/src/util/container_heap.c
+++ b/src/util/container_heap.c
@@ -1,540 +1,540 @@
1/* 1/*
2 This file is part of GNUnet. 2 This file is part of GNUnet.
3 (C) 2008 Christian Grothoff (and other contributing authors) 3 (C) 2008, 2009 Christian Grothoff (and other contributing authors)
4 4
5 GNUnet is free software; you can redistribute it and/or modify 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 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 7 by the Free Software Foundation; either version 2, or (at your
8 option) any later version. 8 option) any later version.
9 9
10 GNUnet is distributed in the hope that it will be useful, but 10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of 11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details. 13 General Public License for more details.
14 14
15 You should have received a copy of the GNU General Public License 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 16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 59 Temple Place - Suite 330, 17 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA. 18 Boston, MA 02111-1307, USA.
19 */ 19*/
20 20
21/** 21/**
22 * @author Nathan Evans
23 * @file util/container_heap.c 22 * @file util/container_heap.c
24 * @brief Implementation of heap operations 23 * @brief Implementation of a heap
24 * @author Nathan Evans
25 * @author Christian Grothoff
25 */ 26 */
26 27
27#include "platform.h" 28#include "platform.h"
28#include "gnunet_protocols.h"
29#include "gnunet_util_lib.h" 29#include "gnunet_util_lib.h"
30 30
31
32#define DEBUG 0
33
31/** 34/**
32 * Generic heap node structure, contains pointer to parent 35 * Node in the heap.
33 * left child, right child, and actual neighbor.
34 */ 36 */
35struct GNUNET_CONTAINER_heap_node 37struct GNUNET_CONTAINER_HeapNode
36{ 38{
37 struct GNUNET_CONTAINER_heap_node *parent; 39 /**
38 40 * Parent node.
39 struct GNUNET_CONTAINER_heap_node *left_child; 41 */
40 42 struct GNUNET_CONTAINER_HeapNode *parent;
41 struct GNUNET_CONTAINER_heap_node *right_child; 43
44 /**
45 * Left child.
46 */
47 struct GNUNET_CONTAINER_HeapNode *left_child;
48
49 /**
50 * Right child.
51 */
52 struct GNUNET_CONTAINER_HeapNode *right_child;
53
54 /**
55 * Our element.
56 */
57 void *element;
42 58
43 GNUNET_CONTAINER_HeapCost cost; 59 /**
60 * Cost for this element.
61 */
62 GNUNET_CONTAINER_HeapCostType cost;
44 63
45 void *element; 64 /**
65 * Number of elements below this node in the heap
66 * (excluding this node itself).
67 */
68 unsigned int tree_size;
46 69
47}; 70};
48 71
72/**
73 * Handle to a node in a heap.
74 */
49struct GNUNET_CONTAINER_Heap 75struct GNUNET_CONTAINER_Heap
50{ 76{
51 unsigned int size;
52
53 unsigned int max_size;
54 77
55 enum GNUNET_CONTAINER_HeapOrder type; 78 /**
79 * Root of the heap.
80 */
81 struct GNUNET_CONTAINER_HeapNode *root;
56 82
57 struct GNUNET_CONTAINER_heap_node *root; 83 /**
84 * Current position of our random walk.
85 */
86 struct GNUNET_CONTAINER_HeapNode *walk_pos;
58 87
59 struct GNUNET_CONTAINER_heap_node *traversal_pos; 88 /**
89 * Number of elements in the heap.
90 */
91 unsigned int size;
92
93 /**
94 * How is the heap sorted?
95 */
96 enum GNUNET_CONTAINER_HeapOrder order;
60 97
61}; 98};
62 99
63 100
101#if DEBUG
64/** 102/**
65 * Returns element stored at root of tree, doesn't effect anything 103 * Check if internal invariants hold for the given node.
66 * 104 *
67 * @param heap the heap 105 * @param node subtree to check
68 * @return NULL if the heap is empty 106 */
69 */
70void *
71GNUNET_CONTAINER_heap_peek (struct GNUNET_CONTAINER_Heap *heap)
72{
73 if ((heap == NULL) || (heap->root == NULL))
74 return NULL;
75
76 return heap->root->element;
77}
78
79static int
80next_power_of_2 (int v)
81{
82 v |= v >> 1;
83 v |= v >> 2;
84 v |= v >> 4;
85 v |= v >> 8;
86 v |= v >> 16;
87 v++;
88 return v;
89}
90
91#if 0
92static void 107static void
93internal_print (struct GNUNET_CONTAINER_heap_node *root) 108check (const struct GNUNET_CONTAINER_HeapNode *node)
94{ 109{
95 fprintf (stdout, "%llu\n", (unsigned long long) root->cost); 110 if (NULL == node)
96 if (root->left_child != NULL) 111 return;
97 { 112 GNUNET_assert (node->tree_size ==
98 fprintf (stdout, "LEFT of %llu\n", (unsigned long long) root->cost); 113 ( (node->left_child == NULL) ? 0 : 1 + node->left_child->tree_size) +
99 internal_print (root->left_child); 114 ( (node->right_child == NULL) ? 0 : 1 + node->right_child->tree_size) );
100 } 115 check (node->left_child);
101 if (root->right_child != NULL) 116 check (node->right_child);
102 {
103 fprintf (stdout, "RIGHT of %llu\n", (unsigned long long) root->cost);
104 internal_print (root->right_child);
105 }
106} 117}
107 118
108static void 119
109printTree (struct GNUNET_CONTAINER_Heap *root) 120#define CHECK(n) check(n)
110{ 121#else
111 internal_print (root->root); 122#define CHECK(n) do {} while (0)
112}
113#endif 123#endif
114 124
125
126/**
127 * Create a new heap.
128 *
129 * @param order how should the heap be sorted?
130 * @return handle to the heap
131 */
115struct GNUNET_CONTAINER_Heap * 132struct GNUNET_CONTAINER_Heap *
116GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder type) 133GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order)
117{ 134{
118 struct GNUNET_CONTAINER_Heap *heap; 135 struct GNUNET_CONTAINER_Heap *heap;
119 heap = malloc (sizeof (struct GNUNET_CONTAINER_Heap));
120 heap->max_size = -1;
121 heap->type = type;
122 heap->root = NULL;
123 heap->traversal_pos = NULL;
124 heap->size = 0;
125 136
137 heap = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_Heap));
138 heap->order = order;
126 return heap; 139 return heap;
127} 140}
128 141
142
143/**
144 * Destroys the heap. Only call on a heap that
145 * is already empty.
146 *
147 * @param heap heap to destroy
148 */
129void 149void
130GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap) 150GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap)
131{ 151{
132 while (heap->size > 0) 152 GNUNET_break (heap->size == 0);
133 GNUNET_CONTAINER_heap_remove_root (heap);
134 GNUNET_free (heap); 153 GNUNET_free (heap);
135} 154}
136 155
137static struct GNUNET_CONTAINER_heap_node * 156
138find_element (struct GNUNET_CONTAINER_heap_node *node, void *element) 157/**
158 * Get element stored at root of heap.
159 *
160 * @param heap heap to inspect
161 * @return NULL if heap is empty
162 */
163void *
164GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap)
139{ 165{
140 struct GNUNET_CONTAINER_heap_node *ret; 166 if (heap->root == NULL)
141 ret = NULL;
142 if (node == NULL)
143 return NULL; 167 return NULL;
144 168 return heap->root->element;
145 if (node->element == element)
146 return node;
147
148 if (node->left_child != NULL)
149 ret = find_element (node->left_child, element);
150
151 if ((ret == NULL) && (node->right_child != NULL))
152 ret = find_element (node->right_child, element);
153
154 return ret;
155} 169}
156 170
157static struct GNUNET_CONTAINER_heap_node *
158getNextPos (struct GNUNET_CONTAINER_Heap *root)
159{
160 struct GNUNET_CONTAINER_heap_node *ret;
161 struct GNUNET_CONTAINER_heap_node *parent;
162 int pos;
163 int i;
164
165 ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_heap_node));
166 pos = root->size + 1;
167 ret->left_child = NULL;
168 ret->right_child = NULL;
169
170 if (0 == root->size)
171 {
172 ret->parent = NULL;
173 root->root = ret;
174 }
175 else
176 {
177 parent = root->root;
178 for (i = next_power_of_2 (pos) >> 2; i > 1; i >>= 1)
179 {
180 if (((pos / i) % 2) == 0)
181 parent = parent->left_child;
182 else
183 parent = parent->right_child;
184 }
185
186 ret->parent = parent;
187 if ((pos % 2) == 0)
188 parent->left_child = ret;
189 else
190 parent->right_child = ret;
191
192 }
193
194 return ret;
195
196}
197 171
198static struct GNUNET_CONTAINER_heap_node * 172/**
199getPos (struct GNUNET_CONTAINER_Heap *root, unsigned int pos) 173 * Get the current size of the heap
174 *
175 * @param heap the heap to get the size of
176 * @return number of elements stored
177 */
178unsigned int
179GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap)
200{ 180{
201 struct GNUNET_CONTAINER_heap_node *ret; 181 return heap->size;
202 unsigned int i; 182}
203
204 ret = NULL;
205 if (pos > root->size)
206 {
207 return ret;
208 }
209 else
210 {
211 ret = root->root;
212 for (i = next_power_of_2 (pos) >> 2; i > 0; i >>= 1)
213 {
214 if (((pos / i) % 2) == 0)
215 ret = ret->left_child;
216 else
217 ret = ret->right_child;
218 }
219 }
220 183
221 return ret;
222 184
185/**
186 * Iterate over the children of the given node.
187 *
188 * @param heap argument to give to iterator
189 * @param node node to iterate over
190 * @param iterator function to call on each node
191 * @param iterator_cls closure for iterator
192 * @return GNUNET_YES to continue to iterate
193 */
194static int
195node_iterator (const struct GNUNET_CONTAINER_Heap *heap,
196 struct GNUNET_CONTAINER_HeapNode *node,
197 GNUNET_CONTAINER_HeapIterator iterator,
198 void *iterator_cls)
199{
200 if (node == NULL)
201 return GNUNET_YES;
202 if (GNUNET_YES != node_iterator (heap,
203 node->left_child,
204 iterator,
205 iterator_cls))
206 return GNUNET_NO;
207 if (GNUNET_YES != node_iterator (heap,
208 node->right_child,
209 iterator,
210 iterator_cls))
211 return GNUNET_NO;
212 return iterator (iterator_cls,
213 node,
214 node->element,
215 node->cost);
223} 216}
224 217
218
219/**
220 * Iterate over all entries in the heap.
221 *
222 * @param heap the heap
223 * @param iterator function to call on each entry
224 * @param iterator_cls closure for iterator
225 */
225void 226void
226swapNodes (struct GNUNET_CONTAINER_heap_node *first, 227GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
227 struct GNUNET_CONTAINER_heap_node *second, 228 GNUNET_CONTAINER_HeapIterator iterator,
228 struct GNUNET_CONTAINER_Heap *root) 229 void *iterator_cls)
229{ 230{
230 void *temp_element; 231 (void) node_iterator (heap, heap->root, iterator, iterator_cls);
231 GNUNET_CONTAINER_HeapCost temp_cost;
232
233 temp_element = first->element;
234 temp_cost = first->cost;
235 first->element = second->element;
236 first->cost = second->cost;
237 second->element = temp_element;
238 second->cost = temp_cost;
239
240 return;
241} 232}
242 233
243void
244percolateHeap (struct GNUNET_CONTAINER_heap_node *pos,
245 struct GNUNET_CONTAINER_Heap *root)
246{
247 234
248 while ((pos->parent != NULL) && 235/**
249 (((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX) 236 * Perform a random walk of the tree. The walk is biased
250 && (pos->parent->cost < pos->cost)) 237 * towards elements closer to the root of the tree (since
251 || ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN) 238 * each walk starts at the root and ends at a random leaf).
252 && (pos->parent->cost > pos->cost)))) 239 * The heap internally tracks the current position of the
253 { 240 * walk.
254 swapNodes (pos, pos->parent, root); 241 *
255 pos = pos->parent; 242 * @param heap heap to walk
256 } 243 * @return data stored at the next random node in the walk;
244 * NULL if the tree is empty.
245 */
246void *
247GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap)
248{
249 struct GNUNET_CONTAINER_HeapNode *pos;
250 void *element;
257 251
258 return; 252 if (heap->root == NULL)
253 return NULL;
254 pos = heap->walk_pos;
255 if (pos == NULL)
256 pos = heap->root;
257 element = pos->element;
258 heap->walk_pos
259 = (0 == GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, 2))
260 ? pos->right_child
261 : pos->left_child;
262 return element;
259} 263}
260 264
261 265
262 266/**
263void 267 * Insert the given node 'node' into the subtree starting
264percolateDownHeap (struct GNUNET_CONTAINER_heap_node *pos, 268 * at 'pos' (while keeping the tree somewhat balanced).
265 struct GNUNET_CONTAINER_Heap *root) 269 *
270 * @param pos existing tree
271 * @param node node to insert (which may be a subtree itself)
272 */
273static void
274insert_node (struct GNUNET_CONTAINER_Heap *heap,
275 struct GNUNET_CONTAINER_HeapNode *pos,
276 struct GNUNET_CONTAINER_HeapNode *node)
266{ 277{
267 struct GNUNET_CONTAINER_heap_node *switchNeighbor; 278 struct GNUNET_CONTAINER_HeapNode *parent;
268 279
269 switchNeighbor = pos; 280 GNUNET_assert (node->parent == NULL);
270 281 while ( (pos->cost < node->cost) ^ (heap->order == GNUNET_CONTAINER_HEAP_ORDER_MAX) )
271 if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX))
272 { 282 {
273 if ((pos->left_child != NULL) 283 /* node is descendent of pos */
274 && (pos->left_child->cost > switchNeighbor->cost)) 284 pos->tree_size += (1 + node->tree_size);
275 { 285 if (pos->left_child == NULL)
276 switchNeighbor = pos->left_child; 286 {
277 } 287 pos->left_child = node;
278 288 node->parent = pos;
279 if ((pos->right_child != NULL) 289 return;
280 && (pos->right_child->cost > switchNeighbor->cost)) 290 }
281 { 291 if (pos->right_child == NULL)
282 switchNeighbor = pos->right_child; 292 {
283 } 293 pos->right_child = node;
294 node->parent = pos;
295 return;
296 }
297 /* keep it balanced by descending into smaller subtree */
298 if (pos->left_child->tree_size < pos->right_child->tree_size)
299 pos = pos->left_child;
300 else
301 pos = pos->right_child;
284 } 302 }
285 else if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)) 303 /* make 'node' parent of 'pos' */
304 parent = pos->parent;
305 pos->parent = NULL;
306 node->parent = parent;
307 if (NULL == parent)
286 { 308 {
287 if ((pos->left_child != NULL) 309 heap->root = node;
288 && (pos->left_child->cost < switchNeighbor->cost))
289 {
290 switchNeighbor = pos->left_child;
291 }
292
293 if ((pos->right_child != NULL)
294 && (pos->right_child->cost < switchNeighbor->cost))
295 {
296 switchNeighbor = pos->right_child;
297 }
298 } 310 }
299 311 else
300 if (switchNeighbor != pos)
301 { 312 {
302 swapNodes (switchNeighbor, pos, root); 313 if (parent->left_child == pos)
303 percolateDownHeap (switchNeighbor, root); 314 parent->left_child = node;
315 else
316 parent->right_child = node;
304 } 317 }
318 /* insert 'pos' below 'node' */
319 insert_node (heap, node, pos);
320 CHECK (pos);
321}
322
305 323
306 return; 324/**
325 * Inserts a new element into the heap.
326 *
327 * @param heap heap to modify
328 * @param element element to insert
329 * @param cost cost for the element
330 * @return node for the new element
331 */
332struct GNUNET_CONTAINER_HeapNode *
333GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap,
334 void *element,
335 GNUNET_CONTAINER_HeapCostType cost)
336{
337 struct GNUNET_CONTAINER_HeapNode *node;
338
339 node = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_HeapNode));
340 node->element = element;
341 node->cost = cost;
342 heap->size++;
343 if (NULL == heap->root)
344 heap->root = node;
345 else
346 insert_node (heap, heap->root, node);
347 GNUNET_assert (heap->size == heap->root->tree_size + 1);
348 CHECK (heap->root);
349 return node;
307} 350}
308 351
352
353/**
354 * Remove root of the heap.
355 *
356 * @param heap heap to modify
357 * @return element data stored at the root node, NULL if heap is empty
358 */
309void * 359void *
310GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *root, 360GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap)
311 void *element)
312{ 361{
313 void *ret; 362 void *ret;
314 struct GNUNET_CONTAINER_heap_node *del_node; 363 struct GNUNET_CONTAINER_HeapNode *root;
315 struct GNUNET_CONTAINER_heap_node *last;
316 GNUNET_CONTAINER_HeapCost old_cost;
317 364
318 del_node = NULL; 365 if (NULL == (root = heap->root))
319 del_node = find_element (root->root, element);
320
321 if (del_node == NULL)
322 return NULL; 366 return NULL;
323 else if (del_node == root->root) 367 heap->size--;
324 return GNUNET_CONTAINER_heap_remove_root (root); 368 ret = root->element;
325 369 if (root->left_child == NULL)
326 ret = del_node->element;
327 last = getPos (root, root->size);
328
329 root->size--;
330
331 old_cost = del_node->cost;
332 del_node->element = last->element;
333 del_node->cost = last->cost;
334
335 if (last->parent->left_child == last)
336 last->parent->left_child = NULL;
337 if (last->parent->right_child == last)
338 last->parent->right_child = NULL;
339
340 if (root->traversal_pos == last)
341 { 370 {
342 root->traversal_pos = root->root; 371 heap->root = root->right_child;
372 if (root->right_child != NULL)
373 root->right_child->parent = NULL;
343 } 374 }
344 375 else if (root->right_child == NULL)
345 if (last == del_node)
346 {
347 GNUNET_free (last);
348 return ret;
349 }
350 GNUNET_free (last);
351
352
353 if (del_node->cost > old_cost)
354 { 376 {
355 if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX) 377 heap->root = root->left_child;
356 percolateHeap (del_node, root); 378 if (root->left_child != NULL)
357 else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN) 379 root->left_child->parent = NULL;
358 percolateDownHeap (del_node, root);
359 } 380 }
360 else if (del_node->cost < old_cost) 381 else
361 { 382 {
362 if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX) 383 root->left_child->parent = NULL;
363 percolateDownHeap (del_node, root); 384 root->right_child->parent = NULL;
364 else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN) 385 heap->root = root->left_child;
365 percolateHeap (del_node, root); 386 insert_node (heap, heap->root, root->right_child);
366 } 387 }
367 388 GNUNET_free (root);
389#if DEBUG
390 GNUNET_assert (( (heap->size == 0) &&
391 (heap->root == NULL) ) ||
392 (heap->size == heap->root->tree_size + 1) );
393 CHECK (heap->root);
394#endif
368 return ret; 395 return ret;
369} 396}
370 397
371int 398
372GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *root, 399/**
373 void *element, GNUNET_CONTAINER_HeapCost cost) 400 * Remove the given node 'node' from the tree and update
401 * the 'tree_size' fields accordingly. Preserves the
402 * children of 'node' and does NOT change the overall
403 * 'size' field of the tree.
404 */
405static void
406remove_node (struct GNUNET_CONTAINER_Heap *heap,
407 struct GNUNET_CONTAINER_HeapNode *node)
374{ 408{
375 struct GNUNET_CONTAINER_heap_node *new_pos; 409 struct GNUNET_CONTAINER_HeapNode *ancestor;
376 int ret;
377 ret = GNUNET_YES;
378 410
379 if (root->max_size > root->size) 411 /* update 'size' of the ancestors */
380 { 412 ancestor = node;
381 new_pos = getNextPos (root); 413 while (NULL != (ancestor = ancestor->parent))
382 new_pos->element = element; 414 ancestor->tree_size--;
383 new_pos->cost = cost; 415
384 root->size++; 416 /* update 'size' of node itself */
417 if (node->left_child != NULL)
418 node->tree_size -= (1 + node->left_child->tree_size);
419 if (node->right_child != NULL)
420 node->tree_size -= (1 + node->right_child->tree_size);
385 421
386 percolateHeap (new_pos, root); 422 /* unlink 'node' itself and insert children in its place */
423 if (node->parent == NULL)
424 {
425 if (node->left_child != NULL)
426 {
427 heap->root = node->left_child;
428 node->left_child->parent = NULL;
429 if (node->right_child != NULL)
430 {
431 node->right_child->parent = NULL;
432 insert_node (heap, heap->root, node->right_child);
433 }
434 }
435 else
436 {
437 heap->root = node->right_child;
438 if (node->right_child != NULL)
439 node->right_child->parent = NULL;
440 }
387 } 441 }
388 else 442 else
389 { 443 {
390 ret = GNUNET_NO; 444 if (node->parent->left_child == node)
445 node->parent->left_child = NULL;
446 else
447 node->parent->right_child = NULL;
448 if (node->left_child != NULL)
449 {
450 node->left_child->parent = NULL;
451 node->parent->tree_size -= (1 + node->left_child->tree_size);
452 insert_node (heap, node->parent, node->left_child);
453 }
454 if (node->right_child != NULL)
455 {
456 node->right_child->parent = NULL;
457 node->parent->tree_size -= (1 + node->right_child->tree_size);
458 insert_node (heap, node->parent, node->right_child);
459 }
391 } 460 }
392 461 node->parent = NULL;
393 return ret; 462 node->left_child = NULL;
463 node->right_child = NULL;
464 GNUNET_assert (node->tree_size == 0);
465 CHECK (heap->root);
394} 466}
395 467
468
469/**
470 * Removes a node from the heap.
471 *
472 * @param heap heap to modify
473 * @param node node to remove
474 * @return element data stored at the node
475 */
396void * 476void *
397GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *root) 477GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *heap,
478 struct GNUNET_CONTAINER_HeapNode *node)
398{ 479{
399 void *ret; 480 void *ret;
400 struct GNUNET_CONTAINER_heap_node *root_node; 481
401 struct GNUNET_CONTAINER_heap_node *last; 482 CHECK (heap->root);
402 483 if (heap->walk_pos == node)
403 if ((root == NULL) || (root->size == 0) || (root->root == NULL)) 484 (void) GNUNET_CONTAINER_heap_walk_get_next (heap);
404 { 485 remove_node (heap, node);
405 GNUNET_break (0); 486 heap->size--;
406 return NULL; 487 ret = node->element;
407 } 488 if (heap->walk_pos == node)
408 489 heap->walk_pos = NULL;
409 root_node = root->root; 490 GNUNET_free (node);
410 ret = root_node->element; 491#if DEBUG
411 last = getPos (root, root->size); 492 CHECK (heap->root);
412 493 GNUNET_assert (( (heap->size == 0) &&
413 if ((root_node == last) && (root->size == 1)) 494 (heap->root == NULL) ) ||
414 { 495 (heap->size == heap->root->tree_size + 1) );
415 /* We are removing the last node in the heap! */ 496#endif
416 GNUNET_free (last);
417 root->root = NULL;
418 root->traversal_pos = NULL;
419 GNUNET_assert (0 == --root->size);
420 return ret;
421 }
422
423 if (last->parent->left_child == last)
424 last->parent->left_child = NULL;
425 else if (last->parent->right_child == last)
426 last->parent->right_child = NULL;
427
428 root_node->element = last->element;
429 root_node->cost = last->cost;
430
431 if (root->traversal_pos == last)
432 root->traversal_pos = root->root;
433 GNUNET_free (last);
434 root->size--;
435 percolateDownHeap (root->root, root);
436 return ret; 497 return ret;
437} 498}
438 499
439static int
440updatedCost (struct GNUNET_CONTAINER_Heap *root,
441 struct GNUNET_CONTAINER_heap_node *node)
442{
443 struct GNUNET_CONTAINER_heap_node *parent;
444
445 if (node == NULL)
446 return GNUNET_SYSERR;
447
448 parent = node->parent;
449
450 if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX) && (parent != NULL)
451 && (node->cost > parent->cost))
452 percolateHeap (node, root);
453 else if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN) && (parent != NULL)
454 && (node->cost < parent->cost))
455 percolateHeap (node, root);
456 else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
457 percolateDownHeap (node, root);
458 else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
459 percolateDownHeap (node, root);
460
461 return GNUNET_YES;
462}
463
464
465int
466GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *root,
467 void *element,
468 GNUNET_CONTAINER_HeapCost new_cost)
469{
470 struct GNUNET_CONTAINER_heap_node *node;
471 int ret = GNUNET_YES;
472 node = find_element (root->root, element);
473 if (node == NULL)
474 return GNUNET_NO;
475
476 node->cost = new_cost;
477 ret = updatedCost (root, node);
478 return ret;
479}
480 500
501/**
502 * Updates the cost of any node in the tree
503 *
504 * @param heap heap to modify
505 * @param node node for which the cost is to be changed
506 * @param new_cost new cost for the node
507 */
481void 508void
482internal_iterator (struct GNUNET_CONTAINER_Heap *root, 509GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
483 struct GNUNET_CONTAINER_heap_node *node, 510 struct GNUNET_CONTAINER_HeapNode *node,
484 GNUNET_CONTAINER_HeapIterator iterator, void *cls) 511 GNUNET_CONTAINER_HeapCostType new_cost)
485{
486 if (node == NULL)
487 return;
488 internal_iterator (root, node->left_child, iterator, cls);
489 internal_iterator (root, node->right_child, iterator, cls);
490 iterator (cls, node->element, node->cost);
491}
492
493int
494GNUNET_CONTAINER_heap_iterate (struct GNUNET_CONTAINER_Heap *heap,
495 GNUNET_CONTAINER_HeapIterator iterator,
496 void *cls)
497{ 512{
498 internal_iterator (heap, heap->root, iterator, cls); 513#if DEBUG
499 return GNUNET_OK; 514 GNUNET_assert ( ( (heap->size == 0) &&
500} 515 (heap->root == NULL) ) ||
501 516 (heap->size == heap->root->tree_size + 1) );
502void * 517 CHECK (heap->root);
503GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *root) 518#endif
504{ 519 remove_node (heap, node);
505 unsigned int choice; 520#if DEBUG
506 void *element; 521 CHECK (heap->root);
507 522 GNUNET_assert ( ( (heap->size == 1) &&
508 if ((root->traversal_pos == NULL) && (root->root != NULL)) 523 (heap->root == NULL) ) ||
509 { 524 (heap->size == heap->root->tree_size + 2) );
510 root->traversal_pos = root->root; 525#endif
511 } 526 node->cost = new_cost;
512 527 if (heap->root == NULL)
513 if (root->traversal_pos == NULL) 528 heap->root = node;
514 return NULL; 529 else
515 530 insert_node (heap, heap->root, node);
516 element = root->traversal_pos->element; 531#if DEBUG
517 532 CHECK (heap->root);
518 choice = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, 2); 533 GNUNET_assert ( ( (heap->size == 0) &&
519 534 (heap->root == NULL) ) ||
520 switch (choice) 535 (heap->size == heap->root->tree_size + 1) );
521 { 536#endif
522 case 1:
523 root->traversal_pos = root->traversal_pos->right_child;
524 break;
525 case 0:
526 root->traversal_pos = root->traversal_pos->left_child;
527 break;
528 }
529
530 return element;
531
532} 537}
533 538
534unsigned int
535GNUNET_CONTAINER_heap_get_size (struct GNUNET_CONTAINER_Heap *heap)
536{
537 return heap->size;
538}
539 539
540/* end of heap.c */ 540/* end of heap.c */
diff --git a/src/util/test_container_heap.c b/src/util/test_container_heap.c
index 7a23855c5..b6e5f642a 100644
--- a/src/util/test_container_heap.c
+++ b/src/util/test_container_heap.c
@@ -28,67 +28,70 @@
28#include "gnunet_common.h" 28#include "gnunet_common.h"
29#include "gnunet_container_lib.h" 29#include "gnunet_container_lib.h"
30 30
31struct TestItem
32{
33 unsigned int cost;
34};
35
36static int 31static int
37iterator_callback (void *cls, void *element, GNUNET_CONTAINER_HeapCost cost) 32iterator_callback (void *cls,
33 struct GNUNET_CONTAINER_HeapNode *node,
34 void *element,
35 GNUNET_CONTAINER_HeapCostType cost)
38{ 36{
39 struct TestItem *node;
40 node = (struct TestItem *) element;
41#ifdef VERBOSE
42 fprintf (stdout, "%d\n", node->cost);
43#endif
44
45 return GNUNET_OK; 37 return GNUNET_OK;
46} 38}
47 39
48 40
49int 41static int
50main (int argc, char **argv) 42check ()
51{ 43{
52 struct GNUNET_CONTAINER_Heap *myHeap; 44 struct GNUNET_CONTAINER_Heap *myHeap;
53 struct TestItem neighbor1; 45 struct GNUNET_CONTAINER_HeapNode *n1;
54 struct TestItem neighbor2; 46 struct GNUNET_CONTAINER_HeapNode *n2;
55 struct TestItem neighbor3; 47 struct GNUNET_CONTAINER_HeapNode *n3;
56 struct TestItem neighbor4; 48 struct GNUNET_CONTAINER_HeapNode *n4;
57 struct TestItem neighbor5; 49 struct GNUNET_CONTAINER_HeapNode *n5;
58 struct TestItem neighbor6; 50 struct GNUNET_CONTAINER_HeapNode *n6;
59 51
60 GNUNET_log_setup ("test-container-heap", "WARNING", NULL); 52 myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
61 53 n1 = GNUNET_CONTAINER_heap_insert (myHeap, "11", 11);
62 myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MAX);
63
64 neighbor1.cost = 60;
65 neighbor2.cost = 50;
66 neighbor3.cost = 70;
67 neighbor4.cost = 120;
68 neighbor5.cost = 100;
69 neighbor6.cost = 30;
70
71 GNUNET_CONTAINER_heap_insert (myHeap, &neighbor1, neighbor1.cost);
72 GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
73 GNUNET_CONTAINER_heap_insert (myHeap, &neighbor2, neighbor2.cost);
74 GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
75 GNUNET_CONTAINER_heap_insert (myHeap, &neighbor3, neighbor3.cost);
76 GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
77 GNUNET_CONTAINER_heap_insert (myHeap, &neighbor4, neighbor4.cost);
78 GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL); 54 GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
79 GNUNET_CONTAINER_heap_insert (myHeap, &neighbor5, neighbor5.cost); 55 GNUNET_assert (1 == GNUNET_CONTAINER_heap_get_size (myHeap));
56 n2 = GNUNET_CONTAINER_heap_insert (myHeap, "78", 78);
57 GNUNET_assert (2 == GNUNET_CONTAINER_heap_get_size (myHeap));
58 GNUNET_assert (0 == strcmp ("78",
59 GNUNET_CONTAINER_heap_remove_node (myHeap, n2)));
60 GNUNET_assert (1 == GNUNET_CONTAINER_heap_get_size (myHeap));
80 GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL); 61 GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
81 GNUNET_CONTAINER_heap_insert (myHeap, &neighbor6, neighbor6.cost); 62
82 GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL); 63 n3 = GNUNET_CONTAINER_heap_insert (myHeap, "15", 5);
83 GNUNET_CONTAINER_heap_remove_node (myHeap, &neighbor5); 64 GNUNET_CONTAINER_heap_update_cost (myHeap, n3, 15);
84 GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL); 65 GNUNET_assert (2 == GNUNET_CONTAINER_heap_get_size (myHeap));
85 GNUNET_CONTAINER_heap_remove_root (myHeap);
86 GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL); 66 GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
87 GNUNET_CONTAINER_heap_update_cost (myHeap, &neighbor6, 200); 67
68 n4 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50);
69 GNUNET_assert (3 == GNUNET_CONTAINER_heap_get_size (myHeap));
88 GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL); 70 GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
89 GNUNET_CONTAINER_heap_destroy (myHeap);
90 71
72 n5 = GNUNET_CONTAINER_heap_insert (myHeap, "100", 100);
73 n6 = GNUNET_CONTAINER_heap_insert (myHeap, "30/200", 30);
74 GNUNET_assert (5 == GNUNET_CONTAINER_heap_get_size (myHeap));
75 GNUNET_CONTAINER_heap_remove_node (myHeap, n5);
76 GNUNET_assert (0 == strcmp ("11",
77 GNUNET_CONTAINER_heap_remove_root (myHeap))); /* n1 */
78 GNUNET_CONTAINER_heap_update_cost (myHeap, n6, 200);
79 GNUNET_CONTAINER_heap_remove_node (myHeap, n3);
80 GNUNET_assert (0 == strcmp ("50",
81 GNUNET_CONTAINER_heap_remove_root (myHeap))); /* n4 */
82 GNUNET_assert (0 == strcmp ("30/200",
83 GNUNET_CONTAINER_heap_remove_root (myHeap))); /* n6 */
84 GNUNET_assert (0 == GNUNET_CONTAINER_heap_get_size (myHeap));
85 GNUNET_CONTAINER_heap_destroy (myHeap);
91 return 0; 86 return 0;
92} 87}
93 88
89
90int
91main (int argc, char **argv)
92{
93 GNUNET_log_setup ("test-container-heap", "WARNING", NULL);
94 return check();
95}
96
94/* end of test_container_heap.c */ 97/* end of test_container_heap.c */
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-19 22:46:46 +0000