misc/glob.c

   1
   2 /* Copyright (C) 1991,92,93,94,95,96,97,98,99 Free Software Foundation, Inc.
   3
   4    This library is free software; you can redistribute it and/or
   5    modify it under the terms of the GNU Library General Public License as
   6    published by the Free Software Foundation; either version 2 of the
   7    License, or (at your option) any later version.
   8
   9    This library is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12    Library General Public License for more details.
  13
  14    You should have received a copy of the GNU Library General Public
  15    License along with this library; see the file COPYING.LIB.  If not,
  16    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  17    Boston, MA 02111-1307, USA.  */
  18
  19 /* AIX requires this to be the first thing in the file.  */
  20 #if defined _AIX && !defined __GNUC__
  21  #pragma alloca
  22 #endif
  23
  24
  25 # include "system.h"
  26
  27 # include <assert.h>
  28
  29 #define __alloca        alloca
  30 #define __stat          stat
  31 #define NAMLEN(_d)      NLENGTH(_d)
  32
  33 #if (defined POSIX || defined WINDOWS32) && !defined __GNU_LIBRARY__
  34 /* Posix does not require that the d_ino field be present, and some
  35    systems do not provide it. */
  36 # define REAL_DIR_ENTRY(dp) 1
  37 #else
  38 # define REAL_DIR_ENTRY(dp) (dp->d_ino != 0)
  39 #endif /* POSIX */
  40
  41 #include <errno.h>
  42 #ifndef __set_errno
  43 # define __set_errno(val) errno = (val)
  44 #endif
  45
  46 /* Outcomment the following line for production quality code.  */
  47 /* #define NDEBUG 1 */
  48
  49 #define GLOB_INTERFACE_VERSION 1
  50
  51 static inline const char *next_brace_sub __P ((const char *begin));
  52 static int glob_in_dir __P ((const char *pattern, const char *directory,
  53                              int flags,
  54                              int (*errfunc) (const char *, int),
  55                              glob_t *pglob));
  56 static int prefix_array __P ((const char *prefix, char **array, size_t n));
  57 static int collated_compare __P ((const __ptr_t, const __ptr_t));
  58
  59
  60 /* Find the end of the sub-pattern in a brace expression.  We define
  61    this as an inline function if the compiler permits.  */
  62 static inline const char *
  63 next_brace_sub (const char *begin)
  64 {
  65   unsigned int depth = 0;
  66   const char *cp = begin;
  67
  68   while (1)
  69     {
  70       if (depth == 0)
  71         {
  72           if (*cp != ',' && *cp != '}' && *cp != '\0')
  73             {
  74               if (*cp == '{')
  75                 ++depth;
  76               ++cp;
  77               continue;
  78             }
  79         }
  80       else
  81         {
  82           while (*cp != '\0' && (*cp != '}' || depth > 0))
  83             {
  84               if (*cp == '}')
  85                 --depth;
  86               ++cp;
  87             }
  88           if (*cp == '\0')
  89             /* An incorrectly terminated brace expression.  */
  90             return NULL;
  91
  92           continue;
  93         }
  94       break;
  95     }
  96
  97   return cp;
  98 }
  99
 100 static int __glob_pattern_p (const char *pattern, int quote);
 101
 102 /* Do glob searching for PATTERN, placing results in PGLOB.
 103    The bits defined above may be set in FLAGS.
 104    If a directory cannot be opened or read and ERRFUNC is not nil,
 105    it is called with the pathname that caused the error, and the
 106    `errno' value from the failing call; if it returns non-zero
 107    `glob' returns GLOB_ABORTED; if it returns zero, the error is ignored.
 108    If memory cannot be allocated for PGLOB, GLOB_NOSPACE is returned.
 109    Otherwise, `glob' returns zero.  */
 110 int
 111 glob (const char *pattern, int flags,
 112         int (*errfunc) __P ((const char *, int)), glob_t *pglob)
 113 {
 114   const char *filename;
 115   const char *dirname;
 116   size_t dirlen;
 117   int status;
 118   int oldcount;
 119
 120   if (pattern == NULL || pglob == NULL || (flags & ~__GLOB_FLAGS) != 0)
 121     {
 122       __set_errno (EINVAL);
 123       return -1;
 124     }
 125
 126   if (flags & GLOB_BRACE)
 127     {
 128       const char *begin = strchr (pattern, '{');
 129       if (begin != NULL)
 130         {
 131           /* Allocate working buffer large enough for our work.  Note that
 132             we have at least an opening and closing brace.  */
 133           int firstc;
 134           char *alt_start;
 135           const char *p;
 136           const char *next;
 137           const char *rest;
 138           size_t rest_len;
 139 #ifdef __GNUC__
 140           char onealt[strlen (pattern) - 1];
 141 #else
 142           char *onealt = (char *) xmalloc (strlen (pattern) - 1);
 143           if (onealt == NULL)
 144             {
 145               if (!(flags & GLOB_APPEND))
 146                 globfree (pglob);
 147               return GLOB_NOSPACE;
 148             }
 149 #endif
 150
 151           /* We know the prefix for all sub-patterns.  */
 152 #ifdef HAVE_MEMPCPY
 153           alt_start = mempcpy (onealt, pattern, begin - pattern);
 154 #else
 155           memcpy (onealt, pattern, begin - pattern);
 156           alt_start = &onealt[begin - pattern];
 157 #endif
 158
 159           /* Find the first sub-pattern and at the same time find the
 160              rest after the closing brace.  */
 161           next = next_brace_sub (begin + 1);
 162           if (next == NULL)
 163             {
 164               /* It is an illegal expression.  */
 165 #ifndef __GNUC__
 166               free (onealt);
 167 #endif
 168               return glob (pattern, flags & ~GLOB_BRACE, errfunc, pglob);
 169             }
 170
 171           /* Now find the end of the whole brace expression.  */
 172           rest = next;
 173           while (*rest != '}')
 174             {
 175               rest = next_brace_sub (rest + 1);
 176               if (rest == NULL)
 177                 {
 178                   /* It is an illegal expression.  */
 179 #ifndef __GNUC__
 180                   free (onealt);
 181 #endif
 182                   return glob (pattern, flags & ~GLOB_BRACE, errfunc, pglob);
 183                 }
 184             }
 185           /* Please note that we now can be sure the brace expression
 186              is well-formed.  */
 187           rest_len = strlen (++rest) + 1;
 188
 189           /* We have a brace expression.  BEGIN points to the opening {,
 190              NEXT points past the terminator of the first element, and END
 191              points past the final }.  We will accumulate result names from
 192              recursive runs for each brace alternative in the buffer using
 193              GLOB_APPEND.  */
 194
 195           if (!(flags & GLOB_APPEND))
 196             {
 197               /* This call is to set a new vector, so clear out the
 198                  vector so we can append to it.  */
 199               pglob->gl_pathc = 0;
 200               pglob->gl_pathv = NULL;
 201             }
 202           firstc = pglob->gl_pathc;
 203
 204           p = begin + 1;
 205           while (1)
 206             {
 207               int result;
 208
 209               /* Construct the new glob expression.  */
 210 #ifdef HAVE_MEMPCPY
 211               mempcpy (mempcpy (alt_start, p, next - p), rest, rest_len);
 212 #else
 213               memcpy (alt_start, p, next - p);
 214               memcpy (&alt_start[next - p], rest, rest_len);
 215 #endif
 216
 217               result = glob (onealt,
 218                              ((flags & ~(GLOB_NOCHECK|GLOB_NOMAGIC))
 219                               | GLOB_APPEND), errfunc, pglob);
 220
 221               /* If we got an error, return it.  */
 222               if (result && result != GLOB_NOMATCH)
 223                 {
 224 #ifndef __GNUC__
 225                   free (onealt);
 226 #endif
 227                   if (!(flags & GLOB_APPEND))
 228                     globfree (pglob);
 229                   return result;
 230                 }
 231
 232               if (*next == '}')
 233                 /* We saw the last entry.  */
 234                 break;
 235
 236               p = next + 1;
 237               next = next_brace_sub (p);
 238               assert (next != NULL);
 239             }
 240
 241 #ifndef __GNUC__
 242           free (onealt);
 243 #endif
 244
 245           if (pglob->gl_pathc != firstc)
 246             /* We found some entries.  */
 247             return 0;
 248           else if (!(flags & (GLOB_NOCHECK|GLOB_NOMAGIC)))
 249             return GLOB_NOMATCH;
 250         }
 251     }
 252
 253   /* Find the filename.  */
 254   filename = strrchr (pattern, '/');
 255 #if defined __MSDOS__ || defined WINDOWS32
 256   /* The case of "d:pattern".  Since `:' is not allowed in
 257      file names, we can safely assume that wherever it
 258      happens in pattern, it signals the filename part.  This
 259      is so we could some day support patterns like "[a-z]:foo".  */
 260   if (filename == NULL)
 261     filename = strchr (pattern, ':');
 262 #endif /* __MSDOS__ || WINDOWS32 */
 263   if (filename == NULL)
 264     {
 265       /* This can mean two things: a simple name or "~name".  The latter
 266          case is nothing but a notation for a directory.  */
 267       if ((flags & (GLOB_TILDE|GLOB_TILDE_CHECK)) && pattern[0] == '~')
 268         {
 269           dirname = pattern;
 270           dirlen = strlen (pattern);
 271
 272           /* Set FILENAME to NULL as a special flag.  This is ugly but
 273              other solutions would require much more code.  We test for
 274              this special case below.  */
 275           filename = NULL;
 276         }
 277       else
 278         {
 279           filename = pattern;
 280 #ifdef _AMIGA
 281           dirname = "";
 282 #else
 283           dirname = ".";
 284 #endif
 285           dirlen = 0;
 286         }
 287     }
 288   else if (filename == pattern)
 289     {
 290       /* "/pattern".  */
 291       dirname = "/";
 292       dirlen = 1;
 293       ++filename;
 294     }
 295   else
 296     {
 297       char *newp;
 298       dirlen = filename - pattern;
 299 #if defined __MSDOS__ || defined WINDOWS32
 300       if (*filename == ':'
 301           || (filename > pattern + 1 && filename[-1] == ':'))
 302         {
 303           char *drive_spec;
 304
 305           ++dirlen;
 306           drive_spec = (char *) __alloca (dirlen + 1);
 307 #ifdef HAVE_MEMPCPY
 308           *((char *) mempcpy (drive_spec, pattern, dirlen)) = '\0';
 309 #else
 310           memcpy (drive_spec, pattern, dirlen);
 311           drive_spec[dirlen] = '\0';
 312 #endif
 313           /* For now, disallow wildcards in the drive spec, to
 314              prevent infinite recursion in glob.  */
 315           if (__glob_pattern_p (drive_spec, !(flags & GLOB_NOESCAPE)))
 316             return GLOB_NOMATCH;
 317           /* If this is "d:pattern", we need to copy `:' to DIRNAME
 318              as well.  If it's "d:/pattern", don't remove the slash
 319              from "d:/", since "d:" and "d:/" are not the same.*/
 320         }
 321 #endif
 322       newp = (char *) __alloca (dirlen + 1);
 323 #ifdef HAVE_MEMPCPY
 324       *((char *) mempcpy (newp, pattern, dirlen)) = '\0';
 325 #else
 326       memcpy (newp, pattern, dirlen);
 327       newp[dirlen] = '\0';
 328 #endif
 329       dirname = newp;
 330       ++filename;
 331
 332       if (filename[0] == '\0'
 333 #if defined __MSDOS__ || defined WINDOWS32
 334           && dirname[dirlen - 1] != ':'
 335           && (dirlen < 3 || dirname[dirlen - 2] != ':'
 336               || dirname[dirlen - 1] != '/')
 337 #endif
 338           && dirlen > 1)
 339         /* "pattern/".  Expand "pattern", appending slashes.  */
 340         {
 341           int val = glob (dirname, flags | GLOB_MARK, errfunc, pglob);
 342           if (val == 0)
 343             pglob->gl_flags = ((pglob->gl_flags & ~GLOB_MARK)
 344                                | (flags & GLOB_MARK));
 345           return val;
 346         }
 347     }
 348
 349   if (!(flags & GLOB_APPEND))
 350     {
 351       pglob->gl_pathc = 0;
 352       pglob->gl_pathv = NULL;
 353     }
 354
 355   oldcount = pglob->gl_pathc;
 356
 357 #ifndef VMS
 358   if ((flags & (GLOB_TILDE|GLOB_TILDE_CHECK)) && dirname[0] == '~')
 359     {
 360       if (dirname[1] == '\0' || dirname[1] == '/')
 361         {
 362           /* Look up home directory.  */
 363           const char *home_dir = getenv ("HOME");
 364 # ifdef _AMIGA
 365           if (home_dir == NULL || home_dir[0] == '\0')
 366             home_dir = "SYS:";
 367 # else
 368 #  ifdef WINDOWS32
 369           if (home_dir == NULL || home_dir[0] == '\0')
 370             home_dir = "c:/users/default"; /* poor default */
 371 #  else
 372           if (home_dir == NULL || home_dir[0] == '\0')
 373             {
 374               int success;
 375               char *name;
 376 #   if defined HAVE_GETLOGIN_R || defined _LIBC
 377               size_t buflen = sysconf (_SC_LOGIN_NAME_MAX) + 1;
 378
 379               if (buflen == 0)
 380                 /* `sysconf' does not support _SC_LOGIN_NAME_MAX.  Try
 381                    a moderate value.  */
 382                 buflen = 20;
 383               name = (char *) __alloca (buflen);
 384
 385               success = getlogin_r (name, buflen) >= 0;
 386 #   else
 387               success = (name = getlogin ()) != NULL;
 388 #   endif
 389               if (success)
 390                 {
 391                   struct passwd *p;
 392 #   if defined HAVE_GETPWNAM_R || defined _LIBC
 393                   size_t pwbuflen = sysconf (_SC_GETPW_R_SIZE_MAX);
 394                   char *pwtmpbuf;
 395                   struct passwd pwbuf;
 396                   int save = errno;
 397
 398                   if (pwbuflen == -1)
 399                     /* `sysconf' does not support _SC_GETPW_R_SIZE_MAX.
 400                        Try a moderate value.  */
 401                     pwbuflen = 1024;
 402                   pwtmpbuf = (char *) __alloca (pwbuflen);
 403
 404                   while (getpwnam_r (name, &pwbuf, pwtmpbuf, pwbuflen, &p)
 405                          != 0)
 406                     {
 407                       if (errno != ERANGE)
 408                         {
 409                           p = NULL;
 410                           break;
 411                         }
 412                       pwbuflen *= 2;
 413                       pwtmpbuf = (char *) __alloca (pwbuflen);
 414                       __set_errno (save);
 415                     }
 416 #   else
 417                   p = getpwnam (name);
 418 #   endif
 419                   if (p != NULL)
 420                     home_dir = p->pw_dir;
 421                 }
 422             }
 423           if (home_dir == NULL || home_dir[0] == '\0')
 424             {
 425               if (flags & GLOB_TILDE_CHECK)
 426                 return GLOB_NOMATCH;
 427               else
 428                 home_dir = "~"; /* No luck.  */
 429             }
 430 #  endif /* WINDOWS32 */
 431 # endif
 432           /* Now construct the full directory.  */
 433           if (dirname[1] == '\0')
 434             dirname = home_dir;
 435           else
 436             {
 437               char *newp;
 438               size_t home_len = strlen (home_dir);
 439               newp = (char *) __alloca (home_len + dirlen);
 440 # ifdef HAVE_MEMPCPY
 441               mempcpy (mempcpy (newp, home_dir, home_len),
 442                        &dirname[1], dirlen);
 443 # else
 444               memcpy (newp, home_dir, home_len);
 445               memcpy (&newp[home_len], &dirname[1], dirlen);
 446 # endif
 447               dirname = newp;
 448             }
 449         }
 450 # if !defined _AMIGA && !defined WINDOWS32
 451       else
 452         {
 453           char *end_name = strchr (dirname, '/');
 454           const char *user_name;
 455           const char *home_dir;
 456
 457           if (end_name == NULL)
 458             user_name = dirname + 1;
 459           else
 460             {
 461               char *newp;
 462               newp = (char *) __alloca (end_name - dirname);
 463 # ifdef HAVE_MEMPCPY
 464               *((char *) mempcpy (newp, dirname + 1, end_name - dirname))
 465                 = '\0';
 466 # else
 467               memcpy (newp, dirname + 1, end_name - dirname);
 468               newp[end_name - dirname - 1] = '\0';
 469 # endif
 470               user_name = newp;
 471             }
 472
 473           /* Look up specific user's home directory.  */
 474           {
 475             struct passwd *p;
 476 #  if defined HAVE_GETPWNAM_R || defined _LIBC
 477             size_t buflen = sysconf (_SC_GETPW_R_SIZE_MAX);
 478             char *pwtmpbuf;
 479             struct passwd pwbuf;
 480             int save = errno;
 481
 482             if (buflen == -1)
 483               /* `sysconf' does not support _SC_GETPW_R_SIZE_MAX.  Try a
 484                  moderate value.  */
 485               buflen = 1024;
 486             pwtmpbuf = (char *) __alloca (buflen);
 487
 488             while (getpwnam_r (user_name, &pwbuf, pwtmpbuf, buflen, &p) != 0)
 489               {
 490                 if (errno != ERANGE)
 491                   {
 492                     p = NULL;
 493                     break;
 494                   }
 495                 buflen *= 2;
 496                 pwtmpbuf = __alloca (buflen);
 497                 __set_errno (save);
 498               }
 499 #  else
 500             p = getpwnam (user_name);
 501 #  endif
 502             if (p != NULL)
 503               home_dir = p->pw_dir;
 504             else
 505               home_dir = NULL;
 506           }
 507           /* If we found a home directory use this.  */
 508           if (home_dir != NULL)
 509             {
 510               char *newp;
 511               size_t home_len = strlen (home_dir);
 512               size_t rest_len = end_name == NULL ? 0 : strlen (end_name);
 513               newp = (char *) __alloca (home_len + rest_len + 1);
 514 #  ifdef HAVE_MEMPCPY
 515               *((char *) mempcpy (mempcpy (newp, home_dir, home_len),
 516                                   end_name, rest_len)) = '\0';
 517 #  else
 518               memcpy (newp, home_dir, home_len);
 519               memcpy (&newp[home_len], end_name, rest_len);
 520               newp[home_len + rest_len] = '\0';
 521 #  endif
 522               dirname = newp;
 523             }
 524           else
 525             if (flags & GLOB_TILDE_CHECK)
 526               /* We have to regard it as an error if we cannot find the
 527                  home directory.  */
 528               return GLOB_NOMATCH;
 529         }
 530 # endif /* Not Amiga && not WINDOWS32.  */
 531     }
 532 #endif  /* Not VMS.  */
 533
 534   /* Now test whether we looked for "~" or "~NAME".  In this case we
 535      can give the answer now.  */
 536   if (filename == NULL)
 537     {
 538       struct stat st;
 539
 540       /* Return the directory if we don't check for error or if it exists.  */
 541       if ((flags & GLOB_NOCHECK)
 542           || (((flags & GLOB_ALTDIRFUNC)
 543                ? (*pglob->gl_stat) (dirname, &st)
 544                : __stat (dirname, &st)) == 0
 545               && S_ISDIR (st.st_mode)))
 546         {
 547           pglob->gl_pathv
 548             = (char **) xrealloc (pglob->gl_pathv,
 549                                  (pglob->gl_pathc +
 550                                   ((flags & GLOB_DOOFFS) ?
 551                                    pglob->gl_offs : 0) +
 552                                   1 + 1) *
 553                                  sizeof (char *));
 554           if (pglob->gl_pathv == NULL)
 555             return GLOB_NOSPACE;
 556
 557           if (flags & GLOB_DOOFFS)
 558             while (pglob->gl_pathc < pglob->gl_offs)
 559               pglob->gl_pathv[pglob->gl_pathc++] = NULL;
 560
 561 #if defined HAVE_STRDUP || defined _LIBC
 562           pglob->gl_pathv[pglob->gl_pathc] = xstrdup (dirname);
 563 #else
 564           {
 565             size_t len = strlen (dirname) + 1;
 566             char *dircopy = xmalloc (len);
 567             if (dircopy != NULL)
 568               pglob->gl_pathv[pglob->gl_pathc] = memcpy (dircopy, dirname,
 569                                                          len);
 570           }
 571 #endif
 572           if (pglob->gl_pathv[pglob->gl_pathc] == NULL)
 573             {
 574               free (pglob->gl_pathv);
 575               return GLOB_NOSPACE;
 576             }
 577           pglob->gl_pathv[++pglob->gl_pathc] = NULL;
 578           pglob->gl_flags = flags;
 579
 580           return 0;
 581         }
 582
 583       /* Not found.  */
 584       return GLOB_NOMATCH;
 585     }
 586
 587   if (__glob_pattern_p (dirname, !(flags & GLOB_NOESCAPE)))
 588     {
 589       /* The directory name contains metacharacters, so we
 590          have to glob for the directory, and then glob for
 591          the pattern in each directory found.  */
 592       glob_t dirs;
 593       register int i;
 594
 595       if ((flags & GLOB_ALTDIRFUNC) != 0)
 596         {
 597           /* Use the alternative access functions also in the recursive
 598              call.  */
 599           dirs.gl_opendir = pglob->gl_opendir;
 600           dirs.gl_readdir = pglob->gl_readdir;
 601           dirs.gl_closedir = pglob->gl_closedir;
 602           dirs.gl_stat = pglob->gl_stat;
 603           dirs.gl_lstat = pglob->gl_lstat;
 604         }
 605
 606       status = glob (dirname,
 607                      ((flags & (GLOB_ERR | GLOB_NOCHECK | GLOB_NOESCAPE
 608                                 | GLOB_ALTDIRFUNC))
 609                       | GLOB_NOSORT | GLOB_ONLYDIR),
 610                      errfunc, &dirs);
 611       if (status != 0)
 612         return status;
 613
 614       /* We have successfully globbed the preceding directory name.
 615          For each name we found, call glob_in_dir on it and FILENAME,
 616          appending the results to PGLOB.  */
 617       for (i = 0; i < dirs.gl_pathc; ++i)
 618         {
 619           int old_pathc;
 620
 621 #ifdef  SHELL
 622           {
 623             /* Make globbing interruptible in the bash shell. */
 624             extern int interrupt_state;
 625
 626             if (interrupt_state)
 627               {
 628                 globfree (&dirs);
 629                 globfree (&files);
 630                 return GLOB_ABORTED;
 631               }
 632           }
 633 #endif /* SHELL.  */
 634
 635           old_pathc = pglob->gl_pathc;
 636           status = glob_in_dir (filename, dirs.gl_pathv[i],
 637                                 ((flags | GLOB_APPEND)
 638                                  & ~(GLOB_NOCHECK | GLOB_ERR)),
 639                                 errfunc, pglob);
 640           if (status == GLOB_NOMATCH)
 641             /* No matches in this directory.  Try the next.  */
 642             continue;
 643
 644           if (status != 0)
 645             {
 646               globfree (&dirs);
 647               globfree (pglob);
 648               return status;
 649             }
 650
 651           /* Stick the directory on the front of each name.  */
 652           if (prefix_array (dirs.gl_pathv[i],
 653                             &pglob->gl_pathv[old_pathc],
 654                             pglob->gl_pathc - old_pathc))
 655             {
 656               globfree (&dirs);
 657               globfree (pglob);
 658               return GLOB_NOSPACE;
 659             }
 660         }
 661
 662       flags |= GLOB_MAGCHAR;
 663
 664       /* We have ignored the GLOB_NOCHECK flag in the `glob_in_dir' calls.
 665          But if we have not found any matching entry and thie GLOB_NOCHECK
 666          flag was set we must return the list consisting of the disrectory
 667          names followed by the filename.  */
 668       if (pglob->gl_pathc == oldcount)
 669         {
 670           /* No matches.  */
 671           if (flags & GLOB_NOCHECK)
 672             {
 673               size_t filename_len = strlen (filename) + 1;
 674               char **new_pathv;
 675               struct stat st;
 676
 677               /* This is an pessimistic guess about the size.  */
 678               pglob->gl_pathv
 679                 = (char **) xrealloc (pglob->gl_pathv,
 680                                      (pglob->gl_pathc +
 681                                       ((flags & GLOB_DOOFFS) ?
 682                                        pglob->gl_offs : 0) +
 683                                       dirs.gl_pathc + 1) *
 684                                      sizeof (char *));
 685               if (pglob->gl_pathv == NULL)
 686                 {
 687                   globfree (&dirs);
 688                   return GLOB_NOSPACE;
 689                 }
 690
 691               if (flags & GLOB_DOOFFS)
 692                 while (pglob->gl_pathc < pglob->gl_offs)
 693                   pglob->gl_pathv[pglob->gl_pathc++] = NULL;
 694
 695               for (i = 0; i < dirs.gl_pathc; ++i)
 696                 {
 697                   const char *dir = dirs.gl_pathv[i];
 698                   size_t dir_len = strlen (dir);
 699
 700                   /* First check whether this really is a directory.  */
 701                   if (((flags & GLOB_ALTDIRFUNC)
 702                        ? (*pglob->gl_stat) (dir, &st) : __stat (dir, &st)) != 0
 703                       || !S_ISDIR (st.st_mode))
 704                     /* No directory, ignore this entry.  */
 705                     continue;
 706
 707                   pglob->gl_pathv[pglob->gl_pathc] = xmalloc (dir_len + 1
 708                                                              + filename_len);
 709                   if (pglob->gl_pathv[pglob->gl_pathc] == NULL)
 710                     {
 711                       globfree (&dirs);
 712                       globfree (pglob);
 713                       return GLOB_NOSPACE;
 714                     }
 715
 716 #ifdef HAVE_MEMPCPY
 717                   mempcpy (mempcpy (mempcpy (pglob->gl_pathv[pglob->gl_pathc],
 718                                              dir, dir_len),
 719                                     "/", 1),
 720                            filename, filename_len);
 721 #else
 722                   memcpy (pglob->gl_pathv[pglob->gl_pathc], dir, dir_len);
 723                   pglob->gl_pathv[pglob->gl_pathc][dir_len] = '/';
 724                   memcpy (&pglob->gl_pathv[pglob->gl_pathc][dir_len + 1],
 725                           filename, filename_len);
 726 #endif
 727                   ++pglob->gl_pathc;
 728                 }
 729
 730               pglob->gl_pathv[pglob->gl_pathc] = NULL;
 731               pglob->gl_flags = flags;
 732
 733               /* Now we know how large the gl_pathv vector must be.  */
 734               new_pathv = (char **) xrealloc (pglob->gl_pathv,
 735                                              ((pglob->gl_pathc + 1)
 736                                               * sizeof (char *)));
 737               if (new_pathv != NULL)
 738                 pglob->gl_pathv = new_pathv;
 739             }
 740           else
 741             return GLOB_NOMATCH;
 742         }
 743
 744       globfree (&dirs);
 745     }
 746   else
 747     {
 748       status = glob_in_dir (filename, dirname, flags, errfunc, pglob);
 749       if (status != 0)
 750         return status;
 751
 752       if (dirlen > 0)
 753         {
 754           /* Stick the directory on the front of each name.  */
 755           int ignore = oldcount;
 756
 757           if ((flags & GLOB_DOOFFS) && ignore < pglob->gl_offs)
 758             ignore = pglob->gl_offs;
 759
 760           if (prefix_array (dirname,
 761                             &pglob->gl_pathv[ignore],
 762                             pglob->gl_pathc - ignore))
 763             {
 764               globfree (pglob);
 765               return GLOB_NOSPACE;
 766             }
 767         }
 768     }
 769
 770   if (flags & GLOB_MARK)
 771     {
 772       /* Append slashes to directory names.  */
 773       int i;
 774       struct stat st;
 775       for (i = oldcount; i < pglob->gl_pathc; ++i)
 776         if (((flags & GLOB_ALTDIRFUNC)
 777              ? (*pglob->gl_stat) (pglob->gl_pathv[i], &st)
 778              : __stat (pglob->gl_pathv[i], &st)) == 0
 779             && S_ISDIR (st.st_mode))
 780           {
 781             size_t len = strlen (pglob->gl_pathv[i]) + 2;
 782             char *new = xrealloc (pglob->gl_pathv[i], len);
 783             if (new == NULL)
 784               {
 785                 globfree (pglob);
 786                 return GLOB_NOSPACE;
 787               }
 788             strcpy (&new[len - 2], "/");
 789             pglob->gl_pathv[i] = new;
 790           }
 791     }
 792
 793   if (!(flags & GLOB_NOSORT))
 794     {
 795       /* Sort the vector.  */
 796       int non_sort = oldcount;
 797
 798       if ((flags & GLOB_DOOFFS) && pglob->gl_offs > oldcount)
 799         non_sort = pglob->gl_offs;
 800
 801       qsort ((__ptr_t) &pglob->gl_pathv[non_sort],
 802              pglob->gl_pathc - non_sort,
 803              sizeof (char *), collated_compare);
 804     }
 805
 806   return 0;
 807 }
 808
 809
 810 /* Free storage allocated in PGLOB by a previous `glob' call.  */
 811 void
 812 globfree (glob_t *pglob)
 813 {
 814   if (pglob->gl_pathv != NULL)
 815     {
 816       register int i;
 817       for (i = 0; i < pglob->gl_pathc; ++i)
 818         if (pglob->gl_pathv[i] != NULL)
 819           free ((__ptr_t) pglob->gl_pathv[i]);
 820       free ((__ptr_t) pglob->gl_pathv);
 821     }
 822 }
 823
 824
 825 /* Do a collated comparison of A and B.  */
 826 static int
 827 collated_compare (const __ptr_t a, const __ptr_t b)
 828 {
 829   const char *const s1 = *(const char *const * const) a;
 830   const char *const s2 = *(const char *const * const) b;
 831
 832   if (s1 == s2)
 833     return 0;
 834   if (s1 == NULL)
 835     return 1;
 836   if (s2 == NULL)
 837     return -1;
 838   return strcoll (s1, s2);
 839 }
 840
 841
 842 /* Prepend DIRNAME to each of N members of ARRAY, replacing ARRAY's
 843    elements in place.  Return nonzero if out of memory, zero if successful.
 844    A slash is inserted between DIRNAME and each elt of ARRAY,
 845    unless DIRNAME is just "/".  Each old element of ARRAY is freed.  */
 846 static int
 847 prefix_array (const char *dirname, char **array, size_t n)
 848 {
 849   register size_t i;
 850   size_t dirlen = strlen (dirname);
 851 #if defined __MSDOS__ || defined WINDOWS32
 852   int sep_char = '/';
 853 # define DIRSEP_CHAR sep_char
 854 #else
 855 # define DIRSEP_CHAR '/'
 856 #endif
 857
 858   if (dirlen == 1 && dirname[0] == '/')
 859     /* DIRNAME is just "/", so normal prepending would get us "//foo".
 860        We want "/foo" instead, so don't prepend any chars from DIRNAME.  */
 861     dirlen = 0;
 862 #if defined __MSDOS__ || defined WINDOWS32
 863   else if (dirlen > 1)
 864     {
 865       if (dirname[dirlen - 1] == '/')
 866         /* DIRNAME is "d:/".  Don't prepend the slash from DIRNAME.  */
 867         --dirlen;
 868       else if (dirname[dirlen - 1] == ':')
 869         {
 870           /* DIRNAME is "d:".  Use `:' instead of `/'.  */
 871           --dirlen;
 872           sep_char = ':';
 873         }
 874     }
 875 #endif
 876
 877   for (i = 0; i < n; ++i)
 878     {
 879       size_t eltlen = strlen (array[i]) + 1;
 880       char *new = (char *) xmalloc (dirlen + 1 + eltlen);
 881       if (new == NULL)
 882         {
 883           while (i > 0)
 884             free ((__ptr_t) array[--i]);
 885           return 1;
 886         }
 887
 888 #ifdef HAVE_MEMPCPY
 889       {
 890         char *endp = (char *) mempcpy (new, dirname, dirlen);
 891         *endp++ = DIRSEP_CHAR;
 892         mempcpy (endp, array[i], eltlen);
 893       }
 894 #else
 895       memcpy (new, dirname, dirlen);
 896       new[dirlen] = DIRSEP_CHAR;
 897       memcpy (&new[dirlen + 1], array[i], eltlen);
 898 #endif
 899       free ((__ptr_t) array[i]);
 900       array[i] = new;
 901     }
 902
 903   return 0;
 904 }
 905
 906
 907 /* We must not compile this function twice.  */
 908 #if !defined _LIBC || !defined NO_GLOB_PATTERN_P
 909 /* Return nonzero if PATTERN contains any metacharacters.
 910    Metacharacters can be quoted with backslashes if QUOTE is nonzero.  */
 911 static int
 912 __glob_pattern_p (const char *pattern, int quote)
 913 {
 914   register const char *p;
 915   int open = 0;
 916
 917   for (p = pattern; *p != '\0'; ++p)
 918     switch (*p)
 919       {
 920       case '?':
 921       case '*':
 922         return 1;
 923
 924       case '\\':
 925         if (quote && p[1] != '\0')
 926           ++p;
 927         break;
 928
 929       case '[':
 930         open = 1;
 931         break;
 932
 933       case ']':
 934         if (open)
 935           return 1;
 936         break;
 937       }
 938
 939   return 0;
 940 }
 941 # ifdef _LIBC
 942 weak_alias (__glob_pattern_p, glob_pattern_p)
 943 # endif
 944 #endif
 945
 946
 947 /* Like `glob', but PATTERN is a final pathname component,
 948    and matches are searched for in DIRECTORY.
 949    The GLOB_NOSORT bit in FLAGS is ignored.  No sorting is ever done.
 950    The GLOB_APPEND flag is assumed to be set (always appends).  */
 951 static int
 952 glob_in_dir (const char *pattern, const char *directory, int flags,
 953                 int (*errfunc) __P ((const char *, int)), glob_t *pglob)
 954 {
 955   __ptr_t stream = NULL;
 956
 957   struct globlink
 958     {
 959       struct globlink *next;
 960       char *name;
 961     };
 962   struct globlink *names = NULL;
 963   size_t nfound;
 964   int meta;
 965   int save;
 966
 967   meta = __glob_pattern_p (pattern, !(flags & GLOB_NOESCAPE));
 968   if (meta == 0)
 969     {
 970       if (flags & (GLOB_NOCHECK|GLOB_NOMAGIC))
 971         /* We need not do any tests.  The PATTERN contains no meta
 972            characters and we must not return an error therefore the
 973            result will always contain exactly one name.  */
 974         flags |= GLOB_NOCHECK;
 975       else
 976         {
 977           /* Since we use the normal file functions we can also use stat()
 978              to verify the file is there.  */
 979           struct stat st;
 980           size_t patlen = strlen (pattern);
 981           size_t dirlen = strlen (directory);
 982           char *fullname = (char *) __alloca (dirlen + 1 + patlen + 1);
 983
 984 # ifdef HAVE_MEMPCPY
 985           mempcpy (mempcpy (mempcpy (fullname, directory, dirlen),
 986                             "/", 1),
 987                    pattern, patlen + 1);
 988 # else
 989           memcpy (fullname, directory, dirlen);
 990           fullname[dirlen] = '/';
 991           memcpy (&fullname[dirlen + 1], pattern, patlen + 1);
 992 # endif
 993           if (((flags & GLOB_ALTDIRFUNC)
 994                ? (*pglob->gl_stat) (fullname, &st)
 995                : __stat (fullname, &st)) == 0)
 996             /* We found this file to be existing.  Now tell the rest
 997                of the function to copy this name into the result.  */
 998             flags |= GLOB_NOCHECK;
 999         }
1000
1001       nfound = 0;
1002     }
1003   else
1004     {
1005       if (pattern[0] == '\0')
1006         {
1007           /* This is a special case for matching directories like in
1008              "*a/".  */
1009           names = (struct globlink *) __alloca (sizeof (struct globlink));
1010           names->name = (char *) xmalloc (1);
1011           if (names->name == NULL)
1012             goto memory_error;
1013           names->name[0] = '\0';
1014           names->next = NULL;
1015           nfound = 1;
1016           meta = 0;
1017         }
1018       else
1019         {
1020           stream = ((flags & GLOB_ALTDIRFUNC)
1021                     ? (*pglob->gl_opendir) (directory)
1022                     : (__ptr_t) opendir (directory));
1023           if (stream == NULL)
1024             {
1025               if (errno != ENOTDIR
1026                   && ((errfunc != NULL && (*errfunc) (directory, errno))
1027                       || (flags & GLOB_ERR)))
1028                 return GLOB_ABORTED;
1029               nfound = 0;
1030               meta = 0;
1031             }
1032           else
1033             {
1034               int fnm_flags = ((!(flags & GLOB_PERIOD) ? FNM_PERIOD : 0)
1035                                | ((flags & GLOB_NOESCAPE) ? FNM_NOESCAPE : 0)
1036 #if defined _AMIGA || defined VMS
1037                                    | FNM_CASEFOLD
1038 #endif
1039                                    );
1040               nfound = 0;
1041               flags |= GLOB_MAGCHAR;
1042
1043               while (1)
1044                 {
1045                   const char *name;
1046                   size_t len;
1047                   struct dirent *d = ((flags & GLOB_ALTDIRFUNC)
1048                                       ? (*pglob->gl_readdir) (stream)
1049                                       : readdir ((DIR *) stream));
1050                   if (d == NULL)
1051                     break;
1052                   if (! REAL_DIR_ENTRY (d))
1053                     continue;
1054
1055 #ifdef HAVE_D_TYPE
1056                   /* If we shall match only directories use the information
1057                      provided by the dirent call if possible.  */
1058                   if ((flags & GLOB_ONLYDIR)
1059                       && d->d_type != DT_UNKNOWN && d->d_type != DT_DIR)
1060                     continue;
1061 #endif
1062
1063                   name = d->d_name;
1064
1065                   if (fnmatch (pattern, name, fnm_flags) == 0)
1066                     {
1067                       struct globlink *new = (struct globlink *)
1068                         __alloca (sizeof (struct globlink));
1069                       len = NAMLEN (d);
1070                       new->name = (char *) xmalloc (len + 1);
1071                       if (new->name == NULL)
1072                         goto memory_error;
1073 #ifdef HAVE_MEMPCPY
1074                       *((char *) mempcpy ((__ptr_t) new->name, name, len))
1075                         = '\0';
1076 #else
1077                       memcpy ((__ptr_t) new->name, name, len);
1078                       new->name[len] = '\0';
1079 #endif
1080                       new->next = names;
1081                       names = new;
1082                       ++nfound;
1083                     }
1084                 }
1085             }
1086         }
1087     }
1088
1089   if (nfound == 0 && (flags & GLOB_NOCHECK))
1090     {
1091       size_t len = strlen (pattern);
1092       nfound = 1;
1093       names = (struct globlink *) __alloca (sizeof (struct globlink));
1094       names->next = NULL;
1095       names->name = (char *) xmalloc (len + 1);
1096       if (names->name == NULL)
1097         goto memory_error;
1098 #ifdef HAVE_MEMPCPY
1099       *((char *) mempcpy (names->name, pattern, len)) = '\0';
1100 #else
1101       memcpy (names->name, pattern, len);
1102       names->name[len] = '\0';
1103 #endif
1104     }
1105
1106   if (nfound != 0)
1107     {
1108       pglob->gl_pathv
1109         = (char **) xrealloc (pglob->gl_pathv,
1110                              (pglob->gl_pathc +
1111                               ((flags & GLOB_DOOFFS) ? pglob->gl_offs : 0) +
1112                               nfound + 1) *
1113                              sizeof (char *));
1114       if (pglob->gl_pathv == NULL)
1115         goto memory_error;
1116
1117       if (flags & GLOB_DOOFFS)
1118         while (pglob->gl_pathc < pglob->gl_offs)
1119           pglob->gl_pathv[pglob->gl_pathc++] = NULL;
1120
1121       for (; names != NULL; names = names->next)
1122         pglob->gl_pathv[pglob->gl_pathc++] = names->name;
1123       pglob->gl_pathv[pglob->gl_pathc] = NULL;
1124
1125       pglob->gl_flags = flags;
1126     }
1127
1128   save = errno;
1129   if (stream != NULL)
1130     {
1131       if (flags & GLOB_ALTDIRFUNC)
1132         (*pglob->gl_closedir) (stream);
1133       else
1134         closedir ((DIR *) stream);
1135     }
1136   __set_errno (save);
1137
1138   return nfound == 0 ? GLOB_NOMATCH : 0;
1139
1140  memory_error:
1141   {
1142     int save = errno;
1143     if (flags & GLOB_ALTDIRFUNC)
1144       (*pglob->gl_closedir) (stream);
1145     else
1146       closedir ((DIR *) stream);
1147     __set_errno (save);
1148   }
1149   while (names != NULL)
1150     {
1151       if (names->name != NULL)
1152         free ((__ptr_t) names->name);
1153       names = names->next;
1154     }
1155   return GLOB_NOSPACE;
1156 }