include/avl64.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 __XR_AVL64_H__
   7 #define __XR_AVL64_H__
   8
   9 #include <sys/types.h>
  10
  11 typedef struct  avl64node {
  12         struct  avl64node       *avl_forw;      /* pointer to right child  (> parent) */
  13         struct  avl64node *avl_back;    /* pointer to left child  (< parent) */
  14         struct  avl64node *avl_parent;  /* parent pointer */
  15         struct  avl64node *avl_nextino; /* next in-order; NULL terminated list*/
  16         char             avl_balance;   /* tree balance */
  17 } avl64node_t;
  18
  19 /*
  20  * avl-tree operations
  21  */
  22 typedef struct avl64ops {
  23         uint64_t        (*avl_start)(avl64node_t *);
  24         uint64_t        (*avl_end)(avl64node_t *);
  25 } avl64ops_t;
  26
  27 /*
  28  * avoid complaints about multiple def's since these are only used by
  29  * the avl code internally
  30  */
  31 #ifndef AVL_START
  32 #define AVL_START(tree, n)      (*(tree)->avl_ops->avl_start)(n)
  33 #define AVL_END(tree, n)        (*(tree)->avl_ops->avl_end)(n)
  34 #endif
  35
  36 /*
  37  * tree descriptor:
  38  *      root points to the root of the tree.
  39  *      firstino points to the first in the ordered list.
  40  */
  41 typedef struct avl64tree_desc {
  42         avl64node_t     *avl_root;
  43         avl64node_t     *avl_firstino;
  44         avl64ops_t      *avl_ops;
  45 } avl64tree_desc_t;
  46
  47 /* possible values for avl_balance */
  48
  49 #define AVL_BACK        1
  50 #define AVL_BALANCE     0
  51 #define AVL_FORW        2
  52
  53 /*
  54  * 'Exported' avl tree routines
  55  */
  56 avl64node_t
  57 *avl64_insert(
  58         avl64tree_desc_t *tree,
  59         avl64node_t *newnode);
  60
  61 void
  62 avl64_delete(
  63         avl64tree_desc_t *tree,
  64         avl64node_t *np);
  65
  66 void
  67 avl64_insert_immediate(
  68         avl64tree_desc_t *tree,
  69         avl64node_t *afterp,
  70         avl64node_t *newnode);
  71
  72 void
  73 avl64_init_tree(
  74         avl64tree_desc_t  *tree,
  75         avl64ops_t *ops);
  76
  77 avl64node_t *
  78 avl64_findrange(
  79         avl64tree_desc_t *tree,
  80         uint64_t value);
  81
  82 avl64node_t *
  83 avl64_find(
  84         avl64tree_desc_t *tree,
  85         uint64_t value);
  86
  87 avl64node_t *
  88 avl64_findanyrange(
  89         avl64tree_desc_t *tree,
  90         uint64_t        start,
  91         uint64_t        end,
  92         int     checklen);
  93
  94
  95 avl64node_t *
  96 avl64_findadjacent(
  97         avl64tree_desc_t *tree,
  98         uint64_t        value,
  99         int             dir);
 100
 101 void
 102 avl64_findranges(
 103         avl64tree_desc_t *tree,
 104         uint64_t        start,
 105         uint64_t        end,
 106         avl64node_t             **startp,
 107         avl64node_t             **endp);
 108
 109 /*
 110  * avoid complaints about multiple def's since these are only used by
 111  * the avl code internally
 112  */
 113 #ifndef AVL_PRECEED
 114 #define AVL_PRECEED     0x1
 115 #define AVL_SUCCEED     0x2
 116
 117 #define AVL_INCLUDE_ZEROLEN     0x0000
 118 #define AVL_EXCLUDE_ZEROLEN     0x0001
 119 #endif
 120
 121 #endif /* __XR_AVL64_H__ */