xref: /csrg-svn/lib/libc/gen/fts.c (revision 52278)
1 /*-
2  * Copyright (c) 1990 The Regents of the University of California.
3  * All rights reserved.
4  *
5  * %sccs.include.redist.c%
6  */
7 
8 #if defined(LIBC_SCCS) && !defined(lint)
9 static char sccsid[] = "@(#)fts.c	5.28 (Berkeley) 01/31/92";
10 #endif /* LIBC_SCCS and not lint */
11 
12 #include <sys/param.h>
13 #include <sys/stat.h>
14 #include <fcntl.h>
15 #include <dirent.h>
16 #include <errno.h>
17 #include <fts.h>
18 #include <stdlib.h>
19 #include <string.h>
20 #include <unistd.h>
21 
22 static FTSENT	*fts_alloc __P((FTS *, char *, int));
23 static FTSENT	*fts_build __P((FTS *, int));
24 static void	 fts_lfree __P((FTSENT *));
25 static void	 fts_load __P((FTS *, FTSENT *));
26 static void	 fts_padjust __P((FTS *, void *));
27 static int	 fts_palloc __P((FTS *, int));
28 static FTSENT	*fts_sort __P((FTS *, FTSENT *, int));
29 static u_short	 fts_stat __P((FTS *, FTSENT *, int));
30 
31 #define	ISDOT(a)	(a[0] == '.' && (!a[1] || a[1] == '.' && !a[2]))
32 
33 #define	ISSET(opt)	(sp->fts_options & opt)
34 #define	SET(opt)	(sp->fts_options |= opt)
35 
36 #define	CHDIR(sp, path)	(!ISSET(FTS_NOCHDIR) && chdir(path))
37 #define	FCHDIR(sp, fd)	(!ISSET(FTS_NOCHDIR) && fchdir(fd))
38 
39 /* fts_build flags */
40 #define	BCHILD		1		/* from fts_children */
41 #define	BREAD		2		/* from fts_read */
42 
43 FTS *
44 fts_open(argv, options, compar)
45 	char * const *argv;
46 	register int options;
47 	int (*compar)();
48 {
49 	register FTS *sp;
50 	register FTSENT *p, *root;
51 	register int nitems, maxlen;
52 	FTSENT *parent, *tmp;
53 	int len;
54 
55 	/* Allocate/initialize the stream */
56 	if ((sp = malloc((u_int)sizeof(FTS))) == NULL)
57 		return (NULL);
58 	bzero(sp, sizeof(FTS));
59 	sp->fts_compar = compar;
60 	sp->fts_options = options;
61 
62 	/* Logical walks turn on NOCHDIR; symbolic links are too hard. */
63 	if (ISSET(FTS_LOGICAL))
64 		SET(FTS_NOCHDIR);
65 
66 	/* Allocate/initialize root's parent. */
67 	if ((parent = fts_alloc(sp, "", 0)) == NULL)
68 		goto mem1;
69 	parent->fts_level = FTS_ROOTPARENTLEVEL;
70 
71 	/* Allocate/initialize root(s). */
72 	for (root = NULL, maxlen = nitems = 0; *argv; ++argv, ++nitems) {
73 		/* Don't allow zero-length paths. */
74 		if ((len = strlen(*argv)) == 0) {
75 			errno = ENOENT;
76 			goto mem2;
77 		}
78 		if (maxlen < len)
79 			maxlen = len;
80 
81 		p = fts_alloc(sp, *argv, len);
82 		p->fts_level = FTS_ROOTLEVEL;
83 		p->fts_parent = parent;
84 		p->fts_accpath = p->fts_name;
85 		p->fts_info = fts_stat(sp, p, 0);
86 
87 		/* Command-line "." and ".." are real directories. */
88 		if (p->fts_info == FTS_DOT)
89 			p->fts_info = FTS_D;
90 
91 		/*
92 		 * If comparison routine supplied, traverse in sorted
93 		 * order; otherwise traverse in the order specified.
94 		 */
95 		if (compar) {
96 			p->fts_link = root;
97 			root = p;
98 		} else {
99 			p->fts_link = NULL;
100 			if (root == NULL)
101 				tmp = root = p;
102 			else {
103 				tmp->fts_link = p;
104 				tmp = p;
105 			}
106 		}
107 	}
108 	if (compar && nitems > 1)
109 		root = fts_sort(sp, root, nitems);
110 
111 	/*
112 	 * Allocate a dummy pointer and make fts_read think that we've just
113 	 * finished the node before the root(s); set p->fts_info to FTS_INIT
114 	 * so that everything about the "current" node is ignored.
115 	 */
116 	if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
117 		goto mem2;
118 	sp->fts_cur->fts_link = root;
119 	sp->fts_cur->fts_info = FTS_INIT;
120 
121 	/*
122 	 * Start out with more than 1K of path space, and enough, in any
123 	 * case, to hold the user's paths.
124 	 */
125 	if (fts_palloc(sp, MAX(maxlen, MAXPATHLEN)))
126 		goto mem3;
127 
128 	/*
129 	 * If using chdir(2), grab a file descriptor pointing to dot to insure
130 	 * that we can get back here; this could be avoided for some paths,
131 	 * but almost certainly not worth the effort.  Slashes, symbolic links,
132 	 * and ".." are all fairly nasty problems.  Note, if we can't get the
133 	 * descriptor we run anyway, just more slowly.
134 	 */
135 	if (!ISSET(FTS_NOCHDIR) && (sp->fts_rfd = open(".", O_RDONLY, 0)) < 0)
136 		SET(FTS_NOCHDIR);
137 
138 	return (sp);
139 
140 mem3:	free(sp->fts_cur);
141 mem2:	fts_lfree(root);
142 	free(parent);
143 mem1:	free(sp);
144 	return (NULL);
145 }
146 
147 static void
148 fts_load(sp, p)
149 	FTS *sp;
150 	register FTSENT *p;
151 {
152 	register int len;
153 	register char *cp;
154 
155 	/*
156 	 * Load the stream structure for the next traversal.  Since we don't
157 	 * actually enter the directory until after the preorder visit, set
158 	 * the fts_accpath field specially so the chdir gets done to the right
159 	 * place and the user can access the first node.  From fts_open it's
160 	 * known that the path will fit.
161 	 */
162 	len = p->fts_pathlen = p->fts_namelen;
163 	bcopy(p->fts_name, sp->fts_path, len + 1);
164 	if ((cp = rindex(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
165 		len = strlen(++cp);
166 		bcopy(cp, p->fts_name, len + 1);
167 		p->fts_namelen = len;
168 	}
169 	p->fts_accpath = p->fts_path = sp->fts_path;
170 	sp->fts_dev = p->fts_dev;
171 }
172 
173 int
174 fts_close(sp)
175 	FTS *sp;
176 {
177 	register FTSENT *freep, *p;
178 	int saved_errno;
179 
180 	/*
181 	 * This still works if we haven't read anything -- the dummy structure
182 	 * points to the root list, so we step through to the end of the root
183 	 * list which has a valid parent pointer.
184 	 */
185 	if (sp->fts_cur) {
186 		for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
187 			freep = p;
188 			p = p->fts_link ? p->fts_link : p->fts_parent;
189 			free(freep);
190 		}
191 		free(p);
192 	}
193 
194 	/* Free up child linked list, sort array, path buffer. */
195 	if (sp->fts_child)
196 		fts_lfree(sp->fts_child);
197 	if (sp->fts_array)
198 		free(sp->fts_array);
199 	free(sp->fts_path);
200 
201 	/* Return to original directory, save errno if necessary. */
202 	if (!ISSET(FTS_NOCHDIR)) {
203 		saved_errno = fchdir(sp->fts_rfd) ? errno : 0;
204 		(void)close(sp->fts_rfd);
205 	}
206 
207 	/* Free up the stream pointer. */
208 	free(sp);
209 
210 	/* Set errno and return. */
211 	if (!ISSET(FTS_NOCHDIR) && saved_errno) {
212 		errno = saved_errno;
213 		return (-1);
214 	}
215 	return (0);
216 }
217 
218 /*
219  * Special case a root of "/" so that slashes aren't appended which would
220  * cause paths to be written as "//foo".
221  */
222 #define	NAPPEND(p) \
223 	(p->fts_level == FTS_ROOTLEVEL && p->fts_pathlen == 1 && \
224 	    p->fts_path[0] == '/' ? 0 : p->fts_pathlen)
225 
226 FTSENT *
227 fts_read(sp)
228 	register FTS *sp;
229 {
230 	register FTSENT *p, *tmp;
231 	register int instr;
232 	register char *t;
233 
234 	/* If finished or unrecoverable error, return NULL. */
235 	if (sp->fts_cur == NULL || ISSET(FTS_STOP))
236 		return (NULL);
237 
238 	/* Set current node pointer. */
239 	p = sp->fts_cur;
240 
241 	/* Save and zero out user instructions. */
242 	instr = p->fts_instr;
243 	p->fts_instr = FTS_NOINSTR;
244 
245 	/* Any type of file may be re-visited; re-stat and re-turn. */
246 	if (instr == FTS_AGAIN) {
247 		p->fts_info = fts_stat(sp, p, 0);
248 		return (p);
249 	}
250 
251 	/*
252 	 * Following a symlink -- SLNONE test allows application to see
253 	 * SLNONE and recover.
254 	 *
255 	 * XXX
256 	 * Have to open a file descriptor to '.' so we can get back.
257 	 */
258 	if (instr == FTS_FOLLOW &&
259 	    (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
260 		p->fts_info = fts_stat(sp, p, 1);
261 		return (p);
262 	}
263 
264 	/* Directory in pre-order. */
265 	if (p->fts_info == FTS_D) {
266 		/* If skipped or crossed mount point, do post-order visit. */
267 		if (instr == FTS_SKIP ||
268 		    ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev) {
269 			if (sp->fts_child) {
270 				fts_lfree(sp->fts_child);
271 				sp->fts_child = NULL;
272 			}
273 			p->fts_info = FTS_DP;
274 			return (p);
275 		}
276 
277 		/*
278 		 * Cd to the subdirectory, reading it if haven't already.  If
279 		 * the read fails for any reason, or the directory is empty,
280 		 * the fts_info field of the current node is set by fts_build.
281 		 * If have already read and now fail to chdir, whack the list
282 		 * to make the names come out right, and set the parent state
283 		 * so the application will eventually get an error condition.
284 		 * If haven't read and fail to chdir, check to see if we're
285 		 * at the root node -- if so, we have to get back or the root
286 		 * node may be inaccessible.
287 		 */
288 		if (sp->fts_child) {
289 			if (CHDIR(sp, p->fts_accpath)) {
290 				p->fts_errno = errno;
291 				for (p = sp->fts_child; p; p = p->fts_link)
292 					p->fts_accpath =
293 					    p->fts_parent->fts_accpath;
294 			}
295 		} else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
296 			if ISSET(FTS_STOP)
297 				return (NULL);
298 			if (p->fts_level == FTS_ROOTLEVEL &&
299 			    FCHDIR(sp, sp->fts_rfd)) {
300 				SET(FTS_STOP);
301 				return (NULL);
302 			}
303 			return (p);
304 		}
305 		p = sp->fts_child;
306 		sp->fts_child = NULL;
307 		goto name;
308 	}
309 
310 	/* Move to the next node on this level. */
311 next:	tmp = p;
312 	if (p = p->fts_link) {
313 		free(tmp);
314 
315 		/* If reached the top, load the paths for the next root. */
316 		if (p->fts_level == FTS_ROOTLEVEL) {
317 			fts_load(sp, p);
318 			return (sp->fts_cur = p);
319 		}
320 
321 		/* User may have called fts_set on the node. */
322 		if (p->fts_instr == FTS_SKIP)
323 			goto next;
324 		/*
325 		 * XXX
326 		 * This may not be able to return to the current directory.
327 		 */
328 		if (p->fts_instr == FTS_FOLLOW) {
329 			p->fts_info = fts_stat(sp, p, 1);
330 			p->fts_instr = FTS_NOINSTR;
331 		}
332 
333 name:		t = sp->fts_path + NAPPEND(p->fts_parent);
334 		*t++ = '/';
335 		bcopy(p->fts_name, t, p->fts_namelen + 1);
336 		return (sp->fts_cur = p);
337 	}
338 
339 	/* Move up to the parent node. */
340 	p = tmp->fts_parent;
341 	free(tmp);
342 
343 	if (p->fts_level == FTS_ROOTPARENTLEVEL) {
344 		/*
345 		 * Done; free everything up and set errno to 0 so the user
346 		 * can distinguish between error and EOF.
347 		 */
348 		free(p);
349 		errno = 0;
350 		return (sp->fts_cur = NULL);
351 	}
352 
353 	sp->fts_path[p->fts_pathlen] = '\0';
354 
355 	/*
356 	 * If at a root node, have to cd back to the starting point, otherwise
357 	 * may not be able to access the original node on post-order.  If not
358 	 * a root node, cd up to the parent directory.  Note that errors are
359 	 * assumed to be caused by an inability to cd to the directory in the
360 	 * first place.
361 	 */
362 	if (p->fts_level == FTS_ROOTLEVEL) {
363 		if (FCHDIR(sp, sp->fts_rfd)) {
364 			SET(FTS_STOP);
365 			return (NULL);
366 		}
367 		p->fts_info = FTS_DP;
368 	} else if (p->fts_errno)
369 		p->fts_info = FTS_ERR;
370 	else {
371 		if (CHDIR(sp, "..")) {
372 			SET(FTS_STOP);
373 			return (NULL);
374 		}
375 		p->fts_info = FTS_DP;
376 	}
377 	return (sp->fts_cur = p);
378 }
379 
380 /*
381  * Fts_set takes the stream as an argument although it's not used in this
382  * implementation; it would be necessary if anyone wanted to add global
383  * semantics to fts using fts_set.  An error return is allowed for similar
384  * reasons.
385  */
386 /* ARGSUSED */
387 int
388 fts_set(sp, p, instr)
389 	FTS *sp;
390 	FTSENT *p;
391 	int instr;
392 {
393 	p->fts_instr = instr;
394 	return (0);
395 }
396 
397 FTSENT *
398 fts_children(sp)
399 	register FTS *sp;
400 {
401 	register FTSENT *p;
402 	int fd;
403 
404 	/* Set current node pointer. */
405 	p = sp->fts_cur;
406 
407 	/*
408 	 * Errno set to 0 so user can distinguish empty directory from
409 	 * an error.
410 	 */
411 	errno = 0;
412 
413 	/* Fatal errors stop here. */
414 	if (ISSET(FTS_STOP))
415 		return (NULL);
416 
417 	/* Return logical hierarchy of user's arguments. */
418 	if (p->fts_info == FTS_INIT)
419 		return (p->fts_link);
420 
421 /* XXX why FTS_DNR?? */
422 	 /* If not a directory being visited in pre-order, stop here. */
423 	if (p->fts_info != FTS_D && p->fts_info != FTS_DNR)
424 		return (NULL);
425 
426 	/* Free up any previous child list. */
427 	if (sp->fts_child)
428 		fts_lfree(sp->fts_child);
429 
430 	/*
431 	 * If using chdir on a relative path and called BEFORE fts_read does
432 	 * its chdir to the root of a traversal, we can lose -- we need to
433 	 * chdir into the subdirectory, and we don't know where the current
434 	 * directory is, so we can't get back so that the upcoming chdir by
435 	 * fts_read will work.
436 	 */
437 	if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
438 	    ISSET(FTS_NOCHDIR))
439 		return (sp->fts_child = fts_build(sp, BCHILD));
440 
441 	if ((fd = open(".", O_RDONLY, 0)) < 0)
442 		return (NULL);
443 	sp->fts_child = fts_build(sp, BCHILD);
444 	if (fchdir(fd))
445 		return (NULL);
446 	(void)close(fd);
447 	return (sp->fts_child);
448 }
449 
450 /*
451  * This is the tricky part -- do not casually change *anything* in here.  The
452  * idea is to build the linked list of entries that are used by fts_children
453  * and fts_read.  There are lots of special cases.
454  *
455  * The real slowdown in walking the tree is the stat calls.  If FTS_NOSTAT is
456  * set and it's a physical walk (so that symbolic links can't be directories),
457  * we assume that the number of subdirectories in a node is equal to the number
458  * of links to the parent.  This allows stat calls to be skipped in any leaf
459  * directories and for any nodes after the directories in the parent node have
460  * been found.  This empirically cuts the stat calls by about 2/3.
461  */
462 static FTSENT *
463 fts_build(sp, type)
464 	register FTS *sp;
465 	int type;
466 {
467 	register struct dirent *dp;
468 	register FTSENT *p, *head;
469 	register int nitems;
470 	FTSENT *cur;
471 	DIR *dirp;
472 	void *adjaddr;
473 	int cderrno, descend, len, level, maxlen, nlinks, saved_errno;
474 	char *cp;
475 
476 	/* Set current node pointer. */
477 	cur = sp->fts_cur;
478 
479 	/*
480 	 * Open the directory for reading.  If this fails, we're done.
481 	 * If being called from fts_read, set the fts_info field.
482 	 */
483 	if ((dirp = opendir(cur->fts_accpath)) == NULL) {
484 		if (type == BREAD) {
485 			cur->fts_info = FTS_DNR;
486 			cur->fts_errno = errno;
487 		}
488 		return (NULL);
489 	}
490 
491 	/*
492 	 * Nlinks is the number of possible entries of type directory in the
493 	 * directory if we're cheating on stat calls, 0 if we're not doing
494 	 * any stat calls at all, -1 if we're doing stats on everything.
495 	 */
496 	nlinks =
497 	    ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL) ?
498 	    cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2) : -1;
499 
500 	/*
501 	 * If we're going to need to stat anything or we want to descend
502 	 * and stay in the directory, chdir.  If this fails we keep going.
503 	 * We won't be able to stat anything, but we can still return the
504 	 * names themselves.  Note, that since fts_read won't be able to
505 	 * chdir into the directory, it will have to return different path
506 	 * names than before, i.e. "a/b" instead of "b".  Since the node
507 	 * has already been visited in pre-order, have to wait until the
508 	 * post-order visit to return the error.  This is all fairly nasty.
509 	 * If a program needed sorted entries or stat information, they had
510 	 * better be checking FTS_NS on the returned nodes.
511 	 */
512 	if (nlinks || type == BREAD)
513 		if (FCHDIR(sp, dirfd(dirp))) {
514 			if (type == BREAD)
515 				cur->fts_errno = errno;
516 			descend = nlinks = 0;
517 			cderrno = errno;
518 		} else {
519 			descend = 1;
520 			cderrno = 0;
521 		}
522 	else
523 		descend = 0;
524 
525 	/*
526 	 * Figure out the max file name length that can be stored in the
527 	 * current path -- the inner loop allocates more path as necessary.
528 	 * We really wouldn't have to do the maxlen calculations here, we
529 	 * could do them in fts_read before returning the path, but it's a
530 	 * lot easier here since the length is part of the dirent structure.
531 	 *
532 	 * If not changing directories set a pointer so that can just append
533 	 * each new name into the path.
534 	 */
535 	maxlen = sp->fts_pathlen - cur->fts_pathlen - 1;
536 	len = NAPPEND(cur);
537 	if (ISSET(FTS_NOCHDIR)) {
538 		cp = sp->fts_path + len;
539 		*cp++ = '/';
540 	}
541 
542 	level = cur->fts_level + 1;
543 
544 	/* Read the directory, attaching each entry to the `link' pointer. */
545 	adjaddr = NULL;
546 	for (head = NULL, nitems = 0; dp = readdir(dirp);) {
547 		if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
548 			continue;
549 
550 		if ((p = fts_alloc(sp, dp->d_name, (int)dp->d_namlen)) == NULL)
551 			goto mem1;
552 		if (dp->d_namlen > maxlen) {
553 			if (fts_palloc(sp, (int)dp->d_namlen)) {
554 				/*
555 				 * No more memory for path or structures.  Save
556 				 * errno, free up the current structure and the
557 				 * structures already allocated.
558 				 */
559 mem1:				saved_errno = errno;
560 				if (p)
561 					free(p);
562 				fts_lfree(head);
563 				(void)closedir(dirp);
564 				errno = saved_errno;
565 				cur->fts_info = FTS_ERR;
566 				SET(FTS_STOP);
567 				return (NULL);
568 			}
569 			adjaddr = sp->fts_path;
570 			maxlen = sp->fts_pathlen - sp->fts_cur->fts_pathlen - 1;
571 		}
572 
573 		p->fts_pathlen = len + dp->d_namlen + 1;
574 		p->fts_parent = sp->fts_cur;
575 		p->fts_level = level;
576 
577 		if (nlinks) {
578 			/* Build a file name for fts_stat to stat. */
579 			if (ISSET(FTS_NOCHDIR)) {
580 				p->fts_accpath = p->fts_path;
581 				bcopy(p->fts_name, cp, p->fts_namelen + 1);
582 			} else
583 				p->fts_accpath = p->fts_name;
584 			p->fts_info = fts_stat(sp, p, 0);
585 			if (nlinks > 0 && (p->fts_info == FTS_D ||
586 			    p->fts_info == FTS_DC || p->fts_info == FTS_DOT))
587 				--nlinks;
588 		} else if (cderrno) {
589 			if (ISSET(FTS_NOSTAT))
590 				p->fts_info = FTS_NSOK;
591 		        else {
592 				p->fts_info = FTS_NS;
593 				p->fts_errno = cderrno;
594 			}
595 			p->fts_accpath = cur->fts_accpath;
596 		} else {
597 			p->fts_accpath =
598 			    ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
599 			p->fts_info = FTS_NSOK;
600 		}
601 
602 		p->fts_link = head;
603 		head = p;
604 		++nitems;
605 	}
606 	(void)closedir(dirp);
607 
608 	/*
609 	 * If had to realloc the path, adjust the addresses for the rest
610 	 * of the tree.
611 	 */
612 	if (adjaddr)
613 		fts_padjust(sp, adjaddr);
614 
615 	/*
616 	 * If not changing directories, reset the path back to original
617 	 * state.
618 	 */
619 	if (ISSET(FTS_NOCHDIR)) {
620 		if (cp - 1 > sp->fts_path)
621 			--cp;
622 		*cp = '\0';
623 	}
624 
625 	/*
626 	 * If descended after called from fts_children or called from
627 	 * fts_read and didn't find anything, get back.  If can't get
628 	 * back, done.
629 	 */
630 	if (descend && (!nitems || type == BCHILD) && CHDIR(sp, "..")) {
631 		cur->fts_info = FTS_ERR;
632 		SET(FTS_STOP);
633 		return (NULL);
634 	}
635 
636 	/* If didn't find anything, just do the post-order visit */
637 	if (!nitems) {
638 		if (type == BREAD)
639 			cur->fts_info = FTS_DP;
640 		return (NULL);
641 	}
642 
643 	/* Sort the entries. */
644 	if (sp->fts_compar && nitems > 1)
645 		head = fts_sort(sp, head, nitems);
646 	return (head);
647 }
648 
649 static u_short
650 fts_stat(sp, p, follow)
651 	FTS *sp;
652 	register FTSENT *p;
653 	int follow;
654 {
655 	register FTSENT *t;
656 	register dev_t dev;
657 	register ino_t ino;
658 	struct stat *sbp, sb;
659 	int saved_errno;
660 
661 	/* If user needs stat info, stat buffer already allocated. */
662 	sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp;
663 
664 	/*
665 	 * If doing a logical walk, or application requested FTS_FOLLOW, do
666 	 * a stat(2).  If that fails, check for a non-existent symlink.  If
667 	 * fail, set the errno from the stat call.
668 	 */
669 	if (ISSET(FTS_LOGICAL) || follow) {
670 		if (stat(p->fts_accpath, sbp)) {
671 			saved_errno = errno;
672 			if (!lstat(p->fts_accpath, sbp)) {
673 				errno = 0;
674 				return (FTS_SLNONE);
675 			}
676 			p->fts_errno = saved_errno;
677 			goto err;
678 		}
679 	} else if (lstat(p->fts_accpath, sbp)) {
680 		p->fts_errno = errno;
681 err:		bzero(sbp, sizeof(struct stat));
682 		return (FTS_NS);
683 	}
684 
685 	if (S_ISDIR(sbp->st_mode)) {
686 		if (ISDOT(p->fts_name))
687 			return (FTS_DOT);
688 		/*
689 		 * Set the device/inode.  Used to find cycles and check for
690 		 * crossing mount points.  Also remember the link count, used
691 		 * in fts_build to limit the number of stat calls.  It is
692 		 * understood that these fields are only referenced if fts_info
693 		 * is set to FTS_D.
694 		 */
695 		dev = p->fts_dev = sbp->st_dev;
696 		ino = p->fts_ino = sbp->st_ino;
697 		p->fts_nlink = sbp->st_nlink;
698 
699 		/*
700 		 * Cycle detection is done by brute force when the directory
701 		 * is first encountered.  If the tree gets deep enough or the
702 		 * number of symbolic links to directories is high enough,
703 		 * something faster might be worthwhile.
704 		 */
705 		for (t = p->fts_parent;
706 		    t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
707 			if (ino == t->fts_ino && dev == t->fts_dev) {
708 				p->fts_cycle = t;
709 				return (FTS_DC);
710 			}
711 		return (FTS_D);
712 	}
713 	if (S_ISLNK(sbp->st_mode))
714 		return (FTS_SL);
715 	if (S_ISREG(sbp->st_mode))
716 		return (FTS_F);
717 	return (FTS_DEFAULT);
718 }
719 
720 static FTSENT *
721 fts_sort(sp, head, nitems)
722 	FTS *sp;
723 	FTSENT *head;
724 	register int nitems;
725 {
726 	register FTSENT **ap, *p;
727 
728 	/*
729 	 * Construct an array of pointers to the structures and call qsort(3).
730 	 * Reassemble the array in the order returned by qsort.  If unable to
731 	 * sort for memory reasons, return the directory entries in their
732 	 * current order.  Allocate enough space for the current needs plus
733 	 * 40 so don't realloc one entry at a time.
734 	 */
735 	if (nitems > sp->fts_nitems) {
736 		sp->fts_nitems = nitems + 40;
737 		if ((sp->fts_array = realloc(sp->fts_array,
738 		    (size_t)(sp->fts_nitems * sizeof(FTSENT *)))) == NULL) {
739 			sp->fts_nitems = 0;
740 			return (head);
741 		}
742 	}
743 	for (ap = sp->fts_array, p = head; p; p = p->fts_link)
744 		*ap++ = p;
745 	qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), sp->fts_compar);
746 	for (head = *(ap = sp->fts_array); --nitems; ++ap)
747 		ap[0]->fts_link = ap[1];
748 	ap[0]->fts_link = NULL;
749 	return (head);
750 }
751 
752 static FTSENT *
753 fts_alloc(sp, name, len)
754 	FTS *sp;
755 	char *name;
756 	register int len;
757 {
758 	register FTSENT *p;
759 	int needstat;
760 
761 	/*
762 	 * Variable sized structures.  The stat structure isn't necessary
763 	 * if the user doesn't need it, and the name is variable length.
764 	 * Allocate enough extra space after the structure to store them.
765 	 */
766 	needstat = ISSET(FTS_NOSTAT) ? 0 : sizeof(struct stat);
767 	if ((p = malloc((size_t)(sizeof(FTSENT) + len + 1 + needstat))) == NULL)
768 		return (NULL);
769 	bcopy(name, p->fts_name, len + 1);
770 	if (needstat)
771 		p->fts_statp = (struct stat *)(p->fts_name + len + 1);
772 	p->fts_namelen = len;
773 	p->fts_path = sp->fts_path;
774 	p->fts_instr = FTS_NOINSTR;
775 	p->fts_errno = 0;
776 	p->fts_number = 0;
777 #ifdef NOT_NECESSARY
778 	p->fts_pointer = NULL;
779 #endif
780 	return (p);
781 }
782 
783 static void
784 fts_lfree(head)
785 	register FTSENT *head;
786 {
787 	register FTSENT *p;
788 
789 	/* Free a linked list of structures. */
790 	while (p = head) {
791 		head = head->fts_link;
792 		free(p);
793 	}
794 }
795 
796 /*
797  * Allow essentially unlimited paths; find, rm, ls should all work on any tree.
798  * Most systems will allow creation of paths much longer than MAXPATHLEN, even
799  * though the kernel won't resolve them.  Add the size (not just what's needed)
800  * plus 256 bytes so don't realloc the path 2 bytes at a time.
801  */
802 static int
803 fts_palloc(sp, more)
804 	FTS *sp;
805 	int more;
806 {
807 
808 	sp->fts_pathlen += more + 256;
809 	sp->fts_path = realloc(sp->fts_path, (size_t)sp->fts_pathlen);
810 	return (sp->fts_path == NULL);
811 }
812 
813 /*
814  * When the path is realloc'd, have to fix all of the pointers in structures
815  * already returned.
816  */
817 static void
818 fts_padjust(sp, addr)
819 	FTS *sp;
820 	void *addr;
821 {
822 	FTSENT *p;
823 
824 #define	ADJUST(p) { \
825 	(p)->fts_accpath = addr + ((p)->fts_accpath - (p)->fts_path); \
826 	(p)->fts_path = addr; \
827 }
828 	/* Adjust the current set of children. */
829 	for (p = sp->fts_child; p; p = p->fts_link)
830 		ADJUST(p);
831 
832 	/* Adjust the rest of the tree. */
833 	for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
834 		ADJUST(p);
835 		p = p->fts_link ? p->fts_link : p->fts_parent;
836 	}
837 }
838