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* 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 37struct Ftsent; 38 39typedef int (*Compar_f)(struct Ftsent* const*, struct Ftsent* const*); 40typedef 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 161typedef int (*Notify_f)(FTS*, FTSENT*, void*); 162 163typedef struct Notify_s 164{ 165 struct Notify_s* next; 166 Notify_f notifyf; 167 void* context; 168} Notify_t; 169 170static Notify_t* notify; 171 172/* 173 * allocate an FTSENT node 174 */ 175 176static FTSENT* 177node(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 223static int 224statcmp(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 257static FTSENT* 258search(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 345static FTSENT* 346deleteroot(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 371static void 372getlist(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 412static int 413setdir(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 438static int 439setpdir(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 */ 459static int 460popdirs(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 503static int 504info(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 581static FTSENT* 582toplist(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, strlen(path) + 1, 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 675static void 676order(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 696static int 697resize(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 732FTS* 733fts_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 _HUH_1997_01_07 796 if (!fts->todo || fts->todo->fts_info == FTS_NS && !fts->todo->fts_link) 797#else 798 if (!fts->todo) 799#endif 800 { 801 fts_close(fts); 802 return 0; 803 } 804 return fts; 805} 806 807/* 808 * return the next FTS entry 809 */ 810 811FTSENT* 812fts_read(register FTS* fts) 813{ 814 register char* s; 815 register int n; 816 register FTSENT* f; 817 struct dirent* d; 818 size_t i; 819 FTSENT* t; 820 Notify_t* p; 821#ifdef verify 822 struct stat sb; 823#endif 824 825 for (;;) 826 switch (fts->state) 827 { 828 829 case FTS_top_return: 830 831 f = fts->todo; 832 t = 0; 833 while (f) 834 if (f->status == FTS_SKIP) 835 { 836 if (t) 837 { 838 t->fts_link = f->fts_link; 839 drop(fts, f); 840 f = t->fts_link; 841 } 842 else 843 { 844 fts->todo = f->fts_link; 845 drop(fts, f); 846 f = fts->todo; 847 } 848 } 849 else 850 { 851 t = f; 852 f = f->fts_link; 853 } 854 /*FALLTHROUGH*/ 855 856 case 0: 857 858 if (!fts->state && fts->comparf) 859 order(fts); 860 if (!(f = fts->todo)) 861 return 0; 862 /*FALLTHROUGH*/ 863 864 case FTS_todo: 865 866 /* 867 * process the top object on the stack 868 */ 869 870 fts->root = fts->top = fts->bot = 0; 871 872 /* 873 * initialize the top level 874 */ 875 876 if (f->fts_level == 0) 877 { 878 fts->parent->fts_number = f->fts_number; 879 fts->parent->fts_pointer = f->fts_pointer; 880 fts->parent->fts_statp = f->fts_statp; 881 fts->parent->statb = *f->fts_statp; 882 f->fts_parent = fts->parent; 883 fts->diroot = 0; 884 if (fts->cd == 0) 885 pathcd(fts->home, NiL); 886 else if (fts->cd < 0) 887 fts->cd = 0; 888 fts->pwd = f->fts_parent; 889 fts->curdir = fts->cd ? 0 : f->fts_parent; 890 *(fts->base = fts->path) = 0; 891 } 892 893 /* 894 * chdir to parent if asked for 895 */ 896 897 if (fts->cd < 0) 898 { 899 fts->cd = setdir(fts->home, fts->path); 900 fts->pwd = f->fts_parent; 901 fts->curdir = fts->cd ? 0 : f->fts_parent; 902 } 903 904 /* 905 * add object's name to the path 906 */ 907 908 if ((fts->baselen = f->fts_namelen) >= (fts->endbuf - fts->base) && resize(fts, fts->baselen)) 909 return 0; 910 memcpy(fts->base, f->name, fts->baselen + 1); 911 fts->name = fts->cd ? fts->path : fts->base; 912 /*FALLTHROUGH*/ 913 914 case FTS_preorder: 915 916 /* 917 * check for cycle and open dir 918 */ 919 920 if (f->fts_info == FTS_D) 921 { 922 if ((fts->diroot = search(f, fts->diroot, statcmp, 0)) != f || f->fts_level > 0 && (t = f) && statcmp(&t, &f->fts_parent) == 0) 923 { 924 f->fts_info = FTS_DC; 925 f->fts_cycle = fts->diroot; 926 } 927 else if (!(fts->flags & FTS_TOP) && (!(fts->flags & FTS_XDEV) || f->statb.st_dev == f->fts_parent->statb.st_dev)) 928 { 929 /* 930 * buffer is known to be large enough here! 931 */ 932 933 if (fts->base[fts->baselen - 1] != '/') 934 memcpy(fts->base + fts->baselen, "/.", 3); 935 if (!(fts->dir = opendir(fts->name))) 936 f->fts_info = FTS_DNX; 937 fts->base[fts->baselen] = 0; 938 if (!fts->dir && !(fts->dir = opendir(fts->name))) 939 f->fts_info = FTS_DNR; 940 } 941 } 942 f->nd = f->fts_info & ~FTS_DNX; 943 if (f->nd || !(fts->flags & FTS_NOPREORDER)) 944 { 945 fts->current = f; 946 fts->link = f->fts_link; 947 f->fts_link = 0; 948 f->fts_path = PATH(fts, fts->path, f->fts_level); 949 f->fts_pathlen = (fts->base - f->fts_path) + fts->baselen; 950 f->fts_accpath = ACCESS(fts, f); 951 fts->state = FTS_preorder_return; 952 goto note; 953 } 954 /*FALLTHROUGH*/ 955 956 case FTS_preorder_resume: 957 958 /* 959 * prune 960 */ 961 962 if (!fts->dir || f->nd || f->status == FTS_SKIP) 963 { 964 if (fts->dir) 965 { 966 closedir(fts->dir); 967 fts->dir = 0; 968 } 969 fts->state = FTS_popstack; 970 continue; 971 } 972 973 /* 974 * FTS_D or FTS_DNX, about to read children 975 */ 976 977 if (fts->cd == 0) 978 { 979 if ((fts->cd = chdir(fts->name)) < 0) 980 pathcd(fts->home, NiL); 981 else if (fts->pwd != f) 982 { 983 f->pwd = fts->pwd; 984 fts->pwd = f; 985 } 986 fts->curdir = fts->cd < 0 ? 0 : f; 987 } 988 fts->nostat = fts->children > 1 || f->fts_info == FTS_DNX; 989 fts->cpname = fts->cd && !fts->nostat || !fts->children && !fts->comparf; 990 fts->dotdot = 0; 991 fts->endbase = fts->base + fts->baselen; 992 if (fts->endbase[-1] != '/') 993 *fts->endbase++ = '/'; 994 fts->current = f; 995 /*FALLTHROUGH*/ 996 997 case FTS_readdir: 998 999 while (d = readdir(fts->dir)) 1000 { 1001 s = d->d_name; 1002 if (s[0] == '.') 1003 { 1004 if (s[1] == 0) 1005 { 1006 fts->current->nlink--; 1007 if (!(fts->flags & FTS_SEEDOT)) 1008 continue; 1009 n = 1; 1010 } 1011 else if (s[1] == '.' && s[2] == 0) 1012 { 1013 fts->current->nlink--; 1014 if (fts->current->must == 1) 1015 fts->current->must = 0; 1016 if (!(fts->flags & FTS_SEEDOT)) 1017 continue; 1018 n = 2; 1019 } 1020 else 1021 n = 0; 1022 } 1023 else 1024 n = 0; 1025 1026 /* 1027 * make a new entry 1028 */ 1029 1030 i = D_NAMLEN(d); 1031 if (!(f = node(fts, fts->current, s, i))) 1032 return 0; 1033 TYPE(f, D_TYPE(d)); 1034 1035 /* 1036 * check for space 1037 */ 1038 1039 if (i >= fts->endbuf - fts->endbase) 1040 { 1041 if (resize(fts, i)) 1042 return 0; 1043 fts->endbase = fts->base + fts->baselen; 1044 if (fts->endbase[-1] != '/') 1045 fts->endbase++; 1046 } 1047 if (fts->cpname) 1048 { 1049 memcpy(fts->endbase, s, i + 1); 1050 if (fts->cd) 1051 s = fts->path; 1052 } 1053 if (n) 1054 { 1055 /* 1056 * don't recurse on . and .. 1057 */ 1058 1059 if (n == 1) 1060 f->fts_statp = fts->current->fts_statp; 1061 else 1062 { 1063 if (f->fts_info != FTS_NS) 1064 fts->dotdot = f; 1065 if (fts->current->fts_parent->fts_level < 0) 1066 { 1067 f->fts_statp = &fts->current->fts_parent->statb; 1068 info(fts, f, s, f->fts_statp, 0); 1069 } 1070 else 1071 f->fts_statp = fts->current->fts_parent->fts_statp; 1072 } 1073 f->fts_info = FTS_DOT; 1074 } 1075 else if ((fts->nostat || SKIP(fts, f)) && (f->fts_info = FTS_NSOK) || info(fts, f, s, &f->statb, fts->flags)) 1076 f->statb.st_ino = D_FILENO(d); 1077 if (fts->comparf) 1078 fts->root = search(f, fts->root, fts->comparf, 1); 1079 else if (fts->children || f->fts_info == FTS_D || f->fts_info == FTS_SL) 1080 { 1081 if (fts->top) 1082 fts->bot = fts->bot->fts_link = f; 1083 else 1084 fts->top = fts->bot = f; 1085 } 1086 else 1087 { 1088 /* 1089 * terminal node 1090 */ 1091 1092 f->fts_path = PATH(fts, fts->path, 1); 1093 f->fts_pathlen = fts->endbase - f->fts_path + f->fts_namelen; 1094 f->fts_accpath = ACCESS(fts, f); 1095 fts->previous = fts->current; 1096 fts->current = f; 1097 fts->state = FTS_terminal; 1098 goto note; 1099 } 1100 } 1101 1102 /* 1103 * done with the directory 1104 */ 1105 1106 closedir(fts->dir); 1107 fts->dir = 0; 1108 if (fts->root) 1109 getlist(&fts->top, &fts->bot, fts->root); 1110 if (fts->children) 1111 { 1112 /* 1113 * try moving back to parent dir 1114 */ 1115 1116 fts->base[fts->baselen] = 0; 1117 if (fts->cd <= 0) 1118 { 1119 f = fts->current->fts_parent; 1120 if (fts->cd < 0 1121 || f != fts->curdir 1122 || !fts->dotdot 1123 || !SAME(f->fts_statp, fts->dotdot->fts_statp) 1124 || fts->pwd && fts->pwd->symlink 1125 || (fts->cd = chdir("..")) < 0 1126#ifdef verify 1127 || stat(".", &sb) < 0 1128 || !SAME(&sb, fts->dotdot->fts_statp) 1129#endif 1130 ) 1131 fts->cd = setpdir(fts->home, fts->path, fts->base); 1132 if (fts->pwd) 1133 fts->pwd = fts->pwd->pwd; 1134 fts->curdir = fts->cd ? 0 : f; 1135 } 1136 f = fts->current; 1137 fts->link = f->fts_link; 1138 f->fts_link = fts->top; 1139 f->fts_path = PATH(fts, fts->path, f->fts_level); 1140 f->fts_pathlen = (fts->base - f->fts_path) + f->fts_namelen; 1141 f->fts_accpath = ACCESS(fts, f); 1142 fts->state = FTS_children_return; 1143 goto note; 1144 } 1145 /*FALLTHROUGH*/ 1146 1147 case FTS_children_resume: 1148 1149 fts->base[fts->baselen] = 0; 1150 if (fts->top) 1151 { 1152 fts->bot->fts_link = fts->todo; 1153 fts->todo = fts->top; 1154 fts->top = 0; 1155 } 1156 /*FALLTHROUGH*/ 1157 1158 case FTS_popstack: 1159 1160 /* 1161 * pop objects completely processed 1162 */ 1163 1164 fts->nd = 0; 1165 f = fts->current; 1166 /*FALLTHROUGH*/ 1167 1168 case FTS_popstack_resume: 1169 1170 while (fts->todo && f == fts->todo) 1171 { 1172 t = f->fts_parent; 1173 if ((f->fts_info & FTS_DP) == FTS_D) 1174 { 1175 /* 1176 * delete from <dev,ino> tree 1177 */ 1178 1179 if (f != fts->diroot) 1180 fts->diroot = search(f, fts->diroot, statcmp, 0); 1181 fts->diroot = deleteroot(fts->diroot); 1182 if (f == fts->curdir) 1183 { 1184 fts->nd++; 1185 fts->curdir = t; 1186 } 1187 1188 /* 1189 * perform post-order processing 1190 */ 1191 1192 if (!(fts->flags & FTS_NOPOSTORDER) && 1193 f->status != FTS_SKIP && 1194 f->status != FTS_NOPOSTORDER) 1195 { 1196 /* 1197 * move to parent dir 1198 */ 1199 1200 if (fts->nd > 0) 1201 fts->cd = popdirs(fts); 1202 if (fts->cd < 0) 1203 fts->cd = setpdir(fts->home, fts->path, fts->base); 1204 fts->curdir = fts->cd ? 0 : t; 1205 f->fts_info = FTS_DP; 1206 f->fts_path = PATH(fts, fts->path, f->fts_level); 1207 f->fts_pathlen = (fts->base - f->fts_path) + f->fts_namelen; 1208 f->fts_accpath = ACCESS(fts, f); 1209 1210 /* 1211 * re-stat to update nlink/times 1212 */ 1213 1214 stat(f->fts_accpath, f->fts_statp); 1215 fts->link = f->fts_link; 1216 f->fts_link = 0; 1217 fts->state = FTS_popstack_return; 1218 goto note; 1219 } 1220 } 1221 1222 /* 1223 * reset base 1224 */ 1225 1226 if (fts->base > fts->path + t->fts_namelen) 1227 fts->base--; 1228 *fts->base = 0; 1229 fts->base -= t->fts_namelen; 1230 1231 /* 1232 * try again or delete from top of stack 1233 */ 1234 1235 if (f->status == FTS_AGAIN) 1236 { 1237 f->fts_info = FTS_D; 1238 f->status = 0; 1239 } 1240 else 1241 { 1242 fts->todo = fts->todo->fts_link; 1243 drop(fts, f); 1244 } 1245 f = t; 1246 } 1247 1248 /* 1249 * reset current directory 1250 */ 1251 1252 if (fts->nd > 0 && popdirs(fts) < 0) 1253 { 1254 pathcd(fts->home, NiL); 1255 fts->curdir = 0; 1256 fts->cd = -1; 1257 } 1258 if (fts->todo) 1259 { 1260 if (*fts->base) 1261 fts->base += f->fts_namelen; 1262 if (*(fts->base - 1) != '/') 1263 *fts->base++ = '/'; 1264 *fts->base = 0; 1265 f = fts->todo; 1266 fts->state = FTS_todo; 1267 continue; 1268 } 1269 return 0; 1270 1271 case FTS_children_return: 1272 1273 f = fts->current; 1274 f->fts_link = fts->link; 1275 1276 /* 1277 * chdir down again 1278 */ 1279 1280 i = f->fts_info != FTS_DNX; 1281 n = f->status == FTS_SKIP; 1282 if (!n && fts->cd == 0) 1283 { 1284 if ((fts->cd = chdir(fts->base)) < 0) 1285 pathcd(fts->home, NiL); 1286 else if (fts->pwd != f) 1287 { 1288 f->pwd = fts->pwd; 1289 fts->pwd = f; 1290 } 1291 fts->curdir = fts->cd ? 0 : f; 1292 } 1293 1294 /* 1295 * prune 1296 */ 1297 1298 if (fts->base[fts->baselen - 1] != '/') 1299 fts->base[fts->baselen] = '/'; 1300 for (fts->bot = 0, f = fts->top; f; ) 1301 if (n || f->status == FTS_SKIP) 1302 { 1303 if (fts->bot) 1304 fts->bot->fts_link = f->fts_link; 1305 else 1306 fts->top = f->fts_link; 1307 drop(fts, f); 1308 f = fts->bot ? fts->bot->fts_link : fts->top; 1309 } 1310 else 1311 { 1312 if (fts->children > 1 && i) 1313 { 1314 if (f->status == FTS_STAT) 1315 info(fts, f, NiL, f->fts_statp, 0); 1316 else if (f->fts_info == FTS_NSOK && !SKIP(fts, f)) 1317 { 1318 s = f->fts_name; 1319 if (fts->cd) 1320 { 1321 memcpy(fts->endbase, s, f->fts_namelen + 1); 1322 s = fts->path; 1323 } 1324 info(fts, f, s, f->fts_statp, fts->flags); 1325 } 1326 } 1327 fts->bot = f; 1328 f = f->fts_link; 1329 } 1330 fts->children = 0; 1331 fts->state = FTS_children_resume; 1332 continue; 1333 1334 case FTS_popstack_return: 1335 1336 f = fts->todo; 1337 f->fts_link = fts->link; 1338 f->fts_info = f->status == FTS_AGAIN ? FTS_DP : 0; 1339 fts->state = FTS_popstack_resume; 1340 continue; 1341 1342 case FTS_preorder_return: 1343 1344 f = fts->current; 1345 f->fts_link = fts->link; 1346 1347 /* 1348 * follow symlink if asked to 1349 */ 1350 1351 if (f->status == FTS_FOLLOW) 1352 { 1353 f->status = 0; 1354 if (f->fts_info == FTS_SL || ISTYPE(f, DT_LNK) || f->fts_info == FTS_NSOK) 1355 { 1356 info(fts, f, f->fts_accpath, f->fts_statp, 0); 1357 if (f->fts_info != FTS_SL) 1358 { 1359 fts->state = FTS_preorder; 1360 continue; 1361 } 1362 } 1363 } 1364 1365 /* 1366 * about to prune this f and already at home 1367 */ 1368 1369 if (fts->cd == 0 && f->fts_level == 0 && f->nd) 1370 fts->cd = -1; 1371 fts->state = FTS_preorder_resume; 1372 continue; 1373 1374 case FTS_terminal: 1375 1376 f = fts->current; 1377 if (f->status == FTS_FOLLOW) 1378 { 1379 f->status = 0; 1380 if (f->fts_info == FTS_SL || ISTYPE(f, DT_LNK) || f->fts_info == FTS_NSOK) 1381 { 1382 info(fts, f, f->fts_accpath, f->fts_statp, 0); 1383 if (f->symlink && f->fts_info != FTS_SL) 1384 { 1385 if (!(f->fts_link = fts->top)) 1386 fts->bot = f; 1387 fts->top = f; 1388 fts->current = fts->previous; 1389 fts->state = FTS_readdir; 1390 continue; 1391 } 1392 } 1393 } 1394 f = f->fts_parent; 1395 drop(fts, fts->current); 1396 fts->current = f; 1397 fts->state = FTS_readdir; 1398 continue; 1399 1400 case FTS_error: 1401 1402 return 0; 1403 1404 default: 1405 1406 fts->fts_errno = EINVAL; 1407 fts->state = FTS_error; 1408 return 0; 1409 1410 } 1411 note: 1412#if __OBSOLETE__ < 20140101 1413 f->_fts_pathlen = (unsigned short)f->fts_pathlen; 1414#endif 1415 for (p = notify; p; p = p->next) 1416 if ((n = (*p->notifyf)(fts, f, p->context)) > 0) 1417 break; 1418 else if (n < 0) 1419 { 1420 fts->fts_errno = EINVAL; 1421 fts->state = FTS_error; 1422 return 0; 1423 } 1424 return f; 1425} 1426 1427/* 1428 * set stream or entry flags 1429 */ 1430 1431int 1432fts_set(register FTS* fts, register FTSENT* f, int status) 1433{ 1434 if (fts || !f || f->fts->current != f) 1435 return -1; 1436 switch (status) 1437 { 1438 case FTS_AGAIN: 1439 break; 1440 case FTS_FOLLOW: 1441 if (!(f->fts_info & FTS_SL)) 1442 return -1; 1443 break; 1444 case FTS_NOPOSTORDER: 1445 break; 1446 case FTS_SKIP: 1447 if ((f->fts_info & (FTS_D|FTS_P)) != FTS_D) 1448 return -1; 1449 break; 1450 default: 1451 return -1; 1452 } 1453 f->status = status; 1454 return 0; 1455} 1456 1457/* 1458 * return the list of child entries 1459 */ 1460 1461FTSENT* 1462fts_children(register FTS* fts, int flags) 1463{ 1464 register FTSENT* f; 1465 1466 switch (fts->state) 1467 { 1468 1469 case 0: 1470 1471 if (fts->comparf) 1472 order(fts); 1473 fts->state = FTS_top_return; 1474 return fts->todo; 1475 1476 case FTS_preorder_return: 1477 1478 fts->children = ((flags | fts->flags) & FTS_NOSTAT) ? 2 : 1; 1479 if (f = fts_read(fts)) 1480 f = f->fts_link; 1481 return f; 1482 1483 } 1484 return 0; 1485} 1486 1487/* 1488 * return default (FTS_LOGICAL|FTS_META|FTS_PHYSICAL|FTS_SEEDOTDIR) flags 1489 * conditioned by astconf() 1490 */ 1491 1492int 1493fts_flags(void) 1494{ 1495 register char* s; 1496 1497 s = astconf("PATH_RESOLVE", NiL, NiL); 1498 if (streq(s, "logical")) 1499 return FTS_LOGICAL; 1500 if (streq(s, "physical")) 1501 return FTS_PHYSICAL|FTS_SEEDOTDIR; 1502 return FTS_META|FTS_PHYSICAL|FTS_SEEDOTDIR; 1503} 1504 1505/* 1506 * return 1 if ent is mounted on a local filesystem 1507 */ 1508 1509int 1510fts_local(FTSENT* ent) 1511{ 1512#ifdef ST_LOCAL 1513 struct statvfs fs; 1514 1515 return statvfs(ent->fts_path, &fs) || (fs.f_flag & ST_LOCAL); 1516#else 1517 return !strgrpmatch(fmtfs(ent->fts_statp), "([an]fs|samb)", NiL, 0, STR_LEFT|STR_ICASE); 1518#endif 1519} 1520 1521/* 1522 * close an open fts stream 1523 */ 1524 1525int 1526fts_close(register FTS* fts) 1527{ 1528 register FTSENT* f; 1529 register FTSENT* x; 1530 1531 if (fts->dir) 1532 closedir(fts->dir); 1533 if (fts->cd == 0) 1534 pathcd(fts->home, NiL); 1535 free(fts->home); 1536 if (fts->state == FTS_children_return) 1537 fts->current->fts_link = fts->link; 1538 if (fts->top) 1539 { 1540 fts->bot->fts_link = fts->todo; 1541 fts->todo = fts->top; 1542 } 1543 for (f = fts->todo; f; f = x) 1544 { 1545 x = f->fts_link; 1546 free(f); 1547 } 1548 for (f = fts->free; f; f = x) 1549 { 1550 x = f->fts_link; 1551 free(f); 1552 } 1553 free(fts); 1554 return 0; 1555} 1556 1557/* 1558 * register function to be called for each fts_read() entry 1559 * context==0 => unregister notifyf 1560 */ 1561 1562int 1563fts_notify(Notify_f notifyf, void* context) 1564{ 1565 register Notify_t* np; 1566 register Notify_t* pp; 1567 1568 if (context) 1569 { 1570 if (!(np = newof(0, Notify_t, 1, 0))) 1571 return -1; 1572 np->notifyf = notifyf; 1573 np->context = context; 1574 np->next = notify; 1575 notify = np; 1576 } 1577 else 1578 { 1579 for (np = notify, pp = 0; np; pp = np, np = np->next) 1580 if (np->notifyf == notifyf) 1581 { 1582 if (pp) 1583 pp->next = np->next; 1584 else 1585 notify = np->next; 1586 free(np); 1587 return 0; 1588 } 1589 return -1; 1590 } 1591 return 0; 1592} 1593