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