git.sur5r.net Git - bacula/bacula/blob - bacula/src/lib/tree.c

   1 /*
   2  * Directory tree build/traverse routines
   3  *
   4  *    Kern Sibbald, June MMII
   5  *
   6 */
   7 /*
   8    Copyright (C) 2002 Kern Sibbald and John Walker
   9
  10    This program is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU General Public License as
  12    published by the Free Software Foundation; either version 2 of
  13    the License, or (at your option) any later version.
  14
  15    This program is distributed in the hope that it will be useful,
  16    but WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  18    General Public License for more details.
  19
  20    You should have received a copy of the GNU General Public
  21    License along with this program; if not, write to the Free
  22    Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  23    MA 02111-1307, USA.
  24
  25  */
  26
  27
  28 #include "bacula.h"
  29 #include "findlib/find.h"
  30 #include "findlib/system.h"
  31
  32 #ifndef MAXPATHLEN
  33 #define MAXPATHLEN 1000
  34 #endif
  35
  36 TREE_NODE *new_tree_node(int type)
  37 {
  38    TREE_NODE *node;
  39    int size;
  40
  41    if (type == TN_ROOT) {
  42       size = sizeof(TREE_ROOT);
  43    } else {
  44       size = sizeof(TREE_NODE);
  45    }
  46    node = (TREE_NODE *)malloc(size);
  47    memset(node, 0, size);
  48    node->type = type;
  49    return node;
  50 }
  51
  52 TREE_NODE *insert_tree_node(char *path, TREE_NODE *node, TREE_ROOT *root, TREE_NODE *parent)
  53 {
  54    char *p, *fname;
  55
  56    Dmsg1(100, "insert_tree_node: %s\n", path);
  57    p = strrchr(path, '/');
  58    if (!p) {
  59       Dmsg1(000, "No / found: %s\n", path);
  60       exit(1);
  61    }
  62    *p = 0;
  63    fname = p + 1;
  64    if (!parent) {
  65       parent = make_tree_path(path, root);
  66    }
  67    *p = '/';
  68    append_tree_node(fname, node, root, parent);
  69    Dmsg1(100, "insert_tree_node: parent=%s\n", parent->fname);
  70    return parent;
  71 }
  72
  73 TREE_NODE *make_tree_path(char *path, TREE_ROOT *root)
  74 {
  75    TREE_NODE *parent, *sibling;
  76    char *fname, *p;
  77
  78    Dmsg1(100, "make_tree_path: %s\n", path);
  79    if (!*path) {
  80       Dmsg0(100, "make_tree_path: parent=*root*\n");
  81       return (TREE_NODE *)root;
  82    }
  83    p = strrchr(path, '/');
  84    if (!p) {
  85       Dmsg1(000, "No / found: %s\n", path);
  86       exit(1);
  87    }
  88    *p = 0;
  89    fname = p + 1;
  90    /* Find parent */
  91    parent = make_tree_path(path, root);
  92    *p = '/';
  93    /* Is it already a sibling? */
  94    for (sibling=parent->sibling; sibling; sibling=sibling->sibling) {
  95       if (strcmp(sibling->fname, fname) == 0) {
  96          Dmsg1(100, "make_tree_path: found parent=%s\n", parent->fname);
  97          return parent;
  98       }
  99    }
 100    /* Must add */
 101    sibling = new_tree_node(TN_NEWDIR);
 102    append_tree_node(fname, sibling, root, parent);
 103    parent = sibling;
 104    Dmsg1(100, "make_tree_path: add parent=%s\n", parent->fname);
 105    return parent;
 106 }
 107
 108 /*
 109  *  Append sibling to parent's child chain
 110  */
 111 void append_tree_node(char *fname, TREE_NODE *node, TREE_ROOT *root, TREE_NODE *parent)
 112 {
 113    TREE_NODE *child;
 114
 115    Dmsg1(100, "append_tree_node: %s\n", fname);
 116    node->fname = bstrdup(fname);
 117    node->parent = parent;
 118    if (!parent->child) {
 119       parent->child = node;
 120       goto item_link;
 121    }
 122    for (child=parent->child; child->sibling; child=child->sibling)
 123       { }
 124    child->sibling = node;
 125
 126 item_link:
 127    if (!root->first) {
 128       root->first = node;
 129       root->last = node;
 130    } else {
 131       root->last->next = node;
 132       root->last = node;
 133    }
 134    return;
 135 }
 136
 137 TREE_NODE *first_tree_node(TREE_ROOT *root)
 138 {
 139    return root->first;
 140 }
 141
 142 TREE_NODE *next_tree_node(TREE_NODE *node)
 143 {
 144    return node->next;
 145 }
 146
 147
 148 void print_tree(char *path, TREE_NODE *tree)
 149 {
 150    char buf[MAXPATHLEN];
 151    char *termchr;
 152
 153    if (!tree) {
 154       return;
 155    }
 156    switch (tree->type) {
 157    case TN_DIR:
 158    case TN_NEWDIR:
 159       termchr = "/";
 160       break;
 161    case TN_ROOT:
 162    case TN_FILE:
 163    default:
 164       termchr = "";
 165       break;
 166    }
 167    Dmsg3(-1, "%s/%s%s\n", path, tree->fname, termchr);
 168    switch (tree->type) {
 169    case TN_FILE:
 170       break;
 171    case TN_DIR:
 172       sprintf(buf, "%s/%s", path, tree->fname);
 173       print_tree(buf, tree->child);
 174       break;
 175    case TN_ROOT:
 176       print_tree(path, tree->child);
 177       break;
 178    case TN_NEWDIR:
 179       sprintf(buf, "%s/%s", path, tree->fname);
 180       print_tree(buf, tree->child);
 181       break;
 182    default:
 183       Dmsg1(000, "Unknown node type %d\n", tree->type);
 184    }
 185    print_tree(path, tree->sibling);
 186    return;
 187 }
 188
 189 void free_tree(TREE_NODE *node)
 190 {
 191    if (!node) {
 192       return;
 193    }
 194    switch (node->type) {
 195    case TN_FILE:
 196       break;
 197    case TN_DIR:
 198    case TN_ROOT:
 199    case TN_NEWDIR:
 200       free_tree(node->child);
 201       break;
 202    default:
 203       Dmsg1(000, "Unknown node type %d\n", node->type);
 204       break;
 205    }
 206    free_tree(node->sibling);
 207    free(node->fname);
 208    free(node);
 209    return;
 210 }
 211
 212 int tree_getpath(TREE_NODE *node, char *buf, int buf_size)
 213 {
 214    if (!node) {
 215       buf[0] = 0;
 216       return 1;
 217    }
 218    tree_getpath(node->parent, buf, buf_size);
 219    strcat(buf, node->fname);
 220    if (node->type != TN_FILE) {
 221       strcat(buf, "/");
 222    }
 223    return 1;
 224 }
 225
 226 /*
 227  * Change to specified directory
 228  */
 229 TREE_NODE *tree_cwd(char *path, TREE_ROOT *root, TREE_NODE *node)
 230 {
 231    if (strcmp(path, ".") == 0) {
 232       return node;
 233    }
 234    if (strcmp(path, "..") == 0) {
 235       if (node->parent) {
 236          return node->parent;
 237       } else {
 238          return node;
 239       }
 240    }
 241    if (path[0] == '/') {
 242       Dmsg0(100, "Doing absolute lookup.\n");
 243       return tree_relcwd(path+1, root, (TREE_NODE *)root);
 244    }
 245    Dmsg0(100, "Doing relative lookup.\n");
 246    return tree_relcwd(path, root, node);
 247 }
 248
 249
 250 TREE_NODE *tree_relcwd(char *path, TREE_ROOT *root, TREE_NODE *node)
 251 {
 252    char *p;
 253    int len;
 254    TREE_NODE *cd;
 255
 256    if (*path == 0) {
 257       return node;
 258    }
 259    p = strchr(path, '/');
 260    if (p) {
 261       len = p - path;
 262    }
 263    for (cd=node->child; cd; cd=cd->sibling) {
 264       if (strncmp(cd->fname, path, len) == 0) {
 265          Dmsg1(100, "tree_relcwd: found cd=%s\n", cd->fname);
 266          break;
 267       }
 268    }
 269    if (!cd || cd->type == TN_FILE) {
 270       Dmsg1(100, "tree_relcwd: failed %s is a file.\n", cd->fname);
 271       return NULL;
 272    }
 273    if (!p) {
 274       Dmsg0(100, "tree_relcwd: no more to lookup. found.\n");
 275       return cd;
 276    }
 277    Dmsg2(100, "recurse tree_relcwd with path=%s, cd=%s\n", p+1, cd->fname);
 278    return tree_relcwd(p+1, root, cd);
 279 }
 280
 281
 282
 283 #ifdef BUILD_TEST_PROGRAM
 284
 285 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent);
 286
 287 static uint32_t FileIndex = 0;
 288 /*
 289  * Simple test program for tree routines
 290  */
 291 int main(int argc, char *argv[])
 292 {
 293     TREE_ROOT *root;
 294     TREE_NODE *node;
 295     char buf[MAXPATHLEN];
 296
 297     root = (TREE_ROOT *)new_tree_node(TN_ROOT);
 298     root->fname = bstrdup("");
 299
 300     FillDirectoryTree("/home/kern/bacula/k", root, NULL);
 301
 302     for (node = first_tree_node(root); node; node=next_tree_node(node)) {
 303        tree_getpath(node, buf, sizeof(buf));
 304        Dmsg2(100, "%d: %s\n", node->FileIndex, buf);
 305     }
 306
 307     node = (TREE_NODE *)root;
 308     Dmsg0(000, "doing cd /home/kern/bacula/k/techlogs\n");
 309     node = tree_cwd("/home/kern/bacula/k/techlogs", root, node);
 310     if (node) {
 311        tree_getpath(node, buf, sizeof(buf));
 312        Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
 313     }
 314
 315     Dmsg0(000, "doing cd /home/kern/bacula/k/src/testprogs\n");
 316     node = tree_cwd("/home/kern/bacula/k/src/testprogs", root, node);
 317     if (node) {
 318        tree_getpath(node, buf, sizeof(buf));
 319        Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
 320     } else {
 321        Dmsg0(100, "testprogs not found.\n");
 322     }
 323
 324     free_tree((TREE_NODE *)root);
 325
 326     return 0;
 327 }
 328
 329 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent)
 330 {
 331    TREE_NODE *newparent = NULL;
 332    TREE_NODE *node;
 333    struct stat statbuf;
 334    DIR *dp;
 335    struct dirent *dir;
 336    char pathbuf[MAXPATHLEN];
 337    char file[MAXPATHLEN];
 338    int type;
 339    int i;
 340
 341    Dmsg1(100, "FillDirectoryTree: %s\n", path);
 342    dp = opendir(path);
 343    if (!dp) {
 344       return;
 345    }
 346    while ((dir = readdir(dp))) {
 347       if (strcmp(dir->d_name, ".") == 0 || strcmp(dir->d_name, "..") == 0) {
 348          continue;
 349       }
 350       strcpy(file, dir->d_name);
 351       snprintf(pathbuf, MAXPATHLEN-1, "%s/%s", path, file);
 352       if (lstat(pathbuf, &statbuf) < 0) {
 353          printf("lstat() failed. ERR=%s\n", strerror(errno));
 354          continue;
 355       }
 356 //      printf("got file=%s, pathbuf=%s\n", file, pathbuf);
 357       type = TN_FILE;
 358       if (S_ISLNK(statbuf.st_mode))
 359          type =  TN_FILE;  /* link */
 360       else if (S_ISREG(statbuf.st_mode))
 361          type = TN_FILE;
 362       else if (S_ISDIR(statbuf.st_mode)) {
 363          type = TN_DIR;
 364       } else if (S_ISCHR(statbuf.st_mode))
 365          type = TN_FILE; /* char dev */
 366       else if (S_ISBLK(statbuf.st_mode))
 367          type = TN_FILE; /* block dev */
 368       else if (S_ISFIFO(statbuf.st_mode))
 369          type = TN_FILE; /* fifo */
 370       else if (S_ISSOCK(statbuf.st_mode))
 371          type = TN_FILE; /* sock */
 372       else {
 373          type = TN_FILE;
 374          printf("Unknown file type: 0x%x\n", statbuf.st_mode);
 375       }
 376
 377       Dmsg2(100, "Doing: %d %s\n", type, pathbuf);
 378       node = new_tree_node(type);
 379       node->FileIndex = ++FileIndex;
 380       parent = insert_tree_node(pathbuf, node, root, parent);
 381       if (S_ISDIR(statbuf.st_mode) && !S_ISLNK(statbuf.st_mode)) {
 382          Dmsg2(100, "calling fill. pathbuf=%s, file=%s\n", pathbuf, file);
 383          FillDirectoryTree(pathbuf, root, node);
 384       }
 385    }
 386    closedir(dp);
 387 }
 388 #endif