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