summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJeff King <peff@peff.net>2014-07-14 01:51:59 -0400
committerJunio C Hamano <gitster@pobox.com>2014-07-15 11:02:54 -0700
commite8f91e3df82a33b7e0b59c935cc4af892068baa2 (patch)
tree04b0e1db2529fb471f5e51822d348b526d757664
parent6d63baa47883315033474fc06196330e3a5ca4e0 (diff)
downloadgit-e8f91e3df82a33b7e0b59c935cc4af892068baa2.tar.gz
prio-queue: make output stable with respect to insertion
If two items are added to a prio_queue and compare equal, they currently come out in an apparently random order (this order is deterministic for a particular sequence of insertions and removals, but does not necessarily match the insertion order). This makes it unlike using a date-ordered commit_list, which is one of the main types we would like to replace with it (because prio_queue does not suffer from O(n) insertions). We can make the priority queue stable by keeping an insertion counter for each element, and using it to break ties. This does increase the memory usage of the structure (one int per element), but in practice it does not seem to affect runtime. A best-of-five "git rev-list --topo-order" on linux.git showed less than 1% difference (well within the run-to-run noise). In an ideal world, we would offer both stable and unstable priority queues (the latter to try to maximize performance). However, given the lack of a measurable performance difference, it is not worth the extra code. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
-rw-r--r--prio-queue.c15
-rw-r--r--prio-queue.h8
2 files changed, 17 insertions, 6 deletions
diff --git a/prio-queue.c b/prio-queue.c
index 0f4fcf2755..e4365b00d6 100644
--- a/prio-queue.c
+++ b/prio-queue.c
@@ -3,14 +3,16 @@
static inline int compare(struct prio_queue *queue, int i, int j)
{
- int cmp = queue->compare(queue->array[i], queue->array[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)
{
- void *tmp = queue->array[i];
+ struct prio_queue_entry tmp = queue->array[i];
queue->array[i] = queue->array[j];
queue->array[j] = tmp;
}
@@ -31,6 +33,7 @@ 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)
@@ -39,7 +42,9 @@ void prio_queue_put(struct prio_queue *queue, void *thing)
/* Append at the end */
ALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);
- queue->array[queue->nr++] = thing;
+ queue->array[queue->nr].ctr = queue->insertion_ctr++;
+ queue->array[queue->nr].data = thing;
+ queue->nr++;
if (!queue->compare)
return; /* LIFO */
@@ -61,9 +66,9 @@ void *prio_queue_get(struct prio_queue *queue)
if (!queue->nr)
return NULL;
if (!queue->compare)
- return queue->array[--queue->nr]; /* LIFO */
+ return queue->array[--queue->nr].data; /* LIFO */
- result = queue->array[0];
+ result = queue->array[0].data;
if (!--queue->nr)
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;
};
/*