← Back to branch summary

~db-keen/tanzanite/rat

« back to all changes in this revision

Viewing changes to sources/libarchive-1.2.53/tar/tree.c

  • Committer: austin
  • Date: 2007-02-05 03:24:13 UTC
  • Revision ID: svn-v4:8b90d6ed-dc11-0410-98dd-e2d1db709ad4:rat/spikes/2006-05-13:45
Reorganizing the RAT project.

Show diffs side-by-side

added added

removed removed

Lines of Context:
sources/libarchive-1.2.53/tar/tree.c
 
1
/*-
 
2
 * Copyright (c) 2003-2004 Tim Kientzle
 
3
 * All rights reserved.
 
4
 *
 
5
 * Redistribution and use in source and binary forms, with or without
 
6
 * modification, are permitted provided that the following conditions
 
7
 * are met:
 
8
 * 1. Redistributions of source code must retain the above copyright
 
9
 *    notice, this list of conditions and the following disclaimer
 
10
 *    in this position and unchanged.
 
11
 * 2. Redistributions in binary form must reproduce the above copyright
 
12
 *    notice, this list of conditions and the following disclaimer in the
 
13
 *    documentation and/or other materials provided with the distribution.
 
14
 *
 
15
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
 
16
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 
17
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 
18
 * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
 
19
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 
20
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 
21
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 
22
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 
23
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 
24
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
25
 */
 
26
 
 
27
/*-
 
28
 * This is a new directory-walking system that addresses a number
 
29
 * of problems I've had with fts(3).  In particular, it has no
 
30
 * pathname-length limits (other than the size of 'int'), handles
 
31
 * deep logical traversals, uses considerably less memory, and has
 
32
 * an opaque interface (easier to modify in the future).
 
33
 *
 
34
 * Internally, it keeps a single list of "tree_entry" items that
 
35
 * represent filesystem objects that require further attention.
 
36
 * Non-directories are not kept in memory: they are pulled from
 
37
 * readdir(), returned to the client, then freed as soon as possible.
 
38
 * Any directory entry to be traversed gets pushed onto the stack.
 
39
 *
 
40
 * There is surprisingly little information that needs to be kept for
 
41
 * each item on the stack.  Just the name, depth (represented here as the
 
42
 * string length of the parent directory's pathname), and some markers
 
43
 * indicating how to get back to the parent (via chdir("..") for a
 
44
 * regular dir or via fchdir(2) for a symlink).
 
45
 */
 
46
#include "bsdtar_platform.h"
 
47
__FBSDID("$FreeBSD: src/usr.bin/tar/tree.c,v 1.4 2006/03/21 17:03:51 kientzle Exp $");
 
48
 
 
49
#include <sys/stat.h>
 
50
#include <dirent.h>
 
51
#include <errno.h>
 
52
#include <fcntl.h>
 
53
#include <stdlib.h>
 
54
#include <string.h>
 
55
#include <unistd.h>
 
56
 
 
57
#include "tree.h"
 
58
 
 
59
/*
 
60
 * TODO:
 
61
 *    1) Loop checking.
 
62
 *    3) Arbitrary logical traversals by closing/reopening intermediate fds.
 
63
 */
 
64
 
 
65
struct tree_entry {
 
66
        struct tree_entry *next;
 
67
        struct tree_entry *parent;
 
68
        char *name;
 
69
        size_t dirname_length;
 
70
        dev_t dev;
 
71
        ino_t ino;
 
72
        int fd;
 
73
        int flags;
 
74
};
 
75
 
 
76
/* Definitions for tree_entry.flags bitmap. */
 
77
#define isDir 1 /* This entry is a regular directory. */
 
78
#define isDirLink 2 /* This entry is a symbolic link to a directory. */
 
79
#define needsPreVisit 4 /* This entry needs to be previsited. */
 
80
#define needsPostVisit 8 /* This entry needs to be postvisited. */
 
81
 
 
82
/*
 
83
 * Local data for this package.
 
84
 */
 
