Move merge functions to merge.c

In so doing, promote commit_list to git_commit_list,
with its own internal API header.

6 files changed, 520 insertions, 467 deletions

diff --git a/src/commit_list.c b/src/commit_list.c
new file mode 100644
index 000000000..c1a7b223f
--- /dev/null
+++ b/src/commit_list.c
@@ -0,0 +1,190 @@
+/*
+ * Copyright (C) 2009-2012 the libgit2 contributors
+ *
+ * This file is part of libgit2, distributed under the GNU GPL v2 with
+ * a Linking Exception. For full terms see the included COPYING file.
+ */
+
+#include "commit_list.h"
+#include "common.h"
+#include "revwalk.h"
+#include "pool.h"
+#include "odb.h"
+
+int git_commit_list_time_cmp(void *a, void *b)
+{
+	git_commit_list_node *commit_a = (git_commit_list_node *)a;
+	git_commit_list_node *commit_b = (git_commit_list_node *)b;
+
+	return (commit_a->time < commit_b->time);
+}
+
+git_commit_list *git_commit_list_insert(git_commit_list_node *item, git_commit_list **list_p)
+{
+	git_commit_list *new_list = git__malloc(sizeof(git_commit_list));
+	if (new_list != NULL) {
+		new_list->item = item;
+		new_list->next = *list_p;
+	}
+	*list_p = new_list;
+	return new_list;
+}
+
+git_commit_list *git_commit_list_insert_by_date(git_commit_list_node *item, git_commit_list **list_p)
+{
+	git_commit_list **pp = list_p;
+	git_commit_list *p;
+
+	while ((p = *pp) != NULL) {
+		if (git_commit_list_time_cmp(p->item, item) < 0)
+			break;
+
+		pp = &p->next;
+	}
+
+	return git_commit_list_insert(item, pp);
+}
+
+git_commit_list_node *git_commit_list_alloc_node(git_revwalk *walk)
+{
+	return (git_commit_list_node *)git_pool_malloc(&walk->commit_pool, COMMIT_ALLOC);
+}
+
+static int commit_error(git_commit_list_node *commit, const char *msg)
+{
+	char commit_oid[GIT_OID_HEXSZ + 1];
+	git_oid_fmt(commit_oid, &commit->oid);
+	commit_oid[GIT_OID_HEXSZ] = '\0';
+
+	giterr_set(GITERR_ODB, "Failed to parse commit %s - %s", commit_oid, msg);
+
+	return -1;
+}
+
+static git_commit_list_node **alloc_parents(
+	git_revwalk *walk, git_commit_list_node *commit, size_t n_parents)
+{
+	if (n_parents <= PARENTS_PER_COMMIT)
+		return (git_commit_list_node **)((char *)commit + sizeof(git_commit_list_node));
+
+	return (git_commit_list_node **)git_pool_malloc(
+		&walk->commit_pool, (uint32_t)(n_parents * sizeof(git_commit_list_node *)));
+}
+
+
+void git_commit_list_free(git_commit_list **list_p)
+{
+	git_commit_list *list = *list_p;
+
+	if (list == NULL)
+		return;
+
+	while (list) {
+		git_commit_list *temp = list;
+		list = temp->next;
+		git__free(temp);
+	}
+
+	*list_p = NULL;
+}
+
+git_commit_list_node *git_commit_list_pop(git_commit_list **stack)
+{
+	git_commit_list *top = *stack;
+	git_commit_list_node *item = top ? top->item : NULL;
+
+	if (top) {
+		*stack = top->next;
+		git__free(top);
+	}
+	return item;
+}
+
+static int commit_quick_parse(git_revwalk *walk, git_commit_list_node *commit, git_rawobj *raw)
+{
+	const size_t parent_len = strlen("parent ") + GIT_OID_HEXSZ + 1;
+	unsigned char *buffer = raw->data;
+	unsigned char *buffer_end = buffer + raw->len;
+	unsigned char *parents_start, *committer_start;
+	int i, parents = 0;
+	int commit_time;
+
+	buffer += strlen("tree ") + GIT_OID_HEXSZ + 1;
+
+	parents_start = buffer;
+	while (buffer + parent_len < buffer_end && memcmp(buffer, "parent ", strlen("parent ")) == 0) {
+		parents++;
+		buffer += parent_len;
+	}
+
+	commit->parents = alloc_parents(walk, commit, parents);
+	GITERR_CHECK_ALLOC(commit->parents);
+
+	buffer = parents_start;
+	for (i = 0; i < parents; ++i) {
+		git_oid oid;
+
+		if (git_oid_fromstr(&oid, (char *)buffer + strlen("parent ")) < 0)
+			return -1;
+
+		commit->parents[i] = commit_lookup(walk, &oid);
+		if (commit->parents[i] == NULL)
+			return -1;
+
+		buffer += parent_len;
+	}
+
+	commit->out_degree = (unsigned short)parents;
+
+	if ((committer_start = buffer = memchr(buffer, '\n', buffer_end - buffer)) == NULL)
+		return commit_error(commit, "object is corrupted");
+
+	buffer++;
+
+	if ((buffer = memchr(buffer, '\n', buffer_end - buffer)) == NULL)
+		return commit_error(commit, "object is corrupted");
+
+	/* Skip trailing spaces */
+	while (buffer > committer_start && git__isspace(*buffer))
+		buffer--;
+
+	/* Seek for the begining of the pack of digits */
+	while (buffer > committer_start && git__isdigit(*buffer))
+		buffer--;
+
+	/* Skip potential timezone offset */
+	if ((buffer > committer_start) && (*buffer == '+' || *buffer == '-')) {
+		buffer--;
+
+		while (buffer > committer_start && git__isspace(*buffer))
+			buffer--;
+
+		while (buffer > committer_start && git__isdigit(*buffer))
+			buffer--;
+	}
+
+	if ((buffer == committer_start) || (git__strtol32(&commit_time, (char *)(buffer + 1), NULL, 10) < 0))
+		return commit_error(commit, "cannot parse commit time");
+
+	commit->time = (time_t)commit_time;
+	commit->parsed = 1;
+	return 0;
+}
+
+int git_commit_list_parse(git_revwalk *walk, git_commit_list_node *commit)
+{
+	git_odb_object *obj;
+	int error;
+
+	if (commit->parsed)
+		return 0;
+
+	if ((error = git_odb_read(&obj, walk->odb, &commit->oid)) < 0)
+		return error;
+	assert(obj->raw.type == GIT_OBJ_COMMIT);
+
+	error = commit_quick_parse(walk, commit, &obj->raw);
+	git_odb_object_free(obj);
+	return error;
+}
+
diff --git a/src/commit_list.h b/src/commit_list.h
new file mode 100644
index 000000000..ba809c901
--- /dev/null
+++ b/src/commit_list.h
@@ -0,0 +1,49 @@
+/*
+ * Copyright (C) 2009-2012 the libgit2 contributors
+ *
+ * This file is part of libgit2, distributed under the GNU GPL v2 with
+ * a Linking Exception. For full terms see the included COPYING file.
+ */
+#ifndef INCLUDE_commit_list_h__
+#define INCLUDE_commit_list_h__
+
+#include "git2/oid.h"
+
+#define PARENT1  (1 << 0)
+#define PARENT2  (1 << 1)
+#define RESULT   (1 << 2)
+#define STALE    (1 << 3)
+
+#define PARENTS_PER_COMMIT	2
+#define COMMIT_ALLOC \
+	(sizeof(git_commit_list_node) + PARENTS_PER_COMMIT * sizeof(git_commit_list_node *))
+
+typedef struct git_commit_list_node {
+	git_oid oid;
+	uint32_t time;
+	unsigned int seen:1,
+			 uninteresting:1,
+			 topo_delay:1,
+			 parsed:1,
+			 flags : 4;
+
+	unsigned short in_degree;
+	unsigned short out_degree;
+
+	struct git_commit_list_node **parents;
+} git_commit_list_node;
+
+typedef struct git_commit_list {
+	git_commit_list_node *item;
+	struct git_commit_list *next;
+} git_commit_list;
+
+git_commit_list_node *git_commit_list_alloc_node(git_revwalk *walk);
+int git_commit_list_time_cmp(void *a, void *b);
+void git_commit_list_free(git_commit_list **list_p);
+git_commit_list *git_commit_list_insert(git_commit_list_node *item, git_commit_list **list_p);
+git_commit_list *git_commit_list_insert_by_date(git_commit_list_node *item, git_commit_list **list_p);
+int git_commit_list_parse(git_revwalk *walk, git_commit_list_node *commit);
+git_commit_list_node *git_commit_list_pop(git_commit_list **stack);
+
+#endif
diff --git a/src/merge.c b/src/merge.c
index 135af6a8c..c795b808b 100644
--- a/src/merge.c
+++ b/src/merge.c
@@ -6,12 +6,14 @@
  */
 
 #include "repository.h"
