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 TAVL_H 24 #define TAVL_H 1 25 26 #include <stddef.h> 27 28 /* Function types. */ 29 typedef int tavl_comparison_func(const void *tavl_a, const void *tavl_b, 30 void *tavl_param); 31 typedef void tavl_item_func(void *tavl_item, void *tavl_param); 32 typedef void *tavl_copy_func(void *tavl_item, void *tavl_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 tavl_allocator_default; 46 void *tavl_malloc(struct libavl_allocator *, size_t); 47 void tavl_free(struct libavl_allocator *, void *); 48 49 /* Maximum TAVL height. */ 50 #ifndef TAVL_MAX_HEIGHT 51 #define TAVL_MAX_HEIGHT 92 52 #endif 53 54 /* Tree data structure. */ 55 struct tavl_table 56 { 57 struct tavl_node *tavl_root; /* Tree's root. */ 58 tavl_comparison_func *tavl_compare; /* Comparison function. */ 59 void *tavl_param; /* Extra argument to |tavl_compare|. */ 60 struct libavl_allocator *tavl_alloc; /* Memory allocator. */ 61 size_t tavl_count; /* Number of items in tree. */ 62 }; 63 64 /* Characterizes a link as a child pointer or a thread. */ 65 enum tavl_tag 66 { 67 TAVL_CHILD, /* Child pointer. */ 68 TAVL_THREAD /* Thread. */ 69 }; 70 71 /* An TAVL tree node. */ 72 struct tavl_node 73 { 74 struct tavl_node *tavl_link[2]; /* Subtrees. */ 75 void *tavl_data; /* Pointer to data. */ 76 unsigned char tavl_tag[2]; /* Tag fields. */ 77 signed char tavl_balance; /* Balance factor. */ 78 }; 79 80 /* TAVL traverser structure. */ 81 struct tavl_traverser 82 { 83 struct tavl_table *tavl_table; /* Tree being traversed. */ 84 struct tavl_node *tavl_node; /* Current node in tree. */ 85 }; 86 87 /* Table functions. */ 88 struct tavl_table *tavl_create(tavl_comparison_func *, void *, 89 struct libavl_allocator *); 90 struct tavl_table *tavl_copy(const struct tavl_table *, tavl_copy_func *, 91 tavl_item_func *, struct libavl_allocator *); 92 void tavl_destroy(struct tavl_table *, tavl_item_func *); 93 void **tavl_probe(struct tavl_table *, void *); 94 void *tavl_insert(struct tavl_table *, void *); 95 void *tavl_replace(struct tavl_table *, void *); 96 void *tavl_delete(struct tavl_table *, const void *); 97 void *tavl_find(const struct tavl_table *, const void *); 98 void tavl_assert_insert(struct tavl_table *, void *); 99 void *tavl_assert_delete(struct tavl_table *, void *); 100 101 #define tavl_count(table) ((size_t) (table)->tavl_count) 102 103 /* Table traverser functions. */ 104 void tavl_t_init(struct tavl_traverser *, struct tavl_table *); 105 void *tavl_t_first(struct tavl_traverser *, struct tavl_table *); 106 void *tavl_t_last(struct tavl_traverser *, struct tavl_table *); 107 void *tavl_t_find(struct tavl_traverser *, struct tavl_table *, void *); 108 void *tavl_t_insert(struct tavl_traverser *, struct tavl_table *, void *); 109 void *tavl_t_copy(struct tavl_traverser *, const struct tavl_traverser *); 110 void *tavl_t_next(struct tavl_traverser *); 111 void *tavl_t_prev(struct tavl_traverser *); 112 void *tavl_t_cur(struct tavl_traverser *); 113 void *tavl_t_replace(struct tavl_traverser *, void *); 114 115 #endif /* tavl.h */ 116