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