[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Cvs-cvs] ccvs ChangeLog NEWS src/ChangeLog src/rcs.c [cvs1-11-x-branch]
|
From: |
Derek Robert Price |
|
Subject: |
[Cvs-cvs] ccvs ChangeLog NEWS src/ChangeLog src/rcs.c [cvs1-11-x-branch] |
|
Date: |
Wed, 06 Sep 2006 16:47:03 +0000 |
CVSROOT: /cvsroot/cvs
Module name: ccvs
Branch: cvs1-11-x-branch
Changes by: Derek Robert Price <dprice> 06/09/06 16:47:02
Modified files:
. : ChangeLog NEWS
src : ChangeLog rcs.c
Log message:
Merge RCS diff application speedup from trunk.
CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/ccvs/ChangeLog?cvsroot=cvs&only_with_tag=cvs1-11-x-branch&r1=1.692.2.250&r2=1.692.2.251
http://cvs.savannah.gnu.org/viewcvs/ccvs/NEWS?cvsroot=cvs&only_with_tag=cvs1-11-x-branch&r1=1.116.2.158&r2=1.116.2.159
http://cvs.savannah.gnu.org/viewcvs/ccvs/src/ChangeLog?cvsroot=cvs&only_with_tag=cvs1-11-x-branch&r1=1.2336.2.472&r2=1.2336.2.473
http://cvs.savannah.gnu.org/viewcvs/ccvs/src/rcs.c?cvsroot=cvs&only_with_tag=cvs1-11-x-branch&r1=1.262.4.55&r2=1.262.4.56
Patches:
Index: ChangeLog
===================================================================
RCS file: /cvsroot/cvs/ccvs/ChangeLog,v
retrieving revision 1.692.2.250
retrieving revision 1.692.2.251
diff -u -b -r1.692.2.250 -r1.692.2.251
--- ChangeLog 28 Aug 2006 19:59:49 -0000 1.692.2.250
+++ ChangeLog 6 Sep 2006 16:47:02 -0000 1.692.2.251
@@ -1,3 +1,7 @@
+2006-09-06 Derek Price <address@hidden>
+
+ * NEWS: Note apply_rcs_diff speedup.
+
2006-08-28 Derek Price <address@hidden>
* NEWS: Note strstr ("/./") assertion fix.
Index: NEWS
===================================================================
RCS file: /cvsroot/cvs/ccvs/NEWS,v
retrieving revision 1.116.2.158
retrieving revision 1.116.2.159
diff -u -b -r1.116.2.158 -r1.116.2.159
--- NEWS 28 Aug 2006 19:59:49 -0000 1.116.2.158
+++ NEWS 6 Sep 2006 16:47:02 -0000 1.116.2.159
@@ -3,6 +3,10 @@
BUG FIXES
+* Applying diffs when checking out very old revisions has been reduced from an
+ O(n^2) operation to an O(n) thanks to a patch from Michael J. Smith
+ <address@hidden> and additional touch-up work from the CVS team.
+
* Thanks to report from Paul Eggert <address@hidden>, an assertion failure
that could occur when "." was in the path (e.g. `cvs co /cvsroot/./module')
has been removed.
Index: src/ChangeLog
===================================================================
RCS file: /cvsroot/cvs/ccvs/src/ChangeLog,v
retrieving revision 1.2336.2.472
retrieving revision 1.2336.2.473
diff -u -b -r1.2336.2.472 -r1.2336.2.473
--- src/ChangeLog 28 Aug 2006 19:56:44 -0000 1.2336.2.472
+++ src/ChangeLog 6 Sep 2006 16:47:02 -0000 1.2336.2.473
@@ -1,3 +1,11 @@
+2006-09-06 Mark D. Baushke <address@hidden>
+
+ [bug #17560]
+ * rcs.c (apply_rcs_changes): Fix the merge algorithm from O(n^2)
+ to O(n).
+ (Based on a patch submitted by "Michael J. Smith"
+ <address@hidden>)
+
2006-08-28 Derek Price <address@hidden>
* recurse.c (do_recursion): Remove misguided assertion.
Index: src/rcs.c
===================================================================
RCS file: /cvsroot/cvs/ccvs/src/rcs.c,v
retrieving revision 1.262.4.55
retrieving revision 1.262.4.56
diff -u -b -r1.262.4.55 -r1.262.4.56
--- src/rcs.c 31 May 2006 15:15:56 -0000 1.262.4.55
+++ src/rcs.c 6 Sep 2006 16:47:02 -0000 1.262.4.56
@@ -7139,10 +7139,14 @@
struct deltafrag *next;
};
struct deltafrag *dfhead;
+ struct deltafrag *dftail;
struct deltafrag *df;
int err;
+ unsigned long numlines, lastmodline, offset;
+ struct linevector *orig_lines = lines;
dfhead = NULL;
+ numlines = lines->nlines; /* start with init # of lines */
for (p = diffbuf; p != NULL && p < diffbuf + difflen; )
{
op = *p++;
@@ -7151,9 +7155,14 @@
of op determines the syntax. */
error (1, 0, "unrecognized operation '\\x%x' in %s",
op, name);
- df = (struct deltafrag *) xmalloc (sizeof (struct deltafrag));
- df->next = dfhead;
+ df = xmalloc (sizeof (struct deltafrag));
+ df->next = NULL;
+ if (dfhead == NULL)
dfhead = df;
+ else
+ dftail->next = df;
+ dftail = df;
+
df->pos = strtoul (p, (char **) &q, 10);
if (p == q)
@@ -7194,6 +7203,7 @@
df->len = q - p;
p = q;
+ numlines += df->nlines;
}
else
{
@@ -7203,14 +7213,44 @@
assert (op == 'd');
df->type = FRAG_DELETE;
+ numlines -= df->nlines;
}
}
+ /* New temp data structure to hold new org before
+ copy back into original structure. */
+ lines = xmalloc (sizeof (struct linevector));
+ lines->nlines = lines->lines_alloced = numlines;
+ lines->vector = xmalloc (numlines * sizeof (*lines->vector));
+
+
+ /* We changed the list order to first to last -- so the
+ list never gets larger than the size numlines. */
+ lastmodline = 0;
+
+ /* offset created when adding/removing lines
+ between new and original structure */
+ offset = 0;
+
err = 0;
for (df = dfhead; df != NULL;)
{
unsigned int ln;
+ /* Here we need to get to the line where the next insert will
+ begin which is <df->pos> we will fill up to df->pos with
+ original items. */
+ unsigned long deltaend;
+
+ for (deltaend = df->pos - offset;
+ lastmodline < deltaend;
+ lastmodline++)
+ {
+ /* we need to copy from the orig structure into new one */
+ lines->vector[lastmodline] =
+ orig_lines->vector[lastmodline + offset];
+ }
+
/* Once an error is encountered, just free the rest of the list and
* return.
*/
@@ -7218,18 +7258,81 @@
switch (df->type)
{
case FRAG_ADD:
- if (! linevector_add (lines, df->new_lines, df->len, addvers,
- df->pos))
- err = 1;
+ {
+ const char *textend, *p;
+ const char *nextline_text;
+ struct line *q;
+ int nextline_newline;
+ size_t nextline_len;
+ int online;
+
+ textend = df->new_lines + df->len;
+ nextline_newline = 0;
+ nextline_text = df->new_lines;
+ online = 0; /* which line we are currently adding */
+ for (p = df->new_lines; p < textend; ++p)
+ {
+ if (*p == '\n')
+ {
+ nextline_newline = 1;
+ if (p + 1 == textend)
+ {
+ /* If there are no characters beyond the
+ last newline, we don't consider it
+ another line. */
+ break;
+ }
+
+ nextline_len = p - nextline_text;
+ q = xmalloc (sizeof (struct line) + nextline_len);
+ q->vers = addvers;
+ q->text = (char *)q + sizeof (struct line);
+ q->len = nextline_len;
+ q->has_newline = nextline_newline;
+ q->refcount = 1;
+ memcpy (q->text, nextline_text, nextline_len);
+ lines->vector[lastmodline++] = q;
+ offset--;
+
+ nextline_text = (char *)p + 1;
+ nextline_newline = 0;
+ }
+ }
+ nextline_len = p - nextline_text;
+ q = xmalloc (sizeof (struct line) + nextline_len);
+ q->vers = addvers;
+ q->text = (char *)q + sizeof (struct line);
+ q->len = nextline_len;
+ q->has_newline = nextline_newline;
+ q->refcount = 1;
+ memcpy (q->text, nextline_text, nextline_len);
+ lines->vector[lastmodline++] = q;
+
+ /* For each line we add the offset between the #'s
+ increases. */
+ offset--;
+
+ }
+
break;
case FRAG_DELETE:
- if (df->pos > lines->nlines
- || df->pos + df->nlines > lines->nlines)
+ /* we are removing this many lines from the source. */
+ offset += df->nlines;
+
+ if (df->pos > orig_lines->nlines
+ || df->pos + df->nlines > orig_lines->nlines)
return 0;
if (delvers != NULL)
for (ln = df->pos; ln < df->pos + df->nlines; ++ln)
- lines->vector[ln]->vers = delvers;
- linevector_delete (lines, df->pos, df->nlines);
+ {
+ if (--orig_lines->vector[ln]->refcount == 0)
+ {
+ free (orig_lines->vector[ln]);
+ orig_lines->vector[ln] = NULL;
+ }
+ else
+ orig_lines->vector[ln]->vers = delvers;
+ }
break;
}
@@ -7238,6 +7341,29 @@
dfhead = df;
}
+ /* add the rest of the remaining lines to the data vector */
+ for (; lastmodline < numlines; lastmodline++) {
+ /* we need to copy from the orig structure into new one */
+ lines->vector[lastmodline] = orig_lines->vector[lastmodline + offset];
+ }
+
+ /* we didn't make the lines structure fully -- so we can't
+ use the linevector_copy without issues -- so we do it inline
+ make the original vector larger if necessary */
+ if (numlines > orig_lines->nlines)
+ {
+ orig_lines->vector = xrealloc (orig_lines->vector,
+ numlines
+ * sizeof (*orig_lines->vector));
+ orig_lines->lines_alloced = numlines;
+ }
+ memcpy (orig_lines->vector, lines->vector,
+ xtimes (lines->nlines, sizeof (*orig_lines->vector)));
+ orig_lines->nlines = lines->nlines;
+
+ free (lines->vector);
+ free (lines); /* we don't need it any longer */
+
return !err;
}
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Cvs-cvs] ccvs ChangeLog NEWS src/ChangeLog src/rcs.c [cvs1-11-x-branch],
Derek Robert Price <=