/[cvs]/eggdrop1.9/src/egglib/avl.h
ViewVC logotype

Contents of /eggdrop1.9/src/egglib/avl.h

Parent Directory Parent Directory | Revision Log Revision Log | View Revision Graph Revision Graph


Revision 1.2 - (show annotations) (download) (as text)
Sun Oct 28 13:30:34 2001 UTC (17 years, 11 months ago) by ite
Branch: MAIN
CVS Tags: HEAD
Changes since 1.1: +0 -0 lines
File MIME type: text/x-csrc
FILE REMOVED
Renamed src/adns, src/compat, src/egglib to lib/adns, lib/compat, lib/egglib respectively.

1 /* libavl - manipulates AVL trees.
2 Copyright (C) 1998, 1999 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. See the GNU
12 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 <pfaffben@pilot.msu.edu> on the
20 Internet, or as Ben Pfaff, 12167 Airport Rd, DeWitt MI 48820, USA
21 through more mundane means. */
22
23 /* This is file avl.h in libavl. */
24
25 #ifndef _AVL_H_
26 #define _AVL_H_
27
28 /* The default maximum height of 32 allows for AVL trees having
29 between 5,704,880 and 4,294,967,295 nodes, depending on order of
30 insertion. You may change this compile-time constant as you
31 wish. */
32 #ifndef AVL_MAX_HEIGHT
33 #define AVL_MAX_HEIGHT 32
34 #endif
35
36 /* Structure for a node in an AVL tree. */
37 typedef struct avl_node_b {
38 void *data; /* Pointer to data. */
39 struct avl_node_b *link[2]; /* Subtrees. */
40 signed char bal; /* Balance factor. */
41 char cache; /* Used during insertion. */
42 signed char pad[2]; /* Unused. Reserved for threaded trees. */
43 } avl_node_t;
44
45 /* Used for traversing an AVL tree. */
46 typedef struct avl_traverser_b {
47 int init; /* Initialized? */
48 int nstack; /* Top of stack. */
49 const avl_node_t *p; /* Used for traversal. */
50 const avl_node_t *stack[AVL_MAX_HEIGHT];/* Descended trees. */
51 } avl_traverser_t;
52
53 /* Function types. */
54 typedef int (*avl_comparison_func) (const void *a, const void *b, void *param);
55 typedef void (*avl_node_func) (void *data, void *param);
56
57 /* Structure which holds information about an AVL tree. */
58 typedef struct avl_tree_b {
59 avl_node_t root; /* Tree root node. */
60 avl_comparison_func cmp; /* Used to compare keys. */
61 int count; /* Number of nodes in the tree. */
62 void *param; /* Arbitary user data. */
63 } avl_tree_t;
64
65 /* General functions. */
66 avl_tree_t *avl_create (avl_tree_t *tree, avl_comparison_func, void *param);
67 void avl_destroy (avl_tree_t *, avl_node_func);
68 void avl_free (avl_tree_t *);
69 int avl_count (const avl_tree_t *);
70
71 /* Walk the tree. */
72 void avl_walk (const avl_tree_t *, avl_node_func, void *param);
73 void *avl_traverse (const avl_tree_t *, avl_traverser_t *);
74 #define avl_init_traverser(TRAVERSER) ((TRAVERSER)->init = 0)
75
76 /* Search for a given item. */
77 void **avl_probe (avl_tree_t *, void *);
78 void *avl_delete (avl_tree_t *, const void *);
79 void *avl_find (const avl_tree_t *, const void *);
80 void *avl_find_close (const avl_tree_t *, const void *);
81
82 /* Insert/replace items. */
83 void *avl_insert (avl_tree_t *tree, void *item);
84 void *avl_replace (avl_tree_t *tree, void *item);
85
86 #endif /* avl_h */

webmaster@eggheads.org
ViewVC Help
Powered by ViewVC 1.1.23