From 5d15bedea1aaae6ec34f5101a0177d13a84a52dc Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Wed, 18 Jun 2003 16:40:03 +0000
Subject: [PATCH] Tweak the binomial heaps a bit to make them easier to use.

---
 lib/binheap-node.h | 15 ++++++-------
 lib/binheap-test.c | 26 ++++++++++++++--------
 lib/binheap.h      | 54 ++++++++++++++++++++++++++++++++++++++--------
 3 files changed, 68 insertions(+), 27 deletions(-)

diff --git a/lib/binheap-node.h b/lib/binheap-node.h
index da03a800..61ed5e97 100644
--- a/lib/binheap-node.h
+++ b/lib/binheap-node.h
@@ -7,16 +7,13 @@
  *	of the GNU Lesser General Public License.
  */
 
-#define BH_NODE struct BH_PREFIX(node)
-#define BH_HEAP struct BH_PREFIX(heap)
-
-BH_NODE {
-  BH_NODE *first_son;
-  BH_NODE *last_son;
-  BH_NODE *next_sibling;
+struct bh_node {
+  struct bh_node *first_son;
+  struct bh_node *last_son;
+  struct bh_node *next_sibling;
   byte order;
 };
 
-BH_HEAP {
-  BH_NODE root;
+struct bh_heap {
+  struct bh_node root;
 };
diff --git a/lib/binheap-test.c b/lib/binheap-test.c
index 703fac87..2a0f026f 100644
--- a/lib/binheap-test.c
+++ b/lib/binheap-test.c
@@ -19,36 +19,36 @@
 #include "lib/binheap-node.h"
 
 struct item {
-  struct bht_node n;
+  struct bh_node n;
   uns key;
 };
 
-static inline uns bht_key(struct bht_node *n)
+static inline uns bht_key(struct bh_node *n)
 {
   return ((struct item *)n)->key;
 }
 
-static inline uns bht_less(struct bht_node *a, struct bht_node *b)
+static inline uns bht_less(struct bh_node *a, struct bh_node *b)
 {
   return bht_key(a) < bht_key(b);
 }
 
 static void
-bht_do_dump(struct bht_node *a, struct bht_node *expected_last, uns offset)
+bht_do_dump(struct bh_node *a, struct bh_node *expected_last, uns offset)
 {
   if (!a)
     return;
   printf("%*s", offset, "");
   printf("[%d](%d)%s\n", a->order, bht_key(a), a == expected_last ? " L" : "");
-  for (struct bht_node *b=a->first_son; b; b=b->next_sibling)
+  for (struct bh_node *b=a->first_son; b; b=b->next_sibling)
     bht_do_dump(b, a->last_son, offset+1);
 }
 
 static void
-bht_dump(struct bht_heap *h)
+bht_dump(struct bh_heap *h)
 {
   printf("root\n");
-  for (struct bht_node *b=h->root.first_son; b; b=b->next_sibling)
+  for (struct bh_node *b=h->root.first_son; b; b=b->next_sibling)
     bht_do_dump(b, b->last_son, 1);
 }
 
@@ -57,7 +57,7 @@ bht_dump(struct bht_heap *h)
 int main(void)
 {
   uns i;
-  struct bht_heap h;
+  struct bh_heap h;
 #define N 1048576
 #define K(i) ((259309*i+1009)%N)
 
@@ -71,8 +71,16 @@ int main(void)
       bht_insert(&h, &a->n);
       // bht_dump(&h);
     }
-  bht_dump(&h);
+  // bht_dump(&h);
   ASSERT(bht_key(bht_findmin(&h)) == 0);
+  uns cnt = 0;
+  BH_FOR_ALL(bht_, &h, a)
+    {
+      cnt++;
+    }
+  BH_END_FOR;
+  printf("cnt=%d\n", cnt);
+  ASSERT(cnt == N);
   for (i=0; i<N; i++)
     {
       struct item *a = (struct item *) bht_deletemin(&h);
diff --git a/lib/binheap.h b/lib/binheap.h
index d8578921..e6f7afda 100644
--- a/lib/binheap.h
+++ b/lib/binheap.h
@@ -20,11 +20,11 @@
  *			names mentioned here except for macro names will be
  *			implicitly prefixed.
  *
- *  Then you continue by including "lib/binheap-node.h" which defines struct node
- *  (also prefixed) and struct root. The heap elements are always allocated by
- *  you and they must include struct node which serves as a handle used for all
+ *  Then you continue by including "lib/binheap-node.h" which defines struct bh_node
+ *  and struct bh_root (both without prefix). The heap elements are always allocated by
+ *  you and they must include struct bh_node which serves as a handle used for all
  *  the heap functions and it contains all information needed for heap-keeping.
- *  The heap itself is also allocated by you and it's represented by struct root.
+ *  The heap itself is also allocated by you and it's represented by struct bh_heap.
  *
  *  When you have the declaration of heap nodes, you continue with defining:
  *
@@ -33,18 +33,32 @@
  *
  *  Then specify what operations you request:
  *
- *  <always defined>	init(heap) -- initialize the heap.
- *  BH_WANT_INSERT	insert(heap, node*) -- insert the node to the heap.
- *  BH_WANT_FINDMIN	node *findmin(heap) -- find node with minimum key.
- *  BH_WANT_DELETEMIN	node *deletemin(heap) -- findmin and delete the node.
+ *  <always defined>	init(heap*) -- initialize the heap.
+ *  BH_WANT_INSERT	insert(heap*, node*) -- insert the node to the heap.
+ *  BH_WANT_FINDMIN	node *findmin(heap*) -- find node with minimum key.
+ *  BH_WANT_DELETEMIN	node *deletemin(heap*) -- findmin and delete the node.
  *
- *  Then include "lib/binheap.h| and voila, you have a binomial heap
+ *  Then include "lib/binheap.h" and voila, you have a binomial heap
  *  suiting all your needs (at least those which you've revealed :) ).
  *
+ *  You also get a iterator macro at no extra charge:
+ *
+ *  BH_FOR_ALL(bh_prefix, hash*, variable)
+ *    {
+ *      // node *variable gets declared automatically
+ *      do_something_with_node(variable);
+ *      // use BH_BREAK and BH_CONTINUE instead of break and continue
+ *	// you must not alter contents of the hash table here
+ *    }
+ *  BH_END_FOR;
+ *
  *  After including this file, all parameter macros are automatically
  *  undef'd.
  */
 
+#define BH_NODE struct bh_node
+#define BH_HEAP struct bh_heap
+
 static void
 BH_PREFIX(merge)(BH_NODE *a, BH_NODE *b)
 {
@@ -158,6 +172,28 @@ BH_PREFIX(init)(BH_HEAP *heap)
   bzero(heap, sizeof(*heap));
 }
 
+#ifndef BH_FOR_ALL
+
+#define BH_FOR_ALL(bh_px, bh_heap, bh_var)	\
+do {						\
+  struct bh_node *bh_stack[32];			\
+  bh_stack[0] = (bh_heap)->root.first_son;	\
+  uns bh_sp = 1;				\
+  while (bh_sp) {				\
+    struct bh_node *bh_var = bh_stack[--bh_sp];	\
+    if (bh_var->next_sibling)			\
+      bh_stack[bh_sp++] = bh_var->next_sibling; \
+    if (bh_var->first_son)			\
+      bh_stack[bh_sp++] = bh_var->first_son;
+#define BH_END_FOR				\
+  }						\
+} while (0)
+
+#define BH_BREAK { bh_sp=0; break; }
+#define BH_CONTINUE continue
+
+#endif
+
 #undef BH_PREFIX
 #undef BH_NODE
 #undef BH_HEAP
-- 
2.39.2