home *** CD-ROM | disk | FTP | other *** search
/ ftp.freefriends.org / ftp.freefriends.org.tar / ftp.freefriends.org / arnold / Source / mush.rstevens.tar.gz / mush.tar / glob.c < prev    next >
C/C++ Source or Header  |  1994-07-09  |  20KB  |  817 lines
  1. #include "mush.h"
  2. #include "glob.h"
  3.  
  4. /*
  5.  * Buried somewhere in here is the skeleton of a pattern matcher posted
  6.  * by koblas@mips.COM (David Koblas).  It has been hacked almost beyond
  7.  * recognition to handle more complex patterns, and directory search has
  8.  * been added (patterns are split at '/' characters when file globbing).
  9.  */
  10.  
  11. #ifdef TEST    /* Define TEST to build a stand-alone file globbing program */
  12.  
  13. extern char *malloc(), *realloc();
  14.  
  15. #define getpath(x,y) (*(y) = 0, (x))
  16. #define Access access
  17. #define Strcpy(x,y) (strcpy(x,y), strlen(x))
  18. #define savestr(x)  (strcpy(malloc(strlen(x)+1),x))
  19. #ifndef max
  20. #define max(x,y) ((x) > (y) ? (x) : (y))
  21. #endif /* max */
  22. #ifndef min
  23. #define min(x,y) ((x) > (y) ? (y) : (x))
  24. #endif /* min */
  25. #define xfree free
  26. #undef wprint
  27. #define wprint printf
  28. #define debug 0
  29. #undef sprintf
  30.  
  31. #define TESTGLOB(str1,str2) \
  32.     printf("%s %s = %s\n",str1,str2,glob(str1,str2)?"TRUE":"FALSE")
  33.  
  34. main(argc, argv)
  35. int argc;
  36. char **argv;
  37. {
  38.     char **e;
  39.     int f;
  40.  
  41.     if (argc > 1)
  42.     while (*++argv) {
  43.         (void) printf("%s -->\n", *argv);
  44.         if (f = filexp(*argv, &e)) {
  45.         columnate(f, e, 0);
  46.         }
  47.     }
  48. #ifdef TEST2    /* Define TEST2 to automatically run these test cases */
  49.     TESTGLOB("abcdefg", "abcdefg");
  50.     TESTGLOB("abcdefg", "a?cd?fg");
  51.     TESTGLOB("abcdefg", "ab[cde]defg");
  52.     TESTGLOB("abcdefg", "ab[a-z]defg");
  53.     TESTGLOB("abcdefg", "ab[a-z]defg");
  54.     TESTGLOB("ab]defg", "ab[a]c]defg");
  55.     TESTGLOB("ab]defg", "ab[a\\]c]defg");
  56.     TESTGLOB("abcdefg", "ab*fg");
  57.     TESTGLOB("./bc/def/gh/ij", "*de*");
  58.     TESTGLOB("./der/den/deq/der/", "*deq*");
  59.     TESTGLOB("./bc/def/gh/ij", "*ij");
  60.     TESTGLOB("./ij", ".?ij");
  61.     TESTGLOB("./bc/def/gh/ij", "./*");
  62.     TESTGLOB("abcdef", "*def");
  63.     TESTGLOB("abcdef", "*abcdef");
  64.     TESTGLOB("abcdef", "abc*");
  65.     TESTGLOB("abcdef", "abcdef*");
  66.     TESTGLOB("abcdef", "*?*{xxx,,yy}");
  67.     TESTGLOB("abcdef", "abcde{f}");
  68.     TESTGLOB("abcdef", "abcdef{xxx,,yyy}");
  69.     TESTGLOB("abcdef", "abc{def,qwrx}");
  70.     TESTGLOB("abcdef", "abc{ab,def,qwrx}");
  71.     TESTGLOB("abcdef", "{naqrwer,fuwnwer,as,abc,a}{ab,def,qwrx}");
  72.     TESTGLOB("abcdef", "{naqrwer,*,as,abc,a}{ab,def,qwrx}");
  73.     TESTGLOB("abcdef", "{{a*,b*},as,a}{ab,def,qwrx}");
  74.     TESTGLOB("abcdef", "{{c*,b*},as,a}{ab,def,qwrx}");
  75.     TESTGLOB("abcdef", "{{c*,?b*},as,a}{ab,def,qwrx}");
  76.     TESTGLOB("abcdef", "{naqrwer,fuwnwer,as,abc,a}{ab,d*f,qwrx}");
  77. #endif /* TEST2 */
  78. }
  79.  
  80. char *
  81. any(s1, s2)
  82. register char *s1, *s2;
  83. {
  84.     register char *p;
  85.     if (!s1 || !*s1 || !s2 || !*s2)
  86.     return 0;
  87.     for( ; *s1; s1++) {
  88.     for(p = s2; *p; p++)
  89.         if (*p == *s1)
  90.         return s1;
  91.     }
  92.     return 0;
  93. }
  94.  
  95. #endif /* TEST */
  96.  
  97. /*
  98.  * Make a string into a one-element vector
  99.  */
  100. char **
  101. unitv(s)
  102. char *s;
  103. {
  104.     char **v;
  105.  
  106.     if (v = (char **)malloc((unsigned)(2 * sizeof(char *)))) {
  107.     v[0] = savestr(s);
  108.     v[1] = NULL;
  109.     }
  110.     return v;
  111. }
  112.  
  113. /*
  114.  * Append one vector to another
  115.  */
  116. catv(s1, v1, s2, v2)
  117. int s1, s2;
  118. char ***v1, **v2;
  119. {
  120.     int i;
  121.  
  122.     if (s1 < 0 || !v1)
  123.     return -1;
  124.     if (s2 < 0 || !v2)
  125.     return s1;
  126.  
  127.     /* realloc(NULL, size) should be legal, but Sun doesn't support it. */
  128.     if (*v1)
  129.         *v1 = (char **)realloc(*v1,(unsigned)((s1+s2+1) * sizeof(char **)));
  130.     else
  131.         *v1 = (char **)malloc((unsigned)((s1+s2+1) * sizeof(char **)));
  132.  
  133.     if (*v1) {
  134.     for (i = 0; i < s2 && v2[i]; i++)
  135.         (*v1)[s1 + i] = v2[i]; 
  136.     (*v1)[s1 + i] = NULL;
  137.     xfree(v2);
  138.     return s1 + i;
  139.     }
  140.     return -1;
  141. }
  142.  
  143. /*
  144.  * A duplicate-eliminating comparison for sorting.  It treats an empty
  145.  * string as greater than any other string, and forces empty one of any
  146.  * pair of of equal strings.  Two passes are sufficient to move the empty
  147.  * strings to the end where they can be deleted by the calling function.
  148.  *
  149.  * This is NOT compatible with the ANSI C qsort(), which requires that the
  150.  * comparison function will not modify its arguments!
  151.  */
  152. uniqcmp(p1, p2)
  153. char **p1, **p2;
  154. {
  155.     int cmp;
  156.  
  157.     if (**p1 && !**p2)
  158.     return -1;
  159.     if (**p2 && !**p1)
  160.     return 1;
  161.     if (cmp = strcmp(*p1, *p2))
  162.     return cmp;
  163.     **p2 = 0;
  164.     return -1;
  165. }
  166.  
  167. /*
  168.  * Expand a pattern into a list of file names.  Returns the number of
  169.  * matches.  As in csh, names generated from pattern sets are returned
  170.  * even if there are no actual matches.
  171.  */
  172. filexp(pat, exp)
  173. char *pat, ***exp;
  174. {
  175.     char **t1, **t2;
  176.     int n, new, cnt;
  177.  
  178.     if (!exp)
  179.     return -1;
  180.     if (!pat || !*pat)
  181.     return 0;
  182.  
  183.     if ((n = sxp(pat, &t1)) > 0)
  184.     cnt = 0;
  185.     else
  186.     return n;
  187.     *exp = DUBL_NULL;
  188.     while (n--)
  189.     if ((new = fxp(t1[n], &t2)) > 0 || new++ == 0 && t2)
  190.         cnt = catv(cnt, exp, new, t2);
  191.     if (cnt > 1) {
  192.     /* Two sort passes to eliminate duplicates -- see uniqcmp() */
  193.     qsort((char *)*exp, cnt, sizeof(char *), uniqcmp);
  194.     qsort((char *)*exp, cnt, sizeof(char *), uniqcmp);
  195.     while (!(*exp)[cnt - 1][0]) {
  196.         xfree((*exp)[--cnt]);
  197.         (*exp)[cnt] = NULL;
  198.     }
  199.     }
  200.     return cnt;
  201. }
  202.  
  203. /*
  204.  * Expand a filename with globbing chars into a list of matching filenames.
  205.  * Pattern set notatation which crosses directories is not handled, e.g.
  206.  * "fi{le/exp,nger/h}and" will NOT expand to "file/expand finger/hand".
  207.  * Such patterns must be pre-expanded by sxp() before calling fxp().
  208.  *
  209.  * The list of expansions is placed in *exp, and the number of matches
  210.  * is returned, or -1 on an error.
  211.  */
  212. fxp(name, exp)
  213. char *name, ***exp;
  214. {
  215.     char *p;
  216.     int isdir;
  217.  
  218.     if (!exp)
  219.     return -1;
  220.  
  221.     isdir = 1; /* ignore no such file */
  222.     p = getpath(name, &isdir);
  223.     if (isdir < 0)
  224.     return -1;
  225.     else if (isdir)
  226.     return ((*exp = unitv(p)) ? 1 : -1);
  227.     return pglob(p, 0, exp);
  228. }
  229.  
  230. /*
  231.  * Match all globbings in a path.  Mutually recursive with dglob(), below.
  232.  * The first "skip" characters of the path are not globbed, see dglob().
  233.  *
  234.  * Returns the number of matches, or -1 on an error.  *exp is set to the
  235.  * list of matches.
  236.  *
  237.  * If the path has no metachars, it is returned in *exp whether it matches
  238.  * a real file or not.  This allows patterns built by sxp() to be recognized
  239.  * and returned even when there are no matches (ala csh generation of names
  240.  * from pattern sets).  pglob() still returns zero in this case.
  241.  */
  242. pglob(path, skip, exp)
  243. char *path, ***exp;
  244. int skip;
  245. {
  246.     char *t, *t2;
  247.     int ret = 0;
  248.  
  249.     if (!path || !exp || skip < 0)
  250.     return -1;
  251.     *exp = DUBL_NULL; /* Must be null in case of zero matches and no sets */
  252.  
  253.     for (t = t2 = path + skip; (t2 = any(t2, META)) && *t2 == '/'; t = t2++)
  254.     ;
  255.     if (!t2) {
  256.     ret = ((*exp = unitv(path)) ? 1 : -1);
  257.     if (ret > 0 && Access(path, F_OK) < 0)
  258.         ret = 0;
  259.     } else {
  260.     if (t2 = index(t + 1, '/'))
  261.         *t2++ = 0;
  262.     if (*t == '/') {
  263.         *t++ = 0;
  264.         if (!*path)
  265.         ret = dglob("/", t, t2, exp);
  266.         else
  267.         ret = dglob(path, t, t2, exp);
  268.     } else {
  269.         ret = dglob("", t, t2, exp);
  270.     }
  271.     }
  272.     return ret;
  273. }
  274.  
  275. /*
  276.  * Search a directory (possibly recursively) for glob matches.
  277.  * Argument pat1 is a pattern to be matched in this directory,
  278.  * and pat2 is a pattern to be matched in matched subdirectories.
  279.  *
  280.  * Matches are returned through *exp.
  281.  */
  282. dglob(dir, pat1, pat2, exp)
  283. char *dir, *pat1, *pat2, ***exp;
  284. {
  285.     DIR *dirp;
  286.     struct dirent *dp;
  287.     char *b, *d, buf[MAXPATHLEN], **tmp;
  288.     int n, ret = 0, skip;
  289.  
  290.     if (!dir || !exp)
  291.     return -1;
  292.     d = (*dir ? dir : ".");
  293.     if (!(dirp = opendir(d)))
  294.     return -1;
  295.     b = buf + Strcpy(buf, dir);
  296.     if (b > buf && *(b - 1) != '/')
  297.     *b++ = '/';
  298.     skip = b - buf; /* We know this much matches, don't glob it again */
  299.     while (ret >= 0 && (dp = readdir(dirp))) {
  300.     if (fglob(dp->d_name, pat1)) {
  301.         if (pat2) {
  302.         (void) sprintf(b, "%s/%s", dp->d_name, pat2);
  303.         n = pglob(buf, skip, &tmp);
  304.         ret = catv(ret, exp, n, tmp);
  305.         } else {
  306.         (void) strcpy(b, dp->d_name);
  307.         ret = catv(ret, exp, 1, unitv(buf));
  308.         }
  309.     }
  310.     }
  311.     closedir(dirp);
  312.     return ret;
  313. }
  314.  
  315. /*
  316.  * Match file names.  This means that metachars do not match leading ".".
  317.  */
  318. fglob(str, pat)
  319. char *str, *pat;
  320. {
  321.     if (!str || !pat || *str == '.' && *pat != '.')
  322.     return FALSE;
  323.     else
  324.     return glob(str, pat);
  325. }
  326.  
  327. /*
  328.  * Match two concatenated patterns.  Mainly for use by sglob().
  329.  */
  330. static
  331. glob2(str, pat1, pat2)
  332. char *str, *pat1, *pat2;
  333. {
  334.     char buf[MAXPATHLEN];
  335.  
  336.     if (!str || !pat1 && !pat2)
  337.     return FALSE;
  338.     (void) sprintf(buf, "%s%s", pat1? pat1 : "", pat2? pat2 : "");
  339.     return glob(str, buf);
  340. }
  341.  
  342. /*
  343.  * Match a pattern set {s1,s2,...} followed by any other pattern.
  344.  * Pattern sets and other patterns may nest arbitrarily.
  345.  *
  346.  * If "mat" is not a null pointer, a vector of possible expansions
  347.  * is generated and placed in *mat; otherwise, the expansions are
  348.  * matched against str and a truth value is returned ("/" is NOT
  349.  * treated as a directory separator in this case).  NOTE: The vector
  350.  * of expansions may still contain nested pattern sets, which must
  351.  * be expanded separately.  See sxp().
  352.  *
  353.  * Currently allows at most 256 alternatives per set.  Enough? :-)
  354.  */
  355. static
  356. sglob(str, pato, mat)
  357. char *str, *pato, ***mat;
  358. {
  359.     char *p, *newpat[256], *oldpat[256], buf[MAXPATHLEN], *b = buf;
  360.     int copy = 1, nest = 0, i = 0, ret = 0;
  361.     char *pat,*pat2;
  362.  
  363.     if (!pato || !str)
  364.     return FALSE;
  365.     pat2 = savestr(pato);
  366.     if (!pat2)
  367.     return FALSE;
  368.     pat = pat2;
  369.     while (*pat) {
  370.     if (copy)
  371.         if (*pat != '{') /*}*/ {
  372.         if (*pat == '\\' && pat[1])
  373.             *b++ = *pat++;
  374.         *b++ = *pat++;
  375.         continue;
  376.         } else {
  377.         copy = 0;
  378.         pat++;
  379.         }
  380.     p = pat;
  381.     while (*pat && (nest || *pat != ',' && /*{*/ *pat != '}')) {
  382.         if (*pat == '\\')
  383.         pat++;
  384.         else if (*pat == '{')
  385.         nest++;
  386.         else if (*pat == '}')
  387.         nest--;
  388.         if (*pat)
  389.         pat++;
  390.     }
  391.     if (*pat) {
  392.         oldpat[i] = pat;
  393.         newpat[i++] = p;
  394.         if (*pat != ',') {
  395.         *pat++ = 0;
  396.         break;
  397.         } else
  398.         *pat++ = 0;
  399.     }
  400.     }
  401.     oldpat[i] = NULL;
  402.     if (i > 0 && mat) {
  403.     *mat = (char **)malloc((unsigned)((i + 1) * sizeof(char *)));
  404.     if (*mat)
  405.         (*mat)[i] = NULL;
  406.     else{
  407.         xfree(pat2);
  408.         return -1;
  409.       }
  410.     ret = i;
  411.     }
  412.     while (!mat && i-- > 0)
  413.     if (ret = glob2(str, newpat[i], pat))
  414.         break;
  415.     for (i = 0; oldpat[i]; i++) {
  416.     if (mat && *mat) {
  417.         (void) sprintf(b, "%s%s", newpat[i], pat);
  418.         (*mat)[i] = savestr(buf);
  419.     }
  420.     if (oldpat[i + 1])
  421.         oldpat[i][0] = ',';
  422.     else
  423.         oldpat[i][0] = /*{*/ '}';
  424.     }
  425.     if (ret == 0 && b > buf && mat) {
  426.     *b = 0;
  427.     ret = ((*mat = unitv(buf)) ? 1 : -1);
  428.     }
  429.     xfree(pat2);
  430.     return ret;
  431. }
  432.  
  433. /*
  434.  * The basic globbing matcher.
  435.  *
  436.  * "*"           = match 0 or more occurances of anything
  437.  * "[abc]"       = match any of "abc" (ranges supported)
  438.  * "{xx,yy,...}" = match any of "xx", "yy", ... where
  439.  *                 "xx", "yy" can be any pattern or empty
  440.  * "?"           = match any character
  441.  */
  442. glob(str, pat)
  443. char *str, *pat;
  444. {
  445.     int done = FALSE, ret = FALSE;
  446.  
  447.     if (!str || !pat)
  448.     return FALSE;
  449.  
  450.     while (*pat && !done && (*str || (*pat == '{' || *pat == '*'))) /*}*/ {
  451.     /*
  452.      * First look for a literal match, stepping over backslashes
  453.      * in the pattern to match against the "protected" character.
  454.      * Ordering and precendence are important in this expression!
  455.      */
  456.     if (*pat == '\\' && *str == *++pat || *str == *pat) {
  457.         str++;
  458.         pat++;
  459.     } else switch (*pat++) {
  460.         case '*':    /* Match any string */
  461.         if (!*pat) {
  462.             while (*str)
  463.             str++;
  464.             break;
  465.         }
  466.         /*
  467.          * Try the rest of the glob against every
  468.          * possible suffix of the string.  A bit
  469.          * inefficient in cases that eventually fail.
  470.          */
  471.         while (*str && !(ret = glob(str++, pat)))
  472.             ;
  473.         return ret;
  474.         break;
  475.         case '[':    /* Match a set */
  476.         repeat:
  477.         /* If we've hit the end of the set, give up. */
  478.         if (!*pat || *pat == ']' || *pat == '\\' && !*++pat) {
  479.             done = TRUE;
  480.             break;
  481.         }
  482.         /* Check for a range. */
  483.         if (*(pat + 1) == '-') {
  484.             char c = *pat++;
  485.             /* We don't handle open-ended ranges. */
  486.             if (*++pat == ']' || *pat == '\\' && !*++pat) {
  487.             done = TRUE;
  488.             break;
  489.             }
  490.             if (*str < c || *str > *pat) {
  491.             pat++;
  492.             goto repeat;
  493.             }
  494.         } else if (*pat != *str) {
  495.             pat++;
  496.             goto repeat;
  497.         }
  498.         /*
  499.          * We matched either the range or a literal member of
  500.          * the set.  Skip to the end of the set.
  501.          */
  502.         pat++;
  503.         while (*pat && *pat != ']')
  504.             if (*pat++ == '\\' && *pat)
  505.             pat++;
  506.         /*
  507.          * If no pattern remains, the set was never closed,
  508.          * so don't increment.  This will cause a FALSE return.
  509.          */
  510.         if (*pat) {
  511.             pat++;
  512.             str++;
  513.         }
  514.         break;
  515.         case '?':    /* Match any one character */
  516.         str++;
  517.         break;
  518.         case '{':    /* } Match any of a set of patterns */
  519.         return sglob(str, pat - 1, TRPL_NULL);
  520.         break;
  521.         default:
  522.         done = TRUE;
  523.     }
  524.     }
  525.     while (*pat == '*')
  526.     pat++;
  527.     return ((*str == '\0') && (*pat == '\0'));
  528. }
  529.  
  530. /*
  531.  * Pre-expand pattern set notations so sets containing "/" separators
  532.  * can be globbed successfully.  Returns the number of expansions.
  533.  */
  534. sxp(pat, exp)
  535. char *pat, ***exp;
  536. {
  537.     char **t1 = DUBL_NULL, **t2;
  538.     int n, new, cnt = 0;
  539.  
  540.     if ((n = sglob(NULL, pat, &t1)) < 2) {
  541.     *exp = t1;
  542.     return n;
  543.     }
  544.     *exp = DUBL_NULL;
  545.     while (n-- && cnt >= 0) {
  546.     new = sxp(t1[n], &t2);
  547.     cnt = catv(cnt, exp, new, t2);
  548.     }
  549.     xfree(t1);
  550.     return cnt;
  551. }
  552.  
  553. /*
  554.  * Generate the "glob difference" of two vectors (*argvp and patv).
  555.  * The "glob difference" means to remove all strings from argv that
  556.  * match any of the glob patterns in patv.
  557.  *
  558.  * Returns the number of strings remaining in *argvp.  The strings "removed"
  559.  * from argv are actually left at the end of *argvp, so they can still be
  560.  * accessed; their number will of course be argc - (returned value).
  561.  */
  562. gdiffv(argc, argvp, patc, patv)
  563. int argc, patc;
  564. char ***argvp, **patv;
  565. {
  566.     char **argv, *t;
  567.     int ac, pc, oldac = argc;
  568.  
  569.     if (argc < 1 || patc < 1 || !patv || !*patv)
  570.     return argc;
  571.     if (!argvp || !(argv = *argvp) || !*argv)
  572.     return -1;
  573.     for (ac = 0; ac < argc && argv[ac]; ac++) {
  574.     for (pc = 0; ac < argc && pc < patc && patv[pc]; pc++) {
  575.         /*
  576.          * We shouldn't cross '/' characters, so test
  577.          * only the "tail" of each element of argv.
  578.          */
  579.         if (!(t = rindex(argv[ac], '/')))
  580.             t = argv[ac];
  581.         if (glob(t, patv[pc])) {
  582.         /* Move matches to the end and reduce argc */
  583.         t = argv[ac];
  584.         argv[ac] = argv[--argc];
  585.         argv[argc] = t;
  586.         /* Start patterns over on the new string */
  587.         pc = -1; /* It'll be incremented to 0 */
  588.         }
  589.     }
  590.     }
  591.     /*
  592.      * Sort the two parts of the argv.  uniqcmp() works here only if
  593.      * there already are no duplicates, but we assume that for now.
  594.      */
  595.     if (argc)
  596.     qsort((char *)argv, argc, sizeof(char *), uniqcmp);
  597.     if (oldac > argc)
  598.     qsort((char *)&argv[argc], oldac - argc, sizeof(char *), uniqcmp);
  599.     return argc;
  600. }
  601.  
  602. /*
  603.  * Generate the longest common prefix from all strings in a vector
  604.  * If "skip" is nonzero, that many chars are assumed to be in common
  605.  * and are not tested.  WARNING: skip must be <= than the length of
  606.  * the shortest string in the vector!  Safest to call with skip = 0.
  607.  *
  608.  * Returns the length of the longest common prefix.
  609.  */
  610. lcprefix(vec, skip)
  611. char **vec;
  612. int skip;
  613. {
  614.     char c, **v;
  615.     int done = FALSE;
  616.  
  617.     if (!vec || !*vec || skip < 0)
  618.     return 0;
  619.     do {
  620.     for (v = vec + 1, c = vec[0][skip]; c && *v; v++)
  621.         if (v[0][skip] != c) {
  622.         done = TRUE;
  623.         break;
  624.         }
  625.     } while (!done && c && ++skip);
  626.     return skip;
  627. }
  628.  
  629. #define MAXCOLS 8    /* Max number of columns of words to make */
  630. #define MINWIDTH 10    /* Minimum width of each column of words */
  631. #ifdef CURSES
  632. #define MAXWIDTH (iscurses? COLS : 80)
  633. #else /* CURSES */
  634. #define MAXWIDTH 80    /* Maximum width of all columns */
  635. #endif /* CURSES */
  636.  
  637. /*
  638.  * Print a vector in columns
  639.  *
  640.  * If "skip" is nonzero, that many chars are assumed to be in common
  641.  * and are not printed.  WARNING: skip must be <= than the length of
  642.  * the shortest string in the vector!  Safest to call with skip = 0.
  643.  */
  644. columnate(argc, argv, skip)
  645. int argc;
  646. char **argv;
  647. int skip;
  648. {
  649.     int colstep, colwidth[MAXCOLS + 1];
  650.     int maxcols = min(argc, MAXCOLS);
  651.     int minwidth, maxwidth, *widths;
  652.     int maxword = 0, n, c;
  653.  
  654.     if (argc <= 0 || !argv || !*argv)
  655.     return -1;
  656.     if (!(widths = (int *)malloc((unsigned)((argc + 1) * sizeof(int)))))
  657.     return -1;
  658.  
  659.     /*
  660.      * Compute the widths of all words in the vector, and
  661.      * remember the maximum width and which word had it.
  662.      * Also remember the minimum width.
  663.      */
  664.     for (minwidth = MAXWIDTH, maxwidth = n = 0; n < argc; n++) {
  665.     widths[n] = max(strlen(argv[n] + skip) + 2, MINWIDTH);
  666.     if (widths[n] > MAXWIDTH - MINWIDTH)
  667.         break;
  668.     if (widths[n] > maxwidth) {
  669.         maxwidth = widths[n];
  670.         maxword = n;
  671.     } 
  672.     if (widths[n] < minwidth)
  673.         minwidth = widths[n];
  674.     }
  675.  
  676.     for (; maxcols > 0; maxcols--) {
  677.     if (argc % maxcols)
  678.         colstep = argc / maxcols + 1;
  679.     else
  680.         colstep = argc / maxcols;
  681.     colwidth[MAXCOLS] = 0;
  682.     for (c = 0; c < maxcols; c++) {
  683.         colwidth[c] = 0;
  684.         for (n = c * colstep; n < (c + 1) * colstep && n < argc; n++)
  685.         colwidth[c] = max(colwidth[c], widths[n]);
  686.         colwidth[MAXCOLS] += colwidth[c];
  687.     }
  688.     if (colwidth[MAXCOLS] <= MAXWIDTH)
  689.         break;
  690.     }
  691.     xfree(widths);
  692.  
  693.     if (maxcols < 2 && minwidth <= MAXWIDTH / 2) {
  694.     /*
  695.      * The maxword fills too much screen, so redo everything
  696.      * above it, print maxword, then do everything below it.
  697.      */
  698.     if (maxword > 0 && columnate(maxword, argv, skip) < 0)
  699.         return -1;
  700.     wprint("%s\n", argv[maxword] + skip);
  701.     if (argc - maxword < 2)
  702.         return 0;
  703.     return columnate(argc - maxword - 1, &argv[maxword + 1], skip);
  704.     }
  705.  
  706.     for (n = 0; n < colstep; n++) {
  707.     for (c = 0; c < maxcols && n + c * colstep < argc - colstep; c++)
  708.         wprint("%-*.*s", colwidth[c], colwidth[c],
  709.                         argv[n + c * colstep] + skip);
  710.     wprint("%s\n", argv[n + c * colstep] + skip);
  711.     }
  712.  
  713.     return 0;
  714. }
  715.  
  716. #ifndef DIRECTORY
  717.  
  718. #undef NULL
  719. #define NULL 0
  720.  
  721. /*
  722.  *  4.2BSD directory access emulation for non-4.2 systems.
  723.  *  Based upon routines in appendix D of Portable C and Unix System
  724.  *  Programming by J. E. Lapin (Rabbit Software).
  725.  *
  726.  *  No responsibility is taken for any error in accuracies inherent
  727.  *  either to the comments or the code of this program, but if
  728.  *  reported to me then an attempt will be made to fix them.
  729.  */
  730.  
  731. /*  Support for Berkeley directory reading routines on a V7/SysV file
  732.  *  system.
  733.  */
  734.  
  735. /*  Open a directory. */
  736.  
  737. DIR *
  738. opendir(name)
  739. char *name ;
  740. {
  741.   register DIR *dirp ;
  742.   register int fd ;
  743.  
  744.   if ((fd = open(name, 0)) == -1) return NULL ;
  745.   if ((dirp = (DIR *) malloc(sizeof(DIR))) == NULL)
  746.     {
  747.       close(fd) ;
  748.       return NULL ;
  749.     }
  750.   dirp->dd_fd = fd ;
  751.   dirp->dd_loc = 0 ;
  752.   return dirp ;
  753. }
  754.  
  755.  
  756. /*  Read an old style directory entry and present it as a new one. */
  757.  
  758. #define  ODIRSIZ  14
  759.  
  760. struct olddirent
  761. {
  762.   short  od_ino ;
  763.   char   od_name[ODIRSIZ] ;
  764. } ;
  765.  
  766.  
  767. /*  Get next entry in a directory. */
  768.  
  769. struct dirent *
  770. readdir(dirp)
  771. register DIR *dirp ;
  772. {
  773.   register struct olddirent *dp ;
  774.   static struct dirent dir ;
  775.  
  776.   for (;;)
  777.     {
  778.       if (dirp->dd_loc == 0)
  779.         {
  780.           dirp->dd_size = read(dirp->dd_fd, dirp->dd_buf, DIRBLKSIZ) ;
  781.           if (dirp->dd_size <= 0) return NULL ;
  782.         }
  783.       if (dirp->dd_loc >= dirp->dd_size)
  784.         {
  785.           dirp->dd_loc = 0 ;
  786.           continue ;
  787.         }
  788.  
  789.       dp = (struct olddirent *)(dirp->dd_buf + dirp->dd_loc) ;
  790.       dirp->dd_loc += sizeof(struct olddirent) ;
  791.  
  792.       if (dp->od_ino == 0) continue ;
  793.  
  794.       dir.d_fileno = dp->od_ino ;
  795.       strncpy(dir.d_name, dp->od_name, ODIRSIZ) ;
  796.       dir.d_name[ODIRSIZ] = '\0' ;       /* Ensure termination. */
  797.       dir.d_namlen = strlen(dir.d_name) ;
  798.       dir.d_reclen = DIRSIZ(&dir) ;
  799.       return(&dir) ;
  800.     }
  801. }
  802.  
  803.  
  804. /*  Close a directory. */
  805.  
  806. void
  807. closedir(dirp)
  808. register DIR *dirp ;
  809. {
  810.   close(dirp->dd_fd) ;
  811.   dirp->dd_fd = -1 ;
  812.   dirp->dd_loc = 0 ;
  813.   xfree(dirp) ;
  814. } 
  815.  
  816. #endif /* DIRECTORY */
  817.