]>
Commit | Line | Data |
---|---|---|
1 | /************************************************************************** | |
2 | * * | |
3 | * Copyright (c) 2000-2002 Silicon Graphics, Inc. All Rights Reserved. | |
4 | * | |
5 | * This program is free software; you can redistribute it and/or modify it | |
6 | * under the terms of version 2 of the GNU General Public License as | |
7 | * published by the Free Software Foundation. | |
8 | * | |
9 | * This program is distributed in the hope that it would be useful, but | |
10 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
11 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. | |
12 | * | |
13 | * Further, this software is distributed without any warranty that it is | |
14 | * free of the rightful claim of any third person regarding infringement | |
15 | * or the like. Any license provided herein, whether implied or | |
16 | * otherwise, applies only to this software file. Patent licenses, if | |
17 | * any, provided herein do not apply to combinations of this program with | |
18 | * other software, or any other product whatsoever. | |
19 | * | |
20 | * You should have received a copy of the GNU General Public License along | |
21 | * with this program; if not, write the Free Software Foundation, Inc., 59 | |
22 | * Temple Place - Suite 330, Boston MA 02111-1307, USA. | |
23 | * | |
24 | * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy, | |
25 | * Mountain View, CA 94043, or: | |
26 | * | |
27 | * http://www.sgi.com | |
28 | * | |
29 | * For further information regarding this notice, see: | |
30 | * | |
31 | * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/ | |
32 | * * | |
33 | **************************************************************************/ | |
34 | #ifndef __SYS_AVL_H__ | |
35 | #define __SYS_AVL_H__ | |
36 | ||
37 | ||
38 | typedef struct avlnode { | |
39 | struct avlnode *avl_forw; /* pointer to right child (> parent) */ | |
40 | struct avlnode *avl_back; /* pointer to left child (< parent) */ | |
41 | struct avlnode *avl_parent; /* parent pointer */ | |
42 | struct avlnode *avl_nextino; /* next in-order; NULL terminated list*/ | |
43 | char avl_balance; /* tree balance */ | |
44 | } avlnode_t; | |
45 | ||
46 | /* | |
47 | * avl-tree operations | |
48 | */ | |
49 | typedef struct avlops { | |
50 | __psunsigned_t (*avl_start)(avlnode_t *); | |
51 | __psunsigned_t (*avl_end)(avlnode_t *); | |
52 | } avlops_t; | |
53 | ||
54 | #define AVL_START(tree, n) (*(tree)->avl_ops->avl_start)(n) | |
55 | #define AVL_END(tree, n) (*(tree)->avl_ops->avl_end)(n) | |
56 | ||
57 | /* | |
58 | * tree descriptor: | |
59 | * root points to the root of the tree. | |
60 | * firstino points to the first in the ordered list. | |
61 | */ | |
62 | typedef struct avltree_desc { | |
63 | avlnode_t *avl_root; | |
64 | avlnode_t *avl_firstino; | |
65 | avlops_t *avl_ops; | |
66 | short avl_flags; | |
67 | } avltree_desc_t; | |
68 | ||
69 | /* possible values for avl_balance */ | |
70 | ||
71 | #define AVL_BACK 1 | |
72 | #define AVL_BALANCE 0 | |
73 | #define AVL_FORW 2 | |
74 | ||
75 | /* possible values for avl_flags */ | |
76 | ||
77 | #define AVLF_DUPLICITY 0x0001 /* no warnings on insert dups */ | |
78 | ||
79 | /* | |
80 | * 'Exported' avl tree routines | |
81 | */ | |
82 | avlnode_t | |
83 | *avl_insert( | |
84 | avltree_desc_t *tree, | |
85 | avlnode_t *newnode); | |
86 | ||
87 | void | |
88 | avl_delete( | |
89 | avltree_desc_t *tree, | |
90 | avlnode_t *np); | |
91 | ||
92 | void | |
93 | avl_insert_immediate( | |
94 | avltree_desc_t *tree, | |
95 | avlnode_t *afterp, | |
96 | avlnode_t *newnode); | |
97 | ||
98 | void | |
99 | avl_init_tree( | |
100 | avltree_desc_t *tree, | |
101 | avlops_t *ops); | |
102 | ||
103 | avlnode_t * | |
104 | avl_findrange( | |
105 | avltree_desc_t *tree, | |
106 | __psunsigned_t value); | |
107 | ||
108 | avlnode_t * | |
109 | avl_find( | |
110 | avltree_desc_t *tree, | |
111 | __psunsigned_t value); | |
112 | ||
113 | avlnode_t * | |
114 | avl_findanyrange( | |
115 | avltree_desc_t *tree, | |
116 | __psunsigned_t start, | |
117 | __psunsigned_t end, | |
118 | int checklen); | |
119 | ||
120 | ||
121 | avlnode_t * | |
122 | avl_findadjacent( | |
123 | avltree_desc_t *tree, | |
124 | __psunsigned_t value, | |
125 | int dir); | |
126 | ||
127 | void | |
128 | avl_findranges( | |
129 | register avltree_desc_t *tree, | |
130 | register __psunsigned_t start, | |
131 | register __psunsigned_t end, | |
132 | avlnode_t **startp, | |
133 | avlnode_t **endp); | |
134 | ||
135 | #define AVL_PRECEED 0x1 | |
136 | #define AVL_SUCCEED 0x2 | |
137 | ||
138 | #define AVL_INCLUDE_ZEROLEN 0x0000 | |
139 | #define AVL_EXCLUDE_ZEROLEN 0x0001 | |
140 | ||
141 | #endif /* __SYS_AVL_H__ */ |