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-2005 Kern Sibbald
   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
  12    version 2 as ammended with additional clauses defined in the
  13    file LICENSE in the main source directory.
  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
  18    the file LICENSE for additional details.
  19
  20  */
  21
  22
  23 #include "bacula.h"
  24 #include "findlib/find.h"
  25
  26
  27 /* Forward referenced subroutines */
  28 static TREE_NODE *search_and_insert_tree_node(char *fname, int type,
  29                TREE_ROOT *root, TREE_NODE *parent);
  30 static char *tree_alloc(TREE_ROOT *root, int size);
  31
  32 /*
  33  * NOTE !!!!! we turn off Debug messages for performance reasons.
  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    /* Assume filename + node  = 40 characters average length */
  79    size = count * (BALIGN(sizeof(TREE_NODE)) + 40);
  80    if (count > 1000000 || size > 10000000) {
  81       size = 10000000;
  82    }
  83    Dmsg2(400, "count=%d size=%d\n", count, size);
  84    malloc_buf(root, size);
  85    root->cached_path_len = -1;
  86    root->cached_path = get_pool_memory(PM_FNAME);
  87    root->type = TN_ROOT;
  88    root->fname = "";
  89    return root;
  90 }
  91
  92 /*
  93  * Create a new tree node.
  94  */
  95 static TREE_NODE *new_tree_node(TREE_ROOT *root)
  96 {
  97    TREE_NODE *node;
  98    int size = sizeof(TREE_NODE);
  99    node = (TREE_NODE *)tree_alloc(root, size);
 100    memset(node, 0, size);
 101    return node;
 102 }
 103
 104 #ifdef USE_DLIST
 105 /*
 106  * This routine can be called to release the
 107  *  previously allocated tree node.
 108  */
 109 static void free_tree_node(TREE_ROOT *root)
 110 {
 111    int asize = BALIGN(sizeof(TREE_NODE));
 112    root->mem->rem += asize;
 113    root->mem->mem -= asize;
 114 }
 115 #endif
 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       root->cached_path = NULL;
 158    }
 159    Dmsg2(400, "Total size=%u blocks=%d\n", root->total_size, root->blocks);
 160    free(root);
 161    return;
 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, char *fname, int type,
 171                             TREE_ROOT *root, TREE_NODE *parent)
 172 {
 173    char *p, *q;
 174    int path_len = strlen(path);
 175    TREE_NODE *node;
 176
 177    Dmsg1(100, "insert_tree_node: %s\n", path);
 178    /*
 179     * If trailing slash on path, 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    /* If no filename, strip last component of path as "filename" */
 192    if (*fname == 0) {
 193       p = strrchr(path, '/');         /* separate path and filename */
 194       if (p) {
 195          fname = p + 1;               /* set new filename */
 196          *p = 0;                      /* terminate new path */
 197       }
 198    } else {
 199       p = NULL;
 200    }
 201    if (*fname) {
 202       if (!parent) {                  /* if no parent, we need to make one */
 203          Dmsg1(100, "make_tree_path for %s\n", path);
 204          path_len = strlen(path);     /* get new length */
 205          if (path_len == root->cached_path_len &&
 206              strcmp(path, root->cached_path) == 0) {
 207             parent = root->cached_parent;
 208          } else {
 209             root->cached_path_len = path_len;
 210             pm_strcpy(&root->cached_path, path);
 211             parent = make_tree_path(path, root);
 212             root->cached_parent = parent;
 213          }
 214          Dmsg1(100, "parent=%s\n", parent->fname);
 215       }
 216    } else {
 217       fname = path;
 218       if (!parent) {
 219          parent = (TREE_NODE *)root;
 220          type = TN_DIR_NLS;
 221       }
 222       Dmsg1(100, "No / found: %s\n", path);
 223    }
 224
 225    node = search_and_insert_tree_node(fname, 0, root, parent);
 226    if (q) {                           /* if trailing slash on entry */
 227       *q = '/';                       /*  restore it */
 228    }
 229    if (p) {                           /* if slash in path trashed */
 230       *p = '/';                       /* restore full path */
 231    }
 232    return node;
 233 }
 234
 235 /*
 236  * Ensure that all appropriate nodes for a full path exist in
 237  *  the tree.
 238  */
 239 TREE_NODE *make_tree_path(char *path, TREE_ROOT *root)
 240 {
 241    TREE_NODE *parent, *node;
 242    char *fname, *p;
 243    int type = TN_NEWDIR;
 244
 245    Dmsg1(100, "make_tree_path: %s\n", path);
 246    if (*path == 0) {
 247       Dmsg0(100, "make_tree_path: parent=*root*\n");
 248       return (TREE_NODE *)root;
 249    }
 250    p = strrchr(path, '/');           /* get last dir component of path */
 251    if (p) {
 252       fname = p + 1;
 253       *p = 0;                         /* terminate path */
 254       parent = make_tree_path(path, root);
 255       *p = '/';                       /* restore full name */
 256    } else {
 257       fname = path;
 258       parent = (TREE_NODE *)root;
 259       type = TN_DIR_NLS;
 260    }
 261    node = search_and_insert_tree_node(fname, type, root, parent);
 262    return node;
 263 }
 264
 265 #ifdef USE_DLIST
 266 static int node_compare(void *item1, void *item2)
 267 {
 268    TREE_NODE *tn1 = (TREE_NODE *)item1;
 269    TREE_NODE *tn2 = (TREE_NODE *)item2;
 270    if (tn1->fname[0] > tn2->fname[0]) {
 271       return 1;
 272    } else if (tn1->fname[0] < tn2->fname[0]) {
 273       return -1;
 274    }
 275    return strcmp(tn1->fname, tn2->fname);
 276 }
 277 #endif
 278
 279 /*
 280  *  See if the fname already exists. If not insert a new node for it.
 281  */
 282 static TREE_NODE *search_and_insert_tree_node(char *fname, int type,
 283                TREE_ROOT *root, TREE_NODE *parent)
 284 {
 285 #ifdef USE_DLIST
 286    TREE_NODE *node, *found_node;
 287    node = new_tree_node(root);
 288    node->fname = fname;
 289    found_node = (TREE_NODE *)parent->child.unique_binary_insert(node, node_compare);
 290    if (found_node != node) {          /* already in list */
 291       free_tree_node(root);           /* free node allocated above */
 292       found_node->inserted = false;
 293       return found_node;
 294    }
 295    /* It was not found, but is now inserted */
 296    node->fname_len = strlen(fname);
 297    node->fname = tree_alloc(root, node->fname_len + 1);
 298    strcpy(node->fname, fname);
 299    node->parent = parent;
 300    node->type = type;
 301
 302    /* Maintain a linear chain of nodes */
 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    node->inserted = true;             /* inserted into tree */
 311    return node;
 312
 313 #else
 314    TREE_NODE *sibling, *last_sibling = NULL;
 315    uint16_t fname_len = strlen(fname);
 316    int cmp;
 317
 318    /* Is it already a sibling? */
 319    foreach_child(sibling, parent) {
 320       Dmsg2(000, "sibling->fname=%s fname=%s\n", sibling->fname, fname);
 321       if (fname[0] > sibling->fname[0] || (cmp=strcmp(fname, sibling->fname)) > 0) {
 322          last_sibling = sibling;
 323          continue;
 324       }
 325       if (cmp < 0) {
 326          /* Insert before current sibling */
 327          if (!node) {
 328             node = new_tree_node(root);
 329          }
 330          node->sibling_ = sibling;
 331          if (sibling == first_child(parent)) { /* if sibling was at head of list */
 332             parent->child_ = NULL;        /* force parent to be updated below */
 333          }
 334          Dmsg2(000, "insert before sibling->fname=%s fname=%s\n", sibling->fname, fname);
 335          break;
 336       }
 337       /* Found it */
 338       sibling->inserted = false;      /* already in tree */
 339       return sibling;
 340    }
 341
 342
 343    /*
 344     * At this point, the fname is not found. We must add it
 345     */
 346    if (!node) {
 347       node = new_tree_node(root);
 348    }
 349    Dmsg1(000, "append_tree_node: %s\n", fname);
 350    node->fname_len = fname_len;
 351    node->fname = tree_alloc(root, node->fname_len + 1);
 352    strcpy(node->fname, fname);
 353    node->parent = parent;
 354    node->type = type;
 355    if (!tree_node_has_child(parent)) {
 356       parent->child_ = node;
 357    } else {
 358       last_sibling->sibling_ = node;
 359    }
 360
 361    /* Maintain a linear chain of nodes */
 362    if (!root->first) {
 363       root->first = node;
 364       root->last = node;
 365    } else {
 366       root->last->next = node;
 367       root->last = node;
 368    }
 369    node->inserted = true;             /* inserted into tree */
 370    return node;
 371 #endif
 372 }
 373
 374 #ifdef SLOW_WAY
 375 /* Moved to tree.h to eliminate subroutine call */
 376 TREE_NODE *first_tree_node(TREE_ROOT *root)
 377 {
 378    return root->first;
 379 }
 380
 381 TREE_NODE *next_tree_node(TREE_NODE *node)
 382 {
 383    return node->next;
 384 }
 385 #endif
 386
 387
 388
 389 int tree_getpath(TREE_NODE *node, char *buf, int buf_size)
 390 {
 391    if (!node) {
 392       buf[0] = 0;
 393       return 1;
 394    }
 395    tree_getpath(node->parent, buf, buf_size);
 396    /*
 397     * Fixup for Win32. If we have a Win32 directory and
 398     *    there is only a / in the buffer, remove it since
 399     *    win32 names don't generally start with /
 400     */
 401    if (node->type == TN_DIR_NLS && buf[0] == '/' && buf[1] == 0) {
 402       buf[0] = 0;
 403    }
 404    bstrncat(buf, node->fname, buf_size);
 405    /* Add a slash for all directories unless we are at the root,
 406     *  also add a slash to a soft linked file if it has children
 407     *  i.e. it is linked to a directory.
 408     */
 409    if ((node->type != TN_FILE && !(buf[0] == '/' && buf[1] == 0)) ||
 410        (node->soft_link && tree_node_has_child(node))) {
 411       bstrncat(buf, "/", buf_size);
 412    }
 413    return 1;
 414 }
 415
 416 /*
 417  * Change to specified directory
 418  */
 419 TREE_NODE *tree_cwd(char *path, TREE_ROOT *root, TREE_NODE *node)
 420 {
 421    if (strcmp(path, ".") == 0) {
 422       return node;
 423    }
 424    if (strcmp(path, "..") == 0) {
 425       if (node->parent) {
 426          return node->parent;
 427       } else {
 428          return node;
 429       }
 430    }
 431    if (path[0] == '/') {
 432       Dmsg0(100, "Doing absolute lookup.\n");
 433       return tree_relcwd(path+1, root, (TREE_NODE *)root);
 434    }
 435    Dmsg0(100, "Doing relative lookup.\n");
 436    return tree_relcwd(path, root, node);
 437 }
 438
 439
 440 /*
 441  * Do a relative cwd -- i.e. relative to current node rather than root node
 442  */
 443 TREE_NODE *tree_relcwd(char *path, TREE_ROOT *root, TREE_NODE *node)
 444 {
 445    char *p;
 446    int len;
 447    TREE_NODE *cd;
 448
 449    if (*path == 0) {
 450       return node;
 451    }
 452    /* Check the current segment only */
 453    p = strchr(path, '/');
 454    if (p) {
 455       len = p - path;
 456    } else {
 457       len = strlen(path);
 458    }
 459    Dmsg2(100, "tree_relcwd: len=%d path=%s\n", len, path);
 460    foreach_child(cd, node) {
 461       Dmsg1(100, "tree_relcwd: test cd=%s\n", cd->fname);
 462       if (cd->fname[0] == path[0] && len == (int)strlen(cd->fname)
 463           && strncmp(cd->fname, path, len) == 0) {
 464          break;
 465       }
 466    }
 467    if (!cd || (cd->type == TN_FILE && !tree_node_has_child(cd))) {
 468       return NULL;
 469    }
 470    if (!p) {
 471       Dmsg0(100, "tree_relcwd: no more to lookup. found.\n");
 472       return cd;
 473    }
 474    Dmsg2(100, "recurse tree_relcwd with path=%s, cd=%s\n", p+1, cd->fname);
 475    /* Check the next segment if any */
 476    return tree_relcwd(p+1, root, cd);
 477 }
 478
 479
 480
 481 #ifdef BUILD_TEST_PROGRAM
 482
 483 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent);
 484
 485 static uint32_t FileIndex = 0;
 486 /*
 487  * Simple test program for tree routines
 488  */
 489 int main(int argc, char *argv[])
 490 {
 491     TREE_ROOT *root;
 492     TREE_NODE *node;
 493     char buf[MAXPATHLEN];
 494
 495     root = new_tree();
 496     root->fname = tree_alloc(root, 1);
 497     *root->fname = 0;
 498     root->fname_len = 0;
 499
 500     FillDirectoryTree("/home/kern/bacula/k", root, NULL);
 501
 502     for (node = first_tree_node(root); node; node=next_tree_node(node)) {
 503        tree_getpath(node, buf, sizeof(buf));
 504        Dmsg2(100, "%d: %s\n", node->FileIndex, buf);
 505     }
 506
 507     node = (TREE_NODE *)root;
 508     Pmsg0(000, "doing cd /home/kern/bacula/k/techlogs\n");
 509     node = tree_cwd("/home/kern/bacula/k/techlogs", root, node);
 510     if (node) {
 511        tree_getpath(node, buf, sizeof(buf));
 512        Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
 513     }
 514
 515     Pmsg0(000, "doing cd /home/kern/bacula/k/src/testprogs\n");
 516     node = tree_cwd("/home/kern/bacula/k/src/testprogs", root, node);
 517     if (node) {
 518        tree_getpath(node, buf, sizeof(buf));
 519        Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
 520     } else {
 521        Dmsg0(100, "testprogs not found.\n");
 522     }
 523
 524     free_tree((TREE_NODE *)root);
 525
 526     return 0;
 527 }
 528
 529 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent)
 530 {
 531    TREE_NODE *newparent = NULL;
 532    TREE_NODE *node;
 533    struct stat statbuf;
 534    DIR *dp;
 535    struct dirent *dir;
 536    char pathbuf[MAXPATHLEN];
 537    char file[MAXPATHLEN];
 538    int type;
 539    int i;
 540
 541    Dmsg1(100, "FillDirectoryTree: %s\n", path);
 542    dp = opendir(path);
 543    if (!dp) {
 544       return;
 545    }
 546    while ((dir = readdir(dp))) {
 547       if (strcmp(dir->d_name, ".") == 0 || strcmp(dir->d_name, "..") == 0) {
 548          continue;
 549       }
 550       bstrncpy(file, dir->d_name, sizeof(file));
 551       snprintf(pathbuf, MAXPATHLEN-1, "%s/%s", path, file);
 552       if (lstat(pathbuf, &statbuf) < 0) {
 553          printf("lstat() failed. ERR=%s\n", strerror(errno));
 554          continue;
 555       }
 556 //      printf("got file=%s, pathbuf=%s\n", file, pathbuf);
 557       type = TN_FILE;
 558       if (S_ISLNK(statbuf.st_mode))
 559          type =  TN_FILE;  /* link */
 560       else if (S_ISREG(statbuf.st_mode))
 561          type = TN_FILE;
 562       else if (S_ISDIR(statbuf.st_mode)) {
 563          type = TN_DIR;
 564       } else if (S_ISCHR(statbuf.st_mode))
 565          type = TN_FILE; /* char dev */
 566       else if (S_ISBLK(statbuf.st_mode))
 567          type = TN_FILE; /* block dev */
 568       else if (S_ISFIFO(statbuf.st_mode))
 569          type = TN_FILE; /* fifo */
 570       else if (S_ISSOCK(statbuf.st_mode))
 571          type = TN_FILE; /* sock */
 572       else {
 573          type = TN_FILE;
 574          printf("Unknown file type: 0x%x\n", statbuf.st_mode);
 575       }
 576
 577       Dmsg2(100, "Doing: %d %s\n", type, pathbuf);
 578       node = new_tree_node(root);
 579       node->FileIndex = ++FileIndex;
 580       parent = insert_tree_node(pathbuf, node, root, parent);
 581       if (S_ISDIR(statbuf.st_mode) && !S_ISLNK(statbuf.st_mode)) {
 582          Dmsg2(100, "calling fill. pathbuf=%s, file=%s\n", pathbuf, file);
 583          FillDirectoryTree(pathbuf, root, node);
 584       }
 585    }
 586    closedir(dp);
 587 }
 588
 589 #ifndef MAXPATHLEN
 590 #define MAXPATHLEN 2000
 591 #endif
 592
 593 void print_tree(char *path, TREE_NODE *tree)
 594 {
 595    char buf[MAXPATHLEN];
 596    char *termchr;
 597
 598    if (!tree) {
 599       return;
 600    }
 601    switch (tree->type) {
 602    case TN_DIR_NLS:
 603    case TN_DIR:
 604    case TN_NEWDIR:
 605       termchr = "/";
 606       break;
 607    case TN_ROOT:
 608    case TN_FILE:
 609    default:
 610       termchr = "";
 611       break;
 612    }
 613    Pmsg3(-1, "%s/%s%s\n", path, tree->fname, termchr);
 614    switch (tree->type) {
 615    case TN_FILE:
 616    case TN_NEWDIR:
 617    case TN_DIR:
 618    case TN_DIR_NLS:
 619       bsnprintf(buf, sizeof(buf), "%s/%s", path, tree->fname);
 620       print_tree(buf, first_child(tree));
 621       break;
 622    case TN_ROOT:
 623       print_tree(path, first_child(tree));
 624       break;
 625    default:
 626       Pmsg1(000, "Unknown node type %d\n", tree->type);
 627    }
 628    print_tree(path, tree->sibling_);
 629    return;
 630 }
 631
 632 #endif