X-Git-Url: https://git.sur5r.net/?a=blobdiff_plain;f=bacula%2Fsrc%2Flib%2Ftree.c;h=b223ef8a94f3d26e57c724b36dc0a00277892a08;hb=3f8a3a045ea058657030f588a10f786449d00e0d;hp=3ca5b14692ceb6bdb3afe90e7a3b192e8286e4b5;hpb=3d44fb828df7e93d6111ec16b8def33eddf8f784;p=bacula%2Fbacula diff --git a/bacula/src/lib/tree.c b/bacula/src/lib/tree.c index 3ca5b14692..b223ef8a94 100755 --- a/bacula/src/lib/tree.c +++ b/bacula/src/lib/tree.c @@ -1,37 +1,37 @@ /* * Directory tree build/traverse routines - * + * * Kern Sibbald, June MMII * */ /* - Copyright (C) 2002-2003 Kern Sibbald and John Walker + Copyright (C) 2002-2006 Kern Sibbald This program is free software; you can redistribute it and/or - modify it under the terms of the GNU General Public License as - published by the Free Software Foundation; either version 2 of - the License, or (at your option) any later version. + modify it under the terms of the GNU General Public License + version 2 as amended with additional clauses defined in the + file LICENSE in the main source directory. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - General Public License for more details. - - You should have received a copy of the GNU General Public - License along with this program; if not, write to the Free - Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, - MA 02111-1307, USA. + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + the file LICENSE for additional details. */ #include "bacula.h" #include "findlib/find.h" - -#ifndef MAXPATHLEN -#define MAXPATHLEN 1000 -#endif + +/* Forward referenced subroutines */ +static TREE_NODE *search_and_insert_tree_node(char *fname, int type, + TREE_ROOT *root, TREE_NODE *parent); +static char *tree_alloc(TREE_ROOT *root, int size); + +/* + * NOTE !!!!! we turn off Debug messages for performance reasons. + */ #undef Dmsg0 #undef Dmsg1 #undef Dmsg2 @@ -70,12 +70,11 @@ TREE_ROOT *new_tree(int count) TREE_ROOT *root; uint32_t size; - if (count < 1000) { /* minimum tree size */ + if (count < 1000) { /* minimum tree size */ count = 1000; } root = (TREE_ROOT *)malloc(sizeof(TREE_ROOT)); memset(root, 0, sizeof(TREE_ROOT)); - root->type = TN_ROOT; /* Assume filename + node = 40 characters average length */ size = count * (BALIGN(sizeof(TREE_NODE)) + 40); if (count > 1000000 || size > 10000000) { @@ -83,35 +82,37 @@ TREE_ROOT *new_tree(int count) } Dmsg2(400, "count=%d size=%d\n", count, size); malloc_buf(root, size); + root->cached_path_len = -1; root->cached_path = get_pool_memory(PM_FNAME); + root->type = TN_ROOT; + root->fname = ""; return root; } -/* - * Create a new tree node. Size depends on type. +/* + * Create a new tree node. */ -TREE_NODE *new_tree_node(TREE_ROOT *root, int type) +static TREE_NODE *new_tree_node(TREE_ROOT *root) { TREE_NODE *node; - int asize = BALIGN(sizeof(TREE_NODE)); - - if (root->mem->rem < asize) { - uint32_t mb_size; - if (root->total_size >= 1000000) { - mb_size = 1000000; - } else { - mb_size = 100000; - } - malloc_buf(root, mb_size); - } - root->mem->rem -= asize; - node = (TREE_NODE *)root->mem->mem; - root->mem->mem += asize; - memset(node, 0, sizeof(TREE_NODE)); - node->type = type; + int size = sizeof(TREE_NODE); + node = (TREE_NODE *)tree_alloc(root, size); + memset(node, 0, size); return node; } +/* + * This routine can be called to release the + * previously allocated tree node. + */ +static void free_tree_node(TREE_ROOT *root) +{ + int asize = BALIGN(sizeof(TREE_NODE)); + root->mem->rem += asize; + root->mem->mem -= asize; +} + + /* * Allocate bytes for filename in tree structure. @@ -126,9 +127,9 @@ static char *tree_alloc(TREE_ROOT *root, int size) if (root->mem->rem < asize) { uint32_t mb_size; if (root->total_size >= 1000000) { - mb_size = 1000000; + mb_size = 1000000; } else { - mb_size = 100000; + mb_size = 100000; } malloc_buf(root, mb_size); } @@ -151,6 +152,7 @@ void free_tree(TREE_ROOT *root) } if (root->cached_path) { free_pool_memory(root->cached_path); + root->cached_path = NULL; } Dmsg2(400, "Total size=%u blocks=%d\n", root->total_size, root->blocks); free(root); @@ -158,79 +160,73 @@ void free_tree(TREE_ROOT *root) } - -/* +/* * Insert a node in the tree. This is the main subroutine * called when building a tree. * */ -TREE_NODE *insert_tree_node(char *path, TREE_NODE *node, - TREE_ROOT *root, TREE_NODE *parent) +TREE_NODE *insert_tree_node(char *path, char *fname, int type, + TREE_ROOT *root, TREE_NODE *parent) { - TREE_NODE *sibling; - char *p, *q, *fname; + char *p, *q; int path_len = strlen(path); + TREE_NODE *node; Dmsg1(100, "insert_tree_node: %s\n", path); /* - * If trailing slash, strip it + * If trailing slash on path, strip it */ if (path_len > 0) { q = path + path_len - 1; if (*q == '/') { - *q = 0; /* strip trailing slash */ + *q = 0; /* strip trailing slash */ } else { - q = NULL; /* no trailing slash */ + q = NULL; /* no trailing slash */ } } else { - q = NULL; /* no trailing slash */ + q = NULL; /* no trailing slash */ } - p = strrchr(path, '/'); /* separate path and filename */ - if (p) { - fname = p + 1; - if (!parent) { /* if no parent, we need to make one */ - *p = 0; /* terminate path */ + /* If no filename, strip last component of path as "filename" */ + if (*fname == 0) { + p = strrchr(path, '/'); /* separate path and filename */ + if (p) { + fname = p + 1; /* set new filename */ + *p = 0; /* terminate new path */ + } + } else { + p = NULL; + } + if (*fname) { + if (!parent) { /* if no parent, we need to make one */ Dmsg1(100, "make_tree_path for %s\n", path); - path_len = strlen(path); /* get new length */ - if (path_len == root->cached_path_len && - strcmp(path, root->cached_path) == 0) { - parent = root->cached_parent; - } else { - root->cached_path_len = path_len; - pm_strcpy(&root->cached_path, path); - parent = make_tree_path(path, root); - root->cached_parent = parent; - } + path_len = strlen(path); /* get new length */ + if (path_len == root->cached_path_len && + strcmp(path, root->cached_path) == 0) { + parent = root->cached_parent; + } else { + root->cached_path_len = path_len; + pm_strcpy(&root->cached_path, path); + parent = make_tree_path(path, root); + root->cached_parent = parent; + } Dmsg1(100, "parent=%s\n", parent->fname); - *p = '/'; /* restore full path */ } } else { fname = path; if (!parent) { - parent = (TREE_NODE *)root; - node->type = TN_DIR_NLS; + parent = (TREE_NODE *)root; + type = TN_DIR_NLS; } Dmsg1(100, "No / found: %s\n", path); } - uint16_t fname_len = strlen(fname); - for (sibling=parent->child; sibling; sibling=sibling->sibling) { - Dmsg2(100, "sibling->fname=%s fname=%s\n", sibling->fname, fname); - if (sibling->fname_len == fname_len && - strcmp(sibling->fname, fname) == 0) { - Dmsg1(100, "make_tree_path: found parent=%s\n", parent->fname); - if (q) { /* if trailing slash on entry */ - *q = '/'; /* restore it */ - } - return sibling; - } - } - - append_tree_node(fname, node, root, parent); - Dmsg1(100, "insert_tree_node: parent=%s\n", parent->fname); - if (q) { /* if trailing slash on entry */ + node = search_and_insert_tree_node(fname, 0, root, parent); + if (q) { /* if trailing slash on entry */ *q = '/'; /* restore it */ } + if (p) { /* if slash in path trashed */ + *p = '/'; /* restore full path */ + } return node; } @@ -240,7 +236,7 @@ TREE_NODE *insert_tree_node(char *path, TREE_NODE *node, */ TREE_NODE *make_tree_path(char *path, TREE_ROOT *root) { - TREE_NODE *parent, *sibling, *node; + TREE_NODE *parent, *node; char *fname, *p; int type = TN_NEWDIR; @@ -252,7 +248,7 @@ TREE_NODE *make_tree_path(char *path, TREE_ROOT *root) p = strrchr(path, '/'); /* get last dir component of path */ if (p) { fname = p + 1; - *p = 0; /* terminate path */ + *p = 0; /* terminate path */ parent = make_tree_path(path, root); *p = '/'; /* restore full name */ } else { @@ -260,46 +256,45 @@ TREE_NODE *make_tree_path(char *path, TREE_ROOT *root) parent = (TREE_NODE *)root; type = TN_DIR_NLS; } - /* Is it already a sibling? */ - uint16_t fname_len = strlen(fname); - for (sibling=parent->child; sibling; sibling=sibling->sibling) { - Dmsg2(100, "sibling->fname=%s fname=%s\n", sibling->fname, fname); - if (sibling->fname_len == fname_len && - strcmp(sibling->fname, fname) == 0) { - Dmsg1(100, "make_tree_path: found parent=%s\n", parent->fname); - return sibling; - } - } - /* Must add */ - node = new_tree_node(root, type); - append_tree_node(fname, node, root, parent); - Dmsg1(100, "make_tree_path: add parent=%s\n", node->fname); + node = search_and_insert_tree_node(fname, type, root, parent); return node; -} +} + +static int node_compare(void *item1, void *item2) +{ + TREE_NODE *tn1 = (TREE_NODE *)item1; + TREE_NODE *tn2 = (TREE_NODE *)item2; + if (tn1->fname[0] > tn2->fname[0]) { + return 1; + } else if (tn1->fname[0] < tn2->fname[0]) { + return -1; + } + return strcmp(tn1->fname, tn2->fname); +} /* - * Append sibling to parent's child chain + * See if the fname already exists. If not insert a new node for it. */ -void append_tree_node(char *fname, TREE_NODE *node, TREE_ROOT *root, TREE_NODE *parent) +static TREE_NODE *search_and_insert_tree_node(char *fname, int type, + TREE_ROOT *root, TREE_NODE *parent) { - TREE_NODE *child; - - Dmsg1(100, "append_tree_node: %s\n", fname); + TREE_NODE *node, *found_node; + node = new_tree_node(root); + node->fname = fname; + found_node = (TREE_NODE *)parent->child.binary_insert(node, node_compare); + if (found_node != node) { /* already in list */ + free_tree_node(root); /* free node allocated above */ + found_node->inserted = false; + return found_node; + } + /* It was not found, but is now inserted */ node->fname_len = strlen(fname); node->fname = tree_alloc(root, node->fname_len + 1); strcpy(node->fname, fname); node->parent = parent; - if (!parent->child) { - parent->child = node; - goto item_link; - } - /* Append to end of sibling chain */ - for (child=parent->child; child->sibling; child=child->sibling) - { } - child->sibling = node; + node->type = type; /* Maintain a linear chain of nodes */ -item_link: if (!root->first) { root->first = node; root->last = node; @@ -307,58 +302,9 @@ item_link: root->last->next = node; root->last = node; } - return; -} - -TREE_NODE *first_tree_node(TREE_ROOT *root) -{ - return root->first; -} + node->inserted = true; /* inserted into tree */ + return node; -TREE_NODE *next_tree_node(TREE_NODE *node) -{ - return node->next; -} - - -void print_tree(char *path, TREE_NODE *tree) -{ - char buf[MAXPATHLEN]; - char *termchr; - - if (!tree) { - return; - } - switch (tree->type) { - case TN_DIR_NLS: - case TN_DIR: - case TN_NEWDIR: - termchr = "/"; - break; - case TN_ROOT: - case TN_FILE: - default: - termchr = ""; - break; - } - Dmsg3(-1, "%s/%s%s\n", path, tree->fname, termchr); - switch (tree->type) { - case TN_FILE: - break; - case TN_NEWDIR: - case TN_DIR: - case TN_DIR_NLS: - bsnprintf(buf, sizeof(buf), "%s/%s", path, tree->fname); - print_tree(buf, tree->child); - break; - case TN_ROOT: - print_tree(path, tree->child); - break; - default: - Pmsg1(000, "Unknown node type %d\n", tree->type); - } - print_tree(path, tree->sibling); - return; } int tree_getpath(TREE_NODE *node, char *buf, int buf_size) @@ -368,22 +314,27 @@ int tree_getpath(TREE_NODE *node, char *buf, int buf_size) return 1; } tree_getpath(node->parent, buf, buf_size); - /* - * Fixup for Win32. If we have a Win32 directory and - * there is only a / in the buffer, remove it since + /* + * Fixup for Win32. If we have a Win32 directory and + * there is only a / in the buffer, remove it since * win32 names don't generally start with / */ if (node->type == TN_DIR_NLS && buf[0] == '/' && buf[1] == 0) { - buf[0] = 0; + buf[0] = 0; } bstrncat(buf, node->fname, buf_size); - if (node->type != TN_FILE) { + /* Add a slash for all directories unless we are at the root, + * also add a slash to a soft linked file if it has children + * i.e. it is linked to a directory. + */ + if ((node->type != TN_FILE && !(buf[0] == '/' && buf[1] == 0)) || + (node->soft_link && tree_node_has_child(node))) { bstrncat(buf, "/", buf_size); } return 1; } -/* +/* * Change to specified directory */ TREE_NODE *tree_cwd(char *path, TREE_ROOT *root, TREE_NODE *node) @@ -393,9 +344,9 @@ TREE_NODE *tree_cwd(char *path, TREE_ROOT *root, TREE_NODE *node) } if (strcmp(path, "..") == 0) { if (node->parent) { - return node->parent; + return node->parent; } else { - return node; + return node; } } if (path[0] == '/') { @@ -427,14 +378,14 @@ TREE_NODE *tree_relcwd(char *path, TREE_ROOT *root, TREE_NODE *node) len = strlen(path); } Dmsg2(100, "tree_relcwd: len=%d path=%s\n", len, path); - for (cd=node->child; cd; cd=cd->sibling) { + foreach_child(cd, node) { Dmsg1(100, "tree_relcwd: test cd=%s\n", cd->fname); - if (cd->fname[0] == path[0] && len == (int)strlen(cd->fname) - && strncmp(cd->fname, path, len) == 0) { - break; + if (cd->fname[0] == path[0] && len == (int)strlen(cd->fname) + && strncmp(cd->fname, path, len) == 0) { + break; } } - if (!cd || cd->type == TN_FILE) { + if (!cd || (cd->type == TN_FILE && !tree_node_has_child(cd))) { return NULL; } if (!p) { @@ -507,7 +458,7 @@ void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent) char file[MAXPATHLEN]; int type; int i; - + Dmsg1(100, "FillDirectoryTree: %s\n", path); dp = opendir(path); if (!dp) { @@ -515,44 +466,88 @@ void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent) } while ((dir = readdir(dp))) { if (strcmp(dir->d_name, ".") == 0 || strcmp(dir->d_name, "..") == 0) { - continue; + continue; } bstrncpy(file, dir->d_name, sizeof(file)); snprintf(pathbuf, MAXPATHLEN-1, "%s/%s", path, file); if (lstat(pathbuf, &statbuf) < 0) { printf("lstat() failed. ERR=%s\n", strerror(errno)); - continue; + continue; } // printf("got file=%s, pathbuf=%s\n", file, pathbuf); type = TN_FILE; if (S_ISLNK(statbuf.st_mode)) - type = TN_FILE; /* link */ + type = TN_FILE; /* link */ else if (S_ISREG(statbuf.st_mode)) - type = TN_FILE; + type = TN_FILE; else if (S_ISDIR(statbuf.st_mode)) { - type = TN_DIR; + type = TN_DIR; } else if (S_ISCHR(statbuf.st_mode)) - type = TN_FILE; /* char dev */ + type = TN_FILE; /* char dev */ else if (S_ISBLK(statbuf.st_mode)) - type = TN_FILE; /* block dev */ + type = TN_FILE; /* block dev */ else if (S_ISFIFO(statbuf.st_mode)) - type = TN_FILE; /* fifo */ + type = TN_FILE; /* fifo */ else if (S_ISSOCK(statbuf.st_mode)) - type = TN_FILE; /* sock */ + type = TN_FILE; /* sock */ else { - type = TN_FILE; + type = TN_FILE; printf("Unknown file type: 0x%x\n", statbuf.st_mode); } Dmsg2(100, "Doing: %d %s\n", type, pathbuf); - node = new_tree_node(root, type); + node = new_tree_node(root); node->FileIndex = ++FileIndex; parent = insert_tree_node(pathbuf, node, root, parent); if (S_ISDIR(statbuf.st_mode) && !S_ISLNK(statbuf.st_mode)) { Dmsg2(100, "calling fill. pathbuf=%s, file=%s\n", pathbuf, file); - FillDirectoryTree(pathbuf, root, node); + FillDirectoryTree(pathbuf, root, node); } } closedir(dp); } + +#ifndef MAXPATHLEN +#define MAXPATHLEN 2000 +#endif + +void print_tree(char *path, TREE_NODE *tree) +{ + char buf[MAXPATHLEN]; + char *termchr; + + if (!tree) { + return; + } + switch (tree->type) { + case TN_DIR_NLS: + case TN_DIR: + case TN_NEWDIR: + termchr = "/"; + break; + case TN_ROOT: + case TN_FILE: + default: + termchr = ""; + break; + } + Pmsg3(-1, "%s/%s%s\n", path, tree->fname, termchr); + switch (tree->type) { + case TN_FILE: + case TN_NEWDIR: + case TN_DIR: + case TN_DIR_NLS: + bsnprintf(buf, sizeof(buf), "%s/%s", path, tree->fname); + print_tree(buf, first_child(tree)); + break; + case TN_ROOT: + print_tree(path, first_child(tree)); + break; + default: + Pmsg1(000, "Unknown node type %d\n", tree->type); + } + print_tree(path, tree->sibling_); + return; +} + #endif