Branch data Line data Source code
1 : : /*
2 : : * libdpkg - Debian packaging suite library routines
3 : : * treewalk.c - directory tree walk support
4 : : *
5 : : * Copyright © 2013-2016 Guillem Jover <guillem@debian.org>
6 : : *
7 : : * This is free software; you can redistribute it and/or modify
8 : : * it under the terms of the GNU General Public License as published by
9 : : * the Free Software Foundation; either version 2 of the License, or
10 : : * (at your option) any later version.
11 : : *
12 : : * This is distributed in the hope that it will be useful,
13 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 : : * GNU General Public License for more details.
16 : : *
17 : : * You should have received a copy of the GNU General Public License
18 : : * along with this program. If not, see <https://www.gnu.org/licenses/>.
19 : : */
20 : :
21 : : #include <config.h>
22 : : #include <compat.h>
23 : :
24 : : #include <sys/stat.h>
25 : : #include <sys/types.h>
26 : : #include <dirent.h>
27 : : #include <string.h>
28 : : #include <stdbool.h>
29 : : #include <stdio.h>
30 : : #include <stdlib.h>
31 : :
32 : : #include <dpkg/dpkg.h>
33 : : #include <dpkg/i18n.h>
34 : : #include <dpkg/treewalk.h>
35 : :
36 : : /* treenode functions. */
37 : :
38 : : typedef int treewalk_stat_func(const char *pathname, struct stat *st);
39 : :
40 : : struct treenode {
41 : : struct treenode *up; /* Parent dir. */
42 : : struct treenode *next; /* Next node in dir. */
43 : : struct treenode **down; /* Dir contents. */
44 : :
45 : : char *pathname; /* Node pathname. */
46 : : char *virtname; /* Node virtname. */
47 : : char *name; /* Node name. */
48 : :
49 : : struct stat *stat; /* Node metadata. */
50 : : mode_t mode;
51 : :
52 : : size_t pathname_len; /* Node pathname length. */
53 : :
54 : : size_t down_used; /* Number of used nodes in dir. */
55 : : size_t down_size; /* Number of allocated nodes in dir. */
56 : : };
57 : :
58 : : static inline struct treenode *
59 : 216 : treenode_alloc(void)
60 : : {
61 : 216 : return m_calloc(1, sizeof(struct treenode));
62 : : }
63 : :
64 : : static struct treenode *
65 : 38 : treenode_root_new(const char *rootdir)
66 : : {
67 : : struct treenode *node;
68 : :
69 : 38 : node = treenode_alloc();
70 : 38 : node->up = NULL;
71 : 38 : node->pathname = m_strdup(rootdir);
72 : 38 : node->pathname_len = strlen(node->pathname);
73 : 38 : node->virtname = node->pathname + node->pathname_len;
74 : 38 : node->name = strrchr(node->pathname, '/');
75 [ + + ]: 38 : if (node->name == NULL)
76 : 18 : node->name = node->pathname;
77 : : else
78 : 20 : node->name++;
79 : :
80 : 38 : return node;
81 : : }
82 : :
83 : : static struct treenode *
84 : 178 : treenode_node_new(struct treenode *root, struct treenode *dir, const char *name)
85 : : {
86 : : struct treenode *node;
87 : :
88 : 178 : node = treenode_alloc();
89 : 178 : node->up = dir;
90 : :
91 : 178 : node->pathname = str_fmt("%s/%s", node->up->pathname, name);
92 : 178 : node->pathname_len = strlen(node->pathname);
93 : 178 : node->virtname = node->pathname + root->pathname_len + 1;
94 : 178 : node->name = node->pathname + node->up->pathname_len + 1;
95 : :
96 : 178 : return node;
97 : : }
98 : :
99 : : static void
100 : 111 : treenode_stat(struct treenode *node, treewalk_stat_func *stat_func)
101 : : {
102 [ - + ]: 111 : if (node->stat)
103 : 0 : return;
104 : :
105 : 111 : node->stat = m_malloc(sizeof(*node->stat));
106 : :
107 [ - + ]: 111 : if (stat_func(node->pathname, node->stat) < 0)
108 : 0 : ohshite(_("cannot stat pathname '%s'"), node->pathname);
109 : :
110 : 111 : node->mode = node->stat->st_mode;
111 : : }
112 : :
113 : : static mode_t
114 : 178 : dirent_to_mode_type(struct dirent *e)
115 : : {
116 : : #ifdef _DIRENT_HAVE_D_TYPE
117 [ + + + - : 178 : switch (e->d_type) {
- - - - ]
118 : 105 : case DT_REG:
119 : 105 : return S_IFREG;
120 : 67 : case DT_DIR:
121 : 67 : return S_IFDIR;
122 : 6 : case DT_LNK:
123 : 6 : return S_IFLNK;
124 : 0 : case DT_CHR:
125 : 0 : return S_IFCHR;
126 : 0 : case DT_BLK:
127 : 0 : return S_IFBLK;
128 : 0 : case DT_FIFO:
129 : 0 : return S_IFIFO;
130 : 0 : case DT_SOCK:
131 : 0 : return S_IFSOCK;
132 : 0 : case DT_UNKNOWN:
133 : : default:
134 : 0 : return 0;
135 : : }
136 : : #else
137 : : return 0;
138 : : #endif
139 : : }
140 : :
141 : : static void
142 : 178 : treenode_stat_shallow(struct treenode *node, struct dirent *e,
143 : : treewalk_stat_func *stat_func)
144 : : {
145 : : mode_t mode;
146 : :
147 : 178 : mode = dirent_to_mode_type(e);
148 [ + - + + : 178 : if (mode == 0 || S_ISDIR(mode) || S_ISLNK(mode))
+ + ]
149 : 73 : treenode_stat(node, stat_func);
150 : : else
151 : 105 : node->mode |= mode;
152 : 178 : }
153 : :
154 : : const char *
155 : 95 : treenode_get_name(struct treenode *node)
156 : : {
157 : 95 : return node->name;
158 : : }
159 : :
160 : : const char *
161 : 242 : treenode_get_pathname(struct treenode *node)
162 : : {
163 : 242 : return node->pathname;
164 : : }
165 : :
166 : : const char *
167 : 215 : treenode_get_virtname(struct treenode *node)
168 : : {
169 : 215 : return node->virtname;
170 : : }
171 : :
172 : : mode_t
173 : 136 : treenode_get_mode(struct treenode *node)
174 : : {
175 : 136 : return node->mode;
176 : : }
177 : :
178 : : struct stat *
179 : 0 : treenode_get_stat(struct treenode *node)
180 : : {
181 : 0 : treenode_stat(node, lstat);
182 : 0 : return node->stat;
183 : : }
184 : :
185 : : struct treenode *
186 : 0 : treenode_get_parent(struct treenode *node)
187 : : {
188 : 0 : return node->up;
189 : : }
190 : :
191 : : static inline bool
192 : 253 : treenode_is_dir(struct treenode *node)
193 : : {
194 [ + - + + ]: 253 : return node && S_ISDIR(node->mode);
195 : : }
196 : :
197 : : static void
198 : 99 : treenode_resize_down(struct treenode *node)
199 : : {
200 : : size_t new_size;
201 : :
202 [ - + ]: 99 : if (node->down_size)
203 : 0 : node->down_size *= 2;
204 [ + + ]: 99 : else if (node->stat->st_nlink > 4)
205 : 7 : node->down_size = node->stat->st_nlink * 2;
206 : : else
207 : 92 : node->down_size = 8;
208 : :
209 : 99 : new_size = node->down_size * sizeof(*node);
210 : 99 : node->down = m_realloc(node->down, new_size);
211 : 99 : }
212 : :
213 : : static int
214 : 105 : treenode_cmp(const void *a, const void *b)
215 : : {
216 : 210 : return strcmp((*(const struct treenode **)a)->name,
217 : 105 : (*(const struct treenode **)b)->name);
218 : : }
219 : :
220 : : static void
221 : 99 : treenode_sort_down(struct treenode *dir)
222 : : {
223 : : size_t i;
224 : :
225 : 99 : qsort(dir->down, dir->down_used, sizeof(struct treenode *), treenode_cmp);
226 : :
227 : : /* Relink the nodes. */
228 [ + + ]: 178 : for (i = 0; i < dir->down_used - 1; i++)
229 : 79 : dir->down[i]->next = dir->down[i + 1];
230 : 99 : dir->down[i]->next = NULL;
231 : 99 : }
232 : :
233 : : static void
234 : 104 : treenode_fill_down(struct treenode *root, struct treenode *dir,
235 : : enum treewalk_options options)
236 : : {
237 : : DIR *d;
238 : : struct dirent *e;
239 : : treewalk_stat_func *stat_func;
240 : :
241 [ - + ]: 104 : if (options & TREEWALK_FOLLOW_LINKS)
242 : 0 : stat_func = stat;
243 : : else
244 : 104 : stat_func = lstat;
245 : :
246 : 104 : d = opendir(dir->pathname);
247 [ - + ]: 104 : if (!d)
248 : 0 : ohshite(_("cannot open directory '%s'"), dir->pathname);
249 : :
250 [ + + ]: 490 : while ((e = readdir(d)) != NULL) {
251 : : struct treenode *node;
252 : :
253 [ + + ]: 386 : if (strcmp(e->d_name, ".") == 0 ||
254 [ + + ]: 282 : strcmp(e->d_name, "..") == 0)
255 : 208 : continue;
256 : :
257 [ + + ]: 178 : if (dir->down_used >= dir->down_size)
258 : 99 : treenode_resize_down(dir);
259 : :
260 : 178 : node = treenode_node_new(root, dir, e->d_name);
261 [ - + ]: 178 : if (options & TREEWALK_FORCE_STAT)
262 : 0 : treenode_stat(node, stat_func);
263 : : else
264 : 178 : treenode_stat_shallow(node, e, stat_func);
265 : :
266 : 178 : dir->down[dir->down_used] = node;
267 : 178 : dir->down_used++;
268 : : }
269 : :
270 : 104 : closedir(d);
271 : 104 : }
272 : :
273 : : static void
274 : 213 : treenode_free_node(struct treenode *node)
275 : : {
276 : 213 : free(node->pathname);
277 : 213 : free(node->stat);
278 : 213 : free(node);
279 : 213 : }
280 : :
281 : : static void
282 : 103 : treenode_free_down(struct treenode *node)
283 : : {
284 : : size_t i;
285 : :
286 [ + + ]: 103 : if (!node->down_size)
287 : 5 : return;
288 : :
289 [ + + ]: 274 : for (i = 0; i < node->down_used; i++)
290 : 176 : treenode_free_node(node->down[i]);
291 : 98 : free(node->down);
292 : : }
293 : :
294 : :
295 : : /* treeroot functions. */
296 : :
297 : : struct treeroot {
298 : : struct treenode *rootnode;
299 : :
300 : : struct treenode *curdir;
301 : : struct treenode *curnode;
302 : :
303 : : enum treewalk_options options;
304 : : struct treewalk_funcs func;
305 : : };
306 : :
307 : : static inline void
308 : 154 : treeroot_set_curdir(struct treeroot *tree, struct treenode *node)
309 : : {
310 : 154 : tree->curdir = node;
311 : 154 : }
312 : :
313 : : static inline void
314 : 253 : treeroot_set_curnode(struct treeroot *tree, struct treenode *node)
315 : : {
316 : 253 : tree->curnode = node;
317 : 253 : }
318 : :
319 : : static bool
320 : 201 : treeroot_skip_node(struct treeroot *tree, struct treenode *node)
321 : : {
322 [ + + ]: 201 : if (tree->func.skip)
323 : 147 : return tree->func.skip(node);
324 : :
325 : 54 : return false;
326 : : }
327 : :
328 : : static void
329 : 104 : treeroot_fill_node(struct treeroot *tree, struct treenode *dir)
330 : : {
331 : 104 : treenode_fill_down(tree->rootnode, dir, tree->options);
332 : 104 : }
333 : :
334 : : static void
335 : 104 : treeroot_sort_node(struct treeroot *tree, struct treenode *dir)
336 : : {
337 : : static struct treenode *down_empty[] = { NULL, NULL };
338 : :
339 [ + + ]: 104 : if (dir->down_used == 0)
340 : 5 : dir->down = down_empty;
341 [ - + ]: 99 : else if (tree->func.sort)
342 : 0 : tree->func.sort(dir);
343 : : else
344 : 99 : treenode_sort_down(dir);
345 : 104 : }
346 : :
347 : : static void
348 : 96 : treeroot_visit_node(struct treeroot *tree, struct treenode *node)
349 : : {
350 [ - + ]: 96 : if (tree->func.visit == NULL)
351 : 0 : return;
352 : :
353 [ + + ]: 96 : if (!treeroot_skip_node(tree, node))
354 : 95 : tree->func.visit(node);
355 : : }
356 : :
357 : : /**
358 : : * Open a new tree to be walked.
359 : : *
360 : : * @param rootdir The root directory to start walking the tree.
361 : : * @param options The options specifying how to walk the tree.
362 : : * @param func The functions callbacks.
363 : : */
364 : : struct treeroot *
365 : 38 : treewalk_open(const char *rootdir, enum treewalk_options options,
366 : : const struct treewalk_funcs *func)
367 : : {
368 : : struct treeroot *tree;
369 : : struct treenode *root;
370 : :
371 : 38 : tree = m_malloc(sizeof(*tree));
372 : :
373 : 38 : tree->options = options;
374 [ + + ]: 38 : if (func)
375 : 2 : tree->func = *func;
376 : : else
377 : 36 : tree->func = TREEWALK_OBJECT;
378 : :
379 : 38 : root = treenode_root_new(rootdir);
380 : 38 : treenode_stat(root, lstat);
381 : :
382 [ - + ]: 38 : if (!treenode_is_dir(root))
383 : 0 : ohshit(_("treewalk root %s is not a directory"), rootdir);
384 : :
385 : 38 : treeroot_set_curnode(tree, root);
386 : 38 : tree->rootnode = tree->curdir = root;
387 : :
388 : 38 : return tree;
389 : : }
390 : :
391 : : /**
392 : : * Return the current node.
393 : : *
394 : : * This function is only needed if you want to start walking the tree from
395 : : * the root node. With something like:
396 : : *
397 : : * @code
398 : : * struct treeroot *tree;
399 : : * struct treenode *node;
400 : : *
401 : : * tree = treewalk_open(...);
402 : : * for (node = treewalk_node(tree); node; node = treewalk_next(tree))
403 : : * visitor(node);
404 : : * treewalk_close(tree);
405 : : * @endcode
406 : : *
407 : : * @param tree The tree structure.
408 : : */
409 : : struct treenode *
410 : 38 : treewalk_node(struct treeroot *tree)
411 : : {
412 : 38 : return tree->curnode;
413 : : }
414 : :
415 : : /**
416 : : * Return the next node.
417 : : *
418 : : * This function works basically as an iterator. And will return NULL when
419 : : * the whole tree has been traversed. When starting it will skip the root
420 : : * node, so you might want to use treewalk_node() to get that, otherwise
421 : : * you could use it like this:
422 : : *
423 : : * @code
424 : : * struct treeroot *tree;
425 : : * struct treenode *node;
426 : : *
427 : : * tree = treewalk_open(...);
428 : : * while ((node = treewalk_next(tree))
429 : : * visitor(node);
430 : : * treewalk_close(tree);
431 : : * @endcode
432 : : *
433 : : * @param tree The tree structure.
434 : : */
435 : : struct treenode *
436 : 215 : treewalk_next(struct treeroot *tree)
437 : : {
438 : : struct treenode *node;
439 : :
440 : : /* Handle rootless trees, such as uninitialized or fully traversed. */
441 [ - + ]: 215 : if (tree->rootnode == NULL)
442 : 0 : return NULL;
443 : :
444 : 215 : node = tree->curnode;
445 : :
446 : : /* Handle end of tree. */
447 [ - + ]: 215 : if (node == NULL)
448 : 0 : return NULL;
449 : :
450 : : /* Get next node, descending or sidewide. */
451 [ + + + + ]: 319 : if (treenode_is_dir(node) && !treeroot_skip_node(tree, node)) {
452 : : struct treenode *dir;
453 : :
454 : 104 : treeroot_fill_node(tree, node);
455 : 104 : treeroot_sort_node(tree, node);
456 : 104 : treeroot_set_curdir(tree, node);
457 : :
458 : : /* Check for directory loops. */
459 [ + + ]: 267 : for (dir = node->up; dir; dir = dir->up) {
460 [ + - ]: 163 : if (dir->stat->st_dev == node->stat->st_dev &&
461 [ - + ]: 163 : dir->stat->st_ino == node->stat->st_ino)
462 : 0 : break;
463 : : }
464 : :
465 : : /* Skip directory loops. */
466 [ - + ]: 104 : if (dir)
467 : 0 : node = node->next;
468 : : else
469 : 104 : node = node->down[0];
470 : : } else {
471 : 111 : node = node->next;
472 : : }
473 : :
474 : : /* Back track node, ascending. */
475 [ + + ]: 260 : while (node == NULL) {
476 : 82 : struct treenode *olddir = tree->curdir;
477 : :
478 [ + + ]: 82 : if (tree->curdir->next) {
479 : : /* Next entry in the parent directory. */
480 : 29 : node = tree->curdir->next;
481 : 29 : treeroot_set_curdir(tree, olddir->up);
482 : 29 : treenode_free_down(olddir);
483 [ + + ]: 53 : } else if (tree->curdir->up) {
484 : : /* Next entry in the grand-parent directory. */
485 : 21 : node = tree->curdir->up->next;
486 : 21 : treeroot_set_curdir(tree, olddir->up->up);
487 : 21 : treenode_free_down(olddir);
488 : 21 : treenode_free_down(olddir->up);
489 : : } else {
490 : : /* Otherwise, we're in the rootnode. */
491 : 32 : treenode_free_down(olddir);
492 : 32 : treenode_free_node(olddir);
493 : 32 : break;
494 : : }
495 : :
496 [ + + ]: 50 : if (tree->curdir == NULL) {
497 : 5 : treenode_free_node(tree->rootnode);
498 : 5 : tree->rootnode = NULL;
499 : 5 : break;
500 : : }
501 : : }
502 : :
503 : 215 : treeroot_set_curnode(tree, node);
504 : :
505 : 215 : return node;
506 : : }
507 : :
508 : : /**
509 : : * Closes the tree being walked.
510 : : *
511 : : * It will free any resources previously allocated.
512 : : */
513 : : void
514 : 37 : treewalk_close(struct treeroot *tree)
515 : : {
516 : 37 : free(tree);
517 : 37 : }
518 : :
519 : : /**
520 : : * Tree walker.
521 : : *
522 : : * @param rootdir The root directory to start walking the tree.
523 : : * @param options The options specifying how to walk the tree.
524 : : * @param func The function callbacks.
525 : : */
526 : : int
527 : 2 : treewalk(const char *rootdir, enum treewalk_options options,
528 : : struct treewalk_funcs *func)
529 : : {
530 : : struct treeroot *tree;
531 : : struct treenode *node;
532 : :
533 : 2 : tree = treewalk_open(rootdir, options, func);
534 : :
535 : : /* Breath first visit. */
536 [ + + ]: 98 : for (node = treewalk_node(tree); node; node = treewalk_next(tree))
537 : 96 : treeroot_visit_node(tree, node);
538 : :
539 : 2 : treewalk_close(tree);
540 : :
541 : 2 : return 0;
542 : : }
|
