tinc-vpn.org Git - tinc/blob - src/avl.h

   1 /*
   2     avl.h -- AVL tree management
   3
   4     Copyright (C) 1998 Michael H. Buselli
   5                   2000-2004 Ivo Timmermans <ivo@tinc-vpn.org>,
   6                   2000-2004 Guus Sliepen <guus@tinc-vpn.org>
   7                   2000-2004 Wessel Dankers <wsl@tinc-vpn.org>
   8
   9     This program is free software; you can redistribute it and/or modify
  10     it under the terms of the GNU General Public License as published by
  11     the Free Software Foundation; either version 2 of the License, or
  12     (at your option) any later version.
  13
  14     This program is distributed in the hope that it will be useful,
  15     but WITHOUT ANY WARRANTY; without even the implied warranty of
  16     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17     GNU General Public License for more details.
  18
  19     You should have received a copy of the GNU General Public License
  20     along with this program; if not, write to the Free Software
  21     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  22
  23     Original AVL tree library by Michael H. Buselli <cosine@cosine.org>.
  24
  25     Modified 2000-11-28 by Wessel Dankers <wsl@tinc-vpn.org> to use counts
  26     instead of depths, to add the ->next and ->prev and to generally obfuscate
  27     the code. Mail me if you found a bug.
  28
  29     Cleaned up and incorporated some of the ideas from the red-black tree
  30     library for inclusion into tinc (http://www.tinc-vpn.org/) by
  31     Guus Sliepen <guus@tinc-vpn.org>.
  32
  33     $Id$
  34 */
  35
  36
  37 #ifndef __AVL_H__
  38 #define __AVL_H__
  39
  40 #ifndef AVL_DEPTH
  41 #ifndef AVL_COUNT
  42 #define AVL_DEPTH
  43 #endif
  44 #endif
  45
  46 typedef uint32_t avl_count_t;
  47 typedef uint16_t avl_depth_t;
  48
  49 typedef struct avl_node {
  50         struct avl_node *next;
  51         struct avl_node *prev;
  52
  53         struct avl_node *parent;
  54         struct avl_node *left;
  55         struct avl_node *right;
  56
  57 #ifdef AVL_COUNT
  58         avl_count_t count;
  59 #endif
  60
  61 #ifdef AVL_DEPTH
  62         avl_depth_t depth;
  63 #endif
  64
  65         void *data;
  66 } avl_node_t;
  67
  68 typedef int (*avl_compare_t)(const void *, const void *);
  69 typedef void (*avl_action_t)(void *);
  70 typedef void (*avl_node_action_t)(struct avl_node *);
  71
  72 typedef struct avl_tree {
  73         struct avl_node *head;
  74         struct avl_node *tail;
  75
  76         struct avl_node *root;
  77
  78         avl_compare_t compare;
  79         avl_action_t free;
  80 } avl_tree_t;
  81
  82 /* (De)constructors */
  83
  84 extern struct avl_tree *avl_tree_new(avl_compare_t, avl_action_t);
  85 extern void avl_tree_free(struct avl_tree *);
  86
  87 extern struct avl_node *avl_node_new(void);
  88 extern void avl_node_free(struct avl_tree *tree, struct avl_node *);
  89
  90 /* Insertion and deletion */
  91
  92 extern struct avl_node *avl_add(struct avl_tree *, void *);
  93 extern struct avl_node *avl_add_node(struct avl_tree *, struct avl_node *);
  94
  95 extern void avl_add_top(struct avl_tree *, struct avl_node *);
  96 extern void avl_add_before(struct avl_tree *, struct avl_node *, struct avl_node *);
  97 extern void avl_add_after(struct avl_tree *, struct avl_node *, struct avl_node *);
  98
  99 extern struct avl_node *avl_unlink(struct avl_tree *, const void *);
 100 extern void avl_unlink_node(struct avl_tree *tree, struct avl_node *);
 101 extern bool avl_del(struct avl_tree *, void *);
 102 extern void avl_del_node(struct avl_tree *, struct avl_node *);
 103
 104 /* Fast tree cleanup */
 105
 106 extern void avl_tree_del(struct avl_tree *);
 107
 108 /* Searching */
 109
 110 extern void *avl_get(const struct avl_tree *, const void *);
 111 extern void *avl_get_closest(const struct avl_tree *, const void *, int *);
 112 extern void *avl_get_closest_smaller(const struct avl_tree *, const void *);
 113 extern void *avl_get_closest_greater(const struct avl_tree *, const void *);
 114
 115 extern struct avl_node *avl_get_node(const struct avl_tree *, const void *);
 116 extern struct avl_node *avl_get_closest_node(const struct avl_tree *, const void *, int *);
 117 extern struct avl_node *avl_get_closest_smaller_node(const struct avl_tree *, const void *);
 118 extern struct avl_node *avl_get_closest_greater_node(const struct avl_tree *, const void *);
 119
 120 /* Tree walking */
 121
 122 #define avl_foreach(tree, object, action) {avl_node_t *_node, *_next; \
 123         for(_node = (tree)->head; _node; _node = _next) { \
 124                 _next = _node->next; \
 125                 (object) = _node->data; \
 126                 action; \
 127         } \
 128 }
 129
 130 #define avl_foreach_node(tree, node, action) {avl_node_t *_next; \
 131         for((node) = (tree)->head; (node); (node) = _next) { \
 132                 _next = (node)->next; \
 133                 action; \
 134         } \
 135 }
 136
 137 /* Indexing */
 138
 139 #ifdef AVL_COUNT
 140 extern avl_count_t avl_count(const struct avl_tree *);
 141 extern avl_count_t avl_index(const struct avl_node *);
 142 extern void *avl_get_indexed(const struct avl_tree *, avl_count_t);
 143 extern struct avl_node *avl_get_indexed_node(const struct avl_tree *, avl_count_t);
 144 #endif
 145 #ifdef AVL_DEPTH
 146 extern avl_depth_t avl_depth(const struct avl_tree *);
 147 #endif
 148
 149 #endif