lib/search.in.h

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