posix/glob.c

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