release/src/router/shared/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  /* http://piumarta.com/software/tree/
  43   * tree.h is an implementation of AVL (Adelson-Velskii and Landis) balanced trees in the spirit of the BSD queue and list implementations.
  44   * tree is distributed under the MIT license. It will not infect your project with a contagious disease if you decide to use it.
  45   */
  46
  47 #ifndef __tree_h
  48 #define __tree_h
  49
  50
  51 #define TREE_DELTA_MAX  1
  52
  53 #define TREE_ENTRY(type)                        \
  54   struct {                                      \
  55     struct type *avl_left;                      \
  56     struct type *avl_right;                     \
  57     int          avl_height;                    \
  58   }
  59
  60 #define TREE_HEAD(name, type)                           \
  61   struct name {                                         \
  62     struct type *th_root;                               \
  63     int  (*th_cmp)(struct type *lhs, struct type *rhs); \
  64   }
  65
  66 #define TREE_INITIALIZER(cmp) { 0, cmp }
  67
  68 #define TREE_DELTA(self, field)                                                         \
  69   (( (((self)->field.avl_left)  ? (self)->field.avl_left->field.avl_height  : 0))       \
  70    - (((self)->field.avl_right) ? (self)->field.avl_right->field.avl_height : 0))
  71
  72 /* Recursion prevents the following from being defined as macros. */
  73
  74 #define TREE_DEFINE(node, field)                                                                        \
  75                                                                                                         \
  76   struct node *TREE_BALANCE_##node##_##field(struct node *);                                            \
  77                                                                                                         \
  78   struct node *TREE_ROTL_##node##_##field(struct node *self)                                            \
  79   {                                                                                                     \
  80     struct node *r= self->field.avl_right;                                                              \
  81     self->field.avl_right= r->field.avl_left;                                                           \
  82     r->field.avl_left= TREE_BALANCE_##node##_##field(self);                                             \
  83     return TREE_BALANCE_##node##_##field(r);                                                            \
  84   }                                                                                                     \
  85                                                                                                         \
  86   struct node *TREE_ROTR_##node##_##field(struct node *self)                                            \
  87   {                                                                                                     \
  88     struct node *l= self->field.avl_left;                                                               \
  89     self->field.avl_left= l->field.avl_right;                                                           \
  90     l->field.avl_right= TREE_BALANCE_##node##_##field(self);                                            \
  91     return TREE_BALANCE_##node##_##field(l);                                                            \
  92   }                                                                                                     \
  93                                                                                                         \
  94   struct node *TREE_BALANCE_##node##_##field(struct node *self)                                         \
  95   {                                                                                                     \
  96     int delta= TREE_DELTA(self, field);                                                                 \
  97                                                                                                         \
  98     if (delta < -TREE_DELTA_MAX)                                                                        \
  99       {                                                                                                 \
 100         if (TREE_DELTA(self->field.avl_right, field) > 0)                                               \
 101           self->field.avl_right= TREE_ROTR_##node##_##field(self->field.avl_right);                     \
 102         return TREE_ROTL_##node##_##field(self);                                                        \
 103       }                                                                                                 \
 104     else if (delta > TREE_DELTA_MAX)                                                                    \
 105       {                                                                                                 \
 106         if (TREE_DELTA(self->field.avl_left, field) < 0)                                                \
 107           self->field.avl_left= TREE_ROTL_##node##_##field(self->field.avl_left);                       \
 108         return TREE_ROTR_##node##_##field(self);                                                        \
 109       }                                                                                                 \
 110     self->field.avl_height= 0;                                                                          \
 111     if (self->field.avl_left && (self->field.avl_left->field.avl_height > self->field.avl_height))      \
 112       self->field.avl_height= self->field.avl_left->field.avl_height;                                   \
 113     if (self->field.avl_right && (self->field.avl_right->field.avl_height > self->field.avl_height))    \
 114       self->field.avl_height= self->field.avl_right->field.avl_height;                                  \
 115     self->field.avl_height += 1;                                                                        \
 116     return self;                                                                                        \
 117   }                                                                                                     \
 118                                                                                                         \
 119   struct node *TREE_INSERT_##node##_##field                                                             \
 120     (struct node *self, struct node *elm, int (*compare)(struct node *lhs, struct node *rhs))           \
 121   {                                                                                                     \
 122     if (!self)                                                                                          \
 123       return elm;                                                                                       \
 124     if (compare(elm, self) < 0)                                                                         \
 125       self->field.avl_left= TREE_INSERT_##node##_##field(self->field.avl_left, elm, compare);           \
 126     else                                                                                                \
 127       self->field.avl_right= TREE_INSERT_##node##_##field(self->field.avl_right, elm, compare);         \
 128     return TREE_BALANCE_##node##_##field(self);                                                         \
 129   }                                                                                                     \
 130                                                                                                         \
 131   struct node *TREE_FIND_##node##_##field                                                               \
 132     (struct node *self, struct node *elm, int (*compare)(struct node *lhs, struct node *rhs))           \
 133   {                                                                                                     \
 134     if (!self)                                                                                          \
 135       return 0;                                                                                         \
 136     if (compare(elm, self) == 0)                                                                        \
 137       return self;                                                                                      \
 138     if (compare(elm, self) < 0)                                                                         \
 139       return TREE_FIND_##node##_##field(self->field.avl_left, elm, compare);                            \
 140     else                                                                                                \
 141       return TREE_FIND_##node##_##field(self->field.avl_right, elm, compare);                           \
 142   }                                                                                                     \
 143                                                                                                         \
 144   struct node *TREE_MOVE_RIGHT(struct node *self, struct node *rhs)                                     \
 145   {                                                                                                     \
 146     if (!self)                                                                                          \
 147       return rhs;                                                                                       \
 148     self->field.avl_right= TREE_MOVE_RIGHT(self->field.avl_right, rhs);                                 \
 149     return TREE_BALANCE_##node##_##field(self);                                                         \
 150   }                                                                                                     \
 151                                                                                                         \
 152   struct node *TREE_REMOVE_##node##_##field                                                             \
 153     (struct node *self, struct node *elm, int (*compare)(struct node *lhs, struct node *rhs))           \
 154   {                                                                                                     \
 155     if (!self) return 0;                                                                                \
 156                                                                                                         \
 157     if (compare(elm, self) == 0)                                                                        \
 158       {                                                                                                 \
 159         struct node *tmp= TREE_MOVE_RIGHT(self->field.avl_left, self->field.avl_right);                 \
 160         self->field.avl_left= 0;                                                                        \
 161         self->field.avl_right= 0;                                                                       \
 162         return tmp;                                                                                     \
 163       }                                                                                                 \
 164     if (compare(elm, self) < 0)                                                                         \
 165       self->field.avl_left= TREE_REMOVE_##node##_##field(self->field.avl_left, elm, compare);           \
 166     else                                                                                                \
 167       self->field.avl_right= TREE_REMOVE_##node##_##field(self->field.avl_right, elm, compare);         \
 168     return TREE_BALANCE_##node##_##field(self);                                                         \
 169   }                                                                                                     \
 170                                                                                                         \
 171   void TREE_FORWARD_APPLY_ALL_##node##_##field                                                          \
 172     (struct node *self, void (*function)(struct node *node, void *data), void *data)                    \
 173   {                                                                                                     \
 174     if (self)                                                                                           \
 175       {                                                                                                 \
 176         TREE_FORWARD_APPLY_ALL_##node##_##field(self->field.avl_left, function, data);                  \
 177         struct node *right = self->field.avl_right; /* Preserve before removing */                      \
 178         function(self, data);                                                                           \
 179         TREE_FORWARD_APPLY_ALL_##node##_##field(right, function, data);                                 \
 180       }                                                                                                 \
 181   }                                                                                                     \
 182                                                                                                         \
 183   void TREE_REVERSE_APPLY_ALL_##node##_##field                                                          \
 184     (struct node *self, void (*function)(struct node *node, void *data), void *data)                    \
 185   {                                                                                                     \
 186     if (self)                                                                                           \
 187       {                                                                                                 \
 188         TREE_REVERSE_APPLY_ALL_##node##_##field(self->field.avl_right, function, data);                 \
 189         function(self, data);                                                                           \
 190         TREE_REVERSE_APPLY_ALL_##node##_##field(self->field.avl_left, function, data);                  \
 191       }                                                                                                 \
 192   }
 193
 194 #define TREE_INSERT(head, node, field, elm)                                             \
 195   ((head)->th_root= TREE_INSERT_##node##_##field((head)->th_root, (elm), (head)->th_cmp))
 196
 197 #define TREE_FIND(head, node, field, elm)                               \
 198   (TREE_FIND_##node##_##field((head)->th_root, (elm), (head)->th_cmp))
 199
 200 #define TREE_REMOVE(head, node, field, elm)                                             \
 201   ((head)->th_root= TREE_REMOVE_##node##_##field((head)->th_root, (elm), (head)->th_cmp))
 202
 203 #define TREE_DEPTH(head, field)                 \
 204   ((head)->th_root->field.avl_height)
 205
 206 #define TREE_FORWARD_APPLY(head, node, field, function, data)   \
 207   TREE_FORWARD_APPLY_ALL_##node##_##field((head)->th_root, function, data)
 208
 209 #define TREE_REVERSE_APPLY(head, node, field, function, data)   \
 210   TREE_REVERSE_APPLY_ALL_##node##_##field((head)->th_root, function, data)
 211
 212 #define TREE_INIT(head, cmp) do {               \
 213     (head)->th_root= 0;                         \
 214     (head)->th_cmp= (cmp);                      \
 215   } while (0)
 216
 217
 218 #endif /* __tree_h */