X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flibpspp%2Fabt.h;fp=src%2Flibpspp%2Fabt.h;h=f48e7a2ab8893c33e995d3f7f69ef965c3689a71;hb=9683d7528884fcb3c60705812de9f96889536388;hp=0000000000000000000000000000000000000000;hpb=3f159627d3b80706e58a54be2431c3edbc5333dc;p=pspp diff --git a/src/libpspp/abt.h b/src/libpspp/abt.h new file mode 100644 index 0000000000..f48e7a2ab8 --- /dev/null +++ b/src/libpspp/abt.h @@ -0,0 +1,208 @@ +/* PSPP - computes sample statistics. + Copyright (C) 2007 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 the Free Software Foundation; either version 2 of the + License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + 02110-1301, USA. */ + +#ifndef LIBPSPP_ABT_H +#define LIBPSPP_ABT_H 1 + +/* Augmented binary tree (ABT) data structure. + + A data structure can be "augmented" by defining new + information for it to maintain. One commonly useful way to + augment a binary search tree-based data structure is to define + part of its data as a function of its immediate children's + data. Furthermore, augmented data defined in this way can be + efficiently maintained as the tree changes over time. + + For example, suppose we define the "size" of a node as the sum + of the "size" of its immediate children, plus 1. In such an + annotated BST with height H, we can find the node that would + be Kth in in-order traversal in O(H) time, instead of O(K) + time, which is a significant saving for balanced trees. + + 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. + + The ABT automatically calls the reaugmentation function + whenever it can tell that a node's augmentation data might + need to be updated: when the node is inserted or when a node's + descendants change due to insertion or deletion. The ABT does + not know to call the reaugmentation function if a node's data + is updated while it is in the ABT. In such a case, call the + abt_reaugmented or abt_changed function to update the + augmentation. + + Augmentation is only partially abstracted: we do not provide + any way to search an ABT based on its augmentations. The + tree structure is thus exposed to the client to allow it to + implement search. + + To allow for optimization, the ABT implementation assumes that + the augmentation function in use is unaffected by the shape of + a binary search tree. That is, if a given subtree within a + larger tree is rearranged, e.g. via a series of rotations, + then the implementation will not call the reaugmentation + function outside of the subtree, because the overall + augmentation data for the subtree is assumed not to changed. + This optimization is valid for the forms of augmentation + described in CLR and Knuth (see below), and it is possible + that it is valid for every efficient binary search tree + augmentation. + + The client should not need to be aware of the form of + balancing applied to the ABT, as its operation should be fully + encapsulated by the reaugmentation function. The current + implementation uses an AA (Arne Andersson) tree, but this is + subject to change. + + The following example illustrates how to use an ABT to build a + tree that can be searched either by a data value or in-order + position: + + // Test data element. + struct element + { + struct abt_node node; // Embedded binary tree element. + int data; // Primary value. + int count; // Number of nodes in subtree, + // including this node. + }; + + // Returns the `struct element' that NODE is embedded within. + static struct element * + node_to_element (const struct abt_node *node) + { + return abt_data (node, struct element, node); + } + + // Compares the DATA values in A and B and returns a + // strcmp-type return value. + static int + compare_elements (const struct abt_node *a_, const struct abt_node *b_, + const void *aux) + { + const struct element *a = node_to_element (a_); + const struct element *b = node_to_element (b_); + + return a->data < b->data ? -1 : a->data > b->data; + } + + // 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) + { + 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; + } + + // Finds and returns the element in ABT that is in the given + // 0-based POSITION in in-order. + static struct element * + find_by_position (struct abt *abt, int position) + { + struct abt_node *p; + for (p = abt->root; p != NULL; ) + { + int p_pos = p->down[0] ? node_to_element (p->down[0])->count : 0; + if (position == p_pos) + return node_to_element (p); + else if (position < p_pos) + p = p->down[0]; + else + { + p = p->down[1]; + position -= p_pos + 1; + } + } + return NULL; + } + + For more information on augmenting binary search tree-based + data structures, see Cormen-Leiserson-Rivest, chapter 15, or + Knuth vol. 3, section 6.2.3, under "Linear list + representation." For more information on AA trees, see + , which includes source + code and links to other resources, such as the original AA + tree paper. */ + +#include + +/* Returns the data structure corresponding to the given NODE, + assuming that NODE is embedded as the given MEMBER name in + data type STRUCT. */ +#define abt_data(NODE, STRUCT, MEMBER) \ + ((STRUCT *) ((char *) (NODE) - offsetof (STRUCT, MEMBER))) + +/* Node in an augmented binary tree. */ +struct abt_node + { + struct abt_node *up; /* Parent (NULL for root). */ + struct abt_node *down[2]; /* Left child, right child. */ + int level; /* AA tree level (not ordinary BST level). */ + }; + +/* Compares nodes A and B, with the tree's AUX. + Returns a strcmp-like result. */ +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); + +/* An augmented binary tree. */ +struct abt + { + struct abt_node *root; /* Tree's root, NULL if empty. */ + abt_compare_func *compare; /* To compare nodes. */ + abt_reaugment_func *reaugment; /* To augment a node using its children. */ + const void *aux; /* Auxiliary data. */ + }; + +void abt_init (struct abt *, abt_compare_func *, abt_reaugment_func *, + const void *aux); + +struct abt_node *abt_insert (struct abt *, struct abt_node *); +void abt_delete (struct abt *, struct abt_node *); + +struct abt_node *abt_first (const struct abt *); +struct abt_node *abt_last (const struct abt *); +struct abt_node *abt_find (const struct abt *, const struct abt_node *); +struct abt_node *abt_next (const struct abt *, const struct abt_node *); +struct abt_node *abt_prev (const struct abt *, const struct abt_node *); + +void abt_reaugmented (const struct abt *, struct abt_node *); +struct abt_node *abt_changed (struct abt *, struct abt_node *); +void abt_moved (struct abt *, struct abt_node *); + +#endif /* libpspp/abt.h */