1 /* tree.h -- AVL trees (in the spirit of BSD's 'queue.h') -*- C -*- */
3 /* Copyright (c) 2005 Ian Piumarta
7 * Permission is hereby granted, free of charge, to any person obtaining a copy
8 * of this software and associated documentation files (the 'Software'), to deal
9 * in the Software without restriction, including without limitation the rights
10 * to use, copy, modify, merge, publish, distribute, and/or sell copies of the
11 * Software, and to permit persons to whom the Software is furnished to do so,
12 * provided that the above copyright notice(s) and this permission notice appear
13 * in all copies of the Software and that both the above copyright notice(s) and
14 * this permission notice appear in supporting documentation.
16 * THE SOFTWARE IS PROVIDED 'AS IS'. USE ENTIRELY AT YOUR OWN RISK.
19 /* This file defines an AVL balanced binary tree [Georgii M. Adelson-Velskii and
20 * Evgenii M. Landis, 'An algorithm for the organization of information',
21 * Doklady Akademii Nauk SSSR, 146:263-266, 1962 (Russian). Also in Myron
22 * J. Ricci (trans.), Soviet Math, 3:1259-1263, 1962 (English)].
24 * An AVL tree is headed by pointers to the root node and to a function defining
25 * the ordering relation between nodes. Each node contains an arbitrary payload
26 * plus three fields per tree entry: the depth of the subtree for which it forms
27 * the root and two pointers to child nodes (singly-linked for minimum space, at
28 * the expense of direct access to the parent node given a pointer to one of the
29 * children). The tree is rebalanced after every insertion or removal. The
30 * tree may be traversed in two directions: forward (in-order left-to-right) and
31 * reverse (in-order, right-to-left).
33 * Because of the recursive nature of many of the operations on trees it is
34 * necessary to define a number of helper functions for each type of tree node.
35 * The macro TREE_DEFINE(node_tag, entry_name) defines these functions with
36 * unique names according to the node_tag. This macro should be invoked,
37 * thereby defining the necessary functions, once per node tag in the program.
39 * For details on the use of these macros, see the tree(3) manual page.
46 #define TREE_DELTA_MAX 1
48 #define TREE_ENTRY(type) \
50 struct type *avl_left; \
51 struct type *avl_right; \
55 #define TREE_HEAD(name, type) \
57 struct type *th_root; \
58 int (*th_cmp)(struct type *lhs, struct type *rhs); \
61 #define TREE_INITIALIZER(cmp) { 0, cmp }
63 #define TREE_DELTA(self, field) \
64 (( (((self)->field.avl_left) ? (self)->field.avl_left->field.avl_height : 0)) \
65 - (((self)->field.avl_right) ? (self)->field.avl_right->field.avl_height : 0))
67 /* Recursion prevents the following from being defined as macros. */
69 #define TREE_DEFINE(node, field) \
71 struct node *TREE_BALANCE_##node##_##field(struct node *); \
73 struct node *TREE_ROTL_##node##_##field(struct node *self) \
75 struct node *r= self->field.avl_right; \
76 self->field.avl_right= r->field.avl_left; \
77 r->field.avl_left= TREE_BALANCE_##node##_##field(self); \
78 return TREE_BALANCE_##node##_##field(r); \
81 struct node *TREE_ROTR_##node##_##field(struct node *self) \
83 struct node *l= self->field.avl_left; \
84 self->field.avl_left= l->field.avl_right; \
85 l->field.avl_right= TREE_BALANCE_##node##_##field(self); \
86 return TREE_BALANCE_##node##_##field(l); \
89 struct node *TREE_BALANCE_##node##_##field(struct node *self) \
91 int delta= TREE_DELTA(self, field); \
93 if (delta < -TREE_DELTA_MAX) \
95 if (TREE_DELTA(self->field.avl_right, field) > 0) \
96 self->field.avl_right= TREE_ROTR_##node##_##field(self->field.avl_right); \
97 return TREE_ROTL_##node##_##field(self); \
99 else if (delta > TREE_DELTA_MAX) \
101 if (TREE_DELTA(self->field.avl_left, field) < 0) \
102 self->field.avl_left= TREE_ROTL_##node##_##field(self->field.avl_left); \
103 return TREE_ROTR_##node##_##field(self); \
105 self->field.avl_height= 0; \
106 if (self->field.avl_left && (self->field.avl_left->field.avl_height > self->field.avl_height)) \
107 self->field.avl_height= self->field.avl_left->field.avl_height; \
108 if (self->field.avl_right && (self->field.avl_right->field.avl_height > self->field.avl_height)) \
109 self->field.avl_height= self->field.avl_right->field.avl_height; \
110 self->field.avl_height += 1; \
114 struct node *TREE_INSERT_##node##_##field \
115 (struct node *self, struct node *elm, int (*compare)(struct node *lhs, struct node *rhs)) \
119 if (compare(elm, self) < 0) \
120 self->field.avl_left= TREE_INSERT_##node##_##field(self->field.avl_left, elm, compare); \
122 self->field.avl_right= TREE_INSERT_##node##_##field(self->field.avl_right, elm, compare); \
123 return TREE_BALANCE_##node##_##field(self); \
126 struct node *TREE_FIND_##node##_##field \
127 (struct node *self, struct node *elm, int (*compare)(struct node *lhs, struct node *rhs)) \
131 if (compare(elm, self) == 0) \
133 if (compare(elm, self) < 0) \
134 return TREE_FIND_##node##_##field(self->field.avl_left, elm, compare); \
136 return TREE_FIND_##node##_##field(self->field.avl_right, elm, compare); \
139 struct node *TREE_MOVE_RIGHT(struct node *self, struct node *rhs) \
143 self->field.avl_right= TREE_MOVE_RIGHT(self->field.avl_right, rhs); \
144 return TREE_BALANCE_##node##_##field(self); \
147 struct node *TREE_REMOVE_##node##_##field \
148 (struct node *self, struct node *elm, int (*compare)(struct node *lhs, struct node *rhs)) \
150 if (!self) return 0; \
152 if (compare(elm, self) == 0) \
154 struct node *tmp= TREE_MOVE_RIGHT(self->field.avl_left, self->field.avl_right); \
155 self->field.avl_left= 0; \
156 self->field.avl_right= 0; \
159 if (compare(elm, self) < 0) \
160 self->field.avl_left= TREE_REMOVE_##node##_##field(self->field.avl_left, elm, compare); \
162 self->field.avl_right= TREE_REMOVE_##node##_##field(self->field.avl_right, elm, compare); \
163 return TREE_BALANCE_##node##_##field(self); \
166 void TREE_FORWARD_APPLY_ALL_##node##_##field \
167 (struct node *self, void (*function)(struct node *node, void *data), void *data) \
171 TREE_FORWARD_APPLY_ALL_##node##_##field(self->field.avl_left, function, data); \
172 function(self, data); \
173 TREE_FORWARD_APPLY_ALL_##node##_##field(self->field.avl_right, function, data); \
177 void TREE_REVERSE_APPLY_ALL_##node##_##field \
178 (struct node *self, void (*function)(struct node *node, void *data), void *data) \
182 TREE_REVERSE_APPLY_ALL_##node##_##field(self->field.avl_right, function, data); \
183 function(self, data); \
184 TREE_REVERSE_APPLY_ALL_##node##_##field(self->field.avl_left, function, data); \
188 #define TREE_INSERT(head, node, field, elm) \
189 ((head)->th_root= TREE_INSERT_##node##_##field((head)->th_root, (elm), (head)->th_cmp))
191 #define TREE_FIND(head, node, field, elm) \
192 (TREE_FIND_##node##_##field((head)->th_root, (elm), (head)->th_cmp))
194 #define TREE_REMOVE(head, node, field, elm) \
195 ((head)->th_root= TREE_REMOVE_##node##_##field((head)->th_root, (elm), (head)->th_cmp))
197 #define TREE_DEPTH(head, field) \
198 ((head)->th_root->field.avl_height)
200 #define TREE_FORWARD_APPLY(head, node, field, function, data) \
201 TREE_FORWARD_APPLY_ALL_##node##_##field((head)->th_root, function, data)
203 #define TREE_REVERSE_APPLY(head, node, field, function, data) \
204 TREE_REVERSE_APPLY_ALL_##node##_##field((head)->th_root, function, data)
206 #define TREE_INIT(head, cmp) do { \
207 (head)->th_root= 0; \
208 (head)->th_cmp= (cmp); \
212 #endif /* __tree_h */