From b7535577132d5d9c81c10c07a1776eacde6e5a44 Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Tue, 9 Apr 2013 16:15:39 -0400 Subject: implement binheap_for_each() visitor function --- include/litmus/binheap.h | 5 +++++ litmus/binheap.c | 17 +++++++++++++++++ 2 files changed, 22 insertions(+) diff --git a/include/litmus/binheap.h b/include/litmus/binheap.h index 901a30a3e296..5fb5f26d8339 100644 --- a/include/litmus/binheap.h +++ b/include/litmus/binheap.h @@ -173,6 +173,11 @@ static inline int binheap_is_in_heap(struct binheap_node *node) /* Returns true if binheap node is in given heap. */ int binheap_is_in_this_heap(struct binheap_node *node, struct binheap* heap); + +typedef void (*binheap_for_each_t)(struct binheap_node *node, void* args); +/* Visit every node in heap with function fn(args). Visit order undefined. */ +void binheap_for_each(struct binheap *heap, binheap_for_each_t fn, void* args); + /* Add a node to a heap */ void __binheap_add(struct binheap_node *new_node, struct binheap *handle, diff --git a/litmus/binheap.c b/litmus/binheap.c index 40a913f4b5a7..6e4eb4dc7553 100644 --- a/litmus/binheap.c +++ b/litmus/binheap.c @@ -15,6 +15,23 @@ int binheap_is_in_this_heap(struct binheap_node *node, return (node == heap->root); } +static void __binheap_for_each(struct binheap_node *h, binheap_for_each_t fn, void* args) +{ + /* pre-order */ + fn(h, args); + + if(h->left) + __binheap_for_each(h->left, fn, args); + if(h->right) + __binheap_for_each(h->right, fn, args); +} + +void binheap_for_each(struct binheap *heap, binheap_for_each_t fn, void* args) +{ + if (!binheap_empty(heap)) + __binheap_for_each(heap->root, fn, args); +} + /* Update the node reference pointers. Same logic as Litmus binomial heap. */ static void __update_ref(struct binheap_node *parent, -- cgit v1.2.2