repair/avl.h

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
   4  * All Rights Reserved.
   5  */
   6 #ifndef __SYS_AVL_H__
   7 #define __SYS_AVL_H__
   8
   9
  10 typedef struct  avlnode {
  11         struct  avlnode *avl_forw;      /* pointer to right child  (> parent) */
  12         struct  avlnode *avl_back;      /* pointer to left child  (< parent) */
  13         struct  avlnode *avl_parent;    /* parent pointer */
  14         struct  avlnode *avl_nextino;   /* next in-order; NULL terminated list*/
  15         char             avl_balance;   /* tree balance */
  16 } avlnode_t;
  17
  18 /*
  19  * avl-tree operations
  20  */
  21 typedef struct avlops {
  22         uintptr_t       (*avl_start)(avlnode_t *);
  23         uintptr_t       (*avl_end)(avlnode_t *);
  24 } avlops_t;
  25
  26 #define AVL_START(tree, n)      (*(tree)->avl_ops->avl_start)(n)
  27 #define AVL_END(tree, n)        (*(tree)->avl_ops->avl_end)(n)
  28
  29 /*
  30  * tree descriptor:
  31  *      root points to the root of the tree.
  32  *      firstino points to the first in the ordered list.
  33  */
  34 typedef struct avltree_desc {
  35         avlnode_t       *avl_root;
  36         avlnode_t       *avl_firstino;
  37         avlops_t        *avl_ops;
  38         short            avl_flags;
  39 } avltree_desc_t;
  40
  41 /* possible values for avl_balance */
  42
  43 #define AVL_BACK        1
  44 #define AVL_BALANCE     0
  45 #define AVL_FORW        2
  46
  47 /* possible values for avl_flags */
  48
  49 #define AVLF_DUPLICITY  0x0001          /* no warnings on insert dups */
  50
  51 /*
  52  * 'Exported' avl tree routines
  53  */
  54 avlnode_t
  55 *avl_insert(
  56         avltree_desc_t *tree,
  57         avlnode_t *newnode);
  58
  59 void
  60 avl_delete(
  61         avltree_desc_t *tree,
  62         avlnode_t *np);
  63
  64 void
  65 avl_insert_immediate(
  66         avltree_desc_t *tree,
  67         avlnode_t *afterp,
  68         avlnode_t *newnode);
  69
  70 void
  71 avl_init_tree(
  72         avltree_desc_t  *tree,
  73         avlops_t *ops);
  74
  75 static inline avlnode_t *
  76 avl_findrange(
  77         avltree_desc_t *tree,
  78         uintptr_t value)
  79 {
  80         avlnode_t *np = tree->avl_root;
  81
  82         while (np) {
  83                 if (value < AVL_START(tree, np)) {
  84                         np = np->avl_back;
  85                         continue;
  86                 }
  87                 if (value >= AVL_END(tree, np)) {
  88                         np = np->avl_forw;
  89                         continue;
  90                 }
  91                 ASSERT(AVL_START(tree, np) <= value &&
  92                        value < AVL_END(tree, np));
  93                 return np;
  94         }
  95         return NULL;
  96 }
  97
  98 avlnode_t *
  99 avl_find(
 100         avltree_desc_t *tree,
 101         uintptr_t value);
 102
 103 avlnode_t *
 104 avl_findanyrange(
 105         avltree_desc_t *tree,
 106         uintptr_t start,
 107         uintptr_t end,
 108         int     checklen);
 109
 110
 111 avlnode_t *
 112 avl_findadjacent(
 113         avltree_desc_t *tree,
 114         uintptr_t value,
 115         int             dir);
 116
 117 void
 118 avl_findranges(
 119         avltree_desc_t *tree,
 120         uintptr_t start,
 121         uintptr_t end,
 122         avlnode_t               **startp,
 123         avlnode_t               **endp);
 124
 125 avlnode_t *
 126 avl_firstino(
 127         avlnode_t               *root);
 128
 129 avlnode_t *
 130 avl_lastino(
 131         avlnode_t               *root);
 132
 133
 134 #define AVL_PRECEED     0x1
 135 #define AVL_SUCCEED     0x2
 136
 137 #define AVL_INCLUDE_ZEROLEN     0x0000
 138 #define AVL_EXCLUDE_ZEROLEN     0x0001
 139
 140 #endif /* __SYS_AVL_H__ */