Projet Informatique Théorique 2016
Instructions et Documentation
Page principale
Pages associées
Structures de données
Fichiers
Liste des fichiers
Variables globales
avl.h
1
/* libavl - library for manipulation of binary trees.
2
Copyright (C) 1998-2002 Free Software Foundation, Inc.
3
4
This program is free software; you can redistribute it and/or
5
modify it under the terms of the GNU General Public License as
6
published by the Free Software Foundation; either version 2 of the
7
License, or (at your option) any later version.
8
9
This program is distributed in the hope that it will be useful, but
10
WITHOUT ANY WARRANTY; without even the implied warranty of
11
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12
See the GNU General Public License for more details.
13
14
You should have received a copy of the GNU General Public License
15
along with this program; if not, write to the Free Software
16
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
17
02111-1307, USA.
18
19
The author may be contacted at <blp@gnu.org> on the Internet, or
20
write to Ben Pfaff, Stanford University, Computer Science Dept., 353
21
Serra Mall, Stanford CA 94305, USA.
22
*/
23
24
#ifndef AVL_H
25
#define AVL_H 1
26
27
#include <stddef.h>
28
29
/* Function types. */
30
typedef
int
avl_comparison_func (
const
void
*avl_a,
const
void
*avl_b,
31
void
*avl_param);
32
typedef
void
avl_item_func (
void
*avl_item,
void
*avl_param);
33
typedef
void
*avl_copy_func (
void
*avl_item,
void
*avl_param);
34
35
#ifndef LIBAVL_ALLOCATOR
36
#define LIBAVL_ALLOCATOR
37
/* Memory allocator. */
38
struct
libavl_allocator
39
{
40
void
*(*libavl_malloc) (
struct
libavl_allocator
*,
size_t
libavl_size);
41
void (*libavl_free) (
struct
libavl_allocator
*,
void
*libavl_block);
42
};
43
#endif
44
45
/* Default memory allocator. */
46
extern
struct
libavl_allocator
avl_allocator_default;
47
void
*avl_malloc (
struct
libavl_allocator
*,
size_t
);
48
void
avl_free (
struct
libavl_allocator
*,
void
*);
49
50
/* Maximum AVL height. */
51
#ifndef AVL_MAX_HEIGHT
52
#define AVL_MAX_HEIGHT 32
53
#endif
54
55
/* Tree data structure. */
56
struct
avl_table
57
{
58
struct
avl_node
*avl_root;
/* Tree's root. */
59
avl_comparison_func *avl_compare;
/* Comparison function. */
60
void
*avl_param;
/* Extra argument to |avl_compare|. */
61
struct
libavl_allocator
*avl_alloc;
/* Memory allocator. */
62
size_t
avl_count;
/* Number of items in tree. */
63
unsigned
long
avl_generation;
/* Generation number. */
64
};
65
66
/* An AVL tree node. */
67
struct
avl_node
68
{
69
struct
avl_node
*avl_link[2];
/* Subtrees. */
70
void
*avl_data;
/* Pointer to data. */
71
signed
char
avl_balance;
/* Balance factor. */
72
};
73
74
/* AVL traverser structure. */
75
struct
avl_traverser
76
{
77
struct
avl_table
*
avl_table
;
/* Tree being traversed. */
78
struct
avl_node
*
avl_node
;
/* Current node in tree. */
79
struct
avl_node *avl_stack[AVL_MAX_HEIGHT];
80
/* All the nodes above |avl_node|. */
81
size_t
avl_height;
/* Number of nodes in |avl_parent|. */
82
unsigned
long
avl_generation;
/* Generation number. */
83
};
84
85
/* Table functions. */
86
struct
avl_table
*avl_create (avl_comparison_func *,
void
*,
87
struct
libavl_allocator
*);
88
struct
avl_table
*avl_copy (
const
struct
avl_table
*, avl_copy_func *,
89
avl_item_func *,
struct
libavl_allocator
*);
90
void
avl_destroy (
struct
avl_table
*, avl_item_func *);
91
void
**avl_probe (
struct
avl_table
*,
void
*);
92
void
*avl_insert (
struct
avl_table
*,
void
*);
93
void
*avl_replace (
struct
avl_table
*,
void
*);
94
void
*avl_delete (
struct
avl_table
*,
const
void
*);
95
void
*avl_find (
const
struct
avl_table
*,
const
void
*);
96
void
avl_assert_insert (
struct
avl_table
*,
void
*);
97
void
*avl_assert_delete (
struct
avl_table
*,
void
*);
98
99
#define avl_count(table) ((size_t) (table)->avl_count)
100
101
/* Table traverser functions. */
102
void
avl_t_init (
struct
avl_traverser
*,
struct
avl_table
*);
103
void
*avl_t_first (
struct
avl_traverser
*,
struct
avl_table
*);
104
void
*avl_t_last (
struct
avl_traverser
*,
struct
avl_table
*);
105
void
*avl_t_find (
struct
avl_traverser
*,
struct
avl_table
*,
void
*);
106
void
*avl_t_insert (
struct
avl_traverser
*,
struct
avl_table
*,
void
*);
107
void
*avl_t_copy (
struct
avl_traverser
*,
const
struct
avl_traverser
*);
108
void
*avl_t_next (
struct
avl_traverser
*);
109
void
*avl_t_prev (
struct
avl_traverser
*);
110
void
*avl_t_cur (
struct
avl_traverser
*);
111
void
*avl_t_replace (
struct
avl_traverser
*,
void
*);
112
int
avl_t_is_null(
struct
avl_traverser
*);
113
114
#endif
/* avl.h */
libavl_allocator
Definition:
avl.h:38
avl_node
Definition:
avl.h:67
avl_table
Definition:
avl.h:56
avl_traverser
Definition:
avl.h:75
Généré par
1.8.9.1