2 * Directory tree build/traverse routines
4 * Kern Sibbald, June MMII
8 Copyright (C) 2002-2006 Kern Sibbald
10 This program is free software; you can redistribute it and/or
11 modify it under the terms of the GNU General Public License
12 version 2 as amended with additional clauses defined in the
13 file LICENSE in the main source directory.
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
18 the file LICENSE for additional details.
24 #include "findlib/find.h"
27 /* Forward referenced subroutines */
28 static TREE_NODE *search_and_insert_tree_node(char *fname, int type,
29 TREE_ROOT *root, TREE_NODE *parent);
30 static char *tree_alloc(TREE_ROOT *root, int size);
33 * NOTE !!!!! we turn off Debug messages for performance reasons.
41 #define Dmsg2(n,f,a1,a2)
42 #define Dmsg3(n,f,a1,a2,a3)
45 * This subroutine gets a big buffer.
47 static void malloc_buf(TREE_ROOT *root, int size)
51 mem = (struct s_mem *)malloc(size);
52 root->total_size += size;
54 mem->next = root->mem;
56 mem->mem = mem->first;
57 mem->rem = (char *)mem + size - mem->mem;
58 Dmsg2(200, "malloc buf size=%d rem=%d\n", size, mem->rem);
63 * Note, we allocate a big buffer in the tree root
64 * from which we allocate nodes. This runs more
65 * than 100 times as fast as directly using malloc()
66 * for each of the nodes.
68 TREE_ROOT *new_tree(int count)
73 if (count < 1000) { /* minimum tree size */
76 root = (TREE_ROOT *)malloc(sizeof(TREE_ROOT));
77 memset(root, 0, sizeof(TREE_ROOT));
78 /* Assume filename + node = 40 characters average length */
79 size = count * (BALIGN(sizeof(TREE_NODE)) + 40);
80 if (count > 1000000 || size > 10000000) {
83 Dmsg2(400, "count=%d size=%d\n", count, size);
84 malloc_buf(root, size);
85 root->cached_path_len = -1;
86 root->cached_path = get_pool_memory(PM_FNAME);
93 * Create a new tree node.
95 static TREE_NODE *new_tree_node(TREE_ROOT *root)
98 int size = sizeof(TREE_NODE);
99 node = (TREE_NODE *)tree_alloc(root, size);
100 memset(node, 0, size);
105 * This routine can be called to release the
106 * previously allocated tree node.
108 static void free_tree_node(TREE_ROOT *root)
110 int asize = BALIGN(sizeof(TREE_NODE));
111 root->mem->rem += asize;
112 root->mem->mem -= asize;
118 * Allocate bytes for filename in tree structure.
119 * Keep the pointers properly aligned by allocating
120 * sizes that are aligned.
122 static char *tree_alloc(TREE_ROOT *root, int size)
125 int asize = BALIGN(size);
127 if (root->mem->rem < asize) {
129 if (root->total_size >= 1000000) {
134 malloc_buf(root, mb_size);
136 root->mem->rem -= asize;
137 buf = root->mem->mem;
138 root->mem->mem += asize;
143 /* This routine frees the whole tree */
144 void free_tree(TREE_ROOT *root)
146 struct s_mem *mem, *rel;
148 for (mem=root->mem; mem; ) {
153 if (root->cached_path) {
154 free_pool_memory(root->cached_path);
155 root->cached_path = NULL;
157 Dmsg2(400, "Total size=%u blocks=%d\n", root->total_size, root->blocks);
164 * Insert a node in the tree. This is the main subroutine
165 * called when building a tree.
168 TREE_NODE *insert_tree_node(char *path, char *fname, int type,
169 TREE_ROOT *root, TREE_NODE *parent)
172 int path_len = strlen(path);
175 Dmsg1(100, "insert_tree_node: %s\n", path);
177 * If trailing slash on path, strip it
180 q = path + path_len - 1;
182 *q = 0; /* strip trailing slash */
184 q = NULL; /* no trailing slash */
187 q = NULL; /* no trailing slash */
189 /* If no filename, strip last component of path as "filename" */
191 p = strrchr(path, '/'); /* separate path and filename */
193 fname = p + 1; /* set new filename */
194 *p = 0; /* terminate new path */
200 if (!parent) { /* if no parent, we need to make one */
201 Dmsg1(100, "make_tree_path for %s\n", path);
202 path_len = strlen(path); /* get new length */
203 if (path_len == root->cached_path_len &&
204 strcmp(path, root->cached_path) == 0) {
205 parent = root->cached_parent;
207 root->cached_path_len = path_len;
208 pm_strcpy(&root->cached_path, path);
209 parent = make_tree_path(path, root);
210 root->cached_parent = parent;
212 Dmsg1(100, "parent=%s\n", parent->fname);
217 parent = (TREE_NODE *)root;
220 Dmsg1(100, "No / found: %s\n", path);
223 node = search_and_insert_tree_node(fname, 0, root, parent);
224 if (q) { /* if trailing slash on entry */
225 *q = '/'; /* restore it */
227 if (p) { /* if slash in path trashed */
228 *p = '/'; /* restore full path */
234 * Ensure that all appropriate nodes for a full path exist in
237 TREE_NODE *make_tree_path(char *path, TREE_ROOT *root)
239 TREE_NODE *parent, *node;
241 int type = TN_NEWDIR;
243 Dmsg1(100, "make_tree_path: %s\n", path);
245 Dmsg0(100, "make_tree_path: parent=*root*\n");
246 return (TREE_NODE *)root;
248 p = strrchr(path, '/'); /* get last dir component of path */
251 *p = 0; /* terminate path */
252 parent = make_tree_path(path, root);
253 *p = '/'; /* restore full name */
256 parent = (TREE_NODE *)root;
259 node = search_and_insert_tree_node(fname, type, root, parent);
263 static int node_compare(void *item1, void *item2)
265 TREE_NODE *tn1 = (TREE_NODE *)item1;
266 TREE_NODE *tn2 = (TREE_NODE *)item2;
267 if (tn1->fname[0] > tn2->fname[0]) {
269 } else if (tn1->fname[0] < tn2->fname[0]) {
272 return strcmp(tn1->fname, tn2->fname);
276 * See if the fname already exists. If not insert a new node for it.
278 static TREE_NODE *search_and_insert_tree_node(char *fname, int type,
279 TREE_ROOT *root, TREE_NODE *parent)
281 TREE_NODE *node, *found_node;
282 node = new_tree_node(root);
284 found_node = (TREE_NODE *)parent->child.binary_insert(node, node_compare);
285 if (found_node != node) { /* already in list */
286 free_tree_node(root); /* free node allocated above */
287 found_node->inserted = false;
290 /* It was not found, but is now inserted */
291 node->fname_len = strlen(fname);
292 node->fname = tree_alloc(root, node->fname_len + 1);
293 strcpy(node->fname, fname);
294 node->parent = parent;
297 /* Maintain a linear chain of nodes */
302 root->last->next = node;
305 node->inserted = true; /* inserted into tree */
310 int tree_getpath(TREE_NODE *node, char *buf, int buf_size)
316 tree_getpath(node->parent, buf, buf_size);
318 * Fixup for Win32. If we have a Win32 directory and
319 * there is only a / in the buffer, remove it since
320 * win32 names don't generally start with /
322 if (node->type == TN_DIR_NLS && buf[0] == '/' && buf[1] == 0) {
325 bstrncat(buf, node->fname, buf_size);
326 /* Add a slash for all directories unless we are at the root,
327 * also add a slash to a soft linked file if it has children
328 * i.e. it is linked to a directory.
330 if ((node->type != TN_FILE && !(buf[0] == '/' && buf[1] == 0)) ||
331 (node->soft_link && tree_node_has_child(node))) {
332 bstrncat(buf, "/", buf_size);
338 * Change to specified directory
340 TREE_NODE *tree_cwd(char *path, TREE_ROOT *root, TREE_NODE *node)
342 if (strcmp(path, ".") == 0) {
345 /* Handle relative path */
346 if (strncmp(path, "..", 2) == 0 && (path[2] == '/' || path[2] == 0)) {
347 TREE_NODE *parent = node->parent ? node->parent : node;
351 return tree_cwd(path+3, root, parent);
354 if (path[0] == '/') {
355 Dmsg0(100, "Doing absolute lookup.\n");
356 return tree_relcwd(path+1, root, (TREE_NODE *)root);
358 Dmsg0(100, "Doing relative lookup.\n");
359 return tree_relcwd(path, root, node);
364 * Do a relative cwd -- i.e. relative to current node rather than root node
366 TREE_NODE *tree_relcwd(char *path, TREE_ROOT *root, TREE_NODE *node)
375 /* Check the current segment only */
376 p = strchr(path, '/');
382 Dmsg2(100, "tree_relcwd: len=%d path=%s\n", len, path);
383 foreach_child(cd, node) {
384 Dmsg1(100, "tree_relcwd: test cd=%s\n", cd->fname);
385 if (cd->fname[0] == path[0] && len == (int)strlen(cd->fname)
386 && strncmp(cd->fname, path, len) == 0) {
390 if (!cd || (cd->type == TN_FILE && !tree_node_has_child(cd))) {
394 Dmsg0(100, "tree_relcwd: no more to lookup. found.\n");
397 Dmsg2(100, "recurse tree_relcwd with path=%s, cd=%s\n", p+1, cd->fname);
398 /* Check the next segment if any */
399 return tree_relcwd(p+1, root, cd);
404 #ifdef BUILD_TEST_PROGRAM
406 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent);
408 static uint32_t FileIndex = 0;
410 * Simple test program for tree routines
412 int main(int argc, char *argv[])
416 char buf[MAXPATHLEN];
419 root->fname = tree_alloc(root, 1);
423 FillDirectoryTree("/home/kern/bacula/k", root, NULL);
425 for (node = first_tree_node(root); node; node=next_tree_node(node)) {
426 tree_getpath(node, buf, sizeof(buf));
427 Dmsg2(100, "%d: %s\n", node->FileIndex, buf);
430 node = (TREE_NODE *)root;
431 Pmsg0(000, "doing cd /home/kern/bacula/k/techlogs\n");
432 node = tree_cwd("/home/kern/bacula/k/techlogs", root, node);
434 tree_getpath(node, buf, sizeof(buf));
435 Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
438 Pmsg0(000, "doing cd /home/kern/bacula/k/src/testprogs\n");
439 node = tree_cwd("/home/kern/bacula/k/src/testprogs", root, node);
441 tree_getpath(node, buf, sizeof(buf));
442 Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
444 Dmsg0(100, "testprogs not found.\n");
447 free_tree((TREE_NODE *)root);
452 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent)
454 TREE_NODE *newparent = NULL;
459 char pathbuf[MAXPATHLEN];
460 char file[MAXPATHLEN];
464 Dmsg1(100, "FillDirectoryTree: %s\n", path);
469 while ((dir = readdir(dp))) {
470 if (strcmp(dir->d_name, ".") == 0 || strcmp(dir->d_name, "..") == 0) {
473 bstrncpy(file, dir->d_name, sizeof(file));
474 snprintf(pathbuf, MAXPATHLEN-1, "%s/%s", path, file);
475 if (lstat(pathbuf, &statbuf) < 0) {
476 printf("lstat() failed. ERR=%s\n", strerror(errno));
479 // printf("got file=%s, pathbuf=%s\n", file, pathbuf);
481 if (S_ISLNK(statbuf.st_mode))
482 type = TN_FILE; /* link */
483 else if (S_ISREG(statbuf.st_mode))
485 else if (S_ISDIR(statbuf.st_mode)) {
487 } else if (S_ISCHR(statbuf.st_mode))
488 type = TN_FILE; /* char dev */
489 else if (S_ISBLK(statbuf.st_mode))
490 type = TN_FILE; /* block dev */
491 else if (S_ISFIFO(statbuf.st_mode))
492 type = TN_FILE; /* fifo */
493 else if (S_ISSOCK(statbuf.st_mode))
494 type = TN_FILE; /* sock */
497 printf("Unknown file type: 0x%x\n", statbuf.st_mode);
500 Dmsg2(100, "Doing: %d %s\n", type, pathbuf);
501 node = new_tree_node(root);
502 node->FileIndex = ++FileIndex;
503 parent = insert_tree_node(pathbuf, node, root, parent);
504 if (S_ISDIR(statbuf.st_mode) && !S_ISLNK(statbuf.st_mode)) {
505 Dmsg2(100, "calling fill. pathbuf=%s, file=%s\n", pathbuf, file);
506 FillDirectoryTree(pathbuf, root, node);
513 #define MAXPATHLEN 2000
516 void print_tree(char *path, TREE_NODE *tree)
518 char buf[MAXPATHLEN];
524 switch (tree->type) {
536 Pmsg3(-1, "%s/%s%s\n", path, tree->fname, termchr);
537 switch (tree->type) {
542 bsnprintf(buf, sizeof(buf), "%s/%s", path, tree->fname);
543 print_tree(buf, first_child(tree));
546 print_tree(path, first_child(tree));
549 Pmsg1(000, "Unknown node type %d\n", tree->type);
551 print_tree(path, tree->sibling_);