Projet Informatique Théorique 2016
Instructions et Documentation
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. */
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. */
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 */
Definition: avl.h:67
Definition: avl.h:56