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