repair/avl.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 __SYS_AVL_H__
  35 #define __SYS_AVL_H__
  36
  37
  38 typedef struct  avlnode {
  39         struct  avlnode *avl_forw;      /* pointer to right child  (> parent) */
  40         struct  avlnode *avl_back;      /* pointer to left child  (< parent) */
  41         struct  avlnode *avl_parent;    /* parent pointer */
  42         struct  avlnode *avl_nextino;   /* next in-order; NULL terminated list*/
  43         char             avl_balance;   /* tree balance */
  44 } avlnode_t;
  45
  46 /*
  47  * avl-tree operations
  48  */
  49 typedef struct avlops {
  50         __psunsigned_t  (*avl_start)(avlnode_t *);
  51         __psunsigned_t  (*avl_end)(avlnode_t *);
  52 } avlops_t;
  53
  54 #define AVL_START(tree, n)      (*(tree)->avl_ops->avl_start)(n)
  55 #define AVL_END(tree, n)        (*(tree)->avl_ops->avl_end)(n)
  56
  57 /*
  58  * tree descriptor:
  59  *      root points to the root of the tree.
  60  *      firstino points to the first in the ordered list.
  61  */
  62 typedef struct avltree_desc {
  63         avlnode_t       *avl_root;
  64         avlnode_t       *avl_firstino;
  65         avlops_t        *avl_ops;
  66         short            avl_flags;
  67 } avltree_desc_t;
  68
  69 /* possible values for avl_balance */
  70
  71 #define AVL_BACK        1
  72 #define AVL_BALANCE     0
  73 #define AVL_FORW        2
  74
  75 /* possible values for avl_flags */
  76
  77 #define AVLF_DUPLICITY  0x0001          /* no warnings on insert dups */
  78
  79 /*
  80  * 'Exported' avl tree routines
  81  */
  82 avlnode_t
  83 *avl_insert(
  84         avltree_desc_t *tree,
  85         avlnode_t *newnode);
  86
  87 void
  88 avl_delete(
  89         avltree_desc_t *tree,
  90         avlnode_t *np);
  91
  92 void
  93 avl_insert_immediate(
  94         avltree_desc_t *tree,
  95         avlnode_t *afterp,
  96         avlnode_t *newnode);
  97
  98 void
  99 avl_init_tree(
 100         avltree_desc_t  *tree,
 101         avlops_t *ops);
 102
 103 avlnode_t *
 104 avl_findrange(
 105         avltree_desc_t *tree,
 106         __psunsigned_t value);
 107
 108 avlnode_t *
 109 avl_find(
 110         avltree_desc_t *tree,
 111         __psunsigned_t value);
 112
 113 avlnode_t *
 114 avl_findanyrange(
 115         avltree_desc_t *tree,
 116         __psunsigned_t start,
 117         __psunsigned_t end,
 118         int     checklen);
 119
 120
 121 avlnode_t *
 122 avl_findadjacent(
 123         avltree_desc_t *tree,
 124         __psunsigned_t value,
 125         int             dir);
 126
 127 void
 128 avl_findranges(
 129         register avltree_desc_t *tree,
 130         register __psunsigned_t start,
 131         register __psunsigned_t end,
 132         avlnode_t               **startp,
 133         avlnode_t               **endp);
 134
 135 #define AVL_PRECEED     0x1
 136 #define AVL_SUCCEED     0x2
 137
 138 #define AVL_INCLUDE_ZEROLEN     0x0000
 139 #define AVL_EXCLUDE_ZEROLEN     0x0001
 140
 141 #endif /* __SYS_AVL_H__ */