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