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

   1 /* -*-c-*-
   2  *
   3  * Searching splay 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 "splay.h"
  30
  31 /*----- Main code ---------------------------------------------------------*/
  32
  33 void *xyla_splay_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   xyla_bt_updfn *updfn = cls ? cls->ops->upd : 0;
  43   struct xyla_bt_node *node;
  44   struct xyla_splay_path path;
  45
  46   /* Find the node and splay the tree. */
  47   node = xyla_splay_probe(cls, root, navfn, arg, &path);
  48   if (path.node) {
  49     xyla__splay_splay(cls, path.node); *root = &path.node->bt;
  50     if (updfn) updfn(cls, &path.node->bt);
  51   }
  52   return (node);
  53 }
  54
  55 void *xyla_splay_probe(struct xyla_bt_nodecls *cls,
  56                        struct xyla_bt_node **root,
  57                        xyla_bt_navfn *navfn, void *arg,
  58                        struct xyla_splay_path *path)
  59 {
  60   /* Search for a node within the tree rooted at ROOT.  The search is
  61    * guided by NAVFN, passing it ARG at each node.  Record the search
  62    * path in PATH.  This can be used later, e.g., by
  63    * `xyla_splay_insert' to insert a new node if none was found, or by
  64    * `xyla_splay_remove' to remove the node that was found.  Return
  65    * the node that the function matches, or null if no matching node
  66    * exists.
  67    */
  68
  69   const struct xyla_bt_ordops *ops;
  70   struct xyla_splay_node *node, *next;
  71   int dir;
  72
  73   /* If no NAVFN is provided, then see if there's one in the node class. */
  74   if (!navfn) { ops = ORDER_OPS(cls->ops); navfn = ops->ord.nav; }
  75
  76   /* Unsurprisingly, start at the root. */
  77   path->root = root; node = SPLAY_NODE(*root);
  78
  79   if (!node) {
  80     /* If the tree is empty then we have no hope. */
  81
  82     path->node = 0; path->f = 0;
  83   } else {
  84     /* Descend the tree.  If we reach the end, then leave an empty path
  85      * identifying the appropriate null link.
  86      */
  87
  88     for (;;) {
  89       dir = navfn(cls, &node->bt, arg);
  90       if (dir < 0) {
  91         next = SPLAY_NODE(node->bt.left);
  92         if (!next)
  93           { path->node = node; path->f = XYLA_SPF_LEFT; node = 0; break; }
  94       } else if (dir > 0) {
  95         next = SPLAY_NODE(node->bt.right);
  96         if (!next)
  97           { path->node = node; path->f = XYLA_SPF_RIGHT; node = 0; break; }
  98       } else
  99         { path->node = node; path->f = 0; break; }
 100       node = next;
 101     }
 102   }
 103
 104   /* All done. */
 105   return (node);
 106 }
 107
 108 /*----- That's all, folks -------------------------------------------------*/