summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJeff King <peff@peff.net>2017-04-24 07:49:20 -0400
committerJunio C Hamano <gitster@pobox.com>2017-04-24 21:16:44 -0700
commit1f9e18b77282070e8fef6dbe6983a8c94a3b0efa (patch)
treedf955d981f1c7f6b0ef240273fa3e8e1cdf26f2a
parentf0e802ca200b1296495d2ee5c55cd8f8083486bc (diff)
downloadgit-1f9e18b77282070e8fef6dbe6983a8c94a3b0efa.tar.gz
prio_queue_reverse: don't swap elements with themselvesjk/prio-queue-avoid-swap-with-self
Our array-reverse algorithm does the usual "walk from both ends, swapping elements". We can quit when the two indices are equal, since: 1. Swapping an element with itself is a noop. 2. If i and j are equal, then in the next iteration i is guaranteed to be bigge than j, and we will exit the loop. So exiting the loop on equality is slightly more efficient. And more importantly, the new SWAP() macro does not expect to handle noop swaps; it will call memcpy() with the same src and dst pointers in this case. It's unclear whether that causes a problem on any platforms by violating the "overlapping memory" constraint of memcpy, but it does cause valgrind to complain. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
-rw-r--r--prio-queue.c2
1 files changed, 1 insertions, 1 deletions
diff --git a/prio-queue.c b/prio-queue.c
index e4365b00d6..76782b66d4 100644
--- a/prio-queue.c
+++ b/prio-queue.c
@@ -23,7 +23,7 @@ void prio_queue_reverse(struct prio_queue *queue)
if (queue->compare != NULL)
die("BUG: prio_queue_reverse() on non-LIFO queue");
- for (i = 0; i <= (j = (queue->nr - 1) - i); i++)
+ for (i = 0; i < (j = (queue->nr - 1) - i); i++)
swap(queue, i, j);
}