Replace pqueue with code from hashsig heap

I accidentally wrote a separate priority queue implementation when
I was working on file rename detection as part of the file hash
signature calculation code.  To simplify licensing terms, I just
adapted that to a general purpose priority queue and replace the
old priority queue implementation that was borrowed from elsewhere.

This also removes parts of the COPYING document that no longer
apply to libgit2.

1 files changed, 43 insertions, 68 deletions

diff --git a/src/pqueue.h b/src/pqueue.h
index 9061f8279..3c977e178 100644
--- a/src/pqueue.h
+++ b/src/pqueue.h
@@ -3,99 +3,74 @@
  *
  * This file is part of libgit2, distributed under the GNU GPL v2 with
  * a Linking Exception. For full terms see the included COPYING file.
- * 
- * This file is based on a modified version of the priority queue found
- * in the Apache project and libpqueue library.
- * 
- * https://github.com/vy/libpqueue
- * 
- * Original file notice:
- * 
- * Copyright 2010 Volkan Yazici <volkan.yazici@gmail.com>
- * Copyright 2006-2010 The Apache Software Foundation
- *
- * Licensed under the Apache License, Version 2.0 (the "License"); you may not
- * use this file except in compliance with the License. You may obtain a copy of
- * the License at
- *
- *     http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
- * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
- * License for the specific language governing permissions and limitations under
- * the License.
  */
-
 #ifndef INCLUDE_pqueue_h__
 #define INCLUDE_pqueue_h__
 
-/** callback functions to get/set/compare the priority of an element */
-typedef int (*git_pqueue_cmp)(void *a, void *b);
+#include "vector.h"
 
-/** the priority queue handle */
 typedef struct {
-	size_t size, avail, step;
-	git_pqueue_cmp cmppri;
-	void **d;
+	git_vector values;
+	size_t     initial_size;
+	uint32_t   flags;
 } git_pqueue;
 
+enum {
+	GIT_PQUEUE_DEFAULT = 0,
+	GIT_PQUEUE_FIXED_SIZE = (1 << 0), /* don't grow heap, keep highest */
+};
 
 /**
- * initialize the queue
+ * Initialize priority queue
  *
- * @param n the initial estimate of the number of queue items for which memory
- *			should be preallocated
- * @param cmppri the callback function to compare two nodes of the queue
- *
- * @return the handle or NULL for insufficent memory
+ * @param pq The priority queue struct to initialize
+ * @param flags Flags (see above) to control queue behavior
+ * @param est_size The estimated/initial queue size
+ * @param cmp The entry priority comparison function
+ * @return 0 on success, <0 on error
  */
-int git_pqueue_init(git_pqueue *q, size_t n, git_pqueue_cmp cmppri);
-
+extern int git_pqueue_init(
+	git_pqueue *pq,
+	uint32_t flags,
+	size_t est_size,
+	git_vector_cmp cmp);
 
 /**
- * free all memory used by the queue
- * @param q the queue
+ * Free the queue memory
  */
-void git_pqueue_free(git_pqueue *q);
+extern void git_pqueue_free(git_pqueue *pq);
 
 /**
- * clear all the elements in the queue
- * @param q the queue
+ * Get the number of items in the queue
  */
-void git_pqueue_clear(git_pqueue *q);
+GIT_INLINE(size_t) git_pqueue_size(const git_pqueue *pq)
+{
+	return git_vector_length(&pq->values);
+}
 
 /**
- * return the size of the queue.
- * @param q the queue
+ * Get an item in the queue
  */
-size_t git_pqueue_size(git_pqueue *q);
-
+GIT_INLINE(void *) git_pqueue_get(const git_pqueue *pq, size_t pos)
+{
+	return git_vector_get(&pq->values, pos);
+}
 
 /**
- * insert an item into the queue.
- * @param q the queue
- * @param d the item
- * @return 0 on success
- */
-int git_pqueue_insert(git_pqueue *q, void *d);
-
-
-/**
- * pop the highest-ranking item from the queue.
- * @param q the queue
- * @return NULL on error, otherwise the entry
+ * Insert a new item into the queue
+ *
+ * @param pq The priority queue
+ * @param item Pointer to the item data
+ * @return 0 on success, <0 on failure
  */
-void *git_pqueue_pop(git_pqueue *q);
-
+extern int git_pqueue_insert(git_pqueue *pq, void *item);
 
 /**
- * access highest-ranking item without removing it.
- * @param q the queue
- * @return NULL on error, otherwise the entry
+ * Remove the top item in the priority queue
+ *
+ * @param pq The priority queue
+ * @return item from heap on success, NULL if queue is empty
  */
-void *git_pqueue_peek(git_pqueue *q);
-
-#endif /* PQUEUE_H */
-/** @} */
+extern void *git_pqueue_pop(git_pqueue *pq);
 
+#endif