X-Git-Url: https://git.sur5r.net/?a=blobdiff_plain;f=bacula%2Fsrc%2Flib%2Ftree.c;h=b223ef8a94f3d26e57c724b36dc0a00277892a08;hb=3f8a3a045ea058657030f588a10f786449d00e0d;hp=05ff49a73ed984d377977fb6c1d6f718cd2b2966;hpb=f593d1be2383ca6ff2972de8def13749f6992c4d;p=bacula%2Fbacula

diff --git a/bacula/src/lib/tree.c b/bacula/src/lib/tree.c
index 05ff49a73e..b223ef8a94 100755
--- a/bacula/src/lib/tree.c
+++ b/bacula/src/lib/tree.c
@@ -1,129 +1,300 @@
 /*
  * Directory tree build/traverse routines
- * 
+ *
  *    Kern Sibbald, June MMII
  *
 */
 /*
-   Copyright (C) 2002 Kern Sibbald and John Walker
+   Copyright (C) 2002-2006 Kern Sibbald
 
    This program is free software; you can redistribute it and/or
-   modify it under the terms of the GNU General Public License as
-   published by the Free Software Foundation; either version 2 of
-   the License, or (at your option) any later version.
+   modify it under the terms of the GNU General Public License
+   version 2 as amended with additional clauses defined in the
+   file LICENSE in the main source directory.
 
    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
-   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
-   General Public License for more details.
-
-   You should have received a copy of the GNU General Public
-   License along with this program; if not, write to the Free
-   Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
-   MA 02111-1307, USA.
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 
+   the file LICENSE for additional details.
 
  */
 
 
 #include "bacula.h"
 #include "findlib/find.h"
-#include "findlib/system.h"
-	     
-#ifndef MAXPATHLEN
-#define MAXPATHLEN 1000
-#endif
 
-TREE_NODE *new_tree_node(int type)
+
+/* Forward referenced subroutines */
+static TREE_NODE *search_and_insert_tree_node(char *fname, int type,
+               TREE_ROOT *root, TREE_NODE *parent);
+static char *tree_alloc(TREE_ROOT *root, int size);
+
+/*
+ * NOTE !!!!! we turn off Debug messages for performance reasons.
+ */
+#undef Dmsg0
+#undef Dmsg1
+#undef Dmsg2
+#undef Dmsg3
+#define Dmsg0(n,f)
+#define Dmsg1(n,f,a1)
+#define Dmsg2(n,f,a1,a2)
+#define Dmsg3(n,f,a1,a2,a3)
+
+/*
+ * This subroutine gets a big buffer.
+ */
+static void malloc_buf(TREE_ROOT *root, int size)
 {
-   TREE_NODE *node;
-   int size;
+   struct s_mem *mem;
+
+   mem = (struct s_mem *)malloc(size);
+   root->total_size += size;
+   root->blocks++;
+   mem->next = root->mem;
+   root->mem = mem;
+   mem->mem = mem->first;
+   mem->rem = (char *)mem + size - mem->mem;
+   Dmsg2(200, "malloc buf size=%d rem=%d\n", size, mem->rem);
+}
 
