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