+2016-07-03 Keith Marshall <keithmarshall@users.sourceforge.net>
+
+ Rework tsearch and friends; resolve issues [#1512] and [#1576].
+
+ * include/search.h: Assert copyright; tidy layout.
+ (_SEARCH_H_): Rename this multiple inclusion guard macro...
+ (_SEARCH_H): ...to conform to this preferred standard convention.
+ (__search_comparator): New function prototype typedef; it provides a
+ convenient shorthand notation for argument declarations in functions
+ which require a comparator function pointer; use it where appropriate.
+ (tsearch, tfind, tdelete) [__MINGW_ATTRIB_NONNULL]: Apply to arguments
+ #2 and #3; was previously incorrectly applied to arguments #1 and #3.
+ (twalk) [__MINGW_ATTRIB_NONNULL]: Apply to both arguments #1 and #2.
+ [_SEARCH_PRIVATE] (__MINGW_ATTRIB_NONNULL): Suppress its effect, to
+ ensure that GCC does not optimize away checks within implementation.
+ (_BEGIN_C_DECLS, _END_C_DECLS): Use these.
+
+ * mingwex/tdelete.c: Tidy layout.
+ (tdelete): Reimplement it as a thin wrapper around...
+ (__tdelete): ...this; it encapsulates the original implementation as a
+ __CRT_ALIAS (inline) function, to simplify void ** --> node_t ** casts.
+ Remove unnecessary non-null assertions for arguments #1 and #3; prefer
+ to validate arguments #2 and #3 internally, and simply return NULL if
+ necessary; hence, do not include <assert.h>
+
+ * mingwex/tfind.c: Tidy layout.
+ (tfind): Similarly reimplement it as a thin wrapper around...
+ (__tfind): ...this __CRT_ALIAS (inline) encapsulation of the original.
+ Add non-null validation for argument #3; do not include <assert.h>
+
+ * mingwex/tsearch.c: Tidy layout.
+ (tsearch): Once again, reimplement it as a thin wrapper around...
+ (__tsearch): ...this __CRT_ALIAS variant. Add non-null validation for
+ argument #3; do not include <assert.h>
+
+ * mingwex/twalk.c: Tidy layout; do not include <assert.h>
+
2016-06-28 Keith Marshall <keithmarshall@users.sourceforge.net>
Rework __try1/__except1 to resolve issue [#1328].
*
* Functions for searching and sorting.
*
- * This file is part of the Mingw32 package.
+ * $Id$
*
- * Contributors:
- * Created by Danny Smith <dannysmith@users.sourceforge.net>
+ * Written by Danny Smith <dannysmith@users.sourceforge.net>
+ * Copyright (C) 2003, 2004, 2007, 2016, MinGW.org Project.
*
- * THIS SOFTWARE IS NOT COPYRIGHTED
*
- * This source code is offered for use in the public domain. You may
- * use, modify or distribute it freely.
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
*
- * This code is distributed in the hope that it will be useful but
- * WITHOUT ANY WARRANTY. ALL WARRANTIES, EXPRESS OR IMPLIED ARE HEREBY
- * DISCLAIMED. This includes but is not limited to warranties of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ * The above copyright notice, this permission notice, and the following
+ * disclaimer shall be included in all copies or substantial portions of
+ * the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OF OR OTHER
+ * DEALINGS IN THE SOFTWARE.
*
*/
+#ifndef _SEARCH_H
+#pragma GCC system_header
+#define _SEARCH_H
-#ifndef _SEARCH_H_
-#define _SEARCH_H_
-
-/* All the headers include this file. */
+/* All MinGW headers must include <_mingw.h>
+ */
#include <_mingw.h>
#ifndef RC_INVOKED
-#ifdef __cplusplus
-extern "C" {
-#endif
+_BEGIN_C_DECLS
-#ifndef _SIZE_T_DEFINED
-typedef unsigned int size_t;
-#define _SIZE_T_DEFINED
-#endif
+/* POSIX specifies that <search.h> must define size_t, as it
+ * is defined in <sys/types.h>; get it from <stddef.h>, just as
+ * <sys/types.h> does.
+ */
+#define __need_size_t
+#include <stddef.h>
+
+/* All search functions require a user-specified comparator
+ * function, to be passed as an argument; this typedef is a
+ * convenient shorthand for its generic prototype.
+ */
+typedef int (*__search_comparator)(const void *, const void *);
-/* bsearch and qsort are also declared in stdlib.h */
-_CRTIMP void* __cdecl bsearch (const void*, const void*, size_t, size_t,
- int (*)(const void*, const void*));
-_CRTIMP void __cdecl qsort (void*, size_t, size_t,
- int (*)(const void*, const void*));
+/* POSIX specifies that bsearch() and qsort() are to be declared in
+ * <stdlib.h>, and NOT here; they ARE duplicated here, for Microsoft
+ * compatibility only.
+ */
+_CRTIMP __cdecl void *bsearch
+(const void *, const void *, size_t, size_t, __search_comparator );
-_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
-*/
+_CRTIMP __cdecl void qsort (void *, size_t, size_t, __search_comparator );
+/* This pair of functions are Microsoft specific; see below for their
+ * POSIX counterparts, (corresponding to Microsoft's old names).
+ */
+_CRTIMP __cdecl void *_lfind
+(const void *, const void *, unsigned int *, unsigned int, __search_comparator );
-typedef struct entry {
- char *key;
- void *data;
+_CRTIMP __cdecl void *_lsearch
+(const void *, void *, unsigned int *, unsigned int, __search_comparator );
+
+#ifdef _POSIX_C_SOURCE
+/* Documentation for the following POSIX definitions and prototypes
+ * may be found in the Open Group Base Specifications Issue 7, (which
+ * corresponds to IEEE Std 1003.1, 2008 Edition); see:
+ *
+ * http://pubs.opengroup.org/onlinepubs/9699919799/basedefs/search.h.html
+ */
+typedef
+struct entry
+{ char *key;
+ void *data;
} ENTRY;
-typedef enum {
- FIND,
- ENTER
-} ACTION;
+typedef
+enum { FIND, ENTER } ACTION;
-typedef enum {
- preorder,
- postorder,
- endorder,
- leaf
-} VISIT;
+typedef
+enum { preorder, postorder, endorder, leaf } VISIT;
#ifdef _SEARCH_PRIVATE
-typedef struct node {
- char *key;
- struct node *llink, *rlink;
+/* For private use within the respective tree function implementations,
+ * we define a structured representation of a tree node.
+ *
+ * FIXME: this really doesn't belong here! Users should NEVER enable
+ * this feature test; they should not be given this opportunity.
+ */
+typedef
+struct node
+{ const void *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*,
- unsigned int, int (*)(const void*, const void*));
-_CRTIMP void* __cdecl lsearch (const void*, void*, unsigned int*, unsigned int,
- int (*)(const void*, const void*));
-#endif
+/* Suppress non-null argument annotations, when building the tsearch(),
+ * tfind(), tdelete(), and twalk() implementations, to ensure that GCC
+ * does not optimize away internal argument validation checks.
+ */
+#undef __MINGW_ATTRIB_NONNULL
+#define __MINGW_ATTRIB_NONNULL(ARG_INDEX) /* NOTHING */
+
+#endif /* _SEARCH_PRIVATE */
+
+__cdecl void *tdelete
+(const void *__restrict__, void **__restrict__, __search_comparator)
+__MINGW_ATTRIB_NONNULL(2) __MINGW_ATTRIB_NONNULL(3);
+
+__cdecl void *tfind (const void *, void *const *, __search_comparator)
+__MINGW_ATTRIB_NONNULL(2) __MINGW_ATTRIB_NONNULL(3);
+
+__cdecl void *tsearch (const void *, void **, __search_comparator)
+__MINGW_ATTRIB_NONNULL(2) __MINGW_ATTRIB_NONNULL(3);
+
+__cdecl void twalk (const void *, void (*)(const void *, VISIT, int))
+__MINGW_ATTRIB_NONNULL(1) __MINGW_ATTRIB_NONNULL(2);
+
+#endif /* _POSIX_C_SOURCE */
+
+#if !defined _NO_OLDNAMES || defined _POSIX_C_SOURCE
+/* Declared as deprecated, by Microsoft, but these are the POSIX names
+ * for the functions which Microsoft now call _lfind() and _lsearch().
+ */
+_CRTIMP __cdecl void *lfind
+(const void *, const void *, unsigned int *, unsigned int, __search_comparator);
-#ifdef __cplusplus
-}
+_CRTIMP __cdecl void *lsearch
+(const void *, void *, unsigned int *, unsigned int, __search_comparator);
#endif
-#endif /* RC_INVOKED */
+_END_C_DECLS
-#endif /* _SEARCH_H_ */
+#endif /* ! RC_INVOKED */
+#endif /* !_SEARCH_H: $RCSfile$: end of file */
-/* $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.
+/* $NetBSD: tdelete.c,v 1.3 1999/09/20 04:39:43 lukem Exp $
*
- * The node_t structure is for internal use only, lint doesn't grok it.
+ *
+ * Tree search generalized from Knuth (6.2.2) Algorithm T just like
+ * the AT&T man page says; tdelete based on Knuth's Algorithm D.
*
* 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 *))
+__CRT_ALIAS void *__tdelete
+(const void *key, node_t **rootp, int (*compar)(const void *, const void *))
{
- node_t **rootp = (node_t **)vrootp;
- node_t *p, *q, *r;
- int cmp;
+ /* Delete node with specified "key", from tree referred to by "rootp".
+ *
+ * NOTE: node_t is defined as a structured data type, for internal use
+ * when _SEARCH_PRIVATE is enabled; for public consumption, it becomes
+ * an alias for "void", (assuming _SEARCH_PRIVATE is NOT enabled).
+ */
+ int cmp;
+ node_t *p, *q, *r;
- _DIAGASSERT(vkey != NULL);
- _DIAGASSERT(compar != NULL);
+ if( (rootp == NULL) || ((p = *rootp) == NULL) || (compar == NULL) )
+ return NULL;
- if (rootp == NULL || (p = *rootp) == NULL)
- return NULL;
+ while( (cmp = (*compar)(key, (*rootp)->key)) != 0 )
+ {
+ rootp = (cmp < 0)
+ ? &(p = *rootp)->llink /* follow llink branch */
+ : &(p = *rootp)->rlink; /* follow rlink branch */
- 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;
+ 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;
}
+
+void *tdelete
+(const void *key, void **rootp, int (*compar)(const void *, const void *))
+{ return __tdelete (key, (node_t **)(rootp), compar); }
-/* $NetBSD: tfind.c,v 1.3.18.2 2005/03/23 11:12:21 tron Exp $ */
-
-/*
+/* $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 *))
+__CRT_ALIAS void *__tfind
+(const void *key, node_t *const *rootp, int (*compar)(const void *, const void *))
{
- node_t * const *rootp = (node_t * const*)vrootp;
+ /* Find node with specified "key", within tree referred to by "rootp";
+ * return NULL if not found, (or if either "rootp" or "compar" is not
+ * a valid pointer).
+ *
+ * NOTE: node_t is defined as a structured data type, for internal use
+ * when _SEARCH_PRIVATE is enabled; for public consumption, it becomes
+ * an alias for "void", (assuming _SEARCH_PRIVATE is NOT enabled).
+ */
+ if( (rootp == NULL) || (compar == NULL) )
+ return NULL;
- if (rootp == NULL)
- return NULL;
+ while (*rootp != NULL) /* Knuth's T1: */
+ {
+ int cmp; /* T2: */
+ if( (cmp = (*compar)(key, (*rootp)->key)) == 0 )
+ return *rootp; /* key found */
- 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;
+ rootp = (cmp < 0)
+ ? &(*rootp)->llink /* T3: follow left branch */
+ : &(*rootp)->rlink; /* T4: follow right branch */
+ }
+ return NULL; /* key not found */
}
+
+void *tfind
+(const void *key, void *const *rootp, int (*compar)(const void *, const void *))
+{ return __tfind (key, (node_t *const *)(rootp), compar); }
-/* $NetBSD: tsearch.c,v 1.4 1999/09/20 04:39:43 lukem Exp $ */
-
-/*
+/* $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 *))
+__CRT_ALIAS void *__tsearch
+(const void *key, node_t **rootp, 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;
+ /* Find node identified by "key", within the tree referred to by "rootp",
+ * or insert such datum node, if not already present.
+ *
+ * NOTE: node_t is defined as a structured data type, for internal use
+ * when _SEARCH_PRIVATE is enabled; for public consumption, it becomes
+ * an alias for "void", (assuming _SEARCH_PRIVATE is NOT enabled).
+ */
+ node_t *q;
+
+ /* Cannot search from an invalid tree reference pointer, or without a
+ * valid comparator function reference.
+ */
+ if( (rootp == NULL) || (compar == NULL) )
+ return NULL;
+
+ while( *rootp != NULL ) /* Knuth's T1: */
+ {
+ int cmp; /* T2: */
+ if( (cmp = (*compar)(key, (*rootp)->key)) == 0 )
+ return *rootp; /* we found it! */
+
+ rootp = (cmp < 0)
+ ? &(*rootp)->llink /* T3: follow left branch */
+ : &(*rootp)->rlink; /* T4: follow right branch */
+ }
+
+ q = malloc( sizeof(node_t) ); /* T5: key not found */
+ if( q != NULL ) /* make new node */
+ {
+ *rootp = q; /* link new node to old */
+ q->key = key; /* initialize new node */
+ q->llink = q->rlink = NULL;
+ }
+ return q;
}
+
+void *tsearch
+(const void *key, void **rootp, int (*compar)(const void *, const void *))
+{ return __tsearch (key, (node_t **)(rootp), compar); }
-/* $NetBSD: twalk.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ */
-
-/*
+/* $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)
+static __MINGW_ATTRIB_NONNULL(1) __MINGW_ATTRIB_NONNULL(2)
+void trecurse (const node_t *, void (*)(const void *, VISIT, int), int);
+
+static void trecurse
+( const node_t *root, 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);
- }
+ /* Recursively walk the nodes of a tree, performing the specified
+ * action as each node is traversed, and as appropriate for each
+ * phase of traversal.
+ */
+ 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))
+void twalk (const void *root, void (*action)(const void *, VISIT, int))
{
- if (vroot != NULL && action != NULL)
- trecurse(vroot, action, 0);
+ /* Walk the nodes of a tree, delegating to the local recursive
+ * helper function, to invoke the specified action on each node
+ * in turn, as appropriate in each phase of traversal.
+ */
+ if( (root != NULL) && (action != NULL) )
+ trecurse (root, action, 0);
}
OSDN Git Service
