1 /***********************************************************************
2 * *
3 * This software is part of the ast package *
4 * Copyright (c) 1985-2011 AT&T Intellectual Property *
5 * and is licensed under the *
6 * Eclipse Public License, Version 1.0 *
7 * by AT&T Intellectual Property *
8 * *
9 * A copy of the License is available at *
10 * http://www.eclipse.org/org/documents/epl-v10.html *
11 * (with md5 checksum b35adb5213ca9657e911e9befb180842) *
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)
554 {
555 TYPE(f, DT_LNK);
556 f->fts_info = FTS_SL;
557 }
558 else if (stat(path, &sb) >= 0)
559 {
560 *sp = sb;
561 flags = FTS_PHYSICAL;
562 goto again;
563 }
564 else
565 {
566 TYPE(f, DT_LNK);
567 f->fts_info = FTS_SLNONE;
568 }
569 }
570 #endif
571 else
572 {
573 TYPE(f, DT_REG);
574 f->fts_info = FTS_F;
575 }
576 return 0;
577 bad:
578 TYPE(f, DT_UNKNOWN);
579 f->fts_info = FTS_NS;
580 return -1;
581 }
582
583 /*
584 * get top list of elements to process
585 * ordering delayed until first fts_read()
586 * to give caller a chance to set fts->handle
587 */
588
589 static FTSENT*
toplist(FTS * fts,register char * const * pathnames)590 toplist(FTS* fts, register char* const* pathnames)
591 {
592 register char* path;
593 register FTSENT* f;
594 register FTSENT* top;
595 register FTSENT* bot;
596 int physical;
597 int metaphysical;
598 char* s;
599 struct stat st;
600
601 if (fts->flags & FTS_NOSEEDOTDIR)
602 fts->flags &= ~FTS_SEEDOTDIR;
603 physical = (fts->flags & FTS_PHYSICAL);
604 metaphysical = (fts->flags & (FTS_META|FTS_PHYSICAL)) == (FTS_META|FTS_PHYSICAL);
605 top = bot = 0;
606 while (path = *pathnames++)
607 {
608 /*
609 * make elements
610 */
611
612 if (!(f = node(fts, fts->parent, path, strlen(path))))
613 break;
614 path = f->fts_name;
615 if (!physical)
616 f->fts_namelen = (fts->flags & FTS_SEEDOTDIR) ? strlen(path) : (pathcanon(path, strlen(path) + 1, 0) - path);
617 else if (*path != '.')
618 {
619 f->fts_namelen = strlen(path);
620 fts->flags |= FTS_SEEDOTDIR;
621 }
622 else
623 {
624 if (fts->flags & FTS_NOSEEDOTDIR)
625 {
626 fts->flags &= ~FTS_SEEDOTDIR;
627 s = path;
628 while (*s++ == '.' && *s++ == '/')
629 {
630 while (*s == '/')
631 s++;
632 if (!*s)
633 break;
634 path = f->fts_name;
635 while (*path++ = *s++);
636 path = f->fts_name;
637 }
638 }
639 else
640 fts->flags |= FTS_SEEDOTDIR;
641 for (s = path + strlen(path); s > path && *(s - 1) == '/'; s--);
642 *s = 0;
643 f->fts_namelen = s - path;
644 }
645 #if __OBSOLETE__ < 20140101
646 f->_fts_namelen = (unsigned short)f->fts_namelen;
647 #endif
648 if (!*path)
649 {
650 errno = ENOENT;
651 f->fts_info = FTS_NS;
652 }
653 else
654 info(fts, f, path, f->fts_statp, fts->flags);
655 #ifdef S_ISLNK
656
657 /*
658 * don't let any standards committee get
659 * away with calling your idea a hack
660 */
661
662 if (metaphysical && f->fts_info == FTS_SL)
663 {
664 if (stat(path, &st) >= 0)
665 {
666 *f->fts_statp = st;
667 info(fts, f, NiL, f->fts_statp, 0);
668 }
669 else
670 f->fts_info = FTS_SLNONE;
671 }
672 #endif
673 if (bot)
674 {
675 bot->fts_link = f;
676 bot = f;
677 }
678 else
679 top = bot = f;
680 }
681 return top;
682 }
683
684 /*
685 * order fts->todo if fts->comparf != 0
686 */
687
688 static void
order(FTS * fts)689 order(FTS* fts)
690 {
691 register FTSENT* f;
692 register FTSENT* root;
693 FTSENT* top;
694 FTSENT* bot;
695
696 top = bot = root = 0;
697 for (f = fts->todo; f; f = f->fts_link)
698 root = search(f, root, fts->comparf, 1);
699 getlist(&top, &bot, root);
700 fts->todo = top;
701 }
702
703 /*
704 * resize the path buffer
705 * note that free() is not used because we may need to chdir(fts->home)
706 * if there isn't enough space to continue
707 */
708
709 static int
resize(register FTS * fts,size_t inc)710 resize(register FTS* fts, size_t inc)
711 {
712 register char* old;
713 register char* newp;
714 register size_t n_old;
715
716 /*
717 * add space for "/." used in testing FTS_DNX
718 */
719
720 n_old = fts->homesize;
721 fts->homesize = ((fts->homesize + inc + 4) / PATH_MAX + 1) * PATH_MAX;
722 if (!(newp = newof(0, char, fts->homesize, 0)))
723 {
724 fts->fts_errno = errno;
725 fts->state = FTS_error;
726 return -1;
727 }
728 old = fts->home;
729 fts->home = newp;
730 memcpy(newp, old, n_old);
731 if (fts->endbuf)
732 fts->endbuf = newp + fts->homesize - 4;
733 if (fts->path)
734 fts->path = newp + (fts->path - old);
735 if (fts->base)
736 fts->base = newp + (fts->base - old);
737 free(old);
738 return 0;
739 }
740
741 /*
742 * open a new fts stream on pathnames
743 */
744
745 FTS*
fts_open(char * const * pathnames,int flags,int (* comparf)(FTSENT * const *,FTSENT * const *))746 fts_open(char* const* pathnames, int flags, int (*comparf)(FTSENT* const*, FTSENT* const*))
747 {
748 register FTS* fts;
749
750 if (!(fts = newof(0, FTS, 1, sizeof(FTSENT))))
751 return 0;
752 fts->flags = flags;
753 fts->cd = (flags & FTS_NOCHDIR) ? 1 : -1;
754 fts->comparf = comparf;
755 fts->fs3d = fs3d(FS3D_TEST);
756
757 /*
758 * set up the path work buffer
759 */
760
761 fts->homesize = 2 * PATH_MAX;
762 for (;;)
763 {
764 if (!(fts->home = newof(fts->home, char, fts->homesize, 0)))
765 {
766 free(fts);
767 return 0;
768 }
769 if (fts->cd > 0 || getcwd(fts->home, fts->homesize))
770 break;
771 if (errno == ERANGE)
772 fts->homesize += PATH_MAX;
773 else
774 fts->cd = 1;
775 }
776 fts->endbuf = fts->home + fts->homesize - 4;
777
778 /*
779 * initialize the tippity-top
780 */
781
782 fts->parent = (FTSENT*)(fts + 1);
783 fts->parent->fts_info = FTS_D;
784 memcpy(fts->parent->fts_accpath = fts->parent->fts_path = fts->parent->fts_name = fts->parent->name, ".", 2);
785 fts->parent->fts_level = -1;
786 #if __OBSOLETE__ < 20140101
787 fts->parent->_fts_level = (short)fts->parent->fts_level;
788 #endif
789 fts->parent->fts_statp = &fts->parent->statb;
790 fts->parent->must = 2;
791 fts->parent->type = DT_UNKNOWN;
792 fts->path = fts->home + strlen(fts->home) + 1;
793
794 /*
795 * make the list of top elements
796 */
797
798 if (!pathnames || (flags & FTS_ONEPATH) || !*pathnames)
799 {
800 char* v[2];
801
802 v[0] = pathnames && (flags & FTS_ONEPATH) ? (char*)pathnames : ".";
803 v[1] = 0;
804 fts->todo = toplist(fts, v);
805 }
806 else
807 fts->todo = toplist(fts, pathnames);
808 #if _HUH_1997_01_07
809 if (!fts->todo || fts->todo->fts_info == FTS_NS && !fts->todo->fts_link)
810 #else
811 if (!fts->todo)
812 #endif
813 {
814 fts_close(fts);
815 return 0;
816 }
817 return fts;
818 }
819
820 /*
821 * return the next FTS entry
822 */
823
824 FTSENT*
fts_read(register FTS * fts)825 fts_read(register FTS* fts)
826 {
827 register char* s;
828 register int n;
829 register FTSENT* f;
830 struct dirent* d;
831 size_t i;
832 FTSENT* t;
833 Notify_t* p;
834 #ifdef verify
835 struct stat sb;
836 #endif
837
838 for (;;)
839 switch (fts->state)
840 {
841
842 case FTS_top_return:
843
844 f = fts->todo;
845 t = 0;
846 while (f)
847 if (f->status == FTS_SKIP)
848 {
849 if (t)
850 {
851 t->fts_link = f->fts_link;
852 drop(fts, f);
853 f = t->fts_link;
854 }
855 else
856 {
857 fts->todo = f->fts_link;
858 drop(fts, f);
859 f = fts->todo;
860 }
861 }
862 else
863 {
864 t = f;
865 f = f->fts_link;
866 }
867 /*FALLTHROUGH*/
868
869 case 0:
870
871 if (!fts->state && fts->comparf)
872 order(fts);
873 if (!(f = fts->todo))
874 return 0;
875 /*FALLTHROUGH*/
876
877 case FTS_todo:
878
879 /*
880 * process the top object on the stack
881 */
882
883 fts->root = fts->top = fts->bot = 0;
884
885 /*
886 * initialize the top level
887 */
888
889 if (f->fts_level == 0)
890 {
891 fts->parent->fts_number = f->fts_number;
892 fts->parent->fts_pointer = f->fts_pointer;
893 fts->parent->fts_statp = f->fts_statp;
894 fts->parent->statb = *f->fts_statp;
895 f->fts_parent = fts->parent;
896 fts->diroot = 0;
897 if (fts->cd == 0)
898 pathcd(fts->home, NiL);
899 else if (fts->cd < 0)
900 fts->cd = 0;
901 fts->pwd = f->fts_parent;
902 fts->curdir = fts->cd ? 0 : f->fts_parent;
903 *(fts->base = fts->path) = 0;
904 }
905
906 /*
907 * chdir to parent if asked for
908 */
909
910 if (fts->cd < 0)
911 {
912 fts->cd = setdir(fts->home, fts->path);
913 fts->pwd = f->fts_parent;
914 fts->curdir = fts->cd ? 0 : f->fts_parent;
915 }
916
917 /*
918 * add object's name to the path
919 */
920
921 if ((fts->baselen = f->fts_namelen) >= (fts->endbuf - fts->base) && resize(fts, fts->baselen))
922 return 0;
923 memcpy(fts->base, f->name, fts->baselen + 1);
924 fts->name = fts->cd ? fts->path : fts->base;
925 /*FALLTHROUGH*/
926
927 case FTS_preorder:
928
929 /*
930 * check for cycle and open dir
931 */
932
933 if (f->fts_info == FTS_D)
934 {
935 if ((fts->diroot = search(f, fts->diroot, statcmp, 0)) != f || f->fts_level > 0 && (t = f) && statcmp(&t, &f->fts_parent) == 0)
936 {
937 f->fts_info = FTS_DC;
938 f->fts_cycle = fts->diroot;
939 }
940 else if (!(fts->flags & FTS_TOP) && (!(fts->flags & FTS_XDEV) || f->statb.st_dev == f->fts_parent->statb.st_dev))
941 {
942 /*
943 * buffer is known to be large enough here!
944 */
945
946 if (fts->base[fts->baselen - 1] != '/')
947 memcpy(fts->base + fts->baselen, "/.", 3);
948 if (!(fts->dir = opendir(fts->name)))
949 f->fts_info = FTS_DNX;
950 fts->base[fts->baselen] = 0;
951 if (!fts->dir && !(fts->dir = opendir(fts->name)))
952 f->fts_info = FTS_DNR;
953 }
954 }
955 f->nd = f->fts_info & ~FTS_DNX;
956 if (f->nd || !(fts->flags & FTS_NOPREORDER))
957 {
958 fts->current = f;
959 fts->link = f->fts_link;
960 f->fts_link = 0;
961 f->fts_path = PATH(fts, fts->path, f->fts_level);
962 f->fts_pathlen = (fts->base - f->fts_path) + fts->baselen;
963 f->fts_accpath = ACCESS(fts, f);
964 fts->state = FTS_preorder_return;
965 goto note;
966 }
967 /*FALLTHROUGH*/
968
969 case FTS_preorder_resume:
970
971 /*
972 * prune
973 */
974
975 if (!fts->dir || f->nd || f->status == FTS_SKIP)
976 {
977 if (fts->dir)
978 {
979 closedir(fts->dir);
980 fts->dir = 0;
981 }
982 fts->state = FTS_popstack;
983 continue;
984 }
985
986 /*
987 * FTS_D or FTS_DNX, about to read children
988 */
989
990 if (fts->cd == 0)
991 {
992 if ((fts->cd = chdir(fts->name)) < 0)
993 pathcd(fts->home, NiL);
994 else if (fts->pwd != f)
995 {
996 f->pwd = fts->pwd;
997 fts->pwd = f;
998 }
999 fts->curdir = fts->cd < 0 ? 0 : f;
1000 }
1001 fts->nostat = fts->children > 1 || f->fts_info == FTS_DNX;
1002 fts->cpname = fts->cd && !fts->nostat || !fts->children && !fts->comparf;
1003 fts->dotdot = 0;
1004 fts->endbase = fts->base + fts->baselen;
1005 if (fts->endbase[-1] != '/')
1006 *fts->endbase++ = '/';
1007 fts->current = f;
1008 /*FALLTHROUGH*/
1009
1010 case FTS_readdir:
1011
1012 while (d = readdir(fts->dir))
1013 {
1014 s = d->d_name;
1015 if (s[0] == '.')
1016 {
1017 if (s[1] == 0)
1018 {
1019 fts->current->nlink--;
1020 if (!(fts->flags & FTS_SEEDOT))
1021 continue;
1022 n = 1;
1023 }
1024 else if (s[1] == '.' && s[2] == 0)
1025 {
1026 fts->current->nlink--;
1027 if (fts->current->must == 1)
1028 fts->current->must = 0;
1029 if (!(fts->flags & FTS_SEEDOT))
1030 continue;
1031 n = 2;
1032 }
1033 else
1034 n = 0;
1035 }
1036 else
1037 n = 0;
1038
1039 /*
1040 * make a new entry
1041 */
1042
1043 i = D_NAMLEN(d);
1044 if (!(f = node(fts, fts->current, s, i)))
1045 return 0;
1046 TYPE(f, D_TYPE(d));
1047
1048 /*
1049 * check for space
1050 */
1051
1052 if (i >= fts->endbuf - fts->endbase)
1053 {
1054 if (resize(fts, i))
1055 return 0;
1056 fts->endbase = fts->base + fts->baselen;
1057 if (fts->endbase[-1] != '/')
1058 fts->endbase++;
1059 }
1060 if (fts->cpname)
1061 {
1062 memcpy(fts->endbase, s, i + 1);
1063 if (fts->cd)
1064 s = fts->path;
1065 }
1066 if (n)
1067 {
1068 /*
1069 * don't recurse on . and ..
1070 */
1071
1072 if (n == 1)
1073 f->fts_statp = fts->current->fts_statp;
1074 else
1075 {
1076 if (f->fts_info != FTS_NS)
1077 fts->dotdot = f;
1078 if (fts->current->fts_parent->fts_level < 0)
1079 {
1080 f->fts_statp = &fts->current->fts_parent->statb;
1081 info(fts, f, s, f->fts_statp, 0);
1082 }
1083 else
1084 f->fts_statp = fts->current->fts_parent->fts_statp;
1085 }
1086 f->fts_info = FTS_DOT;
1087 }
1088 else if ((fts->nostat || SKIP(fts, f)) && (f->fts_info = FTS_NSOK) || info(fts, f, s, &f->statb, fts->flags))
1089 f->statb.st_ino = D_FILENO(d);
1090 if (fts->comparf)
1091 fts->root = search(f, fts->root, fts->comparf, 1);
1092 else if (fts->children || f->fts_info == FTS_D || f->fts_info == FTS_SL)
1093 {
1094 if (fts->top)
1095 fts->bot = fts->bot->fts_link = f;
1096 else
1097 fts->top = fts->bot = f;
1098 }
1099 else
1100 {
1101 /*
1102 * terminal node
1103 */
1104
1105 f->fts_path = PATH(fts, fts->path, 1);
1106 f->fts_pathlen = fts->endbase - f->fts_path + f->fts_namelen;
1107 f->fts_accpath = ACCESS(fts, f);
1108 fts->previous = fts->current;
1109 fts->current = f;
1110 fts->state = FTS_terminal;
1111 goto note;
1112 }
1113 }
1114
1115 /*
1116 * done with the directory
1117 */
1118
1119 closedir(fts->dir);
1120 fts->dir = 0;
1121 if (fts->root)
1122 getlist(&fts->top, &fts->bot, fts->root);
1123 if (fts->children)
1124 {
1125 /*
1126 * try moving back to parent dir
1127 */
1128
1129 fts->base[fts->baselen] = 0;
1130 if (fts->cd <= 0)
1131 {
1132 f = fts->current->fts_parent;
1133 if (fts->cd < 0
1134 || f != fts->curdir
1135 || !fts->dotdot
1136 || !SAME(f->fts_statp, fts->dotdot->fts_statp)
1137 || fts->pwd && fts->pwd->symlink
1138 || (fts->cd = chdir("..")) < 0
1139 #ifdef verify
1140 || stat(".", &sb) < 0
1141 || !SAME(&sb, fts->dotdot->fts_statp)
1142 #endif
1143 )
1144 fts->cd = setpdir(fts->home, fts->path, fts->base);
1145 if (fts->pwd)
1146 fts->pwd = fts->pwd->pwd;
1147 fts->curdir = fts->cd ? 0 : f;
1148 }
1149 f = fts->current;
1150 fts->link = f->fts_link;
1151 f->fts_link = fts->top;
1152 f->fts_path = PATH(fts, fts->path, f->fts_level);
1153 f->fts_pathlen = (fts->base - f->fts_path) + f->fts_namelen;
1154 f->fts_accpath = ACCESS(fts, f);
1155 fts->state = FTS_children_return;
1156 goto note;
1157 }
1158 /*FALLTHROUGH*/
1159
1160 case FTS_children_resume:
1161
1162 fts->base[fts->baselen] = 0;
1163 if (fts->top)
1164 {
1165 fts->bot->fts_link = fts->todo;
1166 fts->todo = fts->top;
1167 fts->top = 0;
1168 }
1169 /*FALLTHROUGH*/
1170
1171 case FTS_popstack:
1172
1173 /*
1174 * pop objects completely processed
1175 */
1176
1177 fts->nd = 0;
1178 f = fts->current;
1179 /*FALLTHROUGH*/
1180
1181 case FTS_popstack_resume:
1182
1183 while (fts->todo && f == fts->todo)
1184 {
1185 t = f->fts_parent;
1186 if ((f->fts_info & FTS_DP) == FTS_D)
1187 {
1188 /*
1189 * delete from <dev,ino> tree
1190 */
1191
1192 if (f != fts->diroot)
1193 fts->diroot = search(f, fts->diroot, statcmp, 0);
1194 fts->diroot = deleteroot(fts->diroot);
1195 if (f == fts->curdir)
1196 {
1197 fts->nd++;
1198 fts->curdir = t;
1199 }
1200
1201 /*
1202 * perform post-order processing
1203 */
1204
1205 if (!(fts->flags & FTS_NOPOSTORDER) &&
1206 f->status != FTS_SKIP &&
1207 f->status != FTS_NOPOSTORDER)
1208 {
1209 /*
1210 * move to parent dir
1211 */
1212
1213 if (fts->nd > 0)
1214 fts->cd = popdirs(fts);
1215 if (fts->cd < 0)
1216 fts->cd = setpdir(fts->home, fts->path, fts->base);
1217 fts->curdir = fts->cd ? 0 : t;
1218 f->fts_info = FTS_DP;
1219 f->fts_path = PATH(fts, fts->path, f->fts_level);
1220 f->fts_pathlen = (fts->base - f->fts_path) + f->fts_namelen;
1221 f->fts_accpath = ACCESS(fts, f);
1222
1223 /*
1224 * re-stat to update nlink/times
1225 */
1226
1227 stat(f->fts_accpath, f->fts_statp);
1228 fts->link = f->fts_link;
1229 f->fts_link = 0;
1230 fts->state = FTS_popstack_return;
1231 goto note;
1232 }
1233 }
1234
1235 /*
1236 * reset base
1237 */
1238
1239 if (fts->base > fts->path + t->fts_namelen)
1240 fts->base--;
1241 *fts->base = 0;
1242 fts->base -= t->fts_namelen;
1243
1244 /*
1245 * try again or delete from top of stack
1246 */
1247
1248 if (f->status == FTS_AGAIN)
1249 {
1250 f->fts_info = FTS_D;
1251 f->status = 0;
1252 }
1253 else
1254 {
1255 fts->todo = fts->todo->fts_link;
1256 drop(fts, f);
1257 }
1258 f = t;
1259 }
1260
1261 /*
1262 * reset current directory
1263 */
1264
1265 if (fts->nd > 0 && popdirs(fts) < 0)
1266 {
1267 pathcd(fts->home, NiL);
1268 fts->curdir = 0;
1269 fts->cd = -1;
1270 }
1271 if (fts->todo)
1272 {
1273 if (*fts->base)
1274 fts->base += f->fts_namelen;
1275 if (*(fts->base - 1) != '/')
1276 *fts->base++ = '/';
1277 *fts->base = 0;
1278 f = fts->todo;
1279 fts->state = FTS_todo;
1280 continue;
1281 }
1282 return 0;
1283
1284 case FTS_children_return:
1285
1286 f = fts->current;
1287 f->fts_link = fts->link;
1288
1289 /*
1290 * chdir down again
1291 */
1292
1293 i = f->fts_info != FTS_DNX;
1294 n = f->status == FTS_SKIP;
1295 if (!n && fts->cd == 0)
1296 {
1297 if ((fts->cd = chdir(fts->base)) < 0)
1298 pathcd(fts->home, NiL);
1299 else if (fts->pwd != f)
1300 {
1301 f->pwd = fts->pwd;
1302 fts->pwd = f;
1303 }
1304 fts->curdir = fts->cd ? 0 : f;
1305 }
1306
1307 /*
1308 * prune
1309 */
1310
1311 if (fts->base[fts->baselen - 1] != '/')
1312 fts->base[fts->baselen] = '/';
1313 for (fts->bot = 0, f = fts->top; f; )
1314 if (n || f->status == FTS_SKIP)
1315 {
1316 if (fts->bot)
1317 fts->bot->fts_link = f->fts_link;
1318 else
1319 fts->top = f->fts_link;
1320 drop(fts, f);
1321 f = fts->bot ? fts->bot->fts_link : fts->top;
1322 }
1323 else
1324 {
1325 if (fts->children > 1 && i)
1326 {
1327 if (f->status == FTS_STAT)
1328 info(fts, f, NiL, f->fts_statp, 0);
1329 else if (f->fts_info == FTS_NSOK && !SKIP(fts, f))
1330 {
1331 s = f->fts_name;
1332 if (fts->cd)
1333 {
1334 memcpy(fts->endbase, s, f->fts_namelen + 1);
1335 s = fts->path;
1336 }
1337 info(fts, f, s, f->fts_statp, fts->flags);
1338 }
1339 }
1340 fts->bot = f;
1341 f = f->fts_link;
1342 }
1343 fts->children = 0;
1344 fts->state = FTS_children_resume;
1345 continue;
1346
1347 case FTS_popstack_return:
1348
1349 f = fts->todo;
1350 f->fts_link = fts->link;
1351 f->fts_info = f->status == FTS_AGAIN ? FTS_DP : 0;
1352 fts->state = FTS_popstack_resume;
1353 continue;
1354
1355 case FTS_preorder_return:
1356
1357 f = fts->current;
1358 f->fts_link = fts->link;
1359
1360 /*
1361 * follow symlink if asked to
1362 */
1363
1364 if (f->status == FTS_FOLLOW)
1365 {
1366 f->status = 0;
1367 if (f->fts_info == FTS_SL || ISTYPE(f, DT_LNK) || f->fts_info == FTS_NSOK)
1368 {
1369 info(fts, f, f->fts_accpath, f->fts_statp, 0);
1370 if (f->fts_info != FTS_SL)
1371 {
1372 fts->state = FTS_preorder;
1373 continue;
1374 }
1375 }
1376 }
1377
1378 /*
1379 * about to prune this f and already at home
1380 */
1381
1382 if (fts->cd == 0 && f->fts_level == 0 && f->nd)
1383 fts->cd = -1;
1384 fts->state = FTS_preorder_resume;
1385 continue;
1386
1387 case FTS_terminal:
1388
1389 f = fts->current;
1390 if (f->status == FTS_FOLLOW)
1391 {
1392 f->status = 0;
1393 if (f->fts_info == FTS_SL || ISTYPE(f, DT_LNK) || f->fts_info == FTS_NSOK)
1394 {
1395 info(fts, f, f->fts_accpath, f->fts_statp, 0);
1396 if (f->symlink && f->fts_info != FTS_SL)
1397 {
1398 if (!(f->fts_link = fts->top))
1399 fts->bot = f;
1400 fts->top = f;
1401 fts->current = fts->previous;
1402 fts->state = FTS_readdir;
1403 continue;
1404 }
1405 }
1406 }
1407 f = f->fts_parent;
1408 drop(fts, fts->current);
1409 fts->current = f;
1410 fts->state = FTS_readdir;
1411 continue;
1412
1413 case FTS_error:
1414
1415 return 0;
1416
1417 default:
1418
1419 fts->fts_errno = EINVAL;
1420 fts->state = FTS_error;
1421 return 0;
1422
1423 }
1424 note:
1425 #if __OBSOLETE__ < 20140101
1426 f->_fts_pathlen = (unsigned short)f->fts_pathlen;
1427 #endif
1428 for (p = notify; p; p = p->next)
1429 if ((n = (*p->notifyf)(fts, f, p->context)) > 0)
1430 break;
1431 else if (n < 0)
1432 {
1433 fts->fts_errno = EINVAL;
1434 fts->state = FTS_error;
1435 return 0;
1436 }
1437 return f;
1438 }
1439
1440 /*
1441 * set stream or entry flags
1442 */
1443
1444 int
fts_set(register FTS * fts,register FTSENT * f,int status)1445 fts_set(register FTS* fts, register FTSENT* f, int status)
1446 {
1447 if (fts || !f || f->fts->current != f)
1448 return -1;
1449 switch (status)
1450 {
1451 case FTS_AGAIN:
1452 break;
1453 case FTS_FOLLOW:
1454 if (!(f->fts_info & FTS_SL))
1455 return -1;
1456 break;
1457 case FTS_NOPOSTORDER:
1458 break;
1459 case FTS_SKIP:
1460 if ((f->fts_info & (FTS_D|FTS_P)) != FTS_D)
1461 return -1;
1462 break;
1463 default:
1464 return -1;
1465 }
1466 f->status = status;
1467 return 0;
1468 }
1469
1470 /*
1471 * return the list of child entries
1472 */
1473
1474 FTSENT*
fts_children(register FTS * fts,int flags)1475 fts_children(register FTS* fts, int flags)
1476 {
1477 register FTSENT* f;
1478
1479 switch (fts->state)
1480 {
1481
1482 case 0:
1483
1484 if (fts->comparf)
1485 order(fts);
1486 fts->state = FTS_top_return;
1487 return fts->todo;
1488
1489 case FTS_preorder_return:
1490
1491 fts->children = ((flags | fts->flags) & FTS_NOSTAT) ? 2 : 1;
1492 if (f = fts_read(fts))
1493 f = f->fts_link;
1494 return f;
1495
1496 }
1497 return 0;
1498 }
1499
1500 /*
1501 * return default (FTS_LOGICAL|FTS_META|FTS_PHYSICAL|FTS_SEEDOTDIR) flags
1502 * conditioned by astconf()
1503 */
1504
1505 int
fts_flags(void)1506 fts_flags(void)
1507 {
1508 register char* s;
1509
1510 s = astconf("PATH_RESOLVE", NiL, NiL);
1511 if (streq(s, "logical"))
1512 return FTS_LOGICAL;
1513 if (streq(s, "physical"))
1514 return FTS_PHYSICAL|FTS_SEEDOTDIR;
1515 return FTS_META|FTS_PHYSICAL|FTS_SEEDOTDIR;
1516 }
1517
1518 /*
1519 * return 1 if ent is mounted on a local filesystem
1520 */
1521
1522 int
fts_local(FTSENT * ent)1523 fts_local(FTSENT* ent)
1524 {
1525 #ifdef ST_LOCAL
1526 struct statvfs fs;
1527
1528 return statvfs(ent->fts_path, &fs) || (fs.f_flag & ST_LOCAL);
1529 #else
1530 return !strgrpmatch(fmtfs(ent->fts_statp), "([an]fs|samb)", NiL, 0, STR_LEFT|STR_ICASE);
1531 #endif
1532 }
1533
1534 /*
1535 * close an open fts stream
1536 */
1537
1538 int
fts_close(register FTS * fts)1539 fts_close(register FTS* fts)
1540 {
1541 register FTSENT* f;
1542 register FTSENT* x;
1543
1544 if (fts->dir)
1545 closedir(fts->dir);
1546 if (fts->cd == 0)
1547 pathcd(fts->home, NiL);
1548 free(fts->home);
1549 if (fts->state == FTS_children_return)
1550 fts->current->fts_link = fts->link;
1551 if (fts->top)
1552 {
1553 fts->bot->fts_link = fts->todo;
1554 fts->todo = fts->top;
1555 }
1556 for (f = fts->todo; f; f = x)
1557 {
1558 x = f->fts_link;
1559 free(f);
1560 }
1561 for (f = fts->free; f; f = x)
1562 {
1563 x = f->fts_link;
1564 free(f);
1565 }
1566 free(fts);
1567 return 0;
1568 }
1569
1570 /*
1571 * register function to be called for each fts_read() entry
1572 * context==0 => unregister notifyf
1573 */
1574
1575 int
fts_notify(Notify_f notifyf,void * context)1576 fts_notify(Notify_f notifyf, void* context)
1577 {
1578 register Notify_t* np;
1579 register Notify_t* pp;
1580
1581 if (context)
1582 {
1583 if (!(np = newof(0, Notify_t, 1, 0)))
1584 return -1;
1585 np->notifyf = notifyf;
1586 np->context = context;
1587 np->next = notify;
1588 notify = np;
1589 }
1590 else
1591 {
1592 for (np = notify, pp = 0; np; pp = np, np = np->next)
1593 if (np->notifyf == notifyf)
1594 {
1595 if (pp)
1596 pp->next = np->next;
1597 else
1598 notify = np->next;
1599 free(np);
1600 return 0;
1601 }
1602 return -1;
1603 }
1604 return 0;
1605 }
1606