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* 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 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* 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* 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 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 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 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 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 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* 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 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 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* 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* 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 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* 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 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 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 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 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