diff options
author | Danny Smith <dannysmith@users.sourceforge.net> | 2007-06-22 14:09:20 +0400 |
---|---|---|
committer | Danny Smith <dannysmith@users.sourceforge.net> | 2007-06-22 14:09:20 +0400 |
commit | e54e4d47f189c0f74930261c95cbb0043c07ef43 (patch) | |
tree | a33b3118e7300a038d7145c135cf770a2d376304 /winsup | |
parent | 3d7e738f7262f5c0dad5c8db97283dc58f5ae3c3 (diff) |
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.
Diffstat (limited to 'winsup')
-rw-r--r-- | winsup/mingw/ChangeLog | 19 | ||||
-rw-r--r-- | winsup/mingw/include/search.h | 42 | ||||
-rw-r--r-- | winsup/mingw/mingwex/Makefile.in | 7 | ||||
-rwxr-xr-x | winsup/mingw/mingwex/tdelete.c | 65 | ||||
-rwxr-xr-x | winsup/mingw/mingwex/tfind.c | 41 | ||||
-rwxr-xr-x | winsup/mingw/mingwex/tsearch.c | 51 | ||||
-rwxr-xr-x | winsup/mingw/mingwex/twalk.c | 48 |
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); +} |