[thirdparty/xfsprogs-dev.git] / repair / avl.h

/*
 * 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 {
	__psunsigned_t	(*avl_start)(avlnode_t *);
	__psunsigned_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);

avlnode_t *
avl_findrange(
	avltree_desc_t *tree,
	__psunsigned_t value);

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

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


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

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

#define AVL_PRECEED	0x1
#define AVL_SUCCEED	0x2

#define AVL_INCLUDE_ZEROLEN	0x0000
#define AVL_EXCLUDE_ZEROLEN	0x0001

#endif /* __SYS_AVL_H__ */
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
da23017d NS	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 __SYS_AVL_H__
	19	#define __SYS_AVL_H__
	20
	21
	22	typedef struct avlnode {
dfc130f3 RC	23	struct avlnode avl_forw; / pointer to right child (> parent) */
dfc130f3 RC	24	struct avlnode avl_back; / pointer to left child (< parent) */
2bd0ea18 NS	25	struct avlnode avl_parent; / parent pointer */
	26	struct avlnode avl_nextino; / next in-order; NULL terminated list*/
	27	char avl_balance; /* tree balance */
	28	} avlnode_t;
	29
	30	/*
	31	* avl-tree operations
	32	*/
	33	typedef struct avlops {
	34	__psunsigned_t (avl_start)(avlnode_t );
	35	__psunsigned_t (avl_end)(avlnode_t );
	36	} avlops_t;
	37
	38	#define AVL_START(tree, n) (*(tree)->avl_ops->avl_start)(n)
	39	#define AVL_END(tree, n) (*(tree)->avl_ops->avl_end)(n)
	40
dfc130f3	41	/*
2bd0ea18 NS	42	* tree descriptor:
	43	* root points to the root of the tree.
	44	* firstino points to the first in the ordered list.
	45	*/
	46	typedef struct avltree_desc {
	47	avlnode_t *avl_root;
	48	avlnode_t *avl_firstino;
	49	avlops_t *avl_ops;
	50	short avl_flags;
	51	} avltree_desc_t;
	52
	53	/* possible values for avl_balance */
	54
	55	#define AVL_BACK 1
	56	#define AVL_BALANCE 0
	57	#define AVL_FORW 2
	58
	59	/* possible values for avl_flags */
	60
	61	#define AVLF_DUPLICITY 0x0001 /* no warnings on insert dups */
	62
	63	/*
	64	* 'Exported' avl tree routines
	65	*/
	66	avlnode_t
	67	*avl_insert(
	68	avltree_desc_t *tree,
	69	avlnode_t *newnode);
	70
	71	void
	72	avl_delete(
	73	avltree_desc_t *tree,
	74	avlnode_t *np);
	75
	76	void
	77	avl_insert_immediate(
	78	avltree_desc_t *tree,
	79	avlnode_t *afterp,
	80	avlnode_t *newnode);
dfc130f3	81
2bd0ea18 NS	82	void
	83	avl_init_tree(
	84	avltree_desc_t *tree,
	85	avlops_t *ops);
	86
	87	avlnode_t *
	88	avl_findrange(
	89	avltree_desc_t *tree,
	90	__psunsigned_t value);
	91
	92	avlnode_t *
	93	avl_find(
	94	avltree_desc_t *tree,
	95	__psunsigned_t value);
	96
	97	avlnode_t *
	98	avl_findanyrange(
	99	avltree_desc_t *tree,
	100	__psunsigned_t start,
	101	__psunsigned_t end,
	102	int checklen);
	103
	104
	105	avlnode_t *
	106	avl_findadjacent(
	107	avltree_desc_t *tree,
	108	__psunsigned_t value,
	109	int dir);
	110
2bd0ea18 NS	111	void
	112	avl_findranges(
	113	register avltree_desc_t *tree,
	114	register __psunsigned_t start,
	115	register __psunsigned_t end,
dfc130f3	116	avlnode_t **startp,
2bd0ea18	117	avlnode_t **endp);
2bd0ea18 NS	118
	119	#define AVL_PRECEED 0x1
	120	#define AVL_SUCCEED 0x2
	121
	122	#define AVL_INCLUDE_ZEROLEN 0x0000
	123	#define AVL_EXCLUDE_ZEROLEN 0x0001
	124
	125	#endif /* __SYS_AVL_H__ */