[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Cvs-cvs] ccvs/src ChangeLog rcs.c
From: |
Mark D. Baushke |
Subject: |
[Cvs-cvs] ccvs/src ChangeLog rcs.c |
Date: |
Wed, 06 Sep 2006 07:49:53 +0000 |
CVSROOT: /cvsroot/cvs
Module name: ccvs
Changes by: Mark D. Baushke <mdb> 06/09/06 07:49:52
Modified files:
src : ChangeLog rcs.c
Log message:
[bug #17560]
* rcs.c (apply_rcs_changes): Fix the merge algorithm from O(n^2) to
O(n).
CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/ccvs/src/ChangeLog?cvsroot=cvs&r1=1.3487&r2=1.3488
http://cvs.savannah.gnu.org/viewcvs/ccvs/src/rcs.c?cvsroot=cvs&r1=1.376&r2=1.377
Patches:
Index: ChangeLog
===================================================================
RCS file: /cvsroot/cvs/ccvs/src/ChangeLog,v
retrieving revision 1.3487
retrieving revision 1.3488
diff -u -b -r1.3487 -r1.3488
--- ChangeLog 2 Sep 2006 23:18:00 -0000 1.3487
+++ ChangeLog 6 Sep 2006 07:49:52 -0000 1.3488
@@ -1,3 +1,10 @@
+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 Smith.)
+
2006-09-02 Mark D. Baushke <address@hidden>
* cvs.h: Remove unprotected config.h include to avoid SIZE_MAX
Index: rcs.c
===================================================================
RCS file: /cvsroot/cvs/ccvs/src/rcs.c,v
retrieving revision 1.376
retrieving revision 1.377
diff -u -b -r1.376 -r1.377
--- rcs.c 5 Jul 2006 19:10:32 -0000 1.376
+++ rcs.c 6 Sep 2006 07:49:52 -0000 1.377
@@ -7443,10 +7443,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++;
@@ -7456,8 +7460,13 @@
error (1, 0, "unrecognized operation '\\x%x' in %s",
op, name);
df = xmalloc (sizeof (struct deltafrag));
- df->next = dfhead;
+ df->next = NULL;
+ if (dfhead == NULL)
dfhead = df;
+ else
+ dftail->next = df;
+ dftail = df;
+
df->pos = strtoul (p, (char **) &q, 10);
if (p == q)
@@ -7498,6 +7507,7 @@
df->len = q - p;
p = q;
+ numlines += df->nlines;
}
else
{
@@ -7507,14 +7517,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 = xnmalloc (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.
*/
@@ -7522,18 +7562,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;
}
@@ -7542,6 +7645,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 = xnrealloc (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;
}
- [Cvs-cvs] ccvs/src ChangeLog rcs.c,
Mark D. Baushke <=