posix/glob.c

   1 /* Copyright (C) 1991, 92, 93, 94, 95, 96 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
  37 /* Comment out all this code if we are using the GNU C Library, and are not
  38    actually compiling the library itself.  This code is part of the GNU C
  39    Library, but also included in many other GNU distributions.  Compiling
  40    and linking in this code is a waste when using the GNU C library
  41    (especially if it is a shared library).  Rather than having every GNU
  42    program understand `configure --with-gnu-libc' and omit the object files,
  43    it is simpler to just do this in the source for each such file.  */
  44
  45 #define GLOB_INTERFACE_VERSION 1
  46 #if !defined (_LIBC) && defined (__GNU_LIBRARY__) && __GNU_LIBRARY__ > 1
  47 #include <gnu-versions.h>
  48 #if _GNU_GLOB_INTERFACE_VERSION == GLOB_INTERFACE_VERSION
  49 #define ELIDE_CODE
  50 #endif
  51 #endif
  52
  53 #ifndef ELIDE_CODE
  54
  55 #ifdef  STDC_HEADERS
  56 #include <stddef.h>
  57 #endif
  58
  59 #if defined HAVE_UNISTD_H || defined _LIBC
  60 #include <unistd.h>
  61 #ifndef POSIX
  62 #ifdef  _POSIX_VERSION
  63 #define POSIX
  64 #endif
  65 #endif
  66 #endif
  67
  68 #if !defined (_AMIGA) && !defined (VMS) && !defined(WIN32)
  69 #include <pwd.h>
  70 #endif
  71
  72 #if !defined(__GNU_LIBRARY__) && !defined(STDC_HEADERS)
  73 extern int errno;
  74 #endif
  75 #ifndef __set_errno
  76 #define __set_errno(val) errno = (val)
  77 #endif
  78
  79 #ifndef NULL
  80 #define NULL    0
  81 #endif
  82
  83
  84 #if defined (HAVE_DIRENT_H) || defined (__GNU_LIBRARY__)
  85 # include <dirent.h>
  86 # define NAMLEN(dirent) strlen((dirent)->d_name)
  87 #else
  88 # define dirent direct
  89 # define NAMLEN(dirent) (dirent)->d_namlen
  90 # ifdef HAVE_SYS_NDIR_H
  91 #  include <sys/ndir.h>
  92 # endif
  93 # ifdef HAVE_SYS_DIR_H
  94 #  include <sys/dir.h>
  95 # endif
  96 # ifdef HAVE_NDIR_H
  97 #  include <ndir.h>
  98 # endif
  99 # ifdef HAVE_VMSDIR_H
 100 #  include "vmsdir.h"
 101 # endif /* HAVE_VMSDIR_H */
 102 #endif
 103
 104
 105 /* In GNU systems, <dirent.h> defines this macro for us.  */
 106 #ifdef _D_NAMLEN
 107 #undef NAMLEN
 108 #define NAMLEN(d) _D_NAMLEN(d)
 109 #endif
 110
 111
 112 #if (defined (POSIX) || defined (WIN32)) && !defined (__GNU_LIBRARY__)
 113 /* Posix does not require that the d_ino field be present, and some
 114    systems do not provide it. */
 115 #define REAL_DIR_ENTRY(dp) 1
 116 #else
 117 #define REAL_DIR_ENTRY(dp) (dp->d_ino != 0)
 118 #endif /* POSIX */
 119
 120 #if     (defined (STDC_HEADERS) || defined (__GNU_LIBRARY__))
 121 #include <stdlib.h>
 122 #include <string.h>
 123 #define ANSI_STRING
 124 #else   /* No standard headers.  */
 125
 126 extern char *getenv ();
 127
 128 #ifdef HAVE_STRING_H
 129 #include <string.h>
 130 #define ANSI_STRING
 131 #else
 132 #include <strings.h>
 133 #endif
 134 #ifdef  HAVE_MEMORY_H
 135 #include <memory.h>
 136 #endif
 137
 138 extern char *malloc (), *realloc ();
 139 extern void free ();
 140
 141 extern void qsort ();
 142 extern void abort (), exit ();
 143
 144 #endif  /* Standard headers.  */
 145
 146 #ifndef ANSI_STRING
 147
 148 #ifndef bzero
 149 extern void bzero ();
 150 #endif
 151 #ifndef bcopy
 152 extern void bcopy ();
 153 #endif
 154
 155 #define memcpy(d, s, n) bcopy ((s), (d), (n))
 156 #define strrchr rindex
 157 /* memset is only used for zero here, but let's be paranoid.  */
 158 #define memset(s, better_be_zero, n) \
 159   ((void) ((better_be_zero) == 0 ? (bzero((s), (n)), 0) : (abort(), 0)))
 160 #endif  /* Not ANSI_STRING.  */
 161
 162 #ifndef HAVE_STRCOLL
 163 #define strcoll strcmp
 164 #endif
 165
 166
 167 #ifndef __GNU_LIBRARY__
 168 #ifdef  __GNUC__
 169 __inline
 170 #endif
 171 #ifndef __SASC
 172 #ifdef WIN32
 173 static void *
 174 #else
 175 static char *
 176 #endif
 177 my_realloc (p, n)
 178      char *p;
 179      unsigned int n;
 180 {
 181   /* These casts are the for sake of the broken Ultrix compiler,
 182      which warns of illegal pointer combinations otherwise.  */
 183   if (p == NULL)
 184     return (char *) malloc (n);
 185   return (char *) realloc (p, n);
 186 }
 187 #define realloc my_realloc
 188 #endif /* __SASC */
 189 #endif /* __GNU_LIBRARY__ */
 190
 191
 192 #if     !defined(__alloca) && !defined(__GNU_LIBRARY__)
 193
 194 #ifdef  __GNUC__
 195 #undef  alloca
 196 #define alloca(n)       __builtin_alloca (n)
 197 #else   /* Not GCC.  */
 198 #ifdef HAVE_ALLOCA_H
 199 #include <alloca.h>
 200 #else   /* Not HAVE_ALLOCA_H.  */
 201 #ifndef _AIX
 202 #ifdef WIN32
 203 #include <malloc.h>
 204 #else
 205 extern char *alloca ();
 206 #endif /* WIN32 */
 207 #endif  /* Not _AIX.  */
 208 #endif  /* sparc or HAVE_ALLOCA_H.  */
 209 #endif  /* GCC.  */
 210
 211 #define __alloca        alloca
 212
 213 #endif
 214
 215 #ifndef __GNU_LIBRARY__
 216 #define __stat stat
 217 #ifdef STAT_MACROS_BROKEN
 218 #undef S_ISDIR
 219 #endif
 220 #ifndef S_ISDIR
 221 #define S_ISDIR(mode) (((mode) & S_IFMT) == S_IFDIR)
 222 #endif
 223 #endif
 224
 225 #ifndef STDC_HEADERS
 226 #undef  size_t
 227 #define size_t  unsigned int
 228 #endif
 229
 230 /* Some system header files erroneously define these.
 231    We want our own definitions from <fnmatch.h> to take precedence.  */
 232 #undef  FNM_PATHNAME
 233 #undef  FNM_NOESCAPE
 234 #undef  FNM_PERIOD
 235 #include <fnmatch.h>
 236
 237 /* Some system header files erroneously define these.
 238    We want our own definitions from <glob.h> to take precedence.  */
 239 #undef  GLOB_ERR
 240 #undef  GLOB_MARK
 241 #undef  GLOB_NOSORT
 242 #undef  GLOB_DOOFFS
 243 #undef  GLOB_NOCHECK
 244 #undef  GLOB_APPEND
 245 #undef  GLOB_NOESCAPE
 246 #undef  GLOB_PERIOD
 247 #include <glob.h>
 248 \f
 249 static int glob_pattern_p __P ((const char *pattern, int quote));
 250 static int glob_in_dir __P ((const char *pattern, const char *directory,
 251                              int flags,
 252                              int (*errfunc) __P ((const char *, int)),
 253                              glob_t *pglob));
 254 static int prefix_array __P ((const char *prefix, char **array, size_t n));
 255 static int collated_compare __P ((const __ptr_t, const __ptr_t));
 256
 257 /* Do glob searching for PATTERN, placing results in PGLOB.
 258    The bits defined above may be set in FLAGS.
 259    If a directory cannot be opened or read and ERRFUNC is not nil,
 260    it is called with the pathname that caused the error, and the
 261    `errno' value from the failing call; if it returns non-zero
 262    `glob' returns GLOB_ABEND; if it returns zero, the error is ignored.
 263    If memory cannot be allocated for PGLOB, GLOB_NOSPACE is returned.
 264    Otherwise, `glob' returns zero.  */
 265 int
 266 glob (pattern, flags, errfunc, pglob)
 267      const char *pattern;
 268      int flags;
 269      int (*errfunc) __P ((const char *, int));
 270      glob_t *pglob;
 271 {
 272   const char *filename;
 273   char *dirname;
 274   size_t dirlen;
 275   int status;
 276   int oldcount;
 277
 278   if (pattern == NULL || pglob == NULL || (flags & ~__GLOB_FLAGS) != 0)
 279     {
 280       __set_errno (EINVAL);
 281       return -1;
 282     }
 283
 284   if (flags & GLOB_BRACE)
 285     {
 286       const char *begin = strchr (pattern, '{');
 287       if (begin != NULL)
 288         {
 289           int firstc;
 290           size_t restlen;
 291           const char *p, *end, *next;
 292           unsigned int depth = 0;
 293
 294           /* Find the end of the brace expression, by counting braces.
 295              While we're at it, notice the first comma at top brace level.  */
 296           end = begin + 1;
 297           next = NULL;
 298           while (1)
 299             {
 300               switch (*end++)
 301                 {
 302                 case ',':
 303                   if (depth == 0 && next == NULL)
 304                     next = end;
 305                   continue;
 306                 case '{':
 307                   ++depth;
 308                   continue;
 309                 case '}':
 310                   if (depth-- == 0)
 311                     break;
 312                   continue;
 313                 case '\0':
 314                   return glob (pattern, flags &~ GLOB_BRACE, errfunc, pglob);
 315                 }
 316               break;
 317             }
 318           restlen = strlen (end) + 1;
 319           if (next == NULL)
 320             next = end;
 321
 322           /* We have a brace expression.  BEGIN points to the opening {,
 323              NEXT points past the terminator of the first element, and END
 324              points past the final }.  We will accumulate result names from
 325              recursive runs for each brace alternative in the buffer using
 326              GLOB_APPEND.  */
 327
 328           if (!(flags & GLOB_APPEND))
 329             {
 330               /* This call is to set a new vector, so clear out the
 331                  vector so we can append to it.  */
 332               pglob->gl_pathc = 0;
 333               pglob->gl_pathv = NULL;
 334             }
 335           firstc = pglob->gl_pathc;
 336
 337           /* In this loop P points to the beginning of the current element
 338              and NEXT points past its terminator.  */
 339           p = begin + 1;
 340           while (1)
 341             {
 342               /* Construct a whole name that is one of the brace
 343                  alternatives in a temporary buffer.  */
 344               int result;
 345               size_t bufsz = (begin - pattern) + (next - 1 - p) + restlen;
 346 #ifdef __GNUC__
 347               char onealt[bufsz];
 348 #else
 349               char *onealt = malloc (bufsz);
 350               if (onealt == NULL)
 351                 {
 352                   if (!(flags & GLOB_APPEND))
 353                     globfree (pglob);
 354                   return GLOB_NOSPACE;
 355                 }
 356 #endif
 357               memcpy (onealt, pattern, begin - pattern);
 358               memcpy (&onealt[begin - pattern], p, next - 1 - p);
 359               memcpy (&onealt[(begin - pattern) + (next - 1 - p)],
 360                       end, restlen);
 361               result = glob (onealt,
 362                              ((flags & ~(GLOB_NOCHECK|GLOB_NOMAGIC)) |
 363                               GLOB_APPEND), errfunc, pglob);
 364 #ifndef __GNUC__
 365               free (onealt);
 366 #endif
 367
 368               /* If we got an error, return it.  */
 369               if (result && result != GLOB_NOMATCH)
 370                 {
 371                   if (!(flags & GLOB_APPEND))
 372                     globfree (pglob);
 373                   return result;
 374                 }
 375
 376               /* Advance past this alternative and process the next.  */
 377               p = next;
 378               depth = 0;
 379             scan:
 380               switch (*p++)
 381                 {
 382                 case ',':
 383                   if (depth == 0)
 384                     {
 385                       /* Found the next alternative.  Loop to glob it.  */
 386                       next = p;
 387                       continue;
 388                     }
 389                   goto scan;
 390                 case '{':
 391                   ++depth;
 392                   goto scan;
 393                 case '}':
 394                   if (depth-- == 0)
 395                     /* End of the brace expression.  Break out of the loop.  */
 396                     break;
 397                   goto scan;
 398                 }
 399             }
 400
 401           if (pglob->gl_pathc == firstc &&
 402               !(flags & (GLOB_NOCHECK|GLOB_NOMAGIC)))
 403             return GLOB_NOMATCH;
 404         }
 405     }
 406
 407   /* Find the filename.  */
 408   filename = strrchr (pattern, '/');
 409   if (filename == NULL)
 410     {
 411       filename = pattern;
 412 #ifdef _AMIGA
 413       dirname = (char *) "";
 414 #else
 415       dirname = (char *) ".";
 416 #endif
 417       dirlen = 0;
 418     }
 419   else if (filename == pattern)
 420     {
 421       /* "/pattern".  */
 422       dirname = (char *) "/";
 423       dirlen = 1;
 424       ++filename;
 425     }
 426   else
 427     {
 428       dirlen = filename - pattern;
 429       dirname = (char *) __alloca (dirlen + 1);
 430       memcpy (dirname, pattern, dirlen);
 431       dirname[dirlen] = '\0';
 432       ++filename;
 433     }
 434
 435   if (filename[0] == '\0' && dirlen > 1)
 436     /* "pattern/".  Expand "pattern", appending slashes.  */
 437     {
 438       int val = glob (dirname, flags | GLOB_MARK, errfunc, pglob);
 439       if (val == 0)
 440         pglob->gl_flags = (pglob->gl_flags & ~GLOB_MARK) | (flags & GLOB_MARK);
 441       return val;
 442     }
 443
 444   if (!(flags & GLOB_APPEND))
 445     {
 446       pglob->gl_pathc = 0;
 447       pglob->gl_pathv = NULL;
 448     }
 449
 450   oldcount = pglob->gl_pathc;
 451
 452 #ifndef VMS
 453   if ((flags & GLOB_TILDE) && dirname[0] == '~')
 454     {
 455       if (dirname[1] == '\0')
 456         {
 457           /* Look up home directory.  */
 458           dirname = getenv ("HOME");
 459 #ifdef _AMIGA
 460           if (dirname == NULL || dirname[0] == '\0')
 461             dirname = "SYS:";
 462 #else
 463 #ifdef WIN32
 464           if (dirname == NULL || dirname[0] == '\0')
 465             dirname = "c:/users/default"; /* poor default */
 466 #else
 467           if (dirname == NULL || dirname[0] == '\0')
 468             {
 469               extern char *getlogin __P ((void));
 470               extern int getlogin_r __P ((char *, size_t));
 471               int success;
 472
 473 #if defined HAVE_GETLOGIN_R || defined _LIBC
 474               size_t buflen = sysconf (_SC_LOGIN_NAME_MAX) + 1;
 475               char *name;
 476
 477               if (buflen == 0)
 478                 /* `sysconf' does not support _SC_LOGIN_NAME_MAX.  Try
 479                    a moderate value.  */
 480                 buflen = 16;
 481               name = __alloca (buflen);
 482
 483               success = getlogin_r (name, buflen) >= 0;
 484 #else
 485               char *name;
 486               success = (name = getlogin ()) != NULL;
 487 #endif
 488               if (success)
 489                 {
 490 #if defined HAVE_GETPWNAM_R || defined _LIBC
 491                   size_t pwbuflen = sysconf (_SC_GETPW_R_SIZE_MAX);
 492                   char *pwtmpbuf;
 493                   struct passwd pwbuf, *p;
 494
 495                   pwtmpbuf = __alloca (pwbuflen);
 496
 497                   success = (__getpwnam_r (name, &pwbuf, pwtmpbuf,
 498                                            pwbuflen, &p) >= 0);
 499 #else
 500                   struct passwd *p = getpwnam (name);
 501                   success = p != NULL;
 502 #endif
 503                   if (success)
 504                     dirname = p->pw_dir;
 505                 }
 506             }
 507           if (dirname == NULL || dirname[0] == '\0')
 508             dirname = (char *) "~"; /* No luck.  */
 509 #endif /* WIN32 */
 510 #endif
 511         }
 512       else
 513         {
 514 #ifdef _AMIGA
 515           if (dirname == NULL || dirname[0] == '\0')
 516             dirname = "SYS:";
 517 #else
 518 #ifdef WIN32
 519           if (dirname == NULL || dirname[0] == '\0')
 520             dirname = "c:/users/default"; /* poor default */
 521 #else
 522           /* Look up specific user's home directory.  */
 523 #if defined HAVE_GETPWNAM_R || defined _LIBC
 524           size_t buflen = sysconf (_SC_GETPW_R_SIZE_MAX);
 525           char *pwtmpbuf = __alloca (buflen);
 526           struct passwd pwbuf, *p;
 527           if (__getpwnam_r (dirname + 1, &pwbuf, pwtmpbuf, buflen, &p) >= 0)
 528             dirname = p->pw_dir;
 529 #else
 530           struct passwd *p = getpwnam (dirname + 1);
 531           if (p != NULL)
 532             dirname = p->pw_dir;
 533 #endif
 534 #endif /* WIN32 */
 535 #endif
 536         }
 537     }
 538 #endif  /* Not VMS.  */
 539
 540   if (glob_pattern_p (dirname, !(flags & GLOB_NOESCAPE)))
 541     {
 542       /* The directory name contains metacharacters, so we
 543          have to glob for the directory, and then glob for
 544          the pattern in each directory found.  */
 545       glob_t dirs;
 546       register int i;
 547
 548       status = glob (dirname,
 549                      ((flags & (GLOB_ERR | GLOB_NOCHECK | GLOB_NOESCAPE)) |
 550                       GLOB_NOSORT),
 551                      errfunc, &dirs);
 552       if (status != 0)
 553         return status;
 554
 555       /* We have successfully globbed the preceding directory name.
 556          For each name we found, call glob_in_dir on it and FILENAME,
 557          appending the results to PGLOB.  */
 558       for (i = 0; i < dirs.gl_pathc; ++i)
 559         {
 560           int oldcount;
 561
 562 #ifdef  SHELL
 563           {
 564             /* Make globbing interruptible in the bash shell. */
 565             extern int interrupt_state;
 566
 567             if (interrupt_state)
 568               {
 569                 globfree (&dirs);
 570                 globfree (&files);
 571                 return GLOB_ABEND;
 572               }
 573           }
 574 #endif /* SHELL.  */
 575
 576           oldcount = pglob->gl_pathc;
 577           status = glob_in_dir (filename, dirs.gl_pathv[i],
 578                                 (flags | GLOB_APPEND) & ~GLOB_NOCHECK,
 579                                 errfunc, pglob);
 580           if (status == GLOB_NOMATCH)
 581             /* No matches in this directory.  Try the next.  */
 582             continue;
 583
 584           if (status != 0)
 585             {
 586               globfree (&dirs);
 587               globfree (pglob);
 588               return status;
 589             }
 590
 591           /* Stick the directory on the front of each name.  */
 592           if (prefix_array (dirs.gl_pathv[i],
 593                             &pglob->gl_pathv[oldcount],
 594                             pglob->gl_pathc - oldcount))
 595             {
 596               globfree (&dirs);
 597               globfree (pglob);
 598               return GLOB_NOSPACE;
 599             }
 600         }
 601
 602       flags |= GLOB_MAGCHAR;
 603
 604       if (pglob->gl_pathc == oldcount)
 605         /* No matches.  */
 606         if (flags & GLOB_NOCHECK)
 607           {
 608             size_t len = strlen (pattern) + 1;
 609             char *patcopy = (char *) malloc (len);
 610             if (patcopy == NULL)
 611               return GLOB_NOSPACE;
 612             memcpy (patcopy, pattern, len);
 613
 614             pglob->gl_pathv
 615               = (char **) realloc (pglob->gl_pathv,
 616                                    (pglob->gl_pathc +
 617                                     ((flags & GLOB_DOOFFS) ?
 618                                      pglob->gl_offs : 0) +
 619                                     1 + 1) *
 620                                    sizeof (char *));
 621             if (pglob->gl_pathv == NULL)
 622               {
 623                 free (patcopy);
 624                 return GLOB_NOSPACE;
 625               }
 626
 627             if (flags & GLOB_DOOFFS)
 628               while (pglob->gl_pathc < pglob->gl_offs)
 629                 pglob->gl_pathv[pglob->gl_pathc++] = NULL;
 630
 631             pglob->gl_pathv[pglob->gl_pathc++] = patcopy;
 632             pglob->gl_pathv[pglob->gl_pathc] = NULL;
 633             pglob->gl_flags = flags;
 634           }
 635         else
 636           return GLOB_NOMATCH;
 637     }
 638   else
 639     {
 640       status = glob_in_dir (filename, dirname, flags, errfunc, pglob);
 641       if (status != 0)
 642         return status;
 643
 644       if (dirlen > 0)
 645         {
 646           /* Stick the directory on the front of each name.  */
 647           if (prefix_array (dirname,
 648                             &pglob->gl_pathv[oldcount],
 649                             pglob->gl_pathc - oldcount))
 650             {
 651               globfree (pglob);
 652               return GLOB_NOSPACE;
 653             }
 654         }
 655     }
 656
 657   if (flags & GLOB_MARK)
 658     {
 659       /* Append slashes to directory names.  */
 660       int i;
 661       struct stat st;
 662       for (i = oldcount; i < pglob->gl_pathc; ++i)
 663         if (((flags & GLOB_ALTDIRFUNC) ?
 664              (*pglob->gl_stat) (pglob->gl_pathv[i], &st) :
 665              __stat (pglob->gl_pathv[i], &st)) == 0 &&
 666             S_ISDIR (st.st_mode))
 667           {
 668             size_t len = strlen (pglob->gl_pathv[i]) + 2;
 669             char *new = realloc (pglob->gl_pathv[i], len);
 670             if (new == NULL)
 671               {
 672                 globfree (pglob);
 673                 return GLOB_NOSPACE;
 674               }
 675             strcpy (&new[len - 2], "/");
 676             pglob->gl_pathv[i] = new;
 677           }
 678     }
 679
 680   if (!(flags & GLOB_NOSORT))
 681     /* Sort the vector.  */
 682     qsort ((__ptr_t) &pglob->gl_pathv[oldcount],
 683            pglob->gl_pathc - oldcount,
 684            sizeof (char *), collated_compare);
 685
 686   return 0;
 687 }
 688
 689
 690 /* Free storage allocated in PGLOB by a previous `glob' call.  */
 691 void
 692 globfree (pglob)
 693      register glob_t *pglob;
 694 {
 695   if (pglob->gl_pathv != NULL)
 696     {
 697       register int i;
 698       for (i = 0; i < pglob->gl_pathc; ++i)
 699         if (pglob->gl_pathv[i] != NULL)
 700           free ((__ptr_t) pglob->gl_pathv[i]);
 701       free ((__ptr_t) pglob->gl_pathv);
 702     }
 703 }
 704
 705
 706 /* Do a collated comparison of A and B.  */
 707 static int
 708 collated_compare (a, b)
 709      const __ptr_t a;
 710      const __ptr_t b;
 711 {
 712   const char *const s1 = *(const char *const * const) a;
 713   const char *const s2 = *(const char *const * const) b;
 714
 715   if (s1 == s2)
 716     return 0;
 717   if (s1 == NULL)
 718     return 1;
 719   if (s2 == NULL)
 720     return -1;
 721   return strcoll (s1, s2);
 722 }
 723
 724
 725 /* Prepend DIRNAME to each of N members of ARRAY, replacing ARRAY's
 726    elements in place.  Return nonzero if out of memory, zero if successful.
 727    A slash is inserted between DIRNAME and each elt of ARRAY,
 728    unless DIRNAME is just "/".  Each old element of ARRAY is freed.  */
 729 static int
 730 prefix_array (dirname, array, n)
 731      const char *dirname;
 732      char **array;
 733      size_t n;
 734 {
 735   register size_t i;
 736   size_t dirlen = strlen (dirname);
 737
 738   if (dirlen == 1 && dirname[0] == '/')
 739     /* DIRNAME is just "/", so normal prepending would get us "//foo".
 740        We want "/foo" instead, so don't prepend any chars from DIRNAME.  */
 741     dirlen = 0;
 742
 743   for (i = 0; i < n; ++i)
 744     {
 745       size_t eltlen = strlen (array[i]) + 1;
 746       char *new = (char *) malloc (dirlen + 1 + eltlen);
 747       if (new == NULL)
 748         {
 749           while (i > 0)
 750             free ((__ptr_t) array[--i]);
 751           return 1;
 752         }
 753
 754       memcpy (new, dirname, dirlen);
 755       new[dirlen] = '/';
 756       memcpy (&new[dirlen + 1], array[i], eltlen);
 757       free ((__ptr_t) array[i]);
 758       array[i] = new;
 759     }
 760
 761   return 0;
 762 }
 763
 764
 765 /* Return nonzero if PATTERN contains any metacharacters.
 766    Metacharacters can be quoted with backslashes if QUOTE is nonzero.  */
 767 static int
 768 glob_pattern_p (pattern, quote)
 769      const char *pattern;
 770      int quote;
 771 {
 772   register const char *p;
 773   int open = 0;
 774
 775   for (p = pattern; *p != '\0'; ++p)
 776     switch (*p)
 777       {
 778       case '?':
 779       case '*':
 780         return 1;
 781
 782       case '\\':
 783         if (quote && p[1] != '\0')
 784           ++p;
 785         break;
 786
 787       case '[':
 788         open = 1;
 789         break;
 790
 791       case ']':
 792         if (open)
 793           return 1;
 794         break;
 795       }
 796
 797   return 0;
 798 }
 799
 800
 801 /* Like `glob', but PATTERN is a final pathname component,
 802    and matches are searched for in DIRECTORY.
 803    The GLOB_NOSORT bit in FLAGS is ignored.  No sorting is ever done.
 804    The GLOB_APPEND flag is assumed to be set (always appends).  */
 805 static int
 806 glob_in_dir (pattern, directory, flags, errfunc, pglob)
 807      const char *pattern;
 808      const char *directory;
 809      int flags;
 810      int (*errfunc) __P ((const char *, int));
 811      glob_t *pglob;
 812 {
 813   __ptr_t stream;
 814
 815   struct globlink
 816     {
 817       struct globlink *next;
 818       char *name;
 819     };
 820   struct globlink *names = NULL;
 821   size_t nfound = 0;
 822
 823   if (!glob_pattern_p (pattern, !(flags & GLOB_NOESCAPE)))
 824     {
 825       stream = NULL;
 826       flags |= GLOB_NOCHECK;
 827     }
 828   else
 829     {
 830       flags |= GLOB_MAGCHAR;
 831
 832       stream = ((flags & GLOB_ALTDIRFUNC) ?
 833                 (*pglob->gl_opendir) (directory) :
 834                 (__ptr_t) opendir (directory));
 835       if (stream == NULL)
 836         {
 837           if ((errfunc != NULL && (*errfunc) (directory, errno)) ||
 838               (flags & GLOB_ERR))
 839             return GLOB_ABEND;
 840         }
 841       else
 842         while (1)
 843           {
 844             const char *name;
 845             size_t len;
 846             struct dirent dirbuf, *d;
 847             int success;
 848
 849             if (flags & GLOB_ALTDIRFUNC)
 850               {
 851                 d = (*pglob->gl_readdir) (stream);
 852                 success = d != NULL;
 853               }
 854             else
 855               {
 856 #if defined HAVE_READDIR_R || defined _LIBC
 857                 success = __readdir_r ((DIR *) stream, &dirbuf, &d) >= 0;
 858 #else
 859                 d = readdir ((DIR *) stream);
 860                 success = d != NULL;
 861 #endif
 862               }
 863             if (! success)
 864               break;
 865             if (! REAL_DIR_ENTRY (d))
 866               continue;
 867
 868             name = d->d_name;
 869
 870             if (fnmatch (pattern, name,
 871                          (!(flags & GLOB_PERIOD) ? FNM_PERIOD : 0) |
 872                          ((flags & GLOB_NOESCAPE) ? FNM_NOESCAPE : 0)
 873 #ifdef _AMIGA
 874                          | FNM_CASEFOLD
 875 #endif
 876                          ) == 0)
 877               {
 878                 struct globlink *new
 879                   = (struct globlink *) __alloca (sizeof (struct globlink));
 880                 len = NAMLEN (d);
 881                 new->name
 882                   = (char *) malloc (len + 1);
 883                 if (new->name == NULL)
 884                   goto memory_error;
 885                 memcpy ((__ptr_t) new->name, name, len);
 886                 new->name[len] = '\0';
 887                 new->next = names;
 888                 names = new;
 889                 ++nfound;
 890               }
 891           }
 892     }
 893
 894   if (nfound == 0 && (flags & GLOB_NOMAGIC) &&
 895       ! glob_pattern_p (pattern, !(flags & GLOB_NOESCAPE)))
 896     flags |= GLOB_NOCHECK;
 897
 898   if (nfound == 0 && (flags & GLOB_NOCHECK))
 899     {
 900       size_t len = strlen (pattern);
 901       nfound = 1;
 902       names = (struct globlink *) __alloca (sizeof (struct globlink));
 903       names->next = NULL;
 904       names->name = (char *) malloc (len + 1);
 905       if (names->name == NULL)
 906         goto memory_error;
 907       memcpy (names->name, pattern, len);
 908       names->name[len] = '\0';
 909     }
 910
 911   pglob->gl_pathv
 912     = (char **) realloc (pglob->gl_pathv,
 913                          (pglob->gl_pathc +
 914                           ((flags & GLOB_DOOFFS) ? pglob->gl_offs : 0) +
 915                           nfound + 1) *
 916                          sizeof (char *));
 917   if (pglob->gl_pathv == NULL)
 918     goto memory_error;
 919
 920   if (flags & GLOB_DOOFFS)
 921     while (pglob->gl_pathc < pglob->gl_offs)
 922       pglob->gl_pathv[pglob->gl_pathc++] = NULL;
 923
 924   for (; names != NULL; names = names->next)
 925     pglob->gl_pathv[pglob->gl_pathc++] = names->name;
 926   pglob->gl_pathv[pglob->gl_pathc] = NULL;
 927
 928   pglob->gl_flags = flags;
 929
 930   if (stream != NULL)
 931     {
 932       int save = errno;
 933       if (flags & GLOB_ALTDIRFUNC)
 934         (*pglob->gl_closedir) (stream);
 935       else
 936         closedir ((DIR *) stream);
 937       __set_errno (save);
 938     }
 939   return nfound == 0 ? GLOB_NOMATCH : 0;
 940
 941  memory_error:
 942   {
 943     int save = errno;
 944     if (flags & GLOB_ALTDIRFUNC)
 945       (*pglob->gl_closedir) (stream);
 946     else
 947       closedir ((DIR *) stream);
 948     __set_errno (save);
 949   }
 950   while (names != NULL)
 951     {
 952       if (names->name != NULL)
 953         free ((__ptr_t) names->name);
 954       names = names->next;
 955     }
 956   return GLOB_NOSPACE;
 957 }
 958
 959 #endif  /* Not ELIDE_CODE.  */