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 /*
 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    if (strcmp(path, "..") == 0) {
 346       if (node->parent) {
 347          return node->parent;
 348       } else {
 349          return node;
 350       }
 351    }
 352    if (path[0] == '/') {
 353       Dmsg0(100, "Doing absolute lookup.\n");
 354       return tree_relcwd(path+1, root, (TREE_NODE *)root);
 355    }
 356    Dmsg0(100, "Doing relative lookup.\n");
 357    return tree_relcwd(path, root, node);
 358 }
 359
 360
 361 /*
 362  * Do a relative cwd -- i.e. relative to current node rather than root node
 363  */
 364 TREE_NODE *tree_relcwd(char *path, TREE_ROOT *root, TREE_NODE *node)
 365 {
 366    char *p;
 367    int len;
 368    TREE_NODE *cd;
 369
 370    if (*path == 0) {
 371       return node;
 372    }
 373    /* Check the current segment only */
 374    p = strchr(path, '/');
 375    if (p) {
 376       len = p - path;
 377    } else {
 378       len = strlen(path);
 379    }
 380    Dmsg2(100, "tree_relcwd: len=%d path=%s\n", len, path);
 381    foreach_child(cd, node) {
 382       Dmsg1(100, "tree_relcwd: test cd=%s\n", cd->fname);
 383       if (cd->fname[0] == path[0] && len == (int)strlen(cd->fname)
 384           && strncmp(cd->fname, path, len) == 0) {
 385          break;
 386       }
 387    }
 388    if (!cd || (cd->type == TN_FILE && !tree_node_has_child(cd))) {
 389       return NULL;
 390    }
 391    if (!p) {
 392       Dmsg0(100, "tree_relcwd: no more to lookup. found.\n");
 393       return cd;
 394    }
 395    Dmsg2(100, "recurse tree_relcwd with path=%s, cd=%s\n", p+1, cd->fname);
 396    /* Check the next segment if any */
 397    return tree_relcwd(p+1, root, cd);
 398 }
 399
 400
 401
 402 #ifdef BUILD_TEST_PROGRAM
 403
 404 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent);
 405
 406 static uint32_t FileIndex = 0;
 407 /*
 408  * Simple test program for tree routines
 409  */
 410 int main(int argc, char *argv[])
 411 {
 412     TREE_ROOT *root;
 413     TREE_NODE *node;
 414     char buf[MAXPATHLEN];
 415
 416     root = new_tree();
 417     root->fname = tree_alloc(root, 1);
 418     *root->fname = 0;
 419     root->fname_len = 0;
 420
 421     FillDirectoryTree("/home/kern/bacula/k", root, NULL);
 422
 423     for (node = first_tree_node(root); node; node=next_tree_node(node)) {
 424        tree_getpath(node, buf, sizeof(buf));
 425        Dmsg2(100, "%d: %s\n", node->FileIndex, buf);
 426     }
 427
 428     node = (TREE_NODE *)root;
 429     Pmsg0(000, "doing cd /home/kern/bacula/k/techlogs\n");
 430     node = tree_cwd("/home/kern/bacula/k/techlogs", root, node);
 431     if (node) {
 432        tree_getpath(node, buf, sizeof(buf));
 433        Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
 434     }
 435
 436     Pmsg0(000, "doing cd /home/kern/bacula/k/src/testprogs\n");
 437     node = tree_cwd("/home/kern/bacula/k/src/testprogs", root, node);
 438     if (node) {
 439        tree_getpath(node, buf, sizeof(buf));
 440        Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
 441     } else {
 442        Dmsg0(100, "testprogs not found.\n");
 443     }
 444
 445     free_tree((TREE_NODE *)root);
 446
 447     return 0;
 448 }
 449
 450 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent)
 451 {
 452    TREE_NODE *newparent = NULL;
 453    TREE_NODE *node;
 454    struct stat statbuf;
 455    DIR *dp;
 456    struct dirent *dir;
 457    char pathbuf[MAXPATHLEN];
 458    char file[MAXPATHLEN];
 459    int type;
 460    int i;
 461
 462    Dmsg1(100, "FillDirectoryTree: %s\n", path);
 463    dp = opendir(path);
 464    if (!dp) {
 465       return;
 466    }
 467    while ((dir = readdir(dp))) {
 468       if (strcmp(dir->d_name, ".") == 0 || strcmp(dir->d_name, "..") == 0) {
 469          continue;
 470       }
 471       bstrncpy(file, dir->d_name, sizeof(file));
 472       snprintf(pathbuf, MAXPATHLEN-1, "%s/%s", path, file);
 473       if (lstat(pathbuf, &statbuf) < 0) {
 474          printf("lstat() failed. ERR=%s\n", strerror(errno));
 475          continue;
 476       }
 477 //      printf("got file=%s, pathbuf=%s\n", file, pathbuf);
 478       type = TN_FILE;
 479       if (S_ISLNK(statbuf.st_mode))
 480          type =  TN_FILE;  /* link */
 481       else if (S_ISREG(statbuf.st_mode))
 482          type = TN_FILE;
 483       else if (S_ISDIR(statbuf.st_mode)) {
 484          type = TN_DIR;
 485       } else if (S_ISCHR(statbuf.st_mode))
 486          type = TN_FILE; /* char dev */
 487       else if (S_ISBLK(statbuf.st_mode))
 488          type = TN_FILE; /* block dev */
 489       else if (S_ISFIFO(statbuf.st_mode))
 490          type = TN_FILE; /* fifo */
 491       else if (S_ISSOCK(statbuf.st_mode))
 492          type = TN_FILE; /* sock */
 493       else {
 494          type = TN_FILE;
 495          printf("Unknown file type: 0x%x\n", statbuf.st_mode);
 496       }
 497
 498       Dmsg2(100, "Doing: %d %s\n", type, pathbuf);
 499       node = new_tree_node(root);
 500       node->FileIndex = ++FileIndex;
 501       parent = insert_tree_node(pathbuf, node, root, parent);
 502       if (S_ISDIR(statbuf.st_mode) && !S_ISLNK(statbuf.st_mode)) {
 503          Dmsg2(100, "calling fill. pathbuf=%s, file=%s\n", pathbuf, file);
 504          FillDirectoryTree(pathbuf, root, node);
 505       }
 506    }
 507    closedir(dp);
 508 }
 509
 510 #ifndef MAXPATHLEN
 511 #define MAXPATHLEN 2000
 512 #endif
 513
 514 void print_tree(char *path, TREE_NODE *tree)
 515 {
 516    char buf[MAXPATHLEN];
 517    char *termchr;
 518
 519    if (!tree) {
 520       return;
 521    }
 522    switch (tree->type) {
 523    case TN_DIR_NLS:
 524    case TN_DIR:
 525    case TN_NEWDIR:
 526       termchr = "/";
 527       break;
 528    case TN_ROOT:
 529    case TN_FILE:
 530    default:
 531       termchr = "";
 532       break;
 533    }
 534    Pmsg3(-1, "%s/%s%s\n", path, tree->fname, termchr);
 535    switch (tree->type) {
 536    case TN_FILE:
 537    case TN_NEWDIR:
 538    case TN_DIR:
 539    case TN_DIR_NLS:
 540       bsnprintf(buf, sizeof(buf), "%s/%s", path, tree->fname);
 541       print_tree(buf, first_child(tree));
 542       break;
 543    case TN_ROOT:
 544       print_tree(path, first_child(tree));
 545       break;
 546    default:
 547       Pmsg1(000, "Unknown node type %d\n", tree->type);
 548    }
 549    print_tree(path, tree->sibling_);
 550    return;
 551 }
 552
 553 #endif