+#include "revwalk.h"
 #include "buffer.h"
 #include "merge.h"
 #include "refs.h"
 #include "git2/repository.h"
 #include "git2/merge.h"
 #include "git2/reset.h"
+#include "commit_list.h"
 
 int git_merge__cleanup(git_repository *repo)
 {
@@ -46,3 +48,197 @@ cleanup:
 	return error;
 }
 
+int git_merge_base_many(git_oid *out, git_repository *repo, const git_oid input_array[], size_t length)
+{
+	git_revwalk *walk;
+	git_vector list;
+	git_commit_list *result = NULL;
+	int error = -1;
+	unsigned int i;
+	git_commit_list_node *commit;
+
+	assert(out && repo && input_array);
+
+	if (length < 2) {
+		giterr_set(GITERR_INVALID, "At least two commits are required to find an ancestor. Provided 'length' was %u.", length);
+		return -1;
+	}
+
+	if (git_vector_init(&list, length - 1, NULL) < 0)
+		return -1;
+
+	if (git_revwalk_new(&walk, repo) < 0)
+		goto cleanup;
+
+	for (i = 1; i < length; i++) {
+		commit = commit_lookup(walk, &input_array[i]);
+		if (commit == NULL)
+			goto cleanup;
+
+		git_vector_insert(&list, commit);
+	}
+
+	commit = commit_lookup(walk, &input_array[0]);
+	if (commit == NULL)
+		goto cleanup;
+
+	if (git_merge__bases_many(&result, walk, commit, &list) < 0)
+		goto cleanup;
+
+	if (!result) {
+		error = GIT_ENOTFOUND;
+		goto cleanup;
+	}
+
+	git_oid_cpy(out, &result->item->oid);
+
+	error = 0;
+
+cleanup:
+	git_commit_list_free(&result);
+	git_revwalk_free(walk);
+	git_vector_free(&list);
+	return error;
+}
+
+int git_merge_base(git_oid *out, git_repository *repo, const git_oid *one, const git_oid *two)
+{
+	git_revwalk *walk;
+	git_vector list;
+	git_commit_list *result = NULL;
+	git_commit_list_node *commit;
+	void *contents[1];
+
+	if (git_revwalk_new(&walk, repo) < 0)
+		return -1;
+
+	commit = commit_lookup(walk, two);
+	if (commit == NULL)
+		goto on_error;
+
+	/* This is just one value, so we can do it on the stack */
+	memset(&list, 0x0, sizeof(git_vector));
+	contents[0] = commit;
+	list.length = 1;
+	list.contents = contents;
+
+	commit = commit_lookup(walk, one);
+	if (commit == NULL)
+		goto on_error;
+
+	if (git_merge__bases_many(&result, walk, commit, &list) < 0)
+		goto on_error;
+
+	if (!result) {
+		git_revwalk_free(walk);
+		giterr_clear();
+		return GIT_ENOTFOUND;
+	}
+
+	git_oid_cpy(out, &result->item->oid);
+	git_commit_list_free(&result);
+	git_revwalk_free(walk);
+
+	return 0;
+
+on_error:
+	git_revwalk_free(walk);
+	return -1;
+}
+
+static int interesting(git_pqueue *list)
+{
+	unsigned int i;
+	/* element 0 isn't used - we need to start at 1 */
+	for (i = 1; i < list->size; i++) {
+		git_commit_list_node *commit = list->d[i];
+		if ((commit->flags & STALE) == 0)
+			return 1;
+	}
+
+	return 0;
+}
+
+int git_merge__bases_many(git_commit_list **out, git_revwalk *walk, git_commit_list_node *one, git_vector *twos)
+{
+	int error;
+	unsigned int i;
+	git_commit_list_node *two;
+	git_commit_list *result = NULL, *tmp = NULL;
+	git_pqueue list;
+
+	/* if the commit is repeated, we have a our merge base already */
+	git_vector_foreach(twos, i, two) {
+		if (one == two)
+			return git_commit_list_insert(one, out) ? 0 : -1;
+	}
+
+	if (git_pqueue_init(&list, twos->length * 2, git_commit_list_time_cmp) < 0)
+		return -1;
+
+	if (git_commit_list_parse(walk, one) < 0)
+	    return -1;
+
+	one->flags |= PARENT1;
+	if (git_pqueue_insert(&list, one) < 0)
+		return -1;
+
+	git_vector_foreach(twos, i, two) {
+		git_commit_list_parse(walk, two);
+		two->flags |= PARENT2;
+		if (git_pqueue_insert(&list, two) < 0)
+			return -1;
+	}
+
+	/* as long as there are non-STALE commits */
+	while (interesting(&list)) {
+		git_commit_list_node *commit;
+		int flags;
+
+		commit = git_pqueue_pop(&list);
+
+		flags = commit->flags & (PARENT1 | PARENT2 | STALE);
+		if (flags == (PARENT1 | PARENT2)) {
+			if (!(commit->flags & RESULT)) {
+				commit->flags |= RESULT;
+				if (git_commit_list_insert(commit, &result) == NULL)
+					return -1;
+			}
+			/* we mark the parents of a merge stale */
+			flags |= STALE;
+		}
+
+		for (i = 0; i < commit->out_degree; i++) {
+			git_commit_list_node *p = commit->parents[i];
+			if ((p->flags & flags) == flags)
+				continue;
+
+			if ((error = git_commit_list_parse(walk, p)) < 0)
+				return error;
+
+			p->flags |= flags;
+			if (git_pqueue_insert(&list, p) < 0)
+				return -1;
+		}
+	}
+
+	git_pqueue_free(&list);
+
+	/* filter out any stale commits in the results */
+	tmp = result;
+	result = NULL;
+
+	while (tmp) {
+		struct git_commit_list *next = tmp->next;
+		if (!(tmp->item->flags & STALE))
+			if (git_commit_list_insert_by_date(tmp->item, &result) == NULL)
+				return -1;
+
+		git__free(tmp);
+		tmp = next;
+	}
+
+	*out = result;
+	return 0;
+}
+
diff --git a/src/merge.h b/src/merge.h
index 2117d9214..3681e24b7 100644
--- a/src/merge.h
+++ b/src/merge.h
@@ -8,6 +8,8 @@
 #define INCLUDE_merge_h__
 
 #include "git2/types.h"
