[thirdparty/xfsprogs-dev.git] / include / avl64.h

// SPDX-License-Identifier: GPL-2.0
/*
 * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
 * All Rights Reserved.
 */
#ifndef __XR_AVL64_H__
#define __XR_AVL64_H__

#include <sys/types.h>

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

/*
 * avl-tree operations
 */
typedef struct avl64ops {
	uint64_t	(*avl_start)(avl64node_t *);
	uint64_t	(*avl_end)(avl64node_t *);
} avl64ops_t;

/*
 * avoid complaints about multiple def's since these are only used by
 * the avl code internally
 */
#ifndef AVL_START
#define	AVL_START(tree, n)	(*(tree)->avl_ops->avl_start)(n)
#define	AVL_END(tree, n)	(*(tree)->avl_ops->avl_end)(n)
#endif

/*
 * tree descriptor:
 *	root points to the root of the tree.
 *	firstino points to the first in the ordered list.
 */
typedef struct avl64tree_desc {
	avl64node_t	*avl_root;
	avl64node_t	*avl_firstino;
	avl64ops_t	*avl_ops;
} avl64tree_desc_t;

/* possible values for avl_balance */

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

/*
 * 'Exported' avl tree routines
 */
avl64node_t
*avl64_insert(
	avl64tree_desc_t *tree,
	avl64node_t *newnode);

void
avl64_delete(
	avl64tree_desc_t *tree,
	avl64node_t *np);

void
avl64_insert_immediate(
	avl64tree_desc_t *tree,
	avl64node_t *afterp,
	avl64node_t *newnode);

void
avl64_init_tree(
	avl64tree_desc_t  *tree,
	avl64ops_t *ops);

avl64node_t *
avl64_findrange(
	avl64tree_desc_t *tree,
	uint64_t value);

avl64node_t *
avl64_find(
	avl64tree_desc_t *tree,
	uint64_t value);

avl64node_t *
avl64_findanyrange(
	avl64tree_desc_t *tree,
	uint64_t	start,
	uint64_t	end,
	int     checklen);


avl64node_t *
avl64_findadjacent(
	avl64tree_desc_t *tree,
	uint64_t	value,
	int		dir);

void
avl64_findranges(
	avl64tree_desc_t *tree,
	uint64_t	start,
	uint64_t	end,
	avl64node_t	        **startp,
	avl64node_t		**endp);

/*
 * avoid complaints about multiple def's since these are only used by
 * the avl code internally
 */
#ifndef AVL_PRECEED
#define AVL_PRECEED	0x1
#define AVL_SUCCEED	0x2

#define AVL_INCLUDE_ZEROLEN	0x0000
#define AVL_EXCLUDE_ZEROLEN	0x0001
#endif

#endif /* __XR_AVL64_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 __XR_AVL64_H__
	7	#define __XR_AVL64_H__
	8
	9	#include <sys/types.h>
	10
	11	typedef struct avl64node {
dfc130f3 RC	12	struct avl64node avl_forw; / pointer to right child (> parent) */
dfc130f3 RC	13	struct avl64node avl_back; / pointer to left child (< parent) */
2bd0ea18 NS	14	struct avl64node avl_parent; / parent pointer */
	15	struct avl64node avl_nextino; / next in-order; NULL terminated list*/
	16	char avl_balance; /* tree balance */
	17	} avl64node_t;
	18
	19	/*
	20	* avl-tree operations
	21	*/
	22	typedef struct avl64ops {
14f8b681 DW	23	uint64_t (avl_start)(avl64node_t );
14f8b681 DW	24	uint64_t (avl_end)(avl64node_t );
2bd0ea18 NS	25	} avl64ops_t;
	26
	27	/*
	28	* avoid complaints about multiple def's since these are only used by
	29	* the avl code internally
	30	*/
	31	#ifndef AVL_START
	32	#define AVL_START(tree, n) (*(tree)->avl_ops->avl_start)(n)
	33	#define AVL_END(tree, n) (*(tree)->avl_ops->avl_end)(n)
	34	#endif
	35
dfc130f3	36	/*
2bd0ea18 NS	37	* tree descriptor:
	38	* root points to the root of the tree.
	39	* firstino points to the first in the ordered list.
	40	*/
	41	typedef struct avl64tree_desc {
	42	avl64node_t *avl_root;
	43	avl64node_t *avl_firstino;
	44	avl64ops_t *avl_ops;
	45	} avl64tree_desc_t;
	46
	47	/* possible values for avl_balance */
	48
	49	#define AVL_BACK 1
	50	#define AVL_BALANCE 0
	51	#define AVL_FORW 2
	52
	53	/*
	54	* 'Exported' avl tree routines
	55	*/
	56	avl64node_t
	57	*avl64_insert(
	58	avl64tree_desc_t *tree,
	59	avl64node_t *newnode);
	60
	61	void
	62	avl64_delete(
	63	avl64tree_desc_t *tree,
	64	avl64node_t *np);
	65
	66	void
	67	avl64_insert_immediate(
	68	avl64tree_desc_t *tree,
	69	avl64node_t *afterp,
	70	avl64node_t *newnode);
dfc130f3	71
2bd0ea18 NS	72	void
	73	avl64_init_tree(
	74	avl64tree_desc_t *tree,
	75	avl64ops_t *ops);
	76
	77	avl64node_t *
	78	avl64_findrange(
	79	avl64tree_desc_t *tree,
14f8b681	80	uint64_t value);
2bd0ea18 NS	81
	82	avl64node_t *
	83	avl64_find(
	84	avl64tree_desc_t *tree,
14f8b681	85	uint64_t value);
2bd0ea18 NS	86
	87	avl64node_t *
	88	avl64_findanyrange(
	89	avl64tree_desc_t *tree,
14f8b681 DW	90	uint64_t start,
14f8b681 DW	91	uint64_t end,
2bd0ea18 NS	92	int checklen);
	93
	94
	95	avl64node_t *
	96	avl64_findadjacent(
	97	avl64tree_desc_t *tree,
14f8b681	98	uint64_t value,
2bd0ea18 NS	99	int dir);
2bd0ea18 NS	100
2bd0ea18 NS	101	void
2bd0ea18 NS	102	avl64_findranges(
0c2a7d46	103	avl64tree_desc_t *tree,
14f8b681 DW	104	uint64_t start,
14f8b681 DW	105	uint64_t end,
dfc130f3	106	avl64node_t **startp,
2bd0ea18	107	avl64node_t **endp);
2bd0ea18 NS	108
	109	/*
	110	* avoid complaints about multiple def's since these are only used by
	111	* the avl code internally
	112	*/
	113	#ifndef AVL_PRECEED
	114	#define AVL_PRECEED 0x1
	115	#define AVL_SUCCEED 0x2
	116
	117	#define AVL_INCLUDE_ZEROLEN 0x0000
	118	#define AVL_EXCLUDE_ZEROLEN 0x0001
	119	#endif
	120
	121	#endif /* __XR_AVL64_H__ */