]>
Commit | Line | Data |
---|---|---|
da23017d NS |
1 | /* |
2 | * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc. | |
3 | * All Rights Reserved. | |
dfc130f3 | 4 | * |
da23017d NS |
5 | * This program is free software; you can redistribute it and/or |
6 | * modify it under the terms of the GNU General Public License as | |
2bd0ea18 | 7 | * published by the Free Software Foundation. |
dfc130f3 | 8 | * |
da23017d NS |
9 | * This program is distributed in the hope that it would be useful, |
10 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
11 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
12 | * GNU General Public License for more details. | |
dfc130f3 | 13 | * |
da23017d NS |
14 | * You should have received a copy of the GNU General Public License |
15 | * along with this program; if not, write the Free Software Foundation, | |
16 | * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA | |
17 | */ | |
2bd0ea18 NS |
18 | #ifndef __XR_AVL64_H__ |
19 | #define __XR_AVL64_H__ | |
20 | ||
21 | #include <sys/types.h> | |
22 | ||
23 | typedef struct avl64node { | |
dfc130f3 RC |
24 | struct avl64node *avl_forw; /* pointer to right child (> parent) */ |
25 | struct avl64node *avl_back; /* pointer to left child (< parent) */ | |
2bd0ea18 NS |
26 | struct avl64node *avl_parent; /* parent pointer */ |
27 | struct avl64node *avl_nextino; /* next in-order; NULL terminated list*/ | |
28 | char avl_balance; /* tree balance */ | |
29 | } avl64node_t; | |
30 | ||
31 | /* | |
32 | * avl-tree operations | |
33 | */ | |
34 | typedef struct avl64ops { | |
14f8b681 DW |
35 | uint64_t (*avl_start)(avl64node_t *); |
36 | uint64_t (*avl_end)(avl64node_t *); | |
2bd0ea18 NS |
37 | } avl64ops_t; |
38 | ||
39 | /* | |
40 | * avoid complaints about multiple def's since these are only used by | |
41 | * the avl code internally | |
42 | */ | |
43 | #ifndef AVL_START | |
44 | #define AVL_START(tree, n) (*(tree)->avl_ops->avl_start)(n) | |
45 | #define AVL_END(tree, n) (*(tree)->avl_ops->avl_end)(n) | |
46 | #endif | |
47 | ||
dfc130f3 | 48 | /* |
2bd0ea18 NS |
49 | * tree descriptor: |
50 | * root points to the root of the tree. | |
51 | * firstino points to the first in the ordered list. | |
52 | */ | |
53 | typedef struct avl64tree_desc { | |
54 | avl64node_t *avl_root; | |
55 | avl64node_t *avl_firstino; | |
56 | avl64ops_t *avl_ops; | |
57 | } avl64tree_desc_t; | |
58 | ||
59 | /* possible values for avl_balance */ | |
60 | ||
61 | #define AVL_BACK 1 | |
62 | #define AVL_BALANCE 0 | |
63 | #define AVL_FORW 2 | |
64 | ||
65 | /* | |
66 | * 'Exported' avl tree routines | |
67 | */ | |
68 | avl64node_t | |
69 | *avl64_insert( | |
70 | avl64tree_desc_t *tree, | |
71 | avl64node_t *newnode); | |
72 | ||
73 | void | |
74 | avl64_delete( | |
75 | avl64tree_desc_t *tree, | |
76 | avl64node_t *np); | |
77 | ||
78 | void | |
79 | avl64_insert_immediate( | |
80 | avl64tree_desc_t *tree, | |
81 | avl64node_t *afterp, | |
82 | avl64node_t *newnode); | |
dfc130f3 | 83 | |
2bd0ea18 NS |
84 | void |
85 | avl64_init_tree( | |
86 | avl64tree_desc_t *tree, | |
87 | avl64ops_t *ops); | |
88 | ||
89 | avl64node_t * | |
90 | avl64_findrange( | |
91 | avl64tree_desc_t *tree, | |
14f8b681 | 92 | uint64_t value); |
2bd0ea18 NS |
93 | |
94 | avl64node_t * | |
95 | avl64_find( | |
96 | avl64tree_desc_t *tree, | |
14f8b681 | 97 | uint64_t value); |
2bd0ea18 NS |
98 | |
99 | avl64node_t * | |
100 | avl64_findanyrange( | |
101 | avl64tree_desc_t *tree, | |
14f8b681 DW |
102 | uint64_t start, |
103 | uint64_t end, | |
2bd0ea18 NS |
104 | int checklen); |
105 | ||
106 | ||
107 | avl64node_t * | |
108 | avl64_findadjacent( | |
109 | avl64tree_desc_t *tree, | |
14f8b681 | 110 | uint64_t value, |
2bd0ea18 NS |
111 | int dir); |
112 | ||
2bd0ea18 NS |
113 | void |
114 | avl64_findranges( | |
0c2a7d46 | 115 | avl64tree_desc_t *tree, |
14f8b681 DW |
116 | uint64_t start, |
117 | uint64_t end, | |
dfc130f3 | 118 | avl64node_t **startp, |
2bd0ea18 | 119 | avl64node_t **endp); |
2bd0ea18 NS |
120 | |
121 | /* | |
122 | * avoid complaints about multiple def's since these are only used by | |
123 | * the avl code internally | |
124 | */ | |
125 | #ifndef AVL_PRECEED | |
126 | #define AVL_PRECEED 0x1 | |
127 | #define AVL_SUCCEED 0x2 | |
128 | ||
129 | #define AVL_INCLUDE_ZEROLEN 0x0000 | |
130 | #define AVL_EXCLUDE_ZEROLEN 0x0001 | |
131 | #endif | |
132 | ||
133 | #endif /* __XR_AVL64_H__ */ |