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 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 #include "findlib/system.h"
  31
  32 #ifndef MAXPATHLEN
  33 #define MAXPATHLEN 1000
  34 #endif
  35
  36 /*
  37  * This subrouting gets a big buffer.
  38  */
  39 static void malloc_buf(TREE_ROOT *root, int size)
  40 {
  41    struct s_mem *mem;
  42
  43    mem = (struct s_mem *)malloc(size);
  44    mem->next = root->mem;
  45    root->mem = mem;
  46    mem->mem = mem->first;
  47    mem->rem = (char *)mem + size - mem->mem;
  48    Dmsg2(400, "malloc buf size=%d rem=%d\n", size, mem->rem);
  49 }
  50
  51
  52 /*
  53  * Note, we allocate a big buffer in the tree root
  54  *  from which we allocate nodes. This runs more
  55  *  than 100 times as fast as directly using malloc()
  56  *  for each of the nodes.
  57  */
  58 TREE_ROOT *new_tree(int count)
  59 {
  60    TREE_ROOT *root;
  61    uint32_t size;
  62
  63    if (count < 1000) {                /* minimum tree size */
  64       count = 1000;
  65    }
  66    root = (TREE_ROOT *)malloc(sizeof(TREE_ROOT));
  67    memset(root, 0, sizeof(TREE_ROOT));
  68    root->type = TN_ROOT;
  69    /* Assume filename = 20 characters average length */
  70    size = count * (BALIGN(sizeof(TREE_NODE)) + 20);
  71    if (size > 10000000) {
  72       size = 10000000;
  73    }
  74    Dmsg2(400, "count=%d size=%d\n", count, size);
  75    malloc_buf(root, size);
  76    return root;
  77 }
  78
  79 /*
  80  * Create a new tree node. Size depends on type.
  81  */
  82 TREE_NODE *new_tree_node(TREE_ROOT *root, int type)
  83 {
  84    TREE_NODE *node;
  85    int size = BALIGN(sizeof(TREE_NODE));
  86
  87    if (root->mem->rem < size) {
  88       malloc_buf(root, 20000);
  89    }
  90
  91    root->mem->rem -= size;
  92    node = (TREE_NODE *)root->mem->mem;
  93    root->mem->mem += size;
  94    memset(node, 0, sizeof(TREE_NODE));
  95    node->type = type;
  96    return node;
  97 }
  98
  99
 100 /*
 101  * Allocate bytes for filename in tree structure.
 102  *  Keep the pointers properly aligned by allocating
 103  *  sizes that are aligned.
 104  */
 105 static char *tree_alloc(TREE_ROOT *root, int size)
 106 {
 107    char *buf;
 108    int asize = BALIGN(size);
 109
 110    if (root->mem->rem < asize) {
 111       malloc_buf(root, 20000+asize);
 112    }
 113    root->mem->rem -= asize;
 114    buf = root->mem->mem;
 115    root->mem->mem += asize;
 116    return buf;
 117 }
 118
 119
 120 /* This routine frees the whole tree */
 121 void free_tree(TREE_ROOT *root)
 122 {
 123    struct s_mem *mem, *rel;
 124
 125    for (mem=root->mem; mem; ) {
 126       rel = mem;
 127       mem = mem->next;
 128       free(rel);
 129    }
 130    free(root);
 131    return;
 132 }
 133
 134
 135
 136 /*
 137  * Insert a node in the tree
 138  *
 139  */
 140 TREE_NODE *insert_tree_node(char *path, TREE_NODE *node, TREE_ROOT *root, TREE_NODE *parent)
 141 {
 142    TREE_NODE *sibling;
 143    char *p, *q, *fname;
 144    int len = strlen(path);
 145
 146    Dmsg1(100, "insert_tree_node: %s\n", path);
 147    /*
 148     * If trailing slash, strip it
 149     */
 150    if (len > 0) {
 151       q = path + len - 1;
 152       if (*q == '/') {
 153          *q = 0;                      /* strip trailing slash */
 154       } else {
 155          q = NULL;                    /* no trailing slash */
 156       }
 157    } else {
 158       q = NULL;                       /* no trailing slash */
 159    }
 160    p = strrchr(path, '/');            /* separate path and filename */
 161    if (p) {
 162       fname = p + 1;
 163       if (!parent) {
 164          *p = 0;                      /* terminate path */
 165          Dmsg1(100, "make_tree_path for %s\n", path);
 166          parent = make_tree_path(path, root);
 167          Dmsg1(100, "parent=%s\n", parent->fname);
 168          *p = '/';                    /* restore full name */
 169       }
 170    } else {
 171       fname = path;
 172       if (!parent) {
 173          parent = (TREE_NODE *)root;
 174          node->type = TN_DIR_NLS;
 175       }
 176       Dmsg1(100, "No / found: %s\n", path);
 177    }
 178
 179    for (sibling=parent->child; sibling; sibling=sibling->sibling) {
 180       Dmsg2(100, "sibling->fname=%s fname=%s\n", sibling->fname, fname);
 181       if (strcmp(sibling->fname, fname) == 0) {
 182          Dmsg1(100, "make_tree_path: found parent=%s\n", parent->fname);
 183          if (q) {                     /* if trailing slash on entry */
 184             *q = '/';                 /*  restore it */
 185          }
 186          return sibling;
 187       }
 188    }
 189
 190
 191    append_tree_node(fname, node, root, parent);
 192    Dmsg1(100, "insert_tree_node: parent=%s\n", parent->fname);
 193    if (q) {                           /* if trailing slash on entry */
 194       *q = '/';                       /*  restore it */
 195    }
 196    return node;
 197 }
 198
 199 /*
 200  * Ensure that all appropriate nodes for a full path exist in
 201  *  the tree.
 202  */
 203 TREE_NODE *make_tree_path(char *path, TREE_ROOT *root)
 204 {
 205    TREE_NODE *parent, *sibling, *node;
 206    char *fname, *p;
 207    int type = TN_NEWDIR;
 208
 209    Dmsg1(100, "make_tree_path: %s\n", path);
 210    if (*path == 0) {
 211       Dmsg0(100, "make_tree_path: parent=*root*\n");
 212       return (TREE_NODE *)root;
 213    }
 214    p = strrchr(path, '/');           /* separate path and filename */
 215    if (p) {
 216       fname = p + 1;
 217       *p = 0;                         /* terminate path */
 218       parent = make_tree_path(path, root);
 219       *p = '/';                       /* restore full name */
 220    } else {
 221       fname = path;
 222       parent = (TREE_NODE *)root;
 223       type = TN_DIR_NLS;
 224    }
 225    /* Is it already a sibling? */
 226    for (sibling=parent->child; sibling; sibling=sibling->sibling) {
 227       Dmsg2(100, "sibling->fname=%s fname=%s\n", sibling->fname, fname);
 228       if (strcmp(sibling->fname, fname) == 0) {
 229          Dmsg1(100, "make_tree_path: found parent=%s\n", parent->fname);
 230          return sibling;
 231       }
 232    }
 233    /* Must add */
 234    node = new_tree_node(root, type);
 235    append_tree_node(fname, node, root, parent);
 236    Dmsg1(100, "make_tree_path: add parent=%s\n", node->fname);
 237    return node;
 238 }
 239
 240 /*
 241  *  Append sibling to parent's child chain
 242  */
 243 void append_tree_node(char *fname, TREE_NODE *node, TREE_ROOT *root, TREE_NODE *parent)
 244 {
 245    TREE_NODE *child;
 246
 247    Dmsg1(100, "append_tree_node: %s\n", fname);
 248    node->fname = tree_alloc(root, strlen(fname) + 1);
 249    strcpy(node->fname, fname);
 250    node->parent = parent;
 251    if (!parent->child) {
 252       parent->child = node;
 253       goto item_link;
 254    }
 255    /* Append to end of sibling chain */
 256    for (child=parent->child; child->sibling; child=child->sibling)
 257       { }
 258    child->sibling = node;
 259
 260    /* Maintain a linear chain of nodes */
 261 item_link:
 262    if (!root->first) {
 263       root->first = node;
 264       root->last = node;
 265    } else {
 266       root->last->next = node;
 267       root->last = node;
 268    }
 269    return;
 270 }
 271
 272 TREE_NODE *first_tree_node(TREE_ROOT *root)
 273 {
 274    return root->first;
 275 }
 276
 277 TREE_NODE *next_tree_node(TREE_NODE *node)
 278 {
 279    return node->next;
 280 }
 281
 282
 283 void print_tree(char *path, TREE_NODE *tree)
 284 {
 285    char buf[MAXPATHLEN];
 286    char *termchr;
 287
 288    if (!tree) {
 289       return;
 290    }
 291    switch (tree->type) {
 292    case TN_DIR_NLS:
 293    case TN_DIR:
 294    case TN_NEWDIR:
 295       termchr = "/";
 296       break;
 297    case TN_ROOT:
 298    case TN_FILE:
 299    default:
 300       termchr = "";
 301       break;
 302    }
 303    Dmsg3(-1, "%s/%s%s\n", path, tree->fname, termchr);
 304    switch (tree->type) {
 305    case TN_FILE:
 306       break;
 307    case TN_NEWDIR:
 308    case TN_DIR:
 309    case TN_DIR_NLS:
 310       sprintf(buf, "%s/%s", path, tree->fname);
 311       print_tree(buf, tree->child);
 312       break;
 313    case TN_ROOT:
 314       print_tree(path, tree->child);
 315       break;
 316    default:
 317       Pmsg1(000, "Unknown node type %d\n", tree->type);
 318    }
 319    print_tree(path, tree->sibling);
 320    return;
 321 }
 322
 323 int tree_getpath(TREE_NODE *node, char *buf, int buf_size)
 324 {
 325    if (!node) {
 326       buf[0] = 0;
 327       return 1;
 328    }
 329    tree_getpath(node->parent, buf, buf_size);
 330    /*
 331     * Fixup for Win32. If we have a Win32 directory and
 332     *    there is only a / in the buffer, remove it since
 333     *    win32 names don't generally start with /
 334     */
 335    if (node->type == TN_DIR_NLS && buf[0] == '/' && buf[1] == 0) {
 336       buf[0] = 0;
 337    }
 338    strcat(buf, node->fname);
 339    if (node->type != TN_FILE) {
 340       strcat(buf, "/");
 341    }
 342    return 1;
 343 }
 344
 345 /*
 346  * Change to specified directory
 347  */
 348 TREE_NODE *tree_cwd(char *path, TREE_ROOT *root, TREE_NODE *node)
 349 {
 350    if (strcmp(path, ".") == 0) {
 351       return node;
 352    }
 353    if (strcmp(path, "..") == 0) {
 354       if (node->parent) {
 355          return node->parent;
 356       } else {
 357          return node;
 358       }
 359    }
 360    if (path[0] == '/') {
 361       Dmsg0(100, "Doing absolute lookup.\n");
 362       return tree_relcwd(path+1, root, (TREE_NODE *)root);
 363    }
 364    Dmsg0(100, "Doing relative lookup.\n");
 365    return tree_relcwd(path, root, node);
 366 }
 367
 368
 369 /*
 370  * Do a relative cwd -- i.e. relative to current node rather than root node
 371  */
 372 TREE_NODE *tree_relcwd(char *path, TREE_ROOT *root, TREE_NODE *node)
 373 {
 374    char *p;
 375    int len;
 376    TREE_NODE *cd;
 377
 378    if (*path == 0) {
 379       return node;
 380    }
 381    /* Check the current segment only */
 382    p = strchr(path, '/');
 383    if (p) {
 384       len = p - path;
 385    } else {
 386       len = strlen(path);
 387    }
 388    Dmsg2(100, "tree_relcwd: len=%d path=%s\n", len, path);
 389    for (cd=node->child; cd; cd=cd->sibling) {
 390       Dmsg1(100, "tree_relcwd: test cd=%s\n", cd->fname);
 391       if (cd->fname[0] == path[0] && len == (int)strlen(cd->fname)
 392           && strncmp(cd->fname, path, len) == 0) {
 393          break;
 394       }
 395    }
 396    if (!cd || cd->type == TN_FILE) {
 397       return NULL;
 398    }
 399    if (!p) {
 400       Dmsg0(100, "tree_relcwd: no more to lookup. found.\n");
 401       return cd;
 402    }
 403    Dmsg2(100, "recurse tree_relcwd with path=%s, cd=%s\n", p+1, cd->fname);
 404    /* Check the next segment if any */
 405    return tree_relcwd(p+1, root, cd);
 406 }
 407
 408
 409
 410 #ifdef BUILD_TEST_PROGRAM
 411
 412 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent);
 413
 414 static uint32_t FileIndex = 0;
 415 /*
 416  * Simple test program for tree routines
 417  */
 418 int main(int argc, char *argv[])
 419 {
 420     TREE_ROOT *root;
 421     TREE_NODE *node;
 422     char buf[MAXPATHLEN];
 423
 424     root = new_tree();
 425     root->fname = tree_alloc(root, 1);
 426     *root->fname = 0;
 427
 428     FillDirectoryTree("/home/kern/bacula/k", root, NULL);
 429
 430     for (node = first_tree_node(root); node; node=next_tree_node(node)) {
 431        tree_getpath(node, buf, sizeof(buf));
 432        Dmsg2(100, "%d: %s\n", node->FileIndex, buf);
 433     }
 434
 435     node = (TREE_NODE *)root;
 436     Pmsg0(000, "doing cd /home/kern/bacula/k/techlogs\n");
 437     node = tree_cwd("/home/kern/bacula/k/techlogs", root, node);
 438     if (node) {
 439        tree_getpath(node, buf, sizeof(buf));
 440        Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
 441     }
 442
 443     Pmsg0(000, "doing cd /home/kern/bacula/k/src/testprogs\n");
 444     node = tree_cwd("/home/kern/bacula/k/src/testprogs", root, node);
 445     if (node) {
 446        tree_getpath(node, buf, sizeof(buf));
 447        Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
 448     } else {
 449        Dmsg0(100, "testprogs not found.\n");
 450     }
 451
 452     free_tree((TREE_NODE *)root);
 453
 454     return 0;
 455 }
 456
 457 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent)
 458 {
 459    TREE_NODE *newparent = NULL;
 460    TREE_NODE *node;
 461    struct stat statbuf;
 462    DIR *dp;
 463    struct dirent *dir;
 464    char pathbuf[MAXPATHLEN];
 465    char file[MAXPATHLEN];
 466    int type;
 467    int i;
 468
 469    Dmsg1(100, "FillDirectoryTree: %s\n", path);
 470    dp = opendir(path);
 471    if (!dp) {
 472       return;
 473    }
 474    while ((dir = readdir(dp))) {
 475       if (strcmp(dir->d_name, ".") == 0 || strcmp(dir->d_name, "..") == 0) {
 476          continue;
 477       }
 478       strcpy(file, dir->d_name);
 479       snprintf(pathbuf, MAXPATHLEN-1, "%s/%s", path, file);
 480       if (lstat(pathbuf, &statbuf) < 0) {
 481          printf("lstat() failed. ERR=%s\n", strerror(errno));
 482          continue;
 483       }
 484 //      printf("got file=%s, pathbuf=%s\n", file, pathbuf);
 485       type = TN_FILE;
 486       if (S_ISLNK(statbuf.st_mode))
 487          type =  TN_FILE;  /* link */
 488       else if (S_ISREG(statbuf.st_mode))
 489          type = TN_FILE;
 490       else if (S_ISDIR(statbuf.st_mode)) {
 491          type = TN_DIR;
 492       } else if (S_ISCHR(statbuf.st_mode))
 493          type = TN_FILE; /* char dev */
 494       else if (S_ISBLK(statbuf.st_mode))
 495          type = TN_FILE; /* block dev */
 496       else if (S_ISFIFO(statbuf.st_mode))
 497          type = TN_FILE; /* fifo */
 498       else if (S_ISSOCK(statbuf.st_mode))
 499          type = TN_FILE; /* sock */
 500       else {
 501          type = TN_FILE;
 502          printf("Unknown file type: 0x%x\n", statbuf.st_mode);
 503       }
 504
 505       Dmsg2(100, "Doing: %d %s\n", type, pathbuf);
 506       node = new_tree_node(root, type);
 507       node->FileIndex = ++FileIndex;
 508       parent = insert_tree_node(pathbuf, node, root, parent);
 509       if (S_ISDIR(statbuf.st_mode) && !S_ISLNK(statbuf.st_mode)) {
 510          Dmsg2(100, "calling fill. pathbuf=%s, file=%s\n", pathbuf, file);
 511          FillDirectoryTree(pathbuf, root, node);
 512       }
 513    }
 514    closedir(dp);
 515 }
 516 #endif