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

   1 /* -*-c-*-
   2  *
   3  * Iteration for 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_inititer(const struct xyla_bt_node *root,
  34                        struct xyla_avl_iter *it)
  35 {
  36   /* Initialize the iterator IT to start returning nodes in left-to-right
  37    * order from the tree rooted at ROOT.
  38    */
  39
  40   int rc;
  41
  42   it->sp = 0;
  43   XYLA_BT_STEPITER(rc, root, it->stack, it->sp, XYLA_AVL_HTMAX, left);
  44     XYLA__ASSERT(!rc);
  45 }
  46
  47 void *xyla_avl_next(struct xyla_avl_iter *it)
  48 {
  49   /* Advance the iterator IT, returning the next node, or null if the
  50    * iteration is complete.
  51    *
  52    * Inserting or removing elements invalidates the iterator.  As a special
  53    * exception, it is permitted to free all of the nodes by iterating over
  54    * the tree in the obvious manner:
  55    *
  56    *    xyla_avl_inititer(tree, &it);
  57    *    for (;;) {
  58    *      node = xyla_avl_next(&it); if (!node) break;
  59    *      free(node);
  60    *    }
  61    *
  62    * It's probably better to use `xyla_bt_severfirst' for this task.
  63    */
  64
  65   const struct xyla_bt_node *node;
  66   int rc, sp = it->sp;
  67
  68   if (!sp) return (0);
  69   node = it->stack[--sp];
  70   XYLA_BT_STEPITER(rc, node->right, it->stack, sp, XYLA_AVL_HTMAX, left);
  71     XYLA__ASSERT(!rc);
  72   it->sp = sp; return (UNCONST(void, node));
  73 }
  74
  75 void xyla_avl_initriter(const struct xyla_bt_node *root,
  76                         struct xyla_avl_riter *rit)
  77 {
  78   /* Initialize the iterator RIT to start returning nodes in right-to-left
  79    * order from the tree rooted at ROOT.
  80    */
  81
  82   int rc;
  83
  84   rit->sp = 0;
  85   XYLA_BT_STEPITER(rc, root, rit->stack, rit->sp, XYLA_AVL_HTMAX, right);
  86     XYLA__ASSERT(!rc);
  87 }
  88
  89 void *xyla_avl_prev(struct xyla_avl_riter *rit)
  90 {
  91   /* Advance the iterator RIT, returning the previous node, or null if the
  92    * iteration is complete.
  93    *
  94    * Inserting or removing elements invalidates the iterator.  As a special
  95    * exception, it is permitted to free all of the nodes by iterating over
  96    * the tree in the obvious manner:
  97    *
  98    *    xyla_avl_initriter(tree, &rit);
  99    *    for (;;) {
 100    *      node = xyla_avl_prev(&it); if (!node) break;
 101    *      free(node);
 102    *    }
 103    *
 104    * It's probably better to use `xyla_bt_severfirst' for this task.
 105    */
 106
 107   const struct xyla_bt_node *node;
 108   int rc, sp = rit->sp;
 109
 110   if (!sp) return (0);
 111   node = rit->stack[--sp];
 112   XYLA_BT_STEPITER(rc, node->left, rit->stack, sp, XYLA_AVL_HTMAX, right);
 113     XYLA__ASSERT(!rc);
 114   rit->sp = sp; return (UNCONST(void, node));
 115 }
 116
 117 /*----- That's all, folks -------------------------------------------------*/