Add POSIX binary tree search API.

	* mingwex/tfind.c: New file.
	* mingwex/tdelete.c: New file.
	* mingwex/tsearch.c: New file.
	* mingwex/twalk.c: New file.
	* mingwex/Makefile.in (DISTFILES): Add tsearch.c twalk.c tdelete.c tfind.c.
	* mingwex/Makefile.in (POSIX_OBJS): Add tsearch.o twalk.o tdelete.o tfind.o.
	* include/search.h (tfind): Declare.
	(tdelete): Declare.
	(tsearch): Declare.
	(twalk): Declare.
	(ENTRY): Define.
	(ACTION): Define.
	(VISIT): Define.
	(node_t): Define, on condition of _SEARCH_PRIVATE.

7 files changed, 269 insertions, 4 deletions

diff --git a/winsup/mingw/ChangeLog b/winsup/mingw/ChangeLog
index 873980478..0a345e062 100644
--- a/winsup/mingw/ChangeLog
+++ b/winsup/mingw/ChangeLog
@@ -1,5 +1,24 @@
 2007-06-22  Danny Smith  <dannysmith@users.sourceforge.net>
 
+	Add POSIX binary tree search API.
+
+	* mingwex/tfind.c: New file.
+	* mingwex/tdelete.c: New file.
+	* mingwex/tsearch.c: New file.
+	* mingwex/twalk.c: New file.
+	* mingwex/Makefile.in (DISTFILES): Add tsearch.c twalk.c tdelete.c tfind.c.
+	* mingwex/Makefile.in (POSIX_OBJS): Add tsearch.o twalk.o tdelete.o tfind.o.
+	* include/search.h (tfind): Declare.
+	(tdelete): Declare.
+	(tsearch): Declare.
+	(twalk): Declare.
+	(ENTRY): Define.
+	(ACTION): Define.
+	(VISIT): Define.
+	(node_t): Define, on condition of _SEARCH_PRIVATE.
+
+2007-06-22  Danny Smith  <dannysmith@users.sourceforge.net>
+
 	* include/_mingw.h (__MINGW_NOTHROW): Define.
 
 2007-06-18  Danny Smith  <dannysmith@users.sourceforge.net>
diff --git a/winsup/mingw/include/search.h b/winsup/mingw/include/search.h
index 2d7768b53..af71a32cc 100644
--- a/winsup/mingw/include/search.h
+++ b/winsup/mingw/include/search.h
@@ -47,6 +47,48 @@ _CRTIMP void* __cdecl _lfind (const void*, const void*, unsigned int*,
 			      unsigned int, int (*)(const void*, const void*));
 _CRTIMP void* __cdecl _lsearch (const void*, void*, unsigned int*, unsigned int,
 				int (*)(const void*, const void*));