85
struct tree {
 
86
        struct tree_entry       *stack;
 
87
        struct tree_entry       *current;
 
88
        DIR     *d;
 
89
        int      initialDirFd;
 
90
        int      flags;
 
91
        int      visit_type;
 
92
        int      tree_errno; /* Error code from last failed operation. */
 
93
 
 
94
        char    *buff;
 
95
        const char      *basename;
 
96
        size_t   buff_length;
 
97
        size_t   path_length;
 
98
        size_t   dirname_length;
 
99
 
 
100
        int      depth;
 
101
        int      openCount;
 
102
        int      maxOpenCount;
 
103
 
 
104
        struct stat     lst;
 
105
        struct stat     st;
 
106
};
 
107
 
 
108
/* Definitions for tree.flags bitmap. */
 
109
#define needsReturn 8  /* Marks first entry as not having been returned yet. */
 
110
#define hasStat 16  /* The st entry is set. */
 
111
#define hasLstat 32 /* The lst entry is set. */
 
112
 
 
113
 
 
114
#ifdef HAVE_DIRENT_D_NAMLEN
 
115
/* BSD extension; avoids need for a strlen() call. */
 
116
#define D_NAMELEN(dp)   (dp)->d_namlen
 
117
#else
 
118
#define D_NAMELEN(dp)   (strlen((dp)->d_name))
 
119
#endif
 
120
 
 
121
#if 0
 
122
#include <stdio.h>
 
123
void
 
124
tree_dump(struct tree *t, FILE *out)
 
125
{
 
126
        struct tree_entry *te;
 
127
 
 
128
        fprintf(out, "\tdepth: %d\n", t->depth);
 
129
        fprintf(out, "\tbuff: %s\n", t->buff);
 
130
        fprintf(out, "\tpwd: "); fflush(stdout); system("pwd");
 
131
        fprintf(out, "\taccess: %s\n", t->basename);
 
132
        fprintf(out, "\tstack:\n");
 
133
        for (te = t->stack; te != NULL; te = te->next) {
 
134
                fprintf(out, "\t\tte->name: %s%s%s\n", te->name,
 
135
                    te->flags & needsPreVisit ? "" : " *",
 
136
                    t->current == te ? " (current)" : "");
 
137
        }
 
138
}
 
139
#endif
 
140
 
 
141
/*
 
142
 * Add a directory path to the current stack.
 
143
 */
 
144
static void
 
145
tree_push(struct tree *t, const char *path)
 
146
{
 
147
        struct tree_entry *te;
 
148
 
 
149
        te = malloc(sizeof(*te));
 
150
        memset(te, 0, sizeof(*te));
 
151
        te->next = t->stack;
 
152
        t->stack = te;
 
153
        te->fd = -1;
 
154
        te->name = strdup(path);
 
155
        te->flags = needsPreVisit | needsPostVisit;
 
156
        te->dirname_length = t->dirname_length;
 
157
}
 
158
 
 
159
/*
 
160
 * Append a name to the current path.
 
161
 */
 
162
static void
 
163
tree_append(struct tree *t, const char *name, size_t name_length)
 
164
{
 
165
        char *p;
 
166
 
 
167
        if (t->buff != NULL)
 
168
                t->buff[t->dirname_length] = '\0';
 
169
        /* Strip trailing '/' from name, unless entire name is "/". */
 
170
        while (name_length > 1 && name[name_length - 1] == '/')
 
171
                name_length--;
 
172
 
 
173
        /* Resize pathname buffer as needed. */
 
174
        while (name_length + 1 + t->dirname_length >= t->buff_length) {
 
175
                t->buff_length *= 2;
 
176
                if (t->buff_length < 1024)
 
177
                        t->buff_length = 1024;
 
178
                t->buff = realloc(t->buff, t->buff_length);
 
179
        }
 
180
        p = t->buff + t->dirname_length;
 
181
        t->path_length = t->dirname_length + name_length;
 
182
        /* Add a separating '/' if it's needed. */
 
183
        if (t->dirname_length > 0 && p[-1] != '/') {
 
184
                *p++ = '/';
 
185
                t->path_length ++;
 
186
        }
 
187
        strncpy(p, name, name_length);
 
188
        p[name_length] = '\0';
 
189
        t->basename = p;
 
190
}
 
