Context Navigation

source: trunk/src/lib/nt/fts-nt.c@ 3680

Last change on this file since 3680 was 3535, checked in by bird, 4 years ago
nt/fts-nt.c+h: A couple of tweaks to make grep happy.
Property svn:eol-style set to `native` Property svn:keywords set to `Id`
File size: 38.9 KB

Line
1	/* $Id: fts-nt.c 3535 2021-12-20 23:32:28Z bird $ */
2	/** @file
3	* Source for the NT port of BSD fts.c.
4	*
5	* @copyright 1990, 1993, 1994 The Regents of the University of California. All rights reserved.
6	* @copyright NT modifications Copyright (C) 2016 knut st. osmundsen <bird-klibc-spam-xiv@anduin.net>
7	* @licenses BSD3
8	*
9	*
10	* Some hints about how the code works.
11	*
12	* The input directories & files are entered into a pseudo root directory and
13	* processed one after another, depth first.
14	*
15	* Directories are completely read into memory first and arranged as linked
16	* list anchored on FTS::fts_cur. fts_read does a pop-like operation on that
17	* list, freeing the nodes after they've been completely processed.
18	* Subdirectories are returned twice by fts_read, the first time when it
19	* decends into it (FTS_D), and the second time as it ascends from it (FTS_DP).
20	*
21	* In parallel to fts_read, there's the fts_children API that fetches the
22	* directory content in a similar manner, but for the consumption of the API
23	* caller rather than FTS itself. The result hangs on FTS::fts_child so it can
24	* be freed when the directory changes or used by fts_read when it is called
25	* upon to enumerate the directory.
26	*
27	*
28	* The NT port of the code does away with the directory changing in favor of
29	* using directory relative opens (present in NT since for ever, just not
30	* exposed thru Win32). A new FTSENT member fts_dirfd has been added to make
31	* this possible for API users too.
32	*
33	* Note! When using Win32 APIs with path input relative to the current
34	* directory, the internal DOS <-> NT path converter will expand it to a
35	* full path and subject it to the 260 char limit.
36	*
37	* The richer NT directory enumeration API allows us to do away with all the
38	* stat() calls, and not have to do link counting and other interesting things
39	* to try speed things up. (You typical stat() implementation on windows is
40	* actually a directory enum call with the name of the file as filter.)
41	*/
42
43	/*-
44	* Copyright (c) 1990, 1993, 1994
45	* The Regents of the University of California. All rights reserved.
46	*
47	* Redistribution and use in source and binary forms, with or without
48	* modification, are permitted provided that the following conditions
49	* are met:
50	* 1. Redistributions of source code must retain the above copyright
51	* notice, this list of conditions and the following disclaimer.
52	* 2. Redistributions in binary form must reproduce the above copyright
53	* notice, this list of conditions and the following disclaimer in the
54	* documentation and/or other materials provided with the distribution.
55	* 4. Neither the name of the University nor the names of its contributors
56	* may be used to endorse or promote products derived from this software
57	* without specific prior written permission.
58	*
59	* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
60	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
61	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
62	* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
63	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
64	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
65	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
66	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
67	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
68	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
69	* SUCH DAMAGE.
70	*
71	* $OpenBSD: fts.c,v 1.22 1999/10/03 19:22:22 millert Exp $
72	*/
73
74	#if 0
75	#if defined(LIBC_SCCS) && !defined(lint)
76	static char sccsid[] = "@(#)fts.c 8.6 (Berkeley) 8/14/94";
77	#endif /* LIBC_SCCS and not lint */
78	#endif
79
80	#include <errno.h>
81	#include "fts-nt.h"
82	#include <stdlib.h>
83	#include <string.h>
84	#include <assert.h>
85	#include "nthlp.h"
86	#include "ntdir.h"
87	#include "ntopenat.h" /* for AT_FDCWD */
88	#include <stdio.h>//debug
89
90	static FTSENT fts_alloc(FTS sp, char const name, size_t namelen, wchar_t const wcsname, size_t cwcname);
91	static FTSENT fts_alloc_ansi(FTS sp, char const *name, size_t namelen);
92	static FTSENT fts_alloc_utf16(FTS sp, wchar_t const *wcsname, size_t cwcname);
93	static void nt_fts_free_alloc_cache(FTS *sp);
94	static FTSENT fts_build(FTS , int);
95	static void fts_lfree(FTSENT *);
96	static void fts_load(FTS , FTSENT );
97	static size_t fts_maxarglen(char * const *);
98	static size_t fts_maxarglenw(wchar_t * const *);
99	static void fts_padjust(FTS , FTSENT );
100	static void fts_padjustw(FTS , FTSENT );
101	static int fts_palloc(FTS *, size_t, size_t);
102	static FTSENT fts_sort(FTS , FTSENT *, size_t);
103	static int fts_stat(FTS , FTSENT , int, HANDLE);
104	static int fts_process_stats(FTSENT , BirdStat_T const );
105
106	#define ISDOT(a) (a[0] == '.' && (!a[1] \|\| (a[1] == '.' && !a[2])))
107
108	#define CLR(opt) (sp->fts_options &= ~(opt))
109	#define ISSET(opt) (sp->fts_options & (opt))
110	#define SET(opt) (sp->fts_options \|= (opt))
111
112	/* fts_build flags */
113	#define BCHILD 1 /* fts_children */
114	#define BNAMES 2 /* fts_children, names only */
115	#define BREAD 3 /* fts_read */
116
117	/* NT needs these: */
118	#define MAXPATHLEN 260
119	#define MAX(a, b) ( (a) >= (b) ? (a) : (b) )
120
121	/** Enables BirdDir_T reuse. (Saves malloc and free calls.) */
122	#define FTS_WITH_DIRHANDLE_REUSE
123	/** Enables allocation statistics. */
124	//#define FTS_WITH_STATISTICS
125	/** Enables FTSENT allocation cache. */
126	#define FTS_WITH_ALLOC_CACHE
127	/** Number of size buckets for the FTSENT allocation cache. */
128	#define FTS_NUM_FREE_BUCKETS 64
129	/** Shift for converting size to free bucket index. */
130	#define FTS_FREE_BUCKET_SHIFT 4
131	/** The FTSENT allocation alignment. */
132	#define FTS_ALIGN_FTSENT (1U << FTS_FREE_BUCKET_SHIFT)
133
134	/*
135	* Internal representation of an FTS, including extra implementation
136	* details. The FTS returned from fts_open points to this structure's
137	* ftsp_fts member (and can be cast to an _fts_private as required)
138	*/
139	struct _fts_private {
140	FTS ftsp_fts;
141	#ifdef FTS_WITH_DIRHANDLE_REUSE
142	/** Statically allocate directory handle. */
143	BirdDir_T dirhandle;
144	#endif
145	#ifdef FTS_WITH_ALLOC_CACHE
146	/** Number of free entries in the above buckets. */
147	size_t numfree;
148	# ifdef FTS_WITH_STATISTICS
149	size_t allocs;
150	size_t hits;
151	size_t misses;
152	# endif
153	/** Free FTSENT buckets (by size).
154	* This is to avoid hitting the heap, which is a little sluggish on windows. */
155	struct
156	{
157	FTSENT *head;
158	} freebuckets[FTS_NUM_FREE_BUCKETS];
159	#endif
160	};
161
162
163	static FTS * FTSCALL
164	nt_fts_open_common(char * const argv, wchar_t const *wcsargv, int options,
165	int (compar)(const FTSENT const , const FTSENT const *))
166	{
167	struct _fts_private *priv;
168	FTS *sp;
169	FTSENT p, root;
170	FTSENT parent, tmp;
171	size_t len, nitems;
172
173	birdResolveImports();
174
175	/* Options check. */
176	if (options & ~FTS_OPTIONMASK) {
177	errno = EINVAL;
178	return (NULL);
179	}
180
181	/* fts_open() requires at least one path */
182	if (wcsargv ? wcsargv == NULL : argv == NULL) {
183	errno = EINVAL;
184	return (NULL);
185	}
186
187	/* Allocate/initialize the stream. */
188	if ((priv = calloc(1, sizeof(*priv))) == NULL)
189	return (NULL);
190	sp = &priv->ftsp_fts;
191	sp->fts_compar = compar;
192	sp->fts_options = options;
193	SET(FTS_NOCHDIR); /* NT: FTS_NOCHDIR is always on (for external consumes) */
194	sp->fts_cwd_fd = AT_FDCWD;
195
196	/* Shush, GCC. */
197	tmp = NULL;
198
199	/*
200	* Start out with 1K of path space, and enough, in any case,
201	* to hold the user's paths.
202	*/
203	if (fts_palloc(sp, MAX(argv ? fts_maxarglen(argv) : 1, MAXPATHLEN),
204	MAX(wcsargv ? fts_maxarglenw(wcsargv) : 1, MAXPATHLEN)) )
205	goto mem1;
206
207	/* Allocate/initialize root's parent. */
208	if ((parent = fts_alloc(sp, NULL, 0, NULL, 0)) == NULL)
209	goto mem2;
210	parent->fts_level = FTS_ROOTPARENTLEVEL;
211
212	/* Allocate/initialize root(s). */
213	for (root = NULL, nitems = 0; wcsargv ? wcsargv != NULL : argv != NULL; ++nitems) {
214	/* NT: We need to do some small input transformations to make this and
215	the API user code happy. 1. Lone drive letters get a dot
216	appended so it won't matter if a slash is appended afterwards.
217	2. DOS slashes are converted to UNIX ones. */
218	wchar_t *wcslash;
219
220	if (wcsargv) {
221	len = wcslen(*wcsargv);
222	if (len == 2 && wcsargv[0][1] == ':') {
223	wchar_t wcsdrive[4];
224	wcsdrive[0] = wcsargv[0][0];
225	wcsdrive[1] = ':';
226	wcsdrive[2] = '.';
227	wcsdrive[3] = '\0';
228	p = fts_alloc_utf16(sp, wcsdrive, 3);
229	} else {
230	p = fts_alloc_utf16(sp, *wcsargv, len);
231	}
232	wcsargv++;
233	} else {
234	len = strlen(*argv);
235	if (len == 2 && argv[0][1] == ':') {
236	char szdrive[4];
237	szdrive[0] = argv[0][0];
238	szdrive[1] = ':';
239	szdrive[2] = '.';
240	szdrive[3] = '\0';
241	p = fts_alloc_ansi(sp, szdrive, 3);
242	} else {
243	p = fts_alloc_ansi(sp, *argv, len);
244	}
245	argv++;
246	}
247	if (p != NULL) { /* likely */ } else { goto mem3; }
248
249	wcslash = wcschr(p->fts_wcsname, '\\');
250	while (wcslash != NULL) {
251	*wcslash++ = '/';
252	wcslash = wcschr(p->fts_wcsname, '\\');
253	}
254
255	if (p->fts_name) {
256	char *slash = strchr(p->fts_name, '\\');
257	while (slash != NULL) {
258	*slash++ = '/';
259	slash = strchr(p->fts_name, '\\');
260	}
261	}
262
263	p->fts_level = FTS_ROOTLEVEL;
264	p->fts_parent = parent;
265	p->fts_accpath = p->fts_name;
266	p->fts_wcsaccpath = p->fts_wcsname;
267	p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW), INVALID_HANDLE_VALUE);
268
269	/* Command-line "." and ".." are real directories. */
270	if (p->fts_info == FTS_DOT)
271	p->fts_info = FTS_D;
272
273	/*
274	* If comparison routine supplied, traverse in sorted
275	* order; otherwise traverse in the order specified.
276	*/
277	if (compar) {
278	p->fts_link = root;
279	root = p;
280	} else {
281	p->fts_link = NULL;
282	if (root == NULL)
283	tmp = root = p;
284	else {
285	tmp->fts_link = p;
286	tmp = p;
287	}
288	}
289	}
290	if (compar && nitems > 1)
291	root = fts_sort(sp, root, nitems);
292
293	/*
294	* Allocate a dummy pointer and make fts_read think that we've just
295	* finished the node before the root(s); set p->fts_info to FTS_INIT
296	* so that everything about the "current" node is ignored.
297	*/
298	if ((sp->fts_cur = fts_alloc(sp, NULL, 0, NULL, 0)) == NULL)
299	goto mem3;
300	sp->fts_cur->fts_link = root;
301	sp->fts_cur->fts_info = FTS_INIT;
302
303	return (sp);
304
305	mem3:
306	fts_lfree(root);
307	free(parent);
308	mem2:
309	free(sp->fts_path);
310	free(sp->fts_wcspath);
311	mem1:
312	free(sp);
313	return (NULL);
314	}
315
316
317	FTS * FTSCALL
318	nt_fts_open(char * const *argv, int options,
319	int (compar)(const FTSENT const , const FTSENT const *))
320	{
321	return nt_fts_open_common(argv, NULL, options, compar);
322	}
323
324
325	FTS * FTSCALL
326	nt_fts_openw(wchar_t * const *argv, int options,
327	int (compar)(const FTSENT const , const FTSENT const *))
328	{
329	return nt_fts_open_common(NULL, argv, options, compar);
330	}
331
332
333	/**
334	* Called by fts_read for FTS_ROOTLEVEL entries only.
335	*/
336	static void
337	fts_load(FTS sp, FTSENT p)
338	{
339	size_t len;
340	wchar_t *pwc;
341
342	/*
343	* Load the stream structure for the next traversal. Since we don't
344	* actually enter the directory until after the preorder visit, set
345	* the fts_accpath field specially so the chdir gets done to the right
346	* place and the user can access the first node. From fts_open it's
347	* known that the path will fit.
348	*/
349	if (!(sp->fts_options & FTS_NO_ANSI)) {
350	char *cp;
351	len = p->fts_pathlen = p->fts_namelen;
352	memmove(sp->fts_path, p->fts_name, len + 1);
353	cp = strrchr(p->fts_name, '/');
354	if (cp != NULL && (cp != p->fts_name \|\| cp[1])) {
355	len = strlen(++cp);
356	memmove(p->fts_name, cp, len + 1);
357	p->fts_namelen = len;
358	}
359	p->fts_accpath = p->fts_path = sp->fts_path;
360	}
361
362	len = p->fts_cwcpath = p->fts_cwcname;
363	memmove(sp->fts_wcspath, p->fts_wcsname, (len + 1) * sizeof(wchar_t));
364	pwc = wcsrchr(p->fts_wcsname, '/');
365	if (pwc != NULL && (pwc != p->fts_wcsname \|\| pwc[1])) {
366	len = wcslen(++pwc);
367	memmove(p->fts_wcsname, pwc, (len + 1) * sizeof(wchar_t));
368	p->fts_cwcname = len;
369	}
370	p->fts_wcsaccpath = p->fts_wcspath = sp->fts_wcspath;
371
372	sp->fts_dev = p->fts_dev;
373	}
374
375
376	int FTSCALL
377	nt_fts_close(FTS *sp)
378	{
379	FTSENT freep, p;
380	/int saved_errno;/
381
382	/*
383	* This still works if we haven't read anything -- the dummy structure
384	* points to the root list, so we step through to the end of the root
385	* list which has a valid parent pointer.
386	*/
387	if (sp->fts_cur) {
388	for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
389	freep = p;
390	p = p->fts_link != NULL ? p->fts_link : p->fts_parent;
391	free(freep);
392	}
393	free(p);
394	}
395
396	/* Free up child linked list, sort array, path buffer. */
397	if (sp->fts_child)
398	fts_lfree(sp->fts_child);
399	if (sp->fts_array)
400	free(sp->fts_array);
401	free(sp->fts_path);
402	free(sp->fts_wcspath);
403	#ifdef FTS_WITH_ALLOC_CACHE
404	# ifdef FTS_WITH_STATISTICS
405	{
406	struct _fts_private priv = (struct _fts_private )sp;
407	fprintf(stderr, "numfree=%u allocs=%u hits=%u (%uppt) misses=%u (%uppt) other=%u\n",
408	priv->numfree, priv->allocs,
409	priv->hits, (unsigned)((double)priv->hits * 1000.0 / priv->allocs),
410	priv->misses, (unsigned)((double)priv->misses * 1000.0 / priv->allocs),
411	priv->allocs - priv->misses - priv->hits);
412	}
413	# endif
414	#endif
415	nt_fts_free_alloc_cache(sp);
416	#ifdef FTS_WITH_DIRHANDLE_REUSE
417	birdDirClose(&((struct _fts_private *)sp)->dirhandle);
418	#endif
419
420	/* Free up the stream pointer. */
421	free(sp);
422	return (0);
423	}
424
425
426	/**
427	* Frees a FTSENT structure by way of the allocation cache.
428	*/
429	static void
430	fts_free_entry(FTS sp, FTSENT tmp)
431	{
432	if (tmp != NULL) {
433	struct _fts_private priv = (struct _fts_private )sp;
434	#ifdef FTS_WITH_ALLOC_CACHE
435	size_t idx;
436	#endif
437
438	if (tmp->fts_dirfd == INVALID_HANDLE_VALUE) {
439	/* There are probably more files than directories out there. */
440	} else {
441	birdCloseFile(tmp->fts_dirfd);
442	tmp->fts_dirfd = INVALID_HANDLE_VALUE;
443	}
444
445	#ifdef FTS_WITH_ALLOC_CACHE
446	idx = (tmp->fts_alloc_size - sizeof(FTSENT)) >> FTS_FREE_BUCKET_SHIFT;
447	if (idx < FTS_NUM_FREE_BUCKETS) {
448	tmp->fts_link = priv->freebuckets[idx].head;
449	priv->freebuckets[idx].head = tmp;
450	} else {
451	tmp->fts_link = priv->freebuckets[FTS_NUM_FREE_BUCKETS - 1].head;
452	priv->freebuckets[FTS_NUM_FREE_BUCKETS - 1].head = tmp;
453	}
454
455	priv->numfree++;
456	#else
457	free(tmp);
458	#endif
459	}
460	}
461
462
463	/*
464	* Special case of "/" at the end of the path so that slashes aren't
465	* appended which would cause paths to be written as "....//foo".
466	*/
467	#define NAPPEND(p) ( p->fts_pathlen - (p->fts_path[p->fts_pathlen - 1] == '/') )
468	#define NAPPENDW(p) ( p->fts_cwcpath - (p->fts_wcspath[p->fts_cwcpath - 1] == L'/') )
469
470	FTSENT * FTSCALL
471	nt_fts_read(FTS *sp)
472	{
473	FTSENT p, tmp;
474	int instr;
475	wchar_t *pwc;
476
477	/* Set current node pointer. */
478	p = sp->fts_cur;
479
480	/* If finished or unrecoverable error, return NULL. */
481	if (p != NULL && !ISSET(FTS_STOP)) {
482	/* likely */
483	} else {
484	return (NULL);
485	}
486
487	/* Save and zero out user instructions. */
488	instr = p->fts_instr;
489	p->fts_instr = FTS_NOINSTR;
490
491	/* Any type of file may be re-visited; re-stat and re-turn. */
492	if (instr != FTS_AGAIN) {
493	/* likely */
494	} else {
495	p->fts_info = fts_stat(sp, p, 0, INVALID_HANDLE_VALUE);
496	return (p);
497	}
498
499	/*
500	* Following a symlink -- SLNONE test allows application to see
501	* SLNONE and recover. If indirecting through a symlink, have
502	* keep a pointer to current location. If unable to get that
503	* pointer, follow fails.
504	*
505	* NT: Since we don't change directory, we just set FTS_SYMFOLLOW
506	* here in case a API client checks it.
507	*/
508	if ( instr != FTS_FOLLOW
509	\|\| (p->fts_info != FTS_SL && p->fts_info != FTS_SLNONE)) {
510	/* likely */
511	} else {
512	p->fts_info = fts_stat(sp, p, 1, INVALID_HANDLE_VALUE);
513	if (p->fts_info == FTS_D /&& !ISSET(FTS_NOCHDIR)/) {
514	p->fts_flags \|= FTS_SYMFOLLOW;
515	}
516	return (p);
517	}
518
519	/* Directory in pre-order. */
520	if (p->fts_info == FTS_D) {
521	/* If skipped or crossed mount point, do post-order visit. */
522	if ( instr == FTS_SKIP
523	\|\| (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) {
524	if (sp->fts_child) {
525	fts_lfree(sp->fts_child);
526	sp->fts_child = NULL;
527	}
528	p->fts_info = FTS_DP;
529	return (p);
530	}
531
532	/* Rebuild if only read the names and now traversing. */
533	if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
534	CLR(FTS_NAMEONLY);
535	fts_lfree(sp->fts_child);
536	sp->fts_child = NULL;
537	}
538
539	/*
540	* Cd to the subdirectory.
541	*
542	* If have already read and now fail to chdir, whack the list
543	* to make the names come out right, and set the parent errno
544	* so the application will eventually get an error condition.
545	* Set the FTS_DONTCHDIR flag so that when we logically change
546	* directories back to the parent we don't do a chdir.
547	*
548	* If haven't read do so. If the read fails, fts_build sets
549	* FTS_STOP or the fts_info field of the node.
550	*/
551	if (sp->fts_child == NULL) {
552	p = fts_build(sp, BREAD);
553	if (p != NULL) {
554	/* likely */
555	} else {
556	if (ISSET(FTS_STOP))
557	return (NULL);
558	return sp->fts_cur;
559	}
560
561	} else {
562	p = sp->fts_child;
563	sp->fts_child = NULL;
564	}
565	goto name;
566	}
567
568	/* Move to the next node on this level. */
569	next: tmp = p;
570	if ((p = p->fts_link) != NULL) {
571	/*
572	* If reached the top, return to the original directory (or
573	* the root of the tree), and load the paths for the next root.
574	*/
575	if (p->fts_level != FTS_ROOTLEVEL) {
576	/* likely */
577	} else {
578	fts_free_entry(sp, tmp);
579	fts_load(sp, p);
580	return (sp->fts_cur = p);
581	}
582
583	/*
584	* User may have called fts_set on the node. If skipped,
585	* ignore. If followed, get a file descriptor so we can
586	* get back if necessary.
587	*/
588	if (p->fts_instr != FTS_SKIP) {
589	/* likely */
590	} else {
591	fts_free_entry(sp, tmp);
592	goto next;
593	}
594	if (p->fts_instr != FTS_FOLLOW) {
595	/* likely */
596	} else {
597	p->fts_info = fts_stat(sp, p, 1, INVALID_HANDLE_VALUE);
598	/* NT: See above regarding fts_flags. */
599	if (p->fts_info == FTS_D) {
600	p->fts_flags \|= FTS_SYMFOLLOW;
601	}
602	p->fts_instr = FTS_NOINSTR;
603	}
604
605	fts_free_entry(sp, tmp);
606
607	name:
608	if (!(sp->fts_options & FTS_NO_ANSI)) {
609	char *t = sp->fts_path + NAPPEND(p->fts_parent);
610	*t++ = '/';
611	memmove(t, p->fts_name, p->fts_namelen + 1);
612	}
613	pwc = sp->fts_wcspath + NAPPENDW(p->fts_parent);
614	*pwc++ = '/';
615	memmove(pwc, p->fts_wcsname, (p->fts_cwcname + 1) * sizeof(wchar_t));
616	return (sp->fts_cur = p);
617	}
618
619	/* Move up to the parent node. */
620	p = tmp->fts_parent;
621
622	if (p->fts_level != FTS_ROOTPARENTLEVEL) {
623	/* likely */
624	} else {
625	/*
626	* Done; free everything up and set errno to 0 so the user
627	* can distinguish between error and EOF.
628	*/
629	fts_free_entry(sp, tmp);
630	fts_free_entry(sp, p);
631	errno = 0;
632	return (sp->fts_cur = NULL);
633	}
634
635	/* NUL terminate the pathname. */
636	if (!(sp->fts_options & FTS_NO_ANSI))
637	sp->fts_path[p->fts_pathlen] = '\0';
638	sp->fts_wcspath[ p->fts_cwcpath] = '\0';
639
640	/*
641	* Return to the parent directory. If at a root node or came through
642	* a symlink, go back through the file descriptor. Otherwise, cd up
643	* one directory.
644	*
645	* NT: We're doing no fchdir, but we need to close the directory handle.
646	*/
647	if (p->fts_dirfd != INVALID_HANDLE_VALUE) {
648	birdCloseFile(p->fts_dirfd);
649	p->fts_dirfd = INVALID_HANDLE_VALUE;
650	}
651	fts_free_entry(sp, tmp);
652	p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
653	return (sp->fts_cur = p);
654	}
655
656	/*
657	* Fts_set takes the stream as an argument although it's not used in this
658	* implementation; it would be necessary if anyone wanted to add global
659	* semantics to fts using fts_set. An error return is allowed for similar
660	* reasons.
661	*/
662	/* ARGSUSED */
663	int FTSCALL
664	nt_fts_set(FTS sp, FTSENT p, int instr)
665	{
666	if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
667	instr != FTS_NOINSTR && instr != FTS_SKIP) {
668	errno = EINVAL;
669	return (1);
670	}
671	p->fts_instr = instr;
672	return (0);
673	}
674
675	FTSENT * FTSCALL
676	nt_fts_children(FTS *sp, int instr)
677	{
678	FTSENT *p;
679
680	if (instr != 0 && instr != FTS_NAMEONLY) {
681	errno = EINVAL;
682	return (NULL);
683	}
684
685	/* Set current node pointer. */
686	p = sp->fts_cur;
687
688	/*
689	* Errno set to 0 so user can distinguish empty directory from
690	* an error.
691	*/
692	errno = 0;
693
694	/* Fatal errors stop here. */
695	if (ISSET(FTS_STOP))
696	return (NULL);
697
698	/* Return logical hierarchy of user's arguments. */
699	if (p->fts_info == FTS_INIT)
700	return (p->fts_link);
701
702	/*
703	* If not a directory being visited in pre-order, stop here. Could
704	* allow FTS_DNR, assuming the user has fixed the problem, but the
705	* same effect is available with FTS_AGAIN.
706	*/
707	if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
708	return (NULL);
709
710	/* Free up any previous child list. */
711	if (sp->fts_child != NULL) {
712	fts_lfree(sp->fts_child);
713	sp->fts_child = NULL; /* (bird - double free for _open(".") failure in original) */
714	}
715
716	/* NT: Some BSD utility sets FTS_NAMEONLY? We don't really need this
717	optimization, but since it only hurts that utility, it can stay. */
718	if (instr == FTS_NAMEONLY) {
719	assert(0); /* don't specify FTS_NAMEONLY on NT. */
720	SET(FTS_NAMEONLY);
721	instr = BNAMES;
722	} else
723	instr = BCHILD;
724
725	return (sp->fts_child = fts_build(sp, instr));
726	}
727
728	#ifndef fts_get_clientptr
729	#error "fts_get_clientptr not defined"
730	#endif
731
732	void *
733	(FTSCALL fts_get_clientptr)(FTS *sp)
734	{
735
736	return (fts_get_clientptr(sp));
737	}
738
739	#ifndef fts_get_stream
740	#error "fts_get_stream not defined"
741	#endif
742
743	FTS *
744	(FTSCALL fts_get_stream)(FTSENT *p)
745	{
746	return (fts_get_stream(p));
747	}
748
749	void FTSCALL
750	nt_fts_set_clientptr(FTS sp, void clientptr)
751	{
752
753	sp->fts_clientptr = clientptr;
754	}
755
756	/*
757	* This is the tricky part -- do not casually change anything in here. The
758	* idea is to build the linked list of entries that are used by fts_children
759	* and fts_read. There are lots of special cases.
760	*
761	* The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is
762	* set and it's a physical walk (so that symbolic links can't be directories),
763	* we can do things quickly. First, if it's a 4.4BSD file system, the type
764	* of the file is in the directory entry. Otherwise, we assume that the number
765	* of subdirectories in a node is equal to the number of links to the parent.
766	* The former skips all stat calls. The latter skips stat calls in any leaf
767	* directories and for any files after the subdirectories in the directory have
768	* been found, cutting the stat calls by about 2/3.
769	*
770	* NT: We do not do any link counting or stat avoiding, which invalidates the
771	* above warnings. This function is very simple for us.
772	*/
773	static FTSENT *
774	fts_build(FTS *sp, int type)
775	{
776	BirdDirEntryW_T *dp;
777	FTSENT p, cur;
778	FTSENT * volatile head,* volatile tailp; / volatile is to prevent aliasing trouble */
779	DIR *dirp;
780	int saved_errno, doadjust, doadjust_utf16;
781	long level;
782	size_t len, cwcdir, maxlen, cwcmax, nitems;
783	unsigned fDirOpenFlags;
784
785	/* Set current node pointer. */
786	cur = sp->fts_cur;
787
788	/*
789	* Open the directory for reading. If this fails, we're done.
790	* If being called from fts_read, set the fts_info field.
791	*
792	* NT: We do a two stage open so we can keep the directory handle around
793	* after we've enumerated the directory. The dir handle is used by
794	* us here and by the API users to more efficiently and safely open
795	* members of the directory.
796	*/
797	fDirOpenFlags = BIRDDIR_F_EXTRA_INFO \| BIRDDIR_F_KEEP_HANDLE;
798	if (cur->fts_dirfd == INVALID_HANDLE_VALUE) {
799	if (cur->fts_parent->fts_dirfd != INVALID_HANDLE_VALUE) {
800	/* (This works fine for symlinks too, since we follow them.) */
801	cur->fts_dirfd = birdOpenFileExW(cur->fts_parent->fts_dirfd,
802	cur->fts_wcsname,
803	FILE_READ_DATA \| SYNCHRONIZE,
804	FILE_ATTRIBUTE_NORMAL,
805	FILE_SHARE_READ \| FILE_SHARE_WRITE \| FILE_SHARE_DELETE,
806	FILE_OPEN,
807	FILE_DIRECTORY_FILE \| FILE_OPEN_FOR_BACKUP_INTENT \| FILE_SYNCHRONOUS_IO_NONALERT,
808	OBJ_CASE_INSENSITIVE);
809	} else {
810	cur->fts_dirfd = birdOpenFileW(cur->fts_wcsaccpath,
811	FILE_READ_DATA \| SYNCHRONIZE,
812	FILE_ATTRIBUTE_NORMAL,
813	FILE_SHARE_READ \| FILE_SHARE_WRITE \| FILE_SHARE_DELETE,
814	FILE_OPEN,
815	FILE_DIRECTORY_FILE \| FILE_OPEN_FOR_BACKUP_INTENT \| FILE_SYNCHRONOUS_IO_NONALERT,
816	OBJ_CASE_INSENSITIVE);
817	}
818	if (cur->fts_dirfd != INVALID_HANDLE_VALUE) { /* likely */ }
819	else goto l_open_err;
820
821	} else {
822	fDirOpenFlags \|= BIRDDIR_F_RESTART_SCAN;
823	}
824	#ifdef FTS_WITH_DIRHANDLE_REUSE
825	dirp = birdDirOpenFromHandleWithReuse(&((struct _fts_private *)sp)->dirhandle, cur->fts_dirfd, NULL,
826	fDirOpenFlags \| BIRDDIR_F_STATIC_ALLOC);
827	#else
828	dirp = birdDirOpenFromHandle(cur->fts_dirfd, NULL, fDirOpenFlags);
829	#endif
830	if (dirp == NULL) {
831	l_open_err:
832	if (type == BREAD) {
833	cur->fts_info = FTS_DNR;
834	cur->fts_errno = errno;
835	}
836	return (NULL);
837	}
838
839	/*
840	* Figure out the max file name length that can be stored in the
841	* current path -- the inner loop allocates more path as necessary.
842	* We really wouldn't have to do the maxlen calculations here, we
843	* could do them in fts_read before returning the path, but it's a
844	* lot easier here since the length is part of the dirent structure.
845	*/
846	if (sp->fts_options & FTS_NO_ANSI) {
847	len = 0;
848	maxlen = 0x10000;
849	} else {
850	len = NAPPEND(cur);
851	len++;
852	maxlen = sp->fts_pathlen - len;
853	}
854
855	cwcdir = NAPPENDW(cur);
856	cwcdir++;
857	cwcmax = sp->fts_cwcpath - len;
858
859	level = cur->fts_level + 1;
860
861	/* Read the directory, attaching each entry to the `link' pointer. */
862	doadjust = doadjust_utf16 = 0;
863	nitems = 0;
864	head = NULL;
865	tailp = &head;
866	while ((dp = birdDirReadW(dirp)) != NULL) {
867	if (ISSET(FTS_SEEDOT) \|\| !ISDOT(dp->d_name)) {
868	/* assume dirs have two or more entries */
869	} else {
870	continue;
871	}
872
873	if ((p = fts_alloc_utf16(sp, dp->d_name, dp->d_namlen)) != NULL) {
874	/* likely */
875	} else {
876	goto mem1;
877	}
878
879	/* include space for NUL */
880	if (p->fts_namelen < maxlen && p->fts_cwcname < cwcmax) {
881	/* likely */
882	} else {
883	void *oldaddr = sp->fts_path;
884	wchar_t *oldwcspath = sp->fts_wcspath;
885	if (fts_palloc(sp,
886	p->fts_namelen >= maxlen ? len + p->fts_namelen + 1 : 0,
887	p->fts_cwcname >= cwcmax ? cwcdir + p->fts_cwcname + 1 : 0)) {
888	mem1:
889	/*
890	* No more memory for path or structures. Save
891	* errno, free up the current structure and the
892	* structures already allocated.
893	*/
894	saved_errno = errno;
895	if (p)
896	free(p);
897	fts_lfree(head);
898	#ifndef FTS_WITH_DIRHANDLE_REUSE
899	birdDirClose(dirp);
900	#endif
901	birdCloseFile(cur->fts_dirfd);
902	cur->fts_dirfd = INVALID_HANDLE_VALUE;
903	cur->fts_info = FTS_ERR;
904	SET(FTS_STOP);
905	errno = saved_errno;
906	return (NULL);
907	}
908	/* Did realloc() change the pointer? */
909	doadjust \|= oldaddr != sp->fts_path;
910	doadjust_utf16 \|= oldwcspath != sp->fts_wcspath;
911	maxlen = sp->fts_pathlen - len;
912	cwcmax = sp->fts_cwcpath - cwcdir;
913	}
914
915	p->fts_level = level;
916	p->fts_parent = sp->fts_cur;
917	p->fts_pathlen = len + p->fts_namelen;
918	p->fts_cwcpath = cwcdir + p->fts_cwcname;
919	p->fts_accpath = p->fts_path;
920	p->fts_wcsaccpath = p->fts_wcspath;
921	p->fts_stat = dp->d_stat;
922	p->fts_info = fts_process_stats(p, &dp->d_stat);
923
924	/* We walk in directory order so "ls -f" doesn't get upset. */
925	p->fts_link = NULL;
926	*tailp = p;
927	tailp = &p->fts_link;
928	++nitems;
929	}
930
931	#ifndef FTS_WITH_DIRHANDLE_REUSE
932	birdDirClose(dirp);
933	#endif
934
935	/*
936	* If realloc() changed the address of the path, adjust the
937	* addresses for the rest of the tree and the dir list.
938	*/
939	if (doadjust)
940	fts_padjust(sp, head);
941	if (doadjust_utf16)
942	fts_padjustw(sp, head);
943
944	/* If didn't find anything, return NULL. */
945	if (!nitems) {
946	if (type == BREAD)
947	cur->fts_info = FTS_DP;
948	return (NULL);
949	}
950
951	/* Sort the entries. */
952	if (sp->fts_compar && nitems > 1)
953	head = fts_sort(sp, head, nitems);
954	return (head);
955	}
956
957
958	/**
959	* @note Only used on NT with input arguments, FTS_AGAIN, and links that needs
960	* following. On link information is generally retrieved during directory
961	* enumeration on NT, in line with it's DOS/OS2/FAT API heritage.
962	*/
963	static int
964	fts_stat(FTS sp, FTSENT p, int follow, HANDLE dfd)
965	{
966	int saved_errno;
967	const wchar_t *wcspath;
968
969	if (dfd == INVALID_HANDLE_VALUE) {
970	wcspath = p->fts_wcsaccpath;
971	} else {
972	wcspath = p->fts_wcsname;
973	}
974
975	/*
976	* If doing a logical walk, or application requested FTS_FOLLOW, do
977	* a stat(2). If that fails, check for a non-existent symlink. If
978	* fail, set the errno from the stat call.
979	*/
980	if (ISSET(FTS_LOGICAL) \|\| follow) {
981	if (birdStatAtW(dfd, wcspath, &p->fts_stat, 1 /fFollowLink/)) {
982	saved_errno = errno;
983	if (birdStatAtW(dfd, wcspath, &p->fts_stat, 0 /fFollowLink/)) {
984	p->fts_errno = saved_errno;
985	goto err;
986	}
987	errno = 0;
988	if (S_ISLNK(p->fts_stat.st_mode))
989	return (FTS_SLNONE);
990	}
991	} else if (birdStatAtW(dfd, wcspath, &p->fts_stat, 0 /fFollowLink/)) {
992	p->fts_errno = errno;
993	err: memset(&p->fts_stat, 0, sizeof(struct stat));
994	return (FTS_NS);
995	}
996	return fts_process_stats(p, &p->fts_stat);
997	}
998
999	/* Shared between fts_stat and fts_build. */
1000	static int
1001	fts_process_stats(FTSENT p, BirdStat_T const sbp)
1002	{
1003	if (S_ISDIR(sbp->st_mode)) {
1004	FTSENT *t;
1005	fts_dev_t dev;
1006	fts_ino_t ino;
1007
1008	/*
1009	* Set the device/inode. Used to find cycles and check for
1010	* crossing mount points. Also remember the link count, used
1011	* in fts_build to limit the number of stat calls. It is
1012	* understood that these fields are only referenced if fts_info
1013	* is set to FTS_D.
1014	*/
1015	dev = p->fts_dev = sbp->st_dev;
1016	ino = p->fts_ino = sbp->st_ino;
1017	p->fts_nlink = sbp->st_nlink;
1018
1019	if (ISDOT(p->fts_wcsname))
1020	return (FTS_DOT);
1021
1022	/*
1023	* Cycle detection is done by brute force when the directory
1024	* is first encountered. If the tree gets deep enough or the
1025	* number of symbolic links to directories is high enough,
1026	* something faster might be worthwhile.
1027	*/
1028	for (t = p->fts_parent;
1029	t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1030	if (ino == t->fts_ino && dev == t->fts_dev) {
1031	p->fts_cycle = t;
1032	return (FTS_DC);
1033	}
1034	return (FTS_D);
1035	}
1036	if (S_ISLNK(sbp->st_mode))
1037	return (FTS_SL);
1038	if (S_ISREG(sbp->st_mode))
1039	return (FTS_F);
1040	return (FTS_DEFAULT);
1041	}
1042
1043	/*
1044	* The comparison function takes pointers to pointers to FTSENT structures.
1045	* Qsort wants a comparison function that takes pointers to void.
1046	* (Both with appropriate levels of const-poisoning, of course!)
1047	* Use a trampoline function to deal with the difference.
1048	*/
1049	static int
1050	fts_compar(const void a, const void b)
1051	{
1052	FTS *parent;
1053
1054	parent = ((const FTSENT const *)a)->fts_fts;
1055	return (*parent->fts_compar)(a, b);
1056	}
1057
1058	static FTSENT *
1059	fts_sort(FTS sp, FTSENT head, size_t nitems)
1060	{
1061	FTSENT *ap, p;
1062
1063	/*
1064	* Construct an array of pointers to the structures and call qsort(3).
1065	* Reassemble the array in the order returned by qsort. If unable to
1066	* sort for memory reasons, return the directory entries in their
1067	* current order. Allocate enough space for the current needs plus
1068	* 40 so don't realloc one entry at a time.
1069	*/
1070	if (nitems > sp->fts_nitems) {
1071	void *ptr;
1072	sp->fts_nitems = nitems + 40;
1073	ptr = realloc(sp->fts_array, sp->fts_nitems * sizeof(FTSENT *));
1074	if (ptr != NULL) {
1075	sp->fts_array = ptr;
1076	} else {
1077	free(sp->fts_array);
1078	sp->fts_array = NULL;
1079	sp->fts_nitems = 0;
1080	return (head);
1081	}
1082	}
1083	for (ap = sp->fts_array, p = head; p; p = p->fts_link)
1084	*ap++ = p;
1085	qsort(sp->fts_array, nitems, sizeof(FTSENT *), fts_compar);
1086	for (head = *(ap = sp->fts_array); --nitems; ++ap)
1087	ap[0]->fts_link = ap[1];
1088	ap[0]->fts_link = NULL;
1089	return (head);
1090	}
1091
1092	static FTSENT *
1093	fts_alloc(FTS sp, char const name, size_t namelen, wchar_t const *wcsname, size_t cwcname)
1094	{
1095	struct _fts_private priv = (struct _fts_private )sp;
1096	FTSENT *p;
1097	size_t len;
1098	#ifdef FTS_WITH_ALLOC_CACHE
1099	size_t aligned;
1100	size_t idx;
1101	#endif
1102
1103	#if defined(FTS_WITH_STATISTICS) && defined(FTS_WITH_ALLOC_CACHE)
1104	priv->allocs++;
1105	#endif
1106	/*
1107	* The file name is a variable length array. Allocate the FTSENT
1108	* structure and the file name.
1109	*/
1110	len = sizeof(FTSENT) + (cwcname + 1) * sizeof(wchar_t);
1111	if (!(sp->fts_options & FTS_NO_ANSI))
1112	len += namelen + 1;
1113
1114	/*
1115	* To speed things up we cache entries. This code is a little insane,
1116	* but that's preferable to slow code.
1117	*/
1118	#ifdef FTS_WITH_ALLOC_CACHE
1119	aligned = (len + FTS_ALIGN_FTSENT + 1) & ~(size_t)(FTS_ALIGN_FTSENT - 1);
1120	idx = ((aligned - sizeof(FTSENT)) >> FTS_FREE_BUCKET_SHIFT);
1121	if ( idx < FTS_NUM_FREE_BUCKETS
1122	&& (p = priv->freebuckets[idx].head)
1123	&& p->fts_alloc_size >= len) {
1124	priv->freebuckets[idx].head = p->fts_link;
1125	priv->numfree--;
1126	# ifdef FTS_WITH_STATISTICS
1127	priv->hits++;
1128	# endif
1129
1130	} else {
1131	# ifdef FTS_WITH_STATISTICS
1132	priv->misses++;
1133	# endif
1134	p = malloc(aligned);
1135	if (p) {
1136	p->fts_alloc_size = (unsigned)aligned;
1137	} else {
1138	nt_fts_free_alloc_cache(sp);
1139	p = malloc(len);
1140	if (!p)
1141	return NULL;
1142	p->fts_alloc_size = (unsigned)len;
1143	}
1144	}
1145	#else /* !FTS_WITH_ALLOC_CACHE */
1146	p = malloc(len);
1147	if (p) {
1148	p->fts_alloc_size = (unsigned)len;
1149	} else {
1150	return NULL;
1151	}
1152	#endif /* !FTS_WITH_ALLOC_CACHE */
1153
1154	/* Copy the names and guarantee NUL termination. */
1155	p->fts_wcsname = (wchar_t *)(p + 1);
1156	memcpy(p->fts_wcsname, wcsname, cwcname * sizeof(wchar_t));
1157	p->fts_wcsname[cwcname] = '\0';
1158	p->fts_cwcname = cwcname;
1159	if (!(sp->fts_options & FTS_NO_ANSI)) {
1160	p->fts_name = (char *)(p->fts_wcsname + cwcname + 1);
1161	memcpy(p->fts_name, name, namelen);
1162	p->fts_name[namelen] = '\0';
1163	p->fts_namelen = namelen;
1164	} else {
1165	p->fts_name = NULL;
1166	p->fts_namelen = 0;
1167	}
1168
1169	p->fts_path = sp->fts_path;
1170	p->fts_wcspath = sp->fts_wcspath;
1171	p->fts_statp = &p->fts_stat;
1172	p->fts_errno = 0;
1173	p->fts_flags = 0;
1174	p->fts_instr = FTS_NOINSTR;
1175	p->fts_number = 0;
1176	p->fts_pointer = NULL;
1177	p->fts_fts = sp;
1178	p->fts_dirfd = INVALID_HANDLE_VALUE;
1179	return (p);
1180	}
1181
1182
1183	/**
1184	* Converts the ANSI name to UTF-16 and calls fts_alloc.
1185	*
1186	* @returns Pointer to allocated and mostly initialized FTSENT structure on
1187	* success. NULL on failure, caller needs to record it.
1188	* @param sp Pointer to FTS instance.
1189	* @param name The ANSI name.
1190	* @param namelen The ANSI name length.
1191	*/
1192	static FTSENT *
1193	fts_alloc_ansi(FTS sp, char const name, size_t namelen)
1194	{
1195	MY_UNICODE_STRING UniStr;
1196	MY_ANSI_STRING AnsiStr;
1197	MY_NTSTATUS rcNt;
1198	FTSENT *pRet;
1199
1200	UniStr.Buffer = NULL;
1201	UniStr.MaximumLength = UniStr.Length = 0;
1202
1203	AnsiStr.Buffer = (char *)name;
1204	AnsiStr.Length = AnsiStr.MaximumLength = (USHORT)namelen;
1205
1206	rcNt = g_pfnRtlAnsiStringToUnicodeString(&UniStr, &AnsiStr, TRUE /fAllocate/);
1207	if (NT_SUCCESS(rcNt)) {
1208	pRet = fts_alloc(sp, name, namelen, UniStr.Buffer, UniStr.Length / sizeof(wchar_t));
1209	HeapFree(GetProcessHeap(), 0, UniStr.Buffer);
1210	} else {
1211	pRet = NULL;
1212	}
1213	return pRet;
1214	}
1215
1216
1217	/**
1218	* Converts the UTF-16 name to ANSI (if necessary) and calls fts_alloc.
1219	*
1220	* @returns Pointer to allocated and mostly initialized FTSENT structure on
1221	* success. NULL on failure, caller needs to record it.
1222	* @param sp Pointer to the FTS instance.
1223	* @param wcsname The UTF-16 name.
1224	* @param cwcname The UTF-16 name length.
1225	*/
1226	static FTSENT *
1227	fts_alloc_utf16(FTS sp, wchar_t const wcsname, size_t cwcname)
1228	{
1229	FTSENT *pRet;
1230
1231	if (sp->fts_options & FTS_NO_ANSI) {
1232	pRet = fts_alloc(sp, NULL, 0, wcsname, cwcname);
1233	} else {
1234	MY_UNICODE_STRING UniStr;
1235	MY_ANSI_STRING AnsiStr;
1236	MY_NTSTATUS rcNt;
1237
1238	UniStr.Buffer = (wchar_t *)wcsname;
1239	UniStr.MaximumLength = UniStr.Length = (USHORT)(cwcname * sizeof(wchar_t));
1240
1241	AnsiStr.Buffer = NULL;
1242	AnsiStr.Length = AnsiStr.MaximumLength = 0;
1243
1244	rcNt = g_pfnRtlUnicodeStringToAnsiString(&AnsiStr, &UniStr, TRUE /fAllocate/);
1245	if (NT_SUCCESS(rcNt)) {
1246	pRet = fts_alloc(sp, AnsiStr.Buffer, AnsiStr.Length, wcsname, cwcname);
1247	HeapFree(GetProcessHeap(), 0, AnsiStr.Buffer);
1248	} else {
1249	pRet = NULL;
1250	}
1251	}
1252	return pRet;
1253	}
1254
1255
1256	/**
1257	* Frees up the FTSENT allocation cache.
1258	*
1259	* Used by nt_fts_close, but also called by fts_alloc on alloc failure.
1260	*
1261	* @param sp Pointer to the FTS instance.
1262	*/
1263	static void nt_fts_free_alloc_cache(FTS *sp)
1264	{
1265	#ifdef FTS_WITH_ALLOC_CACHE
1266	struct _fts_private priv = (struct _fts_private )sp;
1267	unsigned i = K_ELEMENTS(priv->freebuckets);
1268	while (i-- > 0) {
1269	FTSENT *cur = priv->freebuckets[i].head;
1270	priv->freebuckets[i].head = NULL;
1271	while (cur) {
1272	FTSENT *freeit = cur;
1273	cur = cur->fts_link;
1274	free(freeit);
1275	}
1276	}
1277	priv->numfree = 0;
1278	#else
1279	(void)sp;
1280	#endif
1281	}
1282
1283
1284	static void
1285	fts_lfree(FTSENT *head)
1286	{
1287	FTSENT *p;
1288
1289	/* Free a linked list of structures. */
1290	while ((p = head)) {
1291	head = head->fts_link;
1292	assert(p->fts_dirfd == INVALID_HANDLE_VALUE);
1293	free(p);
1294	}
1295	}
1296
1297	/*
1298	* Allow essentially unlimited paths; find, rm, ls should all work on any tree.
1299	* Most systems will allow creation of paths much longer than MAXPATHLEN, even
1300	* though the kernel won't resolve them. Add the size (not just what's needed)
1301	* plus 256 bytes so don't realloc the path 2 bytes at a time.
1302	*/
1303	static int
1304	fts_palloc(FTS *sp, size_t more, size_t cwcmore)
1305	{
1306	void *ptr;
1307
1308	/** @todo Isn't more and cwcmore minimum buffer sizes rather than what needs
1309	* to be added to the buffer?? This code makes no sense when looking at
1310	* the way the caller checks things out! */
1311
1312	if (more) {
1313	sp->fts_pathlen += more + 256;
1314	ptr = realloc(sp->fts_path, sp->fts_pathlen);
1315	if (ptr) {
1316	sp->fts_path = ptr;
1317	} else {
1318	free(sp->fts_path);
1319	sp->fts_path = NULL;
1320	free(sp->fts_wcspath);
1321	sp->fts_wcspath = NULL;
1322	return 1;
1323	}
1324	}
1325
1326	if (cwcmore) {
1327	sp->fts_cwcpath += cwcmore + 256;
1328	ptr = realloc(sp->fts_wcspath, sp->fts_cwcpath);
1329	if (ptr) {
1330	sp->fts_wcspath = ptr;
1331	} else {
1332	free(sp->fts_path);
1333	sp->fts_path = NULL;
1334	free(sp->fts_wcspath);
1335	sp->fts_wcspath = NULL;
1336	return 1;
1337	}
1338	}
1339	return 0;
1340	}
1341
1342	/*
1343	* When the path is realloc'd, have to fix all of the pointers in structures
1344	* already returned.
1345	*/
1346	static void
1347	fts_padjust(FTS sp, FTSENT head)
1348	{
1349	FTSENT *p;
1350	char *addr = sp->fts_path;
1351
1352	#define ADJUST(p) do { \
1353	if ((p)->fts_accpath != (p)->fts_name) { \
1354	(p)->fts_accpath = \
1355	(char *)addr + ((p)->fts_accpath - (p)->fts_path); \
1356	} \
1357	(p)->fts_path = addr; \
1358	} while (0)
1359	/* Adjust the current set of children. */
1360	for (p = sp->fts_child; p; p = p->fts_link)
1361	ADJUST(p);
1362
1363	/* Adjust the rest of the tree, including the current level. */
1364	for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1365	ADJUST(p);
1366	p = p->fts_link ? p->fts_link : p->fts_parent;
1367	}
1368	}
1369
1370	/*
1371	* When the UTF-16 path is realloc'd, have to fix all of the pointers in
1372	* structures already returned.
1373	*/
1374	static void
1375	fts_padjustw(FTS sp, FTSENT head)
1376	{
1377	FTSENT *p;
1378	wchar_t *addr = sp->fts_wcspath;
1379
1380	#define ADJUSTW(p) \
1381	do { \
1382	if ((p)->fts_wcsaccpath != (p)->fts_wcsname) \
1383	(p)->fts_wcsaccpath = addr + ((p)->fts_wcsaccpath - (p)->fts_wcspath); \
1384	(p)->fts_wcspath = addr; \
1385	} while (0)
1386
1387	/* Adjust the current set of children. */
1388	for (p = sp->fts_child; p; p = p->fts_link)
1389	ADJUSTW(p);
1390
1391	/* Adjust the rest of the tree, including the current level. */
1392	for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1393	ADJUSTW(p);
1394	p = p->fts_link ? p->fts_link : p->fts_parent;
1395	}
1396	}
1397
1398	static size_t
1399	fts_maxarglen(char * const *argv)
1400	{
1401	size_t len, max;
1402
1403	for (max = 0; *argv; ++argv)
1404	if ((len = strlen(*argv)) > max)
1405	max = len;
1406	return (max + 1);
1407	}
1408
1409	/** Returns the max string size (including term). */
1410	static size_t
1411	fts_maxarglenw(wchar_t * const *argv)
1412	{
1413	size_t max = 0;
1414	for (; *argv; ++argv) {
1415	size_t len = wcslen(*argv);
1416	if (len > max)
1417	max = len;
1418	}
1419	return max + 1;
1420	}
1421

Note: See TracBrowser for help on using the repository browser.

Download in other formats: