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

   1 /* -*-c-*-
   2  *
   3  * Checking treaps
   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 "treap.h"
  30
  31 /*----- Main code ---------------------------------------------------------*/
  32
  33 static int chktreap(unsigned op, const struct xyla_bt_check *chk)
  34 {
  35   /* Check the heap property for a node. */
  36
  37   struct xyla_bt_nodecls *cls = chk->cls;
  38   const struct xyla_treap_node *node, *parent;
  39   int rc = XYLA_RC_OK;
  40
  41   switch (op) {
  42     case XYLA_CHKOP_BEFORE:
  43       if (chk->pos != XYLA_BTPOS_ROOT) {
  44         node = CONST_TREAP_NODE(chk->node);
  45         parent = CONST_TREAP_NODE(chk->parent);
  46         if (parent->trp.wt > node->trp.wt) {
  47           if (chk->fp) {
  48             xyla_bt_bughdr("XYLA-TREAP", chk->root, chk->fp);
  49             xyla_bt_printnode(cls, &node->bt, chk->fp);
  50             fprintf(chk->fp, " weight %lu < %lu weight of parent ",
  51                     (unsigned long)node->trp.wt,
  52                     (unsigned long)parent->trp.wt);
  53             xyla_bt_printnode(cls, &parent->bt, chk->fp);
  54             fputc('\n', chk->fp);
  55           }
  56           rc = XYLA_RC_BAD;
  57         }
  58       }
  59       break;
  60   }
  61   return (rc);
  62 }
  63
  64 int xyla_treap_check(struct xyla_bt_nodecls *cls,
  65                      struct xyla_bt_node *const *root, FILE *fp, unsigned f,
  66                      void *arg)
  67 {
  68   /* Examine a treap, checking that it satisfies all of the necessary
  69    * invariants.
  70    *
  71    * This function uses the `xyla_bt_check' framework; see the description of
  72    * that function for details.  Returns `XYLA_RC_OK' on success,
  73    * `XYLA_RC_BAD' if problems are found, or some other code if verification
  74    * had to finish prematurely.
  75    */
  76
  77   return (xyla_bt_check(cls, root, fp, f, chktreap, 0, 0, arg));
  78 }
  79
  80 /*----- That's all, folks -------------------------------------------------*/