2 Bacula® - The Network Backup Solution
4 Copyright (C) 2002-2008 Free Software Foundation Europe e.V.
6 The main author of Bacula is Kern Sibbald, with contributions from
7 many others, a complete list can be found in the file AUTHORS.
8 This program is Free Software; you can redistribute it and/or
9 modify it under the terms of version two of the GNU General Public
10 License as published by the Free Software Foundation and included
13 This program is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with this program; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
23 Bacula® is a registered trademark of Kern Sibbald.
24 The licensor of Bacula is the Free Software Foundation Europe
25 (FSFE), Fiduciary Program, Sumatrastrasse 25, 8006 Zürich,
26 Switzerland, email:ftf@fsfeurope.org.
29 * Directory tree build/traverse routines
31 * Kern Sibbald, June MMII
37 #include "findlib/find.h"
40 /* Forward referenced subroutines */
41 static TREE_NODE *search_and_insert_tree_node(char *fname, int type,
42 TREE_ROOT *root, TREE_NODE *parent);
43 static char *tree_alloc(TREE_ROOT *root, int size);
46 * NOTE !!!!! we turn off Debug messages for performance reasons.
54 #define Dmsg2(n,f,a1,a2)
55 #define Dmsg3(n,f,a1,a2,a3)
58 * This subroutine gets a big buffer.
60 static void malloc_buf(TREE_ROOT *root, int size)
64 mem = (struct s_mem *)malloc(size);
65 root->total_size += size;
67 mem->next = root->mem;
69 mem->mem = mem->first;
70 mem->rem = (char *)mem + size - mem->mem;
71 Dmsg2(200, "malloc buf size=%d rem=%d\n", size, mem->rem);
76 * Note, we allocate a big buffer in the tree root
77 * from which we allocate nodes. This runs more
78 * than 100 times as fast as directly using malloc()
79 * for each of the nodes.
81 TREE_ROOT *new_tree(int count)
86 if (count < 1000) { /* minimum tree size */
89 root = (TREE_ROOT *)malloc(sizeof(TREE_ROOT));
90 memset(root, 0, sizeof(TREE_ROOT));
91 /* Assume filename + node = 40 characters average length */
92 size = count * (BALIGN(sizeof(TREE_NODE)) + 40);
93 if (count > 1000000 || size > 10000000) {
96 Dmsg2(400, "count=%d size=%d\n", count, size);
97 malloc_buf(root, size);
98 root->cached_path_len = -1;
99 root->cached_path = get_pool_memory(PM_FNAME);
100 root->type = TN_ROOT;
106 * Create a new tree node.
108 static TREE_NODE *new_tree_node(TREE_ROOT *root)
111 int size = sizeof(TREE_NODE);
112 node = (TREE_NODE *)tree_alloc(root, size);
113 memset(node, 0, size);
118 * This routine can be called to release the
119 * previously allocated tree node.
121 static void free_tree_node(TREE_ROOT *root)
123 int asize = BALIGN(sizeof(TREE_NODE));
124 root->mem->rem += asize;
125 root->mem->mem -= asize;
131 * Allocate bytes for filename in tree structure.
132 * Keep the pointers properly aligned by allocating
133 * sizes that are aligned.
135 static char *tree_alloc(TREE_ROOT *root, int size)
138 int asize = BALIGN(size);
140 if (root->mem->rem < asize) {
142 if (root->total_size >= 1000000) {
147 malloc_buf(root, mb_size);
149 root->mem->rem -= asize;
150 buf = root->mem->mem;
151 root->mem->mem += asize;
156 /* This routine frees the whole tree */
157 void free_tree(TREE_ROOT *root)
159 struct s_mem *mem, *rel;
161 for (mem=root->mem; mem; ) {
166 if (root->cached_path) {
167 free_pool_memory(root->cached_path);
168 root->cached_path = NULL;
170 Dmsg2(400, "Total size=%u blocks=%d\n", root->total_size, root->blocks);
177 * Insert a node in the tree. This is the main subroutine
178 * called when building a tree.
181 TREE_NODE *insert_tree_node(char *path, char *fname, int type,
182 TREE_ROOT *root, TREE_NODE *parent)
185 int path_len = strlen(path);
188 Dmsg1(100, "insert_tree_node: %s\n", path);
190 * If trailing slash on path, strip it
193 q = path + path_len - 1;
194 if (IsPathSeparator(*q)) {
195 *q = 0; /* strip trailing slash */
197 q = NULL; /* no trailing slash */
200 q = NULL; /* no trailing slash */
202 /* If no filename, strip last component of path as "filename" */
204 p = (char *)last_path_separator(path); /* separate path and filename */
206 fname = p + 1; /* set new filename */
207 *p = '\0'; /* terminate new path */
213 if (!parent) { /* if no parent, we need to make one */
214 Dmsg1(100, "make_tree_path for %s\n", path);
215 path_len = strlen(path); /* get new length */
216 if (path_len == root->cached_path_len &&
217 strcmp(path, root->cached_path) == 0) {
218 parent = root->cached_parent;
220 root->cached_path_len = path_len;
221 pm_strcpy(&root->cached_path, path);
222 parent = make_tree_path(path, root);
223 root->cached_parent = parent;
225 Dmsg1(100, "parent=%s\n", parent->fname);
230 parent = (TREE_NODE *)root;
233 Dmsg1(100, "No / found: %s\n", path);
236 node = search_and_insert_tree_node(fname, 0, root, parent);
237 if (q) { /* if trailing slash on entry */
238 *q = '/'; /* restore it */
240 if (p) { /* if slash in path trashed */
241 *p = '/'; /* restore full path */
247 * Ensure that all appropriate nodes for a full path exist in
250 TREE_NODE *make_tree_path(char *path, TREE_ROOT *root)
252 TREE_NODE *parent, *node;
254 int type = TN_NEWDIR;
256 Dmsg1(100, "make_tree_path: %s\n", path);
258 Dmsg0(100, "make_tree_path: parent=*root*\n");
259 return (TREE_NODE *)root;
261 p = (char *)last_path_separator(path); /* get last dir component of path */
264 *p = 0; /* terminate path */
265 parent = make_tree_path(path, root);
266 *p = '/'; /* restore full name */
269 parent = (TREE_NODE *)root;
272 node = search_and_insert_tree_node(fname, type, root, parent);
276 static int node_compare(void *item1, void *item2)
278 TREE_NODE *tn1 = (TREE_NODE *)item1;
279 TREE_NODE *tn2 = (TREE_NODE *)item2;
280 if (tn1->fname[0] > tn2->fname[0]) {
282 } else if (tn1->fname[0] < tn2->fname[0]) {
285 return strcmp(tn1->fname, tn2->fname);
289 * See if the fname already exists. If not insert a new node for it.
291 static TREE_NODE *search_and_insert_tree_node(char *fname, int type,
292 TREE_ROOT *root, TREE_NODE *parent)
294 TREE_NODE *node, *found_node;
295 node = new_tree_node(root);
297 found_node = (TREE_NODE *)parent->child.insert(node, node_compare);
298 if (found_node != node) { /* already in list */
299 free_tree_node(root); /* free node allocated above */
300 found_node->inserted = false;
303 /* It was not found, but is now inserted */
304 node->fname_len = strlen(fname);
305 node->fname = tree_alloc(root, node->fname_len + 1);
306 strcpy(node->fname, fname);
307 node->parent = parent;
310 /* Maintain a linear chain of nodes */
315 root->last->next = node;
318 node->inserted = true; /* inserted into tree */
323 int tree_getpath(TREE_NODE *node, char *buf, int buf_size)
329 tree_getpath(node->parent, buf, buf_size);
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 /
335 if (node->type == TN_DIR_NLS && IsPathSeparator(buf[0]) && buf[1] == '\0') {
338 bstrncat(buf, node->fname, buf_size);
339 /* Add a slash for all directories unless we are at the root,
340 * also add a slash to a soft linked file if it has children
341 * i.e. it is linked to a directory.
343 if ((node->type != TN_FILE && !(IsPathSeparator(buf[0]) && buf[1] == '\0')) ||
344 (node->soft_link && tree_node_has_child(node))) {
345 bstrncat(buf, "/", buf_size);
351 * Change to specified directory
353 TREE_NODE *tree_cwd(char *path, TREE_ROOT *root, TREE_NODE *node)
355 if (path[0] == '.' && path[1] == '\0') {
358 /* Handle relative path */
359 if (path[0] == '.' && path[1] == '.' && (IsPathSeparator(path[2]) || path[2] == '\0')) {
360 TREE_NODE *parent = node->parent ? node->parent : node;
364 return tree_cwd(path+3, root, parent);
367 if (IsPathSeparator(path[0])) {
368 Dmsg0(100, "Doing absolute lookup.\n");
369 return tree_relcwd(path+1, root, (TREE_NODE *)root);
371 Dmsg0(100, "Doing relative lookup.\n");
372 return tree_relcwd(path, root, node);
377 * Do a relative cwd -- i.e. relative to current node rather than root node
379 TREE_NODE *tree_relcwd(char *path, TREE_ROOT *root, TREE_NODE *node)
388 /* Check the current segment only */
389 if ((p = first_path_separator(path)) != NULL) {
394 Dmsg2(100, "tree_relcwd: len=%d path=%s\n", len, path);
395 foreach_child(cd, node) {
396 Dmsg1(100, "tree_relcwd: test cd=%s\n", cd->fname);
397 if (cd->fname[0] == path[0] && len == (int)strlen(cd->fname)
398 && strncmp(cd->fname, path, len) == 0) {
402 if (!cd || (cd->type == TN_FILE && !tree_node_has_child(cd))) {
406 Dmsg0(100, "tree_relcwd: no more to lookup. found.\n");
409 Dmsg2(100, "recurse tree_relcwd with path=%s, cd=%s\n", p+1, cd->fname);
410 /* Check the next segment if any */
411 return tree_relcwd(p+1, root, cd);
416 #ifdef BUILD_TEST_PROGRAM
418 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent);
420 static uint32_t FileIndex = 0;
422 * Simple test program for tree routines
424 int main(int argc, char *argv[])
428 char buf[MAXPATHLEN];
431 root->fname = tree_alloc(root, 1);
435 FillDirectoryTree("/home/kern/bacula/k", root, NULL);
437 for (node = first_tree_node(root); node; node=next_tree_node(node)) {
438 tree_getpath(node, buf, sizeof(buf));
439 Dmsg2(100, "%d: %s\n", node->FileIndex, buf);
442 node = (TREE_NODE *)root;
443 Pmsg0(000, "doing cd /home/kern/bacula/k/techlogs\n");
444 node = tree_cwd("/home/kern/bacula/k/techlogs", root, node);
446 tree_getpath(node, buf, sizeof(buf));
447 Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
450 Pmsg0(000, "doing cd /home/kern/bacula/k/src/testprogs\n");
451 node = tree_cwd("/home/kern/bacula/k/src/testprogs", root, node);
453 tree_getpath(node, buf, sizeof(buf));
454 Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
456 Dmsg0(100, "testprogs not found.\n");
459 free_tree((TREE_NODE *)root);
464 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent)
466 TREE_NODE *newparent = NULL;
471 char pathbuf[MAXPATHLEN];
472 char file[MAXPATHLEN];
476 Dmsg1(100, "FillDirectoryTree: %s\n", path);
481 while ((dir = readdir(dp))) {
482 if (strcmp(dir->d_name, ".") == 0 || strcmp(dir->d_name, "..") == 0) {
485 bstrncpy(file, dir->d_name, sizeof(file));
486 snprintf(pathbuf, MAXPATHLEN-1, "%s/%s", path, file);
487 if (lstat(pathbuf, &statbuf) < 0) {
489 printf("lstat() failed. ERR=%s\n", be.bstrerror(errno));
492 // printf("got file=%s, pathbuf=%s\n", file, pathbuf);
494 if (S_ISLNK(statbuf.st_mode))
495 type = TN_FILE; /* link */
496 else if (S_ISREG(statbuf.st_mode))
498 else if (S_ISDIR(statbuf.st_mode)) {
500 } else if (S_ISCHR(statbuf.st_mode))
501 type = TN_FILE; /* char dev */
502 else if (S_ISBLK(statbuf.st_mode))
503 type = TN_FILE; /* block dev */
504 else if (S_ISFIFO(statbuf.st_mode))
505 type = TN_FILE; /* fifo */
506 else if (S_ISSOCK(statbuf.st_mode))
507 type = TN_FILE; /* sock */
510 printf("Unknown file type: 0x%x\n", statbuf.st_mode);
513 Dmsg2(100, "Doing: %d %s\n", type, pathbuf);
514 node = new_tree_node(root);
515 node->FileIndex = ++FileIndex;
516 parent = insert_tree_node(pathbuf, node, root, parent);
517 if (S_ISDIR(statbuf.st_mode) && !S_ISLNK(statbuf.st_mode)) {
518 Dmsg2(100, "calling fill. pathbuf=%s, file=%s\n", pathbuf, file);
519 FillDirectoryTree(pathbuf, root, node);
526 #define MAXPATHLEN 2000
529 void print_tree(char *path, TREE_NODE *tree)
531 char buf[MAXPATHLEN];
537 switch (tree->type) {
549 Pmsg3(-1, "%s/%s%s\n", path, tree->fname, termchr);
550 switch (tree->type) {
555 bsnprintf(buf, sizeof(buf), "%s/%s", path, tree->fname);
556 print_tree(buf, first_child(tree));
559 print_tree(path, first_child(tree));
562 Pmsg1(000, "Unknown node type %d\n", tree->type);
564 print_tree(path, tree->sibling_);