diff options
Diffstat (limited to 'src/pqueue.h')
| -rw-r--r-- | src/pqueue.h | 111 |
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 |