# Re: [PATCH 3/4] combine-diff: Optimize combine_diff_path sets intersection

```Kirill Smelkov <k...@mns.spb.ru> writes:

> diff --git a/combine-diff.c b/combine-diff.c
> index 3b92c448..98c2562 100644
> --- a/combine-diff.c
> +++ b/combine-diff.c
> @@ -15,8 +15,8 @@
> ...
> +     while (1) {
> ...
> +             if (cmp < 0) {
> +                     if (pprev)
> +                             pprev->next = p->next;
> +                     ptmp = p;
> +                     p = p->next;
> +                     free(ptmp);
> +                     if (curr == ptmp)
> +                             curr = p;
>                       continue;
> ...
> +             if (cmp > 0) {
> +                     i++;
> +                     continue;
>               }
> ...
> +
> +             pprev = p;
> +             p = p->next;
> +             i++;
>       }
>       return curr;
>  }```
```
Thanks. I very much like the approach.

I was staring at the above part of the code, but couldn't help
recalling this gem (look for "understand pointers" in the article):

How about doing it this way (on top of your patch)?  It reduces 7
lines even though it adds two comment lines ;-)

combine-diff.c | 37 +++++++++++++++----------------------
1 file changed, 15 insertions(+), 22 deletions(-)

diff --git a/combine-diff.c b/combine-diff.c
index 2d79312..0809e79 100644
--- a/combine-diff.c
+++ b/combine-diff.c
@@ -15,11 +15,10 @@
static struct combine_diff_path *intersect_paths(struct combine_diff_path
*curr, int n, int num_parent)
{
struct diff_queue_struct *q = &diff_queued_diff;
-       struct combine_diff_path *p, *pprev, *ptmp;
+       struct combine_diff_path *p, **tail = &curr;
int i, cmp;

if (!n) {
-               struct combine_diff_path *list = NULL, **tail = &list;
for (i = 0; i < q->nr; i++) {
int len;
const char *path;
@@ -43,35 +42,30 @@ static struct combine_diff_path *intersect_paths(struct
combine_diff_path *curr,
*tail = p;
tail = &p->next;
}
-               return list;
+               return curr;
}

/*
-        * NOTE paths are coming sorted here (= in tree order)
+        * paths in curr (linked list) and q->queue[] (array) are
+        * both sorted in the tree order.
*/
-
-       pprev = NULL;
-       p = curr;
i = 0;
+       while ((p = *tail) != NULL) {
+               cmp = ((i >= q->nr)
+                      ? -1 : strcmp(p->path, q->queue[i]->two->path));

-       while (1) {
-               if (!p)
-                       break;
-
-               cmp = (i >= q->nr) ? -1
-                                  : strcmp(p->path, q->queue[i]->two->path);
if (cmp < 0) {
-                       if (pprev)
-                               pprev->next = p->next;
-                       ptmp = p;
-                       p = p->next;
-                       free(ptmp);
-                       if (curr == ptmp)
-                               curr = p;
+                       /* p->path not in q->queue[]; drop it */
+                       struct combine_diff_path *next = p->next;
+
+                       if ((*tail = next) != NULL)
+                               tail = &next->next;
+                       free(p);
continue;
}

if (cmp > 0) {
+                       /* q->queue[i] not in p->path; skip it */
i++;
continue;
}
@@ -80,8 +74,7 @@ static struct combine_diff_path *intersect_paths(struct
combine_diff_path *curr,
p->parent[n].mode = q->queue[i]->one->mode;
p->parent[n].status = q->queue[i]->status;

-               pprev = p;
-               p = p->next;
+               tail = &p->next;
i++;
}
return curr;
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
```