GRASS GIS 7 Programmer's Manual  7.5.svn(2018)-r72255
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
tavl.h
Go to the documentation of this file.
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. */
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. */
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. */
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. */
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 */
struct tavl_node * tavl_node
Definition: tavl.h:84
size_t tavl_count
Definition: tavl.h:61
void * tavl_replace(struct tavl_table *table, void *item)
Definition: tavl.c:254
void tavl_item_func(void *tavl_item, void *tavl_param)
Definition: tavl.h:31
void * tavl_t_next(struct tavl_traverser *trav)
Definition: tavl.c:670
Definition: tavl.h:72
void * tavl_t_prev(struct tavl_traverser *trav)
Definition: tavl.c:691
void * tavl_t_last(struct tavl_traverser *trav, struct tavl_table *tree)
Definition: tavl.c:573
void * tavl_t_copy(struct tavl_traverser *trav, const struct tavl_traverser *src)
Definition: tavl.c:656
void * tavl_copy_func(void *tavl_item, void *tavl_param)
Definition: tavl.h:32
void ** tavl_probe(struct tavl_table *tree, void *item)
Definition: tavl.c:90
struct tavl_table * tavl_copy(const struct tavl_table *org, tavl_copy_func *copy, tavl_item_func *destroy, struct libavl_allocator *allocator)
Definition: tavl.c:791
void(* libavl_free)(struct libavl_allocator *, void *libavl_block)
Definition: avl.h:40
void * tavl_data
Definition: tavl.h:75
void * tavl_delete(struct tavl_table *tree, const void *item)
Definition: tavl.c:305
void * tavl_t_cur(struct tavl_traverser *trav)
Definition: tavl.c:710
void * tavl_malloc(struct libavl_allocator *allocator, size_t size)
Definition: tavl.c:886
struct tavl_table * tavl_create(tavl_comparison_func *compare, void *param, struct libavl_allocator *allocator)
Definition: tavl.c:37
struct tavl_node * tavl_link[2]
Definition: tavl.h:74
void * tavl_t_first(struct tavl_traverser *trav, struct tavl_table *tree)
Definition: tavl.c:555
void * tavl_param
Definition: tavl.h:59
void tavl_t_init(struct tavl_traverser *trav, struct tavl_table *tree)
Definition: tavl.c:546
void * tavl_insert(struct tavl_table *table, void *item)
Definition: tavl.c:243
int tavl_comparison_func(const void *tavl_a, const void *tavl_b, void *tavl_param)
Definition: tavl.h:29
void tavl_free(struct libavl_allocator *allocator, void *block)
Definition: tavl.c:893
void * tavl_find(const struct tavl_table *tree, const void *item)
Definition: tavl.c:62
struct tavl_node * tavl_root
Definition: tavl.h:57
void * tavl_t_find(struct tavl_traverser *trav, struct tavl_table *tree, void *item)
Definition: tavl.c:593
struct libavl_allocator tavl_allocator_default
Definition: tavl.c:900
void * tavl_t_replace(struct tavl_traverser *trav, void *new)
Definition: tavl.c:720
void * tavl_t_insert(struct tavl_traverser *trav, struct tavl_table *tree, void *item)
Definition: tavl.c:633
tavl_comparison_func * tavl_compare
Definition: tavl.h:58
void() tavl_assert_insert(struct tavl_table *table, void *item)
Definition: tavl.c:909
void *() tavl_assert_delete(struct tavl_table *table, void *item)
Definition: tavl.c:918
struct tavl_table * tavl_table
Definition: tavl.h:83
void tavl_destroy(struct tavl_table *tree, tavl_item_func *destroy)
Definition: tavl.c:857
struct libavl_allocator * tavl_alloc
Definition: tavl.h:60
tavl_tag
Definition: tavl.h:65
signed char tavl_balance
Definition: tavl.h:77