191
 
 
192
/*
 
193
 * Open a directory tree for traversal.
 
194
 */
 
195
struct tree *
 
196
tree_open(const char *path)
 
197
{
 
198
        struct tree *t;
 
199
 
 
200
        t = malloc(sizeof(*t));
 
201
        memset(t, 0, sizeof(*t));
 
202
        tree_append(t, path, strlen(path));
 
203
        t->initialDirFd = open(".", O_RDONLY);
 
204
        /*
 
205
         * During most of the traversal, items are set up and then
 
206
         * returned immediately from tree_next().  That doesn't work
 
207
         * for the very first entry, so we set a flag for this special
 
208
         * case.
 
209
         */
 
210
        t->flags = needsReturn;
 
211
        return (t);
 
212
}
 
213
 
 
214
/*
 
215
 * We've finished a directory; ascend back to the parent.
 
216
 */
 
217
static void
 
218
tree_ascend(struct tree *t)
 
219
{
 
220
        struct tree_entry *te;
 
221
 
 
222
        te = t->stack;
 
223
        t->depth--;
 
224
        if (te->flags & isDirLink) {
 
225
                fchdir(te->fd);
 
226
                close(te->fd);
 
227
                t->openCount--;
 
228
        } else {
 
229
                chdir("..");
 
230
        }
 
231
}
 
232
 
 
233
/*
 
234
 * Pop the working stack.
 
235
 */
 
236
static void
 
237
tree_pop(struct tree *t)
 
238
{
 
239
        struct tree_entry *te;
 
240
 
 
241
        t->buff[t->dirname_length] = '\0';
 
242
        if (t->stack == t->current && t->current != NULL)
 
243
                t->current = t->current->parent;
 
244
        te = t->stack;
 
245
        t->stack = te->next;
 
246
        t->dirname_length = te->dirname_length;
 
247
        t->basename = t->buff + t->dirname_length;
 
248
        /* Special case: starting dir doesn't skip leading '/'. */
 
249
        if (t->dirname_length > 0)
 
250
                t->basename++;
 
251
        free(te->name);
 
252
        free(te);
 
253
}
 
254
 
 
255
/*
 
256
 * Get the next item in the tree traversal.
 
257
 */
 
258
int
 
259
tree_next(struct tree *t)
 