+#include "git2/merge.h"
+#include "commit_list.h"
 
 #define GIT_MERGE_MSG_FILE		"MERGE_MSG"
 #define GIT_MERGE_MODE_FILE		"MERGE_MODE"
@@ -15,5 +17,6 @@
 #define MERGE_CONFIG_FILE_MODE	0666
 
 int git_merge__cleanup(git_repository *repo);
+int git_merge__bases_many(git_commit_list **out, git_revwalk *walk, git_commit_list_node *one, git_vector *twos);
 
 #endif
diff --git a/src/revwalk.c b/src/revwalk.c
index 236c94502..bdbbdbd17 100644
--- a/src/revwalk.c
+++ b/src/revwalk.c
@@ -8,149 +8,16 @@
 #include "common.h"
 #include "commit.h"
 #include "odb.h"
-#include "pqueue.h"
 #include "pool.h"
-#include "oidmap.h"
 
-#include "git2/revwalk.h"
-#include "git2/merge.h"
+#include "revwalk.h"
+#include "merge.h"
 
 #include <regex.h>
 
-GIT__USE_OIDMAP;
-
-#define PARENT1  (1 << 0)
-#define PARENT2  (1 << 1)
-#define RESULT   (1 << 2)
-#define STALE    (1 << 3)
-
-typedef struct commit_object {
-	git_oid oid;
-	uint32_t time;
-	unsigned int seen:1,
-			 uninteresting:1,
-			 topo_delay:1,
-			 parsed:1,
-			 flags : 4;
-
-	unsigned short in_degree;
-	unsigned short out_degree;
-
-	struct commit_object **parents;
-} commit_object;
-
-typedef struct commit_list {
-	commit_object *item;
-	struct commit_list *next;
-} commit_list;
-
-struct git_revwalk {
-	git_repository *repo;
-	git_odb *odb;
-
-	git_oidmap *commits;
-	git_pool commit_pool;
-
-	commit_list *iterator_topo;
-	commit_list *iterator_rand;
-	commit_list *iterator_reverse;
-	git_pqueue iterator_time;
-
-	int (*get_next)(commit_object **, git_revwalk *);
-	int (*enqueue)(git_revwalk *, commit_object *);
-
-	unsigned walking:1;
-	unsigned int sorting;
-
-	/* merge base calculation */
-	commit_object *one;
-	git_vector twos;
-};
-
-static int commit_time_cmp(void *a, void *b)
-{
-	commit_object *commit_a = (commit_object *)a;
-	commit_object *commit_b = (commit_object *)b;
-
-	return (commit_a->time < commit_b->time);
-}
-
-static commit_list *commit_list_insert(commit_object *item, commit_list **list_p)
-{
-	commit_list *new_list = git__malloc(sizeof(commit_list));
-	if (new_list != NULL) {
-		new_list->item = item;
-		new_list->next = *list_p;
-	}
-	*list_p = new_list;
-	return new_list;
-}
-
-static commit_list *commit_list_insert_by_date(commit_object *item, commit_list **list_p)
-{
-	commit_list **pp = list_p;
-	commit_list *p;
-
-	while ((p = *pp) != NULL) {
-		if (commit_time_cmp(p->item, item) < 0)
-			break;
-
-		pp = &p->next;
-	}
-
-	return commit_list_insert(item, pp);
-}
-static void commit_list_free(commit_list **list_p)
-{
-	commit_list *list = *list_p;
-
-	if (list == NULL)
-		return;
-
-	while (list) {
-		commit_list *temp = list;
-		list = temp->next;
-		git__free(temp);
-	}
-
-	*list_p = NULL;
-}
-
-static commit_object *commit_list_pop(commit_list **stack)
-{
-	commit_list *top = *stack;
-	commit_object *item = top ? top->item : NULL;
-
-	if (top) {
-		*stack = top->next;
-		git__free(top);
-	}
-	return item;
-}
-
-#define PARENTS_PER_COMMIT	2
-#define COMMIT_ALLOC \
-	(sizeof(commit_object) + PARENTS_PER_COMMIT * sizeof(commit_object *))
-
-static commit_object *alloc_commit(git_revwalk *walk)
-{
-	return (commit_object *)git_pool_malloc(&walk->commit_pool, COMMIT_ALLOC);
-}
-
-static commit_object **alloc_parents(
-	git_revwalk *walk, commit_object *commit, size_t n_parents)
-{
-	if (n_parents <= PARENTS_PER_COMMIT)
-		return (commit_object **)((char *)commit + sizeof(commit_object));
-
-	return (commit_object **)git_pool_malloc(
-		&walk->commit_pool, (uint32_t)(n_parents * sizeof(commit_object *)));
-}
-
-
-static commit_object *commit_lookup(git_revwalk *walk, const git_oid *oid)
+git_commit_list_node *commit_lookup(git_revwalk *walk, const git_oid *oid)
 {
-	commit_object *commit;
+	git_commit_list_node *commit;
 	khiter_t pos;
 	int ret;
 
@@ -159,7 +26,7 @@ static commit_object *commit_lookup(git_revwalk *walk, const git_oid *oid)
 	if (pos != kh_end(walk->commits))
 		return kh_value(walk->commits, pos);
 
-	commit = alloc_commit(walk);
+	commit = git_commit_list_alloc_node(walk);
 	if (commit == NULL)
 		return NULL;
 
@@ -172,300 +39,7 @@ static commit_object *commit_lookup(git_revwalk *walk, const git_oid *oid)
 	return commit;
 }
 
