From c410b2dbba61954e97d3790207aa9e7ad806e465 Mon Sep 17 00:00:00 2001 From: Marko Kreen Date: Wed, 2 Sep 2009 15:02:42 +0300 Subject: [PATCH] heap: instead macro, use inline for elem comparision --- usual/heap-impl.h | 34 ++++++++++++++++++++++++---------- 1 file changed, 24 insertions(+), 10 deletions(-) diff --git a/usual/heap-impl.h b/usual/heap-impl.h index f97fbe8..b3097db 100644 --- a/usual/heap-impl.h +++ b/usual/heap-impl.h @@ -24,16 +24,11 @@ * except the last one are fully filled. * * Instead of "min"- or "max"-heap, this is "best"-heap, - * as it operates with user-defined IS_BETTER macro, + * as it operates with user-defined heap_is_better() functions, * which is used to bubble elements on top. Main reason * for such design is to make the comparisions inline. */ -/* #define IS_BETTER(p1, p2) */ -#ifndef IS_BETTER -#error requires IS_BETTER(p1, p2) macro to be defined. -#endif - /* * If user wants to delete elements from the middle of heap, * this macro should be used to keep track where the element @@ -43,8 +38,7 @@ #define SAVE_POS(ptr, pos) #endif -#include -#include +#include struct Heap { void **data; @@ -52,6 +46,14 @@ struct Heap { unsigned used; }; +/* + * For user to be defined. + * + * Should return true if a needs to reach top before b, + * false if not or equal. + */ +static inline bool heap_is_better(const void *a, const void *b); + /* * Low-level operations. @@ -69,7 +71,7 @@ static inline unsigned _heap_get_child(unsigned i, unsigned child_nr) static inline bool _heap_is_better(struct Heap *h, unsigned i1, unsigned i2) { - return IS_BETTER(h->data[i1], h->data[i2]); + return heap_is_better(h->data[i1], h->data[i2]); } static inline void _heap_set(struct Heap *h, unsigned i, void *ptr) @@ -202,8 +204,20 @@ static void heap_delete_pos(struct Heap *h, unsigned pos) _heap_bubble_down(h, pos); } -static inline void heap_delete_top(struct Heap *h) +static void heap_delete_top(struct Heap *h) { heap_delete_pos(h, 0); } +/* example and avoid 'unused' warnings */ +static inline void _heap_example(void *el) +{ + struct Heap h; + void *top; + heap_init(&h); + heap_insert(&h, el); + top = heap_get_top(&h); + heap_delete_top(&h); + heap_destroy(&h); +} + -- 2.39.5