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