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

   1 /* -*-c-*-
   2  *
   3  * Iteration for 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 /* Iteration doesn't work like the other trees in this library, because we
  34  * have parent pointers.  Instead, the `iterator' simply keeps track of the
  35  * /next/ node to return.
  36  */
  37
  38 #define INITITER(root, it, back) do {                                   \
  39   const struct xyla_splay_node *_next = CONST_SPLAY_NODE(root), *_nnext; \
  40                                                                         \
  41   /* Initialize the `next' node to the backmost node in the tree. */    \
  42   if (!_next)                                                           \
  43     (it)->top = 0;                                                      \
  44   else {                                                                \
  45     (it)->top = _next->spl.parent;                                      \
  46     for (;;) {                                                          \
  47       _nnext = CONST_SPLAY_NODE(_next->bt.back); if (!_nnext) break;    \
  48       _next = _nnext;                                                   \
  49     }                                                                   \
  50   }                                                                     \
  51   (it)->next = _next;                                                   \
  52 } while (0)
  53
  54 #define NEXT(node, it, fwd, back) do {                                  \
  55   const struct xyla_splay_node *_node, *_next, *_nnext, *_old;          \
  56                                                                         \
  57   /* The next node to return is just the one recorded in the            \
  58    * iterator.                                                          \
  59    */                                                                   \
  60   _node = (it)->next;                                                   \
  61                                                                         \
  62   /* Now advance the iterator to the /next/ node.  There are two cases  \
  63    * to consider.                                                       \
  64    */                                                                   \
  65   if (_node) {                                                          \
  66     _next = CONST_SPLAY_NODE(_node->bt.fwd);                            \
  67     if (_next)                                                          \
  68       /* The node's forward subtree is non-empty.  The next node is the \
  69        * backmode node in the forward subtree.                          \
  70        */                                                               \
  71                                                                         \
  72       for (;;) {                                                        \
  73         _nnext = CONST_SPLAY_NODE(_next->bt.back);                      \
  74         if (!_nnext) break;                                             \
  75         _next = _nnext;                                                 \
  76       }                                                                 \
  77     else {                                                              \
  78       /* The forward subtree is empty.  The next node is the most       \
  79        * recent ancestor that we descend from through a backward link.  \
  80        * If there is no such ancestor then the iteration concludes      \
  81        * here.                                                          \
  82        */                                                               \
  83                                                                         \
  84       _next = _node;                                                    \
  85       do { _old = _next; _next = _old->spl.parent; }                    \
  86       while (_next != (it)->top && &_old->bt == _next->bt.fwd);         \
  87     }                                                                   \
  88     (it)->next = _next;                                                 \
  89   }                                                                     \
  90   (node) = _node;                                                       \
  91 } while (0)
  92
  93 void xyla_splay_inititer(const struct xyla_bt_node *root,
  94                          struct xyla_splay_iter *it)
  95 {
  96   /* Initialize the iterator IT to start returning nodes in right-to-left
  97    * order from the tree rooted at ROOT.
  98    */
  99
 100   INITITER(root, it, left);
 101 }
 102
 103 void *xyla_splay_next(struct xyla_splay_iter *it)
 104 {
 105   /* Advances a tree iterator.  Inserting or removing elements does /not/
 106    * invalidate the iterator.  It is permitted to free all of the nodes by
 107    * iterating over the tree in the obvious manner:
 108    *
 109    *    xyla_splay_inititer(tree, &it);
 110    *    for (;;) {
 111    *      node = xyla_splay_next(&it); if (!node) break;
 112    *      free(node);
 113    *    }
 114    *
 115    * It's probably better to use `xyla_bt_severfirst' for this task.
 116    */
 117
 118   const struct xyla_splay_node *node;
 119   NEXT(node, it, right, left); return (UNCONST(void, node));
 120 }
 121
 122 void xyla_splay_initriter(const struct xyla_bt_node *root,
 123                           struct xyla_splay_riter *rit)
 124 {
 125   /* Initialize the iterator RIT to start returning nodes in left-to-right
 126    * order from the tree rooted at ROOT.
 127    */
 128
 129   INITITER(root, rit, right);
 130 }
 131
 132 void *xyla_splay_prev(struct xyla_splay_riter *rit)
 133 {
 134   /* Advances a tree iterator.  Inserting or removing elements does /not/
 135    * invalidate the iterator.  It is permitted to free all of the nodes by
 136    * iterating over the tree in the obvious manner:
 137    *
 138    *    xyla_splay_inititer(tree, &rit);
 139    *    for (;;) {
 140    *      node = xyla_splay_next(&rit); if (!node) break;
 141    *      free(node);
 142    *    }
 143    *
 144    * It's probably better to use `xyla_bt_severfirst' for this task.
 145    */
 146
 147   const struct xyla_splay_node *node;
 148   NEXT(node, rit, left, right); return (UNCONST(void, node));
 149 }
 150
 151 /*----- That's all, folks -------------------------------------------------*/