diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/commit_list.c | 6 | ||||
| -rw-r--r-- | src/commit_list.h | 2 | ||||
| -rw-r--r-- | src/graph.c | 35 | ||||
| -rw-r--r-- | src/merge.c | 15 | ||||
| -rw-r--r-- | src/pqueue.c | 184 | ||||
| -rw-r--r-- | src/pqueue.h | 111 | ||||
| -rw-r--r-- | src/revwalk.c | 5 | ||||
| -rw-r--r-- | src/vector.h | 10 |
8 files changed, 142 insertions, 226 deletions
diff --git a/src/commit_list.c b/src/commit_list.c index 64416e54d..9db3f5633 100644 --- a/src/commit_list.c +++ b/src/commit_list.c @@ -11,10 +11,10 @@ #include "pool.h" #include "odb.h" -int git_commit_list_time_cmp(void *a, void *b) +int git_commit_list_time_cmp(const void *a, const void *b) { - git_commit_list_node *commit_a = (git_commit_list_node *)a; - git_commit_list_node *commit_b = (git_commit_list_node *)b; + const git_commit_list_node *commit_a = a; + const git_commit_list_node *commit_b = b; return (commit_a->time < commit_b->time); } diff --git a/src/commit_list.h b/src/commit_list.h index d2f54b3ca..490d841be 100644 --- a/src/commit_list.h +++ b/src/commit_list.h @@ -39,7 +39,7 @@ typedef struct git_commit_list { } git_commit_list; git_commit_list_node *git_commit_list_alloc_node(git_revwalk *walk); -int git_commit_list_time_cmp(void *a, void *b); +int git_commit_list_time_cmp(const void *a, const void *b); void git_commit_list_free(git_commit_list **list_p); git_commit_list *git_commit_list_insert(git_commit_list_node *item, git_commit_list **list_p); git_commit_list *git_commit_list_insert_by_date(git_commit_list_node *item, git_commit_list **list_p); diff --git a/src/graph.c b/src/graph.c index f39af5ed5..96fda7add 100644 --- a/src/graph.c +++ b/src/graph.c @@ -1,4 +1,3 @@ - /* * Copyright (C) the libgit2 contributors. All rights reserved. * @@ -13,9 +12,9 @@ static int interesting(git_pqueue *list, git_commit_list *roots) { unsigned int i; - /* element 0 isn't used - we need to start at 1 */ - for (i = 1; i < list->size; i++) { - git_commit_list_node *commit = list->d[i]; + + for (i = 0; i < git_pqueue_size(list); i++) { + git_commit_list_node *commit = git_pqueue_get(list, i); if ((commit->flags & STALE) == 0) return 1; } @@ -42,7 +41,7 @@ static int mark_parents(git_revwalk *walk, git_commit_list_node *one, return 0; } - if (git_pqueue_init(&list, 2, git_commit_list_time_cmp) < 0) + if (git_pqueue_init(&list, 0, 2, git_commit_list_time_cmp) < 0) return -1; if (git_commit_list_parse(walk, one) < 0) @@ -59,10 +58,9 @@ static int mark_parents(git_revwalk *walk, git_commit_list_node *one, /* as long as there are non-STALE commits */ while (interesting(&list, roots)) { - git_commit_list_node *commit; + git_commit_list_node *commit = git_pqueue_pop(&list); int flags; - commit = git_pqueue_pop(&list); if (commit == NULL) break; @@ -110,16 +108,16 @@ static int ahead_behind(git_commit_list_node *one, git_commit_list_node *two, { git_commit_list_node *commit; git_pqueue pq; - int i; + int error = 0, i; *ahead = 0; *behind = 0; - if (git_pqueue_init(&pq, 2, git_commit_list_time_cmp) < 0) + if (git_pqueue_init(&pq, 0, 2, git_commit_list_time_cmp) < 0) return -1; - if (git_pqueue_insert(&pq, one) < 0) - goto on_error; - if (git_pqueue_insert(&pq, two) < 0) - goto on_error; + + if ((error = git_pqueue_insert(&pq, one)) < 0 || + (error = git_pqueue_insert(&pq, two)) < 0) + goto done; while ((commit = git_pqueue_pop(&pq)) != NULL) { if (commit->flags & RESULT || @@ -132,18 +130,15 @@ static int ahead_behind(git_commit_list_node *one, git_commit_list_node *two, for (i = 0; i < commit->out_degree; i++) { git_commit_list_node *p = commit->parents[i]; - if (git_pqueue_insert(&pq, p) < 0) - return -1; + if ((error = git_pqueue_insert(&pq, p)) < 0) + goto done; } commit->flags |= RESULT; } +done: git_pqueue_free(&pq); - return 0; - -on_error: - git_pqueue_free(&pq); - return -1; + return error; } int git_graph_ahead_behind(size_t *ahead, size_t *behind, git_repository *repo, diff --git a/src/merge.c b/src/merge.c index 20cfc0e23..d004554cf 100644 --- a/src/merge.c +++ b/src/merge.c @@ -161,10 +161,10 @@ on_error: static int interesting(git_pqueue *list) { - unsigned int i; - /* element 0 isn't used - we need to start at 1 */ - for (i = 1; i < list->size; i++) { - git_commit_list_node *commit = list->d[i]; + size_t i; + + for (i = 0; i < git_pqueue_size(list); i++) { + git_commit_list_node *commit = git_pqueue_get(list, i); if ((commit->flags & STALE) == 0) return 1; } @@ -186,7 +186,7 @@ int git_merge__bases_many(git_commit_list **out, git_revwalk *walk, git_commit_l return git_commit_list_insert(one, out) ? 0 : -1; } - if (git_pqueue_init(&list, twos->length * 2, git_commit_list_time_cmp) < 0) + if (git_pqueue_init(&list, 0, twos->length * 2, git_commit_list_time_cmp) < 0) return -1; if (git_commit_list_parse(walk, one) < 0) @@ -205,10 +205,11 @@ int git_merge__bases_many(git_commit_list **out, git_revwalk *walk, git_commit_l /* as long as there are non-STALE commits */ while (interesting(&list)) { - git_commit_list_node *commit; + git_commit_list_node *commit = git_pqueue_pop(&list); int flags; - commit = git_pqueue_pop(&list); + if (commit == NULL) + break; flags = commit->flags & (PARENT1 | PARENT2 | STALE); if (flags == (PARENT1 | PARENT2)) { 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; } 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 diff --git a/src/revwalk.c b/src/revwalk.c index c0a053211..d6dc10652 100644 --- a/src/revwalk.c +++ b/src/revwalk.c @@ -439,7 +439,8 @@ int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo) walk->commits = git_oidmap_alloc(); GITERR_CHECK_ALLOC(walk->commits); - if (git_pqueue_init(&walk->iterator_time, 8, git_commit_list_time_cmp) < 0 || + if (git_pqueue_init( + &walk->iterator_time, 0, 8, git_commit_list_time_cmp) < 0 || git_vector_init(&walk->twos, 4, NULL) < 0 || git_pool_init(&walk->commit_pool, 1, git_pool__suggest_items_per_page(COMMIT_ALLOC) * COMMIT_ALLOC) < 0) @@ -542,7 +543,7 @@ void git_revwalk_reset(git_revwalk *walk) commit->uninteresting = 0; }); - git_pqueue_clear(&walk->iterator_time); + git_pqueue_free(&walk->iterator_time); git_commit_list_free(&walk->iterator_topo); git_commit_list_free(&walk->iterator_rand); git_commit_list_free(&walk->iterator_reverse); diff --git a/src/vector.h b/src/vector.h index d318463c6..e8a967813 100644 --- a/src/vector.h +++ b/src/vector.h @@ -95,4 +95,14 @@ 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 |