| 1 |
/* |
| 2 |
* search.h |
| 3 |
* |
| 4 |
* Functions for searching and sorting. |
| 5 |
* |
| 6 |
* $Id: search.h,v b5eb78a1f3b9 2016/07/03 19:23:28 keithmarshall $ |
| 7 |
* |
| 8 |
* Written by Danny Smith <dannysmith@users.sourceforge.net> |
| 9 |
* Copyright (C) 2003, 2004, 2007, 2016, MinGW.org Project. |
| 10 |
* |
| 11 |
* |
| 12 |
* Permission is hereby granted, free of charge, to any person obtaining a |
| 13 |
* copy of this software and associated documentation files (the "Software"), |
| 14 |
* to deal in the Software without restriction, including without limitation |
| 15 |
* the rights to use, copy, modify, merge, publish, distribute, sublicense, |
| 16 |
* and/or sell copies of the Software, and to permit persons to whom the |
| 17 |
* Software is furnished to do so, subject to the following conditions: |
| 18 |
* |
| 19 |
* The above copyright notice, this permission notice, and the following |
| 20 |
* disclaimer shall be included in all copies or substantial portions of |
| 21 |
* the Software. |
| 22 |
* |
| 23 |
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS |
| 24 |
* OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| 25 |
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL |
| 26 |
* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
| 27 |
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING |
| 28 |
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OF OR OTHER |
| 29 |
* DEALINGS IN THE SOFTWARE. |
| 30 |
* |
| 31 |
*/ |
| 32 |
#ifndef _SEARCH_H |
| 33 |
#pragma GCC system_header |
| 34 |
#define _SEARCH_H |
| 35 |
|
| 36 |
/* All MinGW headers must include <_mingw.h> |
| 37 |
*/ |
| 38 |
#include <_mingw.h> |
| 39 |
|
| 40 |
#ifndef RC_INVOKED |
| 41 |
|
| 42 |
_BEGIN_C_DECLS |
| 43 |
|
| 44 |
/* POSIX specifies that <search.h> must define size_t, as it |
| 45 |
* is defined in <sys/types.h>; get it from <stddef.h>, just as |
| 46 |
* <sys/types.h> does. |
| 47 |
*/ |
| 48 |
#define __need_size_t |
| 49 |
#include <stddef.h> |
| 50 |
|
| 51 |
/* All search functions require a user-specified comparator |
| 52 |
* function, to be passed as an argument; this typedef is a |
| 53 |
* convenient shorthand for its generic prototype. |
| 54 |
*/ |
| 55 |
typedef int (*__search_comparator)(const void *, const void *); |
| 56 |
|
| 57 |
/* POSIX specifies that bsearch() and qsort() are to be declared in |
| 58 |
* <stdlib.h>, and NOT here; they ARE duplicated here, for Microsoft |
| 59 |
* compatibility only. |
| 60 |
*/ |
| 61 |
_CRTIMP __cdecl void *bsearch |
| 62 |
(const void *, const void *, size_t, size_t, __search_comparator ); |
| 63 |
|
| 64 |
_CRTIMP __cdecl void qsort (void *, size_t, size_t, __search_comparator ); |
| 65 |
|
| 66 |
/* This pair of functions are Microsoft specific; see below for their |
| 67 |
* POSIX counterparts, (corresponding to Microsoft's old names). |
| 68 |
*/ |
| 69 |
_CRTIMP __cdecl void *_lfind |
| 70 |
(const void *, const void *, unsigned int *, unsigned int, __search_comparator ); |
| 71 |
|
| 72 |
_CRTIMP __cdecl void *_lsearch |
| 73 |
(const void *, void *, unsigned int *, unsigned int, __search_comparator ); |
| 74 |
|
| 75 |
#ifdef _POSIX_C_SOURCE |
| 76 |
/* Documentation for the following POSIX definitions and prototypes |
| 77 |
* may be found in the Open Group Base Specifications Issue 7, (which |
| 78 |
* corresponds to IEEE Std 1003.1, 2008 Edition); see: |
| 79 |
* |
| 80 |
* http://pubs.opengroup.org/onlinepubs/9699919799/basedefs/search.h.html |
| 81 |
*/ |
| 82 |
typedef |
| 83 |
struct entry |
| 84 |
{ char *key; |
| 85 |
void *data; |
| 86 |
} ENTRY; |
| 87 |
|
| 88 |
typedef |
| 89 |
enum { FIND, ENTER } ACTION; |
| 90 |
|
| 91 |
typedef |
| 92 |
enum { preorder, postorder, endorder, leaf } VISIT; |
| 93 |
|
| 94 |
#ifdef _SEARCH_PRIVATE |
| 95 |
/* For private use within the respective tree function implementations, |
| 96 |
* we define a structured representation of a tree node. |
| 97 |
* |
| 98 |
* FIXME: this really doesn't belong here! Users should NEVER enable |
| 99 |
* this feature test; they should not be given this opportunity. |
| 100 |
*/ |
| 101 |
typedef |
| 102 |
struct node |
| 103 |
{ const void *key; |
| 104 |
struct node *llink, *rlink; |
| 105 |
} node_t; |
| 106 |
|
| 107 |
/* Suppress non-null argument annotations, when building the tsearch(), |
| 108 |
* tfind(), tdelete(), and twalk() implementations, to ensure that GCC |
| 109 |
* does not optimize away internal argument validation checks. |
| 110 |
*/ |
| 111 |
#undef __MINGW_ATTRIB_NONNULL |
| 112 |
#define __MINGW_ATTRIB_NONNULL(ARG_INDEX) /* NOTHING */ |
| 113 |
|
| 114 |
#endif /* _SEARCH_PRIVATE */ |
| 115 |
|
| 116 |
__cdecl void *tdelete |
| 117 |
(const void *__restrict__, void **__restrict__, __search_comparator) |
| 118 |
__MINGW_ATTRIB_NONNULL(2) __MINGW_ATTRIB_NONNULL(3); |
| 119 |
|
| 120 |
__cdecl void *tfind (const void *, void *const *, __search_comparator) |
| 121 |
__MINGW_ATTRIB_NONNULL(2) __MINGW_ATTRIB_NONNULL(3); |
| 122 |
|
| 123 |
__cdecl void *tsearch (const void *, void **, __search_comparator) |
| 124 |
__MINGW_ATTRIB_NONNULL(2) __MINGW_ATTRIB_NONNULL(3); |
| 125 |
|
| 126 |
__cdecl void twalk (const void *, void (*)(const void *, VISIT, int)) |
| 127 |
__MINGW_ATTRIB_NONNULL(1) __MINGW_ATTRIB_NONNULL(2); |
| 128 |
|
| 129 |
#endif /* _POSIX_C_SOURCE */ |
| 130 |
|
| 131 |
#if !defined _NO_OLDNAMES || defined _POSIX_C_SOURCE |
| 132 |
/* Declared as deprecated, by Microsoft, but these are the POSIX names |
| 133 |
* for the functions which Microsoft now call _lfind() and _lsearch(). |
| 134 |
*/ |
| 135 |
_CRTIMP __cdecl void *lfind |
| 136 |
(const void *, const void *, unsigned int *, unsigned int, __search_comparator); |
| 137 |
|
| 138 |
_CRTIMP __cdecl void *lsearch |
| 139 |
(const void *, void *, unsigned int *, unsigned int, __search_comparator); |
| 140 |
#endif |
| 141 |
|
| 142 |
_END_C_DECLS |
| 143 |
|
| 144 |
#endif /* ! RC_INVOKED */ |
| 145 |
#endif /* !_SEARCH_H: $RCSfile: search.h,v $: end of file */ |
