1 /**
2 * This file is part of the mingw-w64 runtime package.
3 * No warranty is given; refer to the file DISCLAIMER within this package.
4 */
5
6 #include <stdlib.h>
7 #include <unistd.h>
8 #include <malloc.h>
9 #include <string.h>
10 #include <errno.h>
11 #include <limits.h>
12 #include <fcntl.h>
13 #include <sys/param.h>
14 #include <sys/stat.h>
15 #include <dirent.h>
16 #include <ftw.h>
17
18 #ifdef IMPL_FTW64
19 #define stat stat64
20 #define nftw nftw64
21 #define ftw ftw64
22 #endif
23
24 typedef struct dir_data_t {
25 DIR *h;
26 char *buf;
27 } dir_data_t;
28
29 typedef struct node_t {
30 struct node_t *l, *r;
31 unsigned int colored : 1;
32 } node_t;
33
34 typedef struct ctx_t {
35 node_t *objs;
36 dir_data_t **dirs;
37 char *buf;
38 struct FTW ftw;
39 int (*fcb) (const char *, const struct stat *, int , struct FTW *);
40 size_t cur_dir, msz_dir, buf_sz;
41 int flags;
42 dev_t dev;
43 } ctx_t;
44
45 static int add_object (ctx_t *);
46 static int do_dir (ctx_t *, struct stat *, dir_data_t *);
47 static int do_entity (ctx_t *, dir_data_t *, const char *, size_t);
48 static int do_it (const char *, int, void *, int, int);
49
50 static int open_directory (ctx_t *, dir_data_t *);
51
52 static void
prepare_for_insert(int forced,node_t ** bp,node_t ** pp1,node_t ** pp2,int p1_c,int p2_c)53 prepare_for_insert (int forced, node_t **bp, node_t **pp1, node_t **pp2, int p1_c, int p2_c)
54 {
55 node_t *p1, *p2, **rp, **lp, *b = *bp;
56
57 rp = &(*bp)->r;
58 lp = &(*bp)->l;
59
60 if (!forced && ((*lp) == NULL || (*lp)->colored == 0 || (*rp) == NULL || (*rp)->colored == 0))
61 return;
62
63 b->colored = 1;
64
65 if (*rp)
66 (*rp)->colored = 0;
67
68 if (*lp)
69 (*lp)->colored = 0;
70
71 if (!pp1 || (*pp1)->colored == 0)
72 return;
73
74 p1 = *pp1;
75 p2 = *pp2;
76
77 if ((p1_c > 0) == (p2_c > 0))
78 {
79 *pp2 = *pp1;
80 p1->colored = 0;
81 p2->colored = 1;
82 *(p1_c < 0 ? &p2->l : &p2->r) = (p1_c < 0 ? p1->r : p1->l);
83 *(p1_c < 0 ? &p1->r : &p1->l) = p2;
84 return;
85 }
86
87 b->colored = 0;
88 p1->colored = p2->colored = 1;
89 *(p1_c < 0 ? &p1->l : &p1->r) = (p1_c < 0 ? *rp : *lp);
90 *(p1_c < 0 ? rp : lp) = p1;
91 *(p1_c < 0 ? &p2->r : &p2->l) = (p1_c < 0 ? *lp : *rp);
92 *(p1_c < 0 ? lp : rp) = p2;
93 *pp2 = b;
94 }
95
96 static int
add_object(ctx_t * ctx)97 add_object (ctx_t *ctx)
98 {
99 node_t **bp, **np, *b, *n, **pp1 = NULL, **pp2 = NULL;
100 int c = 0, p1_c = 0, p2_c = 0;
101
102 if (ctx->objs)
103 ctx->objs->colored = 0;
104
105 np = bp = &ctx->objs;
106
107 if (ctx->objs != NULL)
108 {
109 c = 1;
110
111 do
112 {
113 b = *bp;
114 prepare_for_insert (0, bp, pp1, pp2, p1_c, p2_c);
115 np = &b->r;
116
117 if (*np == NULL)
118 break;
119
120 pp2 = pp1;
121 p2_c = p1_c;
122 pp1 = bp;
123 p1_c = 1;
124 bp = np;
125 }
126 while (*np != NULL);
127 }
128
129 if (!(n = (node_t *) malloc (sizeof (node_t))))
130 return -1;
131
132 *np = n;
133 n->l = n->r = NULL;
134 n->colored = 1;
135
136 if (np != bp)
137 prepare_for_insert (1, np, bp, pp1, c, p1_c);
138
139 return 0;
140 }
141
142 static int
open_directory(ctx_t * ctx,dir_data_t * dirp)143 open_directory (ctx_t *ctx, dir_data_t *dirp)
144 {
145 DIR *st;
146 struct dirent *d;
147 char *buf, *h;
148 size_t cur_sz, buf_sz, sz;
149 int sv_e, ret = 0;
150
151 if (ctx->dirs[ctx->cur_dir] != NULL)
152 {
153 if (!(buf = malloc (1024)))
154 return -1;
155
156 st = ctx->dirs[ctx->cur_dir]->h;
157
158 buf_sz = 1024;
159 cur_sz = 0;
160
161 while ((d = readdir (st)) != NULL)
162 {
163 sz = strlen (d->d_name);
164
165 if ((cur_sz + sz + 2) >= buf_sz)
166 {
167 buf_sz += ((2 * sz) < 1024 ? 1024 : (2 * sz));
168 if (!(h = (char *) realloc (buf, buf_sz)))
169 {
170 sv_e = errno;
171 free (buf);
172 errno = (sv_e);
173
174 return -1;
175 }
176
177 buf = h;
178 }
179
180 *((char *) memcpy (buf + cur_sz, d->d_name, sz) + sz) = 0;
181 cur_sz += sz + 1;
182 }
183
184 buf[cur_sz++] = 0;
185
186 ctx->dirs[ctx->cur_dir]->buf = realloc (buf, cur_sz);
187
188 if (ctx->dirs[ctx->cur_dir]->buf == NULL)
189 {
190 sv_e = errno;
191 free (buf);
192 errno = sv_e;
193 ret = -1;
194 }
195 else
196 {
197 closedir (st);
198
199 ctx->dirs[ctx->cur_dir]->h = NULL;
200 ctx->dirs[ctx->cur_dir] = NULL;
201 }
202 }
203
204 if (!ret)
205 {
206 dirp->h = opendir (ctx->buf);
207
208 if (dirp->h == NULL)
209 ret = -1;
210 else
211 {
212 dirp->buf = NULL;
213 ctx->dirs[ctx->cur_dir] = dirp;
214 ctx->cur_dir += 1;
215
216 if (ctx->cur_dir == ctx->msz_dir)
217 ctx->cur_dir = 0;
218 }
219 }
220
221 return ret;
222 }
223
224
225 static int
do_entity(ctx_t * ctx,dir_data_t * dir,const char * name,size_t namlen)226 do_entity (ctx_t *ctx, dir_data_t *dir, const char *name, size_t namlen)
227 {
228 struct stat st;
229 char *h;
230 size_t cnt_sz;
231 int ret = 0, flag = 0;
232
233 if (name[0] == '.' && (name[1] == 0 || (name[1] == '.' && name[2] == 0)))
234 return 0;
235
236 cnt_sz = ctx->ftw.base + namlen + 2;
237
238 if (ctx->buf_sz < cnt_sz)
239 {
240 ctx->buf_sz = cnt_sz * 2;
241
242 if (!(h = (char *) realloc (ctx->buf, ctx->buf_sz)))
243 return -1;
244
245 ctx->buf = h;
246 }
247
248 *((char *) memcpy (ctx->buf + ctx->ftw.base, name, namlen) + namlen) = 0;
249
250 name = ctx->buf;
251
252 if (stat (name, &st) < 0)
253 {
254 if (errno != EACCES && errno != ENOENT)
255 ret = -1;
256 else
257 flag = FTW_NS;
258
259 if (!(ctx->flags & FTW_PHYS))
260 stat (name, &st);
261 }
262 else
263 flag = (S_ISDIR (st.st_mode) ? FTW_D : FTW_F);
264
265 if (!ret && (flag == FTW_NS || !(ctx->flags & FTW_MOUNT) || st.st_dev == ctx->dev))
266 {
267 if (flag == FTW_D)
268 {
269 if ((ctx->flags & FTW_PHYS) || !(ret = add_object (ctx)))
270 ret = do_dir (ctx, &st, dir);
271 }
272 else
273 ret = (*ctx->fcb) (ctx->buf, &st, flag, &ctx->ftw);
274 }
275
276 if ((ctx->flags & FTW_ACTIONRETVAL) && ret == FTW_SKIP_SUBTREE)
277 ret = 0;
278
279 return ret;
280 }
281
282
283 static int
do_dir(ctx_t * ctx,struct stat * st,__UNUSED_PARAM (dir_data_t * old_dir))284 do_dir (ctx_t *ctx, struct stat *st, __UNUSED_PARAM(dir_data_t *old_dir))
285 {
286 dir_data_t dir;
287 struct dirent *d;
288 char *startp, *runp, *endp;
289 int sv_e, ret, previous_base = ctx->ftw.base;
290
291 if ((ret = open_directory (ctx, &dir)) != 0)
292 {
293 if (errno == EACCES)
294 ret = (*ctx->fcb) (ctx->buf, st, FTW_DNR, &ctx->ftw);
295
296 return ret;
297 }
298
299 if (!(ctx->flags & FTW_DEPTH) && (ret = (*ctx->fcb) (ctx->buf, st, FTW_D, &ctx->ftw)) != 0)
300 {
301 sv_e = errno;
302 closedir (dir.h);
303 errno = sv_e;
304
305 if (ctx->cur_dir-- == 0)
306 ctx->cur_dir = ctx->msz_dir - 1;
307
308 ctx->dirs[ctx->cur_dir] = NULL;
309
310 return ret;
311 }
312
313 ctx->ftw.level += 1;
314 startp = memchr (ctx->buf, 0, 1024);
315
316 if (startp[-1] != '/')
317 *startp++ = '/';
318
319 ctx->ftw.base = (startp - ctx->buf);
320
321 while (dir.h != NULL && (d = readdir (dir.h)) != NULL
322 && !(ret = do_entity (ctx, &dir, d->d_name, strlen (d->d_name))))
323 ;
324
325 if (dir.h != NULL)
326 {
327 sv_e = errno;
328 closedir (dir.h);
329 errno = sv_e;
330
331 if (ctx->cur_dir-- == 0)
332 ctx->cur_dir = ctx->msz_dir - 1;
333
334 ctx->dirs[ctx->cur_dir] = NULL;
335 }
336 else
337 {
338 runp = dir.buf;
339
340 while (!ret && *runp != 0)
341 {
342 endp = strchr (runp, 0);
343 ret = do_entity (ctx, &dir, runp, endp - runp);
344 runp = endp + 1;
345 }
346
347 sv_e = errno;
348 free (dir.buf);
349 errno = sv_e;
350 }
351
352 if ((ctx->flags & FTW_ACTIONRETVAL) && ret == FTW_SKIP_SIBLINGS)
353 ret = 0;
354
355 ctx->buf[ctx->ftw.base - 1] = 0;
356 ctx->ftw.level -= 1;
357 ctx->ftw.base = previous_base;
358
359 if (!ret && (ctx->flags & FTW_DEPTH))
360 ret = (*ctx->fcb) (ctx->buf, st, FTW_DP, &ctx->ftw);
361
362 return ret;
363 }
364
365 static void
free_objs(node_t * r)366 free_objs (node_t *r)
367 {
368 if (r->l)
369 free_objs (r->l);
370
371 if (r->r)
372 free_objs (r->r);
373
374 free (r);
375 }
376
377 static int
do_it(const char * dir,__UNUSED_PARAM (int is_nftw),void * fcb,int descriptors,int flags)378 do_it (const char *dir, __UNUSED_PARAM(int is_nftw), void *fcb, int descriptors, int flags)
379 {
380 struct ctx_t ctx;
381 struct stat st;
382 int ret = 0;
383 int sv_e;
384 char *cp;
385
386 if (dir[0] == 0)
387 {
388 errno = (ENOENT);
389 return -1;
390 }
391
392 ctx.msz_dir = descriptors < 1 ? 1 : descriptors;
393 ctx.cur_dir = 0;
394 ctx.dirs = (dir_data_t **) alloca (ctx.msz_dir * sizeof (dir_data_t *));
395 memset (ctx.dirs, 0, ctx.msz_dir * sizeof (dir_data_t *));
396
397 ctx.buf_sz = 2 * strlen (dir);
398
399 if (ctx.buf_sz <= 1024)
400 ctx.buf_sz = 1024;
401
402 ctx.buf = (char *) malloc (ctx.buf_sz);
403
404 if (ctx.buf == NULL)
405 return -1;
406
407 cp = strcpy (ctx.buf, dir) + strlen (dir);
408
409 while (cp > (ctx.buf + 1) && cp[-1] == '/')
410 --cp;
411
412 *cp = 0;
413
414 while (cp > ctx.buf && cp[-1] != '/')
415 --cp;
416
417 ctx.ftw.level = 0;
418 ctx.ftw.base = cp - ctx.buf;
419 ctx.flags = flags;
420 ctx.fcb = (int (*) (const char *, const struct stat *, int , struct FTW *)) fcb;
421 ctx.objs = NULL;
422
423 if (!ret)
424 {
425 if (stat (ctx.buf, &st) < 0)
426 ret = -1;
427 else if (S_ISDIR (st.st_mode))
428 {
429 ctx.dev = st.st_dev;
430
431 if (!(flags & FTW_PHYS))
432 ret = add_object (&ctx);
433
434 if (!ret)
435 ret = do_dir (&ctx, &st, NULL);
436 }
437 else
438 ret = (*ctx.fcb) (ctx.buf, &st, FTW_F, &ctx.ftw);
439
440 if ((flags & FTW_ACTIONRETVAL) && (ret == FTW_SKIP_SUBTREE || ret == FTW_SKIP_SIBLINGS))
441 ret = 0;
442 }
443
444 sv_e = errno;
445 if (ctx.objs)
446 free_objs (ctx.objs);
447 free (ctx.buf);
448 errno = (sv_e);
449
450 return ret;
451 }
452
453 int
ftw(const char * path,int (* fcb)(const char *,const struct stat *,int),int descriptors)454 ftw (const char *path, int (*fcb) (const char *, const struct stat *, int), int descriptors)
455 {
456 return do_it (path, 0, fcb, descriptors, 0);
457 }
458
459 int
nftw(const char * path,int (* fcb)(const char *,const struct stat *,int,struct FTW *),int descriptors,int flags)460 nftw (const char *path, int (*fcb) (const char *, const struct stat *, int , struct FTW *), int descriptors, int flags)
461 {
462 return do_it (path, 1, fcb, descriptors, flags);
463 }
464