include/avl64.h

   1 /*
   2  * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
   3  * All Rights Reserved.
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms 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,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write the Free Software Foundation,
  16  * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  17  */
  18 #ifndef __XR_AVL64_H__
  19 #define __XR_AVL64_H__
  20
  21 #include <sys/types.h>
  22
  23 typedef struct  avl64node {
  24         struct  avl64node       *avl_forw;      /* pointer to right child  (> parent) */
  25         struct  avl64node *avl_back;    /* pointer to left child  (< parent) */
  26         struct  avl64node *avl_parent;  /* parent pointer */
  27         struct  avl64node *avl_nextino; /* next in-order; NULL terminated list*/
  28         char             avl_balance;   /* tree balance */
  29 } avl64node_t;
  30
  31 /*
  32  * avl-tree operations
  33  */
  34 typedef struct avl64ops {
  35         uint64_t        (*avl_start)(avl64node_t *);
  36         uint64_t        (*avl_end)(avl64node_t *);
  37 } avl64ops_t;
  38
  39 /*
  40  * avoid complaints about multiple def's since these are only used by
  41  * the avl code internally
  42  */
  43 #ifndef AVL_START
  44 #define AVL_START(tree, n)      (*(tree)->avl_ops->avl_start)(n)
  45 #define AVL_END(tree, n)        (*(tree)->avl_ops->avl_end)(n)
  46 #endif
  47
  48 /*
  49  * tree descriptor:
  50  *      root points to the root of the tree.
  51  *      firstino points to the first in the ordered list.
  52  */
  53 typedef struct avl64tree_desc {
  54         avl64node_t     *avl_root;
  55         avl64node_t     *avl_firstino;
  56         avl64ops_t      *avl_ops;
  57 } avl64tree_desc_t;
  58
  59 /* possible values for avl_balance */
  60
  61 #define AVL_BACK        1
  62 #define AVL_BALANCE     0
  63 #define AVL_FORW        2
  64
  65 /*
  66  * 'Exported' avl tree routines
  67  */
  68 avl64node_t
  69 *avl64_insert(
  70         avl64tree_desc_t *tree,
  71         avl64node_t *newnode);
  72
  73 void
  74 avl64_delete(
  75         avl64tree_desc_t *tree,
  76         avl64node_t *np);
  77
  78 void
  79 avl64_insert_immediate(
  80         avl64tree_desc_t *tree,
  81         avl64node_t *afterp,
  82         avl64node_t *newnode);
  83
  84 void
  85 avl64_init_tree(
  86         avl64tree_desc_t  *tree,
  87         avl64ops_t *ops);
  88
  89 avl64node_t *
  90 avl64_findrange(
  91         avl64tree_desc_t *tree,
  92         uint64_t value);
  93
  94 avl64node_t *
  95 avl64_find(
  96         avl64tree_desc_t *tree,
  97         uint64_t value);
  98
  99 avl64node_t *
 100 avl64_findanyrange(
 101         avl64tree_desc_t *tree,
 102         uint64_t        start,
 103         uint64_t        end,
 104         int     checklen);
 105
 106
 107 avl64node_t *
 108 avl64_findadjacent(
 109         avl64tree_desc_t *tree,
 110         uint64_t        value,
 111         int             dir);
 112
 113 void
 114 avl64_findranges(
 115         avl64tree_desc_t *tree,
 116         uint64_t        start,
 117         uint64_t        end,
 118         avl64node_t             **startp,
 119         avl64node_t             **endp);
 120
 121 /*
 122  * avoid complaints about multiple def's since these are only used by
 123  * the avl code internally
 124  */
 125 #ifndef AVL_PRECEED
 126 #define AVL_PRECEED     0x1
 127 #define AVL_SUCCEED     0x2
 128
 129 #define AVL_INCLUDE_ZEROLEN     0x0000
 130 #define AVL_EXCLUDE_ZEROLEN     0x0001
 131 #endif
 132
 133 #endif /* __XR_AVL64_H__ */