lib/search.in.h

   1 /* A GNU-like <search.h>.
   2
   3    Copyright (C) 2007-2021 Free Software Foundation, Inc.
   4
   5    This program is free software: you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 3 of the License, or
   8    (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  17
  18 #ifndef _@GUARD_PREFIX@_SEARCH_H
  19
  20 #if __GNUC__ >= 3
  21 @PRAGMA_SYSTEM_HEADER@
  22 #endif
  23 @PRAGMA_COLUMNS@
  24
  25 /* The include_next requires a split double-inclusion guard.  */
  26 #if @HAVE_SEARCH_H@
  27 # @INCLUDE_NEXT@ @NEXT_SEARCH_H@
  28 #endif
  29
  30 #ifndef _@GUARD_PREFIX@_SEARCH_H
  31 #define _@GUARD_PREFIX@_SEARCH_H
  32
  33
  34 /* The definitions of _GL_FUNCDECL_RPL etc. are copied here.  */
  35
  36 /* The definition of _GL_ARG_NONNULL is copied here.  */
  37
  38 /* The definition of _GL_WARN_ON_USE is copied here.  */
  39
  40
  41 #if @GNULIB_MDA_LFIND@
  42 /* On native Windows, map 'lfind' to '_lfind', so that -loldnames is not
  43    required.  In C++ with GNULIB_NAMESPACE, avoid differences between
  44    platforms by defining GNULIB_NAMESPACE::lfind always.  */
  45 # if defined _WIN32 && !defined __CYGWIN__
  46 #  if !(defined __cplusplus && defined GNULIB_NAMESPACE)
  47 #   undef lfind
  48 #   define lfind _lfind
  49 #  endif
  50 _GL_CXXALIAS_MDA (lfind, void *,
  51                   (const void *key, const void *base, unsigned int *nmemb,
  52                    unsigned int size,
  53                    int (*compar) (const void *, const void *)));
  54 # else
  55 _GL_CXXALIAS_SYS (lfind, void *,
  56                   (const void *key, const void *base, size_t *nmemb,
  57                    size_t size,
  58                    int (*compar) (const void *, const void *)));
  59 # endif
  60 _GL_CXXALIASWARN (lfind);
  61 #endif
  62
  63 #if @GNULIB_MDA_LSEARCH@
  64 /* On native Windows, map 'lsearch' to '_lsearch', so that -loldnames is not
  65    required.  In C++ with GNULIB_NAMESPACE, avoid differences between
  66    platforms by defining GNULIB_NAMESPACE::lsearch always.  */
  67 # if defined _WIN32 && !defined __CYGWIN__
  68 #  if !(defined __cplusplus && defined GNULIB_NAMESPACE)
  69 #   undef lsearch
  70 #   define lsearch _lsearch
  71 #  endif
  72 _GL_CXXALIAS_MDA (lsearch, void *,
  73                   (const void *key, void *base, unsigned int *nmemb,
  74                    unsigned int size,
  75                    int (*compar) (const void *, const void *)));
  76 # else
  77 _GL_CXXALIAS_SYS (lsearch, void *,
  78                   (const void *key, void *base, size_t *nmemb,
  79                    size_t size,
  80                    int (*compar) (const void *, const void *)));
  81 # endif
  82 _GL_CXXALIASWARN (lsearch);
  83 #endif
  84
  85
  86 #if @GNULIB_TSEARCH@
  87 # if @REPLACE_TSEARCH@
  88 #  if !(defined __cplusplus && defined GNULIB_NAMESPACE)
  89 #   define tsearch rpl_tsearch
  90 #   define tfind rpl_tfind
  91 #   define tdelete rpl_tdelete
  92 #   define twalk rpl_twalk
  93 #  endif
  94 # endif
  95
  96 /* See <https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/search.h.html>
  97        <https://pubs.opengroup.org/onlinepubs/9699919799/functions/tsearch.html>
  98    for details.  */
  99
 100 # if !@HAVE_TYPE_VISIT@
 101 #  if !GNULIB_defined_search_types
 102 typedef enum
 103 {
 104   preorder,
 105   postorder,
 106   endorder,
 107   leaf
 108 }
 109 VISIT;
 110 #   define GNULIB_defined_search_types 1
 111 #  endif
 112 # endif
 113
 114 # ifdef __cplusplus
 115 extern "C" {
 116 # endif
 117 # if !GNULIB_defined_search_fn_types
 118 typedef int (*_gl_search_compar_fn) (const void *, const void *);
 119 typedef void (*_gl_search_action_fn) (const void *, VISIT, int);
 120 #  define GNULIB_defined_search_fn_types 1
 121 # endif
 122 # ifdef __cplusplus
 123 }
 124 # endif
 125
 126 /* Searches an element in the tree *VROOTP that compares equal to KEY.
 127    If one is found, it is returned.  Otherwise, a new element equal to KEY
 128    is inserted in the tree and is returned.  */
 129 # if @REPLACE_TSEARCH@
 130 _GL_FUNCDECL_RPL (tsearch, void *,
 131                   (const void *key, void **vrootp,
 132                    _gl_search_compar_fn compar)
 133                   _GL_ARG_NONNULL ((1, 2, 3)));
 134 _GL_CXXALIAS_RPL (tsearch, void *,
 135                   (const void *key, void **vrootp,
 136                    _gl_search_compar_fn compar));
 137 # else
 138 #  if !@HAVE_TSEARCH@
 139 _GL_FUNCDECL_SYS (tsearch, void *,
 140                   (const void *key, void **vrootp,
 141                    _gl_search_compar_fn compar)
 142                   _GL_ARG_NONNULL ((1, 2, 3)));
 143 #  endif
 144 _GL_CXXALIAS_SYS (tsearch, void *,
 145                   (const void *key, void **vrootp,
 146                    _gl_search_compar_fn compar));
 147 # endif
 148 _GL_CXXALIASWARN (tsearch);
 149
 150 /* Searches an element in the tree *VROOTP that compares equal to KEY.
 151    If one is found, it is returned.  Otherwise, NULL is returned.  */
 152 # if @REPLACE_TSEARCH@
 153 _GL_FUNCDECL_RPL (tfind, void *,
 154                   (const void *key, void *const *vrootp,
 155                    _gl_search_compar_fn compar)
 156                   _GL_ARG_NONNULL ((1, 2, 3)));
 157 _GL_CXXALIAS_RPL (tfind, void *,
 158                   (const void *key, void *const *vrootp,
 159                    _gl_search_compar_fn compar));
 160 # else
 161 #  if !@HAVE_TSEARCH@
 162 _GL_FUNCDECL_SYS (tfind, void *,
 163                   (const void *key, void *const *vrootp,
 164                    _gl_search_compar_fn compar)
 165                   _GL_ARG_NONNULL ((1, 2, 3)));
 166 #  endif
 167 /* Need to cast, because on Cygwin 1.5.x systems, the second parameter is
 168                                          void **vrootp.  */
 169 _GL_CXXALIAS_SYS_CAST (tfind, void *,
 170                        (const void *key, void *const *vrootp,
 171                         _gl_search_compar_fn compar));
 172 # endif
 173 _GL_CXXALIASWARN (tfind);
 174
 175 /* Searches an element in the tree *VROOTP that compares equal to KEY.
 176    If one is found, it is removed from the tree, and its parent node is
 177    returned.  Otherwise, NULL is returned.  */
 178 # if @REPLACE_TSEARCH@
 179 _GL_FUNCDECL_RPL (tdelete, void *,
 180                   (const void *restrict key, void **restrict vrootp,
 181                    _gl_search_compar_fn compar)
 182                   _GL_ARG_NONNULL ((1, 2, 3)));
 183 _GL_CXXALIAS_RPL (tdelete, void *,
 184                   (const void *restrict key, void **restrict vrootp,
 185                    _gl_search_compar_fn compar));
 186 # else
 187 #  if !@HAVE_TSEARCH@
 188 _GL_FUNCDECL_SYS (tdelete, void *,
 189                   (const void *restrict key, void **restrict vrootp,
 190                    _gl_search_compar_fn compar)
 191                   _GL_ARG_NONNULL ((1, 2, 3)));
 192 #  endif
 193 _GL_CXXALIAS_SYS (tdelete, void *,
 194                   (const void *restrict key, void **restrict vrootp,
 195                    _gl_search_compar_fn compar));
 196 # endif
 197 _GL_CXXALIASWARN (tdelete);
 198
 199 /* Perform a depth-first, left-to-right traversal of the tree VROOT.
 200    The ACTION function is called:
 201      - for non-leaf nodes: 3 times, before the left subtree traversal,
 202        after the left subtree traversal but before the right subtree traversal,
 203        and after the right subtree traversal,
 204      - for leaf nodes: once.
 205    The arguments passed to ACTION are:
 206      1. the node; it can be cast to a 'const void * const *', i.e. into a
 207         pointer to the key,
 208      2. an indicator which visit of the node this is,
 209      3. the level of the node in the tree (0 for the root).  */
 210 # if @REPLACE_TSEARCH@
 211 _GL_FUNCDECL_RPL (twalk, void,
 212                   (const void *vroot, _gl_search_action_fn action)
 213                   _GL_ARG_NONNULL ((2)));
 214 _GL_CXXALIAS_RPL (twalk, void,
 215                   (const void *vroot, _gl_search_action_fn action));
 216 # else
 217 #  if !@HAVE_TWALK@
 218 _GL_FUNCDECL_SYS (twalk, void,
 219                   (const void *vroot, _gl_search_action_fn action)
 220                   _GL_ARG_NONNULL ((2)));
 221 #  endif
 222 _GL_CXXALIAS_SYS (twalk, void,
 223                   (const void *vroot, _gl_search_action_fn action));
 224 # endif
 225 _GL_CXXALIASWARN (twalk);
 226
 227 /* Flags used by tsearch.c.  */
 228 # define GNULIB_defined_tsearch  (@REPLACE_TSEARCH@ || !@HAVE_TSEARCH@)
 229 # define GNULIB_defined_twalk    (@REPLACE_TSEARCH@ || !@HAVE_TWALK@)
 230
 231 #elif defined GNULIB_POSIXCHECK
 232 # undef tsearch
 233 # if HAVE_RAW_DECL_TSEARCH
 234 _GL_WARN_ON_USE (tsearch, "tsearch is unportable - "
 235                  "use gnulib module tsearch for portability");
 236 # endif
 237 # undef tfind
 238 # if HAVE_RAW_DECL_TFIND
 239 _GL_WARN_ON_USE (tfind, "tfind is unportable - "
 240                  "use gnulib module tsearch for portability");
 241 # endif
 242 # undef tdelete
 243 # if HAVE_RAW_DECL_TDELETE
 244 _GL_WARN_ON_USE (tdelete, "tdelete is unportable - "
 245                  "use gnulib module tsearch for portability");
 246 # endif
 247 # undef twalk
 248 # if HAVE_RAW_DECL_TWALK
 249 _GL_WARN_ON_USE (twalk, "twalk is unportable - "
 250                  "use gnulib module tsearch for portability");
 251 # endif
 252 #endif
 253
 254
 255 #endif /* _@GUARD_PREFIX@_SEARCH_H */
 256 #endif /* _@GUARD_PREFIX@_SEARCH_H */