faux/lub/bintree/bintree_insert.c

/*********************** -*- Mode: C -*- ***********************
 * File            : bintree_insert.c
 *---------------------------------------------------------------
 * Description
 * ===========
 * This operation adds a client node to the specified tree.
 *
 * tree       - the "tree" instance to invoke this operation upon
 * clientnode - a pointer to a client node. NB the tree can find the
 *              necessary util_BintreeNodeT from it's stored offset.
 *
 * RETURNS
 * 0 if the "clientnode" is added correctly to the tree.
 * 
 * If another "clientnode" already exists in the tree with the same key, then
 * -1 is returned, and the tree remains unchanged.
 *
 * If the "clientnode" had not been initialised, then an assert will fire.
 * 
 * If the bintree "node" is already part of a tree, then an assert will fire.
 *
 *---------------------------------------------------------------
 * Author          : Graeme McKerrell
 * Created On      : Wed Jan 28 10:05:11 2004
 * Status          : TESTED
 *---------------------------------------------------------------
 * HISTORY
 * 7-Dec-2004		Graeme McKerrell	
 *    Renamed to the "lub_" namespace
 * 5-May-2004		Graeme McKerrell	
 *    updates following review
 * 2-Mar-2004		Graeme McKerrell	
 *    fixed so that the insertion order is correct
 * 9-Feb-2004		Graeme McKerrell	
 *    updated to use the new getkey prototype and new node, key ordering
 * 28-Jan-2004		Graeme McKerrell	
 *    Initial version
 *---------------------------------------------------------------
 * Copyright (C) 2004 3Com Corporation. All Rights Reserved.
 **************************************************************** */
#include <assert.h>
#include "private.h"

/*--------------------------------------------------------- */
int lub_bintree_insert(lub_bintree_t * this, void *clientnode)
{
	int result = -1;
	lub_bintree_node_t *new;
	lub_bintree_key_t key;

	assert(clientnode);
	if (NULL != clientnode) {
		/* obtain the control block from the clientnode */
		new = lub_bintree_getnode(this, clientnode);

		/* check this node is not currently in another tree */
		assert(new->left == NULL);
		assert(new->right == NULL);

		/* add this node to the splay tree */

		/* Insert "node" into the tree , unless it's already there. */
		if (NULL == this->root) {
			this->root = new;
			this->root->left = this->root->right = NULL;
			result = 0;
		} else {
			int comp;
			/* get a key from the node */
			this->getkeyFn(clientnode, &key);

			/* do the biz */
			this->root = lub_bintree_splay(this, this->root, &key);

			/*
			 * compare the new key with the detail found
			 * in the tree
			 */
			comp = lub_bintree_compare(this, this->root, &key);
			if (comp > 0) {
				new->left = this->root->left;
				new->right = this->root;
				this->root->left = NULL;
				result = 0;
			} else if (comp < 0) {
				new->right = this->root->right;
				new->left = this->root;
				this->root->right = NULL;
				result = 0;
			} else {
				/* We get here if it's already in the tree */
			}
		}
		if (0 == result) {
			/* update the tree root */
			this->root = new;
		}
	}
	/* added OK */
	return result;
}

/*--------------------------------------------------------- */