nkiss

commit 00e23c6d2b854497697af0a86b5151ef66afd2f4
parent c37dcd6c0ddfee55ec676ddf644e863c28c1b453
Author: Nihal Jere <nihal@nihaljere.xyz>
Date:   Wed, 10 Mar 2021 20:18:45 -0600

util.*: add diff, to diff between two arrays of strings

Diffstat:
M
util.c
 | 
83
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
util.h
 | 
7
+++++++

2 files changed, 90 insertions(+), 0 deletions(-)
diff --git a/util.c b/util.c
@@ -69,6 +69,89 @@ strrepl(char *str, const char a, const char b)
     }
 }
 
+#define DIFF_LINES (MANIFEST_LINES / 3)
+/* a and b must be pointers to the first element of a null terminated array of
+ * char pointers */
+int diff(struct diff_t *diff, char **a, char **b)
+{
+    char **left = NULL, **right = NULL, **both = NULL, **temp;
+    int r;
+    size_t leftmax, rightmax, bothmax, leftc = 0, rightc = 0, bothc = 0;
+    char **ai = a, **bi = b;
+
+    /* TODO get some kind of list implementation going for these */
+    if ((left = calloc(DIFF_LINES, sizeof(char *))) == NULL)
+        goto err;
+
+    if ((right = calloc(DIFF_LINES, sizeof(char *))) == NULL)
+        goto err;
+
+    if ((both = calloc(DIFF_LINES, sizeof(char *))) == NULL)
+        goto err;
+
+    leftmax = DIFF_LINES;
+    rightmax = DIFF_LINES;
+    bothmax = DIFF_LINES;
+
+    while (*a || *b) {
+        /* strcmp is safe as we have known line lengths */
+        r = strcmp(*a, *b);
+        if (r > 0 || !(*b)) {
+            if (leftc == leftmax) {
+                if ((temp = realloc(left, leftmax*2*sizeof(char *))) == NULL)
+                    goto err;
+
+                left = temp;
+                leftmax *= 2;
+            }
+
+            left[leftc++] = *a;
+            a++;
+        } else if (r < 0 || !(*a)) {
+            if (rightc == rightmax) {
+                if ((temp = realloc(right, rightmax*2*sizeof(char *))) == NULL)
+                    goto err;
+
+                right = temp;
+                rightmax *= 2;
+            }
+
+            right[rightc++] = *b;
+            b++;
+        } else {
+            if (bothc == bothmax) {
+                if ((temp = realloc(both, bothmax*2*sizeof(char *))) == NULL)
+                    goto err;
+
+                both = temp;
+                bothmax *= 2;
+            }
+
+            both[bothc++] = *a;
+            a++;
+            b++;
+        }
+    }
+
+    /* null-terminate */
+    left[leftc] = 0;
+    right[rightc] = 0;
+    both[bothc] = 0;
+
+    diff->left = left;
+    diff->right = right;
+    diff->both = both;
+
+    return 0;
+
+err:
+    if (left) free(left);
+    if (right) free(right);
+    if (both) free(both);
+    return -1;
+}
+
+
 int
 mv(char *oldpath, char *newpath)
 {
diff --git a/util.h b/util.h
@@ -11,11 +11,18 @@
 
 extern char *argv0;
 
+struct diff_t {
+    char **left;
+    char **right;
+    char **both;
+};
+
 void warn(const char *, ...);
 void die(const char *, ...);
 int vstrcmp(const void *p1, const void *p2);
 void strrepl(char *str, const char a, const char b);
 int mkdirs(const char *path);
+int diff(struct diff_t *diff, char **a, char **b);
 int mv(char *oldpath, char *newpath);
 int file_dropadd(char *path, char *a, char *b);