[Cvs-cvs] ccvs/src ChangeLog rcs.c

[Mark D. Baushke]

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;
 }