install-reloc: Support multi-binary installation.
[gnulib.git] / lib / gl_rbtree_oset.c
index 5e74fc7..9393d12 100644 (file)
@@ -1,11 +1,11 @@
 /* Ordered set data type implemented by a binary tree.
-   Copyright (C) 2006 Free Software Foundation, Inc.
+   Copyright (C) 2006-2007, 2009-2013 Free Software Foundation, Inc.
    Written by Bruno Haible <bruno@clisp.org>, 2006.
 
-   This program is free software; you can redistribute it and/or modify
+   This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
-   the Free Software Foundation; either version 2, or (at your option)
-   any later version.
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
 
    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
@@ -13,8 +13,7 @@
    GNU General Public License for more details.
 
    You should have received a copy of the GNU General Public License
-   along with this program; if not, write to the Free Software Foundation,
-   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
 
 #include <config.h>
 
@@ -23,8 +22,6 @@
 
 #include <stdlib.h>
 
-#include "xalloc.h"
-
 /* A red-black tree is a binary tree where every node is colored black or
    red such that
    1. The root is black.
@@ -35,7 +32,7 @@
    Let's call this the "black-height" bh of the tree.  It follows that every
    such path contains exactly bh black and between 0 and bh red nodes.  (The
    extreme cases are a path containing only black nodes, and a path colored
-   alternatingly black-red-black-red-...-black-red.)  The height of the tree
+   alternately black-red-black-red-...-black-red.)  The height of the tree
    therefore is >= bh, <= 2*bh.
  */
 
@@ -77,15 +74,15 @@ struct gl_oset_impl
 
 /* Rotate left a subtree.
 
-                        B                         D
-                      /   \                     /   \
-                    A       D       -->       B       E
-                           / \               / \
-                          C   E             A   C
+                         B                         D
+                       /   \                     /   \
+                     A       D       -->       B       E
+                            / \               / \
+                           C   E             A   C
 
    Change the tree structure, update the branch sizes.
    The caller must update the colors and register D as child of its parent.  */
