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