Avoid extra copying in pqueue operations

This tweaks the pqueue_up and pqueue_down routines so that they
will not do full element swaps but instead carry over the state
of the previous loop iteration and only assign elements for which
we know the final position.  This will avoid a little bit of data
assignment which should improve performance in theory.

Also got rid of some vector helpers that I'm no longer using.

2 files changed, 25 insertions, 20 deletions

diff --git a/src/pqueue.c b/src/pqueue.c
index cc31a8f95..172cf43d5 100644
--- a/src/pqueue.c
+++ b/src/pqueue.c
@@ -35,32 +35,47 @@ int git_pqueue_init(
 static void pqueue_up(git_pqueue *pq, size_t el)
 {
 	size_t parent_el = PQUEUE_PARENT_OF(el);
+	void *kid = git_vector_get(pq, el);
 
-	while (el > 0 && git_vector_cmp_elements(pq, parent_el, el) > 0) {
-		git_vector_swap_elements(pq, el, parent_el);
+	while (el > 0) {
+		void *parent = pq->contents[parent_el];
+
+		if (pq->_cmp(parent, kid) <= 0)
+			break;
+
+		pq->contents[el] = parent;
 
 		el = parent_el;
 		parent_el = PQUEUE_PARENT_OF(el);
 	}
+
+	pq->contents[el] = kid;
 }
 
 static void pqueue_down(git_pqueue *pq, size_t el)
 {
-	size_t last = git_pqueue_size(pq);
+	void *parent = git_vector_get(pq, el), *kid, *rkid;
 
 	while (1) {
-		size_t kid = PQUEUE_LCHILD_OF(el), rkid = PQUEUE_RCHILD_OF(el);
-		if (kid >= last)
+		size_t kid_el = PQUEUE_LCHILD_OF(el);
+
+		if ((kid = git_vector_get(pq, kid_el)) == NULL)
 			break;
-		if (rkid < last && git_vector_cmp_elements(pq, kid, rkid) > 0)
-			kid = rkid;
 
-		if (git_vector_cmp_elements(pq, el, kid) < 0)
+		if ((rkid = git_vector_get(pq, kid_el + 1)) != NULL &&
+			pq->_cmp(kid, rkid) > 0) {
+			kid    = rkid;
+			kid_el += 1;
+		}
+
+		if (pq->_cmp(parent, kid) < 0)
 			break;
 
-		git_vector_swap_elements(pq, el, kid);
-		el = kid;
+		pq->contents[el] = kid;
+		el = kid_el;
 	}
+
+	pq->contents[el] = parent;
 }
 
 int git_pqueue_insert(git_pqueue *pq, void *item)
diff --git a/src/vector.h b/src/vector.h
index f983c55d5..f8256853b 100644
--- a/src/vector.h
+++ b/src/vector.h
@@ -108,14 +108,4 @@ GIT_INLINE(void) git_vector_set_cmp(git_vector *v, git_vector_cmp cmp)
 	}
 }
 
-/** Swap two elements */
-#define git_vector_swap_elements(V, P1, P2) do { \
-	void *__t = (V)->contents[P1]; \
-	(V)->contents[P1] = (V)->contents[P2]; \
-	(V)->contents[P2] = __t; } while (0)
-
-/** Compare two elements */
-#define git_vector_cmp_elements(V, P1, P2) \
-	(V)->_cmp(git_vector_get(V,P1), git_vector_get(V,P2))
-
 #endif