tree.h revision 268896 
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