lib/search.in.h

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