From 520923e9095e807711f8c4102d3b393aa45dd1ca Mon Sep 17 00:00:00 2001
From: Kern Sibbald <kern@sibbald.com>
Date: Fri, 26 Mar 2004 22:55:03 +0000
Subject: [PATCH] Update tree building code

git-svn-id: https://bacula.svn.sourceforge.net/svnroot/bacula/trunk@1152 91ce42f0-d328-0410-95d8-f526ca767f89
---
 bacula/kernstodo          |  7 +++++
 bacula/src/dird/ua_tree.c | 19 ++++++++-----
 bacula/src/lib/tree.c     | 56 ++++++++++++++++++++++++++++-----------
 bacula/src/version.h      |  4 +--
 4 files changed, 62 insertions(+), 24 deletions(-)

diff --git a/bacula/kernstodo b/bacula/kernstodo
index c40fff101d..b4cf9a08f8 100644
--- a/bacula/kernstodo
+++ b/bacula/kernstodo
@@ -104,6 +104,13 @@ From Chris Hull:
 
 
 For version 1.35:
+- Remove paths (and files that reference them) that have no trailing slash   
+  in dbcheck -- or add a trailing slash.
+- Remove Filenames (and files that reference them) that have a trailing
+  slash in dbcheck -- or remove the trailing slash.
+- Remove orphaned paths/filenames by copying them to a new table with a 
+  reference count, then mark all referenced files/paths and remove unreferenced
+  ones.
 - Add a .list all files in the restore tree (probably also a list all files)
   Do both a long and short form.
 - Allow browsing the catalog to see all versions of a file (with 
diff --git a/bacula/src/dird/ua_tree.c b/bacula/src/dird/ua_tree.c
index 7af685a6c1..7fb06f2a35 100644
--- a/bacula/src/dird/ua_tree.c
+++ b/bacula/src/dird/ua_tree.c
@@ -402,14 +402,12 @@ static int lscmd(UAContext *ua, TREE_CTX *tree)
 /*
  * Ls command that lists only the marked files
  */
-static int lsmarkcmd(UAContext *ua, TREE_CTX *tree)
+static void rlsmark(UAContext *ua, TREE_NODE *node) 
 {
-   TREE_NODE *node;
-
-   if (!tree->node->child) {	 
-      return 1;
+   if (!node->child) {	   
+      return;
    }
-   for (node = tree->node->child; node; node=node->sibling) {
+   for (node = node->child; node; node=node->sibling) {
       if ((ua->argc == 1 || fnmatch(ua->argk[1], node->fname, 0) == 0) &&
 	  (node->extract || node->extract_dir)) {
 	 char *tag;
@@ -421,12 +419,21 @@ static int lsmarkcmd(UAContext *ua, TREE_CTX *tree)
             tag = "";
 	 }
          bsendmsg(ua, "%s%s%s\n", tag, node->fname, node->child?"/":"");
+	 if (node->child) {
+	    rlsmark(ua, node);
+	 }
       }
    }
+}
+
+static int lsmarkcmd(UAContext *ua, TREE_CTX *tree)
+{
+   rlsmark(ua, tree->node);
    return 1;
 }
 
 
+
 extern char *getuser(uid_t uid);
 extern char *getgroup(gid_t gid);
 
diff --git a/bacula/src/lib/tree.c b/bacula/src/lib/tree.c
index 3fe73b4723..381f4531f7 100755
--- a/bacula/src/lib/tree.c
+++ b/bacula/src/lib/tree.c
@@ -29,11 +29,11 @@
 #include "findlib/find.h"
 	     
 /*
- * Define PREPEND if you want the sibling list to
- *  be prepended otherwise it will be appended when
+ * Define SORT_SIBLINGS you want the sibling list to
+ *  be sorted otherwise it will be appended when
  *  a new entry is added.
  */
-// #define PREPEND
+#define SORT_SIBLINGS
 
 
 /* Forward referenced subroutines */
@@ -266,7 +266,34 @@ TREE_NODE *make_tree_path(char *path, TREE_ROOT *root)
 static TREE_NODE *search_and_insert_tree_node(char *fname, int type, 
 	       TREE_NODE *node, TREE_ROOT *root, TREE_NODE *parent)
 {
-   TREE_NODE *sibling, *last_sibling;
+   TREE_NODE *sibling, *last_sibling = NULL;
+#ifdef SORT_SIBLINGS
+   uint16_t fname_len = strlen(fname);
+   int cmp;
+
+   /* Is it already a sibling? */
+   for (sibling=parent->child; sibling; sibling=sibling->sibling) {
+      Dmsg2(000, "sibling->fname=%s fname=%s\n", sibling->fname, fname);
+      if (fname[0] > sibling->fname[0] || (cmp=strcmp(fname, sibling->fname)) > 0) {
+	 last_sibling = sibling;
+	 continue;
+      }
+      if (cmp < 0) {
+	 /* Insert before current sibling */
+	 if (!node) {
+	    node = new_tree_node(root, type);
+	 }
+	 node->sibling = sibling;
+	 if (sibling == parent->child) { /* if sibling was at head of list */
+	    parent->child = NULL;	 /* force parent to be updated below */
+	 }
+         Dmsg2(000, "insert before sibling->fname=%s fname=%s\n", sibling->fname, fname);
+	 break;
+      }
+      /* Found it */
+      return sibling;
+   }
+#else
    uint16_t fname_len = strlen(fname);
 
    /* Is it already a sibling? */
@@ -279,30 +306,27 @@ static TREE_NODE *search_and_insert_tree_node(char *fname, int type,
       }
       last_sibling = sibling;
    }
-   /* Must add */
+#endif
+
+
+   /* 
+    * At this point, the fname is not found. We must add it 
+    */
    if (!node) {
       node = new_tree_node(root, type);
    }
-   Dmsg1(100, "append_tree_node: %s\n", fname);
+   Dmsg1(000, "append_tree_node: %s\n", fname);
    node->fname_len = fname_len;
    node->fname = tree_alloc(root, node->fname_len + 1);
    strcpy(node->fname, fname);
    node->parent = parent;
    if (!parent->child) {
       parent->child = node;
-      goto item_link;		      /* No children, so skip search */
+   } else {
+      last_sibling->sibling = node;
    }
 
-#ifdef	PREPEND
-   /* Add node to head of sibling chain */
-   node->sibling = parent->child;
-   parent->child = node;
-#else
-   last_sibling = node;
-#endif
-
    /* Maintain a linear chain of nodes */
-item_link:
    if (!root->first) {
       root->first = node;
       root->last = node;
diff --git a/bacula/src/version.h b/bacula/src/version.h
index 9ad4fd2483..3015c23ed2 100644
--- a/bacula/src/version.h
+++ b/bacula/src/version.h
@@ -2,8 +2,8 @@
 #undef  VERSION
 #define VERSION "1.33.6"
 #define VSTRING "1"
-#define BDATE   "25 Mar 2004"
-#define LSMDATE "25Mar04"
+#define BDATE   "27 Mar 2004"
+#define LSMDATE "27Mar04"
 
 /* Debug flags */
 #undef  DEBUG
-- 
2.39.5