70 #define TREE_DELTA(self, field)								\  argument
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))
76 #define TREE_DEFINE(node, field)									\  argument
78   static struct node *_HU_FUNCTION(TREE_BALANCE_##node##_##field)(struct node *);						\
80   static struct node *_HU_FUNCTION(TREE_ROTL_##node##_##field)(struct node *self)						\
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);								\
88   static struct node *_HU_FUNCTION(TREE_ROTR_##node##_##field)(struct node *self)						\
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);								\
96   static struct node *_HU_FUNCTION(TREE_BALANCE_##node##_##field)(struct node *self)						\
98     int delta= TREE_DELTA(self, field);									\
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);							\
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);							\
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;									\
121   static struct node *_HU_FUNCTION(TREE_INSERT_##node##_##field)								\
127       self->field.avl_left= TREE_INSERT_##node##_##field(self->field.avl_left, elm, compare);		\
129       self->field.avl_right= TREE_INSERT_##node##_##field(self->field.avl_right, elm, compare);		\
130     return TREE_BALANCE_##node##_##field(self);								\
133   static struct node *_HU_FUNCTION(TREE_FIND_##node##_##field)								\
141       return TREE_FIND_##node##_##field(self->field.avl_left, elm, compare);				\
143       return TREE_FIND_##node##_##field(self->field.avl_right, elm, compare);				\
150     self->field.avl_right= TREE_MOVE_RIGHT(self->field.avl_right, rhs);					\
151     return TREE_BALANCE_##node##_##field(self);								\
154   static struct node *_HU_FUNCTION(TREE_REMOVE_##node##_##field)								\
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;									\
167       self->field.avl_left= TREE_REMOVE_##node##_##field(self->field.avl_left, elm, compare);		\
169       self->field.avl_right= TREE_REMOVE_##node##_##field(self->field.avl_right, elm, compare);		\
170     return TREE_BALANCE_##node##_##field(self);								\
173   static void _HU_FUNCTION(TREE_FORWARD_APPLY_ALL_##node##_##field)								\
178 	TREE_FORWARD_APPLY_ALL_##node##_##field(self->field.avl_left, function, data);			\
180 	TREE_FORWARD_APPLY_ALL_##node##_##field(self->field.avl_right, function, data);			\
184   static void _HU_FUNCTION(TREE_REVERSE_APPLY_ALL_##node##_##field)								\
189 	TREE_REVERSE_APPLY_ALL_##node##_##field(self->field.avl_right, function, data);			\
191 	TREE_REVERSE_APPLY_ALL_##node##_##field(self->field.avl_left, function, data);			\
195 #define TREE_INSERT(head, node, field, elm)						\  argument
196   ((head)->th_root= TREE_INSERT_##node##_##field((head)->th_root, (elm), (head)->th_cmp))
198 #define TREE_FIND(head, node, field, elm)				\  argument
199   (TREE_FIND_##node##_##field((head)->th_root, (elm), (head)->th_cmp))
201 #define TREE_REMOVE(head, node, field, elm)						\  argument
202   ((head)->th_root= TREE_REMOVE_##node##_##field((head)->th_root, (elm), (head)->th_cmp))
204 #define TREE_DEPTH(head, field)			\  argument
205   ((head)->th_root->field.avl_height)
207 #define TREE_FORWARD_APPLY(head, node, field, function, data)	\  argument
208   TREE_FORWARD_APPLY_ALL_##node##_##field((head)->th_root, function, data)
210 #define TREE_REVERSE_APPLY(head, node, field, function, data)	\  argument
211   TREE_REVERSE_APPLY_ALL_##node##_##field((head)->th_root, function, data)