-   if (type == TN_ROOT) {
-      size = sizeof(TREE_ROOT);
-   } else {
-      size = sizeof(TREE_NODE);
+
+/*
+ * Note, we allocate a big buffer in the tree root
+ *  from which we allocate nodes. This runs more
+ *  than 100 times as fast as directly using malloc()
+ *  for each of the nodes.
+ */
+TREE_ROOT *new_tree(int count)
+{
+   TREE_ROOT *root;
+   uint32_t size;
+
+   if (count < 1000) {                /* minimum tree size */
+      count = 1000;
+   }
+   root = (TREE_ROOT *)malloc(sizeof(TREE_ROOT));
+   memset(root, 0, sizeof(TREE_ROOT));
+   /* Assume filename + node  = 40 characters average length */
+   size = count * (BALIGN(sizeof(TREE_NODE)) + 40);
+   if (count > 1000000 || size > 10000000) {
+      size = 10000000;
    }
-   node = (TREE_NODE *)malloc(size);
+   Dmsg2(400, "count=%d size=%d\n", count, size);
+   malloc_buf(root, size);
+   root->cached_path_len = -1;
+   root->cached_path = get_pool_memory(PM_FNAME);
+   root->type = TN_ROOT;
+   root->fname = "";
+   return root;
+}
+
+/*
+ * Create a new tree node.
+ */
+static TREE_NODE *new_tree_node(TREE_ROOT *root)
+{
+   TREE_NODE *node;
+   int size = sizeof(TREE_NODE);
+   node = (TREE_NODE *)tree_alloc(root, size);
    memset(node, 0, size);
-   node->type = type;
    return node;
 }
 
-TREE_NODE *insert_tree_node(char *path, TREE_NODE *node, TREE_ROOT *root, TREE_NODE *parent)
+/*
+ * This routine can be called to release the
+ *  previously allocated tree node.
+ */
+static void free_tree_node(TREE_ROOT *root)
+{
+   int asize = BALIGN(sizeof(TREE_NODE));
+   root->mem->rem += asize;
+   root->mem->mem -= asize;
+}
+
+
+
+/*
+ * Allocate bytes for filename in tree structure.
+ *  Keep the pointers properly aligned by allocating
+ *  sizes that are aligned.
+ */
+static char *tree_alloc(TREE_ROOT *root, int size)
+{
+   char *buf;
+   int asize = BALIGN(size);
+
+   if (root->mem->rem < asize) {
+      uint32_t mb_size;
+      if (root->total_size >= 1000000) {
+         mb_size = 1000000;
+      } else {
+         mb_size = 100000;
+      }
+      malloc_buf(root, mb_size);
+   }
+   root->mem->rem -= asize;
+   buf = root->mem->mem;
+   root->mem->mem += asize;
+   return buf;
+}
+
+
+/* This routine frees the whole tree */
+void free_tree(TREE_ROOT *root)
+{
+   struct s_mem *mem, *rel;
+
+   for (mem=root->mem; mem; ) {
+      rel = mem;
+      mem = mem->next;
+      free(rel);
+   }
+   if (root->cached_path) {
+      free_pool_memory(root->cached_path);
+      root->cached_path = NULL;
+   }
+   Dmsg2(400, "Total size=%u blocks=%d\n", root->total_size, root->blocks);
+   free(root);
+   return;
+}
+
+
+/*
+ * Insert a node in the tree. This is the main subroutine
+ *   called when building a tree.
+ *
+ */
+TREE_NODE *insert_tree_node(char *path, char *fname, int type,
+                            TREE_ROOT *root, TREE_NODE *parent)
 {
-   char *p, *fname;
+   char *p, *q;
+   int path_len = strlen(path);
+   TREE_NODE *node;
 
    Dmsg1(100, "insert_tree_node: %s\n", path);
-   p = strrchr(path, '/');
-   if (!p) {
-      Dmsg1(000, "No / found: %s\n", path);
-      exit(1);
+   /*
+    * If trailing slash on path, strip it
+    */
+   if (path_len > 0) {
+      q = path + path_len - 1;
+      if (*q == '/') {
+         *q = 0;                      /* strip trailing slash */
+      } else {
+         q = NULL;                    /* no trailing slash */
+      }
+   } else {
+      q = NULL;                       /* no trailing slash */
    }
-   *p = 0;
-   fname = p + 1;
-   if (!parent) {
-      parent = make_tree_path(path, root);
+   /* If no filename, strip last component of path as "filename" */
+   if (*fname == 0) {
+      p = strrchr(path, '/');         /* separate path and filename */
+      if (p) {
+         fname = p + 1;               /* set new filename */
+         *p = 0;                      /* terminate new path */
+      }
+   } else {
+      p = NULL;
+   }
+   if (*fname) {
+      if (!parent) {                  /* if no parent, we need to make one */
+         Dmsg1(100, "make_tree_path for %s\n", path);
+         path_len = strlen(path);     /* get new length */
+         if (path_len == root->cached_path_len &&
+             strcmp(path, root->cached_path) == 0) {
+            parent = root->cached_parent;
+         } else {
+            root->cached_path_len = path_len;
+            pm_strcpy(&root->cached_path, path);
+            parent = make_tree_path(path, root);
+            root->cached_parent = parent;
+         }
+         Dmsg1(100, "parent=%s\n", parent->fname);
+      }
+   } else {
+      fname = path;
+      if (!parent) {
+         parent = (TREE_NODE *)root;
+         type = TN_DIR_NLS;
+      }
+      Dmsg1(100, "No / found: %s\n", path);
+   }
+
+   node = search_and_insert_tree_node(fname, 0, root, parent);
+   if (q) {                           /* if trailing slash on entry */
+      *q = '/';                       /*  restore it */
    }
-   *p = '/';
-   append_tree_node(fname, node, root, parent);
-   Dmsg1(100, "insert_tree_node: parent=%s\n", parent->fname);
-   return parent;
+   if (p) {                           /* if slash in path trashed */
+      *p = '/';                       /* restore full path */
+   }
+   return node;
 }
 
+/*
+ * Ensure that all appropriate nodes for a full path exist in
+ *  the tree.
+ */
 TREE_NODE *make_tree_path(char *path, TREE_ROOT *root)
 {
-   TREE_NODE *parent, *sibling;
+   TREE_NODE *parent, *node;
    char *fname, *p;
+   int type = TN_NEWDIR;
 
    Dmsg1(100, "make_tree_path: %s\n", path);
-   if (!*path) {
+   if (*path == 0) {
       Dmsg0(100, "make_tree_path: parent=*root*\n");
       return (TREE_NODE *)root;
    }
-   p = strrchr(path, '/');
-   if (!p) {
-      Dmsg1(000, "No / found: %s\n", path);
-      exit(1);
+   p = strrchr(path, '/');           /* get last dir component of path */
+   if (p) {
+      fname = p + 1;
+      *p = 0;                         /* terminate path */
+      parent = make_tree_path(path, root);
+      *p = '/';                       /* restore full name */
+   } else {
+      fname = path;
+      parent = (TREE_NODE *)root;
+      type = TN_DIR_NLS;
    }
-   *p = 0;
-   fname = p + 1;
-   /* Find parent */
-   parent = make_tree_path(path, root);
-   *p = '/';
-   /* Is it already a sibling? */
-   for (sibling=parent->sibling; sibling; sibling=sibling->sibling) {
-      if (strcmp(sibling->fname, fname) == 0) {
-         Dmsg1(100, "make_tree_path: found parent=%s\n", parent->fname);
-	 return parent;
-      }
+   node = search_and_insert_tree_node(fname, type, root, parent);
+   return node;
+}
+
+static int node_compare(void *item1, void *item2)
+{
+   TREE_NODE *tn1 = (TREE_NODE *)item1;
+   TREE_NODE *tn2 = (TREE_NODE *)item2;
+   if (tn1->fname[0] > tn2->fname[0]) {
+      return 1;
+   } else if (tn1->fname[0] < tn2->fname[0]) {
+      return -1;
    }
-   /* Must add */
-   sibling = new_tree_node(TN_NEWDIR);
-   append_tree_node(fname, sibling, root, parent);
-   parent = sibling;
-   Dmsg1(100, "make_tree_path: add parent=%s\n", parent->fname);
-   return parent;
-}  
+   return strcmp(tn1->fname, tn2->fname);
+}
 
 /*
- *  Append sibling to parent's child chain
+ *  See if the fname already exists. If not insert a new node for it.
  */
-void append_tree_node(char *fname, TREE_NODE *node, TREE_ROOT *root, TREE_NODE *parent)
+static TREE_NODE *search_and_insert_tree_node(char *fname, int type,
+               TREE_ROOT *root, TREE_NODE *parent)
 {
-   TREE_NODE *child;
-
-   Dmsg1(100, "append_tree_node: %s\n", fname);
-   node->fname = bstrdup(fname);
-   node->parent = parent;
-   if (!parent->child) {
-      parent->child = node;
-      goto item_link;
+   TREE_NODE *node, *found_node;
+   node = new_tree_node(root);
+   node->fname = fname;
+   found_node = (TREE_NODE *)parent->child.binary_insert(node, node_compare);
+   if (found_node != node) {          /* already in list */
+      free_tree_node(root);           /* free node allocated above */
+      found_node->inserted = false;
+      return found_node;
    }
-   for (child=parent->child; child->sibling; child=child->sibling)
-      { }
-   child->sibling = node;
+   /* It was not found, but is now inserted */
+   node->fname_len = strlen(fname);
+   node->fname = tree_alloc(root, node->fname_len + 1);
+   strcpy(node->fname, fname);
+   node->parent = parent;
+   node->type = type;
 
-item_link:
+   /* Maintain a linear chain of nodes */
    if (!root->first) {
       root->first = node;
       root->last = node;
@@ -131,82 +302,9 @@ item_link:
       root->last->next = node;
       root->last = node;
    }
-   return;
-}
-
-TREE_NODE *first_tree_node(TREE_ROOT *root)
-{
-   return root->first;
-}
-
-TREE_NODE *next_tree_node(TREE_NODE *node)
-{
-   return node->next;
-}
-
-
-void print_tree(char *path, TREE_NODE *tree)
-{
-   char buf[MAXPATHLEN];
-   char *termchr;
+   node->inserted = true;             /* inserted into tree */
+   return node;
 
-   if (!tree) {
-      return;
-   }
-   switch (tree->type) {
-   case TN_DIR:
-   case TN_NEWDIR:  
-      termchr = "/";
-      break;
-   case TN_ROOT:
-   case TN_FILE:
-   default:
-      termchr = "";
-      break;
-   }
-   Dmsg3(-1, "%s/%s%s\n", path, tree->fname, termchr);
-   switch (tree->type) {
-   case TN_FILE:
-      break;
-   case TN_DIR:
-      sprintf(buf, "%s/%s", path, tree->fname);
-      print_tree(buf, tree->child);
-      break;
-   case TN_ROOT:
-      print_tree(path, tree->child);
-      break;
-   case TN_NEWDIR:  
-      sprintf(buf, "%s/%s", path, tree->fname);
-      print_tree(buf, tree->child);
-      break;
-   default:
-      Dmsg1(000, "Unknown node type %d\n", tree->type);
-   }
-   print_tree(path, tree->sibling);
-   return;
-}
-
-void free_tree(TREE_NODE *node)
-{
-   if (!node) {
-      return;
-   }
-   switch (node->type) {
-   case TN_FILE:
-      break;
-   case TN_DIR:
-   case TN_ROOT:
-   case TN_NEWDIR:  
-      free_tree(node->child);
-      break;
-   default:
-      Dmsg1(000, "Unknown node type %d\n", node->type);
-      break;
-   }
-   free_tree(node->sibling);
-   free(node->fname);
-   free(node);
-   return;
 }
 
 int tree_getpath(TREE_NODE *node, char *buf, int buf_size)
@@ -216,14 +314,27 @@ int tree_getpath(TREE_NODE *node, char *buf, int buf_size)
       return 1;
    }
    tree_getpath(node->parent, buf, buf_size);
-   strcat(buf, node->fname);
-   if (node->type != TN_FILE) {
-      strcat(buf, "/");
+   /*
+    * Fixup for Win32. If we have a Win32 directory and
+    *    there is only a / in the buffer, remove it since
+    *    win32 names don't generally start with /
+    */
+   if (node->type == TN_DIR_NLS && buf[0] == '/' && buf[1] == 0) {
+      buf[0] = 0;
+   }
+   bstrncat(buf, node->fname, buf_size);
+   /* Add a slash for all directories unless we are at the root,
+    *  also add a slash to a soft linked file if it has children
+    *  i.e. it is linked to a directory.
+    */
+   if ((node->type != TN_FILE && !(buf[0] == '/' && buf[1] == 0)) ||
+       (node->soft_link && tree_node_has_child(node))) {
+      bstrncat(buf, "/", buf_size);
    }
    return 1;
 }
 
-/* 
+/*
  * Change to specified directory
  */
 TREE_NODE *tree_cwd(char *path, TREE_ROOT *root, TREE_NODE *node)
@@ -233,9 +344,9 @@ TREE_NODE *tree_cwd(char *path, TREE_ROOT *root, TREE_NODE *node)
    }
    if (strcmp(path, "..") == 0) {
       if (node->parent) {
-	 return node->parent;
+         return node->parent;
       } else {
-	 return node;
+         return node;
       }
    }
    if (path[0] == '/') {
@@ -247,6 +358,9 @@ TREE_NODE *tree_cwd(char *path, TREE_ROOT *root, TREE_NODE *node)
 }
 
 
+/*
+ * Do a relative cwd -- i.e. relative to current node rather than root node
+ */
 TREE_NODE *tree_relcwd(char *path, TREE_ROOT *root, TREE_NODE *node)
 {
    char *p;
@@ -256,18 +370,22 @@ TREE_NODE *tree_relcwd(char *path, TREE_ROOT *root, TREE_NODE *node)
    if (*path == 0) {
       return node;
    }
+   /* Check the current segment only */
    p = strchr(path, '/');
    if (p) {
       len = p - path;
+   } else {
+      len = strlen(path);
    }
-   for (cd=node->child; cd; cd=cd->sibling) {
-      if (strncmp(cd->fname, path, len) == 0) {
-         Dmsg1(100, "tree_relcwd: found cd=%s\n", cd->fname);
-	 break;
+   Dmsg2(100, "tree_relcwd: len=%d path=%s\n", len, path);
+   foreach_child(cd, node) {
+      Dmsg1(100, "tree_relcwd: test cd=%s\n", cd->fname);
+      if (cd->fname[0] == path[0] && len == (int)strlen(cd->fname)
+          && strncmp(cd->fname, path, len) == 0) {
+         break;
       }
    }
-   if (!cd || cd->type == TN_FILE) {
-      Dmsg1(100, "tree_relcwd: failed %s is a file.\n", cd->fname);
+   if (!cd || (cd->type == TN_FILE && !tree_node_has_child(cd))) {
       return NULL;
    }
    if (!p) {
@@ -275,6 +393,7 @@ TREE_NODE *tree_relcwd(char *path, TREE_ROOT *root, TREE_NODE *node)
       return cd;
    }
    Dmsg2(100, "recurse tree_relcwd with path=%s, cd=%s\n", p+1, cd->fname);
+   /* Check the next segment if any */
    return tree_relcwd(p+1, root, cd);
 }
 
@@ -294,8 +413,10 @@ int main(int argc, char *argv[])
     TREE_NODE *node;
     char buf[MAXPATHLEN];
 
-    root = (TREE_ROOT *)new_tree_node(TN_ROOT);
-    root->fname = bstrdup("");
+    root = new_tree();
+    root->fname = tree_alloc(root, 1);
+    *root->fname = 0;
+    root->fname_len = 0;
 
     FillDirectoryTree("/home/kern/bacula/k", root, NULL);
 
@@ -305,14 +426,14 @@ int main(int argc, char *argv[])
     }
 
     node = (TREE_NODE *)root;
-    Dmsg0(000, "doing cd /home/kern/bacula/k/techlogs\n");
+    Pmsg0(000, "doing cd /home/kern/bacula/k/techlogs\n");
     node = tree_cwd("/home/kern/bacula/k/techlogs", root, node);
     if (node) {
        tree_getpath(node, buf, sizeof(buf));
        Dmsg2(100, "findex=%d: cwd=%s\n", node->FileIndex, buf);
     }
 
-    Dmsg0(000, "doing cd /home/kern/bacula/k/src/testprogs\n");
+    Pmsg0(000, "doing cd /home/kern/bacula/k/src/testprogs\n");
     node = tree_cwd("/home/kern/bacula/k/src/testprogs", root, node);
     if (node) {
        tree_getpath(node, buf, sizeof(buf));
@@ -337,7 +458,7 @@ void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent)
    char file[MAXPATHLEN];
    int type;
    int i;
-   
+
    Dmsg1(100, "FillDirectoryTree: %s\n", path);
    dp = opendir(path);
    if (!dp) {
@@ -345,44 +466,88 @@ void FillDirectoryTree(char *path, TREE_ROOT *root, TREE_NODE *parent)
    }
    while ((dir = readdir(dp))) {
       if (strcmp(dir->d_name, ".") == 0 || strcmp(dir->d_name, "..") == 0) {
-	 continue;
+         continue;
       }
-      strcpy(file, dir->d_name);
+      bstrncpy(file, dir->d_name, sizeof(file));
       snprintf(pathbuf, MAXPATHLEN-1, "%s/%s", path, file);
       if (lstat(pathbuf, &statbuf) < 0) {
          printf("lstat() failed. ERR=%s\n", strerror(errno));
-	 continue;
+         continue;
       }
 //      printf("got file=%s, pathbuf=%s\n", file, pathbuf);
       type = TN_FILE;
       if (S_ISLNK(statbuf.st_mode))
-	 type =  TN_FILE;  /* link */
+         type =  TN_FILE;  /* link */
       else if (S_ISREG(statbuf.st_mode))
-	 type = TN_FILE;
+         type = TN_FILE;
       else if (S_ISDIR(statbuf.st_mode)) {
-	 type = TN_DIR;
+         type = TN_DIR;
       } else if (S_ISCHR(statbuf.st_mode))
-	 type = TN_FILE; /* char dev */
+         type = TN_FILE; /* char dev */
       else if (S_ISBLK(statbuf.st_mode))
-	 type = TN_FILE; /* block dev */
+         type = TN_FILE; /* block dev */
       else if (S_ISFIFO(statbuf.st_mode))
-	 type = TN_FILE; /* fifo */
+         type = TN_FILE; /* fifo */
       else if (S_ISSOCK(statbuf.st_mode))
-	 type = TN_FILE; /* sock */
+         type = TN_FILE; /* sock */
       else {
-	 type = TN_FILE;
+         type = TN_FILE;
          printf("Unknown file type: 0x%x\n", statbuf.st_mode);
       }
 
       Dmsg2(100, "Doing: %d %s\n", type, pathbuf);
-      node = new_tree_node(type);
+      node = new_tree_node(root);
       node->FileIndex = ++FileIndex;
       parent = insert_tree_node(pathbuf, node, root, parent);
       if (S_ISDIR(statbuf.st_mode) && !S_ISLNK(statbuf.st_mode)) {
          Dmsg2(100, "calling fill. pathbuf=%s, file=%s\n", pathbuf, file);
-	 FillDirectoryTree(pathbuf, root, node);
+         FillDirectoryTree(pathbuf, root, node);
       }
    }
    closedir(dp);
 }
+
+#ifndef MAXPATHLEN
+#define MAXPATHLEN 2000
+#endif
+
+void print_tree(char *path, TREE_NODE *tree)
+{
+   char buf[MAXPATHLEN];
+   char *termchr;
+
+   if (!tree) {
+      return;
+   }
+   switch (tree->type) {
+   case TN_DIR_NLS:
+   case TN_DIR:
+   case TN_NEWDIR:
+      termchr = "/";
+      break;
+   case TN_ROOT:
+   case TN_FILE:
+   default:
+      termchr = "";
+      break;
+   }
+   Pmsg3(-1, "%s/%s%s\n", path, tree->fname, termchr);
+   switch (tree->type) {
+   case TN_FILE:
+   case TN_NEWDIR:
+   case TN_DIR:
+   case TN_DIR_NLS:
+      bsnprintf(buf, sizeof(buf), "%s/%s", path, tree->fname);
+      print_tree(buf, first_child(tree));
+      break;
+   case TN_ROOT:
+      print_tree(path, first_child(tree));
+      break;
+   default:
+      Pmsg1(000, "Unknown node type %d\n", tree->type);
+   }
+   print_tree(path, tree->sibling_);
+   return;
+}
+
 #endif