Convert pqueue to just be a git_vector

This updates the git_pqueue to simply be a set of specialized
init/insert/pop functions on a git_vector.

To preserve the pqueue feature of having a fixed size heap, I
converted the "sorted" field in git_vectors to a more general
"flags" field so that pqueue could mix in it's own flag.  This
had a bunch of ramifications because a number of places were
directly looking at the vector "sorted" field - I added a couple
new git_vector helpers (is_sorted, set_sorted) so the specific
representation of this information could be abstracted.

1 files changed, 31 insertions, 26 deletions

diff --git a/src/pqueue.c b/src/pqueue.c
index ddbad7a54..cc31a8f95 100644
--- a/src/pqueue.c
+++ b/src/pqueue.c
@@ -15,25 +15,29 @@
 int git_pqueue_init(
 	git_pqueue *pq,
 	uint32_t flags,
-	size_t est_size,
+	size_t init_size,
 	git_vector_cmp cmp)
 {
-	pq->flags = flags;
-	pq->initial_size = est_size;
-	return git_vector_init(&pq->values, est_size, cmp);
-}
+	int error = git_vector_init(pq, init_size, cmp);
 
-void git_pqueue_free(git_pqueue *pq)
-{
-	git_vector_free(&pq->values);
+	if (!error) {
+		/* mix in our flags */
+		pq->flags |= flags;
+
+		/* if fixed size heap, pretend vector is exactly init_size elements */
+		if ((flags & GIT_PQUEUE_FIXED_SIZE) && init_size > 0)
+			pq->_alloc_size = init_size;
+	}
+
+	return error;
 }
 
 static void pqueue_up(git_pqueue *pq, size_t el)
 {
 	size_t parent_el = PQUEUE_PARENT_OF(el);
 
-	while (el > 0 && git_vector_cmp_elements(&pq->values, parent_el, el) > 0) {
-		git_vector_swap_elements(&pq->values, el, parent_el);
+	while (el > 0 && git_vector_cmp_elements(pq, parent_el, el) > 0) {
+		git_vector_swap_elements(pq, el, parent_el);
 
 		el = parent_el;
 		parent_el = PQUEUE_PARENT_OF(el);
@@ -42,19 +46,19 @@ static void pqueue_up(git_pqueue *pq, size_t el)
 
 static void pqueue_down(git_pqueue *pq, size_t el)
 {
-	size_t last = git_vector_length(&pq->values);
+	size_t last = git_pqueue_size(pq);
 
 	while (1) {
 		size_t kid = PQUEUE_LCHILD_OF(el), rkid = PQUEUE_RCHILD_OF(el);
 		if (kid >= last)
 			break;
-		if (rkid < last && git_vector_cmp_elements(&pq->values, kid, rkid) > 0)
+		if (rkid < last && git_vector_cmp_elements(pq, kid, rkid) > 0)
 			kid = rkid;
 
-		if (git_vector_cmp_elements(&pq->values, el, kid) < 0)
+		if (git_vector_cmp_elements(pq, el, kid) < 0)
 			break;
 
-		git_vector_swap_elements(&pq->values, el, kid);
+		git_vector_swap_elements(pq, el, kid);
 		el = kid;
 	}
 }
@@ -65,32 +69,33 @@ int git_pqueue_insert(git_pqueue *pq, void *item)
 
 	/* if heap is full, pop the top element if new one should replace it */
 	if ((pq->flags & GIT_PQUEUE_FIXED_SIZE) != 0 &&
-		pq->values.length >= pq->initial_size)
+		pq->length >= pq->_alloc_size)
 	{
-		/* skip item if below min item in heap */
-		if (pq->values._cmp(item, git_vector_get(&pq->values, 0)) <= 0)
+		/* skip this item if below min item in heap */
+		if (pq->_cmp(item, git_vector_get(pq, 0)) <= 0)
 			return 0;
+		/* otherwise remove the min item before inserting new */
 		(void)git_pqueue_pop(pq);
 	}
 
-	error = git_vector_insert(&pq->values, item);
-
-	if (!error)
-		pqueue_up(pq, pq->values.length - 1);
+	if (!(error = git_vector_insert(pq, item)))
+		pqueue_up(pq, pq->length - 1);
 
 	return error;
 }
 
 void *git_pqueue_pop(git_pqueue *pq)
 {
-	void *rval = git_vector_get(&pq->values, 0);
+	void *rval = git_pqueue_get(pq, 0);
 
-	if (git_vector_length(&pq->values) > 1) {
-		pq->values.contents[0] = git_vector_last(&pq->values);
-		git_vector_pop(&pq->values);
+	if (git_pqueue_size(pq) > 1) {
+		/* move last item to top of heap, shrink, and push item down */
+		pq->contents[0] = git_vector_last(pq);
+		git_vector_pop(pq);
 		pqueue_down(pq, 0);
 	} else {
-		git_vector_pop(&pq->values);
+		/* all we need to do is shrink the heap in this case */
+		git_vector_pop(pq);
 	}
 
 	return rval;