summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/commit.c68
-rw-r--r--src/commit.h12
-rw-r--r--src/revobject.h9
-rw-r--r--src/revwalk.c13
-rw-r--r--tests/t0403-lists.c12
5 files changed, 99 insertions, 15 deletions
diff --git a/src/commit.c b/src/commit.c
index 10b759e73..9b52f4120 100644
--- a/src/commit.c
+++ b/src/commit.c
@@ -193,7 +193,7 @@ int git_commit__parse_buffer(git_commit *commit, void *data, size_t len)
if (commit->uninteresting)
parent->uninteresting = 1;
- git_commit_list_append(&commit->parents, parent);
+ git_commit_list_push_back(&commit->parents, parent);
}
if (git_commit__parse_time(&commit->commit_time, buffer, buffer_end) < 0)
@@ -204,7 +204,7 @@ int git_commit__parse_buffer(git_commit *commit, void *data, size_t len)
return 0;
}
-void git_commit_list_append(git_commit_list *list, git_commit *commit)
+void git_commit_list_push_back(git_commit_list *list, git_commit *commit)
{
git_commit_node *node = NULL;
@@ -230,6 +230,33 @@ void git_commit_list_append(git_commit_list *list, git_commit *commit)
list->size++;
}
+void git_commit_list_push_front(git_commit_list *list, git_commit *commit)
+{
+ git_commit_node *node = NULL;
+
+ node = git__malloc(sizeof(git_commit_list));
+
+ if (node == NULL)
+ return;
+
+ node->commit = commit;
+ node->next = list->head;
+ node->prev = NULL;
+
+ if (list->head == NULL)
+ {
+ list->head = list->tail = node;
+ }
+ else
+ {
+ list->head->next = node;
+ list->head = node;
+ }
+
+ list->size++;
+}
+
+
git_commit *git_commit_list_pop_back(git_commit_list *list)
{
git_commit_node *node;
@@ -291,7 +318,7 @@ void git_commit_list_clear(git_commit_list *list, int free_commits)
list->size = 0;
}
-void git_commit_list_sort(git_commit_list *list)
+void git_commit_list_timesort(git_commit_list *list)
{
git_commit_node *p, *q, *e;
int in_size, p_size, q_size, merge_count, i;
@@ -345,3 +372,38 @@ void git_commit_list_sort(git_commit_list *list)
} while (merge_count > 1);
}
+
+void git_commit_list_toposort(git_commit_list *list)
+{
+ git_commit *commit;
+ git_commit_list topo;
+ memset(&topo, 0x0, sizeof(git_commit_list));
+
+ while ((commit = git_commit_list_pop_front(list)) != NULL)
+ {
+ git_commit_node *p;
+
+ if (commit->in_degree > 0)
+ {
+ commit->topo_delay = 1;
+ continue;
+ }
+
+ for (p = commit->parents.head; p != NULL; p = p->next)
+ {
+ p->commit->in_degree--;
+
+ if (p->commit->in_degree == 0 && p->commit->topo_delay)
+ {
+ p->commit->topo_delay = 0;
+ git_commit_list_push_front(list, p->commit);
+ }
+ }
+
+ git_commit_list_push_back(&topo, commit);
+ }
+
+ list->head = topo.head;
+ list->tail = topo.tail;
+ list->size = topo.size;
+}
diff --git a/src/commit.h b/src/commit.h
index 72ea4e962..e8d0c5322 100644
--- a/src/commit.h
+++ b/src/commit.h
@@ -43,10 +43,16 @@ void git_commit__mark_uninteresting(git_commit *commit);
int git_commit_parse_existing(git_commit *commit);
-void git_commit_list_clear(git_commit_list *list, int free_commits);
-void git_commit_list_append(git_commit_list *list, git_commit *commit);
+
+void git_commit_list_push_back(git_commit_list *list, git_commit *commit);
+void git_commit_list_push_front(git_commit_list *list, git_commit *commit);
+
git_commit *git_commit_list_pop_back(git_commit_list *list);
git_commit *git_commit_list_pop_front(git_commit_list *list);
-void git_commit_list_sort(git_commit_list *list);
+
+void git_commit_list_clear(git_commit_list *list, int free_commits);
+
+void git_commit_list_timesort(git_commit_list *list);
+void git_commit_list_toposort(git_commit_list *list);
#endif
diff --git a/src/revobject.h b/src/revobject.h
index 4a59d93f4..c073337a4 100644
--- a/src/revobject.h
+++ b/src/revobject.h
@@ -26,10 +26,19 @@ struct git_revpool_table
unsigned int max_count;
};
+struct git_revpool_tableit
+{
+ struct git_revpool_node **nodes;
+ struct git_revpool_node *current_node;
+ unsigned int current_pos;
+ unsigned int size;
+};
+
typedef struct git_revpool_node git_revpool_node;
typedef struct git_revpool_object git_revpool_object;
typedef struct git_revpool_table git_revpool_table;
+typedef struct git_revpool_tableit git_revpool_tableit;
git_revpool_table *git_revpool_table_create(unsigned int min_size);
int git_revpool_table_insert(git_revpool_table *table, git_revpool_object *object);
diff --git a/src/revwalk.c b/src/revwalk.c
index 088171c4d..4575d8b63 100644
--- a/src/revwalk.c
+++ b/src/revwalk.c
@@ -73,7 +73,7 @@ void gitrp_push(git_revpool *pool, git_commit *commit)
if (commit->uninteresting)
git_commit__mark_uninteresting(commit);
- git_commit_list_append(&pool->roots, commit);
+ git_commit_list_push_back(&pool->roots, commit);
}
void gitrp_hide(git_revpool *pool, git_commit *commit)
@@ -95,9 +95,12 @@ void gitrp__enroot(git_revpool *pool, git_commit *commit)
commit->seen = 1;
for (parents = commit->parents.head; parents != NULL; parents = parents->next)
+ {
+ parents->commit->in_degree++;
gitrp__enroot(pool, parents->commit);
+ }
- git_commit_list_append(&pool->iterator, commit);
+ git_commit_list_push_back(&pool->iterator, commit);
}
void gitrp_prepare_walk(git_revpool *pool)
@@ -107,7 +110,11 @@ void gitrp_prepare_walk(git_revpool *pool)
for (it = pool->roots.head; it != NULL; it = it->next)
gitrp__enroot(pool, it->commit);
- // TODO: topo sort, time sort
+ if (pool->sorting & GIT_REVPOOL_SORT_TIME)
+ git_commit_list_timesort(&pool->iterator);
+
+ if (pool->sorting & GIT_REVPOOL_SORT_TOPO)
+ git_commit_list_toposort(&pool->iterator);
if (pool->sorting & GIT_REVPOOL_SORT_REVERSE)
pool->next_commit = &git_commit_list_pop_back;
diff --git a/tests/t0403-lists.c b/tests/t0403-lists.c
index 1093c8ff4..c16281e32 100644
--- a/tests/t0403-lists.c
+++ b/tests/t0403-lists.c
@@ -4,7 +4,7 @@
#include <git/odb.h>
#include <git/commit.h>
-BEGIN_TEST(list_sort_test)
+BEGIN_TEST(list_timesort_test)
git_commit_list list;
git_commit_node *n;
@@ -32,10 +32,10 @@ BEGIN_TEST(list_sort_test)
git_commit *c = git__malloc(sizeof(git_commit));
c->commit_time = (time_t)rand();
- git_commit_list_append(&list, c);
+ git_commit_list_push_back(&list, c);
}
- git_commit_list_sort(&list);
+ git_commit_list_timesort(&list);
TEST_SORTED();
git_commit_list_clear(&list, 1);
}
@@ -46,15 +46,15 @@ BEGIN_TEST(list_sort_test)
git_commit *c = git__malloc(sizeof(git_commit));
c->commit_time = 0;
- git_commit_list_append(&list, c);
+ git_commit_list_push_back(&list, c);
}
- git_commit_list_sort(&list);
+ git_commit_list_timesort(&list);
TEST_SORTED();
git_commit_list_clear(&list, 1);
// Try to sort empty list
- git_commit_list_sort(&list);
+ git_commit_list_timesort(&list);
TEST_SORTED();
END_TEST
View Lorry Controller Status