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