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