cde/programs/dtksh/ksh93/src/lib/libast/misc/ftwalk.c

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 /* $XConsortium: ftwalk.c /main/3 1995/11/01 17:55:51 rswiston $ */
  24 /***************************************************************
  25 *                                                              *
  26 *                      AT&T - PROPRIETARY                      *
  27 *                                                              *
  28 *         THIS IS PROPRIETARY SOURCE CODE LICENSED BY          *
  29 *                          AT&T CORP.                          *
  30 *                                                              *
  31 *                Copyright (c) 1995 AT&T Corp.                 *
  32 *                     All Rights Reserved                      *
  33 *                                                              *
  34 *           This software is licensed by AT&T Corp.            *
  35 *       under the terms and conditions of the license in       *
  36 *       http://www.research.att.com/orgs/ssr/book/reuse        *
  37 *                                                              *
  38 *               This software was created by the               *
  39 *           Software Engineering Research Department           *
  40 *                    AT&T Bell Laboratories                    *
  41 *                                                              *
  42 *               For further information contact                *
  43 *                     gsf@research.att.com                     *
  44 *                                                              *
  45 ***************************************************************/
  46
  47 /* : : generated by proto : : */
  48
  49 #if !defined(__PROTO__)
  50 #if defined(__STDC__) || defined(__cplusplus) || defined(_proto) || defined(c_plusplus)
  51 #if defined(__cplusplus)
  52 #define __MANGLE__      "C"
  53 #else
  54 #define __MANGLE__
  55 #endif
  56 #define __STDARG__
  57 #define __PROTO__(x)    x
  58 #define __OTORP__(x)
  59 #define __PARAM__(n,o)  n
  60 #if !defined(__STDC__) && !defined(__cplusplus)
  61 #if !defined(c_plusplus)
  62 #define const
  63 #endif
  64 #define signed
  65 #define void            int
  66 #define volatile
  67 #define __V_            char
  68 #else
  69 #define __V_            void
  70 #endif
  71 #else
  72 #define __PROTO__(x)    ()
  73 #define __OTORP__(x)    x
  74 #define __PARAM__(n,o)  o
  75 #define __MANGLE__
  76 #define __V_            char
  77 #define const
  78 #define signed
  79 #define void            int
  80 #define volatile
  81 #endif
  82 #if defined(__cplusplus) || defined(c_plusplus)
  83 #define __VARARG__      ...
  84 #else
  85 #define __VARARG__
  86 #endif
  87 #if defined(__STDARG__)
  88 #define __VA_START__(p,a)       va_start(p,a)
  89 #else
  90 #define __VA_START__(p,a)       va_start(p)
  91 #endif
  92 #endif
  93 #include        "dirlib.h"
  94
  95 #include        <ftwalk.h>
  96
  97 #if MAXNAMLEN > 16
  98 #define MINNAME         24
  99 #else
 100 #define MINNAME         16
 101 #endif
 102
 103 /* function to determine type of an object */
 104 #ifdef S_ISLNK
 105 #define TYPE(m)         (S_ISDIR(m) ? FTW_D : S_ISLNK(m) ? FTW_SL : FTW_F)
 106 #else
 107 #define TYPE(m)         (S_ISDIR(m) ? FTW_D : FTW_F)
 108 #endif
 109
 110 /* to set state.status and state.base on calls to user function */
 111 #define STATUS(cdrv)    (cdrv == 0 ? FTW_NAME : FTW_PATH)
 112
 113 /* see if same object */
 114 #define SAME(one,two)   ((one).st_ino == (two).st_ino && (one).st_dev == (two).st_dev)
 115
 116 /* path name */
 117 #define PATH(p,l)       ((l) > 0 && (p)[0] == '.' && (p)[1] == '/' ? (p)+2 : (p))
 118
 119 /*
 120         Make/free an object of type FTW.
 121 */
 122 static Ftw_t    *Free;
 123 #define freeFtw(f)      ((f)->link = Free, Free = (f))
 124
 125 static Ftw_t *newFtw __PARAM__((register char* name, register int namelen), (name, namelen)) __OTORP__(register char* name; register int namelen;){
 126         register Ftw_t  *f;
 127         register int    amount;
 128
 129         if(Free && namelen < MINNAME)
 130                 f = Free, Free = f->link;
 131         else
 132         {
 133                 amount = namelen < MINNAME ? MINNAME : namelen+1;
 134                 if(!(f = newof(0, Ftw_t, 1, amount-sizeof(int))))
 135                         return 0;
 136         }
 137         f->link = 0;
 138         f->local.number = 0;
 139         f->local.pointer = 0;
 140         f->status = FTW_NAME;
 141         f->namelen = namelen;
 142         memcpy(f->name,name,namelen+1);
 143
 144         return f;
 145 }
 146
 147 static int freeAll __PARAM__((register Ftw_t* f, register int rv), (f, rv)) __OTORP__(register Ftw_t* f; register int rv;){
 148         register Ftw_t  *next;
 149         register int    freeing;
 150
 151         for(freeing = 0; freeing < 2; ++freeing)
 152         {
 153                 if(freeing == 1)
 154                         f = Free, Free = 0;
 155                 while(f)
 156                 {
 157                         next = f->link;
 158                         free(f);
 159                         f = next;
 160                 }
 161         }
 162         return rv;
 163 }
 164
 165 /*
 166         To compare directories by device/inode.
 167 */
 168 static int statcmp __PARAM__((register Ftw_t* f1, register Ftw_t* f2), (f1, f2)) __OTORP__(register Ftw_t* f1; register Ftw_t* f2;){
 169         register int    d;
 170         if((d = f1->statb.st_ino - f2->statb.st_ino) != 0)
 171                 return d;
 172         if((d = f1->statb.st_dev - f2->statb.st_dev) != 0)
 173                 return d;
 174         /* hack for NFS system where (dev,ino) do not uniquely identify objects */
 175         return (f1->statb.st_mtime - f2->statb.st_mtime);
 176 }
 177
 178 /*
 179         Search trees with top-down splaying (a la Tarjan and Sleator).
 180         When used for insertion sort, this implements a stable sort.
 181 */
 182 #define RROTATE(r)      (t = r->left, r->left = t->right, t->right = r, r = t)
 183 #define LROTATE(r)      (t = r->right, r->right = t->left, t->left = r, r = t)
 184
 185 static Ftw_t *search __PARAM__((register Ftw_t* e, register Ftw_t* root, int(*comparf)(Ftw_t*, Ftw_t*), int insert), (e, root, comparf, insert)) __OTORP__(register Ftw_t* e; register Ftw_t* root; int(*comparf)(); int insert;){
 186         register int            cmp;
 187         register Ftw_t          *t, *left, *right, *lroot, *rroot;
 188
 189         left = right = lroot = rroot = 0;
 190         while(root)
 191         {
 192                 if((cmp = (*comparf)(e,root)) == 0 && !insert)
 193                         break;
 194                 if(cmp < 0)
 195                 {       /* this is the left zig-zig case */
 196                         if(root->left && (cmp = (*comparf)(e,root->left)) <= 0)
 197                         {
 198                                 RROTATE(root);
 199                                 if(cmp == 0 && !insert)
 200                                         break;
 201                         }
 202
 203                         /* stick all things > e to the right tree */
 204                         if(right)
 205                                 right->left = root;
 206                         else    rroot = root;
 207                         right = root;
 208                         root = root->left;
 209                         right->left = 0;
 210                 }
 211                 else
 212                 {       /* this is the right zig-zig case */
 213                         if(root->right && (cmp = (*comparf)(e,root->right)) >= 0)
 214                         {
 215                                 LROTATE(root);
 216                                 if(cmp == 0 && !insert)
 217                                         break;
 218                         }
 219
 220                         /* stick all things <= e to the left tree */
 221                         if(left)
 222                                 left->right = root;
 223                         else    lroot = root;
 224                         left = root;
 225                         root = root->right;
 226                         left->right = 0;
 227                 }
 228         }
 229
 230         if(!root)
 231                 root = e;
 232         else
 233         {
 234                 if(right)
 235                         right->left = root->right;
 236                 else    rroot = root->right;
 237                 if(left)
 238                         left->right = root->left;
 239                 else    lroot = root->left;
 240         }
 241
 242         root->left = lroot;
 243         root->right = rroot;
 244         return root;
 245 }
 246
 247 /*
 248 **      Delete the root element from the tree
 249 */
 250 static Ftw_t *deleteroot __PARAM__((register Ftw_t* root), (root)) __OTORP__(register Ftw_t* root;){
 251         register Ftw_t *t, *left, *right;
 252
 253         left = root->left;
 254         right = root->right;
 255         if(!left)
 256                 root = right;
 257         else
 258         {
 259                 while(left->right)
 260                         LROTATE(left);
 261                 left->right = right;
 262                 root = left;
 263         }
 264         return root;
 265 }
 266
 267 /*
 268         Convert a binary search tree into a sorted todo (link) list
 269 */
 270 static void getlist __PARAM__((register Ftw_t** top, register Ftw_t** bot, register Ftw_t* root), (top, bot, root)) __OTORP__(register Ftw_t** top; register Ftw_t** bot; register Ftw_t* root;){
 271         if(root->left)
 272                 getlist(top,bot,root->left);
 273         if (*top) (*bot)->link = root, *bot = root;
 274         else *top = *bot = root;
 275         if(root->right)
 276                 getlist(top,bot,root->right);
 277 }
 278
 279 /*
 280         Set directory when curdir is lost in space
 281 */
 282 static int setdir __PARAM__((register char* home, register char* path), (home, path)) __OTORP__(register char* home; register char* path;){
 283         register int    cdrv;
 284
 285         if(path[0] == '/')
 286                 cdrv = pathcd(path,NiL);
 287         else
 288         {       /* Note that path and home are in the same buffer */
 289                 path[-1] = '/';
 290                 cdrv = pathcd(home,NiL);
 291                 path[-1] = '\0';
 292         }
 293         if(cdrv < 0)
 294                 (void) pathcd(home,NiL);
 295         return cdrv;
 296 }
 297
 298 /*
 299         Set to parent dir
 300 */
 301 static int setpdir __PARAM__((register char* home, register char* path, register char* base), (home, path, base)) __OTORP__(register char* home; register char* path; register char* base;){
 302         register int    cdrv, c;
 303
 304         if(base > path)
 305         {
 306                 c = base[0];
 307                 base[0] = '\0';
 308                 cdrv = setdir(home,path);
 309                 base[0] = c;
 310         }
 311         else    cdrv = pathcd(home,NiL);
 312         return cdrv;
 313 }
 314
 315 /*
 316         Pop a set of directories
 317 */
 318 static int popdirs __PARAM__((register int n_dir, register Ftw_t* ftw), (n_dir, ftw)) __OTORP__(register int n_dir; register Ftw_t* ftw;){
 319         struct stat     sb;
 320         register char   *s, *endbuf;
 321         char            buf[PATH_MAX];
 322
 323         if(!ftw || ftw->level < 0)
 324                 return -1;
 325
 326         endbuf = buf + (PATH_MAX-4);
 327         while(n_dir > 0)
 328         {
 329                 for(s = buf; s < endbuf && n_dir > 0; --n_dir)
 330                         *s++ = '.', *s++ = '.', *s++ = '/';
 331                 *s = '\0';
 332                 if(chdir(buf) < 0)
 333                         return -1;
 334         }
 335         if(stat(".",&sb) != 0 || !SAME(sb,ftw->statb))
 336                 return -1;
 337         return 0;
 338 }
 339
 340 /*
 341         Get top list of elt to process
 342 */
 343 static Ftw_t *toplist __PARAM__((register char** paths, int(*statf)(const char*, struct stat*),int(*comparf)(Ftw_t*, Ftw_t*), int metaphysical), (paths, statf, comparf, metaphysical)) __OTORP__(register char** paths; int(*statf)();int(*comparf)(); int metaphysical;){
 344         register char           *path;
 345         register Ftw_t          *f, *root;
 346         Ftw_t                   *top, *bot;
 347         register struct stat    *sb;
 348         struct stat             st;
 349
 350         top = bot = root = 0;
 351         for(; *paths; ++paths)
 352         {
 353                 path = *paths;
 354                 if(!path[0])
 355                         path = ".";
 356
 357                 /* make elements */
 358                 if(!(f = newFtw(path,strlen(path))))
 359                         break;
 360                 f->level = 0;
 361                 sb = &(f->statb);
 362                 f->info = (*statf)(path,sb) < 0 ? FTW_NS : TYPE(sb->st_mode);
 363 #ifdef S_ISLNK
 364                 /*
 365                  * don't let any standards committee member
 366                  * get away with calling your idea a hack
 367                  */
 368
 369                 if (metaphysical && f->info == FTW_SL && stat(path,&st) == 0)
 370                 {
 371                         *sb = st;
 372                         f->info = TYPE(sb->st_mode);
 373                 }
 374 #endif
 375
 376                 if(comparf)
 377                         root = search(f,root,comparf,1);
 378                 else if(bot)
 379                         bot->link = f, bot = f;
 380                 else    top = bot = f;
 381         }
 382         if(comparf)
 383                 getlist(&top,&bot,root);
 384         return top;
 385 }
 386
 387 /*
 388         Resize path buffer.
 389         Note that free() is not used because we may need to chdir(home)
 390         if there isn't enough space to continue
 391 */
 392 static int resize __PARAM__((register char** home, register char** endbuf, register char** path, register char** base, int n_buf, int incre), (home, endbuf, path, base, n_buf, incre)) __OTORP__(register char** home; register char** endbuf; register char** path; register char** base; int n_buf; int incre;){
 393         register char   *old, *newp;
 394         register int            n_old;
 395
 396         /* add space for "/." used in testing FTW_DNX */
 397         n_old = n_buf;
 398         n_buf = ((n_buf+incre+4)/PATH_MAX + 1)*PATH_MAX;
 399         if(!(newp = newof(0, char, n_buf, 0)))
 400                 return -1;
 401
 402         old = *home;
 403         *home = newp;
 404         memcpy(newp,old,n_old);
 405         if(endbuf)
 406                 *endbuf = newp + n_buf - 4;
 407         if(path)
 408                 *path = newp + (*path - old);
 409         if(base)
 410                 *base = newp + (*base - old);
 411
 412         free(old);
 413         return n_buf;
 414 }
 415
 416 /*
 417         The real thing.
 418 */
 419 ftwalk __PARAM__((const char *cpath, int (*userf)(Ftw_t*), int flags, int (*comparf)(Ftw_t*, Ftw_t*)), (cpath, userf, flags, comparf)) __OTORP__(const char *cpath; int (*userf)(); int flags; int (*comparf)();){
 420         char            *path = (char*)cpath;
 421         register int    cdrv;           /* chdir value */
 422         int             fnrv;           /* return value from user function */
 423         Ftw_t           topf,           /* the parent of top elt */
 424                         *todo, *top, *bot;
 425         DIR             *dirfp;
 426         int             (*statf) __PROTO__((const char*, struct stat*));
 427         int             preorder, children, postorder;
 428         char            *endbuf; /* space to build paths */
 429         static char     *Home;
 430         static int      N_buf;
 431
 432         /* decode the flags */
 433         children = (flags&FTW_CHILDREN) ? 1 : 0;
 434         children = (children && (flags&FTW_DELAY)) ? 2 : children;
 435         preorder = ((flags&FTW_POST) == 0 && !children);
 436         postorder = (flags&(FTW_POST|FTW_TWICE));
 437         cdrv = (flags&FTW_DOT) ? 1 : -1;
 438 #ifdef S_ISLNK
 439         statf = (flags&FTW_PHYSICAL) ? lstat : pathstat;
 440 #else
 441         statf = stat;
 442 #endif
 443         /* space for home directory and paths */
 444         if(!Home)
 445                 N_buf = 2*PATH_MAX;
 446         while(1)
 447         {
 448                 if(!Home && !(Home = newof(0, char, N_buf, 0)))
 449                         return -1;
 450                 Home[0] = 0;
 451                 if(cdrv > 0 || getcwd(Home,N_buf))
 452                         break;
 453                 else if(errno == ERANGE)
 454                 {       /* need larger buffer */
 455                         free(Home);
 456                         N_buf += PATH_MAX;
 457                         Home = 0;
 458                 }
 459                 else    cdrv = 1;
 460         }
 461         endbuf = Home + N_buf - 4;
 462
 463         fnrv = -1;
 464
 465         /* make the list of top elements */
 466         todo = top = bot = 0;
 467         if((flags&FTW_MULTIPLE) && path)
 468                 todo = toplist((char**)path,statf,comparf,(flags&(FTW_META|FTW_PHYSICAL))==(FTW_META|FTW_PHYSICAL));
 469         else
 470         {
 471                 char    *p[2];
 472                 p[0] = path ? path : ".";
 473                 p[1] = 0;
 474                 todo = toplist(p,statf,comparf,(flags&(FTW_META|FTW_PHYSICAL))==(FTW_META|FTW_PHYSICAL));
 475         }
 476
 477         path = Home + strlen(Home) + 1;
 478         dirfp = 0;
 479         while(todo)
 480         {
 481                 register int            i, nd;
 482                 register Ftw_t          *ftw, *f;
 483                 register struct stat    *sb;
 484                 register char           *name, *endbase;
 485                 Ftw_t                   *link, *root, *curdir, *diroot, *dotdot;
 486                 struct dirent           *dir;
 487                 char                    *base;
 488                 register int            level, n_base, nostat, cpname;
 489
 490                 /* process the top object on the stack */
 491                 ftw = todo;
 492                 link = ftw->link;
 493                 sb = &(ftw->statb);
 494                 name = ftw->name;
 495                 level = ftw->level;
 496                 fnrv = -1;
 497                 top = bot = root = 0;
 498
 499                 /* initialize for level 0 */
 500                 if(level == 0)
 501                 {
 502                         /* initialize parent */
 503                         memcpy(&topf,ftw,sizeof(topf));
 504                         topf.level = -1;
 505                         topf.name[0] = '\0';
 506                         topf.path = 0;
 507                         topf.pathlen = topf.namelen = 0;
 508                         topf.parent = 0;
 509                         ftw->parent = &topf;
 510
 511                         diroot = 0;
 512                         if(cdrv == 0)
 513                                 (void) pathcd(Home,NiL);
 514                         else if(cdrv < 0)
 515                                 cdrv = 0;
 516                         curdir = cdrv ? 0 : ftw->parent;
 517                         base = path;
 518                         *base = '\0';
 519                 }
 520
 521                 /* chdir to parent dir if asked for */
 522                 if(cdrv < 0)
 523                 {
 524                         cdrv = setdir(Home,path);
 525                         curdir = cdrv ? 0 : ftw->parent;
 526                 }
 527
 528                 /* add object's name to the path */
 529                 if((n_base = ftw->namelen) >= endbuf-base &&
 530                    (N_buf = resize(&Home,&endbuf,&path,&base,N_buf,n_base)) < 0)
 531                         goto done;
 532                 memcpy(base,name,n_base+1);
 533                 name = cdrv ? path : base;
 534
 535                 /* check for cycle and open dir */
 536                 if(ftw->info == FTW_D)
 537                 {
 538                         if((diroot = search(ftw,diroot,statcmp,0)) != ftw || level > 0 && statcmp(ftw,ftw->parent) == 0)
 539                         {
 540                                 ftw->info = FTW_DC;
 541                                 ftw->link = diroot;
 542                         }
 543                         else
 544                         {       /* buffer is known to be large enough here! */
 545                                 if(base[n_base-1] != '/')
 546                                         memcpy(base+n_base,"/.",3);
 547                                 if(!(dirfp = opendir(name)))
 548                                         ftw->info = FTW_DNX;
 549                                 base[n_base] = '\0';
 550                                 if(!dirfp && !(dirfp = opendir(name)))
 551                                         ftw->info = FTW_DNR;
 552                         }
 553                 }
 554
 555                 /* call user function in preorder */
 556                 nd = ftw->info & ~FTW_DNX;
 557                 if(nd || preorder)
 558                 {
 559                         ftw->status = STATUS(cdrv);
 560                         ftw->link = 0;
 561                         ftw->path = PATH(path,level);
 562                         ftw->pathlen = (base - ftw->path) + n_base;
 563                         fnrv = (*userf)(ftw);
 564                         ftw->link = link;
 565                         if(fnrv)
 566                                 goto done;
 567
 568                         /* follow symlink if asked to */
 569                         if(ftw->info == FTW_SL && ftw->status == FTW_FOLLOW)
 570                         {
 571                                 ftw->info = stat(name,sb) ? FTW_NS : TYPE(sb->st_mode);
 572                                 if(ftw->info != FTW_SL)
 573                                         continue;
 574                         }
 575                         /* about to prune this ftw and already at home */
 576                         if(cdrv == 0 && level == 0 && nd)
 577                                 cdrv = -1;
 578                 }
 579
 580                 /* pruning the search tree */
 581                 if(!dirfp || nd || ftw->status == FTW_SKIP)
 582                 {
 583                         if(dirfp)
 584                                 closedir(dirfp), dirfp = 0;
 585                         goto popstack;
 586                 }
 587
 588                 /* FTW_D or FTW_DNX, about to read children */
 589                 if(cdrv == 0)
 590                 {
 591                         if((cdrv = chdir(name)) < 0)
 592                                 (void) pathcd(Home,NiL);
 593                         curdir = cdrv < 0 ? 0 : ftw;
 594                 }
 595                 nostat = (children > 1 || ftw->info == FTW_DNX);
 596                 cpname = ((cdrv && !nostat) || (!children && !comparf));
 597                 dotdot = 0;
 598                 endbase = base+n_base;
 599                 if(endbase[-1] != '/')
 600                         *endbase++ = '/';
 601
 602                 while(dir = readdir(dirfp))
 603                 {
 604                         name = dir->d_name;
 605                         nd = 0;
 606                         if(name[0] == '.')
 607                         {
 608                                 if(name[1] == '\0')
 609                                         nd = 1;
 610                                 else if(name[1] == '.' && name[2] == '\0')
 611                                         nd = 2;
 612                         }
 613                         if(!children && nd > 0)
 614                                 continue;
 615
 616                         /* make a new entry */
 617                         fnrv = -1;
 618 #if _mem_d_namlen_dirent
 619                         i = dir->d_namlen;
 620 #else
 621                         i = strlen(dir->d_name);
 622 #endif
 623                         if(!(f = newFtw(name,i)))
 624                                 goto done;
 625                         f->parent = ftw;
 626                         f->level = level+1;
 627                         sb = &(f->statb);
 628
 629                         /* check for space */
 630                         if(i >= endbuf-endbase)
 631                         {
 632                                 N_buf = resize(&Home,&endbuf,&path,&base,N_buf,i);
 633                                 if(N_buf < 0)
 634                                         goto done;
 635                                 endbase = base+n_base;
 636                                 if(endbase[-1] != '/')
 637                                         ++endbase;
 638                         }
 639                         if(cpname)
 640                         {
 641                                 memcpy(endbase,name,i+1);
 642                                 if(cdrv)
 643                                         name = path;
 644                         }
 645
 646                         if(nd == 1)
 647                         {
 648                                 f->info = FTW_D;
 649                                 memcpy(sb,&(ftw->statb),sizeof(struct stat));
 650                         }
 651                         else if(nostat || (*statf)(name,sb))
 652                         {
 653                                 f->info = FTW_NS;
 654 #if _mem_d_fileno_dirent || _mem_d_ino_dirent
 655 #if !_mem_d_fileno_dirent
 656 #define d_fileno        d_ino
 657 #endif
 658                                 sb->st_ino = dir->d_fileno;
 659 #else
 660                                 sb->st_ino = 0;
 661 #endif
 662                         }
 663                         else    f->info = TYPE(sb->st_mode);
 664
 665                         if(nd)
 666                         {       /* don't recurse on . and .. */
 667                                 f->status = FTW_SKIP;
 668                                 if(nd == 2 && f->info != FTW_NS)
 669                                         dotdot = f;
 670                         }
 671
 672                         if(comparf) /* object ordering */
 673                                 root = search(f,root,comparf,1);
 674                         else if(children || f->info == FTW_D || f->info == FTW_SL)
 675                                 top ? (bot->link = f, bot = f) : (top = bot = f);
 676                         else
 677                         {       /* terminal node */
 678                                 f->status = STATUS(cdrv);
 679                                 f->path = PATH(path,1);
 680                                 f->pathlen = endbase - f->path + f->namelen;
 681                                 fnrv = (*userf)(f);
 682                                 freeFtw(f);
 683                                 if(fnrv)
 684                                         goto done;
 685                         }
 686                 }
 687
 688                 /* done with directory reading */
 689                 closedir(dirfp), dirfp = 0;
 690
 691                 if(root)
 692                         getlist(&top,&bot,root);
 693
 694                 /* delay preorder with the children list */
 695                 if(children)
 696                 {       /* try moving back to parent dir */
 697                         base[n_base] = '\0';
 698                         if(cdrv <= 0)
 699                         {
 700                                 f = ftw->parent;
 701                                 if(cdrv < 0 || curdir != ftw || !dotdot ||
 702                                    !SAME(f->statb,dotdot->statb) ||
 703                                    (cdrv = chdir("..")) < 0)
 704                                         cdrv = setpdir(Home,path,base);
 705                                 curdir = cdrv ? 0 : f;
 706                         }
 707
 708                         ftw->link = top;
 709                         ftw->path = PATH(path,level);
 710                         ftw->pathlen = (base - ftw->path) + ftw->namelen;
 711                         ftw->status = STATUS(cdrv);
 712                         fnrv = (*userf)(ftw);
 713                         ftw->link = link;
 714                         if(fnrv)
 715                                 goto done;
 716
 717                         /* chdir down again */
 718                         nd = (ftw->status == FTW_SKIP);
 719                         if(!nd && cdrv == 0)
 720                         {
 721                                 if((cdrv = chdir(base)) < 0)
 722                                         (void) pathcd(Home,NiL);
 723                                 curdir = cdrv ? 0 : ftw;
 724                         }
 725
 726                         /* prune */
 727                         if(base[n_base-1] != '/')
 728                                 base[n_base] = '/';
 729                         for(bot = 0, f = top; f; )
 730                         {
 731                                 if(nd || f->status == FTW_SKIP)
 732                                 {
 733                                         if(bot)
 734                                                 bot->link = f->link;
 735                                         else    top = f->link;
 736                                         freeFtw(f);
 737                                         f = bot ? bot->link : top;
 738                                         continue;
 739                                 }
 740
 741                                 if(children > 1 && ftw->info != FTW_DNX)
 742                                 {       /* now read stat buffer */
 743                                         sb = &(f->statb);
 744                                         if(f->status == FTW_STAT)
 745                                                 f->info = TYPE(sb->st_mode);
 746                                         else
 747                                         {
 748                                                 name = f->name;
 749                                                 if(cdrv)
 750                                                 {
 751                                                         memcpy(endbase,
 752                                                                 name,f->namelen+1);
 753                                                         name = path;
 754                                                 }
 755                                                 if((*statf)(name,sb) == 0)
 756                                                         f->info = TYPE(sb->st_mode);
 757                                         }
 758                                 }
 759
 760                                 /* normal continue */
 761                                 bot = f, f = f->link;
 762                         }
 763                 }
 764
 765                 base[n_base] = '\0';
 766                 if(top)
 767                         bot->link = todo, todo = top, top = 0;
 768
 769                 /* pop objects completely processed */
 770         popstack:
 771                 nd = 0; /* count number of ".." */
 772                 while(todo && ftw == todo)
 773                 {
 774                         f = ftw->parent;
 775                         if(ftw->info & FTW_DNX)
 776                         {
 777                                 if(curdir == ftw)       /* ASSERT(cdrv == 0) */
 778                                 {
 779                                         nd += 1;
 780                                         curdir = f;
 781                                 }
 782
 783                                 /* perform post-order processing */
 784                                 if(postorder &&
 785                                    ftw->status != FTW_SKIP && ftw->status != FTW_NOPOST)
 786                                 {       /* move to parent dir */
 787                                         if(nd > 0)
 788                                         {
 789                                                 cdrv = popdirs(nd,curdir);
 790                                                 nd = 0;
 791                                         }
 792                                         if(cdrv < 0)
 793                                                 cdrv = setpdir(Home,path,base);
 794                                         curdir = cdrv ? 0 : f;
 795
 796                                         ftw->info = FTW_DP;
 797                                         ftw->path = PATH(path,ftw->level);
 798                                         ftw->pathlen = (base - ftw->path) + ftw->namelen;
 799                                         ftw->status = STATUS(cdrv);
 800                                         link = ftw->link;
 801                                         ftw->link = 0;
 802                                         fnrv = (*userf)(ftw);
 803                                         ftw->link = link;
 804                                         if(fnrv)
 805                                                 goto done;
 806                                         if(ftw->status == FTW_AGAIN)
 807                                                 ftw->info = FTW_D;
 808                                 }
 809
 810                                 /* delete from dev/ino tree */
 811                                 if(diroot != ftw)
 812                                         diroot = search(ftw,diroot,statcmp,0);
 813                                 diroot = deleteroot(diroot);
 814                         }
 815
 816                         /* reset base */
 817                         if(base > path+f->namelen)
 818                                 --base;
 819                         *base = '\0';
 820                         base -= f->namelen;
 821
 822                         /* delete from top of stack */
 823                         if(ftw->status != FTW_AGAIN)
 824                         {
 825                                 todo = todo->link;
 826                                 freeFtw(ftw);
 827                         }
 828                         ftw = f;
 829                 }
 830
 831                 /* reset current directory */
 832                 if(nd > 0 && popdirs(nd,curdir) < 0)
 833                 {
 834                         (void) pathcd(Home,NiL);
 835                         curdir = 0;
 836                         cdrv = -1;
 837                 }
 838
 839                 if(todo)
 840                 {
 841                         if(*base)
 842                                 base += ftw->namelen;
 843                         if(*(base-1) != '/')
 844                                 *base++ = '/';
 845                         *base = '\0';
 846                 }
 847         }
 848
 849         /* normal ending */
 850         fnrv = 0;
 851
 852 done:
 853         if(dirfp)
 854                 closedir(dirfp);
 855         if(cdrv == 0)
 856                 (void) pathcd(Home,NiL);
 857         if(top)
 858                 bot->link = todo, todo = top;
 859         return freeAll(todo,fnrv);
 860 }