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