chiark - git - mdw - xyla/blob - rb-misc.c

   1 /* -*-c-*-
   2  *
   3  * Miscellaneous operations for red-black 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 "rb.h"
  30
  31 /*----- Main code ---------------------------------------------------------*/
  32
  33 int xyla_rb_height(const struct xyla_rb_node *node)
  34 {
  35   /* Return the `black height' -- the number of black nodes on every path
  36    * from root to leaf -- for the (sub)tree rooted at NODE.  This is
  37    * primarily useful as input to `xyla_rb_join' and `xyla_rb_split'.
  38    */
  39
  40   int blkht = 0;
  41
  42   while (node) {
  43     if (!(node->rb.f&XYLA_RBF_RED)) blkht++;
  44     node = CONST_RB_NODE(node->bt.left);
  45   }
  46   return (blkht);
  47 }
  48
  49 /*----- That's all, folks -------------------------------------------------*/