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 if (strcmp(path, "..") == 0) {
352 if (path[0] == '/') {
353 Dmsg0(100, "Doing absolute lookup.\n");
354 return tree_relcwd(path+1, root, (TREE_NODE *)root);
356 Dmsg0(100, "Doing relative lookup.\n");
357 return tree_relcwd(path, root, node);
362 * Do a relative cwd -- i.e. relative to current node rather than root node
364 TREE_NODE *tree_relcwd(char *path, TREE_ROOT *root, TREE_NODE *node)
373 /* Check the current segment only */
374 p = strchr(path, '/');
380 Dmsg2(100, "tree_relcwd: len=%d path=%s\n", len, path);
381 foreach_child(cd, node) {
382 Dmsg1(100, "tree_relcwd: test cd=%s\n", cd->fname);
383 if (cd->fname[0] == path[0] && len == (int)strlen(cd->fname)
384 && strncmp(cd->fname, path, len) == 0) {
388 if (!cd || (cd->type == TN_FILE && !tree_node_has_child(cd))) {
392 Dmsg0(100, "tree_relcwd: no more to lookup. found.\n");
395 Dmsg2(100, "recurse tree_relcwd with path=%s, cd=%s\n", p+1, cd->fname);
396 /* Check the next segment if any */
397 return tree_relcwd(p+1, root, cd);
402 #ifdef BUILD_TEST_PROGRAM
404 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent);
406 static uint32_t FileIndex = 0;
408 * Simple test program for tree routines
410 int main(int argc, char *argv[])
414 char buf[MAXPATHLEN];
417 root->fname = tree_alloc(root, 1);
421 FillDirectoryTree("/home/kern/bacula/k", root, NULL);
423 for (node = first_tree_node(root); node; node=next_tree_node(node)) {
424 tree_getpath(node, buf, sizeof(buf));
425 Dmsg2(100, "%d: %s\n", node->FileIndex, buf);
428 node = (TREE_NODE *)root;
429 Pmsg0(000, "doing cd /home/kern/bacula/k/techlogs\n");
430 node = tree_cwd("/home/kern/bacula/k/techlogs", root, node);
432 tree_getpath(node, buf, sizeof(buf));
433 Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
436 Pmsg0(000, "doing cd /home/kern/bacula/k/src/testprogs\n");
437 node = tree_cwd("/home/kern/bacula/k/src/testprogs", root, node);
439 tree_getpath(node, buf, sizeof(buf));
440 Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
442 Dmsg0(100, "testprogs not found.\n");
445 free_tree((TREE_NODE *)root);
450 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent)
452 TREE_NODE *newparent = NULL;
457 char pathbuf[MAXPATHLEN];
458 char file[MAXPATHLEN];
462 Dmsg1(100, "FillDirectoryTree: %s\n", path);
467 while ((dir = readdir(dp))) {
468 if (strcmp(dir->d_name, ".") == 0 || strcmp(dir->d_name, "..") == 0) {
471 bstrncpy(file, dir->d_name, sizeof(file));
472 snprintf(pathbuf, MAXPATHLEN-1, "%s/%s", path, file);
473 if (lstat(pathbuf, &statbuf) < 0) {
474 printf("lstat() failed. ERR=%s\n", strerror(errno));
477 // printf("got file=%s, pathbuf=%s\n", file, pathbuf);
479 if (S_ISLNK(statbuf.st_mode))
480 type = TN_FILE; /* link */
481 else if (S_ISREG(statbuf.st_mode))
483 else if (S_ISDIR(statbuf.st_mode)) {
485 } else if (S_ISCHR(statbuf.st_mode))
486 type = TN_FILE; /* char dev */
487 else if (S_ISBLK(statbuf.st_mode))
488 type = TN_FILE; /* block dev */
489 else if (S_ISFIFO(statbuf.st_mode))
490 type = TN_FILE; /* fifo */
491 else if (S_ISSOCK(statbuf.st_mode))
492 type = TN_FILE; /* sock */
495 printf("Unknown file type: 0x%x\n", statbuf.st_mode);
498 Dmsg2(100, "Doing: %d %s\n", type, pathbuf);
499 node = new_tree_node(root);
500 node->FileIndex = ++FileIndex;
501 parent = insert_tree_node(pathbuf, node, root, parent);
502 if (S_ISDIR(statbuf.st_mode) && !S_ISLNK(statbuf.st_mode)) {
503 Dmsg2(100, "calling fill. pathbuf=%s, file=%s\n", pathbuf, file);
504 FillDirectoryTree(pathbuf, root, node);
511 #define MAXPATHLEN 2000
514 void print_tree(char *path, TREE_NODE *tree)
516 char buf[MAXPATHLEN];
522 switch (tree->type) {
534 Pmsg3(-1, "%s/%s%s\n", path, tree->fname, termchr);
535 switch (tree->type) {
540 bsnprintf(buf, sizeof(buf), "%s/%s", path, tree->fname);
541 print_tree(buf, first_child(tree));
544 print_tree(path, first_child(tree));
547 Pmsg1(000, "Unknown node type %d\n", tree->type);
549 print_tree(path, tree->sibling_);