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@xxxxxxxx>
---
I actually tried implementing a stable queue on top of the existing
prio-queue. However, it was quite a mess. Because prio_queue only stores
one void pointer to a thing, the stable queue has to allocate its own its
(counter,thing) pair. Doing it in a separate array doesn't work (you do
not pop them in insertion order, so you end up with "holes"). So you end
up storing an extra pointer, _plus_ per-entry malloc overhead.
If we really want to offer a non-stable queue (and I do not think we
do), we should probably just do two totally separate queues, or
implement the whole thing with a run-time "element size" member (or even
do it in macros).
I use struct assignment in the swap() function below. Do we want to
replace that with a memcpy? Presumably decent compilers can turn that
into the same code anyway, but I find the assignment more readable, and
IIRC it has been around since C89.
prio-queue.c | 15 ++++++++++-----
prio-queue.h | 8 +++++++-
2 files changed, 17 insertions(+), 6 deletions(-)
diff --git a/prio-queue.c b/prio-queue.c
index 0f4fcf2..e4365b0 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 9c3cd1f..d030ec9 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;
};
/*
--
2.0.0.566.gfe3e6b2
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html