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