-static inline gl_oset_node_t
+static gl_oset_node_t
 rotate_left (gl_oset_node_t b_node, gl_oset_node_t d_node)
 {
   gl_oset_node_t c_node = d_node->left;
@@ -103,15 +100,15 @@ rotate_left (gl_oset_node_t b_node, gl_oset_node_t d_node)
 
 /* Rotate right a subtree.
 
-                          D                     B
-                        /   \                 /   \
-                      B       E     -->     A       D
-                     / \                           / \
-                    A   C                         C   E
+                           D                     B
+                         /   \                 /   \
+                       B       E     -->     A       D
+                      / \                           / \
+                     A   C                         C   E
 
    Change the tree structure, update the branch sizes.
    The caller must update the colors and register B as child of its parent.  */
-static inline gl_oset_node_t
+static gl_oset_node_t
 rotate_right (gl_oset_node_t b_node, gl_oset_node_t d_node)
 {
   gl_oset_node_t c_node = b_node->right;
@@ -136,118 +133,118 @@ rebalance_after_add (gl_oset_t set, gl_oset_node_t node, gl_oset_node_t parent)
   for (;;)
     {
       /* At this point, parent = node->parent != NULL.
-        Think of node->color being RED (although node->color is not yet
-        assigned.)  */
+         Think of node->color being RED (although node->color is not yet
+         assigned.)  */
       gl_oset_node_t grandparent;
       gl_oset_node_t uncle;
 
       if (parent->color == BLACK)
-       {
-         /* A RED color for node is acceptable.  */
-         node->color = RED;
-         return;
-       }
+        {
+          /* A RED color for node is acceptable.  */
+          node->color = RED;
+          return;
+        }
 
       grandparent = parent->parent;
       /* Since parent is RED, we know that
-        grandparent is != NULL and colored BLACK.  */
+         grandparent is != NULL and colored BLACK.  */
 
       if (grandparent->left == parent)
-       uncle = grandparent->right;
+        uncle = grandparent->right;
       else if (grandparent->right == parent)
-       uncle = grandparent->left;
+        uncle = grandparent->left;
       else
-       abort ();
+        abort ();
 
       if (uncle != NULL && uncle->color == RED)
-       {
-         /* Change grandparent from BLACK to RED, and
-            change parent and uncle from RED to BLACK.
-            This makes it acceptable for node to be RED.  */
-         node->color = RED;
-         parent->color = uncle->color = BLACK;
-         node = grandparent;
-       }
+        {
+          /* Change grandparent from BLACK to RED, and
+             change parent and uncle from RED to BLACK.
+             This makes it acceptable for node to be RED.  */
+          node->color = RED;
+          parent->color = uncle->color = BLACK;
+          node = grandparent;
+        }
       else
-       {
-         /* grandparent and uncle are BLACK.  parent is RED.  node wants
-            to be RED too.
-            In this case, recoloring is not sufficient.  Need to perform
-            one or two rotations.  */
-         gl_oset_node_t *grandparentp;
-
-         if (grandparent->parent == NULL)
-           grandparentp = &set->root;
-         else if (grandparent->parent->left == grandparent)
-           grandparentp = &grandparent->parent->left;
-         else if (grandparent->parent->right == grandparent)
-           grandparentp = &grandparent->parent->right;
-         else
-           abort ();
-
-         if (grandparent->left == parent)
-           {
-             if (parent->right == node)
-               {
-                 /* Rotation between node and parent.  */
-                 grandparent->left = rotate_left (parent, node);
-                 node = parent;
-                 parent = grandparent->left;
-               }
-             /* grandparent and uncle are BLACK.  parent and node want to be
-                RED.  parent = grandparent->left.  node = parent->left.
-
-                     grandparent              parent
-                        bh+1                   bh+1
-                        /   \                 /   \
-                    parent  uncle    -->   node  grandparent
-                     bh      bh             bh      bh
-                     / \                           / \
-                  node  C                         C  uncle
-                   bh   bh                       bh    bh
-              */
-             *grandparentp = rotate_right (parent, grandparent);
-             parent->color = BLACK;
-             node->color = grandparent->color = RED;
-           }
-         else /* grandparent->right == parent */
-           {
-             if (parent->left == node)
-               {
-                 /* Rotation between node and parent.  */
-                 grandparent->right = rotate_right (node, parent);
-                 node = parent;
-                 parent = grandparent->right;
-               }
-             /* grandparent and uncle are BLACK.  parent and node want to be
-                RED.  parent = grandparent->right.  node = parent->right.
-
-                   grandparent                    parent
-                      bh+1                         bh+1
-                      /   \                       /   \
-                  uncle  parent     -->   grandparent  node
-                    bh     bh                  bh       bh
-                           / \                 / \
-                          C  node          uncle  C
-                         bh   bh            bh    bh
-              */
-             *grandparentp = rotate_left (grandparent, parent);
-             parent->color = BLACK;
-             node->color = grandparent->color = RED;
-           }
-         return;
-       }
+        {
+          /* grandparent and uncle are BLACK.  parent is RED.  node wants
+             to be RED too.
+             In this case, recoloring is not sufficient.  Need to perform
+             one or two rotations.  */
+          gl_oset_node_t *grandparentp;
+
+          if (grandparent->parent == NULL)
+            grandparentp = &set->root;
+          else if (grandparent->parent->left == grandparent)
+            grandparentp = &grandparent->parent->left;
+          else if (grandparent->parent->right == grandparent)
+            grandparentp = &grandparent->parent->right;
+          else
+            abort ();
+
+          if (grandparent->left == parent)
+            {
+              if (parent->right == node)
+                {
+                  /* Rotation between node and parent.  */
+                  grandparent->left = rotate_left (parent, node);
+                  node = parent;
+                  parent = grandparent->left;
+                }
+              /* grandparent and uncle are BLACK.  parent and node want to be
+                 RED.  parent = grandparent->left.  node = parent->left.
+
+                      grandparent              parent
+                         bh+1                   bh+1
+                         /   \                 /   \
+                     parent  uncle    -->   node  grandparent
+                      bh      bh             bh      bh
+                      / \                           / \
+                   node  C                         C  uncle
+                    bh   bh                       bh    bh
+               */
+              *grandparentp = rotate_right (parent, grandparent);
+              parent->color = BLACK;
+              node->color = grandparent->color = RED;
+            }
+          else /* grandparent->right == parent */
+            {
+              if (parent->left == node)
+                {
+                  /* Rotation between node and parent.  */
+                  grandparent->right = rotate_right (node, parent);
+                  node = parent;
+                  parent = grandparent->right;
+                }
+              /* grandparent and uncle are BLACK.  parent and node want to be
+                 RED.  parent = grandparent->right.  node = parent->right.
+
+                    grandparent                    parent
+                       bh+1                         bh+1
+                       /   \                       /   \
+                   uncle  parent     -->   grandparent  node
+                     bh     bh                  bh       bh
+                            / \                 / \
+                           C  node          uncle  C
+                          bh   bh            bh    bh
+               */
+              *grandparentp = rotate_left (grandparent, parent);
+              parent->color = BLACK;
+              node->color = grandparent->color = RED;
+            }
+          return;
+        }
 
       /* Start again with a new (node, parent) pair.  */
       parent = node->parent;
 
       if (parent == NULL)
-       {
-         /* Change node's color from RED to BLACK.  This increases the
-            tree's black-height.  */
-         node->color = BLACK;
-         return;
-       }
+        {
+          /* Change node's color from RED to BLACK.  This increases the
+             tree's black-height.  */
+          node->color = BLACK;
+          return;
+        }
     }
 }
 
@@ -261,288 +258,292 @@ rebalance_after_remove (gl_oset_t set, gl_oset_node_t child, gl_oset_node_t pare
   for (;;)
     {
       /* At this point, we reduced the black-height of the CHILD subtree by 1.
-        To make up, either look for a possibility to turn a RED to a BLACK
-        node, or try to reduce the black-height tree of CHILD's sibling
-        subtree as well.  */
+         To make up, either look for a possibility to turn a RED to a BLACK
+         node, or try to reduce the black-height tree of CHILD's sibling
+         subtree as well.  */
       gl_oset_node_t *parentp;
 
       if (parent->parent == NULL)
-       parentp = &set->root;
+        parentp = &set->root;
       else if (parent->parent->left == parent)
-       parentp = &parent->parent->left;
+        parentp = &parent->parent->left;
       else if (parent->parent->right == parent)
-       parentp = &parent->parent->right;
+        parentp = &parent->parent->right;
       else
-       abort ();
+        abort ();
 
       if (parent->left == child)
-       {
-         gl_oset_node_t sibling = parent->right;
-         /* sibling's black-height is >= 1.  In particular,
-            sibling != NULL.
-
-                     parent
-                      /   \
-                  child  sibling
-                    bh    bh+1
-          */
-
-         if (sibling->color == RED)
-           {
-             /* sibling is RED, hence parent is BLACK and sibling's children
-                are non-NULL and BLACK.
-
-                     parent                       sibling
-                      bh+2                         bh+2
-                      /   \                        /   \
-                  child  sibling     -->       parent    SR
-                    bh    bh+1                  bh+1    bh+1
-                           / \                  / \
-                         SL   SR            child  SL
-                        bh+1 bh+1             bh  bh+1
-              */
-             *parentp = rotate_left (parent, sibling);
-             parent->color = RED;
-             sibling->color = BLACK;
-
-             /* Concentrate on the subtree of parent.  The new sibling is
-                one of the old sibling's children, and known to be BLACK.  */
-             parentp = &sibling->left;
-             sibling = parent->right;
-           }
-         /* Now we know that sibling is BLACK.
-
-                     parent
-                      /   \
-                  child  sibling
-                    bh    bh+1
-          */
-         if (sibling->right != NULL && sibling->right->color == RED)
-           {
-             /*
-                     parent                     sibling
-                    bh+1|bh+2                  bh+1|bh+2
-                      /   \                      /   \
-                  child  sibling    -->      parent    SR
-                    bh    bh+1                bh+1    bh+1
-                           / \                / \
-                         SL   SR           child  SL
-                         bh   bh             bh   bh
-              */
-             *parentp = rotate_left (parent, sibling);
-             sibling->color = parent->color;
-             parent->color = BLACK;
-             sibling->right->color = BLACK;
-             return;
-           }
-         else if (sibling->left != NULL && sibling->left->color == RED)
-           {
-             /*
-                     parent                   parent
-                    bh+1|bh+2                bh+1|bh+2
-                      /   \                    /   \
-                  child  sibling    -->    child    SL
-                    bh    bh+1               bh    bh+1
-                           / \                     /  \
-                         SL   SR                 SLL  sibling
-                         bh   bh                 bh     bh
-                        /  \                           /   \
-                      SLL  SLR                       SLR    SR
-                      bh    bh                       bh     bh
-
-                where SLL, SLR, SR are all black.
-              */
-             parent->right = rotate_right (sibling->left, sibling);
-             /* Change sibling from BLACK to RED and SL from RED to BLACK.  */
-             sibling->color = RED;
-             sibling = parent->right;
-             sibling->color = BLACK;
-
-             /* Now do as in the previous case.  */
-             *parentp = rotate_left (parent, sibling);
-             sibling->color = parent->color;
-             parent->color = BLACK;
-             sibling->right->color = BLACK;
-             return;
-           }
-         else
-           {
-             if (parent->color == BLACK)
-               {
-                 /* Change sibling from BLACK to RED.  Then the entire
-                    subtree at parent has decreased its black-height.
-                             parent                   parent
-                              bh+2                     bh+1
-                              /   \                    /   \
-                          child  sibling    -->    child  sibling
-                            bh    bh+1               bh     bh
-                  */
-                 sibling->color = RED;
-
-                 child = parent;
-               }
-             else
-               {
-                 /* Change parent from RED to BLACK, but compensate by
-                    changing sibling from BLACK to RED.
-                             parent                   parent
-                              bh+1                     bh+1
-                              /   \                    /   \
-                          child  sibling    -->    child  sibling
-                            bh    bh+1               bh     bh
-                  */
-                 parent->color = BLACK;
-                 sibling->color = RED;
-                 return;
-               }
-           }
-       }
+        {
+          gl_oset_node_t sibling = parent->right;
+          /* sibling's black-height is >= 1.  In particular,
+             sibling != NULL.
+
+                      parent
+                       /   \
+                   child  sibling
+                     bh    bh+1
+           */
+
+          if (sibling->color == RED)
+            {
+              /* sibling is RED, hence parent is BLACK and sibling's children
+                 are non-NULL and BLACK.
+
+                      parent                       sibling
+                       bh+2                         bh+2
+                       /   \                        /   \
+                   child  sibling     -->       parent    SR
+                     bh    bh+1                  bh+1    bh+1
+                            / \                  / \
+                          SL   SR            child  SL
+                         bh+1 bh+1             bh  bh+1
+               */
+              *parentp = rotate_left (parent, sibling);
+              parent->color = RED;
+              sibling->color = BLACK;
+
+              /* Concentrate on the subtree of parent.  The new sibling is
+                 one of the old sibling's children, and known to be BLACK.  */
+              parentp = &sibling->left;
+              sibling = parent->right;
+            }
+          /* Now we know that sibling is BLACK.
+
+                      parent
+                       /   \
+                   child  sibling
+                     bh    bh+1
+           */
+          if (sibling->right != NULL && sibling->right->color == RED)
+            {
+              /*
+                      parent                     sibling
+                     bh+1|bh+2                  bh+1|bh+2
+                       /   \                      /   \
+                   child  sibling    -->      parent    SR
+                     bh    bh+1                bh+1    bh+1
+                            / \                / \
+                          SL   SR           child  SL
+                          bh   bh             bh   bh
+               */
+              *parentp = rotate_left (parent, sibling);
+              sibling->color = parent->color;
+              parent->color = BLACK;
+              sibling->right->color = BLACK;
+              return;
+            }
+          else if (sibling->left != NULL && sibling->left->color == RED)
+            {
+              /*
+                      parent                   parent
+                     bh+1|bh+2                bh+1|bh+2
+                       /   \                    /   \
+                   child  sibling    -->    child    SL
+                     bh    bh+1               bh    bh+1
+                            / \                     /  \
+                          SL   SR                 SLL  sibling
+                          bh   bh                 bh     bh
+                         /  \                           /   \
+                       SLL  SLR                       SLR    SR
+                       bh    bh                       bh     bh
+
+                 where SLL, SLR, SR are all black.
+               */
+              parent->right = rotate_right (sibling->left, sibling);
+              /* Change sibling from BLACK to RED and SL from RED to BLACK.  */
+              sibling->color = RED;
+              sibling = parent->right;
+              sibling->color = BLACK;
+
+              /* Now do as in the previous case.  */
+              *parentp = rotate_left (parent, sibling);
+              sibling->color = parent->color;
+              parent->color = BLACK;
+              sibling->right->color = BLACK;
+              return;
+            }
+          else
+            {
+              if (parent->color == BLACK)
+                {
+                  /* Change sibling from BLACK to RED.  Then the entire
+                     subtree at parent has decreased its black-height.
+                              parent                   parent
+                               bh+2                     bh+1
+                               /   \                    /   \
+                           child  sibling    -->    child  sibling
+                             bh    bh+1               bh     bh
+                   */
+                  sibling->color = RED;
+
+                  child = parent;
+                }
+              else
+                {
+                  /* Change parent from RED to BLACK, but compensate by
+                     changing sibling from BLACK to RED.
+                              parent                   parent
+                               bh+1                     bh+1
+                               /   \                    /   \
+                           child  sibling    -->    child  sibling
+                             bh    bh+1               bh     bh
+                   */
+                  parent->color = BLACK;
+                  sibling->color = RED;
+                  return;
+                }
+            }
+        }
       else if (parent->right == child)
-       {
-         gl_oset_node_t sibling = parent->left;
-         /* sibling's black-height is >= 1.  In particular,
-            sibling != NULL.
-
-                     parent
-                      /   \
-                 sibling  child
-                   bh+1     bh
-          */
-
-         if (sibling->color == RED)
-           {
-             /* sibling is RED, hence parent is BLACK and sibling's children
-                are non-NULL and BLACK.
-
-                     parent                 sibling
-                      bh+2                    bh+2
-                      /   \                  /   \
-                 sibling  child    -->     SR    parent
-                   bh+1     ch            bh+1    bh+1
-                   / \                            / \
-                 SL   SR                        SL  child
-                bh+1 bh+1                      bh+1   bh
-              */
-             *parentp = rotate_right (sibling, parent);
-             parent->color = RED;
-             sibling->color = BLACK;
-
-             /* Concentrate on the subtree of parent.  The new sibling is
-                one of the old sibling's children, and known to be BLACK.  */
-             parentp = &sibling->right;
-             sibling = parent->left;
-           }
-         /* Now we know that sibling is BLACK.
-
-                     parent
-                      /   \
-                 sibling  child
-                   bh+1     bh
-          */
-         if (sibling->left != NULL && sibling->left->color == RED)
-           {
-             /*
-                      parent                 sibling
-                     bh+1|bh+2              bh+1|bh+2
-                       /   \                  /   \
-                  sibling  child    -->     SL   parent
-                    bh+1     bh            bh+1   bh+1
-                    / \                           / \
-                  SL   SR                       SR  child
-                  bh   bh                       bh    bh
-              */
-             *parentp = rotate_right (sibling, parent);
-             sibling->color = parent->color;
-             parent->color = BLACK;
-             sibling->left->color = BLACK;
-             return;
-           }
-         else if (sibling->right != NULL && sibling->right->color == RED)
-           {
-             /*
-                     parent                       parent
-                    bh+1|bh+2                    bh+1|bh+2
-                      /   \                        /   \
-                  sibling  child    -->          SR    child
-                   bh+1      bh                 bh+1     bh
-                    / \                         /  \
-                  SL   SR                  sibling  SRR
-                  bh   bh                    bh      bh
-                      /  \                  /   \
-                    SRL  SRR               SL   SRL
-                    bh    bh               bh    bh
-
-                where SL, SRL, SRR are all black.
-              */
-             parent->left = rotate_left (sibling, sibling->right);
-             /* Change sibling from BLACK to RED and SL from RED to BLACK.  */
-             sibling->color = RED;
-             sibling = parent->left;
-             sibling->color = BLACK;
-
-             /* Now do as in the previous case.  */
-             *parentp = rotate_right (sibling, parent);
-             sibling->color = parent->color;
-             parent->color = BLACK;
-             sibling->left->color = BLACK;
-             return;
-           }
-         else
-           {
-             if (parent->color == BLACK)
-               {
-                 /* Change sibling from BLACK to RED.  Then the entire
-                    subtree at parent has decreased its black-height.
-                             parent                   parent
-                              bh+2                     bh+1
-                              /   \                    /   \
-                          sibling  child    -->    sibling  child
-                           bh+1      bh              bh       bh
-                  */
-                 sibling->color = RED;
-
-                 child = parent;
-               }
-             else
-               {
-                 /* Change parent from RED to BLACK, but compensate by
-                    changing sibling from BLACK to RED.
-                             parent                   parent
-                              bh+1                     bh+1
-                              /   \                    /   \
-                          sibling  child    -->    sibling  child
-                           bh+1      bh              bh       bh
-                  */
-                 parent->color = BLACK;
-                 sibling->color = RED;
-                 return;
-               }
-           }
-       }
+        {
+          gl_oset_node_t sibling = parent->left;
+          /* sibling's black-height is >= 1.  In particular,
+             sibling != NULL.
+
+                      parent
+                       /   \
+                  sibling  child
+                    bh+1     bh
+           */
+
+          if (sibling->color == RED)
+            {
+              /* sibling is RED, hence parent is BLACK and sibling's children
+                 are non-NULL and BLACK.
+
+                      parent                 sibling
+                       bh+2                    bh+2
+                       /   \                  /   \
+                  sibling  child    -->     SR    parent
+                    bh+1     ch            bh+1    bh+1
+                    / \                            / \
+                  SL   SR                        SL  child
+                 bh+1 bh+1                      bh+1   bh
+               */
+              *parentp = rotate_right (sibling, parent);
+              parent->color = RED;
+              sibling->color = BLACK;
+
+              /* Concentrate on the subtree of parent.  The new sibling is
+                 one of the old sibling's children, and known to be BLACK.  */
+              parentp = &sibling->right;
+              sibling = parent->left;
+            }
+          /* Now we know that sibling is BLACK.
+
+                      parent
+                       /   \
+                  sibling  child
+                    bh+1     bh
+           */
+          if (sibling->left != NULL && sibling->left->color == RED)
+            {
+              /*
+                       parent                 sibling
+                      bh+1|bh+2              bh+1|bh+2
+                        /   \                  /   \
+                   sibling  child    -->     SL   parent
+                     bh+1     bh            bh+1   bh+1
+                     / \                           / \
+                   SL   SR                       SR  child
+                   bh   bh                       bh    bh
+               */
+              *parentp = rotate_right (sibling, parent);
+              sibling->color = parent->color;
+              parent->color = BLACK;
+              sibling->left->color = BLACK;
+              return;
+            }
+          else if (sibling->right != NULL && sibling->right->color == RED)
+            {
+              /*
+                      parent                       parent
+                     bh+1|bh+2                    bh+1|bh+2
+                       /   \                        /   \
+                   sibling  child    -->          SR    child
+                    bh+1      bh                 bh+1     bh
+                     / \                         /  \
+                   SL   SR                  sibling  SRR
+                   bh   bh                    bh      bh
+                       /  \                  /   \
+                     SRL  SRR               SL   SRL
+                     bh    bh               bh    bh
+
+                 where SL, SRL, SRR are all black.
+               */
+              parent->left = rotate_left (sibling, sibling->right);
+              /* Change sibling from BLACK to RED and SL from RED to BLACK.  */
+              sibling->color = RED;
+              sibling = parent->left;
+              sibling->color = BLACK;
+
+              /* Now do as in the previous case.  */
+              *parentp = rotate_right (sibling, parent);
+              sibling->color = parent->color;
+              parent->color = BLACK;
+              sibling->left->color = BLACK;
+              return;
+            }
+          else
+            {
+              if (parent->color == BLACK)
+                {
+                  /* Change sibling from BLACK to RED.  Then the entire
+                     subtree at parent has decreased its black-height.
+                              parent                   parent
+                               bh+2                     bh+1
+                               /   \                    /   \
+                           sibling  child    -->    sibling  child
+                            bh+1      bh              bh       bh
+                   */
+                  sibling->color = RED;
+
+                  child = parent;
+                }
+              else
+                {
+                  /* Change parent from RED to BLACK, but compensate by
+                     changing sibling from BLACK to RED.
+                              parent                   parent
+                               bh+1                     bh+1
+                               /   \                    /   \
+                           sibling  child    -->    sibling  child
+                            bh+1      bh              bh       bh
+                   */
+                  parent->color = BLACK;
+                  sibling->color = RED;
+                  return;
+                }
+            }
+        }
       else
-       abort ();
+        abort ();
 
       /* Start again with a new (child, parent) pair.  */
       parent = child->parent;
 
 #if 0 /* Already handled.  */
       if (child != NULL && child->color == RED)
-       {
-         child->color = BLACK;
-         return;
-       }
+        {
+          child->color = BLACK;
+          return;
+        }
 #endif
 
       if (parent == NULL)
-       return;
+        return;
     }
 }
 
 static gl_oset_node_t
-gl_tree_add_first (gl_oset_t set, const void *elt)
+gl_tree_nx_add_first (gl_oset_t set, const void *elt)
 {
   /* Create new node.  */
-  gl_oset_node_t new_node = XMALLOC (struct gl_oset_node_impl);
+  gl_oset_node_t new_node =
+    (struct gl_oset_node_impl *) malloc (sizeof (struct gl_oset_node_impl));
+
+  if (new_node == NULL)
+    return NULL;
 
   new_node->left = NULL;
   new_node->right = NULL;
@@ -560,7 +561,7 @@ gl_tree_add_first (gl_oset_t set, const void *elt)
       gl_oset_node_t node;
 
       for (node = set->root; node->left != NULL; )
-       node = node->left;
+        node = node->left;
 
       node->left = new_node;
       new_node->parent = node;
@@ -574,10 +575,14 @@ gl_tree_add_first (gl_oset_t set, const void *elt)
 }
 
 static gl_oset_node_t
-gl_tree_add_before (gl_oset_t set, gl_oset_node_t node, const void *elt)
+gl_tree_nx_add_before (gl_oset_t set, gl_oset_node_t node, const void *elt)
 {
   /* Create new node.  */
-  gl_oset_node_t new_node = XMALLOC (struct gl_oset_node_impl);
+  gl_oset_node_t new_node =
+    (struct gl_oset_node_impl *) malloc (sizeof (struct gl_oset_node_impl));
+
+  if (new_node == NULL)
+    return NULL;
 
   new_node->left = NULL;
   new_node->right = NULL;
@@ -589,7 +594,7 @@ gl_tree_add_before (gl_oset_t set, gl_oset_node_t node, const void *elt)
   else
     {
       for (node = node->left; node->right != NULL; )
-       node = node->right;
+        node = node->right;
       node->right = new_node;
     }
   new_node->parent = node;
@@ -602,10 +607,14 @@ gl_tree_add_before (gl_oset_t set, gl_oset_node_t node, const void *elt)
 }
 
 static gl_oset_node_t
-gl_tree_add_after (gl_oset_t set, gl_oset_node_t node, const void *elt)
+gl_tree_nx_add_after (gl_oset_t set, gl_oset_node_t node, const void *elt)
 {
   /* Create new node.  */
-  gl_oset_node_t new_node = XMALLOC (struct gl_oset_node_impl);
+  gl_oset_node_t new_node =
+    (struct gl_oset_node_impl *) malloc (sizeof (struct gl_oset_node_impl));
+
+  if (new_node == NULL)
+    return NULL;
 
   new_node->left = NULL;
   new_node->right = NULL;
@@ -617,7 +626,7 @@ gl_tree_add_after (gl_oset_t set, gl_oset_node_t node, const void *elt)
   else
     {
       for (node = node->right; node->left != NULL; )
-       node = node->left;
+        node = node->left;
       node->left = new_node;
     }
   new_node->parent = node;
@@ -640,45 +649,45 @@ gl_tree_remove_node (gl_oset_t set, gl_oset_node_t node)
       gl_oset_node_t child = node->right;
 
       if (child != NULL)
-       {
-         child->parent = parent;
-         /* Since node->left == NULL, child must be RED and of height 1,
-            hence node must have been BLACK.  Recolor the child.  */
-         child->color = BLACK;
-       }
+        {
+          child->parent = parent;
+          /* Since node->left == NULL, child must be RED and of height 1,
+             hence node must have been BLACK.  Recolor the child.  */
+          child->color = BLACK;
+        }
       if (parent == NULL)
-       set->root = child;
+        set->root = child;
       else
-       {
-         if (parent->left == node)
-           parent->left = child;
-         else /* parent->right == node */
-           parent->right = child;
-
-         if (child == NULL && node->color == BLACK)
-           rebalance_after_remove (set, child, parent);
-       }
+        {
+          if (parent->left == node)
+            parent->left = child;
+          else /* parent->right == node */
+            parent->right = child;
+
+          if (child == NULL && node->color == BLACK)
+            rebalance_after_remove (set, child, parent);
+        }
     }
   else if (node->right == NULL)
     {
       /* It is not absolutely necessary to treat this case.  But the more
-        general case below is more complicated, hence slower.  */
+         general case below is more complicated, hence slower.  */
       /* Replace node with node->left.  */
       gl_oset_node_t child = node->left;
 
       child->parent = parent;
       /* Since node->right == NULL, child must be RED and of height 1,
-        hence node must have been BLACK.  Recolor the child.  */
+         hence node must have been BLACK.  Recolor the child.  */
       child->color = BLACK;
       if (parent == NULL)
-       set->root = child;
+        set->root = child;
       else
-       {
-         if (parent->left == node)
-           parent->left = child;
-         else /* parent->right == node */
-           parent->right = child;
-       }
+        {
+          if (parent->left == node)
+            parent->left = child;
+          else /* parent->right == node */
+            parent->right = child;
+        }
     }
   else
     {
@@ -689,7 +698,7 @@ gl_tree_remove_node (gl_oset_t set, gl_oset_node_t node)
       color_t removed_color;
 
       for (subst = node->left; subst->right != NULL; )
-       subst = subst->right;
+        subst = subst->right;
 
       subst_parent = subst->parent;
 
@@ -698,57 +707,59 @@ gl_tree_remove_node (gl_oset_t set, gl_oset_node_t node)
       removed_color = subst->color;
 
       /* The case subst_parent == node is special:  If we do nothing special,
-        we get confusion about node->left, subst->left and child->parent.
-          subst_parent == node
-          <==> The 'for' loop above terminated immediately.
-          <==> subst == subst_parent->left
-               [otherwise subst == subst_parent->right]
-        In this case, we would need to first set
-          child->parent = node; node->left = child;
-        and later - when we copy subst into node's position - again
-          child->parent = subst; subst->left = child;
-        Altogether a no-op.  */
+         we get confusion about node->left, subst->left and child->parent.
+           subst_parent == node
+           <==> The 'for' loop above terminated immediately.
+           <==> subst == subst_parent->left
+                [otherwise subst == subst_parent->right]
+         In this case, we would need to first set
+           child->parent = node; node->left = child;
+         and later - when we copy subst into node's position - again
+           child->parent = subst; subst->left = child;
+         Altogether a no-op.  */
       if (subst_parent != node)
-       {
-         if (child != NULL)
-           child->parent = subst_parent;
-         subst_parent->right = child;
-       }
+        {
+          if (child != NULL)
+            child->parent = subst_parent;
+          subst_parent->right = child;
+        }
 
       /* Copy subst into node's position.
-        (This is safer than to copy subst's value into node, keep node in
-        place, and free subst.)  */
+         (This is safer than to copy subst's value into node, keep node in
+         place, and free subst.)  */
       if (subst_parent != node)
-       {
-         subst->left = node->left;
-         subst->left->parent = subst;
-       }
+        {
+          subst->left = node->left;
+          subst->left->parent = subst;
+        }
       subst->right = node->right;
       subst->right->parent = subst;
       subst->color = node->color;
       subst->parent = parent;
       if (parent == NULL)
-       set->root = subst;
+        set->root = subst;
       else if (parent->left == node)
-       parent->left = subst;
+        parent->left = subst;
       else /* parent->right == node */
-       parent->right = subst;
+        parent->right = subst;
 
       if (removed_color == BLACK)
-       {
-         if (child != NULL && child->color == RED)
-           /* Recolor the child.  */
-           child->color = BLACK;
-         else
-           /* Rebalancing starts at child's parent, that is subst_parent -
-              except when subst_parent == node.  In this case, we need to use
-              its replacement, subst.  */
-           rebalance_after_remove (set, child,
-                                   subst_parent != node ? subst_parent : subst);
-       }
+        {
+          if (child != NULL && child->color == RED)
+            /* Recolor the child.  */
+            child->color = BLACK;
+          else
+            /* Rebalancing starts at child's parent, that is subst_parent -
+               except when subst_parent == node.  In this case, we need to use
+               its replacement, subst.  */
+            rebalance_after_remove (set, child,
+                                    subst_parent != node ? subst_parent : subst);
+        }
     }
 
   set->count--;
+  if (set->base.dispose_fn != NULL)
+    set->base.dispose_fn (node->value);
   free (node);
   return true;
 }
@@ -790,11 +801,11 @@ gl_rbtree_oset_check_invariants (gl_oset_t set)
 
 const struct gl_oset_implementation gl_rbtree_oset_implementation =
   {
-    gl_tree_create_empty,
+    gl_tree_nx_create_empty,
     gl_tree_size,
     gl_tree_search,
     gl_tree_search_atleast,
-    gl_tree_add,
+    gl_tree_nx_add,
     gl_tree_remove,
     gl_tree_oset_free,
     gl_tree_iterator,