lib/search.in.h

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