diff options
Diffstat (limited to 'src/common/modified_tree.h')
| -rw-r--r-- | src/common/modified_tree.h | 292 |
1 files changed, 0 insertions, 292 deletions
diff --git a/src/common/modified_tree.h b/src/common/modified_tree.h deleted file mode 100644 index 9ceddd1..0000000 --- a/src/common/modified_tree.h +++ /dev/null @@ -1,292 +0,0 @@ -/* tree.h -- AVL trees (in the spirit of BSD's 'queue.h') -*- C -*- */ - -/* Copyright (c) 2005 Ian Piumarta - * - * All rights reserved. - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the 'Software'), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, and/or sell copies of the - * Software, and to permit persons to whom the Software is furnished to do so, - * provided that the above copyright notice(s) and this permission notice appear - * in all copies of the Software and that both the above copyright notice(s) and - * this permission notice appear in supporting documentation. - * - * THE SOFTWARE IS PROVIDED 'AS IS'. USE ENTIRELY AT YOUR OWN RISK. - */ - -/* This file defines an AVL balanced binary tree [Georgii M. Adelson-Velskii and - * Evgenii M. Landis, 'An algorithm for the organization of information', - * Doklady Akademii Nauk SSSR, 146:263-266, 1962 (Russian). Also in Myron - * J. Ricci (trans.), Soviet Math, 3:1259-1263, 1962 (English)]. - * - * An AVL tree is headed by pointers to the root node and to a function defining - * the ordering relation between nodes. Each node contains an arbitrary payload - * plus three fields per tree entry: the depth of the subtree for which it forms - * the root and two pointers to child nodes (singly-linked for minimum space, at - * the expense of direct access to the parent node given a pointer to one of the - * children). The tree is rebalanced after every insertion or removal. The - * tree may be traversed in two directions: forward (in-order left-to-right) and - * reverse (in-order, right-to-left). - * - * Because of the recursive nature of many of the operations on trees it is - * necessary to define a number of helper functions for each type of tree node. - * The macro TREE_DEFINE(node_tag, entry_name) defines these functions with - * unique names according to the node_tag. This macro should be invoked, - * thereby defining the necessary functions, once per node tag in the program. - * - * For details on the use of these macros, see the tree(3) manual page. - */ - -#ifndef _modified_tree_h -#define _modified_tree_h - - -#define MOD_TREE_DELTA_MAX 1 - -#define MOD_TREE_ENTRY(type) \ - struct { \ - struct type *avl_left; \ - struct type *avl_right; \ - int avl_height; \ - } - -#define MOD_TREE_HEAD(name, type) \ - struct name { \ - struct type *th_root; \ - int (*th_cmp)(void *lhs, void *rhs); \ - } - -#define MOD_TREE_INITIALIZER(cmp) { 0, cmp} - -#define MOD_TREE_DELTA(self, field) \ - (( (((self)->field.avl_left) ? (self)->field.avl_left->field.avl_height : 0)) \ - - (((self)->field.avl_right) ? (self)->field.avl_right->field.avl_height : 0)) - -/* Recursion prevents the following from being defined as macros. */ - -#define MOD_TREE_DEFINE(node, field) \ - \ - struct node *MOD_TREE_BALANCE_##node##_##field(struct node *); \ - \ - struct node *MOD_TREE_ROTL_##node##_##field(struct node *self) \ - { \ - struct node *r= self->field.avl_right; \ - self->field.avl_right= r->field.avl_left; \ - r->field.avl_left= MOD_TREE_BALANCE_##node##_##field(self); \ - return MOD_TREE_BALANCE_##node##_##field(r); \ - } \ - \ - struct node *MOD_TREE_ROTR_##node##_##field(struct node *self) \ - { \ - struct node *l= self->field.avl_left; \ - self->field.avl_left= l->field.avl_right; \ - l->field.avl_right= MOD_TREE_BALANCE_##node##_##field(self); \ - return MOD_TREE_BALANCE_##node##_##field(l); \ - } \ - \ - struct node *MOD_TREE_BALANCE_##node##_##field(struct node *self) \ - { \ - int delta= MOD_TREE_DELTA(self, field); \ - \ - if (delta < -MOD_TREE_DELTA_MAX) \ - { \ - if (MOD_TREE_DELTA(self->field.avl_right, field) > 0) \ - self->field.avl_right= MOD_TREE_ROTR_##node##_##field(self->field.avl_right); \ - return MOD_TREE_ROTL_##node##_##field(self); \ - } \ - else if (delta > MOD_TREE_DELTA_MAX) \ - { \ - if (MOD_TREE_DELTA(self->field.avl_left, field) < 0) \ - self->field.avl_left= MOD_TREE_ROTL_##node##_##field(self->field.avl_left); \ - return MOD_TREE_ROTR_##node##_##field(self); \ - } \ - self->field.avl_height= 0; \ - if (self->field.avl_left && (self->field.avl_left->field.avl_height > self->field.avl_height)) \ - self->field.avl_height= self->field.avl_left->field.avl_height; \ - if (self->field.avl_right && (self->field.avl_right->field.avl_height > self->field.avl_height)) \ - self->field.avl_height= self->field.avl_right->field.avl_height; \ - self->field.avl_height += 1; \ - return self; \ - } \ - \ - struct node *MOD_TREE_INSERT_##node##_##field \ - (struct node *self, struct node *elm, int (*compare)(void *lhs, void *rhs), int (*merge)(void **lhs, void **rhs), int *merged)\ - { \ - if (!self) { \ - *merged = 0; \ - return elm; } \ - int cmp = compare(elm->data, self->data); \ - if (cmp < 0) \ - self->field.avl_left= MOD_TREE_INSERT_##node##_##field(self->field.avl_left, elm, compare, merge, merged); \ - else if (cmp > 0) \ - self->field.avl_right= MOD_TREE_INSERT_##node##_##field(self->field.avl_right, elm, compare, merge, merged); \ - else if (merge) { \ - merge(&(self->data), &(elm->data)); \ - *merged = 1; } \ - else \ - self->field.avl_right= MOD_TREE_INSERT_##node##_##field(self->field.avl_right, elm, compare, merge, merged); \ - return MOD_TREE_BALANCE_##node##_##field(self); \ - } \ - \ - struct node *MOD_TREE_FIND_##node##_##field \ - (struct node *self, struct node *elm, int (*compare)(void *lhs, void *rhs)) \ - { \ - if (!compare) \ - return 0; \ - if (!self) \ - return 0; \ - if (compare(elm->data, self->data) == 0) \ - return self; \ - if (compare(elm->data, self->data) < 0) \ - return MOD_TREE_FIND_##node##_##field(self->field.avl_left, elm, compare); \ - else \ - return MOD_TREE_FIND_##node##_##field(self->field.avl_right, elm, compare); \ - } \ - \ - int MOD_TREE_FIND_LESS_EQUAL_##node##_##field \ - (struct node *self, struct node *elm, int (*compare)(void *lhs, void *rhs), struct node **found, struct node **prev) \ - { \ - if (!self) \ - return 0; \ - if (compare(elm->data, self->data) == 0) { \ - *found = self; \ - return 1; \ - } \ - if (compare(elm->data, self->data) < 0) { \ - int ret = MOD_TREE_FIND_LESS_EQUAL_##node##_##field(self->field.avl_left, elm, compare, found, prev); \ - if (ret == 0 && *prev == NULL) { \ - *prev = self; \ - ret = -1; \ - } \ - return ret; \ - } else { \ - *found = self; \ - *prev = self; \ - return MOD_TREE_FIND_LESS_EQUAL_##node##_##field(self->field.avl_right, elm, compare, found, prev); \ - } \ - } \ - \ - struct node *MOD_TREE_MOVE_RIGHT_##node##_##field(struct node *self, struct node *rhs) \ - { \ - if (!self) \ - return rhs; \ - self->field.avl_right= MOD_TREE_MOVE_RIGHT_##node##_##field(self->field.avl_right, rhs); \ - return MOD_TREE_BALANCE_##node##_##field(self); \ - } \ - \ - struct node *MOD_TREE_REMOVE_##node##_##field \ - (struct node *self, struct node *elm, int (*compare)(void *lhs, void *rhs), void (*del)(struct node *lhs)) \ - { \ - if (!self) return 0; \ - \ - if (compare(elm->data, self->data) == 0) \ - { \ - struct node *tmp= MOD_TREE_MOVE_RIGHT_##node##_##field(self->field.avl_left, self->field.avl_right); \ - self->field.avl_left= 0; \ - self->field.avl_right= 0; \ - del(self); \ - return tmp; \ - } \ - if (compare(elm->data, self->data) < 0) \ - self->field.avl_left= MOD_TREE_REMOVE_##node##_##field(self->field.avl_left, elm, compare, del); \ - else \ - self->field.avl_right= MOD_TREE_REMOVE_##node##_##field(self->field.avl_right, elm, compare, del); \ - return MOD_TREE_BALANCE_##node##_##field(self); \ - } \ - \ - void MOD_TREE_FORWARD_APPLY_ALL_##node##_##field \ - (struct node *self, void (*function)(void *node, void *data), void *data) \ - { \ - if (self) \ - { \ - MOD_TREE_FORWARD_APPLY_ALL_##node##_##field(self->field.avl_left, function, data); \ - function(self->data, data); \ - MOD_TREE_FORWARD_APPLY_ALL_##node##_##field(self->field.avl_right, function, data); \ - } \ - } \ - \ - void MOD_TREE_REVERSE_APPLY_ALL_##node##_##field \ - (struct node *self, void (*function)(struct node *node, void *data), void *data) \ - { \ - if (self) \ - { \ - MOD_TREE_REVERSE_APPLY_ALL_##node##_##field(self->field.avl_right, function, data); \ - function(self, data); \ - MOD_TREE_REVERSE_APPLY_ALL_##node##_##field(self->field.avl_left, function, data); \ - } \ - } \ - \ - void MOD_TREE_POST_ORDER_APPLY_ALL_##node##_##field \ - (struct node *self, void (*function)(struct node *node, void *data), void *data) \ - { \ - if (self) \ - { \ - MOD_TREE_POST_ORDER_APPLY_ALL_##node##_##field(self->field.avl_left, function, data); \ - MOD_TREE_POST_ORDER_APPLY_ALL_##node##_##field(self->field.avl_right, function, data); \ - function(self, data); \ - } \ - } \ - \ -void MOD_TREE_DESTROY_ALL_##node##_##field \ - (struct node *self, void (*function)(void *node, void *data), void(*dest)(struct node *node), void *data) \ -{ \ - if (self) \ - { \ - MOD_TREE_DESTROY_ALL_##node##_##field(self->field.avl_left, function, dest, data); \ - MOD_TREE_DESTROY_ALL_##node##_##field(self->field.avl_right, function, dest, data); \ - if (function != NULL) \ - function(self->data, data); \ - dest(self); \ - } \ -} \ - \ - void MOD_TREE_REVERSE_APPLY_POST_ALL_##node##_##field \ - (struct node *self, void (*function)(struct node *node, void *data), void *data) \ - { \ - if (self) \ - { \ - MOD_TREE_REVERSE_APPLY_POST_ALL_##node##_##field(self->field.avl_right, function, data); \ - MOD_TREE_REVERSE_APPLY_POST_ALL_##node##_##field(self->field.avl_left, function, data); \ - function(self, data); \ - } \ -} - -#define MOD_TREE_INSERT(head, node, field, elm, merge, merged) \ - ((head)->th_root= MOD_TREE_INSERT_##node##_##field((head)->th_root, (elm), (head)->th_cmp, merge, merged)) - -#define MOD_TREE_FIND(head, node, field, elm) \ - (MOD_TREE_FIND_##node##_##field((head)->th_root, (elm), (head)->th_cmp)) - -#define MOD_TREE_FIND_LESS_EQUAL(head, node, field, elm, found, prev) \ - (MOD_TREE_FIND_LESS_EQUAL_##node##_##field((head)->th_root, (elm), (head)->th_cmp, found, prev)) - -#define MOD_TREE_REMOVE(head, node, field, elm, rem) \ - ((head)->th_root= MOD_TREE_REMOVE_##node##_##field((head)->th_root, (elm), (head)->th_cmp, (rem))) - -#define MOD_TREE_DEPTH(head, field) \ - ((head)->th_root->field.avl_height) - -#define MOD_TREE_FORWARD_APPLY(head, node, field, function, data) \ - MOD_TREE_FORWARD_APPLY_ALL_##node##_##field((head)->th_root, function, data) - -#define MOD_TREE_REVERSE_APPLY(head, node, field, function, data) \ - MOD_TREE_REVERSE_APPLY_ALL_##node##_##field((head)->th_root, function, data) - -#define MOD_TREE_POST_ORDER_APPLY(head, node, field, function, data) \ - MOD_TREE_POST_ORDER_APPLY_ALL_##node##_##field((head)->th_root, function, data) - -#define MOD_TREE_DESTROY(head, node, field, function, dest, data) \ - MOD_TREE_DESTROY_ALL_##node##_##field((head)->th_root, function, dest, data) - -#define MOD_TREE_REVERSE_APPLY_POST(head, node, field, function, data) \ - MOD_TREE_REVERSE_APPLY_POST_ALL_##node##_##field((head)->th_root, function, data) - -#define MOD_TREE_INIT(head, cmp) do { \ - (head)->th_root= 0; \ - (head)->th_cmp= (cmp); \ - } while (0) - - -#endif /* __MOD_TREE_h */ |