[Libsysio-commit] HEAD: libsysio/src tree.c module.mk

[Lee W. <lw...@us...>]

Update of /cvsroot/libsysio/libsysio/src
In directory sc8-pr-cvs6.sourceforge.net:/tmp/cvs-serv32383/src

Modified Files:
	module.mk 
Added Files:
	tree.c 
Log Message:


Add support for in-memory binary tree abstraction, supporting the core.


--- NEW FILE ---
/*
 *    This Cplant(TM) source code is the property of Sandia National
 *    Laboratories.
 *
 *    This Cplant(TM) source code is copyrighted by Sandia National
 *    Laboratories.
 *
 *    The redistribution of this Cplant(TM) source code is subject to the
 *    terms of the GNU Lesser General Public License
 *    (see cit/LGPL or http://www.gnu.org/licenses/lgpl.html)
 *
 *    Cplant(TM) Copyright 1998-2007 Sandia Corporation. 
 *    Under the terms of Contract DE-AC04-94AL85000, there is a non-exclusive
 *    license for use of this work by or on behalf of the US Government.
 *    Export of this program may require a license from the United States
 *    Government.
 */

/*
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 * 
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 * Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 *
 * Questions or comments about this library should be sent to:
 *
 * Lee Ward
 * Sandia National Laboratories, New Mexico
 * P.O. Box 5800
 * Albuquerque, NM 87185-1319
 *
 * le...@sa...
 */

#include <stdlib.h>

#include "tree.h"

/*
 * Splay to node with given key.
 *
 * Returns the value from the last compare; The one that brought, or left,
 * the root node at return.
 */
static int
splay(const void *key,
      struct tree_node **rootp,
      int (*compar)(const void *, const void *))
{
	struct tree_node spare, *l, *r, *tmp, *root;
	int	i;

	spare.tn_left = spare.tn_right = NULL;
	l = r = &spare;
	root = *rootp;
	for (;;) {
		i = (*compar)(key, root->tn_key);
		if (i < 0) {
			if (root->tn_left &&
			    (*compar)(key, root->tn_left->tn_key) < 0) {
				tmp = root->tn_left;
				root->tn_left = tmp->tn_right;
				tmp->tn_right = root;
				root = tmp;
			}
			if (!root->tn_left)
				break;
			r->tn_left = root;
			r = root;
			root = root->tn_left;
		} else if (i > 0) {
			if (root->tn_right &&
			    (*compar)(key, root->tn_right->tn_key) > 0) {
				tmp = root->tn_right;
				root->tn_right = tmp->tn_left;
				tmp->tn_left = root;
				root = tmp;
			}
			if (!root->tn_right)
				break;
			l->tn_right = root;
			l = root;
			root = root->tn_right;
		} else
			break;
	}

	/*
	 * Re-link.
	 */
	l->tn_right = root->tn_left;
	r->tn_left = root->tn_right;
	root->tn_left = spare.tn_right;
	root->tn_right = spare.tn_left;
	*rootp = root;

	return i;
}

/*
 * Return tree node with matching key or replace with passed node.
 */
struct tree_node *
_sysio_tree_search(struct tree_node *tn,
		   struct tree_node **rootp,
		   int (*compar)(const void *, const void *))
{
	int	i;

	if (!*rootp) {
		tn->tn_left = tn->tn_right = NULL;
	} else {
		i = splay(tn->tn_key, rootp, compar);
		if (i < 0) {
			tn->tn_left = (*rootp)->tn_left;
			tn->tn_right = *rootp;
			(*rootp)->tn_left = NULL;
		} else if (i > 0) {
			tn->tn_right = (*rootp)->tn_right;
			tn->tn_left = *rootp;
			(*rootp)->tn_right = NULL;
		} else
			return *rootp;
	}
	*rootp = tn;
	return *rootp;
}

/*
 * Find node with given key. Return NULL if not found.
 */
struct tree_node *
_sysio_tree_find(const void *key,
		 struct tree_node **rootp,
		 int (*compar)(const void *, const void *))
{

	if (!*rootp)
		return NULL;
	return splay(key, rootp, compar) == 0 ? *rootp : NULL;
}

/*
 * Remove node with given key. Returns the node removed or NULL if not found.
 */
struct tree_node *
_sysio_tree_delete(const void *key,
		   struct tree_node **rootp,
		   int (*compar)(const void *, const void *))
{
	struct tree_node *tn;

	tn = _sysio_tree_find(key, rootp, compar);
	if (!tn)
		return NULL;
	/*
	 * Invariant; The desired node is at the root.
	 */
	if (!(*rootp)->tn_left)
		*rootp = (*rootp)->tn_right;
	else {
		splay((*rootp)->tn_key, &(*rootp)->tn_left, compar);
		(*rootp)->tn_left->tn_right = (*rootp)->tn_right;
		*rootp = (*rootp)->tn_left;
	}
	return tn;
}

Index: module.mk
===================================================================
RCS file: /cvsroot/libsysio/libsysio/src/module.mk,v
retrieving revision 1.15
retrieving revision 1.16
diff -u -w -b -B -p -r1.15 -r1.16
--- module.mk	20 Aug 2007 19:12:08 -0000	1.15
+++ module.mk	21 Sep 2007 19:35:53 -0000	1.16
@@ -35,6 +35,6 @@ SRCDIR_SRCS = src/access.c src/chdir.c s
 	src/symlink.c src/readlink.c \
 	src/truncate.c src/unlink.c src/utime.c \
 	$(FILE_SUPPORT) $(LUSTRE_SRCDIR_SRCS) \
-	$(TRACING_SRCS) src/cprintf.c
+	$(TRACING_SRCS) src/cprintf.c src/tree.c
 
 SRCDIR_EXTRA = src/module.mk