1 /*********************** -*- Mode: C -*- ***********************
2 * File : bintree_insert.c
3 *---------------------------------------------------------------
4 * Description
5 * ===========
6 * This operation adds a client node to the specified tree.
7 *
8 * tree - the "tree" instance to invoke this operation upon
9 * clientnode - a pointer to a client node. NB the tree can find the
10 * necessary util_BintreeNodeT from it's stored offset.
11 *
12 * RETURNS
13 * 0 if the "clientnode" is added correctly to the tree.
14 *
15 * If another "clientnode" already exists in the tree with the same key, then
16 * -1 is returned, and the tree remains unchanged.
17 *
18 * If the "clientnode" had not been initialised, then an assert will fire.
19 *
20 * If the bintree "node" is already part of a tree, then an assert will fire.
21 *
22 *---------------------------------------------------------------
23 * Author : Graeme McKerrell
24 * Created On : Wed Jan 28 10:05:11 2004
25 * Status : TESTED
26 *---------------------------------------------------------------
27 * HISTORY
28 * 7-Dec-2004 Graeme McKerrell
29 * Renamed to the "lub_" namespace
30 * 5-May-2004 Graeme McKerrell
31 * updates following review
32 * 2-Mar-2004 Graeme McKerrell
33 * fixed so that the insertion order is correct
34 * 9-Feb-2004 Graeme McKerrell
35 * updated to use the new getkey prototype and new node, key ordering
36 * 28-Jan-2004 Graeme McKerrell
37 * Initial version
38 *---------------------------------------------------------------
39 * Copyright (C) 2004 3Com Corporation. All Rights Reserved.
40 **************************************************************** */
41 #include <assert.h>
42 #include "private.h"
43
44 /*--------------------------------------------------------- */
lub_bintree_insert(lub_bintree_t * this,void * clientnode)45 int lub_bintree_insert(lub_bintree_t * this, void *clientnode)
46 {
47 int result = -1;
48 lub_bintree_node_t *new;
49 lub_bintree_key_t key;
50
51 assert(clientnode);
52 if (NULL != clientnode) {
53 /* obtain the control block from the clientnode */
54 new = lub_bintree_getnode(this, clientnode);
55
56 /* check this node is not currently in another tree */
57 assert(new->left == NULL);
58 assert(new->right == NULL);
59
60 /* add this node to the splay tree */
61
62 /* Insert "node" into the tree , unless it's already there. */
63 if (NULL == this->root) {
64 this->root = new;
65 this->root->left = this->root->right = NULL;
66 result = 0;
67 } else {
68 int comp;
69 /* get a key from the node */
70 this->getkeyFn(clientnode, &key);
71
72 /* do the biz */
73 this->root = lub_bintree_splay(this, this->root, &key);
74
75 /*
76 * compare the new key with the detail found
77 * in the tree
78 */
79 comp = lub_bintree_compare(this, this->root, &key);
80 if (comp > 0) {
81 new->left = this->root->left;
82 new->right = this->root;
83 this->root->left = NULL;
84 result = 0;
85 } else if (comp < 0) {
86 new->right = this->root->right;
87 new->left = this->root;
88 this->root->right = NULL;
89 result = 0;
90 } else {
91 /* We get here if it's already in the tree */
92 }
93 }
94 if (0 == result) {
95 /* update the tree root */
96 this->root = new;
97 }
98 }
99 /* added OK */
100 return result;
101 }
102
103 /*--------------------------------------------------------- */
104