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