-static int commit_error(commit_object *commit, const char *msg)
-{
-	char commit_oid[GIT_OID_HEXSZ + 1];
-	git_oid_fmt(commit_oid, &commit->oid);
-	commit_oid[GIT_OID_HEXSZ] = '\0';
-
-	giterr_set(GITERR_ODB, "Failed to parse commit %s - %s", commit_oid, msg);
-
-	return -1;
-}
-
-static int commit_quick_parse(git_revwalk *walk, commit_object *commit, git_rawobj *raw)
-{
-	const size_t parent_len = strlen("parent ") + GIT_OID_HEXSZ + 1;
-	unsigned char *buffer = raw->data;
-	unsigned char *buffer_end = buffer + raw->len;
-	unsigned char *parents_start, *committer_start;
-	int i, parents = 0;
-	int commit_time;
-
-	buffer += strlen("tree ") + GIT_OID_HEXSZ + 1;
-
-	parents_start = buffer;
-	while (buffer + parent_len < buffer_end && memcmp(buffer, "parent ", strlen("parent ")) == 0) {
-		parents++;
-		buffer += parent_len;
-	}
-
-	commit->parents = alloc_parents(walk, commit, parents);
-	GITERR_CHECK_ALLOC(commit->parents);
-
-	buffer = parents_start;
-	for (i = 0; i < parents; ++i) {
-		git_oid oid;
-
-		if (git_oid_fromstr(&oid, (char *)buffer + strlen("parent ")) < 0)
-			return -1;
-
-		commit->parents[i] = commit_lookup(walk, &oid);
-		if (commit->parents[i] == NULL)
-			return -1;
-
-		buffer += parent_len;
-	}
-
-	commit->out_degree = (unsigned short)parents;
-
-	if ((committer_start = buffer = memchr(buffer, '\n', buffer_end - buffer)) == NULL)
-		return commit_error(commit, "object is corrupted");
-
-	buffer++;
-
-	if ((buffer = memchr(buffer, '\n', buffer_end - buffer)) == NULL)
-		return commit_error(commit, "object is corrupted");
-
-	/* Skip trailing spaces */
-	while (buffer > committer_start && git__isspace(*buffer))
-		buffer--;
-
-	/* Seek for the begining of the pack of digits */
-	while (buffer > committer_start && git__isdigit(*buffer))
-		buffer--;
-
-	/* Skip potential timezone offset */
-	if ((buffer > committer_start) && (*buffer == '+' || *buffer == '-')) {
-		buffer--;
-
-		while (buffer > committer_start && git__isspace(*buffer))
-			buffer--;
-
-		while (buffer > committer_start && git__isdigit(*buffer))
-			buffer--;
-	}
-
-	if ((buffer == committer_start) || (git__strtol32(&commit_time, (char *)(buffer + 1), NULL, 10) < 0))
-		return commit_error(commit, "cannot parse commit time");
-
-	commit->time = (time_t)commit_time;
-	commit->parsed = 1;
-	return 0;
-}
-
-static int commit_parse(git_revwalk *walk, commit_object *commit)
-{
-	git_odb_object *obj;
-	int error;
-
-	if (commit->parsed)
-		return 0;
-
-	if ((error = git_odb_read(&obj, walk->odb, &commit->oid)) < 0)
-		return error;
-	assert(obj->raw.type == GIT_OBJ_COMMIT);
-
-	error = commit_quick_parse(walk, commit, &obj->raw);
-	git_odb_object_free(obj);
-	return error;
-}
-
-static int interesting(git_pqueue *list)
-{
-	unsigned int i;
-	/* element 0 isn't used - we need to start at 1 */
-	for (i = 1; i < list->size; i++) {
-		commit_object *commit = list->d[i];
-		if ((commit->flags & STALE) == 0)
-			return 1;
-	}
-
-	return 0;
-}
-
-static int merge_bases_many(commit_list **out, git_revwalk *walk, commit_object *one, git_vector *twos)
-{
-	int error;
-	unsigned int i;
-	commit_object *two;
-	commit_list *result = NULL, *tmp = NULL;
-	git_pqueue list;
-
-	/* if the commit is repeated, we have a our merge base already */
-	git_vector_foreach(twos, i, two) {
-		if (one == two)
-			return commit_list_insert(one, out) ? 0 : -1;
-	}
-
-	if (git_pqueue_init(&list, twos->length * 2, commit_time_cmp) < 0)
-		return -1;
-
-	if (commit_parse(walk, one) < 0)
-	    return -1;
-
-	one->flags |= PARENT1;
-	if (git_pqueue_insert(&list, one) < 0)
-		return -1;
-
-	git_vector_foreach(twos, i, two) {
-		commit_parse(walk, two);
-		two->flags |= PARENT2;
-		if (git_pqueue_insert(&list, two) < 0)
-			return -1;
-	}
-
-	/* as long as there are non-STALE commits */
-	while (interesting(&list)) {
-		commit_object *commit;
-		int flags;
-
-		commit = git_pqueue_pop(&list);
-
-		flags = commit->flags & (PARENT1 | PARENT2 | STALE);
-		if (flags == (PARENT1 | PARENT2)) {
-			if (!(commit->flags & RESULT)) {
-				commit->flags |= RESULT;
-				if (commit_list_insert(commit, &result) == NULL)
-					return -1;
-			}
-			/* we mark the parents of a merge stale */
-			flags |= STALE;
-		}
-
-		for (i = 0; i < commit->out_degree; i++) {
-			commit_object *p = commit->parents[i];
-			if ((p->flags & flags) == flags)
-				continue;
-
-			if ((error = commit_parse(walk, p)) < 0)
-				return error;
-
-			p->flags |= flags;
-			if (git_pqueue_insert(&list, p) < 0)
-				return -1;
-		}
-	}
-
-	git_pqueue_free(&list);
-
-	/* filter out any stale commits in the results */
-	tmp = result;
-	result = NULL;
-
-	while (tmp) {
-		struct commit_list *next = tmp->next;
-		if (!(tmp->item->flags & STALE))
-			if (commit_list_insert_by_date(tmp->item, &result) == NULL)
-				return -1;
-
-		git__free(tmp);
-		tmp = next;
-	}
-
-	*out = result;
-	return 0;
-}
-
-int git_merge_base_many(git_oid *out, git_repository *repo, const git_oid input_array[], size_t length)
-{
-	git_revwalk *walk;
-	git_vector list;
-	commit_list *result = NULL;
-	int error = -1;
-	unsigned int i;
-	commit_object *commit;
-
-	assert(out && repo && input_array);
-
-	if (length < 2) {
-		giterr_set(GITERR_INVALID, "At least two commits are required to find an ancestor. Provided 'length' was %u.", length);
-		return -1;
-	}
-
-	if (git_vector_init(&list, length - 1, NULL) < 0)
-		return -1;
-
-	if (git_revwalk_new(&walk, repo) < 0)
-		goto cleanup;
-
-	for (i = 1; i < length; i++) {
-		commit = commit_lookup(walk, &input_array[i]);
-		if (commit == NULL)
-			goto cleanup;
-
-		git_vector_insert(&list, commit);
-	}
-
-	commit = commit_lookup(walk, &input_array[0]);
-	if (commit == NULL)
-		goto cleanup;
-
-	if (merge_bases_many(&result, walk, commit, &list) < 0)
-		goto cleanup;
-
-	if (!result) {
-		error = GIT_ENOTFOUND;
-		goto cleanup;
-	}
-
-	git_oid_cpy(out, &result->item->oid);
-
-	error = 0;
-
-cleanup:
-	commit_list_free(&result);
-	git_revwalk_free(walk);
-	git_vector_free(&list);
-	return error;
-}
-
-int git_merge_base(git_oid *out, git_repository *repo, const git_oid *one, const git_oid *two)
-{
-	git_revwalk *walk;
-	git_vector list;
-	commit_list *result = NULL;
-	commit_object *commit;
-	void *contents[1];
-
-	if (git_revwalk_new(&walk, repo) < 0)
-		return -1;
-
-	commit = commit_lookup(walk, two);
-	if (commit == NULL)
-		goto on_error;
-
-	/* This is just one value, so we can do it on the stack */
-	memset(&list, 0x0, sizeof(git_vector));
-	contents[0] = commit;
-	list.length = 1;
-	list.contents = contents;
-
-	commit = commit_lookup(walk, one);
-	if (commit == NULL)
-		goto on_error;
-
-	if (merge_bases_many(&result, walk, commit, &list) < 0)
-		goto on_error;
-
-	if (!result) {
-		git_revwalk_free(walk);
-		giterr_clear();
-		return GIT_ENOTFOUND;
-	}
-
-	git_oid_cpy(out, &result->item->oid);
-	commit_list_free(&result);
-	git_revwalk_free(walk);
-
-	return 0;
-
-on_error:
-	git_revwalk_free(walk);
-	return -1;
-}
-
-static void mark_uninteresting(commit_object *commit)
+static void mark_uninteresting(git_commit_list_node *commit)
 {
 	unsigned short i;
 	assert(commit);
@@ -481,7 +55,7 @@ static void mark_uninteresting(commit_object *commit)
 			mark_uninteresting(commit->parents[i]);
 }
 
