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