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

// SPDX-License-Identifier: GPL-2.0
/*
 * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
 * All Rights Reserved.
 */
#ifndef __LIBFROG_AVL64_H__
#define __LIBFROG_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);

avl64node_t *
avl64_firstino(avl64node_t *root);

avl64node_t *
avl64_lastino(avl64node_t *root);

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 /* __LIBFROG_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	*/
b4a09f89 DW	6	#ifndef __LIBFROG_AVL64_H__
b4a09f89 DW	7	#define __LIBFROG_AVL64_H__
2bd0ea18 NS	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
37717cc4 ES	72	avl64node_t *
	73	avl64_firstino(avl64node_t *root);
	74
	75	avl64node_t *
	76	avl64_lastino(avl64node_t *root);
	77
2bd0ea18 NS	78	void
	79	avl64_init_tree(
	80	avl64tree_desc_t *tree,
	81	avl64ops_t *ops);
	82
	83	avl64node_t *
	84	avl64_findrange(
	85	avl64tree_desc_t *tree,
14f8b681	86	uint64_t value);
2bd0ea18 NS	87
	88	avl64node_t *
	89	avl64_find(
	90	avl64tree_desc_t *tree,
14f8b681	91	uint64_t value);
2bd0ea18 NS	92
	93	avl64node_t *
	94	avl64_findanyrange(
	95	avl64tree_desc_t *tree,
14f8b681 DW	96	uint64_t start,
14f8b681 DW	97	uint64_t end,
2bd0ea18 NS	98	int checklen);
	99
	100
	101	avl64node_t *
	102	avl64_findadjacent(
	103	avl64tree_desc_t *tree,
14f8b681	104	uint64_t value,
2bd0ea18 NS	105	int dir);
2bd0ea18 NS	106
2bd0ea18 NS	107	void
2bd0ea18 NS	108	avl64_findranges(
0c2a7d46	109	avl64tree_desc_t *tree,
14f8b681 DW	110	uint64_t start,
14f8b681 DW	111	uint64_t end,
dfc130f3	112	avl64node_t **startp,
2bd0ea18	113	avl64node_t **endp);
2bd0ea18 NS	114
	115	/*
	116	* avoid complaints about multiple def's since these are only used by
	117	* the avl code internally
	118	*/
	119	#ifndef AVL_PRECEED
	120	#define AVL_PRECEED 0x1
	121	#define AVL_SUCCEED 0x2
	122
	123	#define AVL_INCLUDE_ZEROLEN 0x0000
	124	#define AVL_EXCLUDE_ZEROLEN 0x0001
	125	#endif
	126
b4a09f89	127	#endif /* __LIBFROG_AVL64_H__ */