Changed 'git_commit_list' from a linked list to a doubly-linked list.

Changed 'git_commit' to use bit fields instead of flags.

Signed-off-by: Vicent Marti <tanoku@gmail.com>
Signed-off-by: Andreas Ericsson <ae@op5.se>

4 files changed, 128 insertions, 67 deletions

diff --git a/src/commit.c b/src/commit.c
index 8654e891d..b196a807b 100644
--- a/src/commit.c
+++ b/src/commit.c
@@ -40,12 +40,13 @@ void git_commit__mark_uninteresting(git_commit *commit)
     if (commit == NULL)
         return;
 
-	git_commit_list *parents = commit->parents;
+	git_commit_node *parents = commit->parents.head;
 
-    commit->flags |= GIT_COMMIT_HIDE;
+    commit->uninteresting = 1;
 
-	while (parents) {
-        parents->commit->flags |= GIT_COMMIT_HIDE;
+	while (parents)
+    {
+        parents->commit->uninteresting = 1;
 		parents = parents->next;
 	}
 }
@@ -185,10 +186,10 @@ int git_commit__parse_buffer(git_commit *commit, void *data, size_t len)
             return -1;
 
         // Inherit uninteresting flag
-        if (commit->flags & GIT_COMMIT_HIDE)
-            parent->flags |= GIT_COMMIT_HIDE;
+        if (commit->uninteresting)
+            parent->uninteresting = 1;
 
-        git_commit_list_insert(&commit->parents, parent);
+        git_commit_list_append(&commit->parents, parent);
     }
 
     if (git_commit__parse_time(&commit->commit_time, buffer, buffer_end) < 0)
@@ -199,30 +200,90 @@ int git_commit__parse_buffer(git_commit *commit, void *data, size_t len)
     return 0;
 }
 
