faux/lub/bintree/bintree_remove.c

/*********************** -*- Mode: C -*- ***********************
 * File            : bintree_remove.c
 *---------------------------------------------------------------
 * Description
 * ===========
 * This operation removes a "node" from the specified "tree"
 *
 * tree       - the "tree" instance to invoke this operation upon
 * clientnode - the node to remove
 *
 * RETURNS
 *   none
 *
 * POST CONDITIONS
 * The "node" will no longer be part of the specified tree, and can be
 * subsequently re-inserted
 *
 * If the node is not present in the specified tree, then an assert
 * will fire.
 *---------------------------------------------------------------
 * Author          : Graeme McKerrell
 * Created On      : Wed Jan 28 10:06:58 2004
 * Status          : TESTED
 *---------------------------------------------------------------
 * HISTORY
 * 27-Dec-2004		Graeme McKerrell	
 *    added assert to catch removal of invalid node 
 * 7-Dec-2004		Graeme McKerrell	
 *    Renamed to the "lub_" namespace
  * 5-May-2004		Graeme McKerrell	
 *    updates following review
 * 23-Mar-2004		Graeme McKerrell	
 *    fixed to ensure that control block is re-initialised.
 * 16-Mar-2004		Graeme McKerrell	
 *    removed assert.
 * 27-Feb-2004		Graeme McKerrell	
 *    removed spurious call to node_init
 * 9-Feb-2004		Graeme McKerrell	
 *    updated to use new node,key comparison ordering
 * 28-Jan-2004		Graeme McKerrell	
 *    Initial version
 *---------------------------------------------------------------
 * Copyright (C) 2004 3Com Corporation. All Rights Reserved.
 **************************************************************** */
#include <assert.h>

#include "private.h"

/*--------------------------------------------------------- */
void
lub_bintree_remove(lub_bintree_t *this,
                   void          *clientnode)
{
    lub_bintree_node_t *x,*t;
    lub_bintree_key_t   key;
    int                 comp;

    /* get the key from the node */
    this->getkeyFn(clientnode,&key);

    /* bring the node in question to the root of the tree */
    t = lub_bintree_splay(this,this->root,&key);

    /* check that the node was there to remove */
    comp = lub_bintree_compare(this,t,&key);

    assert(0 == comp);
    if(0 == comp)
    {
        if (t->left == NULL)
        {
            x = t->right;
        }
        else
        {
            x        = lub_bintree_splay(this,t->left,&key);
            x->right = t->right;
        }
        /* set the new root */
        this->root  = x;

        /* re-initialise the node control block for re-use */
        lub_bintree_node_init(lub_bintree_getnode(this,clientnode));
    }
}
/*--------------------------------------------------------- */