Commit 655d381a1948783d7d26ff9ec5ef54ed6bbefb29
2010-05-23T16:51:31
Add topological sorting and new insertion methods for commit lists. 'git_commit_list_toposort()' and 'git_commit_list_timesort()' now sort a commit list by topological and time order respectively. Both sorts are stable and in place. 'git_commit_list_append' has been replaced by 'git_commit_list_push_back' and 'git_commit_list_push_front'. Signed-off-by: Vicent Marti <tanoku@gmail.com> Signed-off-by: Andreas Ericsson <ae@op5.se>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237
diff --git a/src/commit.c b/src/commit.c
index 10b759e..9b52f41 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 72ea4e9..e8d0c53 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 4a59d93..c073337 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 088171c..4575d8b 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 1093c8f..c16281e 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