1 /* A GNU-like <search.h>.
2
3 Copyright (C) 2007-2023 Free Software Foundation, Inc.
4
5 This file is free software: you can redistribute it and/or modify
6 it under the terms of the GNU Lesser General Public License as
7 published by the Free Software Foundation; either version 2.1 of the
8 License, or (at your option) any later version.
9
10 This file 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 Lesser General Public License for more details.
14
15 You should have received a copy of the GNU Lesser General Public License
16 along with this program. If not, see <https://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 /* This file uses GNULIB_POSIXCHECK, HAVE_RAW_DECL_*. */
34 #if !_GL_CONFIG_H_INCLUDED
35 #error "Please include config.h first."
36 #endif
37
38
39 /* The definitions of _GL_FUNCDECL_RPL etc. are copied here. */
40
41 /* The definition of _GL_ARG_NONNULL is copied here. */
42
43 /* The definition of _GL_WARN_ON_USE is copied here. */
44
45
46 #ifdef __cplusplus
47 extern "C" {
48 #endif
49 #if !GNULIB_defined_lsearch_fn_types
50 typedef int (*_gl_lsearch_compar_fn) (const void *, const void *);
51 # define GNULIB_defined_lsearch_fn_types 1
52 #endif
53 #ifdef __cplusplus
54 }
55 #endif
56
57 #if @GNULIB_MDA_LFIND@
58 /* On native Windows, map 'lfind' to '_lfind', so that -loldnames is not
59 required. In C++ with GNULIB_NAMESPACE, avoid differences between
60 platforms by defining GNULIB_NAMESPACE::lfind always. */
61 # if defined _WIN32 && !defined __CYGWIN__
62 # if !(defined __cplusplus && defined GNULIB_NAMESPACE)
63 # undef lfind
64 # define lfind _lfind
65 # endif
66 _GL_CXXALIAS_MDA (lfind, void *,
67 (const void *key, const void *base, unsigned int *nmemb,
68 unsigned int size,
69 _gl_lsearch_compar_fn compar));
70 # else
71 _GL_CXXALIAS_SYS (lfind, void *,
72 (const void *key, const void *base, size_t *nmemb,
73 size_t size,
74 _gl_lsearch_compar_fn compar));
75 # endif
76 _GL_CXXALIASWARN (lfind);
77 #endif
78
79 #if @GNULIB_MDA_LSEARCH@
80 /* On native Windows, map 'lsearch' to '_lsearch', so that -loldnames is not
81 required. In C++ with GNULIB_NAMESPACE, avoid differences between
82 platforms by defining GNULIB_NAMESPACE::lsearch always. */
83 # if defined _WIN32 && !defined __CYGWIN__
84 # if !(defined __cplusplus && defined GNULIB_NAMESPACE)
85 # undef lsearch
86 # define lsearch _lsearch
87 # endif
88 _GL_CXXALIAS_MDA (lsearch, void *,
89 (const void *key, void *base, unsigned int *nmemb,
90 unsigned int size,
91 _gl_lsearch_compar_fn compar));
92 # else
93 _GL_CXXALIAS_SYS (lsearch, void *,
94 (const void *key, void *base, size_t *nmemb,
95 size_t size,
96 _gl_lsearch_compar_fn compar));
97 # endif
98 _GL_CXXALIASWARN (lsearch);
99 #endif
100
101
102 #if @GNULIB_TSEARCH@
103 # if @REPLACE_TSEARCH@
104 # if !(defined __cplusplus && defined GNULIB_NAMESPACE)
105 # define tsearch rpl_tsearch
106 # define tfind rpl_tfind
107 # define tdelete rpl_tdelete
108 # endif
109 # endif
110 # if @REPLACE_TWALK@
111 # if !(defined __cplusplus && defined GNULIB_NAMESPACE)
112 # define twalk rpl_twalk
113 # endif
114 # endif
115
116 /* See <https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/search.h.html>
117 <https://pubs.opengroup.org/onlinepubs/9699919799/functions/tsearch.html>
118 for details. */
119
120 # if !@HAVE_TYPE_VISIT@
121 # if !GNULIB_defined_search_types
122 typedef enum
123 {
124 preorder,
125 postorder,
126 endorder,
127 leaf
128 }
129 VISIT;
130 # define GNULIB_defined_search_types 1
131 # endif
132 # endif
133
134 # ifdef __cplusplus
135 extern "C" {
136 # endif
137 # if !GNULIB_defined_search_fn_types
138 typedef int (*_gl_search_compar_fn) (const void *, const void *);
139 typedef void (*_gl_search_action_fn) (const void *, VISIT, int);
140 # define GNULIB_defined_search_fn_types 1
141 # endif
142 # ifdef __cplusplus
143 }
144 # endif
145
146 /* Searches an element in the tree *VROOTP that compares equal to KEY.
147 If one is found, it is returned. Otherwise, a new element equal to KEY
148 is inserted in the tree and is returned. */
149 # if @REPLACE_TSEARCH@
150 _GL_FUNCDECL_RPL (tsearch, void *,
151 (const void *key, void **vrootp,
152 _gl_search_compar_fn compar)
153 _GL_ARG_NONNULL ((1, 2, 3)));
154 _GL_CXXALIAS_RPL (tsearch, void *,
155 (const void *key, void **vrootp,
156 _gl_search_compar_fn compar));
157 # else
158 # if !@HAVE_TSEARCH@
159 _GL_FUNCDECL_SYS (tsearch, void *,
160 (const void *key, void **vrootp,
161 _gl_search_compar_fn compar)
162 _GL_ARG_NONNULL ((1, 2, 3)));
163 # endif
164 _GL_CXXALIAS_SYS (tsearch, void *,
165 (const void *key, void **vrootp,
166 _gl_search_compar_fn compar));
167 # endif
168 # if __GLIBC__ >= 2
169 _GL_CXXALIASWARN (tsearch);
170 # endif
171
172 /* Searches an element in the tree *VROOTP that compares equal to KEY.
173 If one is found, it is returned. Otherwise, NULL is returned. */
174 # if @REPLACE_TSEARCH@
175 _GL_FUNCDECL_RPL (tfind, void *,
176 (const void *key, void *const *vrootp,
177 _gl_search_compar_fn compar)
178 _GL_ARG_NONNULL ((1, 2, 3)));
179 _GL_CXXALIAS_RPL (tfind, void *,
180 (const void *key, void *const *vrootp,
181 _gl_search_compar_fn compar));
182 # else
183 # if !@HAVE_TSEARCH@
184 _GL_FUNCDECL_SYS (tfind, void *,
185 (const void *key, void *const *vrootp,
186 _gl_search_compar_fn compar)
187 _GL_ARG_NONNULL ((1, 2, 3)));
188 # endif
189 /* Need to cast, because on Cygwin 1.5.x systems, the second parameter is
190 void **vrootp. */
191 _GL_CXXALIAS_SYS_CAST (tfind, void *,
192 (const void *key, void *const *vrootp,
193 _gl_search_compar_fn compar));
194 # endif
195 # if __GLIBC__ >= 2
196 _GL_CXXALIASWARN (tfind);
197 # endif
198
199 /* Searches an element in the tree *VROOTP that compares equal to KEY.
200 If one is found, it is removed from the tree, and its parent node is
201 returned. Otherwise, NULL is returned. */
202 # if @REPLACE_TSEARCH@
203 _GL_FUNCDECL_RPL (tdelete, void *,
204 (const void *restrict key, void **restrict vrootp,
205 _gl_search_compar_fn compar)
206 _GL_ARG_NONNULL ((1, 2, 3)));
207 _GL_CXXALIAS_RPL (tdelete, void *,
208 (const void *restrict key, void **restrict vrootp,
209 _gl_search_compar_fn compar));
210 # else
211 # if !@HAVE_TSEARCH@
212 _GL_FUNCDECL_SYS (tdelete, void *,
213 (const void *restrict key, void **restrict vrootp,
214 _gl_search_compar_fn compar)
215 _GL_ARG_NONNULL ((1, 2, 3)));
216 # endif
217 _GL_CXXALIAS_SYS (tdelete, void *,
218 (const void *restrict key, void **restrict vrootp,
219 _gl_search_compar_fn compar));
220 # endif
221 # if __GLIBC__ >= 2
222 _GL_CXXALIASWARN (tdelete);
223 # endif
224
225 /* Perform a depth-first, left-to-right traversal of the tree VROOT.
226 The ACTION function is called:
227 - for non-leaf nodes: 3 times, before the left subtree traversal,
228 after the left subtree traversal but before the right subtree traversal,
229 and after the right subtree traversal,
230 - for leaf nodes: once.
231 The arguments passed to ACTION are:
232 1. the node; it can be cast to a 'const void * const *', i.e. into a
233 pointer to the key,
234 2. an indicator which visit of the node this is,
235 3. the level of the node in the tree (0 for the root). */
236 # if @REPLACE_TWALK@
237 _GL_FUNCDECL_RPL (twalk, void,
238 (const void *vroot, _gl_search_action_fn action)
239 _GL_ARG_NONNULL ((2)));
240 _GL_CXXALIAS_RPL (twalk, void,
241 (const void *vroot, _gl_search_action_fn action));
242 # else
243 # if !@HAVE_TWALK@
244 _GL_FUNCDECL_SYS (twalk, void,
245 (const void *vroot, _gl_search_action_fn action)
246 _GL_ARG_NONNULL ((2)));
247 # endif
248 _GL_CXXALIAS_SYS (twalk, void,
249 (const void *vroot, _gl_search_action_fn action));
250 # endif
251 # if __GLIBC__ >= 2
252 _GL_CXXALIASWARN (twalk);
253 # endif
254
255 /* Flags used by tsearch.c. */
256 # define GNULIB_defined_tsearch (@REPLACE_TSEARCH@ || !@HAVE_TSEARCH@)
257 # define GNULIB_defined_twalk (@REPLACE_TWALK@ || !@HAVE_TWALK@)
258
259 #elif defined GNULIB_POSIXCHECK
260 # undef tsearch
261 # if HAVE_RAW_DECL_TSEARCH
262 _GL_WARN_ON_USE (tsearch, "tsearch is unportable - "
263 "use gnulib module tsearch for portability");
264 # endif
265 # undef tfind
266 # if HAVE_RAW_DECL_TFIND
267 _GL_WARN_ON_USE (tfind, "tfind is unportable - "
268 "use gnulib module tsearch for portability");
269 # endif
270 # undef tdelete
271 # if HAVE_RAW_DECL_TDELETE
272 _GL_WARN_ON_USE (tdelete, "tdelete is unportable - "
273 "use gnulib module tsearch for portability");
274 # endif
275 # undef twalk
276 # if HAVE_RAW_DECL_TWALK
277 _GL_WARN_ON_USE (twalk, "twalk is unportable - "
278 "use gnulib module tsearch for portability");
279 # endif
280 #endif
281
282
283 #endif /* _@GUARD_PREFIX@_SEARCH_H */
284 #endif /* _@GUARD_PREFIX@_SEARCH_H */