260
{
 
261
        struct dirent *de = NULL;
 
262
 
 
263
        /* Handle the startup case by returning the initial entry. */
 
264
        if (t->flags & needsReturn) {
 
265
                t->flags &= ~needsReturn;
 
266
                return (t->visit_type = TREE_REGULAR);
 
267
        }
 
268
 
 
269
        while (t->stack != NULL) {
 
270
                /* If there's an open dir, get the next entry from there. */
 
271
                while (t->d != NULL) {
 
272
                        de = readdir(t->d);
 
273
                        if (de == NULL) {
 
274
                                closedir(t->d);
 
275
                                t->d = NULL;
 
276
                        } else if (de->d_name[0] == '.'
 
277
                            && de->d_name[1] == '\0') {
 
278
                                /* Skip '.' */
 
279
                        } else if (de->d_name[0] == '.'
 
280
                            && de->d_name[1] == '.'
 
281
                            && de->d_name[2] == '\0') {
 
282
                                /* Skip '..' */
 
283
                        } else {
 
284
                                /*
 
285
                                 * Append the path to the current path
 
286
                                 * and return it.
 
287
                                 */
 
288
                                tree_append(t, de->d_name, D_NAMELEN(de));
 
289
                                t->flags &= ~hasLstat;
 
290
                                t->flags &= ~hasStat;
 
291
                                return (t->visit_type = TREE_REGULAR);
 
292
                        }
 
293
                }
 
294
 
 
295
                /* If the current dir needs to be visited, set it up. */
 
296
                if (t->stack->flags & needsPreVisit) {
 
297
                        t->current = t->stack;
 
298
                        tree_append(t, t->stack->name, strlen(t->stack->name));
 
299
                        t->stack->flags &= ~needsPreVisit;
 
300
                        /* If it is a link, set up fd for the ascent. */
 
301
                        if (t->stack->flags & isDirLink) {
 
302
                                t->stack->fd = open(".", O_RDONLY);
 
303
                                t->openCount++;
 
304
                                if (t->openCount > t->maxOpenCount)
 
305
                                        t->maxOpenCount = t->openCount;
 
306
                        }
 
307
                        t->dirname_length = t->path_length;
 
308
                        if (chdir(t->stack->name) != 0) {
 
309
                                /* chdir() failed; return error */
 
310
                                tree_pop(t);
 
311
                                t->tree_errno = errno;
 
312
                                return (t->visit_type = TREE_ERROR_DIR);
 
313
                        }
 
314
                        t->depth++;
 
315
                        t->d = opendir(".");
 
316
                        if (t->d == NULL) {
 
317
                                tree_ascend(t); /* Undo "chdir" */
 
318
                                tree_pop(t);
 
319
                                t->tree_errno = errno;
 
320
                                return (t->visit_type = TREE_ERROR_DIR);
 
321
                        }
 
322
                        t->flags &= ~hasLstat;
 
323
                        t->flags &= ~hasStat;
 
324
                        t->basename = ".";
 
325
                        return (t->visit_type = TREE_POSTDESCENT);
 
326
                }
 
327
 
 
328
                /* We've done everything necessary for the top stack entry. */
 
329
                if (t->stack->flags & needsPostVisit) {
 
330
                        tree_ascend(t);
 
331
                        tree_pop(t);
 
332
                        t->flags &= ~hasLstat;
 
333
                        t->flags &= ~hasStat;
 
334
                        return (t->visit_type = TREE_POSTASCENT);
 
335
                }
 
336
        }
 
337
        return (t->visit_type = 0);
 
338
}
 
339
 
 
340
/*
 
341
 * Return error code.
 
342
 */
 
343
int
 
344
tree_errno(struct tree *t)
 
345
{
 
346
        return (t->tree_errno);
 
347
}
 
348
 
 
349
/*
 
350
 * Called by the client to mark the directory just returned from
 
351
 * tree_next() as needing to be visited.
 
352
 */
 
353
void
 
354
tree_descend(struct tree *t)
 
355
{
 
356
        if (t->visit_type != TREE_REGULAR)
 
357
                return;
 
358
 
 
359
        if (tree_current_is_physical_dir(t)) {
 
360
                tree_push(t, t->basename);
 
361
                t->stack->flags |= isDir;
 
362
        } else if (tree_current_is_dir(t)) {
 
363
                tree_push(t, t->basename);
 
364
                t->stack->flags |= isDirLink;
 
365
        }
 
366
}
 
367
 
 
368
/*
 
369
 * Get the stat() data for the entry just returned from tree_next().
 
370
 */
 
371
const struct stat *
 
372
tree_current_stat(struct tree *t)
 
373
{
 
374
        if (!(t->flags & hasStat)) {
 
375
                if (stat(t->basename, &t->st) != 0)
 
376
                        return NULL;
 
377
                t->flags |= hasStat;
 
378
        }
 
379
        return (&t->st);
 
380
}
 
381
 
 
382
/*
 
383
 * Get the lstat() data for the entry just returned from tree_next().
 
384
 */
 
385
const struct stat *
 
386
tree_current_lstat(struct tree *t)
 
387
{
 
388
        if (!(t->flags & hasLstat)) {
 
389
                if (lstat(t->basename, &t->lst) != 0)
 
390
                        return NULL;
 
391
                t->flags |= hasLstat;
 
392
        }
 
393
        return (&t->lst);
 
394
}
 
395
 
 
396
/*
 
397
 * Test whether current entry is a dir or dir link.
 
398
 */
 
