contrib/libucl/src/tree.h

   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 */