GRASS Programmer's Manual
6.4.3(2013)-r
Main Page
Related Pages
Namespaces
Data Structures
Files
File List
Globals
All
Data Structures
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Properties
Macros
Pages
avl.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 AVL_H
26
#define AVL_H 1
27
28
#include <stddef.h>
29
30
/* Function types. */
31
typedef
int
avl_comparison_func
(
const
void
*avl_a,
const
void
*avl_b,
32
void
*
avl_param
);
33
typedef
void
avl_item_func
(
void
*avl_item,
void
*
avl_param
);
34
typedef
void
*
avl_copy_func
(
void
*avl_item,
void
*
avl_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
avl_allocator_default
;
48
void
*
avl_malloc
(
struct
libavl_allocator
*,
size_t
);
49
void
avl_free
(
struct
libavl_allocator
*,
void
*);
50
51
/* Maximum AVL height. */
52
#ifndef AVL_MAX_HEIGHT
53
#define AVL_MAX_HEIGHT 32
54
#endif
55
56
/* Tree data structure. */
57
struct
avl_table
58
{
59
struct
avl_node
*
avl_root
;
/* Tree's root. */
60
avl_comparison_func
*
avl_compare
;
/* Comparison function. */
61
void
*
avl_param
;
/* Extra argument to |avl_compare|. */
62
struct
libavl_allocator
*
avl_alloc
;
/* Memory allocator. */
63
size_t
avl_count
;
/* Number of items in tree. */
64
unsigned
long
avl_generation
;
/* Generation number. */
65
};
66
67
/* An AVL tree node. */
68
struct
avl_node
69
{
70
struct
avl_node
*
avl_link
[2];
/* Subtrees. */
71
void
*
avl_data
;
/* Pointer to data. */
72
signed
char
avl_balance
;
/* Balance factor. */
73
};
74
75
/* AVL traverser structure. */
76
struct
avl_traverser
77
{
78
struct
avl_table
*
avl_table
;
/* Tree being traversed. */
79
struct
avl_node
*
avl_node
;
/* Current node in tree. */
80
struct
avl_node
*
avl_stack
[
AVL_MAX_HEIGHT
];
81
/* All the nodes above |avl_node|. */
82
size_t
avl_height
;
/* Number of nodes in |avl_parent|. */
83
unsigned
long
avl_generation
;
/* Generation number. */
84
};
85
86
/* Table functions. */
87
struct
avl_table
*
avl_create
(
avl_comparison_func
*,
void
*,
88
struct
libavl_allocator
*);
89
struct
avl_table
*
avl_copy
(
const
struct
avl_table
*,
avl_copy_func
*,
90
avl_item_func
*,
struct
libavl_allocator
*);
91
void
avl_destroy
(
struct
avl_table
*,
avl_item_func
*);
92
void
**
avl_probe
(
struct
avl_table
*,
void
*);
93
void
*
avl_insert
(
struct
avl_table
*,
void
*);
94
void
*
avl_replace
(
struct
avl_table
*,
void
*);
95
void
*
avl_delete
(
struct
avl_table
*,
const
void
*);
96
void
*
avl_find
(
const
struct
avl_table
*,
const
void
*);
97
void
avl_assert_insert
(
struct
avl_table
*,
void
*);
98
void
*
avl_assert_delete
(
struct
avl_table
*,
void
*);
99
100
#define avl_count(table) ((size_t) (table)->avl_count)
101
102
/* Table traverser functions. */
103
void
avl_t_init
(
struct
avl_traverser
*,
struct
avl_table
*);
104
void
*
avl_t_first
(
struct
avl_traverser
*,
struct
avl_table
*);
105
void
*
avl_t_last
(
struct
avl_traverser
*,
struct
avl_table
*);
106
void
*
avl_t_find
(
struct
avl_traverser
*,
struct
avl_table
*,
void
*);
107
void
*
avl_t_insert
(
struct
avl_traverser
*,
struct
avl_table
*,
void
*);
108
void
*
avl_t_copy
(
struct
avl_traverser
*,
const
struct
avl_traverser
*);
109
void
*
avl_t_next
(
struct
avl_traverser
*);
110
void
*
avl_t_prev
(
struct
avl_traverser
*);
111
void
*
avl_t_cur
(
struct
avl_traverser
*);
112
void
*
avl_t_replace
(
struct
avl_traverser
*,
void
*);
113
114
#endif
/* avl.h */
lib
vector
dglib
avl.h
Generated on Thu Sep 26 2013 09:47:58 for GRASS Programmer's Manual by
1.8.4