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

   1 /* -*-c-*-
   2  *
   3  * Checking 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 static int chksplay(unsigned op, const struct xyla_bt_check *chk)
  34 {
  35   /* Check the parent link for a node. */
  36
  37   struct xyla_bt_nodecls *cls = chk->cls;
  38   const struct xyla_splay_node *node;
  39   const struct xyla_bt_node *parent;
  40   int rc = XYLA_RC_OK;
  41
  42   switch (op) {
  43     case XYLA_CHKOP_AFTER:
  44       node = CONST_SPLAY_NODE(chk->node);
  45       parent = node->spl.parent ? &node->spl.parent->bt : 0;
  46       if (chk->pos == XYLA_BTPOS_ROOT) {
  47         if (parent) {
  48           if (chk->fp) {
  49             xyla_bt_bughdr("XYLA-SPLAY", chk->root, chk->fp);
  50             fputs("root ", chk->fp);
  51             xyla_bt_printnode(cls, &node->bt, chk->fp);
  52             fputs(" non-nil parent link ", chk->fp);
  53             xyla_bt_printnode(cls, parent, chk->fp);
  54             fputc('\n', chk->fp);
  55           }
  56           rc = XYLA_RC_BAD;
  57         }
  58       } else {
  59         if (parent != chk->parent) {
  60           if (chk->fp) {
  61             xyla_bt_bughdr("XYLA-SPLAY", chk->root, chk->fp);
  62             fputs("internal ", chk->fp);
  63             xyla_bt_printnode(cls, &node->bt, chk->fp);
  64             fputs(" incorrect parent ", chk->fp);
  65             xyla_bt_printnode(cls, parent, chk->fp);
  66             fputc('\n', chk->fp);
  67           }
  68           rc = XYLA_RC_BAD;
  69         }
  70       }
  71       break;
  72   }
  73   return (rc);
  74 }
  75
  76 int xyla_splay_check(struct xyla_bt_nodecls *cls,
  77                      struct xyla_bt_node *const *root, FILE *fp, unsigned f,
  78                      void *arg)
  79 {
  80   /* Examine a splay tree, checking that it satisfies all of the necessary
  81    * invariants.  A splay tree has no special structural invariants: splay
  82    * trees are characterized by the algorithms that act on them, rather than
  83    * their static structure.  But we do need to check the parent links.
  84    *
  85    * This function uses the `xyla_bt_check' framework; see the description of
  86    * that function for details.  Returns `XYLA_RC_OK' on success,
  87    * `XYLA_RC_BAD' if problems are found, or some other code if verification
  88    * had to finish prematurely.
  89    */
  90
  91   return (xyla_bt_check(cls, root, fp, f, chksplay, 0, 0, arg));
  92 }
  93
  94 /*----- That's all, folks -------------------------------------------------*/