chiark - git - mdw - xyla/blob - avl-search.c

   1 /* -*-c-*-
   2  *
   3  * Searching AVL trees
   4  *
   5  * (c) 2024 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Xyla, a library of binary trees.
  11  *
  12  * Xyla is free software: you can redistribute it and/or modify it under
  13  * the terms of the GNU Lesser General Public License as published by the
  14  * Free Software Foundation; either version 3 of the License, or (at your
  15  * option) any later version.
  16  *
  17  * Xyla is distributed in the hope that it will be useful, but WITHOUT
  18  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  19  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  20  * License for more details.
  21  *
  22  * You should have received a copy of the GNU Lesser General Public
  23  * License along with Xyla.  If not, see <https://www.gnu.org/licenses/>.
  24  */
  25
  26 /*----- Header files ------------------------------------------------------*/
  27
  28 #include "lib.h"
  29 #include "avl.h"
  30
  31 /*----- Main code ---------------------------------------------------------*/
  32
  33 void *xyla_avl_lookup(struct xyla_bt_nodecls *cls,
  34                       struct xyla_bt_node **root,
  35                       xyla_bt_navfn *navfn, void *arg)
  36 {
  37   /* Search for a node within the tree rooted at ROOT.  The search is guided
  38    * by NAVFN, passing it ARG at each node.  Return the node that the
  39    * function matches, or null if no matching node exists.
  40    */
  41
  42   struct xyla_bt_node *node;
  43
  44   XYLA_BT_LOOKUP(node, cls, *root, navfn, arg);
  45   return (node);
  46 }
  47
  48 void *xyla_avl_probe(struct xyla_bt_nodecls *cls,
  49                      struct xyla_bt_node **root,
  50                      xyla_bt_navfn *navfn, void *arg,
  51                      struct xyla_avl_path *path)
  52 {
  53   /* Search for a node within the tree rooted at ROOT.  The search is guided
  54    * by NAVFN, passing it ARG at each node.  Record the search path in PATH.
  55    * This can be used later, e.g., by `xyla_avl_insert' to insert a new node
  56    * if none was found, or by `xyla_avl_remove' to remove the node that was
  57    * found.  Return the node that the function matches, or null if no
  58    * matching node exists.
  59    */
  60
  61   struct xyla_bt_node *node;
  62   int rc;
  63
  64   XYLA_BT_PROBE(rc, node, cls, root, navfn, arg,
  65                 path->p, path->k, XYLA_AVL_HTMAX);
  66     XYLA__ASSERT(!rc);
  67   return (node);
  68 }
  69
  70 /*----- That's all, folks -------------------------------------------------*/