diff options
Diffstat (limited to 'src/pqueue.c')
-rw-r--r-- | src/pqueue.c | 184 |
1 files changed, 59 insertions, 125 deletions
diff --git a/src/pqueue.c b/src/pqueue.c index 7819ed41e..ddbad7a54 100644 --- a/src/pqueue.c +++ b/src/pqueue.c @@ -3,161 +3,95 @@ * * 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. */ -#include "common.h" #include "pqueue.h" +#include "util.h" -#define left(i) ((i) << 1) -#define right(i) (((i) << 1) + 1) -#define parent(i) ((i) >> 1) - -int git_pqueue_init(git_pqueue *q, size_t n, git_pqueue_cmp cmppri) -{ - assert(q); - - /* Need to allocate n+1 elements since element 0 isn't used. */ - q->d = git__malloc((n + 1) * sizeof(void *)); - GITERR_CHECK_ALLOC(q->d); - - q->size = 1; - q->avail = q->step = (n + 1); /* see comment above about n+1 */ - q->cmppri = cmppri; - - return 0; -} - +#define PQUEUE_LCHILD_OF(I) (((I)<<1)+1) +#define PQUEUE_RCHILD_OF(I) (((I)<<1)+2) +#define PQUEUE_PARENT_OF(I) (((I)-1)>>1) -void git_pqueue_free(git_pqueue *q) +int git_pqueue_init( + git_pqueue *pq, + uint32_t flags, + size_t est_size, + git_vector_cmp cmp) { - git__free(q->d); - q->d = NULL; + pq->flags = flags; + pq->initial_size = est_size; + return git_vector_init(&pq->values, est_size, cmp); } -void git_pqueue_clear(git_pqueue *q) +void git_pqueue_free(git_pqueue *pq) { - q->size = 1; + git_vector_free(&pq->values); } -size_t git_pqueue_size(git_pqueue *q) +static void pqueue_up(git_pqueue *pq, size_t el) { - /* queue element 0 exists but doesn't count since it isn't used. */ - return (q->size - 1); -} + 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); -static void bubble_up(git_pqueue *q, size_t i) -{ - size_t parent_node; - void *moving_node = q->d[i]; - - for (parent_node = parent(i); - ((i > 1) && q->cmppri(q->d[parent_node], moving_node)); - i = parent_node, parent_node = parent(i)) { - q->d[i] = q->d[parent_node]; + el = parent_el; + parent_el = PQUEUE_PARENT_OF(el); } - - q->d[i] = moving_node; } - -static size_t maxchild(git_pqueue *q, size_t i) +static void pqueue_down(git_pqueue *pq, size_t el) { - size_t child_node = left(i); + size_t last = git_vector_length(&pq->values); - if (child_node >= q->size) - return 0; + 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) + kid = rkid; - if ((child_node + 1) < q->size && - q->cmppri(q->d[child_node], q->d[child_node + 1])) - child_node++; /* use right child instead of left */ - - return child_node; -} + if (git_vector_cmp_elements(&pq->values, el, kid) < 0) + break; - -static void percolate_down(git_pqueue *q, size_t i) -{ - size_t child_node; - void *moving_node = q->d[i]; - - while ((child_node = maxchild(q, i)) != 0 && - q->cmppri(moving_node, q->d[child_node])) { - q->d[i] = q->d[child_node]; - i = child_node; + git_vector_swap_elements(&pq->values, el, kid); + el = kid; } - - q->d[i] = moving_node; } - -int git_pqueue_insert(git_pqueue *q, void *d) +int git_pqueue_insert(git_pqueue *pq, void *item) { - void *tmp; - size_t i; - size_t newsize; - - if (!q) return 1; - - /* allocate more memory if necessary */ - if (q->size >= q->avail) { - newsize = q->size + q->step; - tmp = git__realloc(q->d, sizeof(void *) * newsize); - GITERR_CHECK_ALLOC(tmp); - - q->d = tmp; - q->avail = newsize; + int error = 0; + + /* 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) + { + /* skip item if below min item in heap */ + if (pq->values._cmp(item, git_vector_get(&pq->values, 0)) <= 0) + return 0; + (void)git_pqueue_pop(pq); } - /* insert item */ - i = q->size++; - q->d[i] = d; - bubble_up(q, i); + error = git_vector_insert(&pq->values, item); - return 0; -} + if (!error) + pqueue_up(pq, pq->values.length - 1); - -void *git_pqueue_pop(git_pqueue *q) -{ - void *head; - - if (!q || q->size == 1) - return NULL; - - head = q->d[1]; - q->d[1] = q->d[--q->size]; - percolate_down(q, 1); - - return head; + return error; } - -void *git_pqueue_peek(git_pqueue *q) +void *git_pqueue_pop(git_pqueue *pq) { - if (!q || q->size == 1) - return NULL; - return q->d[1]; + void *rval = git_vector_get(&pq->values, 0); + + if (git_vector_length(&pq->values) > 1) { + pq->values.contents[0] = git_vector_last(&pq->values); + git_vector_pop(&pq->values); + pqueue_down(pq, 0); + } else { + git_vector_pop(&pq->values); + } + + return rval; } |