-void git_commit_list_insert(git_commit_list **list, git_commit *commit)
+void git_commit_list_append(git_commit_list *list, git_commit *commit)
 {
-    if (*list == NULL)
-    {
-        *list = git__malloc(sizeof(git_commit_list));
+    git_commit_node *node = NULL;
+
+    node = git__malloc(sizeof(git_commit_list));
+
+    if (node == NULL)
+        return;
 
-        if (*list == NULL)
-            return;
+    node->commit = commit;
+    node->next = NULL;
+    node->prev = list->tail;
 
-        (*list)->commit = commit;
-        (*list)->next = NULL;
+    if (list->tail == NULL)
+    {
+        list->head = list->tail = node;
     }
     else
     {
-        git_commit_list *new_list = NULL;
+        list->tail->next = node;
+        list->tail = node;
+    }
+
+    list->size++;
+}
+
+git_commit *git_commit_list_pop_back(git_commit_list *list)
+{
+    git_commit_node *node;
+    git_commit *commit;
+
+    if (list->tail == NULL)
+        return NULL;
+
+    node = list->tail;
+    list->tail = list->tail->prev;
+    if (list->tail == NULL)
+        list->head = NULL;
+
+    commit = node->commit;
+    free(node);
+
+    list->size--;
 
-        new_list = git__malloc(sizeof(git_commit_list));
+    return commit;
+}
+
+git_commit *git_commit_list_pop_front(git_commit_list *list)
+{
+    git_commit_node *node;
+    git_commit *commit;
+
+    if (list->head == NULL)
+        return NULL;
+
+    node = list->head;
+    list->head = list->head->next;
+    if (list->head == NULL)
+        list->tail = NULL;
+
+    commit = node->commit;
+    free(node);
 
-        if (new_list == NULL)
-            return;
+    list->size--;
 
-        new_list->commit = commit;
-        new_list->next = *list;
+    return commit;
+}
+
+void git_commit_list_clear(git_commit_list *list, int free_commits)
+{
+    git_commit_node *node, *next_node;
 
-        *list = new_list;
+    node = list->head;
+    while (node)
+    {
+        if (free_commits)
+            free(node->commit);
+
+        next_node = node->next;
+        free(node);
+        node = next_node;
     }
+
+    list->head = list->tail = NULL;
+    list->size = 0;
 }
+
diff --git a/src/commit.h b/src/commit.h
index a0c0512a8..75e6d95a8 100644
--- a/src/commit.h
+++ b/src/commit.h
@@ -5,24 +5,33 @@
 
 #include <time.h>
 
-#define GIT_COMMIT_SEEN     (1 << 0)
-#define GIT_COMMIT_HIDE     (1 << 1)
-#define GIT_COMMIT_DELAY    (1 << 2)
+struct git_commit_node {
+    struct git_commit *commit;
+
+    struct git_commit_node *next;
+    struct git_commit_node *prev;
+};
 
 struct git_commit_list {
-    struct git_commit *commit;
-    struct git_commit_list *next;
+    struct git_commit_node *head;
+    struct git_commit_node *tail;
+    size_t size;
 };
 
 typedef struct git_commit_list git_commit_list;
+typedef struct git_commit_node git_commit_node;
 
 struct git_commit {
     git_oid id;
     time_t commit_time;
     git_revpool *pool;
-    git_commit_list *parents;
+    git_commit_list parents;
 
+    unsigned short in_degree;
     unsigned parsed:1,
+             seen:1,
+             uninteresting:1,
+             topo_delay:1,
              flags:26;
 };
 
@@ -33,6 +42,9 @@ void git_commit__mark_uninteresting(git_commit *commit);
 
 int git_commit_parse_existing(git_commit *commit);
 
-void git_commit_list_insert(git_commit_list **list, 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);
+git_commit *git_commit_list_pop_back(git_commit_list *list);
+git_commit *git_commit_list_pop_front(git_commit_list *list);
 
 #endif
diff --git a/src/revwalk.c b/src/revwalk.c
index 001d938db..94b6d09da 100644
--- a/src/revwalk.c
+++ b/src/revwalk.c
@@ -41,17 +41,8 @@ git_revpool *gitrp_alloc(git_odb *db)
 
 void gitrp_free(git_revpool *walk)
 {
-    git_commit_list *list;
-
-    list = walk->roots;
-    while (list)
-    {
-        free(list->commit);
-        free(list);
-
-        list = list->next;
-    }
-
+    git_commit_list_clear(&(walk->iterator), 0);
+    git_commit_list_clear(&(walk->roots), 1);
 	free(walk);
 }
 
@@ -60,7 +51,7 @@ void gitrp_push(git_revpool *pool, git_commit *commit)
     if (commit->pool != pool)
         return;
 
-    if ((commit->flags & GIT_COMMIT_SEEN) != 0)
+    if (commit->seen)
         return;
 
     if (!commit->parsed)
@@ -72,30 +63,30 @@ void gitrp_push(git_revpool *pool, git_commit *commit)
     // Sanity check: make sure that if the commit
     // has been manually marked as uninteresting,
     // all the parent commits are too.
-    if ((commit->flags & GIT_COMMIT_HIDE) != 0)
+    if (commit->uninteresting)
         git_commit__mark_uninteresting(commit);
 
-    commit->flags |= GIT_COMMIT_SEEN;
+    commit->seen = 1;
 
-    git_commit_list_insert(&pool->roots, commit);
-    git_commit_list_insert(&pool->iterator, commit);
+    git_commit_list_append(&pool->roots, commit);
+    git_commit_list_append(&pool->iterator, commit);
 }
 
 void gitrp_hide(git_revpool *pool, git_commit *commit)
 {
-    git_commit_mark_uninteresting(commit);
+    git_commit__mark_uninteresting(commit);
     gitrp_push(pool, commit);
 }
 
 void gitrp_prepare_walk(git_revpool *pool)
 {
-    git_commit_list *list;
+    git_commit_node *roots;
 
-    list = pool->roots;
-    while (list)
+    roots = pool->roots.head;
+    while (roots)
     {
-        git_commit_list_insert(&pool->iterator, list->commit);
-        list = list->next;
+        git_commit_list_append(&pool->iterator, roots->commit);
+        roots = roots->next;
     }
 
     pool->walking = 1;
@@ -108,30 +99,26 @@ git_commit *gitrp_next(git_revpool *pool)
     if (!pool->walking)
         gitrp_prepare_walk(pool);
 
-    while (pool->iterator != NULL)
+    while ((next = git_commit_list_pop_front(&pool->iterator)) != NULL)
     {
-        git_commit_list *list;
-
-        next = pool->iterator->commit;
-        free(pool->iterator);
-        pool->iterator = pool->iterator->next;
+        git_commit_node *parents;
 
-        list = next->parents;
-        while (list)
+        parents = next->parents.head;
+        while (parents)
         {
-            git_commit *parent = list->commit;
-            list = list->next;
+            git_commit *parent = parents->commit;
+            parents = parents->next;
 
-            if ((parent->flags & GIT_COMMIT_SEEN) != 0)
+            if (parent->seen)
                 continue;
 
             if (parent->parsed == 0)
                 git_commit_parse_existing(parent);
 
-            git_commit_list_insert(&pool->iterator, list->commit);
+            git_commit_list_append(&pool->iterator, parent);
         }
 
-        if ((next->flags & GIT_COMMIT_HIDE) != 0)
+        if (next->uninteresting == 0)
             return next;
     }
 
@@ -142,6 +129,7 @@ git_commit *gitrp_next(git_revpool *pool)
 
 void gitrp_reset(git_revpool *pool)
 {
-    pool->iterator = NULL;
+    git_commit_list_clear(&pool->iterator, 0);
     pool->walking = 0;
 }
+
diff --git a/src/revwalk.h b/src/revwalk.h
index be01c4799..ae692bf0e 100644
--- a/src/revwalk.h
+++ b/src/revwalk.h
@@ -6,8 +6,8 @@
 
 struct git_revpool {
 	git_odb *db;
-    git_commit_list *iterator;
-    git_commit_list *roots;
+    git_commit_list iterator;
+    git_commit_list roots;
 
     unsigned walking:1,
              topological_sort:1;