]>
Commit | Line | Data |
---|---|---|
1 | // SPDX-License-Identifier: GPL-2.0 | |
2 | /* | |
3 | * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc. | |
4 | * All Rights Reserved. | |
5 | */ | |
6 | #ifndef __SYS_AVL_H__ | |
7 | #define __SYS_AVL_H__ | |
8 | ||
9 | ||
10 | typedef struct avlnode { | |
11 | struct avlnode *avl_forw; /* pointer to right child (> parent) */ | |
12 | struct avlnode *avl_back; /* pointer to left child (< parent) */ | |
13 | struct avlnode *avl_parent; /* parent pointer */ | |
14 | struct avlnode *avl_nextino; /* next in-order; NULL terminated list*/ | |
15 | char avl_balance; /* tree balance */ | |
16 | } avlnode_t; | |
17 | ||
18 | /* | |
19 | * avl-tree operations | |
20 | */ | |
21 | typedef struct avlops { | |
22 | uintptr_t (*avl_start)(avlnode_t *); | |
23 | uintptr_t (*avl_end)(avlnode_t *); | |
24 | } avlops_t; | |
25 | ||
26 | #define AVL_START(tree, n) (*(tree)->avl_ops->avl_start)(n) | |
27 | #define AVL_END(tree, n) (*(tree)->avl_ops->avl_end)(n) | |
28 | ||
29 | /* | |
30 | * tree descriptor: | |
31 | * root points to the root of the tree. | |
32 | * firstino points to the first in the ordered list. | |
33 | */ | |
34 | typedef struct avltree_desc { | |
35 | avlnode_t *avl_root; | |
36 | avlnode_t *avl_firstino; | |
37 | avlops_t *avl_ops; | |
38 | short avl_flags; | |
39 | } avltree_desc_t; | |
40 | ||
41 | /* possible values for avl_balance */ | |
42 | ||
43 | #define AVL_BACK 1 | |
44 | #define AVL_BALANCE 0 | |
45 | #define AVL_FORW 2 | |
46 | ||
47 | /* possible values for avl_flags */ | |
48 | ||
49 | #define AVLF_DUPLICITY 0x0001 /* no warnings on insert dups */ | |
50 | ||
51 | /* | |
52 | * 'Exported' avl tree routines | |
53 | */ | |
54 | avlnode_t | |
55 | *avl_insert( | |
56 | avltree_desc_t *tree, | |
57 | avlnode_t *newnode); | |
58 | ||
59 | void | |
60 | avl_delete( | |
61 | avltree_desc_t *tree, | |
62 | avlnode_t *np); | |
63 | ||
64 | void | |
65 | avl_insert_immediate( | |
66 | avltree_desc_t *tree, | |
67 | avlnode_t *afterp, | |
68 | avlnode_t *newnode); | |
69 | ||
70 | void | |
71 | avl_init_tree( | |
72 | avltree_desc_t *tree, | |
73 | avlops_t *ops); | |
74 | ||
75 | static inline avlnode_t * | |
76 | avl_findrange( | |
77 | avltree_desc_t *tree, | |
78 | uintptr_t value) | |
79 | { | |
80 | avlnode_t *np = tree->avl_root; | |
81 | ||
82 | while (np) { | |
83 | if (value < AVL_START(tree, np)) { | |
84 | np = np->avl_back; | |
85 | continue; | |
86 | } | |
87 | if (value >= AVL_END(tree, np)) { | |
88 | np = np->avl_forw; | |
89 | continue; | |
90 | } | |
91 | ASSERT(AVL_START(tree, np) <= value && | |
92 | value < AVL_END(tree, np)); | |
93 | return np; | |
94 | } | |
95 | return NULL; | |
96 | } | |
97 | ||
98 | avlnode_t * | |
99 | avl_find( | |
100 | avltree_desc_t *tree, | |
101 | uintptr_t value); | |
102 | ||
103 | avlnode_t * | |
104 | avl_findanyrange( | |
105 | avltree_desc_t *tree, | |
106 | uintptr_t start, | |
107 | uintptr_t end, | |
108 | int checklen); | |
109 | ||
110 | ||
111 | avlnode_t * | |
112 | avl_findadjacent( | |
113 | avltree_desc_t *tree, | |
114 | uintptr_t value, | |
115 | int dir); | |
116 | ||
117 | void | |
118 | avl_findranges( | |
119 | avltree_desc_t *tree, | |
120 | uintptr_t start, | |
121 | uintptr_t end, | |
122 | avlnode_t **startp, | |
123 | avlnode_t **endp); | |
124 | ||
125 | avlnode_t * | |
126 | avl_firstino( | |
127 | avlnode_t *root); | |
128 | ||
129 | avlnode_t * | |
130 | avl_lastino( | |
131 | avlnode_t *root); | |
132 | ||
133 | ||
134 | #define AVL_PRECEED 0x1 | |
135 | #define AVL_SUCCEED 0x2 | |
136 | ||
137 | #define AVL_INCLUDE_ZEROLEN 0x0000 | |
138 | #define AVL_EXCLUDE_ZEROLEN 0x0001 | |
139 | ||
140 | #endif /* __SYS_AVL_H__ */ |