From 3b3a2fbcf058b90d9116f48ba26ad9528d450134 Mon Sep 17 00:00:00 2001
From: Andrew Tridgell <tridge@samba.org>
Date: Tue, 6 Jan 1998 16:53:52 +0000
Subject: [PATCH] *** empty log message ***

---
 flist.c | 10 --------
 rsync.c | 72 +++++++++++++++++++++++++++++++++++++++++++++++++--------
 rsync.h | 10 ++++++++
 3 files changed, 73 insertions(+), 19 deletions(-)

diff --git a/flist.c b/flist.c
index 894cf16c..40158fae 100644
--- a/flist.c
+++ b/flist.c
@@ -581,16 +581,6 @@ int file_compare(struct file_struct *f1,struct file_struct *f2)
 }
 
 
-/* we need this function because of the silly way in which duplicate
-   entries are handled in the file lists - we can't change this
-   without breaking existing versions */
-static int flist_up(struct file_list *flist, int i)
-{
-	while (!flist->files[i].name) i++;
-	return i;
-}
-
-
 int flist_find(struct file_list *flist,struct file_struct *f)
 {
 	int low=0,high=flist->count-1;
diff --git a/rsync.c b/rsync.c
index 78022fbb..673f1414 100644
--- a/rsync.c
+++ b/rsync.c
@@ -551,6 +551,61 @@ static void delete_one(struct file_struct *f)
 }
 
 
+/* yuck! This function wouldn't have been necessary if I had the sorting
+   algorithm right. Unfortunately fixing the sorting algorithm would introduce
+   a backward incompatibility as file list indexes are sent over the link.
+
+   The aim is to see if a directory has already had the deletion algorithm applied
+   to it (due to recursion), and if so to skip it. The bisection is to 
+   prevent this being an n^2 algorithm */
+static int delete_already_done(struct file_list *flist,int j)
+{
+	int low=0,high=j-1;
+	char *name;
+	char *p;
+
+	if (j == 0) return 0;
+
+	name = strdup(flist->files[j].name);
+
+	if (!name) {
+		fprintf(FERROR,"out of memory in delete_already_done");
+		exit_cleanup(1);
+	}
+
+	p = strrchr(name,'/');
+	if (!p) {
+		free(name);
+		return 0;
+	}
+	*p = 0;
+
+	while (low != high) {
+		int mid = (low+high)/2;
+		int ret = strcmp(flist->files[flist_up(flist, mid)].name,name);
+		if (ret == 0) {
+			free(name);
+			return 1;
+		}
+		if (ret > 0) {
+			high=mid;
+		} else {
+			low=mid+1;
+		}
+	}
+
+	low = flist_up(flist, low);
+
+	if (strcmp(flist->files[low].name,name) == 0) {
+		free(name);
+		return 1;
+	}
+
+	free(name);
+	return 0;
+}
+
+
 /* this deletes any files on the receiving side that are not present
    on the sending side. For version 1.6.4 I have changed the behaviour
    to match more closely what most people seem to expect of this option */
@@ -558,23 +613,22 @@ static void delete_files(struct file_list *flist)
 {
   struct file_list *local_file_list;
   int i, j;
-  char *last_name=NULL;
 
   if (cvs_exclude)
     add_cvs_excludes();
 
   for (j=0;j<flist->count;j++) {
+	  char *name = flist->files[j].name;
+
 	  if (!S_ISDIR(flist->files[j].mode)) continue;
-	  if (strcmp(flist->files[j].name,".")==0) continue;
-	  if (last_name &&
-	      flist->files[j].name[strlen(last_name)] == '/' &&
-	      strncmp(flist->files[j].name,last_name, strlen(last_name))==0)
-		  continue;
-	  last_name = flist->files[j].name;
-	  if (!(local_file_list = send_file_list(-1,1,&last_name)))
+
+	  if (delete_already_done(flist, j)) continue;
+
+	  if (!(local_file_list = send_file_list(-1,1,&name)))
 		  continue;
+
 	  if (verbose > 1)
-		  fprintf(FINFO,"deleting in %s\n", last_name);
+		  fprintf(FINFO,"deleting in %s\n", name);
 
 	  for (i=local_file_list->count-1;i>=0;i--) {
 		  if (!local_file_list->files[i].name) continue;
diff --git a/rsync.h b/rsync.h
index b9bca21c..0b881039 100644
--- a/rsync.h
+++ b/rsync.h
@@ -248,6 +248,16 @@ struct map_struct {
   int fd,size,p_size,p_offset,p_len;
 };
 
+/* we need this function because of the silly way in which duplicate
+   entries are handled in the file lists - we can't change this
+   without breaking existing versions */
+static int flist_up(struct file_list *flist, int i)
+{
+	while (!flist->files[i].name) i++;
+	return i;
+}
+
+
 #include "byteorder.h"
 #include "version.h"
 #include "proto.h"
-- 
2.34.1