1 /* Produced by texiweb from libavl.w. */ 2 3 /* libavl - library for manipulation of binary trees. 4 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004 Free Software 5 Foundation, Inc. 6 7 This library is free software; you can redistribute it and/or 8 modify it under the terms of the GNU Lesser General Public 9 License as published by the Free Software Foundation; either 10 version 3 of the License, or (at your option) any later version. 11 12 This library is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15 Lesser General Public License for more details. 16 17 You should have received a copy of the GNU Lesser General Public 18 License along with this library; if not, write to the Free Software 19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 20 02110-1301 USA. 21 */ 22 23 #ifndef AVL_H 24 #define AVL_H 1 25 26 #include <stddef.h> 27 28 /* Function types. */ 29 typedef int avl_comparison_func(const void *avl_a, const void *avl_b, 30 void *avl_param); 31 typedef void avl_item_func(void *avl_item, void *avl_param); 32 typedef void *avl_copy_func(void *avl_item, void *avl_param); 33 34 #ifndef LIBAVL_ALLOCATOR 35 #define LIBAVL_ALLOCATOR 36 /* Memory allocator. */ 37 struct libavl_allocator 38 { 39 void *(*libavl_malloc) (struct libavl_allocator *, size_t libavl_size); 40 void (*libavl_free) (struct libavl_allocator *, void *libavl_block); 41 }; 42 #endif 43 44 /* Default memory allocator. */ 45 extern struct libavl_allocator avl_allocator_default; 46 void *avl_malloc(struct libavl_allocator *, size_t); 47 void avl_free(struct libavl_allocator *, void *); 48 49 /* Maximum AVL tree height. */ 50 #ifndef AVL_MAX_HEIGHT 51 #define AVL_MAX_HEIGHT 92 52 #endif 53 54 /* Tree data structure. */ 55 struct avl_table 56 { 57 struct avl_node *avl_root; /* Tree's root. */ 58 avl_comparison_func *avl_compare; /* Comparison function. */ 59 void *avl_param; /* Extra argument to |avl_compare|. */ 60 struct libavl_allocator *avl_alloc; /* Memory allocator. */ 61 size_t avl_count; /* Number of items in tree. */ 62 unsigned long avl_generation; /* Generation number. */ 63 }; 64 65 /* An AVL tree node. */ 66 struct avl_node 67 { 68 struct avl_node *avl_link[2]; /* Subtrees. */ 69 void *avl_data; /* Pointer to data. */ 70 signed char avl_balance; /* Balance factor. */ 71 }; 72 73 /* AVL traverser structure. */ 74 struct avl_traverser 75 { 76 struct avl_table *avl_table; /* Tree being traversed. */ 77 struct avl_node *avl_node; /* Current node in tree. */ 78 struct avl_node *avl_stack[AVL_MAX_HEIGHT]; 79 /* All the nodes above |avl_node|. */ 80 size_t avl_height; /* Number of nodes in |avl_parent|. */ 81 unsigned long avl_generation; /* Generation number. */ 82 }; 83 84 /* Table functions. */ 85 struct avl_table *avl_create(avl_comparison_func *, void *, 86 struct libavl_allocator *); 87 struct avl_table *avl_copy(const struct avl_table *, avl_copy_func *, 88 avl_item_func *, struct libavl_allocator *); 89 void avl_destroy(struct avl_table *, avl_item_func *); 90 void **avl_probe(struct avl_table *, void *); 91 void *avl_insert(struct avl_table *, void *); 92 void *avl_replace(struct avl_table *, void *); 93 void *avl_delete(struct avl_table *, const void *); 94 void *avl_find(const struct avl_table *, const void *); 95 void avl_assert_insert(struct avl_table *, void *); 96 void *avl_assert_delete(struct avl_table *, void *); 97 98 #define avl_count(table) ((size_t) (table)->avl_count) 99 100 /* Table traverser functions. */ 101 void avl_t_init(struct avl_traverser *, struct avl_table *); 102 void *avl_t_first(struct avl_traverser *, struct avl_table *); 103 void *avl_t_last(struct avl_traverser *, struct avl_table *); 104 void *avl_t_find(struct avl_traverser *, struct avl_table *, void *); 105 void *avl_t_insert(struct avl_traverser *, struct avl_table *, void *); 106 void *avl_t_copy(struct avl_traverser *, const struct avl_traverser *); 107 void *avl_t_next(struct avl_traverser *); 108 void *avl_t_prev(struct avl_traverser *); 109 void *avl_t_cur(struct avl_traverser *); 110 void *avl_t_replace(struct avl_traverser *, void *); 111 112 #endif /* avl.h */ 113