]>
git.ipfire.org Git - thirdparty/xfsprogs-dev.git/blob - libfrog/avl64.h
1 // SPDX-License-Identifier: GPL-2.0
3 * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
6 #ifndef __LIBFROG_AVL64_H__
7 #define __LIBFROG_AVL64_H__
11 typedef struct avl64node
{
12 struct avl64node
*avl_forw
; /* pointer to right child (> parent) */
13 struct avl64node
*avl_back
; /* pointer to left child (< parent) */
14 struct avl64node
*avl_parent
; /* parent pointer */
15 struct avl64node
*avl_nextino
; /* next in-order; NULL terminated list*/
16 char avl_balance
; /* tree balance */
22 typedef struct avl64ops
{
23 uint64_t (*avl_start
)(avl64node_t
*);
24 uint64_t (*avl_end
)(avl64node_t
*);
28 * avoid complaints about multiple def's since these are only used by
29 * the avl code internally
32 #define AVL_START(tree, n) (*(tree)->avl_ops->avl_start)(n)
33 #define AVL_END(tree, n) (*(tree)->avl_ops->avl_end)(n)
38 * root points to the root of the tree.
39 * firstino points to the first in the ordered list.
41 typedef struct avl64tree_desc
{
42 avl64node_t
*avl_root
;
43 avl64node_t
*avl_firstino
;
47 /* possible values for avl_balance */
54 * 'Exported' avl tree routines
58 avl64tree_desc_t
*tree
,
59 avl64node_t
*newnode
);
63 avl64tree_desc_t
*tree
,
67 avl64_insert_immediate(
68 avl64tree_desc_t
*tree
,
70 avl64node_t
*newnode
);
73 avl64_firstino(avl64node_t
*root
);
76 avl64_lastino(avl64node_t
*root
);
80 avl64tree_desc_t
*tree
,
85 avl64tree_desc_t
*tree
,
90 avl64tree_desc_t
*tree
,
95 avl64tree_desc_t
*tree
,
103 avl64tree_desc_t
*tree
,
109 avl64tree_desc_t
*tree
,
112 avl64node_t
**startp
,
116 * avoid complaints about multiple def's since these are only used by
117 * the avl code internally
120 #define AVL_PRECEED 0x1
121 #define AVL_SUCCEED 0x2
123 #define AVL_INCLUDE_ZEROLEN 0x0000
124 #define AVL_EXCLUDE_ZEROLEN 0x0001
127 #endif /* __LIBFROG_AVL64_H__ */