diff options
author | Christian Grothoff <christian@grothoff.org> | 2009-09-22 17:33:51 +0000 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2009-09-22 17:33:51 +0000 |
commit | 377b5e6c3615d2d482cb3341520bd5e84a0704b7 (patch) | |
tree | 457c6951baceeb4212a6769a1e2e4926735dbcb5 | |
parent | 9360aeb6e64646e9912642fc45d51e030003cb98 (diff) | |
download | gnunet-377b5e6c3615d2d482cb3341520bd5e84a0704b7.tar.gz gnunet-377b5e6c3615d2d482cb3341520bd5e84a0704b7.zip |
heap fixes
-rw-r--r-- | src/include/gnunet_container_lib.h | 16 | ||||
-rw-r--r-- | src/util/container_heap.c | 19 |
2 files changed, 31 insertions, 4 deletions
diff --git a/src/include/gnunet_container_lib.h b/src/include/gnunet_container_lib.h index 79d7866ed..61dee9918 100644 --- a/src/include/gnunet_container_lib.h +++ b/src/include/gnunet_container_lib.h | |||
@@ -689,7 +689,8 @@ void *GNUNET_CONTAINER_multihashmap_get_random (const struct | |||
689 | /** | 689 | /** |
690 | * Cost by which elements in a heap can be ordered. | 690 | * Cost by which elements in a heap can be ordered. |
691 | */ | 691 | */ |
692 | typedef unsigned int GNUNET_CONTAINER_HeapCost; | 692 | typedef uint64_t GNUNET_CONTAINER_HeapCost; |
693 | |||
693 | 694 | ||
694 | /* | 695 | /* |
695 | * Heap type, either max or min. Hopefully makes the | 696 | * Heap type, either max or min. Hopefully makes the |
@@ -708,6 +709,7 @@ enum GNUNET_CONTAINER_HeapOrder | |||
708 | GNUNET_CONTAINER_HEAP_ORDER_MIN | 709 | GNUNET_CONTAINER_HEAP_ORDER_MIN |
709 | }; | 710 | }; |
710 | 711 | ||
712 | |||
711 | /** | 713 | /** |
712 | * Handle to a Heap. | 714 | * Handle to a Heap. |
713 | */ | 715 | */ |
@@ -723,6 +725,7 @@ struct GNUNET_CONTAINER_Heap *GNUNET_CONTAINER_heap_create (enum | |||
723 | GNUNET_CONTAINER_HeapOrder | 725 | GNUNET_CONTAINER_HeapOrder |
724 | type); | 726 | type); |
725 | 727 | ||
728 | |||
726 | /** | 729 | /** |
727 | * Free a heap | 730 | * Free a heap |
728 | * | 731 | * |
@@ -730,6 +733,7 @@ struct GNUNET_CONTAINER_Heap *GNUNET_CONTAINER_heap_create (enum | |||
730 | */ | 733 | */ |
731 | void GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *h); | 734 | void GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *h); |
732 | 735 | ||
736 | |||
733 | /** | 737 | /** |
734 | * Function called on elements of a heap. | 738 | * Function called on elements of a heap. |
735 | * | 739 | * |
@@ -742,6 +746,8 @@ void GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *h); | |||
742 | typedef int (*GNUNET_CONTAINER_HeapIterator) (void *cls, | 746 | typedef int (*GNUNET_CONTAINER_HeapIterator) (void *cls, |
743 | void *element, | 747 | void *element, |
744 | GNUNET_CONTAINER_HeapCost cost); | 748 | GNUNET_CONTAINER_HeapCost cost); |
749 | |||
750 | |||
745 | /** | 751 | /** |
746 | * Iterate over all entries in the map. | 752 | * Iterate over all entries in the map. |
747 | * | 753 | * |
@@ -756,6 +762,7 @@ int GNUNET_CONTAINER_heap_iterate (struct GNUNET_CONTAINER_Heap *heap, | |||
756 | void *iterator_cls); | 762 | void *iterator_cls); |
757 | 763 | ||
758 | 764 | ||
765 | |||
759 | /** | 766 | /** |
760 | * Inserts a new item into the heap, item is always neighbor now. | 767 | * Inserts a new item into the heap, item is always neighbor now. |
761 | * @param heap the heap | 768 | * @param heap the heap |
@@ -764,6 +771,7 @@ int | |||
764 | GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, | 771 | GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, |
765 | void *element, GNUNET_CONTAINER_HeapCost cost); | 772 | void *element, GNUNET_CONTAINER_HeapCost cost); |
766 | 773 | ||
774 | |||
767 | /** | 775 | /** |
768 | * Removes root of the tree, is remove max if a max heap and remove min | 776 | * Removes root of the tree, is remove max if a max heap and remove min |
769 | * if a min heap, returns the data stored at the node. | 777 | * if a min heap, returns the data stored at the node. |
@@ -773,6 +781,7 @@ GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, | |||
773 | */ | 781 | */ |
774 | void *GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap); | 782 | void *GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap); |
775 | 783 | ||
784 | |||
776 | /** | 785 | /** |
777 | * Returns element stored at root of tree, doesn't effect anything | 786 | * Returns element stored at root of tree, doesn't effect anything |
778 | * | 787 | * |
@@ -781,6 +790,7 @@ void *GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap); | |||
781 | */ | 790 | */ |
782 | void *GNUNET_CONTAINER_heap_peek (struct GNUNET_CONTAINER_Heap *heap); | 791 | void *GNUNET_CONTAINER_heap_peek (struct GNUNET_CONTAINER_Heap *heap); |
783 | 792 | ||
793 | |||
784 | /** | 794 | /** |
785 | * Removes any node from the tree based on the neighbor given, does | 795 | * Removes any node from the tree based on the neighbor given, does |
786 | * not traverse the tree (backpointers) but may take more time due to | 796 | * not traverse the tree (backpointers) but may take more time due to |
@@ -790,6 +800,7 @@ void *GNUNET_CONTAINER_heap_peek (struct GNUNET_CONTAINER_Heap *heap); | |||
790 | void *GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *heap, | 800 | void *GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *heap, |
791 | void *element); | 801 | void *element); |
792 | 802 | ||
803 | |||
793 | /** | 804 | /** |
794 | * Updates the cost of any node in the tree | 805 | * Updates the cost of any node in the tree |
795 | * | 806 | * |
@@ -803,6 +814,7 @@ GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap, | |||
803 | void *element, | 814 | void *element, |
804 | GNUNET_CONTAINER_HeapCost new_cost); | 815 | GNUNET_CONTAINER_HeapCost new_cost); |
805 | 816 | ||
817 | |||
806 | /** | 818 | /** |
807 | * Random walk of the tree, returns the data stored at the next random node | 819 | * Random walk of the tree, returns the data stored at the next random node |
808 | * in the walk. Calls callee with the data, or NULL if the tree is empty | 820 | * in the walk. Calls callee with the data, or NULL if the tree is empty |
@@ -814,6 +826,7 @@ GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap, | |||
814 | void *GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap | 826 | void *GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap |
815 | *heap); | 827 | *heap); |
816 | 828 | ||
829 | |||
817 | /** | 830 | /** |
818 | * Returns the current size of the heap | 831 | * Returns the current size of the heap |
819 | * | 832 | * |
@@ -824,6 +837,7 @@ unsigned int | |||
824 | GNUNET_CONTAINER_heap_get_size (struct GNUNET_CONTAINER_Heap *heap); | 837 | GNUNET_CONTAINER_heap_get_size (struct GNUNET_CONTAINER_Heap *heap); |
825 | 838 | ||
826 | 839 | ||
840 | |||
827 | #if 0 /* keep Emacsens' auto-indent happy */ | 841 | #if 0 /* keep Emacsens' auto-indent happy */ |
828 | { | 842 | { |
829 | #endif | 843 | #endif |
diff --git a/src/util/container_heap.c b/src/util/container_heap.c index 7e41c40f2..fd5838f60 100644 --- a/src/util/container_heap.c +++ b/src/util/container_heap.c | |||
@@ -72,18 +72,31 @@ struct GNUNET_CONTAINER_Heap | |||
72 | 72 | ||
73 | }; | 73 | }; |
74 | 74 | ||
75 | |||
76 | /** | ||
77 | * Returns element stored at root of tree, doesn't effect anything | ||
78 | * | ||
79 | * @param heap the heap | ||
80 | * @return NULL if the heap is empty | ||
81 | */ | ||
82 | void *GNUNET_CONTAINER_heap_peek (struct GNUNET_CONTAINER_Heap *heap) | ||
83 | { | ||
84 | return heap->root; | ||
85 | } | ||
86 | |||
87 | |||
75 | void | 88 | void |
76 | internal_print (struct GNUNET_CONTAINER_heap_node *root) | 89 | internal_print (struct GNUNET_CONTAINER_heap_node *root) |
77 | { | 90 | { |
78 | fprintf (stdout, "%d\n", root->cost); | 91 | fprintf (stdout, "%llu\n", (unsigned long long) root->cost); |
79 | if (root->left_child != NULL) | 92 | if (root->left_child != NULL) |
80 | { | 93 | { |
81 | fprintf (stdout, "LEFT of %d\n", root->cost); | 94 | fprintf (stdout, "LEFT of %llu\n", (unsigned long long) root->cost); |
82 | internal_print (root->left_child); | 95 | internal_print (root->left_child); |
83 | } | 96 | } |
84 | if (root->right_child != NULL) | 97 | if (root->right_child != NULL) |
85 | { | 98 | { |
86 | fprintf (stdout, "RIGHT of %d\n", root->cost); | 99 | fprintf (stdout, "RIGHT of %llu\n", (unsigned long long) root->cost); |
87 | internal_print (root->right_child); | 100 | internal_print (root->right_child); |
88 | } | 101 | } |
89 | } | 102 | } |