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