![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to fts.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDReno / lib / libc / gen|
Return to fts.c CVS log | Up to [CSRG BSD Unix] / 43BSDReno / lib / libc / gen |
1.1 root 1: /*-
2: * Copyright (c) 1990 The Regents of the University of California.
3: * All rights reserved.
4: *
5: * Redistribution and use in source and binary forms are permitted provided
6: * that: (1) source distributions retain this entire copyright notice and
7: * comment, and (2) distributions including binaries display the following
8: * acknowledgement: ``This product includes software developed by the
9: * University of California, Berkeley and its contributors'' in the
10: * documentation or other materials provided with the distribution and in
11: * all advertising materials mentioning features or use of this software.
12: * Neither the name of the University nor the names of its contributors may
13: * be used to endorse or promote products derived from this software without
14: * specific prior written permission.
15: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
16: * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
17: * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
18: */
19:
20: #if defined(LIBC_SCCS) && !defined(lint)
21: static char sccsid[] = "@(#)fts.c 5.10 (Berkeley) 6/9/90";
22: #endif /* LIBC_SCCS and not lint */
23:
24: #include <sys/param.h>
25: #include <sys/stat.h>
26: #include <fcntl.h>
27: #include <dirent.h>
28: #include <errno.h>
29: #include <fts.h>
30: #include <string.h>
31: #include <stdlib.h>
32:
33: FTSENT *fts_alloc(), *fts_build(), *fts_cycle(), *fts_sort(), *fts_root();
34: short fts_stat();
35:
36: /*
37: * Special case a root of "/" so that slashes aren't appended causing
38: * paths to be written as "//foo".
39: */
40: #define NAPPEND(p) \
41: (p->fts_level == ROOTLEVEL && p->fts_pathlen == 1 && \
42: p->fts_path[0] == '/' ? 0 : p->fts_pathlen)
43:
44: #define CHDIR(sp, path) (!(sp->fts_options & FTS_NOCHDIR) && chdir(path))
45: #define FCHDIR(sp, fd) (!(sp->fts_options & FTS_NOCHDIR) && fchdir(fd))
46:
47: #define ROOTLEVEL 0
48: #define ROOTPARENTLEVEL -1
49:
50: /* fts_build flags */
51: #define BCHILD 1 /* from ftschildren */
52: #define BREAD 2 /* from ftsread */
53:
54: static FTS *stream; /* current stream pointer */
55:
56: FTS *
57: ftsopen(argv, options, compar)
58: char *argv[];
59: register int options;
60: int (*compar)();
61: {
62: register FTS *sp;
63: register FTSENT *p, *root;
64: register int nitems, maxlen;
65: FTSENT *parent, *tmp;
66: char *fts_path();
67:
68: /* allocate/initialize the stream */
69: if (!(stream = sp = (FTS *)malloc((u_int)sizeof(FTS))))
70: return(NULL);
71: bzero(sp, sizeof(FTS));
72: sp->fts_compar = compar;
73:
74: /*
75: * logical walks turn on NOCHDIR; symbolic links are just too
76: * hard to deal with.
77: */
78: sp->fts_options = options;
79: if (options & FTS_LOGICAL)
80: sp->fts_options |= FTS_NOCHDIR;
81:
82: /* allocate/initialize root's parent */
83: if (!(parent = fts_alloc("", 0)))
84: goto mem1;
85: parent->fts_level = ROOTPARENTLEVEL;
86:
87: /* allocate/initialize root(s) */
88: maxlen = -1;
89: for (root = NULL, nitems = 0; *argv; ++argv, ++nitems) {
90: if (!(p = fts_root(*argv)))
91: goto mem2;
92: if (maxlen < p->fts_namelen)
93: maxlen = p->fts_namelen;
94: /*
95: * if comparison routine supplied, traverse in sorted
96: * order; otherwise traverse in the order specified.
97: */
98: if (compar) {
99: p->fts_link = root;
100: root = p;
101: p->fts_accpath = p->fts_name;
102: if (!(options & FTS_NOSTAT))
103: p->fts_info = fts_stat(p, 0);
104: } else {
105: p->fts_link = NULL;
106: if (!root)
107: tmp = root = p;
108: else {
109: tmp->fts_link = p;
110: tmp = p;
111: }
112: }
113: p->fts_level = ROOTLEVEL;
114: p->fts_parent = parent;
115: }
116: if (compar && nitems > 1)
117: root = fts_sort(root, nitems);
118:
119: /*
120: * allocate a dummy pointer and make ftsread think that we've just
121: * finished the node before the root(s); set p->fts_info to FTS_NS
122: * so that everything about the "current" node is ignored.
123: */
124: if (!(sp->fts_cur = fts_alloc("", 0)))
125: goto mem2;
126: sp->fts_cur->fts_link = root;
127: sp->fts_cur->fts_info = FTS_NS;
128:
129: /* start out with at least 1K+ of path space */
130: if (!fts_path(MAX(maxlen, MAXPATHLEN)))
131: goto mem3;
132:
133: /*
134: * if using chdir(2), grab a file descriptor pointing to dot to insure
135: * that we can get back here; this could be avoided for some paths,
136: * but almost certainly not worth the effort. Slashes, symbolic links,
137: * and ".." are all fairly nasty problems. Note, if we can't get the
138: * descriptor we run anyway, just more slowly.
139: */
140: if (!(options & FTS_NOCHDIR) &&
141: (sp->fts_sd = open(".", O_RDONLY, 0)) < 0)
142: sp->fts_options |= FTS_NOCHDIR;
143:
144: return(sp);
145:
146: mem3: (void)free((void *)sp->fts_cur);
147: mem2: fts_lfree(root);
148: (void)free((void *)parent);
149: mem1: (void)free((void *)sp);
150: return(NULL);
151: }
152:
153: static
154: fts_load(p)
155: register FTSENT *p;
156: {
157: register int len;
158: register char *cp;
159:
160: /*
161: * load the stream structure for the next traversal; set the
162: * accpath field specially so the chdir gets done to the right
163: * place and the user can access the first node.
164: */
165: len = p->fts_pathlen = p->fts_namelen;
166: bcopy(p->fts_name, stream->fts_path, len + 1);
167: if ((cp = rindex(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
168: len = strlen(++cp);
169: bcopy(cp, p->fts_name, len + 1);
170: p->fts_namelen = len;
171: }
172: p->fts_accpath = p->fts_path = stream->fts_path;
173: }
174:
175: ftsclose(sp)
176: FTS *sp;
177: {
178: register FTSENT *freep, *p;
179: int saved_errno;
180:
181: if (sp->fts_cur) {
182: /*
183: * this still works if we haven't read anything -- the dummy
184: * structure points to the root list, so we step through to
185: * the end of the root list which has a valid parent pointer.
186: */
187: for (p = sp->fts_cur; p->fts_level > ROOTPARENTLEVEL;) {
188: freep = p;
189: p = p->fts_link ? p->fts_link : p->fts_parent;
190: (void)free((void *)freep);
191: }
192: (void)free((void *)p);
193: }
194:
195: /* free up child linked list, sort array, path buffer */
196: if (sp->fts_child)
197: fts_lfree(sp->fts_child);
198: if (sp->fts_array)
199: (void)free((void *)sp->fts_array);
200: (void)free((char *)sp->fts_path);
201:
202: /*
203: * return to original directory, save errno if necessary;
204: * free up the directory buffer
205: */
206: if (!(sp->fts_options & FTS_NOCHDIR)) {
207: saved_errno = fchdir(sp->fts_sd) ? errno : 0;
208: (void)close(sp->fts_sd);
209: }
210:
211: /* free up the stream pointer */
212: (void)free((void *)sp);
213:
214: /* set errno and return */
215: if (!(sp->fts_options & FTS_NOCHDIR) && saved_errno) {
216: errno = saved_errno;
217: return(-1);
218: }
219: return(0);
220: }
221:
222: FTSENT *
223: ftsread(sp)
224: register FTS *sp;
225: {
226: register FTSENT *p, *tmp;
227: register int instr;
228: register char *cp;
229: static int cd;
230:
231: /* if finished or unrecoverable error, return NULL */
232: if (!sp->fts_cur || sp->fts_options & FTS__STOP)
233: return(NULL);
234:
235: /* set global stream pointer, and current node pointer */
236: stream = sp;
237: p = sp->fts_cur;
238:
239: /* save and zero out user instructions */
240: instr = p->fts_instr;
241: p->fts_instr = 0;
242:
243: /* if used link pointer for cycle detection, restore it */
244: if (sp->fts_savelink) {
245: p->fts_link = sp->fts_savelink;
246: sp->fts_savelink = NULL;
247: }
248:
249: /* any type of file may be re-visited; re-stat and return */
250: if (instr == FTS_AGAIN) {
251: p->fts_info = fts_stat(p, 0);
252: return(p);
253: }
254:
255: /* following a symbolic link */
256: if (p->fts_info == FTS_SL && instr == FTS_FOLLOW) {
257: p->fts_info = fts_stat(p, 1);
258: return(p);
259: }
260:
261: /* directory in pre-order */
262: if (p->fts_info == FTS_D) {
263: /* if skipped or crossed mount point, do post-order visit */
264: if (instr == FTS_SKIP || sp->fts_options & FTS_XDEV &&
265: p->fts_statb.st_dev != sp->sdev) {
266: if (sp->fts_child) {
267: fts_lfree(sp->fts_child);
268: sp->fts_child = NULL;
269: }
270: p->fts_info = FTS_DP;
271: return(p);
272: }
273:
274: /* read the directory if necessary, and return first entry */
275: if (sp->fts_child)
276: if (CHDIR(sp, p->fts_accpath)) {
277: fts_lfree(sp->fts_child);
278: p->fts_info = FTS_DNX;
279: } else {
280: p = sp->fts_child;
281: cp = sp->fts_path + NAPPEND(p->fts_parent);
282: *cp++ = '/';
283: bcopy(p->fts_name, cp, p->fts_namelen + 1);
284: }
285: else {
286: if (!(sp->fts_child = fts_build(sp, BREAD)))
287: return(p);
288: p = sp->fts_child;
289: }
290: sp->fts_child = NULL;
291: return(sp->fts_cur = p);
292: }
293:
294: /* move to next node on this level */
295: next: tmp = p;
296: if (p = p->fts_link) {
297: /*
298: * if root level node, set up paths and return. If not the
299: * first time, and it's not an absolute pathname, get back
300: * to starting directory.
301: */
302: if (p->fts_level == ROOTLEVEL) {
303: fts_load(p);
304: (void)free((void *)tmp);
305: if (cd &&
306: p->fts_path[0] != '/' && FCHDIR(sp, sp->fts_sd)) {
307: /* should never happen... */
308: p->fts_path = "starting directory";
309: p->fts_info = FTS_ERR;
310: sp->fts_options |= FTS__STOP;
311: return(sp->fts_cur = p);
312: }
313: cd = 1;
314: p->fts_info = fts_stat(p, 0);
315: sp->sdev = p->fts_statb.st_dev;
316: } else {
317: (void)free((void *)tmp);
318:
319: /* user may have called ftsset on node */
320: if (p->fts_instr == FTS_SKIP)
321: goto next;
322: if (p->fts_instr == FTS_FOLLOW) {
323: p->fts_info = fts_stat(p, 1);
324: p->fts_instr = 0;
325: }
326:
327: /* fill in the paths */
328: cp = sp->fts_path + NAPPEND(p->fts_parent);
329: *cp++ = '/';
330: bcopy(p->fts_name, cp, p->fts_namelen + 1);
331:
332: /* check for directory cycles */
333: if (p->fts_info == FTS_D && (tmp = fts_cycle(p))) {
334: sp->fts_savelink = p->fts_link;
335: p->fts_link = tmp;
336: p->fts_info = FTS_DC;
337: }
338: }
339: return(sp->fts_cur = p);
340: }
341:
342: /* move to parent */
343: p = tmp->fts_parent;
344: (void)free((void *)tmp);
345:
346: if (p->fts_level == ROOTPARENTLEVEL) {
347: /*
348: * done; free everything up and set errno to 0 so the user
349: * can distinguish between error and EOF.
350: */
351: (void)free((void *)p);
352: errno = 0;
353: return(sp->fts_cur = NULL);
354: }
355:
356: sp->fts_path[p->fts_pathlen] = '\0';
357: if (CHDIR(sp, "..")) {
358: sp->fts_options |= FTS__STOP;
359: p->fts_info = FTS_ERR;
360: } else
361: p->fts_info = FTS_DP;
362: return(sp->fts_cur = p);
363: }
364:
365: /*
366: * ftsset takes the stream as an argument although it's not used in this
367: * implementation; it would be necessary if anyone wanted to add global
368: * semantics to fts using ftsset. A possible error return is allowed for
369: * similar reasons.
370: */
371: /* ARGSUSED */
372: ftsset(sp, p, instr)
373: FTS *sp;
374: FTSENT *p;
375: int instr;
376: {
377: p->fts_instr = instr;
378: return(0);
379: }
380:
381: FTSENT *
382: ftschildren(sp)
383: register FTS *sp;
384: {
385: register FTSENT *p;
386: int fd;
387:
388: /*
389: * set errno to 0 so that user can tell the difference between an
390: * error and a directory without entries.
391: */
392: errno = 0;
393: p = sp->fts_cur;
394: if (p->fts_info != FTS_D || sp->fts_options & FTS__STOP)
395: return(NULL);
396: if (sp->fts_child)
397: fts_lfree(sp->fts_child);
398:
399: /*
400: * if using chdir on a relative path and called BEFORE ftsread on the
401: * root of a traversal, we can lose because we need to chdir into the
402: * subdirectory, and we don't know where the current directory is to
403: * get back so that the upcoming chdir by ftsread will work.
404: */
405: if (p->fts_level != ROOTLEVEL || p->fts_accpath[0] == '/' ||
406: sp->fts_options & FTS_NOCHDIR)
407: return(sp->fts_child = fts_build(sp, BCHILD));
408:
409: if ((fd = open(".", O_RDONLY, 0)) < 0)
410: return(NULL);
411: sp->fts_child = fts_build(sp, BCHILD);
412: if (fchdir(fd))
413: return(NULL);
414: (void)close(fd);
415: return(sp->fts_child);
416: }
417:
418: #define ISDOT(a) (a[0] == '.' && (!a[1] || a[1] == '.' && !a[2]))
419:
420: FTSENT *
421: fts_build(sp, type)
422: register FTS *sp;
423: int type;
424: {
425: register struct dirent *dp;
426: register FTSENT *p, *head;
427: register int nitems;
428: DIR *dirp;
429: int descend, len, level, maxlen, nlinks, saved_errno;
430: char *cp;
431:
432: p = sp->fts_cur;
433: if (!(dirp = opendir(p->fts_accpath))) {
434: if (type == BREAD) {
435: errno = 0;
436: p->fts_info = FTS_DNR;
437: }
438: return(NULL);
439: }
440:
441: /*
442: * the real slowdown in walking the tree is the stat calls. If
443: * FTS_NOSTAT is set and it's a physical walk (so that symbolic
444: * links can't be directories), fts assumes that the number of
445: * subdirectories in a node is equal to the number of links to
446: * the parent. This allows stat calls to be skipped in any leaf
447: * directories and for any nodes after the directories in the
448: * parent node have been found. This empirically cuts the stat
449: * calls by about 2/3.
450: */
451: nlinks =
452: sp->fts_options & FTS_NOSTAT && sp->fts_options & FTS_PHYSICAL ?
453: p->fts_statb.st_nlink - (sp->fts_options & FTS_SEEDOT ? 0 : 2) : -1;
454:
455: /* if told to descend or found links and not told not to descend. */
456: if (nlinks || type == BREAD) {
457: if (FCHDIR(sp, dirfd(dirp))) {
458: if (type == BREAD) {
459: errno = 0;
460: p->fts_info = FTS_DNX;
461: }
462: (void)closedir(dirp);
463: return(NULL);
464: }
465: descend = 1;
466: } else
467: descend = 0;
468:
469: /* get max file name length that can be stored in current path */
470: maxlen = sp->fts_pathlen - p->fts_pathlen - 1;
471:
472: cp = sp->fts_path + (len = NAPPEND(p));
473: *cp++ = '/';
474:
475: level = p->fts_level + 1;
476:
477: /* read the directory, attching each new entry to the `link' pointer */
478: for (head = NULL, nitems = 0; dp = readdir(dirp);) {
479: if (ISDOT(dp->d_name) && !(sp->fts_options & FTS_SEEDOT))
480: continue;
481:
482: if (!(p = fts_alloc(dp->d_name, dp->d_namlen))) {
483: saved_errno = errno;
484: goto mem1;
485: }
486: if (dp->d_namlen > maxlen) {
487: if (!fts_path((int)dp->d_namlen)) {
488: /* quit: this stream no longer has a path */
489: sp->fts_options |= FTS__STOP;
490: saved_errno = errno;
491: (void)free((void *)p);
492: mem1: fts_lfree(head);
493: if (type == BREAD)
494: p->fts_info = FTS_ERR;
495: if (descend && CHDIR(sp, "..")) {
496: saved_errno = errno;
497: sp->fts_options |= FTS__STOP;
498: }
499: errno = saved_errno;
500: (void)closedir(dirp);
501: return(NULL);
502: }
503: maxlen = sp->fts_pathlen - sp->fts_cur->fts_pathlen - 1;
504: }
505:
506: p->fts_pathlen = len + dp->d_namlen + 1;
507: p->fts_accpath =
508: sp->fts_options & FTS_NOCHDIR ? p->fts_path : p->fts_name;
509:
510: p->fts_parent = sp->fts_cur;
511: p->fts_level = level;
512:
513: if (nlinks) {
514: /* make sure fts_stat has a filename to stat */
515: if (sp->fts_options & FTS_NOCHDIR)
516: bcopy(p->fts_name, cp, p->fts_namelen + 1);
517: p->fts_info = fts_stat(p, 0);
518: if (nlinks > 0 && (p->fts_info == FTS_D ||
519: p->fts_info == FTS_DNR || p->fts_info == FTS_DNX))
520: --nlinks;
521: } else
522: p->fts_info = FTS_NS;
523:
524: p->fts_link = head;
525: head = p;
526: ++nitems;
527: }
528: (void)closedir(dirp);
529:
530: /* reset the path */
531: if (cp - 1 > sp->fts_path)
532: --cp;
533: *cp = '\0';
534:
535: /*
536: * if descended: if were called from ftsread and didn't find anything,
537: * or were called from ftschildren, get back.
538: */
539: if (descend && (!nitems || type == BCHILD) && CHDIR(sp, "..")) {
540: sp->fts_options |= FTS__STOP;
541: p->fts_info = FTS_ERR;
542: return(NULL);
543: }
544:
545: if (!nitems) {
546: if (type == BREAD)
547: p->fts_info = FTS_DP;
548: return(NULL);
549: }
550:
551: if (sp->fts_compar && nitems > 1)
552: head = fts_sort(head, nitems);
553:
554: if (type == BREAD) {
555: *cp = '/';
556: bcopy(head->fts_name, cp + 1, head->fts_namelen + 1);
557: }
558: return(head);
559: }
560:
561: static short
562: fts_stat(p, symflag)
563: register FTSENT *p;
564: int symflag;
565: {
566: /*
567: * detection of symbolic links w/o targets. If FTS_FOLLOW is set,
568: * the symlink structure is overwritten with the stat structure of
569: * the target.
570: */
571: if (stream->fts_options & FTS_LOGICAL || symflag) {
572: if (stat(p->fts_accpath, &p->fts_statb))
573: return(symflag || !lstat(p->fts_accpath,
574: &p->fts_statb) ? FTS_SLNONE : FTS_ERR);
575: } else if (lstat(p->fts_accpath, &p->fts_statb))
576: return(FTS_ERR);
577:
578: switch(p->fts_statb.st_mode&S_IFMT) {
579: case S_IFDIR:
580: return(FTS_D);
581: case S_IFLNK:
582: return(FTS_SL);
583: case S_IFREG:
584: return(FTS_F);
585: }
586: return(FTS_DEFAULT);
587: }
588:
589: static FTSENT *
590: fts_cycle(p)
591: register FTSENT *p;
592: {
593: register dev_t dev;
594: register ino_t ino;
595:
596: /*
597: * cycle detection is brute force; if the tree gets deep enough or
598: * the number of symbolic links to directories is really high
599: * something faster might be worthwhile.
600: */
601: dev = p->fts_statb.st_dev;
602: ino = p->fts_statb.st_ino;
603: for (p = p->fts_parent; p->fts_level > ROOTLEVEL; p = p->fts_parent)
604: if (ino == p->fts_statb.st_ino && dev == p->fts_statb.st_dev)
605: return(p);
606: return(NULL);
607: }
608:
609: #define R(type, nelem, ptr) \
610: (type *)realloc((void *)ptr, (u_int)((nelem) * sizeof(type)))
611:
612: static FTSENT *
613: fts_sort(head, nitems)
614: FTSENT *head;
615: register int nitems;
616: {
617: register FTSENT **ap, *p;
618:
619: /*
620: * construct an array of pointers to the structures and call qsort(3).
621: * Reassemble the array in the order returned by qsort. If unable to
622: * sort for memory reasons, return the directory entries in their
623: * current order. Allocate enough space for the current needs plus
624: * 40 so we don't realloc one entry at a time.
625: */
626: if (nitems > stream->fts_nitems) {
627: stream->fts_nitems = nitems + 40;
628: if (!(stream->fts_array =
629: R(FTSENT *, stream->fts_nitems, stream->fts_array))) {
630: stream->fts_nitems = 0;
631: return(head);
632: }
633: }
634: for (ap = stream->fts_array, p = head; p; p = p->fts_link)
635: *ap++ = p;
636: qsort((void *)stream->fts_array, nitems, sizeof(FTSENT *),
637: stream->fts_compar);
638: for (head = *(ap = stream->fts_array); --nitems; ++ap)
639: ap[0]->fts_link = ap[1];
640: ap[0]->fts_link = NULL;
641: return(head);
642: }
643:
644: static FTSENT *
645: fts_alloc(name, len)
646: char *name;
647: register int len;
648: {
649: register FTSENT *p;
650:
651: /*
652: * variable sized structures; the name is the last element so
653: * allocate enough extra space after the structure to hold it.
654: */
655: if (!(p = (FTSENT *)malloc((size_t)(sizeof(FTSENT) + len))))
656: return(NULL);
657: bcopy(name, p->fts_name, len + 1);
658: p->fts_namelen = len;
659: p->fts_path = stream->fts_path;
660: p->fts_instr = 0;
661: p->fts_local.number = 0;
662: p->fts_local.pointer = NULL;
663: return(p);
664: }
665:
666: static
667: fts_lfree(head)
668: register FTSENT *head;
669: {
670: register FTSENT *p;
671:
672: while (p = head) {
673: head = head->fts_link;
674: (void)free((void *)p);
675: }
676: }
677:
678: /*
679: * allow essentially unlimited paths; certain programs (find, remove, ls)
680: * need to work on any tree. Most systems will allow creation of paths
681: * much longer than MAXPATHLEN, even though the kernel won't resolve them.
682: * Add an extra 128 bytes to the requested size so that we don't realloc
683: * the path 2 bytes at a time.
684: */
685: static char *
686: fts_path(size)
687: int size;
688: {
689: stream->fts_pathlen += size + 128;
690: return(stream->fts_path =
691: R(char, stream->fts_pathlen, stream->fts_path));
692: }
693:
694: static FTSENT *
695: fts_root(name)
696: register char *name;
697: {
698: register char *cp;
699:
700: /*
701: * rip trailing slashes; it's somewhat unclear in POSIX 1003.1 what
702: * /a/b/ really is, they don't talk about what a null path component
703: * resolves to. This hopefully does what the user intended. Don't
704: * allow null pathnames.
705: */
706: for (cp = name; *cp; ++cp);
707: if (cp == name) {
708: errno = ENOENT;
709: return(NULL);
710: }
711: while (--cp > name && *cp == '/');
712: *++cp = '\0';
713: return(fts_alloc(name, cp - name));
714: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.