toposort: rename "lifo" field

diff --git a/commit.c b/commit.c
index 9365e3b34aba1c0d4f1ffe9e5e5eebcce886a42e..11b9635df27ae2d6379cf70f5737c33d9d49e701 100644 (file)
--- a/commit.c
+++ b/commit.c
@@ -8,6 +8,7 @@
 #include "notes.h"
 #include "gpg-interface.h"
 #include "mergesort.h"
+#include "commit-slab.h"
 
 static struct commit_extra_header *read_commit_extra_header_lines(const char *buf, size_t len, const char **);
 
@@ -501,56 +502,33 @@ struct commit *pop_commit(struct commit_list **stack)
        return item;
 }
 
-struct commit_slab {
-       int *buf;
-       int alloc;
-};
-
-static void slab_init(struct commit_slab *s)
-{
-       memset(s, 0, sizeof(*s));
-}
-
-static void slab_clear(struct commit_slab *s)
-{
-       free(s->buf);
-       slab_init(s);
-}
+/*
+ * Topological sort support
+ */
 
-static inline int *slab_at(struct commit_slab *s, const struct commit *c)
-{
-       if (s->alloc <= c->index) {
-               int new_alloc = alloc_nr(s->alloc);
-               if (new_alloc <= c->index)
-                       new_alloc = c->index + 1;
-
-               s->buf = xrealloc(s->buf, new_alloc * sizeof(*s->buf));
-               memset(s->buf + s->alloc, 0, new_alloc - s->alloc);
-               s->alloc = new_alloc;
-       }
-       return s->buf + c->index;
-}
+/* count number of children that have not been emitted */
+define_commit_slab(indegree_slab, int);
 
 /*
  * Performs an in-place topological sort on the list supplied.
  */
-void sort_in_topological_order(struct commit_list ** list, int lifo)
+void sort_in_topological_order(struct commit_list ** list, enum rev_sort_order sort_order)
 {
        struct commit_list *next, *orig = *list;
        struct commit_list *work, **insert;
        struct commit_list **pptr;
-       struct commit_slab indegree;
+       struct indegree_slab indegree;
 
        if (!orig)
                return;
        *list = NULL;
 
-       slab_init(&indegree);
+       init_indegree_slab(&indegree);
 
        /* Mark them and clear the indegree */
        for (next = orig; next; next = next->next) {
                struct commit *commit = next->item;
-               *slab_at(&indegree, commit) = 1;
+               *(indegree_slab_at(&indegree, commit)) = 1;
        }
 
        /* update the indegree */
@@ -558,7 +536,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
                struct commit_list * parents = next->item->parents;
                while (parents) {
                        struct commit *parent = parents->item;
-                       int *pi = slab_at(&indegree, parent);
+                       int *pi = indegree_slab_at(&indegree, parent);
 
                        if (*pi)
                                (*pi)++;
@@ -578,12 +556,12 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
        for (next = orig; next; next = next->next) {
                struct commit *commit = next->item;
 
-               if (*slab_at(&indegree, commit) == 1)
+               if (*(indegree_slab_at(&indegree, commit)) == 1)
                        insert = &commit_list_insert(commit, insert)->next;
        }
 
        /* process the list in topological order */
-       if (!lifo)
+       if (sort_order != REV_SORT_IN_GRAPH_ORDER)
                commit_list_sort_by_date(&work);
 
        pptr = list;
@@ -599,7 +577,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
                commit = work_item->item;
                for (parents = commit->parents; parents ; parents = parents->next) {
                        struct commit *parent = parents->item;
-                       int *pi = slab_at(&indegree, parent);
+                       int *pi = indegree_slab_at(&indegree, parent);
 
                        if (!*pi)
                                continue;
@@ -610,22 +588,26 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
                         * guaranteeing topological order.
                         */
                        if (--(*pi) == 1) {
-                               if (!lifo)
+                               switch (sort_order) {
+                               case REV_SORT_BY_COMMIT_DATE:
                                        commit_list_insert_by_date(parent, &work);
-                               else
+                                       break;
+                               default: /* REV_SORT_IN_GRAPH_ORDER */
                                        commit_list_insert(parent, &work);
+                                       break;
+                               }
                        }
                }
                /*
                 * work_item is a commit all of whose children
                 * have already been emitted. we can emit it now.
                 */
-               *slab_at(&indegree, commit) = 0;
+               *(indegree_slab_at(&indegree, commit)) = 0;
                *pptr = work_item;
                pptr = &work_item->next;
        }
 
-       slab_clear(&indegree);
+       clear_indegree_slab(&indegree);
 }
 
 /* merge-base stuff */