mdw@git.distorted.org.uk Git - dpkg/blob - lib/dpkg/treewalk.c

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