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__ */