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