git.meshlink.io Git - meshlink/blob - lib/avl_tree.h

   1 /*
   2     avl_tree.h -- header file for avl_tree.c
   3     Copyright (C) 1998 Michael H. Buselli
   4                   2000,2001 Ivo Timmermans <itimmermans@bigfoot.com>,
   5                   2000,2001 Guus Sliepen <guus@sliepen.warande.net>
   6                   2000,2001 Wessel Dankers <wsl@nl.linux.org>
   7
   8     This program is free software; you can redistribute it and/or modify
   9     it under the terms of the GNU General Public License as published by
  10     the Free Software Foundation; either version 2 of the License, or
  11     (at your option) any later version.
  12
  13     This program is distributed in the hope that it will be useful,
  14     but WITHOUT ANY WARRANTY; without even the implied warranty of
  15     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16     GNU General Public License for more details.
  17
  18     You should have received a copy of the GNU General Public License
  19     along with this program; if not, write to the Free Software
  20     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  21
  22     Original AVL tree library by Michael H. Buselli <cosine@cosine.org>.
  23
  24     Modified 2000-11-28 by Wessel Dankers <wsl@nl.linux.org> to use counts
  25     instead of depths, to add the ->next and ->prev and to generally obfuscate
  26     the code. Mail me if you found a bug.
  27
  28     Cleaned up and incorporated some of the ideas from the red-black tree
  29     library for inclusion into tinc (http://tinc.nl.linux.org/) by
  30     Guus Sliepen <guus@sliepen.warande.net>.
  31
  32     $Id: avl_tree.h,v 1.1.2.4 2001/02/06 10:13:22 guus Exp $
  33 */
  34
  35
  36 #ifndef __AVL_TREE_H__
  37 #define __AVL_TREE_H__
  38
  39 #ifndef AVL_DEPTH
  40  #ifndef AVL_COUNT
  41   #define AVL_DEPTH
  42  #endif
  43 #endif
  44
  45 typedef struct avl_node_t {
  46
  47   /* Linked list part */
  48
  49   struct avl_node_t *next;
  50   struct avl_node_t *prev;
  51
  52   /* Tree part */
  53
  54   struct avl_node_t *parent;
  55   struct avl_node_t *left;
  56   struct avl_node_t *right;
  57
  58 #ifdef AVL_COUNT
  59   unsigned int count;
  60 #endif
  61 #ifdef AVL_DEPTH
  62   unsigned char depth;
  63 #endif
  64
  65   /* Payload */
  66
  67   void *data;
  68
  69 } avl_node_t;
  70
  71 typedef int (*avl_compare_t) (const void *, const void *);
  72 typedef void (*avl_action_t) (const void *);
  73 typedef void (*avl_action_node_t) (const avl_node_t *);
  74
  75 typedef struct avl_tree_t {
  76
  77   /* Linked list part */
  78
  79   avl_node_t *head;
  80   avl_node_t *tail;
  81
  82   /* Tree part */
  83
  84   avl_node_t *root;
  85
  86   avl_compare_t compare;
  87   avl_action_t delete;
  88
  89 } avl_tree_t;
  90
  91 /* (De)constructors */
  92
  93 extern avl_tree_t *avl_alloc_tree(avl_compare_t, avl_action_t);
  94 extern void avl_free_tree(avl_tree_t *);
  95
  96 extern avl_node_t *avl_alloc_node(void);
  97 extern void avl_free_node(avl_tree_t *tree, avl_node_t *);
  98
  99 /* Insertion and deletion */
 100
 101 extern avl_node_t *avl_insert(avl_tree_t *, void *);
 102 extern avl_node_t *avl_insert_node(avl_tree_t *, avl_node_t *);
 103
 104 extern void avl_insert_top(avl_tree_t *, avl_node_t *);
 105 extern void avl_insert_before(avl_tree_t *, avl_node_t *, avl_node_t *);
 106 extern void avl_insert_after(avl_tree_t *, avl_node_t *, avl_node_t *);
 107
 108 extern avl_node_t *avl_unlink(avl_tree_t *, void *);
 109 extern void avl_unlink_node(avl_tree_t *tree, avl_node_t *);
 110 extern void avl_delete(avl_tree_t *, void *);
 111 extern void avl_delete_node(avl_tree_t *, avl_node_t *);
 112
 113 /* Fast tree cleanup */
 114
 115 extern void avl_delete_tree(avl_tree_t *);
 116
 117 /* Searching */
 118
 119 extern void *avl_search(const avl_tree_t *, const void *);
 120 extern void *avl_search_closest(const avl_tree_t *, const void *, int *);
 121 extern void *avl_search_closest_smaller(const avl_tree_t *, const void *);
 122 extern void *avl_search_closest_greater(const avl_tree_t *, const void *);
 123
 124 extern avl_node_t *avl_search_node(const avl_tree_t *, const void *);
 125 extern avl_node_t *avl_search_closest_node(const avl_tree_t *, const void *, int *);
 126 extern avl_node_t *avl_search_closest_smaller_node(const avl_tree_t *, const void *);
 127 extern avl_node_t *avl_search_closest_greater_node(const avl_tree_t *, const void *);
 128
 129 /* Tree walking */
 130
 131 extern void avl_foreach(avl_tree_t *, avl_action_t);
 132 extern void avl_foreach_node(avl_tree_t *, avl_action_t);
 133
 134 /* Indexing */
 135
 136 #ifdef AVL_COUNT
 137 extern unsigned int avl_count(avl_tree_t *);
 138 extern avl_node_t *avl_get_node(const avl_tree_t *, unsigned int);
 139 extern unsigned int avl_index(const avl_node_t *);
 140 #endif
 141 #ifdef AVL_DEPTH
 142 extern unsigned int avl_depth(avl_tree_t *);
 143 #endif
 144
 145 #endif /* __AVL_TREE_H__ */