diff options
| -rw-r--r-- | src/index.c | 6 | ||||
| -rw-r--r-- | src/pqueue.c | 57 | ||||
| -rw-r--r-- | src/pqueue.h | 38 | ||||
| -rw-r--r-- | src/revwalk.c | 2 | ||||
| -rw-r--r-- | src/sortedcache.c | 2 | ||||
| -rw-r--r-- | src/tree.c | 6 | ||||
| -rw-r--r-- | src/vector.c | 17 | ||||
| -rw-r--r-- | src/vector.h | 17 | ||||
| -rw-r--r-- | tests/index/tests.c | 8 |
9 files changed, 78 insertions, 75 deletions
diff --git a/src/index.c b/src/index.c index 7bc5d5b24..1ab126c87 100644 --- a/src/index.c +++ b/src/index.c @@ -1564,7 +1564,7 @@ static int read_reuc(git_index *index, const char *buffer, size_t size) } /* entries are guaranteed to be sorted on-disk */ - index->reuc.sorted = 1; + git_vector_set_sorted(&index->reuc, true); return 0; } @@ -1610,7 +1610,7 @@ static int read_conflict_names(git_index *index, const char *buffer, size_t size #undef read_conflict_name /* entries are guaranteed to be sorted on-disk */ - index->names.sorted = 1; + git_vector_set_sorted(&index->names, true); return 0; } @@ -1812,7 +1812,7 @@ static int parse_index(git_index *index, const char *buffer, size_t buffer_size) #undef seek_forward /* Entries are stored case-sensitively on disk. */ - index->entries.sorted = !index->ignore_case; + git_vector_set_sorted(&index->entries, index->ignore_case); git_vector_sort(&index->entries); return 0; 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; diff --git a/src/pqueue.h b/src/pqueue.h index 3c977e178..da7b74edf 100644 --- a/src/pqueue.h +++ b/src/pqueue.h @@ -9,15 +9,11 @@ #include "vector.h" -typedef struct { - git_vector values; - size_t initial_size; - uint32_t flags; -} git_pqueue; +typedef git_vector git_pqueue; enum { - GIT_PQUEUE_DEFAULT = 0, - GIT_PQUEUE_FIXED_SIZE = (1 << 0), /* don't grow heap, keep highest */ + /* flag meaning: don't grow heap, keep highest values only */ + GIT_PQUEUE_FIXED_SIZE = (GIT_VECTOR_FLAG_MAX << 1), }; /** @@ -25,36 +21,20 @@ enum { * * @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 init_size The initial queue size * @param cmp The entry priority comparison function * @return 0 on success, <0 on error */ extern int git_pqueue_init( git_pqueue *pq, uint32_t flags, - size_t est_size, + size_t init_size, git_vector_cmp cmp); -/** - * Free the queue memory - */ -extern void git_pqueue_free(git_pqueue *pq); - -/** - * Get the number of items in the queue - */ -GIT_INLINE(size_t) git_pqueue_size(const git_pqueue *pq) -{ - return git_vector_length(&pq->values); -} - -/** - * Get an item in the queue - */ -GIT_INLINE(void *) git_pqueue_get(const git_pqueue *pq, size_t pos) -{ - return git_vector_get(&pq->values, pos); -} +#define git_pqueue_free git_vector_free +#define git_pqueue_clear git_vector_clear +#define git_pqueue_size git_vector_length +#define git_pqueue_get git_vector_get /** * Insert a new item into the queue diff --git a/src/revwalk.c b/src/revwalk.c index d6dc10652..3bfc4d1aa 100644 --- a/src/revwalk.c +++ b/src/revwalk.c @@ -543,7 +543,7 @@ void git_revwalk_reset(git_revwalk *walk) commit->uninteresting = 0; }); - git_pqueue_free(&walk->iterator_time); + git_pqueue_clear(&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/sortedcache.c b/src/sortedcache.c index 466e55dbe..13f0921f1 100644 --- a/src/sortedcache.c +++ b/src/sortedcache.c @@ -321,7 +321,7 @@ size_t git_sortedcache_entrycount(const git_sortedcache *sc) void *git_sortedcache_entry(git_sortedcache *sc, size_t pos) { /* make sure the items are sorted so this gets the correct item */ - if (!sc->items.sorted) + if (!git_vector_is_sorted(&sc->items)) git_vector_sort(&sc->items); return git_vector_get(&sc->items, pos); diff --git a/src/tree.c b/src/tree.c index 877a3fcee..94f779eca 100644 --- a/src/tree.c +++ b/src/tree.c @@ -283,7 +283,8 @@ static const git_tree_entry *entry_fromname( { size_t idx; - assert(tree->entries.sorted); /* be safe when we cast away constness */ + /* be safe when we cast away constness - i.e. don't trigger a sort */ + assert(git_vector_is_sorted(&tree->entries)); if (tree_key_search(&idx, (git_vector *)&tree->entries, name, name_len) < 0) return NULL; @@ -333,7 +334,8 @@ int git_tree__prefix_position(const git_tree *tree, const char *path) ksearch.filename = path; ksearch.filename_len = strlen(path); - assert(tree->entries.sorted); /* be safe when we cast away constness */ + /* be safe when we cast away constness - i.e. don't trigger a sort */ + assert(git_vector_is_sorted(&tree->entries)); /* Find tree entry with appropriate prefix */ git_vector_bsearch2( diff --git a/src/vector.c b/src/vector.c index f0c2f06c2..e5d8919d3 100644 --- a/src/vector.c +++ b/src/vector.c @@ -56,7 +56,9 @@ int git_vector_dup(git_vector *v, const git_vector *src, git_vector_cmp cmp) v->_alloc_size = src->length; v->_cmp = cmp; v->length = src->length; - v->sorted = src->sorted && cmp == src->_cmp; + v->flags = src->flags; + if (cmp != src->_cmp) + git_vector_set_sorted(v, 0); v->contents = git__malloc(bytes); GITERR_CHECK_ALLOC(v->contents); @@ -97,7 +99,7 @@ int git_vector_init(git_vector *v, size_t initial_size, git_vector_cmp cmp) v->_alloc_size = 0; v->_cmp = cmp; v->length = 0; - v->sorted = 1; + v->flags = GIT_VECTOR_SORTED; v->contents = NULL; return resize_vector(v, max(initial_size, MIN_ALLOCSIZE)); @@ -128,7 +130,8 @@ int git_vector_insert(git_vector *v, void *element) return -1; v->contents[v->length++] = element; - v->sorted = 0; + + git_vector_set_sorted(v, v->length <= 1); return 0; } @@ -141,7 +144,7 @@ int git_vector_insert_sorted( assert(v && v->_cmp); - if (!v->sorted) + if (!git_vector_is_sorted(v)) git_vector_sort(v); if (v->length >= v->_alloc_size && @@ -171,11 +174,11 @@ void git_vector_sort(git_vector *v) { assert(v); - if (v->sorted || !v->_cmp) + if (git_vector_is_sorted(v) || !v->_cmp) return; git__tsort(v->contents, v->length, v->_cmp); - v->sorted = 1; + git_vector_set_sorted(v, 1); } int git_vector_bsearch2( @@ -291,7 +294,7 @@ void git_vector_clear(git_vector *v) { assert(v); v->length = 0; - v->sorted = 1; + git_vector_set_sorted(v, 1); } void git_vector_swap(git_vector *a, git_vector *b) diff --git a/src/vector.h b/src/vector.h index e8a967813..f983c55d5 100644 --- a/src/vector.h +++ b/src/vector.h @@ -11,12 +11,17 @@ typedef int (*git_vector_cmp)(const void *, const void *); +enum { + GIT_VECTOR_SORTED = (1u << 0), + GIT_VECTOR_FLAG_MAX = (1u << 1), +}; + typedef struct git_vector { size_t _alloc_size; git_vector_cmp _cmp; void **contents; size_t length; - int sorted; + uint32_t flags; } git_vector; #define GIT_VECTOR_INIT {0} @@ -86,12 +91,20 @@ void git_vector_remove_matching( int git_vector_resize_to(git_vector *v, size_t new_length); int git_vector_set(void **old, git_vector *v, size_t position, void *value); +/** Check if vector is sorted */ +#define git_vector_is_sorted(V) (((V)->flags & GIT_VECTOR_SORTED) != 0) + +/** Directly set sorted state of vector */ +#define git_vector_set_sorted(V,S) do { \ + (V)->flags = (S) ? ((V)->flags | GIT_VECTOR_SORTED) : \ + ((V)->flags & ~GIT_VECTOR_SORTED); } while (0) + /** Set the comparison function used for sorting the vector */ GIT_INLINE(void) git_vector_set_cmp(git_vector *v, git_vector_cmp cmp) { if (cmp != v->_cmp) { v->_cmp = cmp; - v->sorted = 0; + git_vector_set_sorted(v, 0); } } diff --git a/tests/index/tests.c b/tests/index/tests.c index bd90bc557..55a2f2c51 100644 --- a/tests/index/tests.c +++ b/tests/index/tests.c @@ -80,7 +80,7 @@ void test_index_tests__empty_index(void) cl_assert(index->on_disk == 0); cl_assert(git_index_entrycount(index) == 0); - cl_assert(index->entries.sorted); + cl_assert(git_vector_is_sorted(&index->entries)); git_index_free(index); } @@ -95,7 +95,7 @@ void test_index_tests__default_test_index(void) cl_assert(index->on_disk); cl_assert(git_index_entrycount(index) == index_entry_count); - cl_assert(index->entries.sorted); + cl_assert(git_vector_is_sorted(&index->entries)); entries = (git_index_entry **)index->entries.contents; @@ -118,7 +118,7 @@ void test_index_tests__gitgit_index(void) cl_assert(index->on_disk); cl_assert(git_index_entrycount(index) == index_entry_count_2); - cl_assert(index->entries.sorted); + cl_assert(git_vector_is_sorted(&index->entries)); cl_assert(index->tree != NULL); git_index_free(index); @@ -195,7 +195,7 @@ void test_index_tests__sort1(void) cl_git_pass(git_index_open(&index, "fake-index")); /* FIXME: this test is slightly dumb */ - cl_assert(index->entries.sorted); + cl_assert(git_vector_is_sorted(&index->entries)); git_index_free(index); } |