2 * Directory tree build/traverse routines
4 * Kern Sibbald, June MMII
8 Copyright (C) 2002 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"
30 #include "findlib/system.h"
33 #define MAXPATHLEN 1000
37 * This subrouting gets a big buffer.
39 static void malloc_buf(TREE_ROOT *root, int size)
43 mem = (struct s_mem *)malloc(size);
44 mem->next = root->mem;
46 mem->mem = mem->first;
47 mem->rem = (char *)mem + size - mem->mem;
48 Dmsg2(400, "malloc buf size=%d rem=%d\n", size, mem->rem);
53 * Note, we allocate a big buffer in the tree root
54 * from which we allocate nodes. This runs more
55 * than 100 times as fast as directly using malloc()
56 * for each of the nodes.
58 TREE_ROOT *new_tree(int count)
63 if (count < 1000) { /* minimum tree size */
66 root = (TREE_ROOT *)malloc(sizeof(TREE_ROOT));
67 memset(root, 0, sizeof(TREE_ROOT));
69 /* Assume filename = 20 characters average length */
70 size = count * (BALIGN(sizeof(TREE_NODE)) + 20);
71 if (size > 10000000) {
74 Dmsg2(400, "count=%d size=%d\n", count, size);
75 malloc_buf(root, size);
80 * Create a new tree node. Size depends on type.
82 TREE_NODE *new_tree_node(TREE_ROOT *root, int type)
85 int size = BALIGN(sizeof(TREE_NODE));
87 if (root->mem->rem < size) {
88 malloc_buf(root, 20000);
91 root->mem->rem -= size;
92 node = (TREE_NODE *)root->mem->mem;
93 root->mem->mem += size;
94 memset(node, 0, sizeof(TREE_NODE));
101 * Allocate bytes for filename in tree structure.
102 * Keep the pointers properly aligned by allocating
103 * sizes that are aligned.
105 static char *tree_alloc(TREE_ROOT *root, int size)
108 int asize = BALIGN(size);
110 if (root->mem->rem < asize) {
111 malloc_buf(root, 20000+asize);
113 root->mem->rem -= asize;
114 buf = root->mem->mem;
115 root->mem->mem += asize;
120 /* This routine frees the whole tree */
121 void free_tree(TREE_ROOT *root)
123 struct s_mem *mem, *rel;
125 for (mem=root->mem; mem; ) {
137 * Insert a node in the tree
140 TREE_NODE *insert_tree_node(char *path, TREE_NODE *node, TREE_ROOT *root, TREE_NODE *parent)
144 int len = strlen(path);
146 Dmsg1(100, "insert_tree_node: %s\n", path);
148 * If trailing slash, strip it
153 *q = 0; /* strip trailing slash */
155 q = NULL; /* no trailing slash */
158 q = NULL; /* no trailing slash */
160 p = strrchr(path, '/'); /* separate path and filename */
164 *p = 0; /* terminate path */
165 Dmsg1(100, "make_tree_path for %s\n", path);
166 parent = make_tree_path(path, root);
167 Dmsg1(100, "parent=%s\n", parent->fname);
168 *p = '/'; /* restore full name */
173 parent = (TREE_NODE *)root;
175 Dmsg1(100, "No / found: %s\n", path);
178 for (sibling=parent->child; sibling; sibling=sibling->sibling) {
179 Dmsg2(100, "sibling->fname=%s fname=%s\n", sibling->fname, fname);
180 if (strcmp(sibling->fname, fname) == 0) {
181 Dmsg1(100, "make_tree_path: found parent=%s\n", parent->fname);
182 if (q) { /* if trailing slash on entry */
183 *q = '/'; /* restore it */
190 append_tree_node(fname, node, root, parent);
191 Dmsg1(100, "insert_tree_node: parent=%s\n", parent->fname);
192 if (q) { /* if trailing slash on entry */
193 *q = '/'; /* restore it */
199 * Ensure that all appropriate nodes for a full path exist in
202 TREE_NODE *make_tree_path(char *path, TREE_ROOT *root)
204 TREE_NODE *parent, *sibling, *node;
207 Dmsg1(100, "make_tree_path: %s\n", path);
209 Dmsg0(100, "make_tree_path: parent=*root*\n");
210 return (TREE_NODE *)root;
212 p = strrchr(path, '/'); /* separate path and filename */
215 *p = 0; /* terminate path */
216 parent = make_tree_path(path, root);
217 *p = '/'; /* restore full name */
220 parent = (TREE_NODE *)root;
222 /* Is it already a sibling? */
223 for (sibling=parent->child; sibling; sibling=sibling->sibling) {
224 Dmsg2(100, "sibling->fname=%s fname=%s\n", sibling->fname, fname);
225 if (strcmp(sibling->fname, fname) == 0) {
226 Dmsg1(100, "make_tree_path: found parent=%s\n", parent->fname);
231 node = new_tree_node(root, TN_NEWDIR);
232 append_tree_node(fname, node, root, parent);
233 Dmsg1(100, "make_tree_path: add parent=%s\n", node->fname);
238 * Append sibling to parent's child chain
240 void append_tree_node(char *fname, TREE_NODE *node, TREE_ROOT *root, TREE_NODE *parent)
244 Dmsg1(100, "append_tree_node: %s\n", fname);
245 node->fname = tree_alloc(root, strlen(fname) + 1);
246 strcpy(node->fname, fname);
247 node->parent = parent;
248 if (!parent->child) {
249 parent->child = node;
252 /* Append to end of sibling chain */
253 for (child=parent->child; child->sibling; child=child->sibling)
255 child->sibling = node;
257 /* Maintain a linear chain of nodes */
263 root->last->next = node;
269 TREE_NODE *first_tree_node(TREE_ROOT *root)
274 TREE_NODE *next_tree_node(TREE_NODE *node)
280 void print_tree(char *path, TREE_NODE *tree)
282 char buf[MAXPATHLEN];
288 switch (tree->type) {
299 Dmsg3(-1, "%s/%s%s\n", path, tree->fname, termchr);
300 switch (tree->type) {
304 sprintf(buf, "%s/%s", path, tree->fname);
305 print_tree(buf, tree->child);
308 print_tree(path, tree->child);
311 sprintf(buf, "%s/%s", path, tree->fname);
312 print_tree(buf, tree->child);
315 Dmsg1(000, "Unknown node type %d\n", tree->type);
317 print_tree(path, tree->sibling);
321 int tree_getpath(TREE_NODE *node, char *buf, int buf_size)
327 tree_getpath(node->parent, buf, buf_size);
328 strcat(buf, node->fname);
329 if (node->type != TN_FILE) {
336 * Change to specified directory
338 TREE_NODE *tree_cwd(char *path, TREE_ROOT *root, TREE_NODE *node)
340 if (strcmp(path, ".") == 0) {
343 if (strcmp(path, "..") == 0) {
350 if (path[0] == '/') {
351 Dmsg0(100, "Doing absolute lookup.\n");
352 return tree_relcwd(path+1, root, (TREE_NODE *)root);
354 Dmsg0(100, "Doing relative lookup.\n");
355 return tree_relcwd(path, root, node);
359 TREE_NODE *tree_relcwd(char *path, TREE_ROOT *root, TREE_NODE *node)
368 p = strchr(path, '/');
372 for (cd=node->child; cd; cd=cd->sibling) {
373 if (strncmp(cd->fname, path, len) == 0) {
374 Dmsg1(100, "tree_relcwd: found cd=%s\n", cd->fname);
378 if (!cd || cd->type == TN_FILE) {
382 Dmsg0(100, "tree_relcwd: no more to lookup. found.\n");
385 Dmsg2(100, "recurse tree_relcwd with path=%s, cd=%s\n", p+1, cd->fname);
386 return tree_relcwd(p+1, root, cd);
391 #ifdef BUILD_TEST_PROGRAM
393 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent);
395 static uint32_t FileIndex = 0;
397 * Simple test program for tree routines
399 int main(int argc, char *argv[])
403 char buf[MAXPATHLEN];
406 root->fname = tree_alloc(root, 1);
409 FillDirectoryTree("/home/kern/bacula/k", root, NULL);
411 for (node = first_tree_node(root); node; node=next_tree_node(node)) {
412 tree_getpath(node, buf, sizeof(buf));
413 Dmsg2(100, "%d: %s\n", node->FileIndex, buf);
416 node = (TREE_NODE *)root;
417 Dmsg0(000, "doing cd /home/kern/bacula/k/techlogs\n");
418 node = tree_cwd("/home/kern/bacula/k/techlogs", root, node);
420 tree_getpath(node, buf, sizeof(buf));
421 Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
424 Dmsg0(000, "doing cd /home/kern/bacula/k/src/testprogs\n");
425 node = tree_cwd("/home/kern/bacula/k/src/testprogs", root, node);
427 tree_getpath(node, buf, sizeof(buf));
428 Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
430 Dmsg0(100, "testprogs not found.\n");
433 free_tree((TREE_NODE *)root);
438 void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent)
440 TREE_NODE *newparent = NULL;
445 char pathbuf[MAXPATHLEN];
446 char file[MAXPATHLEN];
450 Dmsg1(100, "FillDirectoryTree: %s\n", path);
455 while ((dir = readdir(dp))) {
456 if (strcmp(dir->d_name, ".") == 0 || strcmp(dir->d_name, "..") == 0) {
459 strcpy(file, dir->d_name);
460 snprintf(pathbuf, MAXPATHLEN-1, "%s/%s", path, file);
461 if (lstat(pathbuf, &statbuf) < 0) {
462 printf("lstat() failed. ERR=%s\n", strerror(errno));
465 // printf("got file=%s, pathbuf=%s\n", file, pathbuf);
467 if (S_ISLNK(statbuf.st_mode))
468 type = TN_FILE; /* link */
469 else if (S_ISREG(statbuf.st_mode))
471 else if (S_ISDIR(statbuf.st_mode)) {
473 } else if (S_ISCHR(statbuf.st_mode))
474 type = TN_FILE; /* char dev */
475 else if (S_ISBLK(statbuf.st_mode))
476 type = TN_FILE; /* block dev */
477 else if (S_ISFIFO(statbuf.st_mode))
478 type = TN_FILE; /* fifo */
479 else if (S_ISSOCK(statbuf.st_mode))
480 type = TN_FILE; /* sock */
483 printf("Unknown file type: 0x%x\n", statbuf.st_mode);
486 Dmsg2(100, "Doing: %d %s\n", type, pathbuf);
487 node = new_tree_node(root, type);
488 node->FileIndex = ++FileIndex;
489 parent = insert_tree_node(pathbuf, node, root, parent);
490 if (S_ISDIR(statbuf.st_mode) && !S_ISLNK(statbuf.st_mode)) {
491 Dmsg2(100, "calling fill. pathbuf=%s, file=%s\n", pathbuf, file);
492 FillDirectoryTree(pathbuf, root, node);