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