1 /*********************** -*- Mode: C -*- ***********************
2 * File : bintree_remove.c
3 *---------------------------------------------------------------
4 * Description
5 * ===========
6 * This operation removes a "node" from the specified "tree"
7 *
8 * tree - the "tree" instance to invoke this operation upon
9 * clientnode - the node to remove
10 *
11 * RETURNS
12 * none
13 *
14 * POST CONDITIONS
15 * The "node" will no longer be part of the specified tree, and can be
16 * subsequently re-inserted
17 *
18 * If the node is not present in the specified tree, then an assert
19 * will fire.
20 *---------------------------------------------------------------
21 * Author : Graeme McKerrell
22 * Created On : Wed Jan 28 10:06:58 2004
23 * Status : TESTED
24 *---------------------------------------------------------------
25 * HISTORY
26 * 27-Dec-2004 Graeme McKerrell
27 * added assert to catch removal of invalid node
28 * 7-Dec-2004 Graeme McKerrell
29 * Renamed to the "lub_" namespace
30 * 5-May-2004 Graeme McKerrell
31 * updates following review
32 * 23-Mar-2004 Graeme McKerrell
33 * fixed to ensure that control block is re-initialised.
34 * 16-Mar-2004 Graeme McKerrell
35 * removed assert.
36 * 27-Feb-2004 Graeme McKerrell
37 * removed spurious call to node_init
38 * 9-Feb-2004 Graeme McKerrell
39 * updated to use new node,key comparison ordering
40 * 28-Jan-2004 Graeme McKerrell
41 * Initial version
42 *---------------------------------------------------------------
43 * Copyright (C) 2004 3Com Corporation. All Rights Reserved.
44 **************************************************************** */
45 #include <assert.h>
46
47 #include "private.h"
48
49 /*--------------------------------------------------------- */
lub_bintree_remove(lub_bintree_t * this,void * clientnode)50 void lub_bintree_remove(lub_bintree_t * this, void *clientnode)
51 {
52 lub_bintree_node_t *x, *t;
53 lub_bintree_key_t key;
54 int comp;
55
56 /* get the key from the node */
57 this->getkeyFn(clientnode, &key);
58
59 /* bring the node in question to the root of the tree */
60 t = lub_bintree_splay(this, this->root, &key);
61
62 /* check that the node was there to remove */
63 comp = lub_bintree_compare(this, t, &key);
64
65 assert(0 == comp);
66 if (0 == comp) {
67 if (t->left == NULL) {
68 x = t->right;
69 } else {
70 x = lub_bintree_splay(this, t->left, &key);
71 x->right = t->right;
72 }
73 /* set the new root */
74 this->root = x;
75
76 /* re-initialise the node control block for re-use */
77 lub_bintree_node_init(lub_bintree_getnode(this, clientnode));
78 }
79 }
80
81 /*--------------------------------------------------------- */
82