From 5afa4c0d579f1ebff37b638a30ea397d58aca5f8 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Mon, 22 Aug 2011 22:00:12 -0700 Subject: [PATCH] abt: Drop child parameters from 'reaugment' function. The function can simply inspect the 'down' members. --- src/libpspp/abt.c | 10 +++++----- src/libpspp/abt.h | 32 +++++++++++++------------------- src/libpspp/tower.c | 32 ++++++++++++++------------------ tests/libpspp/abt-test.c | 15 ++++++--------- 4 files changed, 38 insertions(+), 51 deletions(-) diff --git a/src/libpspp/abt.c b/src/libpspp/abt.c index c06047b4ab..ae74618302 100644 --- a/src/libpspp/abt.c +++ b/src/libpspp/abt.c @@ -351,7 +351,7 @@ void abt_reaugmented (const struct abt *abt, struct abt_node *p) { for (; p != NULL; p = p->up) - abt->reaugment (p, p->down[0], p->down[1], abt->aux); + abt->reaugment (p, abt->aux); } /* Moves P around in ABT to compensate for its key having @@ -452,8 +452,8 @@ skew (struct abt *abt, struct abt_node *a) b->up = a->up; a->up = b; - abt->reaugment (a, a->down[0], a->down[1], abt->aux); - abt->reaugment (b, b->down[0], b->down[1], abt->aux); + abt->reaugment (a, abt->aux); + abt->reaugment (b, abt->aux); return b; } @@ -483,8 +483,8 @@ split (struct abt *abt, struct abt_node *a) b->level++; - abt->reaugment (a, a->down[0], a->down[1], abt->aux); - abt->reaugment (b, b->down[0], b->down[1], abt->aux); + abt->reaugment (a, abt->aux); + abt->reaugment (b, abt->aux); return b; } diff --git a/src/libpspp/abt.h b/src/libpspp/abt.h index fa9d0dc87d..0e5b25281e 100644 --- a/src/libpspp/abt.h +++ b/src/libpspp/abt.h @@ -34,10 +34,9 @@ The ABT data structure partially abstracts augmentation. The client passes in a "reaugmentation" function that accepts a - node and its left and right children. This function must - recalculate the node's augmentation data based on its own - contents and the contents of its children, and store the new - augmentation data in the node. + node. This function must recalculate the node's augmentation + data based on its own contents and the contents of its + children, and store the new augmentation data in the node. The ABT automatically calls the reaugmentation function whenever it can tell that a node's augmentation data might @@ -104,19 +103,16 @@ } // Recalculates the count for NODE's subtree by adding up the - // counts for its LEFT and RIGHT child subtrees. + // counts for its left and right child subtrees. static void - reaugment_elements (struct abt_node *node_, - const struct abt_node *left, - const struct abt_node *right, - const void *aux) + reaugment_elements (struct abt_node *node_, const void *aux) { struct element *node = node_to_element (node_); node->count = 1; - if (left != NULL) - node->count += node_to_element (left)->count; - if (right != NULL) - node->count += node_to_element (right)->count; + if (node->node.down[0] != NULL) + node->count += node_to_element (node->node.down[0])->count; + if (node->node.down[1] != NULL) + node->count += node_to_element (node->node.down[1])->count; } // Finds and returns the element in ABT that is in the given @@ -173,12 +169,10 @@ typedef int abt_compare_func (const struct abt_node *a, const struct abt_node *b, const void *aux); -/* Recalculates NODE's augmentation based on NODE's data and that - of its LEFT and RIGHT children, with the tree's AUX. */ -typedef void abt_reaugment_func (struct abt_node *node, - const struct abt_node *left, - const struct abt_node *right, - const void *aux); +/* Recalculates NODE's augmentation based on NODE's data and that of its left + and right children NODE->down[0] and NODE[1], respectively, with the tree's + AUX. */ +typedef void abt_reaugment_func (struct abt_node *node, const void *aux); /* An augmented binary tree. */ struct abt diff --git a/src/libpspp/tower.c b/src/libpspp/tower.c index 863da820c3..bdaaffbca3 100644 --- a/src/libpspp/tower.c +++ b/src/libpspp/tower.c @@ -33,10 +33,7 @@ static struct tower_node *prev_node (const struct tower *, const struct tower_node *); static unsigned long int get_subtree_size (const struct abt_node *); static unsigned long int get_subtree_count (const struct abt_node *); -static void reaugment_tower_node (struct abt_node *, - const struct abt_node *, - const struct abt_node *, - const void *aux); +static void reaugment_tower_node (struct abt_node *, const void *aux); /* Returns the height of the bottom of the given tower NODE. @@ -351,27 +348,26 @@ get_subtree_count (const struct abt_node *p) return p != NULL ? abt_to_tower_node (p)->subtree_count : 0; } -/* Recalculates the subtree_size of NODE based on its LEFT and - RIGHT children's subtree_sizes. */ +/* Recalculates the subtree_size of NODE based on the subtree_sizes of its + children. */ static void -reaugment_tower_node (struct abt_node *node_, - const struct abt_node *left, - const struct abt_node *right, - const void *aux UNUSED) +reaugment_tower_node (struct abt_node *node_, const void *aux UNUSED) { struct tower_node *node = abt_to_tower_node (node_); node->subtree_size = node->size; node->subtree_count = 1; - if (left != NULL) + + if (node->abt_node.down[0] != NULL) { - struct tower_node *left_node = abt_to_tower_node (left); - node->subtree_size += left_node->subtree_size; - node->subtree_count += left_node->subtree_count; + struct tower_node *left = abt_to_tower_node (node->abt_node.down[0]); + node->subtree_size += left->subtree_size; + node->subtree_count += left->subtree_count; } - if (right != NULL) + + if (node->abt_node.down[1] != NULL) { - struct tower_node *right_node = abt_to_tower_node (right); - node->subtree_size += right_node->subtree_size; - node->subtree_count += right_node->subtree_count; + struct tower_node *right = abt_to_tower_node (node->abt_node.down[1]); + node->subtree_size += right->subtree_size; + node->subtree_count += right->subtree_count; } } diff --git a/tests/libpspp/abt-test.c b/tests/libpspp/abt-test.c index 8bbe7d76e4..eae7d46787 100644 --- a/tests/libpspp/abt-test.c +++ b/tests/libpspp/abt-test.c @@ -1,5 +1,5 @@ /* PSPP - a program for statistical analysis. - Copyright (C) 2007, 2010 Free Software Foundation, Inc. + Copyright (C) 2007, 2010, 2011 Free Software Foundation, Inc. This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -138,20 +138,17 @@ compare_elements (const struct abt_node *a_, const struct abt_node *b_, /* Recalculates the count for NODE's subtree by adding up the counts for its LEFT and RIGHT child subtrees. */ static void -reaugment_elements (struct abt_node *node_, - const struct abt_node *left, - const struct abt_node *right, - const void *aux) +reaugment_elements (struct abt_node *node_, const void *aux) { struct element *node = abt_node_to_element (node_); check (aux == &aux_data); node->count = 1; - if (left != NULL) - node->count += abt_node_to_element (left)->count; - if (right != NULL) - node->count += abt_node_to_element (right)->count; + if (node->node.down[0] != NULL) + node->count += abt_node_to_element (node->node.down[0])->count; + if (node->node.down[1] != NULL) + node->count += abt_node_to_element (node->node.down[1])->count; } /* Compares A and B and returns a strcmp-type return value. */ -- 2.30.2