GRASS Programmer's Manual
6.4.2(2012)
Main Page
Related Pages
Namespaces
Data Structures
Files
File List
Globals
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. */
47
extern
struct
libavl_allocator
tavl_allocator_default
;
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. */
67
enum
tavl_tag
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. */
83
struct
tavl_traverser
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. */
90
struct
tavl_table
*
tavl_create
(
tavl_comparison_func
*,
void
*,
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 */
lib
vector
dglib
tavl.h
Generated on Sun Sep 9 2012 18:55:35 for GRASS Programmer's Manual by
1.8.1.2