1 //
2 // Copyright(C) 2018 Simon Howard
3 //
4 // This program is free software; you can redistribute it and/or
5 // modify it under the terms of the GNU General Public License
6 // as published by the Free Software Foundation; either version 2
7 // of the License, or (at your option) any later version.
8 //
9 // This program is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU General Public License for more details.
13 //
14 //
15 // File globbing API. This allows the contents of the filesystem
16 // to be interrogated.
17 //
18
19 #include <stdlib.h>
20 #include <string.h>
21 #include <ctype.h>
22
23 #include "i_glob.h"
24 #include "m_misc.h"
25 #include "config.h"
26
27 #if defined(_MSC_VER)
28 // For Visual C++, we need to include the win_opendir module.
29 #include <win_opendir.h>
30 #include <sys/stat.h>
31 #define S_ISDIR(m) (((m)& S_IFMT) == S_IFDIR)
32 #elif defined(HAVE_DIRENT_H)
33 #include <dirent.h>
34 #include <sys/stat.h>
35 #elif defined(__WATCOMC__)
36 // Watcom has the same API in a different header.
37 #include <direct.h>
38 #else
39 #define NO_DIRENT_IMPLEMENTATION
40 #endif
41
42 #ifndef NO_DIRENT_IMPLEMENTATION
43
44 // Only the fields d_name and (as an XSI extension) d_ino are specified
45 // in POSIX.1. Other than Linux, the d_type field is available mainly
46 // only on BSD systems. The remaining fields are available on many, but
47 // not all systems.
IsDirectory(char * dir,struct dirent * de)48 static boolean IsDirectory(char *dir, struct dirent *de)
49 {
50 #if defined(_DIRENT_HAVE_D_TYPE)
51 if (de->d_type != DT_UNKNOWN && de->d_type != DT_LNK)
52 {
53 return de->d_type == DT_DIR;
54 }
55 else
56 #endif
57 {
58 char *filename;
59 struct stat sb;
60 int result;
61
62 filename = M_StringJoin(dir, DIR_SEPARATOR_S, de->d_name, NULL);
63 result = stat(filename, &sb);
64 free(filename);
65
66 if (result != 0)
67 {
68 return false;
69 }
70
71 return S_ISDIR(sb.st_mode);
72 }
73 }
74
75 struct glob_s
76 {
77 char **globs;
78 int num_globs;
79 int flags;
80 DIR *dir;
81 char *directory;
82 char *last_filename;
83 // These fields are only used when the GLOB_FLAG_SORTED flag is set:
84 char **filenames;
85 int filenames_len;
86 int next_index;
87 };
88
FreeStringList(char ** globs,int num_globs)89 static void FreeStringList(char **globs, int num_globs)
90 {
91 int i;
92 for (i = 0; i < num_globs; ++i)
93 {
94 free(globs[i]);
95 }
96 free(globs);
97 }
98
I_StartMultiGlob(const char * directory,int flags,const char * glob,...)99 glob_t *I_StartMultiGlob(const char *directory, int flags,
100 const char *glob, ...)
101 {
102 char **globs;
103 int num_globs;
104 glob_t *result;
105 va_list args;
106
107 globs = malloc(sizeof(char *));
108 if (globs == NULL)
109 {
110 return NULL;
111 }
112 globs[0] = M_StringDuplicate(glob);
113 num_globs = 1;
114
115 va_start(args, glob);
116 for (;;)
117 {
118 const char *arg = va_arg(args, const char *);
119 char **new_globs;
120
121 if (arg == NULL)
122 {
123 break;
124 }
125
126 new_globs = realloc(globs, sizeof(char *) * (num_globs + 1));
127 if (new_globs == NULL)
128 {
129 FreeStringList(globs, num_globs);
130 }
131 globs = new_globs;
132 globs[num_globs] = M_StringDuplicate(arg);
133 ++num_globs;
134 }
135 va_end(args);
136
137 result = malloc(sizeof(glob_t));
138 if (result == NULL)
139 {
140 FreeStringList(globs, num_globs);
141 return NULL;
142 }
143
144 result->dir = opendir(directory);
145 if (result->dir == NULL)
146 {
147 FreeStringList(globs, num_globs);
148 free(result);
149 return NULL;
150 }
151
152 result->directory = M_StringDuplicate(directory);
153 result->globs = globs;
154 result->num_globs = num_globs;
155 result->flags = flags;
156 result->last_filename = NULL;
157 result->filenames = NULL;
158 result->filenames_len = 0;
159 result->next_index = -1;
160 return result;
161 }
162
I_StartGlob(const char * directory,const char * glob,int flags)163 glob_t *I_StartGlob(const char *directory, const char *glob, int flags)
164 {
165 return I_StartMultiGlob(directory, flags, glob, NULL);
166 }
167
I_EndGlob(glob_t * glob)168 void I_EndGlob(glob_t *glob)
169 {
170 if (glob == NULL)
171 {
172 return;
173 }
174
175 FreeStringList(glob->globs, glob->num_globs);
176 FreeStringList(glob->filenames, glob->filenames_len);
177
178 free(glob->directory);
179 free(glob->last_filename);
180 (void) closedir(glob->dir);
181 free(glob);
182 }
183
MatchesGlob(const char * name,const char * glob,int flags)184 static boolean MatchesGlob(const char *name, const char *glob, int flags)
185 {
186 int n, g;
187
188 while (*glob != '\0')
189 {
190 n = *name;
191 g = *glob;
192
193 if ((flags & GLOB_FLAG_NOCASE) != 0)
194 {
195 n = tolower(n);
196 g = tolower(g);
197 }
198
199 if (g == '*')
200 {
201 // To handle *-matching we skip past the * and recurse
202 // to check each subsequent character in turn. If none
203 // match then the whole match is a failure.
204 while (*name != '\0')
205 {
206 if (MatchesGlob(name, glob + 1, flags))
207 {
208 return true;
209 }
210 ++name;
211 }
212 return glob[1] == '\0';
213 }
214 else if (g != '?' && n != g)
215 {
216 // For normal characters the name must match the glob,
217 // but for ? we don't care what the character is.
218 return false;
219 }
220
221 ++name;
222 ++glob;
223 }
224
225 // Match successful when glob and name end at the same time.
226 return *name == '\0';
227 }
228
MatchesAnyGlob(const char * name,glob_t * glob)229 static boolean MatchesAnyGlob(const char *name, glob_t *glob)
230 {
231 int i;
232
233 for (i = 0; i < glob->num_globs; ++i)
234 {
235 if (MatchesGlob(name, glob->globs[i], glob->flags))
236 {
237 return true;
238 }
239 }
240 return false;
241 }
242
NextGlob(glob_t * glob)243 static char *NextGlob(glob_t *glob)
244 {
245 struct dirent *de;
246
247 do
248 {
249 de = readdir(glob->dir);
250 if (de == NULL)
251 {
252 return NULL;
253 }
254 } while (IsDirectory(glob->directory, de)
255 || !MatchesAnyGlob(de->d_name, glob));
256
257 // Return the fully-qualified path, not just the bare filename.
258 return M_StringJoin(glob->directory, DIR_SEPARATOR_S, de->d_name, NULL);
259 }
260
ReadAllFilenames(glob_t * glob)261 static void ReadAllFilenames(glob_t *glob)
262 {
263 char *name;
264
265 glob->filenames = NULL;
266 glob->filenames_len = 0;
267 glob->next_index = 0;
268
269 for (;;)
270 {
271 name = NextGlob(glob);
272 if (name == NULL)
273 {
274 break;
275 }
276 glob->filenames = realloc(glob->filenames,
277 (glob->filenames_len + 1) * sizeof(char *));
278 glob->filenames[glob->filenames_len] = name;
279 ++glob->filenames_len;
280 }
281 }
282
SortFilenames(char ** filenames,int len,int flags)283 static void SortFilenames(char **filenames, int len, int flags)
284 {
285 char *pivot, *tmp;
286 int i, left_len, cmp;
287
288 if (len <= 1)
289 {
290 return;
291 }
292 pivot = filenames[len - 1];
293 left_len = 0;
294 for (i = 0; i < len-1; ++i)
295 {
296 if ((flags & GLOB_FLAG_NOCASE) != 0)
297 {
298 cmp = strcasecmp(filenames[i], pivot);
299 }
300 else
301 {
302 cmp = strcmp(filenames[i], pivot);
303 }
304
305 if (cmp < 0)
306 {
307 tmp = filenames[i];
308 filenames[i] = filenames[left_len];
309 filenames[left_len] = tmp;
310 ++left_len;
311 }
312 }
313 filenames[len - 1] = filenames[left_len];
314 filenames[left_len] = pivot;
315
316 SortFilenames(filenames, left_len, flags);
317 SortFilenames(&filenames[left_len + 1], len - left_len - 1, flags);
318 }
319
I_NextGlob(glob_t * glob)320 const char *I_NextGlob(glob_t *glob)
321 {
322 const char *result;
323
324 if (glob == NULL)
325 {
326 return NULL;
327 }
328
329 // In unsorted mode we just return the filenames as we read
330 // them back from the system API.
331 if ((glob->flags & GLOB_FLAG_SORTED) == 0)
332 {
333 free(glob->last_filename);
334 glob->last_filename = NextGlob(glob);
335 return glob->last_filename;
336 }
337
338 // In sorted mode we read the whole list of filenames into memory,
339 // sort them and return them one at a time.
340 if (glob->next_index < 0)
341 {
342 ReadAllFilenames(glob);
343 SortFilenames(glob->filenames, glob->filenames_len, glob->flags);
344 }
345 if (glob->next_index >= glob->filenames_len)
346 {
347 return NULL;
348 }
349 result = glob->filenames[glob->next_index];
350 ++glob->next_index;
351 return result;
352 }
353
354 #else /* #ifdef NO_DIRENT_IMPLEMENTATION */
355
356 #warning No native implementation of file globbing.
357
I_StartGlob(const char * directory,const char * glob,int flags)358 glob_t *I_StartGlob(const char *directory, const char *glob, int flags)
359 {
360 return NULL;
361 }
362
I_EndGlob(glob_t * glob)363 void I_EndGlob(glob_t *glob)
364 {
365 }
366
I_NextGlob(glob_t * glob)367 const char *I_NextGlob(glob_t *glob)
368 {
369 return "";
370 }
371
372 #endif /* #ifdef NO_DIRENT_IMPLEMENTATION */
373
374