[Libsysio-commit] HEAD: libsysio/src tree.c module.mk
Brought to you by:
lward
|
From: Lee W. <lw...@us...> - 2007-09-21 19:36:00
|
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 |