From d04082bb551785a0fc45776581916b44044921ed Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 30 Aug 2007 11:58:00 +0200 Subject: [PATCH] Cleanup and commentary. --- lib/sorter/s-multiway.h | 23 +++++++++++++++-------- 1 file changed, 15 insertions(+), 8 deletions(-) diff --git a/lib/sorter/s-multiway.h b/lib/sorter/s-multiway.h index c22af45e..9295396f 100644 --- a/lib/sorter/s-multiway.h +++ b/lib/sorter/s-multiway.h @@ -7,14 +7,21 @@ * of the GNU Lesser General Public License. */ -typedef struct P(mwt_node) { - int i; +/* + * We use a binary tree to keep track of the current minimum. The tree is + * represented by an array (in the same way as binary heaps usually are), + * leaves correspond to input streams and each internal vertex remembers + * the leaf in its subtree, which has the lowest key. + */ + +typedef struct P(mwt) { + int i; // Minimum of the subtree #ifdef SORT_UNIFY - int eq; + int eq; // Did we encounter equality anywhere in the subtree? #endif -} P(mwt_node); +} P(mwt); -static inline void P(update_tree)(P(key) *keys, P(mwt_node) *tree, uns i) +static inline void P(update_tree)(P(key) *keys, P(mwt) *tree, uns i) { while (i /= 2) { @@ -48,7 +55,7 @@ static inline void P(update_tree)(P(key) *keys, P(mwt_node) *tree, uns i) #endif } -static inline void P(set_tree)(P(key) *keys, P(mwt_node) *tree, uns i, int val) +static inline void P(set_tree)(P(key) *keys, P(mwt) *tree, uns i, int val) { tree[i].i = val; P(update_tree)(keys, tree, i); @@ -67,9 +74,9 @@ static void P(multiway_merge)(struct sort_context *ctx UNUSED, struct sort_bucke struct fastbuf *fout = sbuck_write(out); struct fastbuf *fins[num_ins]; P(key) keys[num_ins]; - P(mwt_node) tree[2*n2]; // A complete binary tree, leaves are input streams, each internal vertex contains a minimum of its sons + P(mwt) tree[2*n2]; for (uns i=1; i<2*n2; i++) - tree[i] = (P(mwt_node)) { .i = -1 }; + tree[i] = (P(mwt)) { .i = -1 }; for (uns i=0; i