/* tree.h -- AVL trees (in the spirit of BSD's 'queue.h') -*- C -*- */
/* Copyright (c) 2005 Ian Piumarta
*
* All rights reserved.
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the 'Software'), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, and/or sell copies of the
* Software, and to permit persons to whom the Software is furnished to do so,
* provided that the above copyright notice(s) and this permission notice appear
* in all copies of the Software and that both the above copyright notice(s) and
* this permission notice appear in supporting documentation.
*
* THE SOFTWARE IS PROVIDED 'AS IS'. USE ENTIRELY AT YOUR OWN RISK.
*/
/* This file defines an AVL balanced binary tree [Georgii M. Adelson-Velskii and
* Evgenii M. Landis, 'An algorithm for the organization of information',
* Doklady Akademii Nauk SSSR, 146:263-266, 1962 (Russian). Also in Myron
* J. Ricci (trans.), Soviet Math, 3:1259-1263, 1962 (English)].
*
* An AVL tree is headed by pointers to the root node and to a function defining
* the ordering relation between nodes. Each node contains an arbitrary payload
* plus three fields per tree entry: the depth of the subtree for which it forms
* the root and two pointers to child nodes (singly-linked for minimum space, at
* the expense of direct access to the parent node given a pointer to one of the
* children). The tree is rebalanced after every insertion or removal. The
* tree may be traversed in two directions: forward (in-order left-to-right) and
* reverse (in-order, right-to-left).
*
* Because of the recursive nature of many of the operations on trees it is
* necessary to define a number of helper functions for each type of tree node.
* The macro TREE_DEFINE(node_tag, entry_name) defines these functions with
* unique names according to the node_tag. This macro should be invoked,
* thereby defining the necessary functions, once per node tag in the program.
*
* For details on the use of these macros, see the tree(3) manual page.
*/
#ifndef __tree_h
#define __tree_h
#define TREE_DELTA_MAX 1
#ifndef _HU_FUNCTION
#if defined(__GNUC__) || defined(__clang__)
#define _HU_FUNCTION(x) __attribute__((__unused__)) x
#else
#define _HU_FUNCTION(x) x
#endif
#endif
#define TREE_ENTRY(type) \
struct { \
struct type *avl_left; \
struct type *avl_right; \
int avl_height; \
}
#define TREE_HEAD(name, type) \
struct name { \
struct type *th_root; \
int (*th_cmp)(struct type * lhs, struct type *rhs); \
}
#define TREE_INITIALIZER(cmp) {0, cmp}
#define TREE_DELTA(self, field) \
(((((self)->field.avl_left) ? (self)->field.avl_left->field.avl_height : 0)) - (((self)->field.avl_right) ? (self)->field.avl_right->field.avl_height : 0))
/* Recursion prevents the following from being defined as macros. */
#define TREE_DEFINE(node, field) \
\
static struct node *_HU_FUNCTION(TREE_BALANCE_##node##_##field)(struct node *); \
\
static struct node *_HU_FUNCTION(TREE_ROTL_##node##_##field)(struct node * self) \
{ \
struct node *r = self->field.avl_right; \
self->field.avl_right = r->field.avl_left; \
r->field.avl_left = TREE_BALANCE_##node##_##field(self); \
return TREE_BALANCE_##node##_##field(r); \
} \
\
static struct node *_HU_FUNCTION(TREE_ROTR_##node##_##field)(struct node * self) \
{ \
struct node *l = self->field.avl_left; \
self->field.avl_left = l->field.avl_right; \
l->field.avl_right = TREE_BALANCE_##node##_##field(self); \
return TREE_BALANCE_##node##_##field(l); \
} \
\
static struct node *_HU_FUNCTION(TREE_BALANCE_##node##_##field)(struct node * self) \
{ \
int delta = TREE_DELTA(self, field); \
\
if (delta < -TREE_DELTA_MAX) { \
if (TREE_DELTA(self->field.avl_right, field) > 0) \
self->field.avl_right = TREE_ROTR_##node##_##field(self->field.avl_right); \
return TREE_ROTL_##node##_##field(self); \
} \
else if (delta > TREE_DELTA_MAX) { \
if (TREE_DELTA(self->field.avl_left, field) < 0) \
self->field.avl_left = TREE_ROTL_##node##_##field(self->field.avl_left); \
return TREE_ROTR_##node##_##field(self); \
} \
self->field.avl_height = 0; \
if (self->field.avl_left && (self->field.avl_left->field.avl_height > self->field.avl_height)) \
self->field.avl_height = self->field.avl_left->field.avl_height; \
if (self->field.avl_right && (self->field.avl_right->field.avl_height > self->field.avl_height)) \
self->field.avl_height = self->field.avl_right->field.avl_height; \
self->field.avl_height += 1; \
return self; \
} \
\
static struct node *_HU_FUNCTION(TREE_INSERT_##node##_##field)(struct node * self, struct node * elm, int (*compare)(struct node * lhs, struct node * rhs)) \
{ \
if (!self) \
return elm; \
if (compare(elm, self) < 0) \
self->field.avl_left = TREE_INSERT_##node##_##field(self->field.avl_left, elm, compare); \
else \
self->field.avl_right = TREE_INSERT_##node##_##field(self->field.avl_right, elm, compare); \
return TREE_BALANCE_##node##_##field(self); \
} \
\
static struct node *_HU_FUNCTION(TREE_FIND_##node##_##field)(struct node * self, struct node * elm, int (*compare)(struct node * lhs, struct node * rhs)) \
{ \
if (!self) \
return 0; \
if (compare(elm, self) == 0) \
return self; \
if (compare(elm, self) < 0) \
return TREE_FIND_##node##_##field(self->field.avl_left, elm, compare); \
else \
return TREE_FIND_##node##_##field(self->field.avl_right, elm, compare); \
} \
\
static struct node *_HU_FUNCTION(TREE_MOVE_RIGHT)(struct node * self, struct node * rhs) \
{ \
if (!self) \
return rhs; \
self->field.avl_right = TREE_MOVE_RIGHT(self->field.avl_right, rhs); \
return TREE_BALANCE_##node##_##field(self); \
} \
\
static struct node *_HU_FUNCTION(TREE_REMOVE_##node##_##field)(struct node * self, struct node * elm, int (*compare)(struct node * lhs, struct node * rhs)) \
{ \
if (!self) return 0; \
\
if (compare(elm, self) == 0) { \
struct node *tmp = TREE_MOVE_RIGHT(self->field.avl_left, self->field.avl_right); \
self->field.avl_left = 0; \
self->field.avl_right = 0; \
return tmp; \
} \
if (compare(elm, self) < 0) \
self->field.avl_left = TREE_REMOVE_##node##_##field(self->field.avl_left, elm, compare); \
else \
self->field.avl_right = TREE_REMOVE_##node##_##field(self->field.avl_right, elm, compare); \
return TREE_BALANCE_##node##_##field(self); \
} \
\
static void _HU_FUNCTION(TREE_FORWARD_APPLY_ALL_##node##_##field)(struct node * self, void (*function)(struct node * node, void *data), void *data) \
{ \
if (self) { \
TREE_FORWARD_APPLY_ALL_##node##_##field(self->field.avl_left, function, data); \
function(self, data); \
TREE_FORWARD_APPLY_ALL_##node##_##field(self->field.avl_right, function, data); \
} \
} \
\
static void _HU_FUNCTION(TREE_REVERSE_APPLY_ALL_##node##_##field)(struct node * self, void (*function)(struct node * node, void *data), void *data) \
{ \
if (self) { \
TREE_REVERSE_APPLY_ALL_##node##_##field(self->field.avl_right, function, data); \
function(self, data); \
TREE_REVERSE_APPLY_ALL_##node##_##field(self->field.avl_left, function, data); \
} \
}
#define TREE_INSERT(head, node, field, elm) \
((head)->th_root = TREE_INSERT_##node##_##field((head)->th_root, (elm), (head)->th_cmp))
#define TREE_FIND(head, node, field, elm) \
(TREE_FIND_##node##_##field((head)->th_root, (elm), (head)->th_cmp))
#define TREE_REMOVE(head, node, field, elm) \
((head)->th_root = TREE_REMOVE_##node##_##field((head)->th_root, (elm), (head)->th_cmp))
#define TREE_DEPTH(head, field) \
((head)->th_root->field.avl_height)
#define TREE_FORWARD_APPLY(head, node, field, function, data) \
TREE_FORWARD_APPLY_ALL_##node##_##field((head)->th_root, function, data)
#define TREE_REVERSE_APPLY(head, node, field, function, data) \
TREE_REVERSE_APPLY_ALL_##node##_##field((head)->th_root, function, data)
#define TREE_INIT(head, cmp) \
do { \
(head)->th_root = 0; \
(head)->th_cmp = (cmp); \
} while (0)
#endif /* __tree_h */