-static int process_commit(git_revwalk *walk, commit_object *commit, int hide)
+static int process_commit(git_revwalk *walk, git_commit_list_node *commit, int hide)
 {
 	int error;
 
@@ -493,13 +67,13 @@ static int process_commit(git_revwalk *walk, commit_object *commit, int hide)
 
 	commit->seen = 1;
 
-	if ((error = commit_parse(walk, commit)) < 0)
+	if ((error = git_commit_list_parse(walk, commit)) < 0)
 		return error;
 
 	return walk->enqueue(walk, commit);
 }
 
-static int process_commit_parents(git_revwalk *walk, commit_object *commit)
+static int process_commit_parents(git_revwalk *walk, git_commit_list_node *commit)
 {
 	unsigned short i;
 	int error = 0;
@@ -514,7 +88,7 @@ static int push_commit(git_revwalk *walk, const git_oid *oid, int uninteresting)
 {
 	git_object *obj;
 	git_otype type;
-	commit_object *commit;
+	git_commit_list_node *commit;
 
 	if (git_object_lookup(&obj, walk->repo, oid, GIT_OBJ_ANY) < 0)
 		return -1;
@@ -659,20 +233,20 @@ int git_revwalk_hide_ref(git_revwalk *walk, const char *refname)
 	return push_ref(walk, refname, 1);
 }
 
-static int revwalk_enqueue_timesort(git_revwalk *walk, commit_object *commit)
+static int revwalk_enqueue_timesort(git_revwalk *walk, git_commit_list_node *commit)
 {
 	return git_pqueue_insert(&walk->iterator_time, commit);
 }
 
-static int revwalk_enqueue_unsorted(git_revwalk *walk, commit_object *commit)
+static int revwalk_enqueue_unsorted(git_revwalk *walk, git_commit_list_node *commit)
 {
-	return commit_list_insert(commit, &walk->iterator_rand) ? 0 : -1;
+	return git_commit_list_insert(commit, &walk->iterator_rand) ? 0 : -1;
 }
 
-static int revwalk_next_timesort(commit_object **object_out, git_revwalk *walk)
+static int revwalk_next_timesort(git_commit_list_node **object_out, git_revwalk *walk)
 {
 	int error;
-	commit_object *next;
+	git_commit_list_node *next;
 
 	while ((next = git_pqueue_pop(&walk->iterator_time)) != NULL) {
 		if ((error = process_commit_parents(walk, next)) < 0)
@@ -688,12 +262,12 @@ static int revwalk_next_timesort(commit_object **object_out, git_revwalk *walk)
 	return GIT_ITEROVER;
 }
 
-static int revwalk_next_unsorted(commit_object **object_out, git_revwalk *walk)
+static int revwalk_next_unsorted(git_commit_list_node **object_out, git_revwalk *walk)
 {
 	int error;
-	commit_object *next;
+	git_commit_list_node *next;
 
-	while ((next = commit_list_pop(&walk->iterator_rand)) != NULL) {
+	while ((next = git_commit_list_pop(&walk->iterator_rand)) != NULL) {
 		if ((error = process_commit_parents(walk, next)) < 0)
 			return error;
 
@@ -707,13 +281,13 @@ static int revwalk_next_unsorted(commit_object **object_out, git_revwalk *walk)
 	return GIT_ITEROVER;
 }
 
-static int revwalk_next_toposort(commit_object **object_out, git_revwalk *walk)
+static int revwalk_next_toposort(git_commit_list_node **object_out, git_revwalk *walk)
 {
-	commit_object *next;
+	git_commit_list_node *next;
 	unsigned short i;
 
 	for (;;) {
-		next = commit_list_pop(&walk->iterator_topo);
+		next = git_commit_list_pop(&walk->iterator_topo);
 		if (next == NULL) {
 			giterr_clear();
 			return GIT_ITEROVER;
@@ -725,11 +299,11 @@ static int revwalk_next_toposort(commit_object **object_out, git_revwalk *walk)
 		}
 
 		for (i = 0; i < next->out_degree; ++i) {
-			commit_object *parent = next->parents[i];
+			git_commit_list_node *parent = next->parents[i];
 
 			if (--parent->in_degree == 0 && parent->topo_delay) {
 				parent->topo_delay = 0;
-				if (commit_list_insert(parent, &walk->iterator_topo) == NULL)
+				if (git_commit_list_insert(parent, &walk->iterator_topo) == NULL)
 					return -1;
 			}
 		}
@@ -739,9 +313,9 @@ static int revwalk_next_toposort(commit_object **object_out, git_revwalk *walk)
 	}
 }
 
-static int revwalk_next_reverse(commit_object **object_out, git_revwalk *walk)
+static int revwalk_next_reverse(git_commit_list_node **object_out, git_revwalk *walk)
 {
-	*object_out = commit_list_pop(&walk->iterator_reverse);
+	*object_out = git_commit_list_pop(&walk->iterator_reverse);
 	return *object_out ? 0 : GIT_ITEROVER;
 }
 
@@ -750,8 +324,8 @@ static int prepare_walk(git_revwalk *walk)
 {
 	int error;
 	unsigned int i;
-	commit_object *next, *two;
-	commit_list *bases = NULL;
+	git_commit_list_node *next, *two;
+	git_commit_list *bases = NULL;
 
 	/*
 	 * If walk->one is NULL, there were no positive references,
@@ -763,10 +337,10 @@ static int prepare_walk(git_revwalk *walk)
 	}
 
 	/* first figure out what the merge bases are */
-	if (merge_bases_many(&bases, walk, walk->one, &walk->twos) < 0)
+	if (git_merge__bases_many(&bases, walk, walk->one, &walk->twos) < 0)
 		return -1;
 
-	commit_list_free(&bases);
+	git_commit_list_free(&bases);
 	if (process_commit(walk, walk->one, walk->one->uninteresting) < 0)
 		return -1;
 
@@ -780,11 +354,11 @@ static int prepare_walk(git_revwalk *walk)
 
 		while ((error = walk->get_next(&next, walk)) == 0) {
 			for (i = 0; i < next->out_degree; ++i) {
-				commit_object *parent = next->parents[i];
+				git_commit_list_node *parent = next->parents[i];
 				parent->in_degree++;
 			}
 
-			if (commit_list_insert(next, &walk->iterator_topo) == NULL)
+			if (git_commit_list_insert(next, &walk->iterator_topo) == NULL)
 				return -1;
 		}
 
@@ -797,7 +371,7 @@ static int prepare_walk(git_revwalk *walk)
 	if (walk->sorting & GIT_SORT_REVERSE) {
 
 		while ((error = walk->get_next(&next, walk)) == 0)
-			if (commit_list_insert(next, &walk->iterator_reverse) == NULL)
+			if (git_commit_list_insert(next, &walk->iterator_reverse) == NULL)
 				return -1;
 
 		if (error != GIT_ITEROVER)
@@ -811,9 +385,6 @@ static int prepare_walk(git_revwalk *walk)
 }
 
 
-
-
-
 int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)
 {
 	git_revwalk *walk;
@@ -826,7 +397,7 @@ int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)
 	walk->commits = git_oidmap_alloc();
 	GITERR_CHECK_ALLOC(walk->commits);
 
-	if (git_pqueue_init(&walk->iterator_time, 8, commit_time_cmp) < 0 ||
+	if (git_pqueue_init(&walk->iterator_time, 8, git_commit_list_time_cmp) < 0 ||
 		git_vector_init(&walk->twos, 4, NULL) < 0 ||
 		git_pool_init(&walk->commit_pool, 1,
 			git_pool__suggest_items_per_page(COMMIT_ALLOC) * COMMIT_ALLOC) < 0)
@@ -888,7 +459,7 @@ void git_revwalk_sorting(git_revwalk *walk, unsigned int sort_mode)
 int git_revwalk_next(git_oid *oid, git_revwalk *walk)
 {
 	int error;
-	commit_object *next;
+	git_commit_list_node *next;
 
 	assert(walk && oid);
 
@@ -913,7 +484,7 @@ int git_revwalk_next(git_oid *oid, git_revwalk *walk)
 
 void git_revwalk_reset(git_revwalk *walk)
 {
-	commit_object *commit;
+	git_commit_list_node *commit;
 
 	assert(walk);
 
@@ -925,9 +496,9 @@ void git_revwalk_reset(git_revwalk *walk)
 		});
 
 	git_pqueue_clear(&walk->iterator_time);
-	commit_list_free(&walk->iterator_topo);
-	commit_list_free(&walk->iterator_rand);
-	commit_list_free(&walk->iterator_reverse);
+	git_commit_list_free(&walk->iterator_topo);
+	git_commit_list_free(&walk->iterator_rand);
+	git_commit_list_free(&walk->iterator_reverse);
 	walk->walking = 0;
 
 	walk->one = NULL;
diff --git a/src/revwalk.h b/src/revwalk.h
new file mode 100644
index 000000000..2d482cfcc
--- /dev/null
+++ b/src/revwalk.h
@@ -0,0 +1,44 @@
+/*
+ * Copyright (C) 2009-2012 the libgit2 contributors
+ *
+ * This file is part of libgit2, distributed under the GNU GPL v2 with
+ * a Linking Exception. For full terms see the included COPYING file.
+ */
+#ifndef INCLUDE_revwalk_h__
+#define INCLUDE_revwalk_h__
+
+#include "git2/revwalk.h"
+#include "oidmap.h"
+#include "commit_list.h"
+#include "pqueue.h"
+#include "pool.h"
+#include "vector.h"
+
+GIT__USE_OIDMAP;
+
+struct git_revwalk {
+	git_repository *repo;
+	git_odb *odb;
+
+	git_oidmap *commits;
+	git_pool commit_pool;
+
+	git_commit_list *iterator_topo;
+	git_commit_list *iterator_rand;
+	git_commit_list *iterator_reverse;
+	git_pqueue iterator_time;
+
+	int (*get_next)(git_commit_list_node **, git_revwalk *);
+	int (*enqueue)(git_revwalk *, git_commit_list_node *);
+
+	unsigned walking:1;
+	unsigned int sorting;
+
+	/* merge base calculation */
+	git_commit_list_node *one;
+	git_vector twos;
+};
+
+git_commit_list_node *commit_lookup(git_revwalk *walk, const git_oid *oid);
+
+#endif