File: avl.h

package info (click to toggle)
xfsprogs 4.9.0+nmu1
  • links: PTS
  • area: main
  • in suites: stretch
  • size: 8,012 kB
  • ctags: 10,574
  • sloc: ansic: 110,850; sh: 3,804; makefile: 863; python: 126
file content (152 lines) | stat: -rw-r--r-- 3,168 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
/*
 * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
 * All Rights Reserved.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it would be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write the Free Software Foundation,
 * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */
#ifndef __SYS_AVL_H__
#define __SYS_AVL_H__


typedef struct	avlnode {
	struct	avlnode	*avl_forw;	/* pointer to right child  (> parent) */
	struct	avlnode *avl_back;	/* pointer to left child  (< parent) */
	struct	avlnode *avl_parent;	/* parent pointer */
	struct	avlnode *avl_nextino;	/* next in-order; NULL terminated list*/
	char		 avl_balance;	/* tree balance */
} avlnode_t;

/*
 * avl-tree operations
 */
typedef struct avlops {
	uintptr_t	(*avl_start)(avlnode_t *);
	uintptr_t	(*avl_end)(avlnode_t *);
} avlops_t;

#define	AVL_START(tree, n)	(*(tree)->avl_ops->avl_start)(n)
#define	AVL_END(tree, n)	(*(tree)->avl_ops->avl_end)(n)

/*
 * tree descriptor:
 *	root points to the root of the tree.
 *	firstino points to the first in the ordered list.
 */
typedef struct avltree_desc {
	avlnode_t	*avl_root;
	avlnode_t	*avl_firstino;
	avlops_t	*avl_ops;
	short		 avl_flags;
} avltree_desc_t;

/* possible values for avl_balance */

#define AVL_BACK	1
#define AVL_BALANCE	0
#define AVL_FORW	2

/* possible values for avl_flags */

#define AVLF_DUPLICITY	0x0001		/* no warnings on insert dups */

/*
 * 'Exported' avl tree routines
 */
avlnode_t
*avl_insert(
	avltree_desc_t *tree,
	avlnode_t *newnode);

void
avl_delete(
	avltree_desc_t *tree,
	avlnode_t *np);

void
avl_insert_immediate(
	avltree_desc_t *tree,
	avlnode_t *afterp,
	avlnode_t *newnode);

void
avl_init_tree(
	avltree_desc_t  *tree,
	avlops_t *ops);

static inline avlnode_t *
avl_findrange(
	avltree_desc_t *tree,
	uintptr_t value)
{
	avlnode_t *np = tree->avl_root;

	while (np) {
		if (value < AVL_START(tree, np)) {
			np = np->avl_back;
			continue;
		}
		if (value >= AVL_END(tree, np)) {
			np = np->avl_forw;
			continue;
		}
		ASSERT(AVL_START(tree, np) <= value &&
		       value < AVL_END(tree, np));
		return np;
	}
	return NULL;
}

avlnode_t *
avl_find(
	avltree_desc_t *tree,
	uintptr_t value);

avlnode_t *
avl_findanyrange(
	avltree_desc_t *tree,
	uintptr_t start,
	uintptr_t end,
	int     checklen);


avlnode_t *
avl_findadjacent(
	avltree_desc_t *tree,
	uintptr_t value,
	int		dir);

void
avl_findranges(
	avltree_desc_t *tree,
	uintptr_t start,
	uintptr_t end,
	avlnode_t	        **startp,
	avlnode_t		**endp);

avlnode_t *
avl_firstino(
	avlnode_t		*root);

avlnode_t *
avl_lastino(
	avlnode_t		*root);


#define AVL_PRECEED	0x1
#define AVL_SUCCEED	0x2

#define AVL_INCLUDE_ZEROLEN	0x0000
#define AVL_EXCLUDE_ZEROLEN	0x0001

#endif /* __SYS_AVL_H__ */