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    Bacula® - The Network Backup Solution
   9
  10    Copyright (C) 2002-2006 Free Software Foundation Europe e.V.
  11
  12    The main author of Bacula is Kern Sibbald, with contributions from
  13    many others, a complete list can be found in the file AUTHORS.
  14    This program is Free Software; you can redistribute it and/or
  15    modify it under the terms of version two of the GNU General Public
  16    License as published by the Free Software Foundation plus additions
  17    that are listed in the file LICENSE.
  18
  19    This program is distributed in the hope that it will be useful, but
  20    WITHOUT ANY WARRANTY; without even the implied warranty of
  21    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  22    General Public License for more details.
  23
  24    You should have received a copy of the GNU General Public License
  25    along with this program; if not, write to the Free Software
  26    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  27    02110-1301, USA.
  28
  29    Bacula® is a registered trademark of John Walker.
  30    The licensor of Bacula is the Free Software Foundation Europe
  31    (FSFE), Fiduciary Program, Sumatrastrasse 25, 8006 Zürich,
  32    Switzerland, email:ftf@fsfeurope.org.
  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 (*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 = strrchr(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 = strrchr(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.binary_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 && 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 && !(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 (strcmp(path, ".") == 0) {
 356       return node;
 357    }
 358    /* Handle relative path */
 359    if (strncmp(path, "..", 2) == 0 && (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 (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    p = strchr(path, '/');
 390    if (p) {
 391       len = p - path;
 392    } else {
 393       len = strlen(path);
 394    }
 395    Dmsg2(100, "tree_relcwd: len=%d path=%s\n", len, path);
 396    foreach_child(cd, node) {
 397       Dmsg1(100, "tree_relcwd: test cd=%s\n", cd->fname);
 398       if (cd->fname[0] == path[0] && len == (int)strlen(cd->fname)
 399           && strncmp(cd->fname, path, len) == 0) {
 400          break;
 401       }
 402    }
 403    if (!cd || (cd->type == TN_FILE && !tree_node_has_child(cd))) {
 404       return NULL;
 405    }
 406    if (!p) {
 407       Dmsg0(100, "tree_relcwd: no more to lookup. found.\n");
 408       return cd;
 409    }
 410    Dmsg2(100, "recurse tree_relcwd with path=%s, cd=%s\n", p+1, cd->fname);
 411    /* Check the next segment if any */
 412    return tree_relcwd(p+1, root, cd);
 413 }
 414
 415
 416
 417 #ifdef BUILD_TEST_PROGRAM
 418
 419 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent);
 420
 421 static uint32_t FileIndex = 0;
 422 /*
 423  * Simple test program for tree routines
 424  */
 425 int main(int argc, char *argv[])
 426 {
 427     TREE_ROOT *root;
 428     TREE_NODE *node;
 429     char buf[MAXPATHLEN];
 430
 431     root = new_tree();
 432     root->fname = tree_alloc(root, 1);
 433     *root->fname = 0;
 434     root->fname_len = 0;
 435
 436     FillDirectoryTree("/home/kern/bacula/k", root, NULL);
 437
 438     for (node = first_tree_node(root); node; node=next_tree_node(node)) {
 439        tree_getpath(node, buf, sizeof(buf));
 440        Dmsg2(100, "%d: %s\n", node->FileIndex, buf);
 441     }
 442
 443     node = (TREE_NODE *)root;
 444     Pmsg0(000, "doing cd /home/kern/bacula/k/techlogs\n");
 445     node = tree_cwd("/home/kern/bacula/k/techlogs", root, node);
 446     if (node) {
 447        tree_getpath(node, buf, sizeof(buf));
 448        Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
 449     }
 450
 451     Pmsg0(000, "doing cd /home/kern/bacula/k/src/testprogs\n");
 452     node = tree_cwd("/home/kern/bacula/k/src/testprogs", root, node);
 453     if (node) {
 454        tree_getpath(node, buf, sizeof(buf));
 455        Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
 456     } else {
 457        Dmsg0(100, "testprogs not found.\n");
 458     }
 459
 460     free_tree((TREE_NODE *)root);
 461
 462     return 0;
 463 }
 464
 465 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent)
 466 {
 467    TREE_NODE *newparent = NULL;
 468    TREE_NODE *node;
 469    struct stat statbuf;
 470    DIR *dp;
 471    struct dirent *dir;
 472    char pathbuf[MAXPATHLEN];
 473    char file[MAXPATHLEN];
 474    int type;
 475    int i;
 476
 477    Dmsg1(100, "FillDirectoryTree: %s\n", path);
 478    dp = opendir(path);
 479    if (!dp) {
 480       return;
 481    }
 482    while ((dir = readdir(dp))) {
 483       if (strcmp(dir->d_name, ".") == 0 || strcmp(dir->d_name, "..") == 0) {
 484          continue;
 485       }
 486       bstrncpy(file, dir->d_name, sizeof(file));
 487       snprintf(pathbuf, MAXPATHLEN-1, "%s/%s", path, file);
 488       if (lstat(pathbuf, &statbuf) < 0) {
 489          printf("lstat() failed. ERR=%s\n", strerror(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