chiark - git - mdw - xyla/blob - bt-sever.c

   1 /* -*-c-*-
   2  *
   3  * Destructive iteration
   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 "bt.h"
  30
  31 /*----- Main code ---------------------------------------------------------*/
  32
  33 void *xyla_bt_severfirst(struct xyla_bt_node **root)
  34 {
  35   /* Remove and return the first node in the traversal order of the tree
  36    * rooted at *ROOT.  The tree is restructured in a simple way which likely
  37    * invalidates any invariants maintained by the application or balance
  38    * policy, so this is mostly useful if the entire tree is about to be
  39    * destroyed.
  40    */
  41
  42   struct xyla_bt_node *n, *l, *p;
  43
  44   /* This is essentially a destructive iterator over the tree: we record our
  45    * progress through the tree by modifying its links.
  46    */
  47
  48   /* Start with the root node.  If there isn't one, then we're done. */
  49   p = *root; if (!p) return (0);
  50
  51   /* Our focus is on the root's left child. */
  52   n = p->left;
  53
  54   if (!n) {
  55     /* The current root has no left child.  It's therefore the first
  56      * (leftmost) node in the tree.  Detach it, leaving its right child as
  57      * the new tree root.  It's as good a choice as any other.
  58      */
  59
  60     *root = p->right; return (p);
  61   } else {
  62     for (;;) {
  63       /* The current node is the left child of the current tree root. */
  64
  65       l = n->left;
  66       if (!l) {
  67         /* The current node has no left child.  It's therefore the first node
  68          * in the tree.  Detach it, replacing it with its right child.
  69          *
  70          *             p
  71          *               (*)
  72          *       n     /     \                  p
  73          *         (*)                  --->      (*)
  74          *        /   \                         /     \
  75          *     _|_
  76          */
  77
  78         p->left = n->right; *root = p; return (n);
  79       } else {
  80         /* The current node has a left child of it own.  Adjust links to
  81          * promote it to be the new tree root, and move focus to its left
  82          * child.
  83          *
  84          *               p
  85          *                 (*)                       n
  86          *         n     /     \                       (*)
  87          *           (*)                --->   l     /     \     p
  88          *     l    /   \                        (*)         (*)
  89          *       (*)                            /   \       /   \
  90          *      /   \
  91          *
  92          * The old root, and the entire current rightward path, remain on the
  93          * rightward path.  During an iteration, every node is therefore
  94          * promoted in this way at most once (exactly once, except for the
  95          * nodes initially on the rightward path from the original root), and
  96          * the algorithm as a whole runs in amortized linear time.
  97          */
  98
  99         p->left = n->right; n->right = p;
 100         p = n; n = l;
 101       }
 102     }
 103   }
 104 }
 105
 106 /*----- That's all, folks -------------------------------------------------*/