diff options
| -rw-r--r-- | commit.c | 42 | ||||
| -rw-r--r-- | prio-queue.c | 60 | ||||
| -rw-r--r-- | prio-queue.h | 8 | ||||
| -rwxr-xr-x | t/t5539-fetch-http-shallow.sh | 1 |
4 files changed, 60 insertions, 51 deletions
@@ -764,45 +764,41 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT); -static struct commit *interesting(struct commit_list *list) +static int queue_has_nonstale(struct prio_queue *queue) { - while (list) { - struct commit *commit = list->item; - list = list->next; - if (commit->object.flags & STALE) - continue; - return commit; + int i; + for (i = 0; i < queue->nr; i++) { + struct commit *commit = queue->array[i].data; + if (!(commit->object.flags & STALE)) + return 1; } - return NULL; + return 0; } /* all input commits in one and twos[] must have been parsed! */ static struct commit_list *paint_down_to_common(struct commit *one, int n, struct commit **twos) { - struct commit_list *list = NULL; + struct prio_queue queue = { compare_commits_by_commit_date }; struct commit_list *result = NULL; int i; one->object.flags |= PARENT1; - commit_list_insert_by_date(one, &list); - if (!n) - return list; + if (!n) { + commit_list_append(one, &result); + return result; + } + prio_queue_put(&queue, one); + for (i = 0; i < n; i++) { twos[i]->object.flags |= PARENT2; - commit_list_insert_by_date(twos[i], &list); + prio_queue_put(&queue, twos[i]); } - while (interesting(list)) { - struct commit *commit; + while (queue_has_nonstale(&queue)) { + struct commit *commit = prio_queue_get(&queue); struct commit_list *parents; - struct commit_list *next; int flags; - commit = list->item; - next = list->next; - free(list); - list = next; - flags = commit->object.flags & (PARENT1 | PARENT2 | STALE); if (flags == (PARENT1 | PARENT2)) { if (!(commit->object.flags & RESULT)) { @@ -821,11 +817,11 @@ static struct commit_list *paint_down_to_common(struct commit *one, int n, struc if (parse_commit(p)) return NULL; p->object.flags |= flags; - commit_list_insert_by_date(p, &list); + prio_queue_put(&queue, p); } } - free_commit_list(list); + clear_prio_queue(&queue); return result; } diff --git a/prio-queue.c b/prio-queue.c index c9f8c6d253..e4365b00d6 100644 --- a/prio-queue.c +++ b/prio-queue.c @@ -1,18 +1,30 @@ #include "cache.h" -#include "commit.h" #include "prio-queue.h" +static inline int compare(struct prio_queue *queue, int i, int j) +{ + int cmp = queue->compare(queue->array[i].data, queue->array[j].data, + queue->cb_data); + if (!cmp) + cmp = queue->array[i].ctr - queue->array[j].ctr; + return cmp; +} + +static inline void swap(struct prio_queue *queue, int i, int j) +{ + struct prio_queue_entry tmp = queue->array[i]; + queue->array[i] = queue->array[j]; + queue->array[j] = tmp; +} + void prio_queue_reverse(struct prio_queue *queue) { int i, j; if (queue->compare != NULL) die("BUG: prio_queue_reverse() on non-LIFO queue"); - for (i = 0; i <= (j = (queue->nr - 1) - i); i++) { - struct commit *swap = queue->array[i]; - queue->array[i] = queue->array[j]; - queue->array[j] = swap; - } + for (i = 0; i <= (j = (queue->nr - 1) - i); i++) + swap(queue, i, j); } void clear_prio_queue(struct prio_queue *queue) @@ -21,44 +33,42 @@ void clear_prio_queue(struct prio_queue *queue) queue->nr = 0; queue->alloc = 0; queue->array = NULL; + queue->insertion_ctr = 0; } void prio_queue_put(struct prio_queue *queue, void *thing) { - prio_queue_compare_fn compare = queue->compare; int ix, parent; /* Append at the end */ ALLOC_GROW(queue->array, queue->nr + 1, queue->alloc); - queue->array[queue->nr++] = thing; - if (!compare) + queue->array[queue->nr].ctr = queue->insertion_ctr++; + queue->array[queue->nr].data = thing; + queue->nr++; + if (!queue->compare) return; /* LIFO */ /* Bubble up the new one */ for (ix = queue->nr - 1; ix; ix = parent) { parent = (ix - 1) / 2; - if (compare(queue->array[parent], queue->array[ix], - queue->cb_data) <= 0) + if (compare(queue, parent, ix) <= 0) break; - thing = queue->array[parent]; - queue->array[parent] = queue->array[ix]; - queue->array[ix] = thing; + swap(queue, parent, ix); } } void *prio_queue_get(struct prio_queue *queue) { - void *result, *swap; + void *result; int ix, child; - prio_queue_compare_fn compare = queue->compare; if (!queue->nr) return NULL; - if (!compare) - return queue->array[--queue->nr]; /* LIFO */ + if (!queue->compare) + return queue->array[--queue->nr].data; /* LIFO */ - result = queue->array[0]; + result = queue->array[0].data; if (!--queue->nr) return result; @@ -67,18 +77,14 @@ void *prio_queue_get(struct prio_queue *queue) /* Push down the one at the root */ for (ix = 0; ix * 2 + 1 < queue->nr; ix = child) { child = ix * 2 + 1; /* left */ - if ((child + 1 < queue->nr) && - (compare(queue->array[child], queue->array[child + 1], - queue->cb_data) >= 0)) + if (child + 1 < queue->nr && + compare(queue, child, child + 1) >= 0) child++; /* use right child */ - if (compare(queue->array[ix], queue->array[child], - queue->cb_data) <= 0) + if (compare(queue, ix, child) <= 0) break; - swap = queue->array[child]; - queue->array[child] = queue->array[ix]; - queue->array[ix] = swap; + swap(queue, child, ix); } return result; } diff --git a/prio-queue.h b/prio-queue.h index 9c3cd1f875..d030ec9dd6 100644 --- a/prio-queue.h +++ b/prio-queue.h @@ -21,11 +21,17 @@ */ typedef int (*prio_queue_compare_fn)(const void *one, const void *two, void *cb_data); +struct prio_queue_entry { + unsigned ctr; + void *data; +}; + struct prio_queue { prio_queue_compare_fn compare; + unsigned insertion_ctr; void *cb_data; int alloc, nr; - void **array; + struct prio_queue_entry *array; }; /* diff --git a/t/t5539-fetch-http-shallow.sh b/t/t5539-fetch-http-shallow.sh index 94553e1039..b46118846c 100755 --- a/t/t5539-fetch-http-shallow.sh +++ b/t/t5539-fetch-http-shallow.sh @@ -54,6 +54,7 @@ EOF test_expect_success 'no shallow lines after receiving ACK ready' ' ( cd shallow && + test_tick && for i in $(test_seq 15) do git checkout --orphan unrelated$i && |