GRASS Programmer's Manual  6.4.2(2012)
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
tavl.h
Go to the documentation of this file.
1 /* Produced by texiweb from libavl.w on 2002/02/09 at 01:45. */
2 
3 /* libavl - library for manipulation of binary trees.
4  Copyright (C) 1998-2002 Free Software Foundation, Inc.
5 
6  This program is free software; you can redistribute it and/or
7  modify it under the terms of the GNU General Public License as
8  published by the Free Software Foundation; either version 2 of the
9  License, or (at your option) any later version.
10 
11  This program is distributed in the hope that it will be useful, but
12  WITHOUT ANY WARRANTY; without even the implied warranty of
13  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
14  See the GNU General Public License for more details.
15 
16  You should have received a copy of the GNU General Public License
17  along with this program; if not, write to the Free Software
18  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
19 
20  The author may be contacted at <blp@gnu.org> on the Internet, or
21  as Ben Pfaff, 12167 Airport Rd, DeWitt MI 48820, USA through more
22  mundane means.
23  */
24 
25 #ifndef TAVL_H
26 #define TAVL_H 1
27 
28 #include <stddef.h>
29 
30 /* Function types. */
31 typedef int tavl_comparison_func(const void *tavl_a, const void *tavl_b,
32  void *tavl_param);
33 typedef void tavl_item_func(void *tavl_item, void *tavl_param);
34 typedef void *tavl_copy_func(void *tavl_item, void *tavl_param);
35 
36 #ifndef LIBAVL_ALLOCATOR
37 #define LIBAVL_ALLOCATOR
38 /* Memory allocator. */
39 struct libavl_allocator
40 {
41  void *(*libavl_malloc) (struct libavl_allocator *, size_t libavl_size);
42  void (*libavl_free) (struct libavl_allocator *, void *libavl_block);
43 };
44 #endif
45 
46 /* Default memory allocator. */
48 void *tavl_malloc(struct libavl_allocator *, size_t);
49 void tavl_free(struct libavl_allocator *, void *);
50 
51 /* Maximum TAVL height. */
52 #ifndef TAVL_MAX_HEIGHT
53 #define TAVL_MAX_HEIGHT 32
54 #endif
55 
56 /* Tree data structure. */
57 struct tavl_table
58 {
59  struct tavl_node *tavl_root; /* Tree's root. */
60  tavl_comparison_func *tavl_compare; /* Comparison function. */
61  void *tavl_param; /* Extra argument to |tavl_compare|. */
62  struct libavl_allocator *tavl_alloc; /* Memory allocator. */
63  size_t tavl_count; /* Number of items in tree. */
64 };
65 
66 /* Characterizes a link as a child pointer or a thread. */
68 {
69  TAVL_CHILD, /* Child pointer. */
70  TAVL_THREAD /* Thread. */
71 };
72 
73 /* An TAVL tree node. */
74 struct tavl_node
75 {
76  struct tavl_node *tavl_link[2]; /* Subtrees. */
77  void *tavl_data; /* Pointer to data. */
78  unsigned char tavl_tag[2]; /* Tag fields. */
79  signed char tavl_balance; /* Balance factor. */
80 };
81 
82 /* TAVL traverser structure. */
84 {
85  struct tavl_table *tavl_table; /* Tree being traversed. */
86  struct tavl_node *tavl_node; /* Current node in tree. */
87 };
88 
89 /* Table functions. */
91  struct libavl_allocator *);
92 struct tavl_table *tavl_copy(const struct tavl_table *, tavl_copy_func *,
93  tavl_item_func *, struct libavl_allocator *);
94 void tavl_destroy(struct tavl_table *, tavl_item_func *);
95 void **tavl_probe(struct tavl_table *, void *);
96 void *tavl_insert(struct tavl_table *, void *);
97 void *tavl_replace(struct tavl_table *, void *);
98 void *tavl_delete(struct tavl_table *, const void *);
99 void *tavl_find(const struct tavl_table *, const void *);
100 void tavl_assert_insert(struct tavl_table *, void *);
101 void *tavl_assert_delete(struct tavl_table *, void *);
102 
103 #define tavl_count(table) ((size_t) (table)->tavl_count)
104 
105 /* Table traverser functions. */
106 void tavl_t_init(struct tavl_traverser *, struct tavl_table *);
107 void *tavl_t_first(struct tavl_traverser *, struct tavl_table *);
108 void *tavl_t_last(struct tavl_traverser *, struct tavl_table *);
109 void *tavl_t_find(struct tavl_traverser *, struct tavl_table *, void *);
110 void *tavl_t_insert(struct tavl_traverser *, struct tavl_table *, void *);
111 void *tavl_t_copy(struct tavl_traverser *, const struct tavl_traverser *);
112 void *tavl_t_next(struct tavl_traverser *);
113 void *tavl_t_prev(struct tavl_traverser *);
114 void *tavl_t_cur(struct tavl_traverser *);
115 void *tavl_t_replace(struct tavl_traverser *, void *);
116 
117 #endif /* tavl.h */