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)) - (((self)->field.avl_right) ? (self)->field.avl_right->field.avl_height : 0)) 72 73 /* Recursion prevents the following from being defined as macros. */ 74 75 #define TREE_DEFINE(node, field) \ 76 \ 77 static struct node *_HU_FUNCTION(TREE_BALANCE_##node##_##field)(struct node *); \ 78 \ 79 static struct node *_HU_FUNCTION(TREE_ROTL_##node##_##field)(struct node * self) \ 80 { \ 81 struct node *r = self->field.avl_right; \ 82 self->field.avl_right = r->field.avl_left; \ 83 r->field.avl_left = TREE_BALANCE_##node##_##field(self); \ 84 return TREE_BALANCE_##node##_##field(r); \ 85 } \ 86 \ 87 static struct node *_HU_FUNCTION(TREE_ROTR_##node##_##field)(struct node * self) \ 88 { \ 89 struct node *l = self->field.avl_left; \ 90 self->field.avl_left = l->field.avl_right; \ 91 l->field.avl_right = TREE_BALANCE_##node##_##field(self); \ 92 return TREE_BALANCE_##node##_##field(l); \ 93 } \ 94 \ 95 static struct node *_HU_FUNCTION(TREE_BALANCE_##node##_##field)(struct node * self) \ 96 { \ 97 int delta = TREE_DELTA(self, field); \ 98 \ 99 if (delta < -TREE_DELTA_MAX) { \ 100 if (TREE_DELTA(self->field.avl_right, field) > 0) \ 101 self->field.avl_right = TREE_ROTR_##node##_##field(self->field.avl_right); \ 102 return TREE_ROTL_##node##_##field(self); \ 103 } \ 104 else if (delta > TREE_DELTA_MAX) { \ 105 if (TREE_DELTA(self->field.avl_left, field) < 0) \ 106 self->field.avl_left = TREE_ROTL_##node##_##field(self->field.avl_left); \ 107 return TREE_ROTR_##node##_##field(self); \ 108 } \ 109 self->field.avl_height = 0; \ 110 if (self->field.avl_left && (self->field.avl_left->field.avl_height > self->field.avl_height)) \ 111 self->field.avl_height = self->field.avl_left->field.avl_height; \ 112 if (self->field.avl_right && (self->field.avl_right->field.avl_height > self->field.avl_height)) \ 113 self->field.avl_height = self->field.avl_right->field.avl_height; \ 114 self->field.avl_height += 1; \ 115 return self; \ 116 } \ 117 \ 118 static struct node *_HU_FUNCTION(TREE_INSERT_##node##_##field)(struct node * self, struct node * elm, int (*compare)(struct node * lhs, struct node * rhs)) \ 119 { \ 120 if (!self) \ 121 return elm; \ 122 if (compare(elm, self) < 0) \ 123 self->field.avl_left = TREE_INSERT_##node##_##field(self->field.avl_left, elm, compare); \ 124 else \ 125 self->field.avl_right = TREE_INSERT_##node##_##field(self->field.avl_right, elm, compare); \ 126 return TREE_BALANCE_##node##_##field(self); \ 127 } \ 128 \ 129 static struct node *_HU_FUNCTION(TREE_FIND_##node##_##field)(struct node * self, struct node * elm, int (*compare)(struct node * lhs, struct node * rhs)) \ 130 { \ 131 if (!self) \ 132 return 0; \ 133 if (compare(elm, self) == 0) \ 134 return self; \ 135 if (compare(elm, self) < 0) \ 136 return TREE_FIND_##node##_##field(self->field.avl_left, elm, compare); \ 137 else \ 138 return TREE_FIND_##node##_##field(self->field.avl_right, elm, compare); \ 139 } \ 140 \ 141 static struct node *_HU_FUNCTION(TREE_MOVE_RIGHT)(struct node * self, struct node * rhs) \ 142 { \ 143 if (!self) \ 144 return rhs; \ 145 self->field.avl_right = TREE_MOVE_RIGHT(self->field.avl_right, rhs); \ 146 return TREE_BALANCE_##node##_##field(self); \ 147 } \ 148 \ 149 static struct node *_HU_FUNCTION(TREE_REMOVE_##node##_##field)(struct node * self, struct node * elm, int (*compare)(struct node * lhs, struct node * rhs)) \ 150 { \ 151 if (!self) return 0; \ 152 \ 153 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; \ 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 static void _HU_FUNCTION(TREE_FORWARD_APPLY_ALL_##node##_##field)(struct node * self, void (*function)(struct node * node, void *data), void *data) \ 167 { \ 168 if (self) { \ 169 TREE_FORWARD_APPLY_ALL_##node##_##field(self->field.avl_left, function, data); \ 170 function(self, data); \ 171 TREE_FORWARD_APPLY_ALL_##node##_##field(self->field.avl_right, function, data); \ 172 } \ 173 } \ 174 \ 175 static void _HU_FUNCTION(TREE_REVERSE_APPLY_ALL_##node##_##field)(struct node * self, void (*function)(struct node * node, void *data), void *data) \ 176 { \ 177 if (self) { \ 178 TREE_REVERSE_APPLY_ALL_##node##_##field(self->field.avl_right, function, data); \ 179 function(self, data); \ 180 TREE_REVERSE_APPLY_ALL_##node##_##field(self->field.avl_left, function, data); \ 181 } \ 182 } 183 184 #define TREE_INSERT(head, node, field, elm) \ 185 ((head)->th_root = TREE_INSERT_##node##_##field((head)->th_root, (elm), (head)->th_cmp)) 186 187 #define TREE_FIND(head, node, field, elm) \ 188 (TREE_FIND_##node##_##field((head)->th_root, (elm), (head)->th_cmp)) 189 190 #define TREE_REMOVE(head, node, field, elm) \ 191 ((head)->th_root = TREE_REMOVE_##node##_##field((head)->th_root, (elm), (head)->th_cmp)) 192 193 #define TREE_DEPTH(head, field) \ 194 ((head)->th_root->field.avl_height) 195 196 #define TREE_FORWARD_APPLY(head, node, field, function, data) \ 197 TREE_FORWARD_APPLY_ALL_##node##_##field((head)->th_root, function, data) 198 199 #define TREE_REVERSE_APPLY(head, node, field, function, data) \ 200 TREE_REVERSE_APPLY_ALL_##node##_##field((head)->th_root, function, data) 201 202 #define TREE_INIT(head, cmp) \ 203 do { \ 204 (head)->th_root = 0; \ 205 (head)->th_cmp = (cmp); \ 206 } while (0) 207 208 209 #endif /* __tree_h */ 210