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 * Define PREPEND if you want the sibling list to
33 * be prepended otherwise it will be appended when
34 * a new entry is added.
39 /* Forward referenced subroutines */
40 static TREE_NODE *search_and_insert_tree_node(char *fname, int type,
41 TREE_NODE *node, TREE_ROOT *root, TREE_NODE *parent);
44 * NOTE !!!!! we turn off Debug messages for performance reasons.
52 #define Dmsg2(n,f,a1,a2)
53 #define Dmsg3(n,f,a1,a2,a3)
56 * This subroutine gets a big buffer.
58 static void malloc_buf(TREE_ROOT *root, int size)
62 mem = (struct s_mem *)malloc(size);
63 root->total_size += size;
65 mem->next = root->mem;
67 mem->mem = mem->first;
68 mem->rem = (char *)mem + size - mem->mem;
69 Dmsg2(200, "malloc buf size=%d rem=%d\n", size, mem->rem);
74 * Note, we allocate a big buffer in the tree root
75 * from which we allocate nodes. This runs more
76 * than 100 times as fast as directly using malloc()
77 * for each of the nodes.
79 TREE_ROOT *new_tree(int count)
84 if (count < 1000) { /* minimum tree size */
87 root = (TREE_ROOT *)malloc(sizeof(TREE_ROOT));
88 memset(root, 0, sizeof(TREE_ROOT));
90 /* Assume filename + node = 40 characters average length */
91 size = count * (BALIGN(sizeof(TREE_NODE)) + 40);
92 if (count > 1000000 || size > 10000000) {
95 Dmsg2(400, "count=%d size=%d\n", count, size);
96 malloc_buf(root, size);
97 root->cached_path = get_pool_memory(PM_FNAME);
102 * Create a new tree node. Size depends on type.
104 TREE_NODE *new_tree_node(TREE_ROOT *root, int type)
107 int asize = BALIGN(sizeof(TREE_NODE));
109 if (root->mem->rem < asize) {
111 if (root->total_size >= 1000000) {
116 malloc_buf(root, mb_size);
118 root->mem->rem -= asize;
119 node = (TREE_NODE *)root->mem->mem;
120 root->mem->mem += asize;
121 memset(node, 0, sizeof(TREE_NODE));
128 * Allocate bytes for filename in tree structure.
129 * Keep the pointers properly aligned by allocating
130 * sizes that are aligned.
132 static char *tree_alloc(TREE_ROOT *root, int size)
135 int asize = BALIGN(size);
137 if (root->mem->rem < asize) {
139 if (root->total_size >= 1000000) {
144 malloc_buf(root, mb_size);
146 root->mem->rem -= asize;
147 buf = root->mem->mem;
148 root->mem->mem += asize;
153 /* This routine frees the whole tree */
154 void free_tree(TREE_ROOT *root)
156 struct s_mem *mem, *rel;
158 for (mem=root->mem; mem; ) {
163 if (root->cached_path) {
164 free_pool_memory(root->cached_path);
166 Dmsg2(400, "Total size=%u blocks=%d\n", root->total_size, root->blocks);
174 * Insert a node in the tree. This is the main subroutine
175 * called when building a tree.
178 TREE_NODE *insert_tree_node(char *path, TREE_NODE *node,
179 TREE_ROOT *root, TREE_NODE *parent)
182 int path_len = strlen(path);
184 Dmsg1(100, "insert_tree_node: %s\n", path);
186 * If trailing slash, strip it
189 q = path + path_len - 1;
191 *q = 0; /* strip trailing slash */
193 q = NULL; /* no trailing slash */
196 q = NULL; /* no trailing slash */
198 p = strrchr(path, '/'); /* separate path and filename */
201 if (!parent) { /* if no parent, we need to make one */
202 *p = 0; /* terminate path */
203 Dmsg1(100, "make_tree_path for %s\n", path);
204 path_len = strlen(path); /* get new length */
205 if (path_len == root->cached_path_len &&
206 strcmp(path, root->cached_path) == 0) {
207 parent = root->cached_parent;
209 root->cached_path_len = path_len;
210 pm_strcpy(&root->cached_path, path);
211 parent = make_tree_path(path, root);
212 root->cached_parent = parent;
214 Dmsg1(100, "parent=%s\n", parent->fname);
215 *p = '/'; /* restore full path */
220 parent = (TREE_NODE *)root;
221 node->type = TN_DIR_NLS;
223 Dmsg1(100, "No / found: %s\n", path);
226 node = search_and_insert_tree_node(fname, 0, node, root, parent);
227 if (q) { /* if trailing slash on entry */
228 *q = '/'; /* restore it */
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, NULL, root, parent);
264 * See if the fname already exists. If not insert a new node for it.
266 static TREE_NODE *search_and_insert_tree_node(char *fname, int type,
267 TREE_NODE *node, TREE_ROOT *root, TREE_NODE *parent)
269 TREE_NODE *sibling, *last_sibling;
270 uint16_t fname_len = strlen(fname);
272 /* Is it already a sibling? */
273 for (sibling=parent->child; sibling; sibling=sibling->sibling) {
274 Dmsg2(100, "sibling->fname=%s fname=%s\n", sibling->fname, fname);
275 if (sibling->fname_len == fname_len &&
276 strcmp(sibling->fname, fname) == 0) {
277 Dmsg1(100, "make_tree_path: found parent=%s\n", parent->fname);
280 last_sibling = sibling;
284 node = new_tree_node(root, type);
286 Dmsg1(100, "append_tree_node: %s\n", fname);
287 node->fname_len = fname_len;
288 node->fname = tree_alloc(root, node->fname_len + 1);
289 strcpy(node->fname, fname);
290 node->parent = parent;
291 if (!parent->child) {
292 parent->child = node;
293 goto item_link; /* No children, so skip search */
297 /* Add node to head of sibling chain */
298 node->sibling = parent->child;
299 parent->child = node;
304 /* Maintain a linear chain of nodes */
310 root->last->next = node;
317 /* Moved to tree.h to eliminate subroutine call */
318 TREE_NODE *first_tree_node(TREE_ROOT *root)
323 TREE_NODE *next_tree_node(TREE_NODE *node)
331 int tree_getpath(TREE_NODE *node, char *buf, int buf_size)
337 tree_getpath(node->parent, buf, buf_size);
339 * Fixup for Win32. If we have a Win32 directory and
340 * there is only a / in the buffer, remove it since
341 * win32 names don't generally start with /
343 if (node->type == TN_DIR_NLS && buf[0] == '/' && buf[1] == 0) {
346 bstrncat(buf, node->fname, buf_size);
347 /* Add a slash for all directories unless we are at the root,
348 * also add a slash to a soft linked file if it has children
349 * i.e. it is linked to a directory.
351 if ((node->type != TN_FILE && !(buf[0] == '/' && buf[1] == 0)) ||
352 (node->soft_link && node->child)) {
353 bstrncat(buf, "/", buf_size);
359 * Change to specified directory
361 TREE_NODE *tree_cwd(char *path, TREE_ROOT *root, TREE_NODE *node)
363 if (strcmp(path, ".") == 0) {
366 if (strcmp(path, "..") == 0) {
373 if (path[0] == '/') {
374 Dmsg0(100, "Doing absolute lookup.\n");
375 return tree_relcwd(path+1, root, (TREE_NODE *)root);
377 Dmsg0(100, "Doing relative lookup.\n");
378 return tree_relcwd(path, root, node);
383 * Do a relative cwd -- i.e. relative to current node rather than root node
385 TREE_NODE *tree_relcwd(char *path, TREE_ROOT *root, TREE_NODE *node)
394 /* Check the current segment only */
395 p = strchr(path, '/');
401 Dmsg2(100, "tree_relcwd: len=%d path=%s\n", len, path);
402 for (cd=node->child; cd; cd=cd->sibling) {
403 Dmsg1(100, "tree_relcwd: test cd=%s\n", cd->fname);
404 if (cd->fname[0] == path[0] && len == (int)strlen(cd->fname)
405 && strncmp(cd->fname, path, len) == 0) {
409 if (!cd || (cd->type == TN_FILE && !cd->child)) {
413 Dmsg0(100, "tree_relcwd: no more to lookup. found.\n");
416 Dmsg2(100, "recurse tree_relcwd with path=%s, cd=%s\n", p+1, cd->fname);
417 /* Check the next segment if any */
418 return tree_relcwd(p+1, root, cd);
423 #ifdef BUILD_TEST_PROGRAM
425 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent);
427 static uint32_t FileIndex = 0;
429 * Simple test program for tree routines
431 int main(int argc, char *argv[])
435 char buf[MAXPATHLEN];
438 root->fname = tree_alloc(root, 1);
442 FillDirectoryTree("/home/kern/bacula/k", root, NULL);
444 for (node = first_tree_node(root); node; node=next_tree_node(node)) {
445 tree_getpath(node, buf, sizeof(buf));
446 Dmsg2(100, "%d: %s\n", node->FileIndex, buf);
449 node = (TREE_NODE *)root;
450 Pmsg0(000, "doing cd /home/kern/bacula/k/techlogs\n");
451 node = tree_cwd("/home/kern/bacula/k/techlogs", root, node);
453 tree_getpath(node, buf, sizeof(buf));
454 Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
457 Pmsg0(000, "doing cd /home/kern/bacula/k/src/testprogs\n");
458 node = tree_cwd("/home/kern/bacula/k/src/testprogs", root, node);
460 tree_getpath(node, buf, sizeof(buf));
461 Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
463 Dmsg0(100, "testprogs not found.\n");
466 free_tree((TREE_NODE *)root);
471 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent)
473 TREE_NODE *newparent = NULL;
478 char pathbuf[MAXPATHLEN];
479 char file[MAXPATHLEN];
483 Dmsg1(100, "FillDirectoryTree: %s\n", path);
488 while ((dir = readdir(dp))) {
489 if (strcmp(dir->d_name, ".") == 0 || strcmp(dir->d_name, "..") == 0) {
492 bstrncpy(file, dir->d_name, sizeof(file));
493 snprintf(pathbuf, MAXPATHLEN-1, "%s/%s", path, file);
494 if (lstat(pathbuf, &statbuf) < 0) {
495 printf("lstat() failed. ERR=%s\n", strerror(errno));
498 // printf("got file=%s, pathbuf=%s\n", file, pathbuf);
500 if (S_ISLNK(statbuf.st_mode))
501 type = TN_FILE; /* link */
502 else if (S_ISREG(statbuf.st_mode))
504 else if (S_ISDIR(statbuf.st_mode)) {
506 } else if (S_ISCHR(statbuf.st_mode))
507 type = TN_FILE; /* char dev */
508 else if (S_ISBLK(statbuf.st_mode))
509 type = TN_FILE; /* block dev */
510 else if (S_ISFIFO(statbuf.st_mode))
511 type = TN_FILE; /* fifo */
512 else if (S_ISSOCK(statbuf.st_mode))
513 type = TN_FILE; /* sock */
516 printf("Unknown file type: 0x%x\n", statbuf.st_mode);
519 Dmsg2(100, "Doing: %d %s\n", type, pathbuf);
520 node = new_tree_node(root, type);
521 node->FileIndex = ++FileIndex;
522 parent = insert_tree_node(pathbuf, node, root, parent);
523 if (S_ISDIR(statbuf.st_mode) && !S_ISLNK(statbuf.st_mode)) {
524 Dmsg2(100, "calling fill. pathbuf=%s, file=%s\n", pathbuf, file);
525 FillDirectoryTree(pathbuf, root, node);
532 #define MAXPATHLEN 2000
535 void print_tree(char *path, TREE_NODE *tree)
537 char buf[MAXPATHLEN];
543 switch (tree->type) {
555 Dmsg3(-1, "%s/%s%s\n", path, tree->fname, termchr);
556 switch (tree->type) {
561 bsnprintf(buf, sizeof(buf), "%s/%s", path, tree->fname);
562 print_tree(buf, tree->child);
565 print_tree(path, tree->child);
568 Pmsg1(000, "Unknown node type %d\n", tree->type);
570 print_tree(path, tree->sibling);