← Back to branch summary

~ubuntu-branches/ubuntu/utopic/xfsprogs/utopic-proposed

« back to all changes in this revision

Viewing changes to repair/avl64.h

  • Committer: Bazaar Package Importer
  • Author(s): Nathan Scott
  • Date: 2002-04-13 09:45:06 UTC
  • Revision ID: james.westby@ubuntu.com-20020413094506-t8dhemv41gkeg4kx
Tags: 2.0.3-1
New upstream bugfix release

Show diffs side-by-side

added added

removed removed

Lines of Context:
repair/avl64.h
 
1
/**************************************************************************
 
2
 *                                                                        *
 
3
 * Copyright (c) 2000 Silicon Graphics, Inc.  All Rights Reserved.
 
4
 * 
 
5
 * This program is free software; you can redistribute it and/or modify it
 
6
 * under the terms of version 2 of the GNU General Public License as
 
7
 * published by the Free Software Foundation.
 
8
 * 
 
9
 * This program is distributed in the hope that it would be useful, but
 
10
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 
11
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 
12
 * 
 
13
 * Further, this software is distributed without any warranty that it is
 
14
 * free of the rightful claim of any third person regarding infringement
 
15
 * or the like.  Any license provided herein, whether implied or
 
16
 * otherwise, applies only to this software file.  Patent licenses, if
 
17
 * any, provided herein do not apply to combinations of this program with
 
18
 * other software, or any other product whatsoever.
 
19
 * 
 
20
 * You should have received a copy of the GNU General Public License along
 
21
 * with this program; if not, write the Free Software Foundation, Inc., 59
 
22
 * Temple Place - Suite 330, Boston MA 02111-1307, USA.
 
23
 * 
 
24
 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
 
25
 * Mountain View, CA  94043, or:
 
26
 * 
 
27
 * http://www.sgi.com 
 
28
 * 
 
29
 * For further information regarding this notice, see: 
 
30
 * 
 
31
 * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
 
32
 *                                                                        *
 
33
 **************************************************************************/
 
34
#ifndef __XR_AVL64_H__
 
35
#define __XR_AVL64_H__
 
36
 
 
37
#include <sys/types.h>
 
38
 
 
39
typedef struct  avl64node {
 
40
        struct  avl64node       *avl_forw;      /* pointer to right child  (> parent) */
 
41
        struct  avl64node *avl_back;    /* pointer to left child  (< parent) */
 
42
        struct  avl64node *avl_parent;  /* parent pointer */
 
43
        struct  avl64node *avl_nextino; /* next in-order; NULL terminated list*/
 
44
        char             avl_balance;   /* tree balance */
 
45
} avl64node_t;
 
46
 
 
47
/*
 
48
 * avl-tree operations
 
49
 */
 
50
typedef struct avl64ops {
 
51
        __uint64_t      (*avl_start)(avl64node_t *);
 
52
        __uint64_t      (*avl_end)(avl64node_t *);
 
53
} avl64ops_t;
 
54
 
 
55
/*
 
56
 * avoid complaints about multiple def's since these are only used by
 
57
 * the avl code internally
 
58
 */
 
59
#ifndef AVL_START
 
60
#define AVL_START(tree, n)      (*(tree)->avl_ops->avl_start)(n)
 
61
#define AVL_END(tree, n)        (*(tree)->avl_ops->avl_end)(n)
 
62
#endif
 
63
 
 
64
/* 
 
65
 * tree descriptor:
 
66
 *      root points to the root of the tree.
 
67
 *      firstino points to the first in the ordered list.
 
68
 */
 
69
typedef struct avl64tree_desc {
 
70
        avl64node_t     *avl_root;
 
71
        avl64node_t     *avl_firstino;
 
72
        avl64ops_t      *avl_ops;
 
73
} avl64tree_desc_t;
 
74
 
 
75
/* possible values for avl_balance */
 
76
 
 
77
#define AVL_BACK        1
 
78
#define AVL_BALANCE     0
 
79
#define AVL_FORW        2
 
80
 
 
81
/*
 
82
 * 'Exported' avl tree routines
 
83
 */
 
84
avl64node_t
 
85
*avl64_insert(
 
86
        avl64tree_desc_t *tree,
 
87
        avl64node_t *newnode);
 
88
 
 
89
void
 
90
avl64_delete(
 
91
        avl64tree_desc_t *tree,
 
92
        avl64node_t *np);
 
93
 
 
94
void
 
95
avl64_insert_immediate(
 
96
        avl64tree_desc_t *tree,
 
97
        avl64node_t *afterp,
 
98
        avl64node_t *newnode);
 
99
        
 
100
void
 
101
avl64_init_tree(
 
102
        avl64tree_desc_t  *tree,
 
103
        avl64ops_t *ops);
 
104
 
 
105
avl64node_t *
 
106
avl64_findrange(
 
107
        avl64tree_desc_t *tree,
 
108
        __uint64_t value);
 
109
 
 
110
avl64node_t *
 
111
avl64_find(
 
112
        avl64tree_desc_t *tree,
 
113
        __uint64_t value);
 
114
 
 
115
avl64node_t *
 
116
avl64_findanyrange(
 
117
        avl64tree_desc_t *tree,
 
118
        __uint64_t      start,
 
119
        __uint64_t      end,
 
120
        int     checklen);
 
121
 
 
122
 
 
123
avl64node_t *
 
124
avl64_findadjacent(
 
125
        avl64tree_desc_t *tree,
 
126
        __uint64_t      value,
 
127
        int             dir);
 
128
 
 
129
void
 
130
avl64_findranges(
 
131
        register avl64tree_desc_t *tree,
 
132
        register __uint64_t     start,
 
133
        register __uint64_t     end,
 
134
        avl64node_t             **startp,
 
135
        avl64node_t             **endp);
 
136
 
 
137
/*
 
138
 * avoid complaints about multiple def's since these are only used by
 
139
 * the avl code internally
 
140
 */
 
141
#ifndef AVL_PRECEED
 
142
#define AVL_PRECEED     0x1
 
143
#define AVL_SUCCEED     0x2
 
144
 
 
145
#define AVL_INCLUDE_ZEROLEN     0x0000
 
146
#define AVL_EXCLUDE_ZEROLEN     0x0001
 
147
#endif
 
148
 
 
149
#endif /* __XR_AVL64_H__ */