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

   1 /* -*-c-*-
   2  *
   3  * Checking 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 /*----- Data structures ---------------------------------------------------*/
  32
  33 struct nodeinfo {
  34   int ht;
  35 };
  36
  37 struct chkstate {
  38   int expht;
  39 };
  40
  41 /*----- Main code ---------------------------------------------------------*/
  42
  43 static int chkavl(unsigned op, const struct xyla_bt_check *chk)
  44 {
  45   /* Check the AVL balance property for a node. */
  46
  47   struct xyla_bt_nodecls *cls = chk->cls;
  48   struct chkstate *st = chk->state;
  49   const struct xyla_avl_node *node;
  50   struct nodeinfo *node_info, *left_info, *right_info;
  51   int ht, lht, rht;
  52   int delta, rc = XYLA_RC_OK;
  53
  54   switch (op) {
  55     case XYLA_CHKOP_AFTER:
  56       node = CONST_AVL_NODE(chk->node);
  57       node_info = chk->node_info;
  58       left_info = chk->left_info; right_info = chk->right_info;
  59       lht = left_info ? left_info->ht : 0;
  60       rht = right_info ? right_info->ht : 0;
  61       if (lht == -1 || rht == -1) { ht = -1; goto skip_htchk; }
  62       switch (node->avl.f&XYLA_AVLF_BALMASK) {
  63         case XYLA_AVLBAL_LBIAS: delta = -1; ht = lht + 1; break;
  64         case XYLA_AVLBAL_EVEN:  delta =  0; ht = lht + 1; break;
  65         case XYLA_AVLBAL_RBIAS: delta = +1; ht = rht + 1; break;
  66         default:
  67           if (chk->fp) {
  68             xyla_bt_bughdr("XYLA-AVL", chk->root, chk->fp);
  69             xyla_bt_printnode(cls, &node->bt, chk->fp);
  70             fprintf(chk->fp, " invalid balance code %u\n",
  71                     (unsigned)(node->avl.f&XYLA_AVLF_BALMASK));
  72           }
  73           ht = -1; rc = XYLA_RC_BAD; goto skip_htchk;
  74       }
  75       if (rht - lht != delta) {
  76         if (chk->fp) {
  77           xyla_bt_bughdr("XYLA-AVL", chk->root, chk->fp);
  78           xyla_bt_printnode(cls, &node->bt, chk->fp);
  79           fprintf(chk->fp, " incorrect balance annotation "
  80                   "`%c' /= left %d - %d right\n",
  81                   AVL_BALCH(node), lht, rht);
  82         }
  83         ht = -1; rc = XYLA_RC_BAD; goto skip_htchk;
  84       }
  85       if (chk->pos == XYLA_BTPOS_ROOT &&
  86           st->expht != -1 && ht != st->expht) {
  87         if (chk->fp) {
  88           xyla_bt_bughdr("XYLA-AVL", chk->root, chk->fp);
  89           fputs("root ", chk->fp);
  90           xyla_bt_printnode(cls, &node->bt, chk->fp);
  91           fprintf(chk->fp, " height %d /= %d expected\n", ht, st->expht);
  92         }
  93         ht = -1; rc = XYLA_RC_BAD; goto skip_htchk;
  94       }
  95     skip_htchk:
  96       node_info->ht = ht;
  97       break;
  98   }
  99   return (rc);
 100 }
 101
 102 int xyla_avl_check(struct xyla_bt_nodecls *cls,
 103                    struct xyla_bt_node *const *root, FILE *fp, unsigned f,
 104                    int expht, void *arg)
 105 {
 106   /* Examine an AVL tree, checking that it satisfies all of the necessary
 107    * invariants.  If EXPHT is not equal to -1, then check that the overall
 108    * tree height is equal to EXPHT.
 109    *
 110    * This function uses the `xyla_bt_check' framework; see the description of
 111    * that function for details.  Returns `XYLA_RC_OK' on success,
 112    * `XYLA_RC_BAD' if problems are found, or some other code if verification
 113    * had to finish prematurely.
 114    */
 115
 116   struct chkstate st;
 117
 118   st.expht = expht;
 119   return (xyla_bt_check(cls, root, fp, f,
 120                         chkavl, sizeof(struct nodeinfo), &st, arg));
 121 }
 122
 123 /*----- That's all, folks -------------------------------------------------*/