399
int
 
400
tree_current_is_dir(struct tree *t)
 
401
{
 
402
        /* If we've already pulled stat(), just use that. */
 
403
        if (t->flags & hasStat)
 
404
                return (S_ISDIR(tree_current_stat(t)->st_mode));
 
405
 
 
406
        /* If we've already pulled lstat(), we may be able to use that. */
 
407
        if (t->flags & hasLstat) {
 
408
                /* If lstat() says it's a dir, it must be a dir. */
 
409
                if (S_ISDIR(tree_current_lstat(t)->st_mode))
 
410
                        return 1;
 
411
                /* If it's not a dir and not a link, we're done. */
 
412
                if (!S_ISLNK(tree_current_lstat(t)->st_mode))
 
413
                        return 0;
 
414
                /*
 
415
                 * If the above two tests fail, then it's a link, but
 
416
                 * we don't know whether it's a link to a dir or a
 
417
                 * non-dir.
 
418
                 */
 
419
        }
 
420
 
 
421
        /* TODO: Use a more efficient mechanism when available. */
 
422
        return (S_ISDIR(tree_current_stat(t)->st_mode));
 
423
}
 
424
 
 
425
/*
 
426
 * Test whether current entry is a physical directory.
 
427
 */
 
428
int
 
429
tree_current_is_physical_dir(struct tree *t)
 
430
{
 
431
        /* If we've already pulled lstat(), just use that. */
 
432
        if (t->flags & hasLstat)
 
433
                return (S_ISDIR(tree_current_lstat(t)->st_mode));
 
434
 
 
435
        /* TODO: Use a more efficient mechanism when available. */
 
436
        return (S_ISDIR(tree_current_lstat(t)->st_mode));
 
437
}
 
438
 
 
439
/*
 
440
 * Test whether current entry is a symbolic link.
 
441
 */
 
442
int
 
443
tree_current_is_physical_link(struct tree *t)
 
444
{
 
445
        /* If we've already pulled lstat(), just use that. */
 
446
        if (t->flags & hasLstat)
 
447
                return (S_ISLNK(tree_current_lstat(t)->st_mode));
 
448
 
 
449
        /* TODO: Use a more efficient mechanism when available. */
 
450
        return (S_ISLNK(tree_current_lstat(t)->st_mode));
 
451
}
 
452
 
 
453
/*
 
454
 * Return the access path for the entry just returned from tree_next().
 
455
 */
 
456
const char *
 
457
tree_current_access_path(struct tree *t)
 
458
{
 
459
        return (t->basename);
 
460
}
 
461
 
 
462
/*
 
463
 * Return the full path for the entry just returned from tree_next().
 
464
 */
 
465
const char *
 
466
tree_current_path(struct tree *t)
 
467
{
 
468
        return (t->buff);
 
469
}
 
470
 
 
471
/*
 
472
 * Return the length of the path for the entry just returned from tree_next().
 
473
 */
 
474
size_t
 
475
tree_current_pathlen(struct tree *t)
 
476
{
 
477
        return (t->path_length);
 
478
}
 
479
 
 
480
/*
 
481
 * Return the nesting depth of the entry just returned from tree_next().
 
482
 */
 
483
int
 
484
tree_current_depth(struct tree *t)
 
485
{
 
486
        return (t->depth);
 
487
}
 
488
 
 
489
/*
 
490
 * Terminate the traversal and release any resources.
 
491
 */
 
492
void
 
493
tree_close(struct tree *t)
 
494
{
 
495
        /* Release anything remaining in the stack. */
 
496
        while (t->stack != NULL)
 
497
                tree_pop(t);
 
498
        if (t->buff)
 
499
                free(t->buff);
 
500
        /* chdir() back to where we started. */
 
501
        if (t->initialDirFd >= 0) {
 
502
                fchdir(t->initialDirFd);
 
503
                close(t->initialDirFd);
 
504
                t->initialDirFd = -1;
 
505
        }
 
506
        free(t);
 
507
}