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

   1 /*
   2    Bacula® - The Network Backup Solution
   3
   4    Copyright (C) 2002-2007 Free Software Foundation Europe e.V.
   5
   6    The main author of Bacula is Kern Sibbald, with contributions from
   7    many others, a complete list can be found in the file AUTHORS.
   8    This program is Free Software; you can redistribute it and/or
   9    modify it under the terms of version two of the GNU General Public
  10    License as published by the Free Software Foundation and included
  11    in the file LICENSE.
  12
  13    This program is distributed in the hope that it will be useful, but
  14    WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16    General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program; if not, write to the Free Software
  20    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  21    02110-1301, USA.
  22
  23    Bacula® is a registered trademark of John Walker.
  24    The licensor of Bacula is the Free Software Foundation Europe
  25    (FSFE), Fiduciary Program, Sumatrastrasse 25, 8006 Zürich,
  26    Switzerland, email:ftf@fsfeurope.org.
  27 */
  28 /*
  29  * Directory tree build/traverse routines
  30  *
  31  *    Kern Sibbald, June MMII
  32  *
  33 */
  34
  35
  36 #include "bacula.h"
  37 #include "findlib/find.h"
  38
  39
  40 /* Forward referenced subroutines */
  41 static TREE_NODE *search_and_insert_tree_node(char *fname, int type,
  42                TREE_ROOT *root, TREE_NODE *parent);
  43 static char *tree_alloc(TREE_ROOT *root, int size);
  44
  45 /*
  46  * NOTE !!!!! we turn off Debug messages for performance reasons.
  47  */
  48 #undef Dmsg0
  49 #undef Dmsg1
  50 #undef Dmsg2
  51 #undef Dmsg3
  52 #define Dmsg0(n,f)
  53 #define Dmsg1(n,f,a1)
  54 #define Dmsg2(n,f,a1,a2)
  55 #define Dmsg3(n,f,a1,a2,a3)
  56
  57 /*
  58  * This subroutine gets a big buffer.
  59  */
  60 static void malloc_buf(TREE_ROOT *root, int size)
  61 {
  62    struct s_mem *mem;
  63
  64    mem = (struct s_mem *)malloc(size);
  65    root->total_size += size;
  66    root->blocks++;
  67    mem->next = root->mem;
  68    root->mem = mem;
  69    mem->mem = mem->first;
  70    mem->rem = (char *)mem + size - mem->mem;
  71    Dmsg2(200, "malloc buf size=%d rem=%d\n", size, mem->rem);
  72 }
  73
  74
  75 /*
  76  * Note, we allocate a big buffer in the tree root
  77  *  from which we allocate nodes. This runs more
  78  *  than 100 times as fast as directly using malloc()
  79  *  for each of the nodes.
  80  */
  81 TREE_ROOT *new_tree(int count)
  82 {
  83    TREE_ROOT *root;
  84    uint32_t size;
  85
  86    if (count < 1000) {                /* minimum tree size */
  87       count = 1000;
  88    }
  89    root = (TREE_ROOT *)malloc(sizeof(TREE_ROOT));
  90    memset(root, 0, sizeof(TREE_ROOT));
  91    /* Assume filename + node  = 40 characters average length */
  92    size = count * (BALIGN(sizeof(TREE_NODE)) + 40);
  93    if (count > 1000000 || size > 10000000) {
  94       size = 10000000;
  95    }
  96    Dmsg2(400, "count=%d size=%d\n", count, size);
  97    malloc_buf(root, size);
  98    root->cached_path_len = -1;
  99    root->cached_path = get_pool_memory(PM_FNAME);
 100    root->type = TN_ROOT;
 101    root->fname = "";
 102    return root;
 103 }
 104
 105 /*
 106  * Create a new tree node.
 107  */
 108 static TREE_NODE *new_tree_node(TREE_ROOT *root)
 109 {
 110    TREE_NODE *node;
 111    int size = sizeof(TREE_NODE);
 112    node = (TREE_NODE *)tree_alloc(root, size);
 113    memset(node, 0, size);
 114    return node;
 115 }
 116
 117 /*
 118  * This routine can be called to release the
 119  *  previously allocated tree node.
 120  */
 121 static void free_tree_node(TREE_ROOT *root)
 122 {
 123    int asize = BALIGN(sizeof(TREE_NODE));
 124    root->mem->rem += asize;
 125    root->mem->mem -= asize;
 126 }
 127
 128
 129
 130 /*
 131  * Allocate bytes for filename in tree structure.
 132  *  Keep the pointers properly aligned by allocating
 133  *  sizes that are aligned.
 134  */
 135 static char *tree_alloc(TREE_ROOT *root, int size)
 136 {
 137    char *buf;
 138    int asize = BALIGN(size);
 139
 140    if (root->mem->rem < asize) {
 141       uint32_t mb_size;
 142       if (root->total_size >= 1000000) {
 143          mb_size = 1000000;
 144       } else {
 145          mb_size = 100000;
 146       }
 147       malloc_buf(root, mb_size);
 148    }
 149    root->mem->rem -= asize;
 150    buf = root->mem->mem;
 151    root->mem->mem += asize;
 152    return buf;
 153 }
 154
 155
 156 /* This routine frees the whole tree */
 157 void free_tree(TREE_ROOT *root)
 158 {
 159    struct s_mem *mem, *rel;
 160
 161    for (mem=root->mem; mem; ) {
 162       rel = mem;
 163       mem = mem->next;
 164       free(rel);
 165    }
 166    if (root->cached_path) {
 167       free_pool_memory(root->cached_path);
 168       root->cached_path = NULL;
 169    }
 170    Dmsg2(400, "Total size=%u blocks=%d\n", root->total_size, root->blocks);
 171    free(root);
 172    return;
 173 }
 174
 175
 176 /*
 177  * Insert a node in the tree. This is the main subroutine
 178  *   called when building a tree.
 179  *
 180  */
 181 TREE_NODE *insert_tree_node(char *path, char *fname, int type,
 182                             TREE_ROOT *root, TREE_NODE *parent)
 183 {
 184    char *p, *q;
 185    int path_len = strlen(path);
 186    TREE_NODE *node;
 187
 188    Dmsg1(100, "insert_tree_node: %s\n", path);
 189    /*
 190     * If trailing slash on path, strip it
 191     */
 192    if (path_len > 0) {
 193       q = path + path_len - 1;
 194       if (IsPathSeparator(*q)) {
 195          *q = 0;                      /* strip trailing slash */
 196       } else {
 197          q = NULL;                    /* no trailing slash */
 198       }
 199    } else {
 200       q = NULL;                       /* no trailing slash */
 201    }
 202    /* If no filename, strip last component of path as "filename" */
 203    if (*fname == 0) {
 204       p = (char *)last_path_separator(path);  /* separate path and filename */
 205       if (p) {
 206          fname = p + 1;               /* set new filename */
 207          *p = '\0';                   /* terminate new path */
 208       }
 209    } else {
 210       p = NULL;
 211    }
 212    if (*fname) {
 213       if (!parent) {                  /* if no parent, we need to make one */
 214          Dmsg1(100, "make_tree_path for %s\n", path);
 215          path_len = strlen(path);     /* get new length */
 216          if (path_len == root->cached_path_len &&
 217              strcmp(path, root->cached_path) == 0) {
 218             parent = root->cached_parent;
 219          } else {
 220             root->cached_path_len = path_len;
 221             pm_strcpy(&root->cached_path, path);
 222             parent = make_tree_path(path, root);
 223             root->cached_parent = parent;
 224          }
 225          Dmsg1(100, "parent=%s\n", parent->fname);
 226       }
 227    } else {
 228       fname = path;
 229       if (!parent) {
 230          parent = (TREE_NODE *)root;
 231          type = TN_DIR_NLS;
 232       }
 233       Dmsg1(100, "No / found: %s\n", path);
 234    }
 235
 236    node = search_and_insert_tree_node(fname, 0, root, parent);
 237    if (q) {                           /* if trailing slash on entry */
 238       *q = '/';                       /*  restore it */
 239    }
 240    if (p) {                           /* if slash in path trashed */
 241       *p = '/';                       /* restore full path */
 242    }
 243    return node;
 244 }
 245
 246 /*
 247  * Ensure that all appropriate nodes for a full path exist in
 248  *  the tree.
 249  */
 250 TREE_NODE *make_tree_path(char *path, TREE_ROOT *root)
 251 {
 252    TREE_NODE *parent, *node;
 253    char *fname, *p;
 254    int type = TN_NEWDIR;
 255
 256    Dmsg1(100, "make_tree_path: %s\n", path);
 257    if (*path == 0) {
 258       Dmsg0(100, "make_tree_path: parent=*root*\n");
 259       return (TREE_NODE *)root;
 260    }
 261    p = (char *)last_path_separator(path);           /* get last dir component of path */
 262    if (p) {
 263       fname = p + 1;
 264       *p = 0;                         /* terminate path */
 265       parent = make_tree_path(path, root);
 266       *p = '/';                       /* restore full name */
 267    } else {
 268       fname = path;
 269       parent = (TREE_NODE *)root;
 270       type = TN_DIR_NLS;
 271    }
 272    node = search_and_insert_tree_node(fname, type, root, parent);
 273    return node;
 274 }
 275
 276 static int node_compare(void *item1, void *item2)
 277 {
 278    TREE_NODE *tn1 = (TREE_NODE *)item1;
 279    TREE_NODE *tn2 = (TREE_NODE *)item2;
 280    if (tn1->fname[0] > tn2->fname[0]) {
 281       return 1;
 282    } else if (tn1->fname[0] < tn2->fname[0]) {
 283       return -1;
 284    }
 285    return strcmp(tn1->fname, tn2->fname);
 286 }
 287
 288 /*
 289  *  See if the fname already exists. If not insert a new node for it.
 290  */
 291 static TREE_NODE *search_and_insert_tree_node(char *fname, int type,
 292                TREE_ROOT *root, TREE_NODE *parent)
 293 {
 294    TREE_NODE *node, *found_node;
 295    node = new_tree_node(root);
 296    node->fname = fname;
 297    found_node = (TREE_NODE *)parent->child.insert(node, node_compare);
 298    if (found_node != node) {          /* already in list */
 299       free_tree_node(root);           /* free node allocated above */
 300       found_node->inserted = false;
 301       return found_node;
 302    }
 303    /* It was not found, but is now inserted */
 304    node->fname_len = strlen(fname);
 305    node->fname = tree_alloc(root, node->fname_len + 1);
 306    strcpy(node->fname, fname);
 307    node->parent = parent;
 308    node->type = type;
 309
 310    /* Maintain a linear chain of nodes */
 311    if (!root->first) {
 312       root->first = node;
 313       root->last = node;
 314    } else {
 315       root->last->next = node;
 316       root->last = node;
 317    }
 318    node->inserted = true;             /* inserted into tree */
 319    return node;
 320
 321 }
 322
 323 int tree_getpath(TREE_NODE *node, char *buf, int buf_size)
 324 {
 325    if (!node) {
 326       buf[0] = 0;
 327       return 1;
 328    }
 329    tree_getpath(node->parent, buf, buf_size);
 330    /*
 331     * Fixup for Win32. If we have a Win32 directory and
 332     *    there is only a / in the buffer, remove it since
 333     *    win32 names don't generally start with /
 334     */
 335    if (node->type == TN_DIR_NLS && IsPathSeparator(buf[0]) && buf[1] == '\0') {
 336       buf[0] = '\0';
 337    }
 338    bstrncat(buf, node->fname, buf_size);
 339    /* Add a slash for all directories unless we are at the root,
 340     *  also add a slash to a soft linked file if it has children
 341     *  i.e. it is linked to a directory.
 342     */
 343    if ((node->type != TN_FILE && !(IsPathSeparator(buf[0]) && buf[1] == '\0')) ||
 344        (node->soft_link && tree_node_has_child(node))) {
 345       bstrncat(buf, "/", buf_size);
 346    }
 347    return 1;
 348 }
 349
 350 /*
 351  * Change to specified directory
 352  */
 353 TREE_NODE *tree_cwd(char *path, TREE_ROOT *root, TREE_NODE *node)
 354 {
 355    if (path[0] == '.' && path[1] == '\0') {
 356       return node;
 357    }
 358    /* Handle relative path */
 359    if (path[0] == '.' && path[1] == '.' && (IsPathSeparator(path[2]) || path[2] == '\0')) {
 360       TREE_NODE *parent = node->parent ? node->parent : node;
 361       if (path[2] == 0) {
 362          return parent;
 363       } else {
 364          return tree_cwd(path+3, root, parent);
 365       }
 366    }
 367    if (IsPathSeparator(path[0])) {
 368       Dmsg0(100, "Doing absolute lookup.\n");
 369       return tree_relcwd(path+1, root, (TREE_NODE *)root);
 370    }
 371    Dmsg0(100, "Doing relative lookup.\n");
 372    return tree_relcwd(path, root, node);
 373 }
 374
 375
 376 /*
 377  * Do a relative cwd -- i.e. relative to current node rather than root node
 378  */
 379 TREE_NODE *tree_relcwd(char *path, TREE_ROOT *root, TREE_NODE *node)
 380 {
 381    char *p;
 382    int len;
 383    TREE_NODE *cd;
 384
 385    if (*path == 0) {
 386       return node;
 387    }
 388    /* Check the current segment only */
 389    if ((p = first_path_separator(path)) != NULL) {
 390       len = p - path;
 391    } else {
 392       len = strlen(path);
 393    }
 394    Dmsg2(100, "tree_relcwd: len=%d path=%s\n", len, path);
 395    foreach_child(cd, node) {
 396       Dmsg1(100, "tree_relcwd: test cd=%s\n", cd->fname);
 397       if (cd->fname[0] == path[0] && len == (int)strlen(cd->fname)
 398           && strncmp(cd->fname, path, len) == 0) {
 399          break;
 400       }
 401    }
 402    if (!cd || (cd->type == TN_FILE && !tree_node_has_child(cd))) {
 403       return NULL;
 404    }
 405    if (!p) {
 406       Dmsg0(100, "tree_relcwd: no more to lookup. found.\n");
 407       return cd;
 408    }
 409    Dmsg2(100, "recurse tree_relcwd with path=%s, cd=%s\n", p+1, cd->fname);
 410    /* Check the next segment if any */
 411    return tree_relcwd(p+1, root, cd);
 412 }
 413
 414
 415
 416 #ifdef BUILD_TEST_PROGRAM
 417
 418 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent);
 419
 420 static uint32_t FileIndex = 0;
 421 /*
 422  * Simple test program for tree routines
 423  */
 424 int main(int argc, char *argv[])
 425 {
 426     TREE_ROOT *root;
 427     TREE_NODE *node;
 428     char buf[MAXPATHLEN];
 429
 430     root = new_tree();
 431     root->fname = tree_alloc(root, 1);
 432     *root->fname = 0;
 433     root->fname_len = 0;
 434
 435     FillDirectoryTree("/home/kern/bacula/k", root, NULL);
 436
 437     for (node = first_tree_node(root); node; node=next_tree_node(node)) {
 438        tree_getpath(node, buf, sizeof(buf));
 439        Dmsg2(100, "%d: %s\n", node->FileIndex, buf);
 440     }
 441
 442     node = (TREE_NODE *)root;
 443     Pmsg0(000, "doing cd /home/kern/bacula/k/techlogs\n");
 444     node = tree_cwd("/home/kern/bacula/k/techlogs", root, node);
 445     if (node) {
 446        tree_getpath(node, buf, sizeof(buf));
 447        Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
 448     }
 449
 450     Pmsg0(000, "doing cd /home/kern/bacula/k/src/testprogs\n");
 451     node = tree_cwd("/home/kern/bacula/k/src/testprogs", root, node);
 452     if (node) {
 453        tree_getpath(node, buf, sizeof(buf));
 454        Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
 455     } else {
 456        Dmsg0(100, "testprogs not found.\n");
 457     }
 458
 459     free_tree((TREE_NODE *)root);
 460
 461     return 0;
 462 }
 463
 464 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent)
 465 {
 466    TREE_NODE *newparent = NULL;
 467    TREE_NODE *node;
 468    struct stat statbuf;
 469    DIR *dp;
 470    struct dirent *dir;
 471    char pathbuf[MAXPATHLEN];
 472    char file[MAXPATHLEN];
 473    int type;
 474    int i;
 475
 476    Dmsg1(100, "FillDirectoryTree: %s\n", path);
 477    dp = opendir(path);
 478    if (!dp) {
 479       return;
 480    }
 481    while ((dir = readdir(dp))) {
 482       if (strcmp(dir->d_name, ".") == 0 || strcmp(dir->d_name, "..") == 0) {
 483          continue;
 484       }
 485       bstrncpy(file, dir->d_name, sizeof(file));
 486       snprintf(pathbuf, MAXPATHLEN-1, "%s/%s", path, file);
 487       if (lstat(pathbuf, &statbuf) < 0) {
 488          berrno be;
 489          printf("lstat() failed. ERR=%s\n", be.bstrerror(errno));
 490          continue;
 491       }
 492 //      printf("got file=%s, pathbuf=%s\n", file, pathbuf);
 493       type = TN_FILE;
 494       if (S_ISLNK(statbuf.st_mode))
 495          type =  TN_FILE;  /* link */
 496       else if (S_ISREG(statbuf.st_mode))
 497          type = TN_FILE;
 498       else if (S_ISDIR(statbuf.st_mode)) {
 499          type = TN_DIR;
 500       } else if (S_ISCHR(statbuf.st_mode))
 501          type = TN_FILE; /* char dev */
 502       else if (S_ISBLK(statbuf.st_mode))
 503          type = TN_FILE; /* block dev */
 504       else if (S_ISFIFO(statbuf.st_mode))
 505          type = TN_FILE; /* fifo */
 506       else if (S_ISSOCK(statbuf.st_mode))
 507          type = TN_FILE; /* sock */
 508       else {
 509          type = TN_FILE;
 510          printf("Unknown file type: 0x%x\n", statbuf.st_mode);
 511       }
 512
 513       Dmsg2(100, "Doing: %d %s\n", type, pathbuf);
 514       node = new_tree_node(root);
 515       node->FileIndex = ++FileIndex;
 516       parent = insert_tree_node(pathbuf, node, root, parent);
 517       if (S_ISDIR(statbuf.st_mode) && !S_ISLNK(statbuf.st_mode)) {
 518          Dmsg2(100, "calling fill. pathbuf=%s, file=%s\n", pathbuf, file);
 519          FillDirectoryTree(pathbuf, root, node);
 520       }
 521    }
 522    closedir(dp);
 523 }
 524
 525 #ifndef MAXPATHLEN
 526 #define MAXPATHLEN 2000
 527 #endif
 528
 529 void print_tree(char *path, TREE_NODE *tree)
 530 {
 531    char buf[MAXPATHLEN];
 532    char *termchr;
 533
 534    if (!tree) {
 535       return;
 536    }
 537    switch (tree->type) {
 538    case TN_DIR_NLS:
 539    case TN_DIR:
 540    case TN_NEWDIR:
 541       termchr = "/";
 542       break;
 543    case TN_ROOT:
 544    case TN_FILE:
 545    default:
 546       termchr = "";
 547       break;
 548    }
 549    Pmsg3(-1, "%s/%s%s\n", path, tree->fname, termchr);
 550    switch (tree->type) {
 551    case TN_FILE:
 552    case TN_NEWDIR:
 553    case TN_DIR:
 554    case TN_DIR_NLS:
 555       bsnprintf(buf, sizeof(buf), "%s/%s", path, tree->fname);
 556       print_tree(buf, first_child(tree));
 557       break;
 558    case TN_ROOT:
 559       print_tree(path, first_child(tree));
 560       break;
 561    default:
 562       Pmsg1(000, "Unknown node type %d\n", tree->type);
 563    }
 564    print_tree(path, tree->sibling_);
 565    return;
 566 }
 567
 568 #endif