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 #ifndef _HU_FUNCTION 48 # if defined(__GNUC__) || defined(__clang__) 49 # define _HU_FUNCTION(x) __attribute__((__unused__)) x 50 # else 51 # define _HU_FUNCTION(x) x 52 # endif 53 #endif 54 55 #define TREE_ENTRY(type) \ 56 struct { \ 57 struct type *avl_left; \ 58 struct type *avl_right; \ 59 int avl_height; \ 60 } 61 62 #define TREE_HEAD(name, type) \ 63 struct name { \ 64 struct type *th_root; \ 65 int (*th_cmp)(struct type *lhs, struct type *rhs); \ 66 } 67 68 #define TREE_INITIALIZER(cmp) { 0, cmp } 69 70 #define TREE_DELTA(self, field) \ 71 (( (((self)->field.avl_left) ? (self)->field.avl_left->field.avl_height : 0)) \ 72 - (((self)->field.avl_right) ? (self)->field.avl_right->field.avl_height : 0)) 73 74 /* Recursion prevents the following from being defined as macros. */ 75 76 #define TREE_DEFINE(node, field) \ 77 \ 78 static struct node *_HU_FUNCTION(TREE_BALANCE_##node##_##field)(struct node *); \ 79 \ 80 static struct node *_HU_FUNCTION(TREE_ROTL_##node##_##field)(struct node *self) \ 81 { \ 82 struct node *r= self->field.avl_right; \ 83 self->field.avl_right= r->field.avl_left; \ 84 r->field.avl_left= TREE_BALANCE_##node##_##field(self); \ 85 return TREE_BALANCE_##node##_##field(r); \ 86 } \ 87 \ 88 static struct node *_HU_FUNCTION(TREE_ROTR_##node##_##field)(struct node *self) \ 89 { \ 90 struct node *l= self->field.avl_left; \ 91 self->field.avl_left= l->field.avl_right; \ 92 l->field.avl_right= TREE_BALANCE_##node##_##field(self); \ 93 return TREE_BALANCE_##node##_##field(l); \ 94 } \ 95 \ 96 static struct node *_HU_FUNCTION(TREE_BALANCE_##node##_##field)(struct node *self) \ 97 { \ 98 int delta= TREE_DELTA(self, field); \ 99 \ 100 if (delta < -TREE_DELTA_MAX) \ 101 { \ 102 if (TREE_DELTA(self->field.avl_right, field) > 0) \ 103 self->field.avl_right= TREE_ROTR_##node##_##field(self->field.avl_right); \ 104 return TREE_ROTL_##node##_##field(self); \ 105 } \ 106 else if (delta > TREE_DELTA_MAX) \ 107 { \ 108 if (TREE_DELTA(self->field.avl_left, field) < 0) \ 109 self->field.avl_left= TREE_ROTL_##node##_##field(self->field.avl_left); \ 110 return TREE_ROTR_##node##_##field(self); \ 111 } \ 112 self->field.avl_height= 0; \ 113 if (self->field.avl_left && (self->field.avl_left->field.avl_height > self->field.avl_height)) \ 114 self->field.avl_height= self->field.avl_left->field.avl_height; \ 115 if (self->field.avl_right && (self->field.avl_right->field.avl_height > self->field.avl_height)) \ 116 self->field.avl_height= self->field.avl_right->field.avl_height; \ 117 self->field.avl_height += 1; \ 118 return self; \ 119 } \ 120 \ 121 static struct node *_HU_FUNCTION(TREE_INSERT_##node##_##field) \ 122 (struct node *self, struct node *elm, int (*compare)(struct node *lhs, struct node *rhs)) \ 123 { \ 124 if (!self) \ 125 return elm; \ 126 if (compare(elm, self) < 0) \ 127 self->field.avl_left= TREE_INSERT_##node##_##field(self->field.avl_left, elm, compare); \ 128 else \ 129 self->field.avl_right= TREE_INSERT_##node##_##field(self->field.avl_right, elm, compare); \ 130 return TREE_BALANCE_##node##_##field(self); \ 131 } \ 132 \ 133 static struct node *_HU_FUNCTION(TREE_FIND_##node##_##field) \ 134 (struct node *self, struct node *elm, int (*compare)(struct node *lhs, struct node *rhs)) \ 135 { \ 136 if (!self) \ 137 return 0; \ 138 if (compare(elm, self) == 0) \ 139 return self; \ 140 if (compare(elm, self) < 0) \ 141 return TREE_FIND_##node##_##field(self->field.avl_left, elm, compare); \ 142 else \ 143 return TREE_FIND_##node##_##field(self->field.avl_right, elm, compare); \ 144 } \ 145 \ 146 static struct node *_HU_FUNCTION(TREE_MOVE_RIGHT)(struct node *self, struct node *rhs) \ 147 { \ 148 if (!self) \ 149 return rhs; \ 150 self->field.avl_right= TREE_MOVE_RIGHT(self->field.avl_right, rhs); \ 151 return TREE_BALANCE_##node##_##field(self); \ 152 } \ 153 \ 154 static struct node *_HU_FUNCTION(TREE_REMOVE_##node##_##field) \ 155 (struct node *self, struct node *elm, int (*compare)(struct node *lhs, struct node *rhs)) \ 156 { \ 157 if (!self) return 0; \ 158 \ 159 if (compare(elm, self) == 0) \ 160 { \ 161 struct node *tmp= TREE_MOVE_RIGHT(self->field.avl_left, self->field.avl_right); \ 162 self->field.avl_left= 0; \ 163 self->field.avl_right= 0; \ 164 return tmp; \ 165 } \ 166 if (compare(elm, self) < 0) \ 167 self->field.avl_left= TREE_REMOVE_##node##_##field(self->field.avl_left, elm, compare); \ 168 else \ 169 self->field.avl_right= TREE_REMOVE_##node##_##field(self->field.avl_right, elm, compare); \ 170 return TREE_BALANCE_##node##_##field(self); \ 171 } \ 172 \ 173 static void _HU_FUNCTION(TREE_FORWARD_APPLY_ALL_##node##_##field) \ 174 (struct node *self, void (*function)(struct node *node, void *data), void *data) \ 175 { \ 176 if (self) \ 177 { \ 178 TREE_FORWARD_APPLY_ALL_##node##_##field(self->field.avl_left, function, data); \ 179 function(self, data); \ 180 TREE_FORWARD_APPLY_ALL_##node##_##field(self->field.avl_right, function, data); \ 181 } \ 182 } \ 183 \ 184 static void _HU_FUNCTION(TREE_REVERSE_APPLY_ALL_##node##_##field) \ 185 (struct node *self, void (*function)(struct node *node, void *data), void *data) \ 186 { \ 187 if (self) \ 188 { \ 189 TREE_REVERSE_APPLY_ALL_##node##_##field(self->field.avl_right, function, data); \ 190 function(self, data); \ 191 TREE_REVERSE_APPLY_ALL_##node##_##field(self->field.avl_left, function, data); \ 192 } \ 193 } 194 195 #define TREE_INSERT(head, node, field, elm) \ 196 ((head)->th_root= TREE_INSERT_##node##_##field((head)->th_root, (elm), (head)->th_cmp)) 197 198 #define TREE_FIND(head, node, field, elm) \ 199 (TREE_FIND_##node##_##field((head)->th_root, (elm), (head)->th_cmp)) 200 201 #define TREE_REMOVE(head, node, field, elm) \ 202 ((head)->th_root= TREE_REMOVE_##node##_##field((head)->th_root, (elm), (head)->th_cmp)) 203 204 #define TREE_DEPTH(head, field) \ 205 ((head)->th_root->field.avl_height) 206 207 #define TREE_FORWARD_APPLY(head, node, field, function, data) \ 208 TREE_FORWARD_APPLY_ALL_##node##_##field((head)->th_root, function, data) 209 210 #define TREE_REVERSE_APPLY(head, node, field, function, data) \ 211 TREE_REVERSE_APPLY_ALL_##node##_##field((head)->th_root, function, data) 212 213 #define TREE_INIT(head, cmp) do { \ 214 (head)->th_root= 0; \ 215 (head)->th_cmp= (cmp); \ 216 } while (0) 217 218 219 #endif /* __tree_h */ 220