Changeset 2132 for trunk

Timestamp:

Mar 10, 2011, 7:35:02 AM (14 years ago)

Author:

mmc

Message:

Fixed the Diffview widget to work with large diff files. There was a
problem with the way pointers were handled that manifested with large
diff strings that required reallocation of memory. Fixed to use integer
indices now instead of pointers, so the pointer values can't go stale.

File:

• trunk/gui/src/RpDiffview.c (modified) (8 diffs)

trunk/gui/src/RpDiffview.c

@@ -83 +83 @@
     int index1;                 /* index in buffer #1 */
     int index2;                 /* index in buffer #2 */
-    struct subseq *subseqPtr;   /* LCS indices for buffer #1 */
+    int next;                   /* next candidate match in the chain */
 } DiffviewSubseq;
 
@@ -2389 +2389 @@
     Tcl_HashEntry *entryPtr;
     Tcl_DString buffer;
-    DiffviewSubseq *K, *newK, *candidate, newCandidate; int Kmax; int Klen;
+    DiffviewSubseq *K, *newK, newCandidate; int Kmax; int Klen;
     Tcl_Obj *listPtr, **objv;
-    int i, j, subseqLen, longestMatch, max, min, mid, midval, sLen, del;
+    int i, j, candidateIdx, subseqLen, longestMatch;
+    int max, min, mid, midval, sLen, del;
     int len, created, o, objc, index1, *lcsIndex1, index2, *lcsIndex2;
     char *key;
@@ -2428 +2429 @@
     K[0].index1 = -1;
     K[0].index2 = -1;
-    K[0].subseqPtr = NULL;
+    K[0].next = -1;
     K[1].index1 = limsPtr1->numLines;
     K[1].index2 = limsPtr2->numLines;
-    K[1].subseqPtr = NULL;
+    K[1].next = -1;
     Klen = 2;
     longestMatch = 0;
@@ -2448 +2449 @@
         if (entryPtr) {
             subseqLen = 0;
-            candidate = &K[0];
+            candidateIdx = 0;
 
             listPtr = (Tcl_Obj*)Tcl_GetHashValue(entryPtr);
@@ -2489 +2490 @@
                  */
                 if (subseqLen >= 0) {
-                    K[subseqLen].index1    = candidate->index1;
-                    K[subseqLen].index2    = candidate->index2;
-                    K[subseqLen].subseqPtr = candidate->subseqPtr;
+                    if (candidateIdx >= 0) {
+                        K[subseqLen].index1 = K[candidateIdx].index1;
+                        K[subseqLen].index2 = K[candidateIdx].index2;
+                        K[subseqLen].next   = K[candidateIdx].next;
+                    } else {
+                        K[subseqLen].index1 = newCandidate.index1;
+                        K[subseqLen].index2 = newCandidate.index2;
+                        K[subseqLen].next   = newCandidate.next;
+                    }
                 }
                 newCandidate.index1 = i;
                 newCandidate.index2 = j;
-                newCandidate.subseqPtr = &K[sLen];
-                candidate = &newCandidate;
+                newCandidate.next = sLen;
+                candidateIdx = -1;  /* use newCandidate info */
                 subseqLen = sLen + 1;
 
@@ -2512 +2519 @@
                         K = newK;
                     }
-                    K[Klen].index1    = K[Klen-1].index1;
-                    K[Klen].index2    = K[Klen-1].index2;
-                    K[Klen].subseqPtr = K[Klen-1].subseqPtr;
+                    K[Klen].index1 = K[Klen-1].index1;
+                    K[Klen].index2 = K[Klen-1].index2;
+                    K[Klen].next   = K[Klen-1].next;
                     Klen++;
 
@@ -2523 +2530 @@
 
             /* put the last candidate into the array */
-            K[subseqLen].index1    = candidate->index1;
-            K[subseqLen].index2    = candidate->index2;
-            K[subseqLen].subseqPtr = candidate->subseqPtr;
+            if (candidateIdx >= 0) {
+                K[subseqLen].index1 = K[candidateIdx].index1;
+                K[subseqLen].index2 = K[candidateIdx].index2;
+                K[subseqLen].next   = K[candidateIdx].next;
+            } else {
+                K[subseqLen].index1 = newCandidate.index1;
+                K[subseqLen].index2 = newCandidate.index2;
+                K[subseqLen].next   = newCandidate.next;
+            }
         }
     }
@@ -2538 +2551 @@
     len = longestMatch;
 
-    candidate = &K[longestMatch];
-    while (candidate->index1 >= 0) {
-        longestMatch--;
-        lcsIndex1[longestMatch] = candidate->index1;
-        lcsIndex2[longestMatch] = candidate->index2;
-        candidate = candidate->subseqPtr;
+    candidateIdx = longestMatch;
+    while (K[candidateIdx].index1 >= 0) {
+        if (longestMatch-- < 0) {
+            Tcl_Panic("internal mismatch in diff algorithm");
+        }
+        lcsIndex1[longestMatch] = K[candidateIdx].index1;
+        lcsIndex2[longestMatch] = K[candidateIdx].index2;
+        candidateIdx = K[candidateIdx].next;
     }