]>
git.ipfire.org Git - thirdparty/xfsprogs-dev.git/blob - repair/avl.h
1 /**************************************************************************
3 * Copyright (c) 2000 Silicon Graphics, Inc. All Rights Reserved.
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.
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.
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.
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.
24 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
25 * Mountain View, CA 94043, or:
29 * For further information regarding this notice, see:
31 * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
33 **************************************************************************/
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 */
49 typedef struct avlops
{
50 __psunsigned_t (*avl_start
)(avlnode_t
*);
51 __psunsigned_t (*avl_end
)(avlnode_t
*);
54 #define AVL_START(tree, n) (*(tree)->avl_ops->avl_start)(n)
55 #define AVL_END(tree, n) (*(tree)->avl_ops->avl_end)(n)
59 * root points to the root of the tree.
60 * firstino points to the first in the ordered list.
62 typedef struct avltree_desc
{
64 avlnode_t
*avl_firstino
;
69 /* possible values for avl_balance */
75 /* possible values for avl_flags */
77 #define AVLF_DUPLICITY 0x0001 /* no warnings on insert dups */
80 * 'Exported' avl tree routines
100 avltree_desc_t
*tree
,
105 avltree_desc_t
*tree
,
106 __psunsigned_t value
);
110 avltree_desc_t
*tree
,
111 __psunsigned_t value
);
115 avltree_desc_t
*tree
,
116 __psunsigned_t start
,
123 avltree_desc_t
*tree
,
124 __psunsigned_t value
,
129 register avltree_desc_t
*tree
,
130 register __psunsigned_t start
,
131 register __psunsigned_t end
,
135 #define AVL_PRECEED 0x1
136 #define AVL_SUCCEED 0x2
138 #define AVL_INCLUDE_ZEROLEN 0x0000
139 #define AVL_EXCLUDE_ZEROLEN 0x0001
141 #endif /* __SYS_AVL_H__ */