--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/usr/src/lib/libc/port/gen/tsearch.c Tue Jun 14 00:00:00 2005 -0700
@@ -0,0 +1,159 @@
+/*
+ * CDDL HEADER START
+ *
+ * The contents of this file are subject to the terms of the
+ * Common Development and Distribution License, Version 1.0 only
+ * (the "License"). You may not use this file except in compliance
+ * with the License.
+ *
+ * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
+ * or http://www.opensolaris.org/os/licensing.
+ * See the License for the specific language governing permissions
+ * and limitations under the License.
+ *
+ * When distributing Covered Code, include this CDDL HEADER in each
+ * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
+ * If applicable, add the following below this CDDL HEADER, with the
+ * fields enclosed by brackets "[]" replaced with your own identifying
+ * information: Portions Copyright [yyyy] [name of copyright owner]
+ *
+ * CDDL HEADER END
+ */
+/*
+ * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
+ * Use is subject to license terms.
+ */
+
+#pragma ident "%Z%%M% %I% %E% SMI"
+
+/* Copyright (c) 1988 AT&T */
+/* All Rights Reserved */
+
+
+/*
+ * Tree search algorithm, generalized from Knuth (6.2.2) Algorithm T.
+ *
+ *
+ * The NODE * arguments are declared in the lint files as char *,
+ * because the definition of NODE isn't available to the user.
+ */
+
+#pragma weak tdelete = _tdelete
+#pragma weak tsearch = _tsearch
+#pragma weak twalk = _twalk
+
+#include "synonyms.h"
+#include "mtlib.h"
+#include "libc.h"
+#include <sys/types.h>
+#include <search.h>
+#include <stdlib.h>
+#include <thread.h>
+#include <synch.h>
+
+
+
+typedef struct node { char *key; struct node *llink, *rlink; } NODE;
+
+static void __twalk(NODE *, void (*)(const void *, VISIT, int), int);
+
+
+/* Find or insert key into search tree */
+void *
+tsearch(const void *ky, void **rtp, int (*compar)())
+{
+ char *key = (char *)ky;
+ NODE **rootp = (NODE **)rtp;
+ NODE *q; /* New node if key not found */
+
+ if (rootp == NULL)
+ return (NULL);
+ while (*rootp != NULL) { /* T1: */
+ int r = (*compar)(key, (*rootp)->key); /* T2: */
+ if (r == 0)
+ return ((void *)*rootp); /* Key found */
+ rootp = (r < 0) ?
+ &(*rootp)->llink : /* T3: Take left branch */
+ &(*rootp)->rlink; /* T4: Take right branch */
+ }
+ q = lmalloc(sizeof (NODE)); /* T5: Not found */
+ if (q != NULL) { /* Allocate new node */
+ *rootp = q; /* Link new node to old */
+ q->key = key; /* Initialize new node */
+ q->llink = q->rlink = NULL;
+ }
+ return ((void *)q);
+}
+
+/* Delete node with key key */
+void *
+tdelete(const void *ky, void **rtp, int (*compar)())
+{
+ char *key = (char *)ky;
+ NODE **rootp = (NODE **)rtp;
+ NODE *p; /* Parent of node to be deleted */
+ NODE *q; /* Successor node */
+ NODE *r; /* Right son node */
+ int ans; /* Result of comparison */
+
+ if (rootp == NULL || (p = *rootp) == NULL)
+ return (NULL);
+ while ((ans = (*compar)(key, (*rootp)->key)) != 0) {
+ p = *rootp;
+ rootp = (ans < 0) ?
+ &(*rootp)->llink : /* Take left branch */
+ &(*rootp)->rlink; /* Take right branch */
+ if (*rootp == NULL)
+ return (NULL); /* Key not found */
+ }
+ r = (*rootp)->rlink; /* D1: */
+ if ((q = (*rootp)->llink) == NULL) /* Llink NULL? */
+ q = r;
+ else if (r != NULL) { /* Rlink NULL? */
+ if (r->llink == NULL) { /* D2: Find successor */
+ r->llink = q;
+ q = r;
+ } else { /* D3: Find NULL link */
+ for (q = r->llink; q->llink != NULL; q = r->llink)
+ r = q;
+ r->llink = q->rlink;
+ q->llink = (*rootp)->llink;
+ q->rlink = (*rootp)->rlink;
+ }
+ }
+ lfree(*rootp, sizeof (NODE)); /* D4: Free node */
+ *rootp = q; /* Link parent to replacement */
+ return ((void *)p);
+}
+
+
+/* Walk the nodes of a tree */
+void
+twalk(const void *rt, /* Root of the tree to be walked */
+ void (*action)(const void *, VISIT, int))
+{
+ NODE *root = (NODE *)rt;
+
+ if (root != NULL && action != NULL)
+ __twalk(root, action, 0);
+}
+
+
+/* Walk the nodes of a tree */
+static void
+__twalk(NODE *root, /* Root of the tree to be walked */
+ void (*action)(const void *, VISIT, int),
+ int level)
+{
+ if (root->llink == NULL && root->rlink == NULL)
+ (*action)(root, leaf, level);
+ else {
+ (*action)(root, preorder, level);
+ if (root->llink != NULL)
+ __twalk(root->llink, action, level + 1);
+ (*action)(root, postorder, level);
+ if (root->rlink != NULL)
+ __twalk(root->rlink, action, level + 1);
+ (*action)(root, endorder, level);
+ }
+}