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