1 /* tree.h -- AVL trees (in the spirit of BSD's 'queue.h') -*- C -*- */ 2 3 /* Copyright (c) 2005 Ian Piumarta 4 * 5 * All rights reserved. 6 * 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. 15 * 16 * THE SOFTWARE IS PROVIDED 'AS IS'. USE ENTIRELY AT YOUR OWN RISK. 17 */ 18 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)]. 23 * 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). 32 * 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. 38 * 39 * For details on the use of these macros, see the tree(3) manual page. 40 */ 41 42 #ifndef __tree_h 43 #define __tree_h 44 45 46 #define TREE_DELTA_MAX 1 47 48 #define TREE_ENTRY(type) \ 49 struct { \ 50 struct type *avl_left; \ 51 struct type *avl_right; \ 52 int avl_height; \ 53 } 54 55 #define TREE_HEAD(name, type) \ 56 struct name { \ 57 struct type *th_root; \ 58 int (*th_cmp)(struct type *lhs, struct type *rhs); \ 59 } 60 61 #define TREE_INITIALIZER(cmp) { 0, cmp } 62 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)) 66 67 /* Recursion prevents the following from being defined as macros. */ 68 69 #define TREE_DEFINE(node, field) \ 70 \ 71 struct node *TREE_BALANCE_##node##_##field(struct node *); \ 72 \ 73 struct node *TREE_ROTL_##node##_##field(struct node *self) \ 74 { \ 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); \ 79 } \ 80 \ 81 struct node *TREE_ROTR_##node##_##field(struct node *self) \ 82 { \ 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); \ 87 } \ 88 \ 89 struct node *TREE_BALANCE_##node##_##field(struct node *self) \ 90 { \ 91 int delta= TREE_DELTA(self, field); \ 92 \ 93 if (delta < -TREE_DELTA_MAX) \ 94 { \ 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); \ 98 } \ 99 else if (delta > TREE_DELTA_MAX) \ 100 { \ 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); \ 104 } \ 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; \ 111 return self; \ 112 } \ 113 \ 114 struct node *TREE_INSERT_##node##_##field \ 115 (struct node *self, struct node *elm, int (*compare)(struct node *lhs, struct node *rhs)) \ 116 { \ 117 if (!self) \ 118 return elm; \ 119 if (compare(elm, self) < 0) \ 120 self->field.avl_left= TREE_INSERT_##node##_##field(self->field.avl_left, elm, compare); \ 121 else \ 122 self->field.avl_right= TREE_INSERT_##node##_##field(self->field.avl_right, elm, compare); \ 123 return TREE_BALANCE_##node##_##field(self); \ 124 } \ 125 \ 126 struct node *TREE_FIND_##node##_##field \ 127 (struct node *self, struct node *elm, int (*compare)(struct node *lhs, struct node *rhs)) \ 128 { \ 129 if (!self) \ 130 return 0; \ 131 if (compare(elm, self) == 0) \ 132 return self; \ 133 if (compare(elm, self) < 0) \ 134 return TREE_FIND_##node##_##field(self->field.avl_left, elm, compare); \ 135 else \ 136 return TREE_FIND_##node##_##field(self->field.avl_right, elm, compare); \ 137 } \ 138 \ 139 struct node *TREE_MOVE_RIGHT(struct node *self, struct node *rhs) \ 140 { \ 141 if (!self) \ 142 return rhs; \ 143 self->field.avl_right= TREE_MOVE_RIGHT(self->field.avl_right, rhs); \ 144 return TREE_BALANCE_##node##_##field(self); \ 145 } \ 146 \ 147 struct node *TREE_REMOVE_##node##_##field \ 148 (struct node *self, struct node *elm, int (*compare)(struct node *lhs, struct node *rhs)) \ 149 { \ 150 if (!self) return 0; \ 151 \ 152 if (compare(elm, self) == 0) \ 153 { \ 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; \ 157 return tmp; \ 158 } \ 159 if (compare(elm, self) < 0) \ 160 self->field.avl_left= TREE_REMOVE_##node##_##field(self->field.avl_left, elm, compare); \ 161 else \ 162 self->field.avl_right= TREE_REMOVE_##node##_##field(self->field.avl_right, elm, compare); \ 163 return TREE_BALANCE_##node##_##field(self); \ 164 } \ 165 \ 166 void TREE_FORWARD_APPLY_ALL_##node##_##field \ 167 (struct node *self, void (*function)(struct node *node, void *data), void *data) \ 168 { \ 169 if (self) \ 170 { \ 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); \ 174 } \ 175 } \ 176 \ 177 void TREE_REVERSE_APPLY_ALL_##node##_##field \ 178 (struct node *self, void (*function)(struct node *node, void *data), void *data) \ 179 { \ 180 if (self) \ 181 { \ 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); \ 185 } \ 186 } 187 188 #define TREE_INSERT(head, node, field, elm) \ 189 ((head)->th_root= TREE_INSERT_##node##_##field((head)->th_root, (elm), (head)->th_cmp)) 190 191 #define TREE_FIND(head, node, field, elm) \ 192 (TREE_FIND_##node##_##field((head)->th_root, (elm), (head)->th_cmp)) 193 194 #define TREE_REMOVE(head, node, field, elm) \ 195 ((head)->th_root= TREE_REMOVE_##node##_##field((head)->th_root, (elm), (head)->th_cmp)) 196 197 #define TREE_DEPTH(head, field) \ 198 ((head)->th_root->field.avl_height) 199 200 #define TREE_FORWARD_APPLY(head, node, field, function, data) \ 201 TREE_FORWARD_APPLY_ALL_##node##_##field((head)->th_root, function, data) 202 203 #define TREE_REVERSE_APPLY(head, node, field, function, data) \ 204 TREE_REVERSE_APPLY_ALL_##node##_##field((head)->th_root, function, data) 205 206 #define TREE_INIT(head, cmp) do { \ 207 (head)->th_root= 0; \ 208 (head)->th_cmp= (cmp); \ 209 } while (0) 210 211 212 #endif /* __tree_h */ 213