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 three of the GNU Affero 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 Affero 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);
114 node->delta_seq = -1;
119 * This routine can be called to release the
120 * previously allocated tree node.
122 static void free_tree_node(TREE_ROOT *root)
124 int asize = BALIGN(sizeof(TREE_NODE));
125 root->mem->rem += asize;
126 root->mem->mem -= asize;
129 void tree_remove_node(TREE_ROOT *root, TREE_NODE *node)
131 int asize = BALIGN(sizeof(TREE_NODE));
132 node->parent->child.remove(node);
133 if ((root->mem->mem - asize) == (char *)node) {
134 free_tree_node(root);
136 Dmsg0(0, "Can't release tree node\n");
141 * Allocate bytes for filename in tree structure.
142 * Keep the pointers properly aligned by allocating
143 * sizes that are aligned.
145 static char *tree_alloc(TREE_ROOT *root, int size)
148 int asize = BALIGN(size);
150 if (root->mem->rem < asize) {
152 if (root->total_size >= 1000000) {
157 malloc_buf(root, mb_size);
159 root->mem->rem -= asize;
160 buf = root->mem->mem;
161 root->mem->mem += asize;
166 /* This routine frees the whole tree */
167 void free_tree(TREE_ROOT *root)
169 struct s_mem *mem, *rel;
171 for (mem=root->mem; mem; ) {
176 if (root->cached_path) {
177 free_pool_memory(root->cached_path);
178 root->cached_path = NULL;
180 Dmsg2(400, "Total size=%u blocks=%d\n", root->total_size, root->blocks);
185 /* Add Delta part for this node */
186 void tree_add_delta_part(TREE_ROOT *root, TREE_NODE *node,
187 JobId_t JobId, int32_t FileIndex)
189 struct delta_list *elt =
190 (struct delta_list*) tree_alloc(root, sizeof(struct delta_list));
192 elt->next = node->delta_list;
194 elt->FileIndex = FileIndex;
195 node->delta_list = elt;
199 * Insert a node in the tree. This is the main subroutine
200 * called when building a tree.
203 TREE_NODE *insert_tree_node(char *path, char *fname, int type,
204 TREE_ROOT *root, TREE_NODE *parent)
207 int path_len = strlen(path);
210 Dmsg1(100, "insert_tree_node: %s\n", path);
212 * If trailing slash on path, strip it
215 q = path + path_len - 1;
216 if (IsPathSeparator(*q)) {
217 *q = 0; /* strip trailing slash */
219 q = NULL; /* no trailing slash */
222 q = NULL; /* no trailing slash */
224 /* If no filename, strip last component of path as "filename" */
226 p = (char *)last_path_separator(path); /* separate path and filename */
228 fname = p + 1; /* set new filename */
229 *p = '\0'; /* terminate new path */
235 if (!parent) { /* if no parent, we need to make one */
236 Dmsg1(100, "make_tree_path for %s\n", path);
237 path_len = strlen(path); /* get new length */
238 if (path_len == root->cached_path_len &&
239 strcmp(path, root->cached_path) == 0) {
240 parent = root->cached_parent;
242 root->cached_path_len = path_len;
243 pm_strcpy(&root->cached_path, path);
244 parent = make_tree_path(path, root);
245 root->cached_parent = parent;
247 Dmsg1(100, "parent=%s\n", parent->fname);
252 parent = (TREE_NODE *)root;
255 Dmsg1(100, "No / found: %s\n", path);
258 node = search_and_insert_tree_node(fname, 0, root, parent);
259 if (q) { /* if trailing slash on entry */
260 *q = '/'; /* restore it */
262 if (p) { /* if slash in path trashed */
263 *p = '/'; /* restore full path */
269 * Ensure that all appropriate nodes for a full path exist in
272 TREE_NODE *make_tree_path(char *path, TREE_ROOT *root)
274 TREE_NODE *parent, *node;
276 int type = TN_NEWDIR;
278 Dmsg1(100, "make_tree_path: %s\n", path);
280 Dmsg0(100, "make_tree_path: parent=*root*\n");
281 return (TREE_NODE *)root;
283 p = (char *)last_path_separator(path); /* get last dir component of path */
286 *p = 0; /* terminate path */
287 parent = make_tree_path(path, root);
288 *p = '/'; /* restore full name */
291 parent = (TREE_NODE *)root;
294 node = search_and_insert_tree_node(fname, type, root, parent);
298 static int node_compare(void *item1, void *item2)
300 TREE_NODE *tn1 = (TREE_NODE *)item1;
301 TREE_NODE *tn2 = (TREE_NODE *)item2;
302 if (tn1->fname[0] > tn2->fname[0]) {
304 } else if (tn1->fname[0] < tn2->fname[0]) {
307 return strcmp(tn1->fname, tn2->fname);
311 * See if the fname already exists. If not insert a new node for it.
313 static TREE_NODE *search_and_insert_tree_node(char *fname, int type,
314 TREE_ROOT *root, TREE_NODE *parent)
316 TREE_NODE *node, *found_node;
317 node = new_tree_node(root);
319 found_node = (TREE_NODE *)parent->child.insert(node, node_compare);
320 if (found_node != node) { /* already in list */
321 free_tree_node(root); /* free node allocated above */
322 found_node->inserted = false;
325 /* It was not found, but is now inserted */
326 node->fname_len = strlen(fname);
327 node->fname = tree_alloc(root, node->fname_len + 1);
328 strcpy(node->fname, fname);
329 node->parent = parent;
332 /* Maintain a linear chain of nodes */
337 root->last->next = node;
340 node->inserted = true; /* inserted into tree */
345 int tree_getpath(TREE_NODE *node, char *buf, int buf_size)
351 tree_getpath(node->parent, buf, buf_size);
353 * Fixup for Win32. If we have a Win32 directory and
354 * there is only a / in the buffer, remove it since
355 * win32 names don't generally start with /
357 if (node->type == TN_DIR_NLS && IsPathSeparator(buf[0]) && buf[1] == '\0') {
360 bstrncat(buf, node->fname, buf_size);
361 /* Add a slash for all directories unless we are at the root,
362 * also add a slash to a soft linked file if it has children
363 * i.e. it is linked to a directory.
365 if ((node->type != TN_FILE && !(IsPathSeparator(buf[0]) && buf[1] == '\0')) ||
366 (node->soft_link && tree_node_has_child(node))) {
367 bstrncat(buf, "/", buf_size);
373 * Change to specified directory
375 TREE_NODE *tree_cwd(char *path, TREE_ROOT *root, TREE_NODE *node)
377 if (path[0] == '.' && path[1] == '\0') {
380 /* Handle relative path */
381 if (path[0] == '.' && path[1] == '.' && (IsPathSeparator(path[2]) || path[2] == '\0')) {
382 TREE_NODE *parent = node->parent ? node->parent : node;
386 return tree_cwd(path+3, root, parent);
389 if (IsPathSeparator(path[0])) {
390 Dmsg0(100, "Doing absolute lookup.\n");
391 return tree_relcwd(path+1, root, (TREE_NODE *)root);
393 Dmsg0(100, "Doing relative lookup.\n");
394 return tree_relcwd(path, root, node);
399 * Do a relative cwd -- i.e. relative to current node rather than root node
401 TREE_NODE *tree_relcwd(char *path, TREE_ROOT *root, TREE_NODE *node)
410 /* Check the current segment only */
411 if ((p = first_path_separator(path)) != NULL) {
416 Dmsg2(100, "tree_relcwd: len=%d path=%s\n", len, path);
417 foreach_child(cd, node) {
418 Dmsg1(100, "tree_relcwd: test cd=%s\n", cd->fname);
419 if (cd->fname[0] == path[0] && len == (int)strlen(cd->fname)
420 && strncmp(cd->fname, path, len) == 0) {
424 if (!cd || (cd->type == TN_FILE && !tree_node_has_child(cd))) {
428 Dmsg0(100, "tree_relcwd: no more to lookup. found.\n");
431 Dmsg2(100, "recurse tree_relcwd with path=%s, cd=%s\n", p+1, cd->fname);
432 /* Check the next segment if any */
433 return tree_relcwd(p+1, root, cd);
438 #ifdef BUILD_TEST_PROGRAM
440 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent);
442 static uint32_t FileIndex = 0;
444 * Simple test program for tree routines
446 int main(int argc, char *argv[])
450 char buf[MAXPATHLEN];
453 root->fname = tree_alloc(root, 1);
457 FillDirectoryTree("/home/kern/bacula/k", root, NULL);
459 for (node = first_tree_node(root); node; node=next_tree_node(node)) {
460 tree_getpath(node, buf, sizeof(buf));
461 Dmsg2(100, "%d: %s\n", node->FileIndex, buf);
464 node = (TREE_NODE *)root;
465 Pmsg0(000, "doing cd /home/kern/bacula/k/techlogs\n");
466 node = tree_cwd("/home/kern/bacula/k/techlogs", root, node);
468 tree_getpath(node, buf, sizeof(buf));
469 Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
472 Pmsg0(000, "doing cd /home/kern/bacula/k/src/testprogs\n");
473 node = tree_cwd("/home/kern/bacula/k/src/testprogs", root, node);
475 tree_getpath(node, buf, sizeof(buf));
476 Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
478 Dmsg0(100, "testprogs not found.\n");
481 free_tree((TREE_NODE *)root);
486 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent)
488 TREE_NODE *newparent = NULL;
493 char pathbuf[MAXPATHLEN];
494 char file[MAXPATHLEN];
498 Dmsg1(100, "FillDirectoryTree: %s\n", path);
503 while ((dir = readdir(dp))) {
504 if (strcmp(dir->d_name, ".") == 0 || strcmp(dir->d_name, "..") == 0) {
507 bstrncpy(file, dir->d_name, sizeof(file));
508 snprintf(pathbuf, MAXPATHLEN-1, "%s/%s", path, file);
509 if (lstat(pathbuf, &statbuf) < 0) {
511 printf("lstat() failed. ERR=%s\n", be.bstrerror(errno));
514 // printf("got file=%s, pathbuf=%s\n", file, pathbuf);
516 if (S_ISLNK(statbuf.st_mode))
517 type = TN_FILE; /* link */
518 else if (S_ISREG(statbuf.st_mode))
520 else if (S_ISDIR(statbuf.st_mode)) {
522 } else if (S_ISCHR(statbuf.st_mode))
523 type = TN_FILE; /* char dev */
524 else if (S_ISBLK(statbuf.st_mode))
525 type = TN_FILE; /* block dev */
526 else if (S_ISFIFO(statbuf.st_mode))
527 type = TN_FILE; /* fifo */
528 else if (S_ISSOCK(statbuf.st_mode))
529 type = TN_FILE; /* sock */
532 printf("Unknown file type: 0x%x\n", statbuf.st_mode);
535 Dmsg2(100, "Doing: %d %s\n", type, pathbuf);
536 node = new_tree_node(root);
537 node->FileIndex = ++FileIndex;
538 parent = insert_tree_node(pathbuf, node, root, parent);
539 if (S_ISDIR(statbuf.st_mode) && !S_ISLNK(statbuf.st_mode)) {
540 Dmsg2(100, "calling fill. pathbuf=%s, file=%s\n", pathbuf, file);
541 FillDirectoryTree(pathbuf, root, node);
548 #define MAXPATHLEN 2000
551 void print_tree(char *path, TREE_NODE *tree)
553 char buf[MAXPATHLEN];
559 switch (tree->type) {
571 Pmsg3(-1, "%s/%s%s\n", path, tree->fname, termchr);
572 switch (tree->type) {
577 bsnprintf(buf, sizeof(buf), "%s/%s", path, tree->fname);
578 print_tree(buf, first_child(tree));
581 print_tree(path, first_child(tree));
584 Pmsg1(000, "Unknown node type %d\n", tree->type);
586 print_tree(path, tree->sibling_);