+/*
+Documentation for these POSIX definitions and prototypes can be found in 
+The Open Group Base Specifications Issue 6
+IEEE Std 1003.1, 2004 Edition.
+eg:  http://www.opengroup.org/onlinepubs/009695399/functions/twalk.html
+*/
+
+
+typedef struct entry {
+	char *key;
+	void *data;
+} ENTRY;
+
+typedef enum {
+	FIND,
+	ENTER
+} ACTION;
+
+typedef enum {
+	preorder,
+	postorder,
+	endorder,
+	leaf
+} VISIT;
+
+#ifdef _SEARCH_PRIVATE
+typedef struct node {
+	char         *key;
+	struct node  *llink, *rlink;
+} node_t;
+#endif
+
+void * __cdecl tdelete (const void * __restrict__, void ** __restrict__,
+			int (*)(const void *, const void *))
+			__MINGW_ATTRIB_NONNULL (1)  __MINGW_ATTRIB_NONNULL (3);
+void * __cdecl tfind (const void *, void * const *,
+		      int (*)(const void *, const void *))
+		      __MINGW_ATTRIB_NONNULL (1)  __MINGW_ATTRIB_NONNULL (3);
+void * __cdecl tsearch (const void *, void **, 
+			int (*)(const void *, const void *))
+			__MINGW_ATTRIB_NONNULL (1)  __MINGW_ATTRIB_NONNULL (3);
+void __cdecl twalk (const void *, void (*)(const void *, VISIT, int));
 
 #ifndef	_NO_OLDNAMES
 _CRTIMP void* __cdecl lfind (const void*, const void*, unsigned int*,
diff --git a/winsup/mingw/mingwex/Makefile.in b/winsup/mingw/mingwex/Makefile.in
index 15f110c60..d6907da87 100644
--- a/winsup/mingw/mingwex/Makefile.in
+++ b/winsup/mingw/mingwex/Makefile.in
@@ -37,7 +37,8 @@ DISTFILES = Makefile.in configure configure.in aclocal.m4 \
 	wdirent.c wmemchr.c wmemcmp.c wmemcpy.c wmemmove.c wmemset.c wtoll.c \
 	wcrtomb.c wctob.c mbrtowc.c btowc.c mb_wc_common.h \
 	gettimeofday.c isblank.c iswblank.c \
-	basename.c dirname.c
+	basename.c dirname.c \
+        tsearch.c twalk.c tdelete.c tfind.c
 
 MATH_DISTFILES = \
 	acosf.c acosl.c asinf.c asinl.c atan2f.c atan2l.c \
@@ -90,7 +91,6 @@ GDTOA_DISTFILES = \
 	gd_arith.h  gd_qnan.h gdtoa.c gdtoa.h gdtoaimp.h gethex.c gmisc.c \
 	hd_init.c hexnan.c  misc.c qnan.c README smisc.c strtodg.c strtodnrp.c \
 	strtof.c strtopx.c sum.c ulp.c
-
 CC = @CC@
 # FIXME: Which is it, CC or CC_FOR_TARGET?
 CC_FOR_TARGET = $(CC)
@@ -174,7 +174,7 @@ FENV_OBJS = fesetround.o  fegetround.o \
 	feraiseexcept.o fetestexcept.o fesetexceptflag.o
 POSIX_OBJS = \
 	dirent.o wdirent.o getopt.o ftruncate.o gettimeofday.o \
-	basename.o dirname.o
+	basename.o dirname.o tsearch.o twalk.o tdelete.o tfind.o
 REPLACE_OBJS = \
 	mingw-aligned-malloc.o mingw-fseek.o
 COMPLEX_OBJS = \
@@ -191,7 +191,6 @@ GDTOA_OBJS = \
 	dmisc.o dtoa.o g__fmt.o g_dfmt.o g_ffmt.o g_xfmt.o gdtoa.o \
 	gethex.o gmisc.o hd_init.o hexnan.o misc.o smisc.o \
 	strtodg.o strtodnrp.o strtof.o strtopx.o sum.o ulp.o
-LIB_OBJS = $(Q8_OBJS)  $(CTYPE_OBJS) $(STDLIB_STUB_OBJS) \
 	$(STDIO_OBJS) $(MATH_OBJS)  $(FENV_OBJS) \
 	$(POSIX_OBJS) $(REPLACE_OBJS) $(COMPLEX_OBJS) \
 	$(GDTOA_OBJS)
diff --git a/winsup/mingw/mingwex/tdelete.c b/winsup/mingw/mingwex/tdelete.c
new file mode 100755
index 000000000..4de3897db
--- /dev/null
+++ b/winsup/mingw/mingwex/tdelete.c
@@ -0,0 +1,65 @@
+/*	$NetBSD: tdelete.c,v 1.3 1999/09/20 04:39:43 lukem Exp $	*/
+
+/*
+ * Tree search generalized from Knuth (6.2.2) Algorithm T just like
+ * the AT&T man page says.
+ *
+ * The node_t structure is for internal use only, lint doesn't grok it.
+ *
+ * Written by reading the System V Interface Definition, not the code.
+ *
+ * Totally public domain.
+ */
+
+#include <assert.h>
+#define _SEARCH_PRIVATE
+#include <search.h>
+#include <stdlib.h>
+
+#define _DIAGASSERT assert
+
+
+
+/* delete node with given key */
+void *
+tdelete(const void *vkey,	/* key to be deleted */
+	void      **vrootp,	/* address of the root of tree */
+	int       (*compar)(const void *, const void *))
+{
+	node_t **rootp = (node_t **)vrootp;
+	node_t *p, *q, *r;
+	int  cmp;
+
+	_DIAGASSERT(vkey != NULL);
+	_DIAGASSERT(compar != NULL);
+
+	if (rootp == NULL || (p = *rootp) == NULL)
+		return NULL;
+
+	while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) {
+		p = *rootp;
+		rootp = (cmp < 0) ?
+		    &(*rootp)->llink :		/* follow llink branch */
+		    &(*rootp)->rlink;		/* follow rlink branch */
+		if (*rootp == NULL)
+			return NULL;		/* key not found */
+	}
+	r = (*rootp)->rlink;			/* D1: */
+	if ((q = (*rootp)->llink) == NULL)	/* Left NULL? */
+		q = r;
+	else if (r != NULL) {			/* Right link is 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;
+		}
+	}
+	free(*rootp);				/* D4: Free node */
+	*rootp = q;				/* link parent to new node */
+	return p;
+}
diff --git a/winsup/mingw/mingwex/tfind.c b/winsup/mingw/mingwex/tfind.c
new file mode 100755
index 000000000..e8ffe657a
--- /dev/null
+++ b/winsup/mingw/mingwex/tfind.c
@@ -0,0 +1,41 @@
+/*	$NetBSD: tfind.c,v 1.3.18.2 2005/03/23 11:12:21 tron Exp $	*/
+
+/*
+ * Tree search generalized from Knuth (6.2.2) Algorithm T just like
+ * the AT&T man page says.
+ *
+ * The node_t structure is for internal use only, lint doesn't grok it.
+ *
+ * Written by reading the System V Interface Definition, not the code.
+ *
+ * Totally public domain.
+ */
+
+#include <assert.h>
+#define _SEARCH_PRIVATE
+#include <stdlib.h>
+#include <search.h>
+
+
+/* find a node, or return 0 */
+void *
+tfind(const void *vkey,
+      void * const *vrootp,
+      int (*compar) (const void *, const void *))
+{
+	node_t * const *rootp = (node_t * const*)vrootp;
+
+	if (rootp == NULL)
+		return NULL;
+
+	while (*rootp != NULL) {		/* T1: */
+		int r;
+
+		if ((r = (*compar)(vkey, (*rootp)->key)) == 0)	/* T2: */
+			return *rootp;		/* key found */
+		rootp = (r < 0) ?
+		    &(*rootp)->llink :		/* T3: follow left branch */
+		    &(*rootp)->rlink;		/* T4: follow right branch */
+	}
+	return NULL;
+}
diff --git a/winsup/mingw/mingwex/tsearch.c b/winsup/mingw/mingwex/tsearch.c
new file mode 100755
index 000000000..a0aa0eb36
--- /dev/null
+++ b/winsup/mingw/mingwex/tsearch.c
@@ -0,0 +1,51 @@
+/*	$NetBSD: tsearch.c,v 1.4 1999/09/20 04:39:43 lukem Exp $	*/
+
+/*
+ * Tree search generalized from Knuth (6.2.2) Algorithm T just like
+ * the AT&T man page says.
+ *
+ * The node_t structure is for internal use only, lint doesn't grok it.
+ *
+ * Written by reading the System V Interface Definition, not the code.
+ *
+ * Totally public domain.
+ */
+
+#include <assert.h>
+#define _SEARCH_PRIVATE
+#include <search.h>
+#include <stdlib.h>
+
+
+/* find or insert datum into search tree */
+void *
+tsearch(const void * __restrict__ vkey,		/* key to be located */
+	void ** __restrict__ vrootp,		/* address of tree root */
+	int (*compar) (const void *, const void *))
+{
+	node_t *q;
+	node_t **rootp = (node_t **)vrootp;
+
+	if (rootp == NULL)
+		return NULL;
+
+	while (*rootp != NULL) {	/* Knuth's T1: */
+		int r;
+
+		if ((r = (*compar)(vkey, (*rootp)->key)) == 0)	/* T2: */
+			return *rootp;		/* we found it! */
+
+		rootp = (r < 0) ?
+		    &(*rootp)->llink :		/* T3: follow left branch */
+		    &(*rootp)->rlink;		/* T4: follow right branch */
+	}
+
+	q = malloc(sizeof(node_t));		/* T5: key not found */
+	if (q != 0) {				/* make new node */
+		*rootp = q;			/* link new node to old */
+		/* LINTED const castaway ok */
+		q->key = (void *)vkey;		/* initialize new node */
+		q->llink = q->rlink = NULL;
+	}
+	return q;
+}
diff --git a/winsup/mingw/mingwex/twalk.c b/winsup/mingw/mingwex/twalk.c
new file mode 100755
index 000000000..aa7909c8a
--- /dev/null
+++ b/winsup/mingw/mingwex/twalk.c
@@ -0,0 +1,48 @@
+/*	$NetBSD: twalk.c,v 1.2 1999/09/16 11:45:37 lukem Exp $	*/
+
+/*
+ * Tree search generalized from Knuth (6.2.2) Algorithm T just like
+ * the AT&T man page says.
+ *
+ * The node_t structure is for internal use only, lint doesn't grok it.
+ *
+ * Written by reading the System V Interface Definition, not the code.
+ *
+ * Totally public domain.
+ */
+
+#include <assert.h>
+#define _SEARCH_PRIVATE
+#include <search.h>
+#include <stdlib.h>
+
+static void trecurse (const node_t *, void (*action)(const void *, VISIT, int),
+	              int level)  __MINGW_ATTRIB_NONNULL (1)
+				  __MINGW_ATTRIB_NONNULL (2);
+/* Walk the nodes of a tree */
+static void
+trecurse( const node_t *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)
+			trecurse(root->llink, action, level + 1);
+		(*action)(root, postorder, level);
+		if (root->rlink != NULL)
+			trecurse(root->rlink, action, level + 1);
+		(*action)(root, endorder, level);
+	}
+}
+
+/* Walk the nodes of a tree */
+void
+twalk( const void *vroot,	/* Root of the tree to be walked */
+	void (*action) (const void *, VISIT, int))
+{
+	if (vroot != NULL && action != NULL)
+		trecurse(vroot, action, 0);
+}