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

// SPDX-License-Identifier: GPL-2.0
/*
 * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
 * All Rights Reserved.
 */
#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__ */
Commit	Line	Data
959ef981	1	// SPDX-License-Identifier: GPL-2.0
da23017d NS	2	/*
	3	* Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
	4	* All Rights Reserved.
da23017d	5	*/
2bd0ea18 NS	6	#ifndef __SYS_AVL_H__
	7	#define __SYS_AVL_H__
	8
	9
	10	typedef struct avlnode {
dfc130f3 RC	11	struct avlnode avl_forw; / pointer to right child (> parent) */
dfc130f3 RC	12	struct avlnode avl_back; / pointer to left child (< parent) */
2bd0ea18 NS	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 {
ee6cd73e CH	22	uintptr_t (avl_start)(avlnode_t );
ee6cd73e CH	23	uintptr_t (avl_end)(avlnode_t );
2bd0ea18 NS	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
dfc130f3	29	/*
2bd0ea18 NS	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);
dfc130f3	69
2bd0ea18 NS	70	void
	71	avl_init_tree(
	72	avltree_desc_t *tree,
	73	avlops_t *ops);
	74
78a0dc91	75	static inline avlnode_t *
2bd0ea18 NS	76	avl_findrange(
2bd0ea18 NS	77	avltree_desc_t *tree,
ee6cd73e	78	uintptr_t value)
1e77098c	79	{
0c2a7d46	80	avlnode_t *np = tree->avl_root;
1e77098c MV	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	}
2bd0ea18 NS	97
	98	avlnode_t *
	99	avl_find(
	100	avltree_desc_t *tree,
ee6cd73e	101	uintptr_t value);
2bd0ea18 NS	102
	103	avlnode_t *
	104	avl_findanyrange(
	105	avltree_desc_t *tree,
ee6cd73e CH	106	uintptr_t start,
ee6cd73e CH	107	uintptr_t end,
2bd0ea18 NS	108	int checklen);
	109
	110
	111	avlnode_t *
	112	avl_findadjacent(
	113	avltree_desc_t *tree,
ee6cd73e	114	uintptr_t value,
2bd0ea18 NS	115	int dir);
2bd0ea18 NS	116
2bd0ea18 NS	117	void
2bd0ea18 NS	118	avl_findranges(
0c2a7d46	119	avltree_desc_t *tree,
ee6cd73e CH	120	uintptr_t start,
ee6cd73e CH	121	uintptr_t end,
dfc130f3	122	avlnode_t **startp,
2bd0ea18	123	avlnode_t **endp);
2bd0ea18	124
52cb19dc CH	125	avlnode_t *
	126	avl_firstino(
	127	avlnode_t *root);
	128
	129	avlnode_t *
	130	avl_lastino(
	131	avlnode_t *root);
	132
	133
2bd0ea18 NS	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__ */