2 * Directory tree build/traverse routines
4 * Kern Sibbald, June MMII
8 Copyright (C) 2002-2004 Kern Sibbald and John Walker
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.
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.
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,
29 #include "findlib/find.h"
32 /* Forward referenced subroutines */
33 static TREE_NODE *search_and_insert_tree_node(char *fname, int type,
34 TREE_ROOT *root, TREE_NODE *parent);
35 static char *tree_alloc(TREE_ROOT *root, int size);
38 * NOTE !!!!! we turn off Debug messages for performance reasons.
46 #define Dmsg2(n,f,a1,a2)
47 #define Dmsg3(n,f,a1,a2,a3)
50 * This subroutine gets a big buffer.
52 static void malloc_buf(TREE_ROOT *root, int size)
56 mem = (struct s_mem *)malloc(size);
57 root->total_size += size;
59 mem->next = root->mem;
61 mem->mem = mem->first;
62 mem->rem = (char *)mem + size - mem->mem;
63 Dmsg2(200, "malloc buf size=%d rem=%d\n", size, mem->rem);
68 * Note, we allocate a big buffer in the tree root
69 * from which we allocate nodes. This runs more
70 * than 100 times as fast as directly using malloc()
71 * for each of the nodes.
73 TREE_ROOT *new_tree(int count)
78 if (count < 1000) { /* minimum tree size */
81 root = (TREE_ROOT *)malloc(sizeof(TREE_ROOT));
82 memset(root, 0, sizeof(TREE_ROOT));
83 /* Assume filename + node = 40 characters average length */
84 size = count * (BALIGN(sizeof(TREE_NODE)) + 40);
85 if (count > 1000000 || size > 10000000) {
88 Dmsg2(400, "count=%d size=%d\n", count, size);
89 malloc_buf(root, size);
90 root->cached_path_len = -1;
91 root->cached_path = get_pool_memory(PM_FNAME);
98 * Create a new tree node.
100 static TREE_NODE *new_tree_node(TREE_ROOT *root)
103 int size = sizeof(TREE_NODE);
104 node = (TREE_NODE *)tree_alloc(root, size);
105 memset(node, 0, size);
111 * This routine can be called to release the
112 * previously allocated tree node.
114 static void free_tree_node(TREE_ROOT *root)
116 int asize = BALIGN(sizeof(TREE_NODE));
117 root->mem->rem += asize;
118 root->mem->mem -= asize;
125 * Allocate bytes for filename in tree structure.
126 * Keep the pointers properly aligned by allocating
127 * sizes that are aligned.
129 static char *tree_alloc(TREE_ROOT *root, int size)
132 int asize = BALIGN(size);
134 if (root->mem->rem < asize) {
136 if (root->total_size >= 1000000) {
141 malloc_buf(root, mb_size);
143 root->mem->rem -= asize;
144 buf = root->mem->mem;
145 root->mem->mem += asize;
150 /* This routine frees the whole tree */
151 void free_tree(TREE_ROOT *root)
153 struct s_mem *mem, *rel;
155 for (mem=root->mem; mem; ) {
160 if (root->cached_path) {
161 free_pool_memory(root->cached_path);
162 root->cached_path = NULL;
164 Dmsg2(400, "Total size=%u blocks=%d\n", root->total_size, root->blocks);
171 * Insert a node in the tree. This is the main subroutine
172 * called when building a tree.
175 TREE_NODE *insert_tree_node(char *path, char *fname, int type,
176 TREE_ROOT *root, TREE_NODE *parent)
179 int path_len = strlen(path);
182 Dmsg1(100, "insert_tree_node: %s\n", path);
184 * If trailing slash on path, strip it
187 q = path + path_len - 1;
189 *q = 0; /* strip trailing slash */
191 q = NULL; /* no trailing slash */
194 q = NULL; /* no trailing slash */
196 /* If no filename, strip last component of path as "filename" */
198 p = strrchr(path, '/'); /* separate path and filename */
200 fname = p + 1; /* set new filename */
201 *p = 0; /* terminate new path */
207 if (!parent) { /* if no parent, we need to make one */
208 Dmsg1(100, "make_tree_path for %s\n", path);
209 path_len = strlen(path); /* get new length */
210 if (path_len == root->cached_path_len &&
211 strcmp(path, root->cached_path) == 0) {
212 parent = root->cached_parent;
214 root->cached_path_len = path_len;
215 pm_strcpy(&root->cached_path, path);
216 parent = make_tree_path(path, root);
217 root->cached_parent = parent;
219 Dmsg1(100, "parent=%s\n", parent->fname);
224 parent = (TREE_NODE *)root;
227 Dmsg1(100, "No / found: %s\n", path);
230 node = search_and_insert_tree_node(fname, 0, root, parent);
231 if (q) { /* if trailing slash on entry */
232 *q = '/'; /* restore it */
234 if (p) { /* if slash in path trashed */
235 *p = '/'; /* restore full path */
241 * Ensure that all appropriate nodes for a full path exist in
244 TREE_NODE *make_tree_path(char *path, TREE_ROOT *root)
246 TREE_NODE *parent, *node;
248 int type = TN_NEWDIR;
250 Dmsg1(100, "make_tree_path: %s\n", path);
252 Dmsg0(100, "make_tree_path: parent=*root*\n");
253 return (TREE_NODE *)root;
255 p = strrchr(path, '/'); /* get last dir component of path */
258 *p = 0; /* terminate path */
259 parent = make_tree_path(path, root);
260 *p = '/'; /* restore full name */
263 parent = (TREE_NODE *)root;
266 node = search_and_insert_tree_node(fname, type, root, parent);
271 static int node_compare(void *item1, void *item2)
273 TREE_NODE *tn1 = (TREE_NODE *)item1;
274 TREE_NODE *tn2 = (TREE_NODE *)item2;
275 if (tn1->fname[0] > tn2->fname[0]) {
277 } else if (tn1->fname[0] < tn2->fname[0]) {
280 return strcmp(tn1->fname, tn2->fname);
285 * See if the fname already exists. If not insert a new node for it.
287 static TREE_NODE *search_and_insert_tree_node(char *fname, int type,
288 TREE_ROOT *root, TREE_NODE *parent)
291 TREE_NODE *node, *found_node;
292 node = new_tree_node(root);
294 found_node = (TREE_NODE *)parent->child.unique_binary_insert(node, node_compare);
295 if (found_node != node) { /* already in list */
296 free_tree_node(root); /* free node allocated above */
297 found_node->inserted = false;
300 /* It was not found, but is now inserted */
301 node->fname_len = strlen(fname);
302 node->fname = tree_alloc(root, node->fname_len + 1);
303 strcpy(node->fname, fname);
304 node->parent = parent;
307 /* Maintain a linear chain of nodes */
312 root->last->next = node;
315 node->inserted = true; /* inserted into tree */
319 TREE_NODE *sibling, *last_sibling = NULL;
320 uint16_t fname_len = strlen(fname);
323 /* Is it already a sibling? */
324 foreach_child(sibling, parent) {
325 Dmsg2(000, "sibling->fname=%s fname=%s\n", sibling->fname, fname);
326 if (fname[0] > sibling->fname[0] || (cmp=strcmp(fname, sibling->fname)) > 0) {
327 last_sibling = sibling;
331 /* Insert before current sibling */
333 node = new_tree_node(root);
335 node->sibling_ = sibling;
336 if (sibling == first_child(parent)) { /* if sibling was at head of list */
337 parent->child_ = NULL; /* force parent to be updated below */
339 Dmsg2(000, "insert before sibling->fname=%s fname=%s\n", sibling->fname, fname);
343 sibling->inserted = false; /* already in tree */
349 * At this point, the fname is not found. We must add it
352 node = new_tree_node(root);
354 Dmsg1(000, "append_tree_node: %s\n", fname);
355 node->fname_len = fname_len;
356 node->fname = tree_alloc(root, node->fname_len + 1);
357 strcpy(node->fname, fname);
358 node->parent = parent;
360 if (!tree_node_has_child(parent)) {
361 parent->child_ = node;
363 last_sibling->sibling_ = node;
366 /* Maintain a linear chain of nodes */
371 root->last->next = node;
374 node->inserted = true; /* inserted into tree */
380 /* Moved to tree.h to eliminate subroutine call */
381 TREE_NODE *first_tree_node(TREE_ROOT *root)
386 TREE_NODE *next_tree_node(TREE_NODE *node)
394 int tree_getpath(TREE_NODE *node, char *buf, int buf_size)
400 tree_getpath(node->parent, buf, buf_size);
402 * Fixup for Win32. If we have a Win32 directory and
403 * there is only a / in the buffer, remove it since
404 * win32 names don't generally start with /
406 if (node->type == TN_DIR_NLS && buf[0] == '/' && buf[1] == 0) {
409 bstrncat(buf, node->fname, buf_size);
410 /* Add a slash for all directories unless we are at the root,
411 * also add a slash to a soft linked file if it has children
412 * i.e. it is linked to a directory.
414 if ((node->type != TN_FILE && !(buf[0] == '/' && buf[1] == 0)) ||
415 (node->soft_link && tree_node_has_child(node))) {
416 bstrncat(buf, "/", buf_size);
422 * Change to specified directory
424 TREE_NODE *tree_cwd(char *path, TREE_ROOT *root, TREE_NODE *node)
426 if (strcmp(path, ".") == 0) {
429 if (strcmp(path, "..") == 0) {
436 if (path[0] == '/') {
437 Dmsg0(100, "Doing absolute lookup.\n");
438 return tree_relcwd(path+1, root, (TREE_NODE *)root);
440 Dmsg0(100, "Doing relative lookup.\n");
441 return tree_relcwd(path, root, node);
446 * Do a relative cwd -- i.e. relative to current node rather than root node
448 TREE_NODE *tree_relcwd(char *path, TREE_ROOT *root, TREE_NODE *node)
457 /* Check the current segment only */
458 p = strchr(path, '/');
464 Dmsg2(100, "tree_relcwd: len=%d path=%s\n", len, path);
465 foreach_child(cd, node) {
466 Dmsg1(100, "tree_relcwd: test cd=%s\n", cd->fname);
467 if (cd->fname[0] == path[0] && len == (int)strlen(cd->fname)
468 && strncmp(cd->fname, path, len) == 0) {
472 if (!cd || (cd->type == TN_FILE && !tree_node_has_child(cd))) {
476 Dmsg0(100, "tree_relcwd: no more to lookup. found.\n");
479 Dmsg2(100, "recurse tree_relcwd with path=%s, cd=%s\n", p+1, cd->fname);
480 /* Check the next segment if any */
481 return tree_relcwd(p+1, root, cd);
486 #ifdef BUILD_TEST_PROGRAM
488 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent);
490 static uint32_t FileIndex = 0;
492 * Simple test program for tree routines
494 int main(int argc, char *argv[])
498 char buf[MAXPATHLEN];
501 root->fname = tree_alloc(root, 1);
505 FillDirectoryTree("/home/kern/bacula/k", root, NULL);
507 for (node = first_tree_node(root); node; node=next_tree_node(node)) {
508 tree_getpath(node, buf, sizeof(buf));
509 Dmsg2(100, "%d: %s\n", node->FileIndex, buf);
512 node = (TREE_NODE *)root;
513 Pmsg0(000, "doing cd /home/kern/bacula/k/techlogs\n");
514 node = tree_cwd("/home/kern/bacula/k/techlogs", root, node);
516 tree_getpath(node, buf, sizeof(buf));
517 Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
520 Pmsg0(000, "doing cd /home/kern/bacula/k/src/testprogs\n");
521 node = tree_cwd("/home/kern/bacula/k/src/testprogs", root, node);
523 tree_getpath(node, buf, sizeof(buf));
524 Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
526 Dmsg0(100, "testprogs not found.\n");
529 free_tree((TREE_NODE *)root);
534 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent)
536 TREE_NODE *newparent = NULL;
541 char pathbuf[MAXPATHLEN];
542 char file[MAXPATHLEN];
546 Dmsg1(100, "FillDirectoryTree: %s\n", path);
551 while ((dir = readdir(dp))) {
552 if (strcmp(dir->d_name, ".") == 0 || strcmp(dir->d_name, "..") == 0) {
555 bstrncpy(file, dir->d_name, sizeof(file));
556 snprintf(pathbuf, MAXPATHLEN-1, "%s/%s", path, file);
557 if (lstat(pathbuf, &statbuf) < 0) {
558 printf("lstat() failed. ERR=%s\n", strerror(errno));
561 // printf("got file=%s, pathbuf=%s\n", file, pathbuf);
563 if (S_ISLNK(statbuf.st_mode))
564 type = TN_FILE; /* link */
565 else if (S_ISREG(statbuf.st_mode))
567 else if (S_ISDIR(statbuf.st_mode)) {
569 } else if (S_ISCHR(statbuf.st_mode))
570 type = TN_FILE; /* char dev */
571 else if (S_ISBLK(statbuf.st_mode))
572 type = TN_FILE; /* block dev */
573 else if (S_ISFIFO(statbuf.st_mode))
574 type = TN_FILE; /* fifo */
575 else if (S_ISSOCK(statbuf.st_mode))
576 type = TN_FILE; /* sock */
579 printf("Unknown file type: 0x%x\n", statbuf.st_mode);
582 Dmsg2(100, "Doing: %d %s\n", type, pathbuf);
583 node = new_tree_node(root);
584 node->FileIndex = ++FileIndex;
585 parent = insert_tree_node(pathbuf, node, root, parent);
586 if (S_ISDIR(statbuf.st_mode) && !S_ISLNK(statbuf.st_mode)) {
587 Dmsg2(100, "calling fill. pathbuf=%s, file=%s\n", pathbuf, file);
588 FillDirectoryTree(pathbuf, root, node);
595 #define MAXPATHLEN 2000
598 void print_tree(char *path, TREE_NODE *tree)
600 char buf[MAXPATHLEN];
606 switch (tree->type) {
618 Dmsg3(-1, "%s/%s%s\n", path, tree->fname, termchr);
619 switch (tree->type) {
624 bsnprintf(buf, sizeof(buf), "%s/%s", path, tree->fname);
625 print_tree(buf, first_child(tree));
628 print_tree(path, first_child(tree));
631 Pmsg1(000, "Unknown node type %d\n", tree->type);
633 print_tree(path, tree->sibling_);