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

Last change on this file since 3000 was 3000, checked in by bird, 9 years ago

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