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