libfrog/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 __LIBFROG_AVL64_H__
   7 #define __LIBFROG_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 avl64node_t *
  73 avl64_firstino(avl64node_t *root);
  74
  75 avl64node_t *
  76 avl64_lastino(avl64node_t *root);
  77
  78 void
  79 avl64_init_tree(
  80         avl64tree_desc_t  *tree,
  81         avl64ops_t *ops);
  82
  83 avl64node_t *
  84 avl64_findrange(
  85         avl64tree_desc_t *tree,
  86         uint64_t value);
  87
  88 avl64node_t *
  89 avl64_find(
  90         avl64tree_desc_t *tree,
  91         uint64_t value);
  92
  93 avl64node_t *
  94 avl64_findanyrange(
  95         avl64tree_desc_t *tree,
  96         uint64_t        start,
  97         uint64_t        end,
  98         int     checklen);
  99
 100
 101 avl64node_t *
 102 avl64_findadjacent(
 103         avl64tree_desc_t *tree,
 104         uint64_t        value,
 105         int             dir);
 106
 107 void
 108 avl64_findranges(
 109         avl64tree_desc_t *tree,
 110         uint64_t        start,
 111         uint64_t        end,
 112         avl64node_t             **startp,
 113         avl64node_t             **endp);
 114
 115 /*
 116  * avoid complaints about multiple def's since these are only used by
 117  * the avl code internally
 118  */
 119 #ifndef AVL_PRECEED
 120 #define AVL_PRECEED     0x1
 121 #define AVL_SUCCEED     0x2
 122
 123 #define AVL_INCLUDE_ZEROLEN     0x0000
 124 #define AVL_EXCLUDE_ZEROLEN     0x0001
 125 #endif
 126
 127 #endif /* __LIBFROG_AVL64_H__ */