From: Lukas Sandström Date: Tue, 15 Nov 2005 21:24:02 GMT Subject: [PATCH] Fix llist_sorted_difference_inplace in git-pack-redundant Message-ID: <437A51F2.4000106@etek.chalmers.se> In-Reply-To: <81b0412b0511150749g5672158v7b39c02ffdf13e08@mail.gmail.com> Simplify and actually make llist_sorted_difference_inplace work by using llist_sorted_remove instead of duplicating parts of the code. Signed-off-by: Lukas Sandström --- Looking at the code; I must have been tired when I wrote llist_sorted_difference_inplace. This should hopefully fix things up nicely. Note that I think the old version got the case "remove last element from list" wrong too. I think the Signed-off line is in utf8 this time. Tell me if it works better, of if I just should change my name ;) pack-redundant.c | 47 +++++++++++++++-------------------------------- 1 files changed, 15 insertions(+), 32 deletions(-) applies-to: 4b6dbe856a3e63699b299c76f4f1fc5cb34cbe26 560aa97889ef028fed0678389d4bb05ebf3ead62 diff --git a/pack-redundant.c b/pack-redundant.c index 28b82ee..fcb36ff 100644 --- a/pack-redundant.c +++ b/pack-redundant.c @@ -127,38 +127,6 @@ inline struct llist_item * llist_insert_ return llist_insert_back(list, sha1); } -/* computes A\B */ -void llist_sorted_difference_inplace(struct llist *A, - struct llist *B) -{ - struct llist_item *prev, *a, *b, *x; - - prev = a = A->front; - b = B->front; - - while (a != NULL && b != NULL) { - int cmp = memcmp(a->sha1, b->sha1, 20); - if (!cmp) { - x = a; - if (a == A->front) - A->front = a->next; - a = prev->next = a->next; - - if (a == NULL) /* end of list */ - A->back = prev; - A->size--; - free(x); - b = b->next; - } else - if (cmp > 0) - b = b->next; - else { - prev = a; - a = a->next; - } - } -} - /* returns a pointer to an item in front of sha1 */ inline struct llist_item * llist_sorted_remove(struct llist *list, char *sha1, struct llist_item *hint) @@ -194,6 +162,21 @@ redo_from_start: return prev; } +/* computes A\B */ +void llist_sorted_difference_inplace(struct llist *A, + struct llist *B) +{ + struct llist_item *hint, *b; + + hint = NULL; + b = B->front; + + while (b) { + hint = llist_sorted_remove(A, b->sha1, hint); + b = b->next; + } +} + inline struct pack_list * pack_list_insert(struct pack_list **pl, struct pack_list *entry) { --- 0.99.9.GIT