lib/search.in.h

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