1 /***********************************************************************
2 * *
3 * This software is part of the ast package *
4 * Copyright (c) 1985-2010 AT&T Intellectual Property *
5 * and is licensed under the *
6 * Common Public License, Version 1.0 *
7 * by AT&T Intellectual Property *
8 * *
9 * A copy of the License is available at *
10 * http://www.opensource.org/licenses/cpl1.0.txt *
11 * (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) *
12 * *
13 * Information and Software Systems Research *
14 * AT&T Research *
15 * Florham Park NJ *
16 * *
17 * Glenn Fowler <gsf@research.att.com> *
18 * David Korn <dgk@research.att.com> *
19 * Phong Vo <kpv@research.att.com> *
20 * *
21 ***********************************************************************/
22 #pragma prototyped
23 /*
24 * Phong Vo
25 * Glenn Fowler
26 * AT&T Research
27 *
28 * fts implementation unwound from the kpv ftwalk() of 1988-10-30
29 */
30
31 #include <ast.h>
32 #include <ast_dir.h>
33 #include <error.h>
34 #include <fs3d.h>
35 #include <ls.h>
36
37 struct Ftsent;
38
39 typedef int (*Compar_f)(struct Ftsent* const*, struct Ftsent* const*);
40 typedef int (*Stat_f)(const char*, struct stat*);
41
42 #define _fts_status status
43 #define _fts_statb statb
44
45 #define _FTS_PRIVATE_ \
46 FTSENT* parent; /* top parent */ \
47 FTSENT* todo; /* todo list */ \
48 FTSENT* top; /* top element */ \
49 FTSENT* root; \
50 FTSENT* bot; /* bottom element */ \
51 FTSENT* free; /* free element */ \
52 FTSENT* diroot; \
53 FTSENT* curdir; \
54 FTSENT* current; /* current element */ \
55 FTSENT* previous; /* previous current */ \
56 FTSENT* dotdot; \
57 FTSENT* link; /* real current fts_link*/ \
58 FTSENT* pwd; /* pwd parent */ \
59 DIR* dir; /* current dir stream */ \
60 Compar_f comparf; /* node comparison func */ \
61 size_t baselen; /* current strlen(base) */ \
62 size_t homesize; /* sizeof(home) */ \
63 int cd; /* chdir status */ \
64 int cpname; \
65 int flags; /* fts_open() flags */ \
66 int nd; \
67 unsigned char children; \
68 unsigned char fs3d; \
69 unsigned char nostat; \
70 unsigned char state; /* fts_read() state */ \
71 char* base; /* basename in path */ \
72 char* name; \
73 char* path; /* path workspace */ \
74 char* home; /* home/path buffer */ \
75 char* endbase; /* space to build paths */ \
76 char* endbuf; /* space to build paths */ \
77 char* pad[2]; /* $0.02 to splain this */
78
79 /*
80 * NOTE: <ftwalk.h> relies on status and statb being the first two elements
81 */
82
83 #define _FTSENT_PRIVATE_ \
84 int nd; /* popdir() count */ \
85 FTSENT* left; /* left child */ \
86 FTSENT* right; /* right child */ \
87 FTSENT* pwd; /* pwd parent */ \
88 FTSENT* stack; /* getlist() stack */ \
89 long nlink; /* FTS_D link count */ \
90 unsigned char must; /* must stat */ \
91 unsigned char type; /* DT_* type */ \
92 unsigned char symlink; /* originally a symlink */ \
93 char name[sizeof(int)]; /* fts_name data */
94
95 #include <fts.h>
96
97 #ifndef ENOSYS
98 #define ENOSYS EINVAL
99 #endif
100
101
102 #if MAXNAMLEN > 16
103 #define MINNAME 32
104 #else
105 #define MINNAME 16
106 #endif
107
108 #define drop(p,f) (((f)->fts_namelen < MINNAME) ? ((f)->fts_link = (p)->free, (p)->free = (f)) : (free(f), (p)->free))
109
110 #define ACCESS(p,f) ((p)->cd==0?(f)->fts_name:(f)->fts_path)
111 #define PATH(f,p,l) ((!((f)->flags&FTS_SEEDOTDIR)&&(l)>0&&(p)[0]=='.'&&(p)[1]=='/')?((p)+2):(p))
112 #define SAME(one,two) ((one)->st_ino==(two)->st_ino&&(one)->st_dev==(two)->st_dev)
113 #define SKIPLINK(p,f) ((f)->fts_parent->nlink == 0)
114
115 #ifdef D_TYPE
116 #define ISTYPE(f,t) ((f)->type == (t))
117 #define TYPE(f,t) ((f)->type = (t))
118 #define SKIP(p,f) ((f)->fts_parent->must == 0 && (((f)->type == DT_UNKNOWN) ? SKIPLINK(p,f) : ((f)->type != DT_DIR && ((f)->type != DT_LNK || ((p)->flags & FTS_PHYSICAL)))))
119 #else
120 #undef DT_UNKNOWN
121 #define DT_UNKNOWN 0
122 #undef DT_LNK
123 #define DT_LNK 1
124 #define ISTYPE(f,t) ((t)==DT_UNKNOWN)
125 #define TYPE(f,d)
126 #define SKIP(p,f) ((f)->fts_parent->must == 0 && SKIPLINK(p,f))
127 #endif
128
129 #ifndef D_FILENO
130 #define D_FILENO(d) (1)
131 #endif
132
133 /*
134 * NOTE: a malicious dir rename() could change .. underfoot so we
135 * must always verify; undef verify to enable the unsafe code
136 */
137
138 #define verify 1
139
140 /*
141 * FTS_NOSTAT requires a dir with
142 * D_TYPE(&dirent_t)!=DT_UNKNOWN
143 * OR
144 * st_nlink>=2
145 */
146
147 #define FTS_children_resume 1
148 #define FTS_children_return 2
149 #define FTS_error 3
150 #define FTS_popstack 4
151 #define FTS_popstack_resume 5
152 #define FTS_popstack_return 6
153 #define FTS_preorder 7
154 #define FTS_preorder_resume 8
155 #define FTS_preorder_return 9
156 #define FTS_readdir 10
157 #define FTS_terminal 11
158 #define FTS_todo 12
159 #define FTS_top_return 13
160
161 typedef int (*Notify_f)(FTS*, FTSENT*, void*);
162
163 typedef struct Notify_s
164 {
165 struct Notify_s* next;
166 Notify_f notifyf;
167 void* context;
168 } Notify_t;
169
170 static Notify_t* notify;
171
172 /*
173 * allocate an FTSENT node
174 */
175
176 static FTSENT*
node(FTS * fts,FTSENT * parent,register char * name,register size_t namelen)177 node(FTS* fts, FTSENT* parent, register char* name, register size_t namelen)
178 {
179 register FTSENT* f;
180 register size_t n;
181
182 if (fts->free && namelen < MINNAME)
183 {
184 f = fts->free;
185 fts->free = f->fts_link;
186 }
187 else
188 {
189 n = (namelen < MINNAME ? MINNAME : namelen + 1) - sizeof(int);
190 if (!(f = newof(0, FTSENT, 1, n)))
191 {
192 fts->fts_errno = errno;
193 fts->state = FTS_error;
194 return 0;
195 }
196 f->fts = fts;
197 }
198 TYPE(f, DT_UNKNOWN);
199 f->status = 0;
200 f->symlink = 0;
201 f->fts_level = (f->fts_parent = parent)->fts_level + 1;
202 #if __OBSOLETE__ < 20140101
203 f->_fts_level = (short)f->fts_level;
204 #endif
205 f->fts_link = 0;
206 f->fts_pointer = 0;
207 f->fts_number = 0;
208 f->fts_errno = 0;
209 f->fts_namelen = namelen;
210 #if __OBSOLETE__ < 20140101
211 f->_fts_namelen = (unsigned short)f->fts_namelen;
212 #endif
213 f->fts_name = f->name;
214 f->fts_statp = &f->statb;
215 memcpy(f->fts_name, name, namelen + 1);
216 return f;
217 }
218
219 /*
220 * compare directories by device/inode
221 */
222
223 static int
statcmp(FTSENT * const * pf1,FTSENT * const * pf2)224 statcmp(FTSENT* const* pf1, FTSENT* const* pf2)
225 {
226 register const FTSENT* f1 = *pf1;
227 register const FTSENT* f2 = *pf2;
228
229 if (f1->statb.st_ino < f2->statb.st_ino)
230 return -1;
231 if (f1->statb.st_ino > f2->statb.st_ino)
232 return 1;
233 if (f1->statb.st_dev < f2->statb.st_dev)
234 return -1;
235 if (f1->statb.st_dev > f2->statb.st_dev)
236 return 1;
237
238 /*
239 * hack for NFS where <dev,ino> may not uniquely identify objects
240 */
241
242 if (f1->statb.st_mtime < f2->statb.st_mtime)
243 return -1;
244 if (f1->statb.st_mtime > f2->statb.st_mtime)
245 return 1;
246 return 0;
247 }
248
249 /*
250 * search trees with top-down splaying (a la Tarjan and Sleator)
251 * when used for insertion sort, this implements a stable sort
252 */
253
254 #define RROTATE(r) (t = r->left, r->left = t->right, t->right = r, r = t)
255 #define LROTATE(r) (t = r->right, r->right = t->left, t->left = r, r = t)
256
257 static FTSENT*
search(FTSENT * e,FTSENT * root,int (* comparf)(FTSENT * const *,FTSENT * const *),int insert)258 search(FTSENT* e, FTSENT* root, int(*comparf)(FTSENT* const*, FTSENT* const*), int insert)
259 {
260 register int cmp;
261 register FTSENT* t;
262 register FTSENT* left;
263 register FTSENT* right;
264 register FTSENT* lroot;
265 register FTSENT* rroot;
266
267 left = right = lroot = rroot = 0;
268 while (root)
269 {
270 if (!(cmp = (*comparf)(&e, &root)) && !insert)
271 break;
272 if (cmp < 0)
273 {
274 /*
275 * this is the left zig-zig case
276 */
277
278 if (root->left && (cmp = (*comparf)(&e, &root->left)) <= 0)
279 {
280 RROTATE(root);
281 if (!cmp && !insert)
282 break;
283 }
284
285 /*
286 * stick all things > e to the right tree
287 */
288
289 if (right)
290 right->left = root;
291 else
292 rroot = root;
293 right = root;
294 root = root->left;
295 right->left = 0;
296 }
297 else
298 {
299 /*
300 * this is the right zig-zig case
301 */
302
303 if (root->right && (cmp = (*comparf)(&e, &root->right)) >= 0)
304 {
305 LROTATE(root);
306 if (!cmp && !insert)
307 break;
308 }
309
310 /*
311 * stick all things <= e to the left tree
312 */
313
314 if (left)
315 left->right = root;
316 else
317 lroot = root;
318 left = root;
319 root = root->right;
320 left->right = 0;
321 }
322 }
323 if (!root)
324 root = e;
325 else
326 {
327 if (right)
328 right->left = root->right;
329 else
330 rroot = root->right;
331 if (left)
332 left->right = root->left;
333 else
334 lroot = root->left;
335 }
336 root->left = lroot;
337 root->right = rroot;
338 return root;
339 }
340
341 /*
342 * delete the root element from the tree
343 */
344
345 static FTSENT*
deleteroot(register FTSENT * root)346 deleteroot(register FTSENT* root)
347 {
348 register FTSENT* t;
349 register FTSENT* left;
350 register FTSENT* right;
351
352 right = root->right;
353 if (!(left = root->left))
354 root = right;
355 else
356 {
357 while (left->right)
358 LROTATE(left);
359 left->right = right;
360 root = left;
361 }
362 return root;
363 }
364
365 /*
366 * generate ordered fts_link list from binary tree at root
367 * FTSENT.stack instead of recursion to avoid blowing the real
368 * stack on big directories
369 */
370
371 static void
getlist(register FTSENT ** top,register FTSENT ** bot,register FTSENT * root)372 getlist(register FTSENT** top, register FTSENT** bot, register FTSENT* root)
373 {
374 register FTSENT* stack = 0;
375
376 for (;;)
377 {
378 if (root->left)
379 {
380 root->stack = stack;
381 stack = root;
382 root = root->left;
383 }
384 else
385 {
386 for (;;)
387 {
388 if (*top)
389 *bot = (*bot)->fts_link = root;
390 else
391 *bot = *top = root;
392 if (root->right)
393 {
394 root = root->right;
395 break;
396 }
397 if (!(root = stack))
398 {
399 (*bot)->fts_link = 0;
400 return;
401 }
402 stack = stack->stack;
403 }
404 }
405 }
406 }
407
408 /*
409 * set directory when curdir is lost in space
410 */
411
412 static int
setdir(register char * home,register char * path)413 setdir(register char* home, register char* path)
414 {
415 register int cdrv;
416
417 if (path[0] == '/')
418 cdrv = pathcd(path, NiL);
419 else
420 {
421 /*
422 * note that path and home are in the same buffer
423 */
424
425 path[-1] = '/';
426 cdrv = pathcd(home, NiL);
427 path[-1] = 0;
428 }
429 if (cdrv < 0)
430 pathcd(home, NiL);
431 return cdrv;
432 }
433
434 /*
435 * set to parent dir
436 */
437
438 static int
setpdir(register char * home,register char * path,register char * base)439 setpdir(register char* home, register char* path, register char* base)
440 {
441 register int c;
442 register int cdrv;
443
444 if (base > path)
445 {
446 c = base[0];
447 base[0] = 0;
448 cdrv = setdir(home, path);
449 base[0] = c;
450 }
451 else
452 cdrv = pathcd(home, NiL);
453 return cdrv;
454 }
455
456 /*
457 * pop a set of directories
458 */
459 static int
popdirs(FTS * fts)460 popdirs(FTS* fts)
461 {
462 register FTSENT*f;
463 register char* s;
464 register char* e;
465 #ifndef verify
466 register int verify;
467 #endif
468 struct stat sb;
469 char buf[PATH_MAX];
470
471 if (!(f = fts->curdir) || f->fts_level < 0)
472 return -1;
473 e = buf + sizeof(buf) - 4;
474 #ifndef verify
475 verify = 0;
476 #endif
477 while (fts->nd > 0)
478 {
479 for (s = buf; s < e && fts->nd > 0; fts->nd--)
480 {
481 if (fts->pwd)
482 {
483 #ifndef verify
484 verify |= fts->pwd->symlink;
485 #endif
486 fts->pwd = fts->pwd->pwd;
487 }
488 *s++ = '.';
489 *s++ = '.';
490 *s++ = '/';
491 }
492 *s = 0;
493 if (chdir(buf))
494 return -1;
495 }
496 return (verify && (stat(".", &sb) < 0 || !SAME(&sb, f->fts_statp))) ? -1 : 0;
497 }
498
499 /*
500 * initialize st from path and fts_info from st
501 */
502
503 static int
info(FTS * fts,register FTSENT * f,const char * path,struct stat * sp,int flags)504 info(FTS* fts, register FTSENT* f, const char* path, struct stat* sp, int flags)
505 {
506 if (path)
507 {
508 #ifdef S_ISLNK
509 if (!f->symlink && (ISTYPE(f, DT_UNKNOWN) || ISTYPE(f, DT_LNK)))
510 {
511 if (lstat(path, sp) < 0)
512 goto bad;
513 }
514 else
515 #endif
516 if (stat(path, sp) < 0)
517 goto bad;
518 }
519 #ifdef S_ISLNK
520 again:
521 #endif
522 if (S_ISDIR(sp->st_mode))
523 {
524 if ((flags & FTS_NOSTAT) && !fts->fs3d)
525 {
526 f->fts_parent->nlink--;
527 #ifdef D_TYPE
528 if ((f->nlink = sp->st_nlink) < 2)
529 {
530 f->must = 2;
531 f->nlink = 2;
532 }
533 else
534 f->must = 0;
535 #else
536 if ((f->nlink = sp->st_nlink) >= 2)
537 f->must = 1;
538 else
539 f->must = 2;
540 #endif
541 }
542 else
543 f->must = 2;
544 TYPE(f, DT_DIR);
545 f->fts_info = FTS_D;
546 }
547 #ifdef S_ISLNK
548 else if (S_ISLNK((sp)->st_mode))
549 {
550 struct stat sb;
551
552 f->symlink = 1;
553 if (!(flags & FTS_PHYSICAL) && stat(path, &sb) >= 0)
554 {
555 *sp = sb;
556 flags = FTS_PHYSICAL;
557 goto again;
558 }
559 TYPE(f, DT_LNK);
560 f->fts_info = FTS_SL;
561 }
562 #endif
563 else
564 {
565 TYPE(f, DT_REG);
566 f->fts_info = FTS_F;
567 }
568 return 0;
569 bad:
570 TYPE(f, DT_UNKNOWN);
571 f->fts_info = FTS_NS;
572 return -1;
573 }
574
575 /*
576 * get top list of elements to process
577 * ordering delayed until first fts_read()
578 * to give caller a chance to set fts->handle
579 */
580
581 static FTSENT*
toplist(FTS * fts,register char * const * pathnames)582 toplist(FTS* fts, register char* const* pathnames)
583 {
584 register char* path;
585 register FTSENT* f;
586 register FTSENT* top;
587 register FTSENT* bot;
588 int physical;
589 int metaphysical;
590 char* s;
591 struct stat st;
592
593 if (fts->flags & FTS_NOSEEDOTDIR)
594 fts->flags &= ~FTS_SEEDOTDIR;
595 physical = (fts->flags & FTS_PHYSICAL);
596 metaphysical = (fts->flags & (FTS_META|FTS_PHYSICAL)) == (FTS_META|FTS_PHYSICAL);
597 top = bot = 0;
598 while (path = *pathnames++)
599 {
600 /*
601 * make elements
602 */
603
604 if (!(f = node(fts, fts->parent, path, strlen(path))))
605 break;
606 path = f->fts_name;
607 if (!physical)
608 f->fts_namelen = (fts->flags & FTS_SEEDOTDIR) ? strlen(path) : (pathcanon(path, 0) - path);
609 else if (*path != '.')
610 {
611 f->fts_namelen = strlen(path);
612 fts->flags |= FTS_SEEDOTDIR;
613 }
614 else
615 {
616 if (fts->flags & FTS_NOSEEDOTDIR)
617 {
618 fts->flags &= ~FTS_SEEDOTDIR;
619 s = path;
620 while (*s++ == '.' && *s++ == '/')
621 {
622 while (*s == '/')
623 s++;
624 if (!*s)
625 break;
626 path = f->fts_name;
627 while (*path++ = *s++);
628 path = f->fts_name;
629 }
630 }
631 else
632 fts->flags |= FTS_SEEDOTDIR;
633 for (s = path + strlen(path); s > path && *(s - 1) == '/'; s--);
634 *s = 0;
635 f->fts_namelen = s - path;
636 }
637 #if __OBSOLETE__ < 20140101
638 f->_fts_namelen = (unsigned short)f->fts_namelen;
639 #endif
640 if (!*path)
641 {
642 errno = ENOENT;
643 f->fts_info = FTS_NS;
644 }
645 else
646 info(fts, f, path, f->fts_statp, fts->flags);
647 #ifdef S_ISLNK
648
649 /*
650 * don't let any standards committee get
651 * away with calling your idea a hack
652 */
653
654 if (metaphysical && f->fts_info == FTS_SL && stat(path, &st) >= 0)
655 {
656 *f->fts_statp = st;
657 info(fts, f, NiL, f->fts_statp, 0);
658 }
659 #endif
660 if (bot)
661 {
662 bot->fts_link = f;
663 bot = f;
664 }
665 else
666 top = bot = f;
667 }
668 return top;
669 }
670
671 /*
672 * order fts->todo if fts->comparf != 0
673 */
674
675 static void
order(FTS * fts)676 order(FTS* fts)
677 {
678 register FTSENT* f;
679 register FTSENT* root;
680 FTSENT* top;
681 FTSENT* bot;
682
683 top = bot = root = 0;
684 for (f = fts->todo; f; f = f->fts_link)
685 root = search(f, root, fts->comparf, 1);
686 getlist(&top, &bot, root);
687 fts->todo = top;
688 }
689
690 /*
691 * resize the path buffer
692 * note that free() is not used because we may need to chdir(fts->home)
693 * if there isn't enough space to continue
694 */
695
696 static int
resize(register FTS * fts,size_t inc)697 resize(register FTS* fts, size_t inc)
698 {
699 register char* old;
700 register char* newp;
701 register size_t n_old;
702
703 /*
704 * add space for "/." used in testing FTS_DNX
705 */
706
707 n_old = fts->homesize;
708 fts->homesize = ((fts->homesize + inc + 4) / PATH_MAX + 1) * PATH_MAX;
709 if (!(newp = newof(0, char, fts->homesize, 0)))
710 {
711 fts->fts_errno = errno;
712 fts->state = FTS_error;
713 return -1;
714 }
715 old = fts->home;
716 fts->home = newp;
717 memcpy(newp, old, n_old);
718 if (fts->endbuf)
719 fts->endbuf = newp + fts->homesize - 4;
720 if (fts->path)
721 fts->path = newp + (fts->path - old);
722 if (fts->base)
723 fts->base = newp + (fts->base - old);
724 free(old);
725 return 0;
726 }
727
728 /*
729 * open a new fts stream on pathnames
730 */
731
732 FTS*
fts_open(char * const * pathnames,int flags,int (* comparf)(FTSENT * const *,FTSENT * const *))733 fts_open(char* const* pathnames, int flags, int (*comparf)(FTSENT* const*, FTSENT* const*))
734 {
735 register FTS* fts;
736
737 if (!(fts = newof(0, FTS, 1, sizeof(FTSENT))))
738 return 0;
739 fts->flags = flags;
740 fts->cd = (flags & FTS_NOCHDIR) ? 1 : -1;
741 fts->comparf = comparf;
742 fts->fs3d = fs3d(FS3D_TEST);
743
744 /*
745 * set up the path work buffer
746 */
747
748 fts->homesize = 2 * PATH_MAX;
749 for (;;)
750 {
751 if (!(fts->home = newof(fts->home, char, fts->homesize, 0)))
752 {
753 free(fts);
754 return 0;
755 }
756 if (fts->cd > 0 || getcwd(fts->home, fts->homesize))
757 break;
758 if (errno == ERANGE)
759 fts->homesize += PATH_MAX;
760 else
761 fts->cd = 1;
762 }
763 fts->endbuf = fts->home + fts->homesize - 4;
764
765 /*
766 * initialize the tippity-top
767 */
768
769 fts->parent = (FTSENT*)(fts + 1);
770 fts->parent->fts_info = FTS_D;
771 memcpy(fts->parent->fts_accpath = fts->parent->fts_path = fts->parent->fts_name = fts->parent->name, ".", 2);
772 fts->parent->fts_level = -1;
773 #if __OBSOLETE__ < 20140101
774 fts->parent->_fts_level = (short)fts->parent->fts_level;
775 #endif
776 fts->parent->fts_statp = &fts->parent->statb;
777 fts->parent->must = 2;
778 fts->parent->type = DT_UNKNOWN;
779 fts->path = fts->home + strlen(fts->home) + 1;
780
781 /*
782 * make the list of top elements
783 */
784
785 if (!pathnames || (flags & FTS_ONEPATH) || !*pathnames)
786 {
787 char* v[2];
788
789 v[0] = pathnames && (flags & FTS_ONEPATH) ? (char*)pathnames : ".";
790 v[1] = 0;
791 fts->todo = toplist(fts, v);
792 }
793 else
794 fts->todo = toplist(fts, pathnames);
795 if (!fts->todo || fts->todo->fts_info == FTS_NS && !fts->todo->fts_link)
796 {
797 fts_close(fts);
798 return 0;
799 }
800 return fts;
801 }
802
803 /*
804 * return the next FTS entry
805 */
806
807 FTSENT*
fts_read(register FTS * fts)808 fts_read(register FTS* fts)
809 {
810 register char* s;
811 register int n;
812 register FTSENT* f;
813 struct dirent* d;
814 size_t i;
815 FTSENT* t;
816 Notify_t* p;
817 #ifdef verify
818 struct stat sb;
819 #endif
820
821 for (;;)
822 switch (fts->state)
823 {
824
825 case FTS_top_return:
826
827 f = fts->todo;
828 t = 0;
829 while (f)
830 if (f->status == FTS_SKIP)
831 {
832 if (t)
833 {
834 t->fts_link = f->fts_link;
835 drop(fts, f);
836 f = t->fts_link;
837 }
838 else
839 {
840 fts->todo = f->fts_link;
841 drop(fts, f);
842 f = fts->todo;
843 }
844 }
845 else
846 {
847 t = f;
848 f = f->fts_link;
849 }
850 /*FALLTHROUGH*/
851
852 case 0:
853
854 if (!fts->state && fts->comparf)
855 order(fts);
856 if (!(f = fts->todo))
857 return 0;
858 /*FALLTHROUGH*/
859
860 case FTS_todo:
861
862 /*
863 * process the top object on the stack
864 */
865
866 fts->root = fts->top = fts->bot = 0;
867
868 /*
869 * initialize the top level
870 */
871
872 if (f->fts_level == 0)
873 {
874 fts->parent->fts_number = f->fts_number;
875 fts->parent->fts_pointer = f->fts_pointer;
876 fts->parent->fts_statp = f->fts_statp;
877 fts->parent->statb = *f->fts_statp;
878 f->fts_parent = fts->parent;
879 fts->diroot = 0;
880 if (fts->cd == 0)
881 pathcd(fts->home, NiL);
882 else if (fts->cd < 0)
883 fts->cd = 0;
884 fts->pwd = f->fts_parent;
885 fts->curdir = fts->cd ? 0 : f->fts_parent;
886 *(fts->base = fts->path) = 0;
887 }
888
889 /*
890 * chdir to parent if asked for
891 */
892
893 if (fts->cd < 0)
894 {
895 fts->cd = setdir(fts->home, fts->path);
896 fts->pwd = f->fts_parent;
897 fts->curdir = fts->cd ? 0 : f->fts_parent;
898 }
899
900 /*
901 * add object's name to the path
902 */
903
904 if ((fts->baselen = f->fts_namelen) >= (fts->endbuf - fts->base) && resize(fts, fts->baselen))
905 return 0;
906 memcpy(fts->base, f->name, fts->baselen + 1);
907 fts->name = fts->cd ? fts->path : fts->base;
908 /*FALLTHROUGH*/
909
910 case FTS_preorder:
911
912 /*
913 * check for cycle and open dir
914 */
915
916 if (f->fts_info == FTS_D)
917 {
918 if ((fts->diroot = search(f, fts->diroot, statcmp, 0)) != f || f->fts_level > 0 && (t = f) && statcmp(&t, &f->fts_parent) == 0)
919 {
920 f->fts_info = FTS_DC;
921 f->fts_cycle = fts->diroot;
922 }
923 else if (!(fts->flags & FTS_TOP) && (!(fts->flags & FTS_XDEV) || f->statb.st_dev == f->fts_parent->statb.st_dev))
924 {
925 /*
926 * buffer is known to be large enough here!
927 */
928
929 if (fts->base[fts->baselen - 1] != '/')
930 memcpy(fts->base + fts->baselen, "/.", 3);
931 if (!(fts->dir = opendir(fts->name)))
932 f->fts_info = FTS_DNX;
933 fts->base[fts->baselen] = 0;
934 if (!fts->dir && !(fts->dir = opendir(fts->name)))
935 f->fts_info = FTS_DNR;
936 }
937 }
938 f->nd = f->fts_info & ~FTS_DNX;
939 if (f->nd || !(fts->flags & FTS_NOPREORDER))
940 {
941 fts->current = f;
942 fts->link = f->fts_link;
943 f->fts_link = 0;
944 f->fts_path = PATH(fts, fts->path, f->fts_level);
945 f->fts_pathlen = (fts->base - f->fts_path) + fts->baselen;
946 f->fts_accpath = ACCESS(fts, f);
947 fts->state = FTS_preorder_return;
948 goto note;
949 }
950 /*FALLTHROUGH*/
951
952 case FTS_preorder_resume:
953
954 /*
955 * prune
956 */
957
958 if (!fts->dir || f->nd || f->status == FTS_SKIP)
959 {
960 if (fts->dir)
961 {
962 closedir(fts->dir);
963 fts->dir = 0;
964 }
965 fts->state = FTS_popstack;
966 continue;
967 }
968
969 /*
970 * FTS_D or FTS_DNX, about to read children
971 */
972
973 if (fts->cd == 0)
974 {
975 if ((fts->cd = chdir(fts->name)) < 0)
976 pathcd(fts->home, NiL);
977 else if (fts->pwd != f)
978 {
979 f->pwd = fts->pwd;
980 fts->pwd = f;
981 }
982 fts->curdir = fts->cd < 0 ? 0 : f;
983 }
984 fts->nostat = fts->children > 1 || f->fts_info == FTS_DNX;
985 fts->cpname = fts->cd && !fts->nostat || !fts->children && !fts->comparf;
986 fts->dotdot = 0;
987 fts->endbase = fts->base + fts->baselen;
988 if (fts->endbase[-1] != '/')
989 *fts->endbase++ = '/';
990 fts->current = f;
991 /*FALLTHROUGH*/
992
993 case FTS_readdir:
994
995 while (d = readdir(fts->dir))
996 {
997 s = d->d_name;
998 if (s[0] == '.')
999 {
1000 if (s[1] == 0)
1001 {
1002 fts->current->nlink--;
1003 if (!(fts->flags & FTS_SEEDOT))
1004 continue;
1005 n = 1;
1006 }
1007 else if (s[1] == '.' && s[2] == 0)
1008 {
1009 fts->current->nlink--;
1010 if (fts->current->must == 1)
1011 fts->current->must = 0;
1012 if (!(fts->flags & FTS_SEEDOT))
1013 continue;
1014 n = 2;
1015 }
1016 else
1017 n = 0;
1018 }
1019 else
1020 n = 0;
1021
1022 /*
1023 * make a new entry
1024 */
1025
1026 i = D_NAMLEN(d);
1027 if (!(f = node(fts, fts->current, s, i)))
1028 return 0;
1029 TYPE(f, D_TYPE(d));
1030
1031 /*
1032 * check for space
1033 */
1034
1035 if (i >= fts->endbuf - fts->endbase)
1036 {
1037 if (resize(fts, i))
1038 return 0;
1039 fts->endbase = fts->base + fts->baselen;
1040 if (fts->endbase[-1] != '/')
1041 fts->endbase++;
1042 }
1043 if (fts->cpname)
1044 {
1045 memcpy(fts->endbase, s, i + 1);
1046 if (fts->cd)
1047 s = fts->path;
1048 }
1049 if (n)
1050 {
1051 /*
1052 * don't recurse on . and ..
1053 */
1054
1055 if (n == 1)
1056 f->fts_statp = fts->current->fts_statp;
1057 else
1058 {
1059 if (f->fts_info != FTS_NS)
1060 fts->dotdot = f;
1061 if (fts->current->fts_parent->fts_level < 0)
1062 {
1063 f->fts_statp = &fts->current->fts_parent->statb;
1064 info(fts, f, s, f->fts_statp, 0);
1065 }
1066 else
1067 f->fts_statp = fts->current->fts_parent->fts_statp;
1068 }
1069 f->fts_info = FTS_DOT;
1070 }
1071 else if ((fts->nostat || SKIP(fts, f)) && (f->fts_info = FTS_NSOK) || info(fts, f, s, &f->statb, fts->flags))
1072 f->statb.st_ino = D_FILENO(d);
1073 if (fts->comparf)
1074 fts->root = search(f, fts->root, fts->comparf, 1);
1075 else if (fts->children || f->fts_info == FTS_D || f->fts_info == FTS_SL)
1076 {
1077 if (fts->top)
1078 fts->bot = fts->bot->fts_link = f;
1079 else
1080 fts->top = fts->bot = f;
1081 }
1082 else
1083 {
1084 /*
1085 * terminal node
1086 */
1087
1088 f->fts_path = PATH(fts, fts->path, 1);
1089 f->fts_pathlen = fts->endbase - f->fts_path + f->fts_namelen;
1090 f->fts_accpath = ACCESS(fts, f);
1091 fts->previous = fts->current;
1092 fts->current = f;
1093 fts->state = FTS_terminal;
1094 goto note;
1095 }
1096 }
1097
1098 /*
1099 * done with the directory
1100 */
1101
1102 closedir(fts->dir);
1103 fts->dir = 0;
1104 if (fts->root)
1105 getlist(&fts->top, &fts->bot, fts->root);
1106 if (fts->children)
1107 {
1108 /*
1109 * try moving back to parent dir
1110 */
1111
1112 fts->base[fts->baselen] = 0;
1113 if (fts->cd <= 0)
1114 {
1115 f = fts->current->fts_parent;
1116 if (fts->cd < 0
1117 || f != fts->curdir
1118 || !fts->dotdot
1119 || !SAME(f->fts_statp, fts->dotdot->fts_statp)
1120 || fts->pwd && fts->pwd->symlink
1121 || (fts->cd = chdir("..")) < 0
1122 #ifdef verify
1123 || stat(".", &sb) < 0
1124 || !SAME(&sb, fts->dotdot->fts_statp)
1125 #endif
1126 )
1127 fts->cd = setpdir(fts->home, fts->path, fts->base);
1128 if (fts->pwd)
1129 fts->pwd = fts->pwd->pwd;
1130 fts->curdir = fts->cd ? 0 : f;
1131 }
1132 f = fts->current;
1133 fts->link = f->fts_link;
1134 f->fts_link = fts->top;
1135 f->fts_path = PATH(fts, fts->path, f->fts_level);
1136 f->fts_pathlen = (fts->base - f->fts_path) + f->fts_namelen;
1137 f->fts_accpath = ACCESS(fts, f);
1138 fts->state = FTS_children_return;
1139 goto note;
1140 }
1141 /*FALLTHROUGH*/
1142
1143 case FTS_children_resume:
1144
1145 fts->base[fts->baselen] = 0;
1146 if (fts->top)
1147 {
1148 fts->bot->fts_link = fts->todo;
1149 fts->todo = fts->top;
1150 fts->top = 0;
1151 }
1152 /*FALLTHROUGH*/
1153
1154 case FTS_popstack:
1155
1156 /*
1157 * pop objects completely processed
1158 */
1159
1160 fts->nd = 0;
1161 f = fts->current;
1162 /*FALLTHROUGH*/
1163
1164 case FTS_popstack_resume:
1165
1166 while (fts->todo && f == fts->todo)
1167 {
1168 t = f->fts_parent;
1169 if ((f->fts_info & FTS_DP) == FTS_D)
1170 {
1171 /*
1172 * delete from <dev,ino> tree
1173 */
1174
1175 if (f != fts->diroot)
1176 fts->diroot = search(f, fts->diroot, statcmp, 0);
1177 fts->diroot = deleteroot(fts->diroot);
1178 if (f == fts->curdir)
1179 {
1180 fts->nd++;
1181 fts->curdir = t;
1182 }
1183
1184 /*
1185 * perform post-order processing
1186 */
1187
1188 if (!(fts->flags & FTS_NOPOSTORDER) &&
1189 f->status != FTS_SKIP &&
1190 f->status != FTS_NOPOSTORDER)
1191 {
1192 /*
1193 * move to parent dir
1194 */
1195
1196 if (fts->nd > 0)
1197 fts->cd = popdirs(fts);
1198 if (fts->cd < 0)
1199 fts->cd = setpdir(fts->home, fts->path, fts->base);
1200 fts->curdir = fts->cd ? 0 : t;
1201 f->fts_info = FTS_DP;
1202 f->fts_path = PATH(fts, fts->path, f->fts_level);
1203 f->fts_pathlen = (fts->base - f->fts_path) + f->fts_namelen;
1204 f->fts_accpath = ACCESS(fts, f);
1205
1206 /*
1207 * re-stat to update nlink/times
1208 */
1209
1210 stat(f->fts_accpath, f->fts_statp);
1211 fts->link = f->fts_link;
1212 f->fts_link = 0;
1213 fts->state = FTS_popstack_return;
1214 goto note;
1215 }
1216 }
1217
1218 /*
1219 * reset base
1220 */
1221
1222 if (fts->base > fts->path + t->fts_namelen)
1223 fts->base--;
1224 *fts->base = 0;
1225 fts->base -= t->fts_namelen;
1226
1227 /*
1228 * try again or delete from top of stack
1229 */
1230
1231 if (f->status == FTS_AGAIN)
1232 {
1233 f->fts_info = FTS_D;
1234 f->status = 0;
1235 }
1236 else
1237 {
1238 fts->todo = fts->todo->fts_link;
1239 drop(fts, f);
1240 }
1241 f = t;
1242 }
1243
1244 /*
1245 * reset current directory
1246 */
1247
1248 if (fts->nd > 0 && popdirs(fts) < 0)
1249 {
1250 pathcd(fts->home, NiL);
1251 fts->curdir = 0;
1252 fts->cd = -1;
1253 }
1254 if (fts->todo)
1255 {
1256 if (*fts->base)
1257 fts->base += f->fts_namelen;
1258 if (*(fts->base - 1) != '/')
1259 *fts->base++ = '/';
1260 *fts->base = 0;
1261 f = fts->todo;
1262 fts->state = FTS_todo;
1263 continue;
1264 }
1265 return 0;
1266
1267 case FTS_children_return:
1268
1269 f = fts->current;
1270 f->fts_link = fts->link;
1271
1272 /*
1273 * chdir down again
1274 */
1275
1276 i = f->fts_info != FTS_DNX;
1277 n = f->status == FTS_SKIP;
1278 if (!n && fts->cd == 0)
1279 {
1280 if ((fts->cd = chdir(fts->base)) < 0)
1281 pathcd(fts->home, NiL);
1282 else if (fts->pwd != f)
1283 {
1284 f->pwd = fts->pwd;
1285 fts->pwd = f;
1286 }
1287 fts->curdir = fts->cd ? 0 : f;
1288 }
1289
1290 /*
1291 * prune
1292 */
1293
1294 if (fts->base[fts->baselen - 1] != '/')
1295 fts->base[fts->baselen] = '/';
1296 for (fts->bot = 0, f = fts->top; f; )
1297 if (n || f->status == FTS_SKIP)
1298 {
1299 if (fts->bot)
1300 fts->bot->fts_link = f->fts_link;
1301 else
1302 fts->top = f->fts_link;
1303 drop(fts, f);
1304 f = fts->bot ? fts->bot->fts_link : fts->top;
1305 }
1306 else
1307 {
1308 if (fts->children > 1 && i)
1309 {
1310 if (f->status == FTS_STAT)
1311 info(fts, f, NiL, f->fts_statp, 0);
1312 else if (f->fts_info == FTS_NSOK && !SKIP(fts, f))
1313 {
1314 s = f->fts_name;
1315 if (fts->cd)
1316 {
1317 memcpy(fts->endbase, s, f->fts_namelen + 1);
1318 s = fts->path;
1319 }
1320 info(fts, f, s, f->fts_statp, fts->flags);
1321 }
1322 }
1323 fts->bot = f;
1324 f = f->fts_link;
1325 }
1326 fts->children = 0;
1327 fts->state = FTS_children_resume;
1328 continue;
1329
1330 case FTS_popstack_return:
1331
1332 f = fts->todo;
1333 f->fts_link = fts->link;
1334 f->fts_info = f->status == FTS_AGAIN ? FTS_DP : 0;
1335 fts->state = FTS_popstack_resume;
1336 continue;
1337
1338 case FTS_preorder_return:
1339
1340 f = fts->current;
1341 f->fts_link = fts->link;
1342
1343 /*
1344 * follow symlink if asked to
1345 */
1346
1347 if (f->status == FTS_FOLLOW)
1348 {
1349 f->status = 0;
1350 if (f->fts_info == FTS_SL || ISTYPE(f, DT_LNK) || f->fts_info == FTS_NSOK)
1351 {
1352 info(fts, f, f->fts_accpath, f->fts_statp, 0);
1353 if (f->fts_info != FTS_SL)
1354 {
1355 fts->state = FTS_preorder;
1356 continue;
1357 }
1358 }
1359 }
1360
1361 /*
1362 * about to prune this f and already at home
1363 */
1364
1365 if (fts->cd == 0 && f->fts_level == 0 && f->nd)
1366 fts->cd = -1;
1367 fts->state = FTS_preorder_resume;
1368 continue;
1369
1370 case FTS_terminal:
1371
1372 f = fts->current;
1373 if (f->status == FTS_FOLLOW)
1374 {
1375 f->status = 0;
1376 if (f->fts_info == FTS_SL || ISTYPE(f, DT_LNK) || f->fts_info == FTS_NSOK)
1377 {
1378 info(fts, f, f->fts_accpath, f->fts_statp, 0);
1379 if (f->symlink && f->fts_info != FTS_SL)
1380 {
1381 if (!(f->fts_link = fts->top))
1382 fts->bot = f;
1383 fts->top = f;
1384 fts->current = fts->previous;
1385 fts->state = FTS_readdir;
1386 continue;
1387 }
1388 }
1389 }
1390 f = f->fts_parent;
1391 drop(fts, fts->current);
1392 fts->current = f;
1393 fts->state = FTS_readdir;
1394 continue;
1395
1396 case FTS_error:
1397
1398 return 0;
1399
1400 default:
1401
1402 fts->fts_errno = EINVAL;
1403 fts->state = FTS_error;
1404 return 0;
1405
1406 }
1407 note:
1408 #if __OBSOLETE__ < 20140101
1409 f->_fts_pathlen = (unsigned short)f->fts_pathlen;
1410 #endif
1411 for (p = notify; p; p = p->next)
1412 if ((n = (*p->notifyf)(fts, f, p->context)) > 0)
1413 break;
1414 else if (n < 0)
1415 {
1416 fts->fts_errno = EINVAL;
1417 fts->state = FTS_error;
1418 return 0;
1419 }
1420 return f;
1421 }
1422
1423 /*
1424 * set stream or entry flags
1425 */
1426
1427 int
fts_set(register FTS * fts,register FTSENT * f,int status)1428 fts_set(register FTS* fts, register FTSENT* f, int status)
1429 {
1430 if (fts || !f || f->fts->current != f)
1431 return -1;
1432 switch (status)
1433 {
1434 case FTS_AGAIN:
1435 break;
1436 case FTS_FOLLOW:
1437 if (!(f->fts_info & FTS_SL))
1438 return -1;
1439 break;
1440 case FTS_NOPOSTORDER:
1441 break;
1442 case FTS_SKIP:
1443 if ((f->fts_info & (FTS_D|FTS_P)) != FTS_D)
1444 return -1;
1445 break;
1446 default:
1447 return -1;
1448 }
1449 f->status = status;
1450 return 0;
1451 }
1452
1453 /*
1454 * return the list of child entries
1455 */
1456
1457 FTSENT*
fts_children(register FTS * fts,int flags)1458 fts_children(register FTS* fts, int flags)
1459 {
1460 register FTSENT* f;
1461
1462 switch (fts->state)
1463 {
1464
1465 case 0:
1466
1467 if (fts->comparf)
1468 order(fts);
1469 fts->state = FTS_top_return;
1470 return fts->todo;
1471
1472 case FTS_preorder_return:
1473
1474 fts->children = ((flags | fts->flags) & FTS_NOSTAT) ? 2 : 1;
1475 if (f = fts_read(fts))
1476 f = f->fts_link;
1477 return f;
1478
1479 }
1480 return 0;
1481 }
1482
1483 /*
1484 * return default (FTS_LOGICAL|FTS_META|FTS_PHYSICAL|FTS_SEEDOTDIR) flags
1485 * conditioned by astconf()
1486 */
1487
1488 int
fts_flags(void)1489 fts_flags(void)
1490 {
1491 register char* s;
1492
1493 s = astconf("PATH_RESOLVE", NiL, NiL);
1494 if (streq(s, "logical"))
1495 return FTS_LOGICAL;
1496 if (streq(s, "physical"))
1497 return FTS_PHYSICAL|FTS_SEEDOTDIR;
1498 return FTS_META|FTS_PHYSICAL|FTS_SEEDOTDIR;
1499 }
1500
1501 /*
1502 * return 1 if ent is mounted on a local filesystem
1503 */
1504
1505 int
fts_local(FTSENT * ent)1506 fts_local(FTSENT* ent)
1507 {
1508 #ifdef ST_LOCAL
1509 struct statvfs fs;
1510
1511 return statvfs(ent->fts_path, &fs) || (fs.f_flag & ST_LOCAL);
1512 #else
1513 return !strgrpmatch(fmtfs(ent->fts_statp), "([an]fs|samb)", NiL, 0, STR_LEFT|STR_ICASE);
1514 #endif
1515 }
1516
1517 /*
1518 * close an open fts stream
1519 */
1520
1521 int
fts_close(register FTS * fts)1522 fts_close(register FTS* fts)
1523 {
1524 register FTSENT* f;
1525 register FTSENT* x;
1526
1527 if (fts->dir)
1528 closedir(fts->dir);
1529 if (fts->cd == 0)
1530 pathcd(fts->home, NiL);
1531 free(fts->home);
1532 if (fts->state == FTS_children_return)
1533 fts->current->fts_link = fts->link;
1534 if (fts->top)
1535 {
1536 fts->bot->fts_link = fts->todo;
1537 fts->todo = fts->top;
1538 }
1539 for (f = fts->todo; f; f = x)
1540 {
1541 x = f->fts_link;
1542 free(f);
1543 }
1544 for (f = fts->free; f; f = x)
1545 {
1546 x = f->fts_link;
1547 free(f);
1548 }
1549 free(fts);
1550 return 0;
1551 }
1552
1553 /*
1554 * register function to be called for each fts_read() entry
1555 * context==0 => unregister notifyf
1556 */
1557
1558 int
fts_notify(Notify_f notifyf,void * context)1559 fts_notify(Notify_f notifyf, void* context)
1560 {
1561 register Notify_t* np;
1562 register Notify_t* pp;
1563
1564 if (context)
1565 {
1566 if (!(np = newof(0, Notify_t, 1, 0)))
1567 return -1;
1568 np->notifyf = notifyf;
1569 np->context = context;
1570 np->next = notify;
1571 notify = np;
1572 }
1573 else
1574 {
1575 for (np = notify, pp = 0; np; pp = np, np = np->next)
1576 if (np->notifyf == notifyf)
1577 {
1578 if (pp)
1579 pp->next = np->next;
1580 else
1581 notify = np->next;
1582 free(np);
1583 return 0;
1584 }
1585 return -1;
1586 }
1587 return 0;
1588 }
1589