fts-nt.c@ 3372

Last change on this file since 3372 was 3009, checked in by bird, 8 years ago
ntunlink: W apis.
Property svn:eol-style set to `native` Property svn:keywords set to `Id`
File size: 38.9 KB

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

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

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

Download in other formats: