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 definition of GL_LINK_WARNING is copied here.  */
  33
  34 /* The definition of _GL_ARG_NONNULL is copied here.  */
  35
  36
  37 #ifdef __cplusplus
  38 extern "C" {
  39 #endif
  40
  41
  42 #if @GNULIB_TSEARCH@
  43 # if @REPLACE_TSEARCH@
  44 #  define tsearch rpl_tsearch
  45 #  define tfind rpl_tfind
  46 #  define tdelete rpl_tdelete
  47 #  define twalk rpl_twalk
  48 # endif
  49 # if !@HAVE_TSEARCH@ || @REPLACE_TSEARCH@
  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 /* Searches an element in the tree *VROOTP that compares equal to KEY.
  67    If one is found, it is returned.  Otherwise, a new element equal to KEY
  68    is inserted in the tree and is returned.  */
  69 extern void * tsearch (const void *key, void **vrootp,
  70                        int (*compar) (const void *, const void *))
  71      _GL_ARG_NONNULL ((1, 2, 3));
  72
  73 /* Searches an element in the tree *VROOTP that compares equal to KEY.
  74    If one is found, it is returned.  Otherwise, NULL is returned.  */
  75 extern void * tfind (const void *key, void *const *vrootp,
  76                      int (*compar) (const void *, const void *))
  77      _GL_ARG_NONNULL ((1, 2, 3));
  78
  79 /* Searches an element in the tree *VROOTP that compares equal to KEY.
  80    If one is found, it is removed from the tree, and its parent node is
  81    returned.  Otherwise, NULL is returned.  */
  82 extern void * tdelete (const void *key, void **vrootp,
  83                        int (*compar) (const void *, const void *))
  84      _GL_ARG_NONNULL ((1, 2, 3));
  85
  86 /* Perform a depth-first, left-to-right traversal of the tree VROOT.
  87    The ACTION function is called:
  88      - for non-leaf nodes: 3 times, before the left subtree traversal,
  89        after the left subtree traversal but before the right subtree traversal,
  90        and after the right subtree traversal,
  91      - for leaf nodes: once.
  92    The arguments passed to ACTION are:
  93      1. the node; it can be casted to a 'const void * const *', i.e. into a
  94         pointer to the key,
  95      2. an indicator which visit of the node this is,
  96      3. the level of the node in the tree (0 for the root).  */
  97 extern void twalk (const void *vroot,
  98                    void (*action) (const void *, VISIT, int))
  99      _GL_ARG_NONNULL ((2));
 100
 101 # endif
 102 #elif defined GNULIB_POSIXCHECK
 103 # undef tsearch
 104 # define tsearch(k,v,c) \
 105     (GL_LINK_WARNING ("tsearch is unportable - " \
 106                       "use gnulib module tsearch for portability"), \
 107      tsearch (k, v, c))
 108 # undef tfind
 109 # define tfind(k,v,c) \
 110     (GL_LINK_WARNING ("tfind is unportable - " \
 111                       "use gnulib module tsearch for portability"), \
 112      tfind (k, v, c))
 113 # undef tdelete
 114 # define tdelete(k,v,c) \
 115     (GL_LINK_WARNING ("tdelete is unportable - " \
 116                       "use gnulib module tsearch for portability"), \
 117      tdelete (k, v, c))
 118 # undef twalk
 119 # define twalk(v,a) \
 120     (GL_LINK_WARNING ("twalk is unportable - " \
 121                       "use gnulib module tsearch for portability"), \
 122      twalk (v, a))
 123 #endif
 124
 125
 126 #ifdef __cplusplus
 127 }
 128 #endif
 129
 130 #endif /* _GL_SEARCH_H */
 131 #endif /* _GL_SEARCH_H */