Merge upstream/development

Signed-off-by: Carlos Martín Nieto <cmn@elego.de>

1 files changed, 392 insertions, 276 deletions

diff --git a/src/revwalk.c b/src/revwalk.c
index a1cd0ebb7..73bb060f5 100644
--- a/src/revwalk.c
+++ b/src/revwalk.c
@@ -25,437 +25,553 @@
 
 #include "common.h"
 #include "commit.h"
-#include "revwalk.h"
+#include "odb.h"
 #include "hashtable.h"
+#include "pqueue.h"
 
-uint32_t git_revwalk__commit_hash(const void *key, int hash_id)
-{
-	uint32_t r;
-	git_commit *commit;
+#include "git2/revwalk.h"
 
-	commit = (git_commit *)key;
-	memcpy(&r, commit->object.id.id + (hash_id * sizeof(uint32_t)), sizeof(r));
-	return r;
-}
+typedef struct commit_object {
+	git_oid oid;
+	uint32_t time;
+	unsigned int seen:1,
+			 uninteresting:1,
+			 topo_delay:1,
+			 parsed:1;
+
+	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;
 
-int git_revwalk__commit_keycmp(const void *key_a, const void *key_b)
+struct git_revwalk {
+	git_repository *repo;
+
+	git_hashtable *commits;
+
+	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 *);
+
+	git_vector memory_alloc;
+	size_t chunk_size;
+
+	unsigned walking:1;
+	unsigned int sorting;
+};
+
+commit_list *commit_list_insert(commit_object *item, commit_list **list_p)
 {
-	git_commit *a = (git_commit *)key_a;
-	git_commit *b = (git_commit *)key_b;
-	return git_oid_cmp(&a->object.id, &b->object.id);
+	commit_list *new_list = git__malloc(sizeof(commit_list));
+	new_list->item = item;
+	new_list->next = *list_p;
+	*list_p = new_list;
+	return new_list;
 }
 
-int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)
+void commit_list_free(commit_list **list_p)
 {
-	git_revwalk *walk;
+	commit_list *list = *list_p;
 
-	walk = git__malloc(sizeof(git_revwalk));
-	if (walk == NULL)
-		return GIT_ENOMEM;
+	while (list) {
+		commit_list *temp = list;
+		list = temp->next;
+		free(temp);
+	}
 
-	memset(walk, 0x0, sizeof(git_revwalk));
+	*list_p = NULL;
+}
 
-	walk->commits = git_hashtable_alloc(64,
-			git_revwalk__commit_hash,
-			git_revwalk__commit_keycmp);
+commit_object *commit_list_pop(commit_list **stack)
+{
+	commit_list *top = *stack;
+	commit_object *item = top ? top->item : NULL;
 
-	if (walk->commits == NULL) {
-		free(walk);
-		return GIT_ENOMEM;
+	if (top) {
+		*stack = top->next;
+		free(top);
 	}
+	return item;
+}
 
-	walk->repo = repo;
+static int commit_time_cmp(void *a, void *b)
+{
+	commit_object *commit_a = (commit_object *)a;
+	commit_object *commit_b = (commit_object *)b;
 
-	*revwalk_out = walk;
-	return GIT_SUCCESS;
+	return (commit_a->time < commit_b->time);
 }
 
-void git_revwalk_free(git_revwalk *walk)
+static uint32_t object_table_hash(const void *key, int hash_id)
 {
-	if (walk == NULL)
-		return;
+	uint32_t r;
+	git_oid *id;
 
-	git_revwalk_reset(walk);
-	git_hashtable_free(walk->commits);
-	free(walk);
+	id = (git_oid *)key;
+	memcpy(&r, id->id + (hash_id * sizeof(uint32_t)), sizeof(r));
+	return r;
 }
 
-git_repository *git_revwalk_repository(git_revwalk *walk)
+#define COMMITS_PER_CHUNK 128
+#define CHUNK_STEP 64
+#define PARENTS_PER_COMMIT ((CHUNK_STEP - sizeof(commit_object)) / sizeof(commit_object *))
+
+static int alloc_chunk(git_revwalk *walk)
 {
-	assert(walk);
-	return walk->repo;
+	void *chunk;
+
+	chunk = git__calloc(COMMITS_PER_CHUNK, CHUNK_STEP);
+	if (chunk == NULL)
+		return GIT_ENOMEM;
+
+	walk->chunk_size = 0;
+	return git_vector_insert(&walk->memory_alloc, chunk);
 }
 
-int git_revwalk_sorting(git_revwalk *walk, unsigned int sort_mode)
+static commit_object *alloc_commit(git_revwalk *walk)
 {
-	assert(walk);
+	unsigned char *chunk;
 
-	if (walk->walking)
-		return GIT_EBUSY;
+	if (walk->chunk_size == COMMITS_PER_CHUNK)
+		alloc_chunk(walk);
 
-	walk->sorting = sort_mode;
-	git_revwalk_reset(walk);
-	return GIT_SUCCESS;
+	chunk = git_vector_get(&walk->memory_alloc, walk->memory_alloc.length - 1);
+	chunk += (walk->chunk_size * CHUNK_STEP);
+	walk->chunk_size++;
+
+	return (commit_object *)chunk;
 }
 
-static git_revwalk_commit *commit_to_walkcommit(git_revwalk *walk, git_commit *commit_object)
+static commit_object **alloc_parents(commit_object *commit, size_t n_parents)
 {
-	git_revwalk_commit *commit;
+	if (n_parents <= PARENTS_PER_COMMIT)
+		return (commit_object **)((unsigned char *)commit + sizeof(commit_object));
 
-	commit = (git_revwalk_commit *)git_hashtable_lookup(walk->commits, commit_object);
+	return git__malloc(n_parents * sizeof(commit_object *));
+}
 
-	if (commit != NULL)
+
+static commit_object *commit_lookup(git_revwalk *walk, const git_oid *oid)
+{
+	commit_object *commit;
+
+	if ((commit = git_hashtable_lookup(walk->commits, oid)) != NULL)
 		return commit;
 
-	commit = git__malloc(sizeof(git_revwalk_commit));
+	commit = alloc_commit(walk);
 	if (commit == NULL)
 		return NULL;
 
-	memset(commit, 0x0, sizeof(git_revwalk_commit));
-
-	commit->commit_object = commit_object;
-	GIT_OBJECT_INCREF(walk->repo, commit_object);
+	git_oid_cpy(&commit->oid, oid);
 
-	git_hashtable_insert(walk->commits, commit_object, commit);
+	if (git_hashtable_insert(walk->commits, &commit->oid, commit) < GIT_SUCCESS) {
+		free(commit);
+		return NULL;
+	}
 
 	return commit;
 }
 
-static git_revwalk_commit *insert_commit(git_revwalk *walk, git_commit *commit_object)
+static int commit_quick_parse(git_revwalk *walk, commit_object *commit, git_rawobj *raw)
 {
-	git_revwalk_commit *commit;
-	unsigned int i;
+	const int parent_len = STRLEN("parent ") + GIT_OID_HEXSZ + 1;
 
-	assert(walk && commit_object);
+	unsigned char *buffer = raw->data;
+	unsigned char *buffer_end = buffer + raw->len;
+	unsigned char *parents_start;
 
-	if (commit_object->object.repo != walk->repo || walk->walking)
-		return NULL;
+	int i, parents = 0;
 
-	commit = commit_to_walkcommit(walk, commit_object);
-	if (commit == NULL)
-		return NULL;
+	buffer += STRLEN("tree ") + GIT_OID_HEXSZ + 1;
 
-	if (commit->seen)
-		return commit;
+	parents_start = buffer;
+	while (buffer + parent_len < buffer_end && memcmp(buffer, "parent ", STRLEN("parent ")) == 0) {
+		parents++;
+		buffer += parent_len;
+	}
 
-	commit->seen = 1;
+	commit->parents = alloc_parents(commit, parents);
+	if (commit->parents == NULL)
+		return GIT_ENOMEM;
 
-	for (i = 0; i < commit->commit_object->parents.length; ++i) {
-		git_commit *parent_object;
-		git_revwalk_commit *parent;
+	buffer = parents_start;
+	for (i = 0; i < parents; ++i) {
+		git_oid oid;
 
-		parent_object = git_vector_get(&commit->commit_object->parents, i);
+		if (git_oid_mkstr(&oid, (char *)buffer + STRLEN("parent ")) < GIT_SUCCESS)
+			return GIT_EOBJCORRUPTED;
 
-		if ((parent = commit_to_walkcommit(walk, parent_object)) == NULL)
-			return NULL;
+		commit->parents[i] = commit_lookup(walk, &oid);
+		if (commit->parents[i] == NULL)
+			return GIT_ENOMEM;
 
-		parent = insert_commit(walk, parent_object);
-		if (parent == NULL)
-			return NULL;
+		buffer += parent_len;
+	}
 
-		parent->in_degree++;
+	commit->out_degree = (unsigned short)parents;
 
-		git_revwalk_list_push_back(&commit->parents, parent);
-	}
+	if ((buffer = memchr(buffer, '\n', buffer_end - buffer)) == NULL)
+		return GIT_EOBJCORRUPTED;
 
-	if (git_revwalk_list_push_back(&walk->iterator, commit))
-		return NULL;
+	buffer = memchr(buffer, '>', buffer_end - buffer);
+	if (buffer == NULL)
+		return GIT_EOBJCORRUPTED;
 
-	return commit;
+	commit->time = strtol((char *)buffer + 2, NULL, 10);
+	if (commit->time == 0)
+		return GIT_EOBJCORRUPTED;
+
+	commit->parsed = 1;
+	return GIT_SUCCESS;
 }
 
-int git_revwalk_push(git_revwalk *walk, git_commit *commit)
+static int commit_parse(git_revwalk *walk, commit_object *commit)
 {
-	assert(walk && commit);
-	return insert_commit(walk, commit) ? GIT_SUCCESS : GIT_ENOMEM;
+	git_odb_object *obj;
+	int error;
+
+	if (commit->parsed)
+		return GIT_SUCCESS;
+
+	if ((error = git_odb_read(&obj, walk->repo->db, &commit->oid)) < GIT_SUCCESS)
+		return error;
+
+	if (obj->raw.type != GIT_OBJ_COMMIT) {
+		git_odb_object_close(obj);
+		return GIT_EOBJTYPE;
+	}
+
+	error = commit_quick_parse(walk, commit, &obj->raw);
+	git_odb_object_close(obj);
+	return error;
 }
 
-static void mark_uninteresting(git_revwalk_commit *commit)
+static void mark_uninteresting(commit_object *commit)
 {
-	git_revwalk_listnode *parent;
-
+	unsigned short i;
 	assert(commit);
 
 	commit->uninteresting = 1;
-	parent = commit->parents.head;
 
-	while (parent) {
-		mark_uninteresting(parent->walk_commit);
-		parent = parent->next;
-	}
+	for (i = 0; i < commit->out_degree; ++i)
+		if (!commit->parents[i]->uninteresting)
+			mark_uninteresting(commit->parents[i]);
 }
 
-int git_revwalk_hide(git_revwalk *walk, git_commit *commit)
+static int process_commit(git_revwalk *walk, commit_object *commit)
 {
-	git_revwalk_commit *hide;
+	int error;
 
-	assert(walk && commit);
-	
-	hide = insert_commit(walk, commit);
-	if (hide == NULL)
-		return GIT_ENOMEM;
+	if (commit->seen)
+		return GIT_SUCCESS;
 
-	mark_uninteresting(hide);
-	return GIT_SUCCESS;
+	commit->seen = 1;
+
+	if ((error = commit_parse(walk, commit)) < GIT_SUCCESS)
+			return error;
+
+	if (commit->uninteresting)
+		mark_uninteresting(commit);
+
+	return walk->enqueue(walk, commit);
 }
 
+static int process_commit_parents(git_revwalk *walk, commit_object *commit)
+{
+	unsigned short i;
+	int error = GIT_SUCCESS;
+
+	for (i = 0; i < commit->out_degree && error == GIT_SUCCESS; ++i) {
+		error = process_commit(walk, commit->parents[i]);
+	}
+
+	return error;
+}
 
-static void prepare_walk(git_revwalk *walk)
+static int push_commit(git_revwalk *walk, const git_oid *oid, int uninteresting)
 {
-	if (walk->sorting & GIT_SORT_TIME)
-		git_revwalk_list_timesort(&walk->iterator);
+	commit_object *commit;
 
-	if (walk->sorting & GIT_SORT_TOPOLOGICAL)
-		git_revwalk_list_toposort(&walk->iterator);
+	commit = commit_lookup(walk, oid);
+	if (commit == NULL)
+		return GIT_ENOTFOUND;
 
-	if (walk->sorting & GIT_SORT_REVERSE)
-		walk->next = &git_revwalk_list_pop_back;
-	else
-		walk->next = &git_revwalk_list_pop_front;
+	commit->uninteresting = uninteresting;
 
-	walk->walking = 1;
+	return process_commit(walk, commit);
 }
 
-int git_revwalk_next(git_commit **commit, git_revwalk *walk)
+int git_revwalk_push(git_revwalk *walk, const git_oid *oid)
 {
-	git_revwalk_commit *next;
+	assert(walk && oid);
+	return push_commit(walk, oid, 0);
+}
 
-	assert(walk && commit);
+int git_revwalk_hide(git_revwalk *walk, const git_oid *oid)
+{
+	assert(walk && oid);
+	return push_commit(walk, oid, 1);
+}
+
+static int revwalk_enqueue_timesort(git_revwalk *walk, commit_object *commit)
+{
+	return git_pqueue_insert(&walk->iterator_time, commit);
+}
+
+static int revwalk_enqueue_unsorted(git_revwalk *walk, commit_object *commit)
+{
+	return commit_list_insert(commit, &walk->iterator_rand) ? GIT_SUCCESS : GIT_ENOMEM;
+}
 
-	if (!walk->walking)
-		prepare_walk(walk);
+static int revwalk_next_timesort(commit_object **object_out, git_revwalk *walk)
+{
+	int error;
+	commit_object *next;
 
-	*commit = NULL;
+	while ((next = git_pqueue_pop(&walk->iterator_time)) != NULL) {
+		if ((error = process_commit_parents(walk, next)) < GIT_SUCCESS)
+			return error;
 
-	while ((next = walk->next(&walk->iterator)) != NULL) {
 		if (!next->uninteresting) {
-			*commit = next->commit_object;
-			GIT_OBJECT_INCREF(walk->repo, *commit);
+			*object_out = next;
 			return GIT_SUCCESS;
 		}
 	}
 
-	/* No commits left to iterate */
-	git_revwalk_reset(walk);
 	return GIT_EREVWALKOVER;
 }
 
-void git_revwalk_reset(git_revwalk *walk)
+static int revwalk_next_unsorted(commit_object **object_out, git_revwalk *walk)
 {
-	const void *_unused;
-	git_revwalk_commit *commit;
+	int error;
+	commit_object *next;
 
-	assert(walk);
+	while ((next = commit_list_pop(&walk->iterator_rand)) != NULL) {
+		if ((error = process_commit_parents(walk, next)) < GIT_SUCCESS)
+			return error;
 
-	GIT_HASHTABLE_FOREACH(walk->commits, _unused, commit, {
-		GIT_OBJECT_DECREF(walk->repo, commit->commit_object);
-		git_revwalk_list_clear(&commit->parents);
-		free(commit);
-	});
+		if (!next->uninteresting) {
+			*object_out = next;
+			return GIT_SUCCESS;
+		}
+	}
 
-	git_hashtable_clear(walk->commits);
-	git_revwalk_list_clear(&walk->iterator);
-	walk->walking = 0;
+	return GIT_EREVWALKOVER;
 }
 
-
-
-
-
-
-int git_revwalk_list_push_back(git_revwalk_list *list, git_revwalk_commit *commit)
+static int revwalk_next_toposort(commit_object **object_out, git_revwalk *walk)
 {
-	git_revwalk_listnode *node = NULL;
+	commit_object *next;
+	unsigned short i;
 
-	node = git__malloc(sizeof(git_revwalk_listnode));
+	for (;;) {
+		next = commit_list_pop(&walk->iterator_topo);
+		if (next == NULL)
+			return GIT_EREVWALKOVER;
 
-	if (node == NULL)
-		return GIT_ENOMEM;
+		if (next->in_degree > 0) {
+			next->topo_delay = 1;
+			continue;
+		}
 
-	node->walk_commit = commit;
-	node->next = NULL;
-	node->prev = list->tail;
+		for (i = 0; i < next->out_degree; ++i) {
+			commit_object *parent = next->parents[i];
 
-	if (list->tail == NULL) {
-		list->head = list->tail = node;
-	} else {
-		list->tail->next = node;
-		list->tail = node;
+			if (--parent->in_degree == 0 && parent->topo_delay) {
+				parent->topo_delay = 0;
+				commit_list_insert(parent, &walk->iterator_topo);
+			}
+		}
+
+		*object_out = next;
+		return GIT_SUCCESS;
 	}
+}
 
-	list->size++;
-	return 0;
+static int revwalk_next_reverse(commit_object **object_out, git_revwalk *walk)
+{
+	*object_out = commit_list_pop(&walk->iterator_reverse);
+	return *object_out ? GIT_SUCCESS : GIT_EREVWALKOVER;
 }
 
-int git_revwalk_list_push_front(git_revwalk_list *list, git_revwalk_commit *commit)
+
+static int prepare_walk(git_revwalk *walk)
 {
-	git_revwalk_listnode *node = NULL;
+	int error;
+	commit_object *next;
 
-	node = git__malloc(sizeof(git_revwalk_listnode));
+	if (walk->sorting & GIT_SORT_TOPOLOGICAL) {
+		unsigned short i;
 
-	if (node == NULL)
-		return GIT_ENOMEM;
+		while ((error = walk->get_next(&next, walk)) == GIT_SUCCESS) {
+			for (i = 0; i < next->out_degree; ++i) {
+				commit_object *parent = next->parents[i];
+				parent->in_degree++;
+			}
 
-	node->walk_commit = commit;
-	node->next = list->head;
-	node->prev = NULL;
+			commit_list_insert(next, &walk->iterator_topo);
+		}
 
-	if (list->head == NULL) {
-		list->head = list->tail = node;
-	} else {
-		list->head->prev = node;
-		list->head = node;
+		if (error != GIT_EREVWALKOVER)
+			return error;
+
+		walk->get_next = &revwalk_next_toposort;
 	}
 
-	list->size++;
-	return 0;
-}
+	if (walk->sorting & GIT_SORT_REVERSE) {
 
+		while ((error = walk->get_next(&next, walk)) == GIT_SUCCESS)
+			commit_list_insert(next, &walk->iterator_reverse);
 
-git_revwalk_commit *git_revwalk_list_pop_back(git_revwalk_list *list)
-{
-	git_revwalk_listnode *node;
-	git_revwalk_commit *commit;
+		if (error != GIT_EREVWALKOVER)
+			return error;
 
-	if (list->tail == NULL)
-		return NULL;
+		walk->get_next = &revwalk_next_reverse;
+	}
+
+	walk->walking = 1;
+	return GIT_SUCCESS;
+}
 
-	node = list->tail;
-	list->tail = list->tail->prev;
-	if (list->tail == NULL)
-		list->head = NULL;
-	else
-		list->tail->next = NULL;
 
-	commit = node->walk_commit;
-	free(node);
 
-	list->size--;
 
-	return commit;
-}
 
-git_revwalk_commit *git_revwalk_list_pop_front(git_revwalk_list *list)
+int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)
 {
-	git_revwalk_listnode *node;
-	git_revwalk_commit *commit;
+	git_revwalk *walk;
 
-	if (list->head == NULL)
-		return NULL;
+	walk = git__malloc(sizeof(git_revwalk));
+	if (walk == NULL)
+		return GIT_ENOMEM;
 
-	node = list->head;
-	list->head = list->head->next;
-	if (list->head == NULL)
-		list->tail = NULL;
-	else
-		list->head->prev = NULL;
+	memset(walk, 0x0, sizeof(git_revwalk));
 
-	commit = node->walk_commit;
-	free(node);
+	walk->commits = git_hashtable_alloc(64,
+			object_table_hash,
+			(git_hash_keyeq_ptr)git_oid_cmp);
 
-	list->size--;
+	if (walk->commits == NULL) {
+		free(walk);
+		return GIT_ENOMEM;
+	}
 
-	return commit;
-}
+	git_pqueue_init(&walk->iterator_time, 8, commit_time_cmp);
+	git_vector_init(&walk->memory_alloc, 8, NULL);
+	alloc_chunk(walk);
 
-void git_revwalk_list_clear(git_revwalk_list *list)
-{
-	git_revwalk_listnode *node, *next_node;
+	walk->get_next = &revwalk_next_unsorted;
+	walk->enqueue = &revwalk_enqueue_unsorted;
 
-	node = list->head;
-	while (node) {
-		next_node = node->next;
-		free(node);
-		node = next_node;
-	}
+	walk->repo = repo;
 
-	list->head = list->tail = NULL;
-	list->size = 0;
+	*revwalk_out = walk;
+	return GIT_SUCCESS;
 }
 
-void git_revwalk_list_timesort(git_revwalk_list *list)
+void git_revwalk_free(git_revwalk *walk)
 {
-	git_revwalk_listnode *p, *q, *e;
-	int in_size, p_size, q_size, merge_count, i;
+	unsigned int i;
+	const void *_unused;
+	commit_object *commit;
 
-	if (list->head == NULL)
+	if (walk == NULL)
 		return;
 
-	in_size = 1;
-
-	do {
-		p = list->head;
-		list->tail = NULL;
-		merge_count = 0;
-
-		while (p != NULL) {
-			merge_count++;
-			q = p;
-			p_size = 0;
-			q_size = in_size;
-
-			for (i = 0; i < in_size && q; ++i, q = q->next)
-				p_size++;
+	git_revwalk_reset(walk);
 
-			while (p_size > 0 || (q_size > 0 && q)) {
+	/* if the parent has more than PARENTS_PER_COMMIT parents,
+	 * we had to allocate a separate array for those parents.
+	 * make sure it's being free'd */
+	GIT_HASHTABLE_FOREACH(walk->commits, _unused, commit, {
+		if (commit->out_degree > PARENTS_PER_COMMIT)
+			free(commit->parents);
+	});
 
-				if (p_size == 0)
-					e = q, q = q->next, q_size--;
+	git_hashtable_free(walk->commits);
+	git_pqueue_free(&walk->iterator_time);
 
-				else if (q_size == 0 || q == NULL ||
-						p->walk_commit->commit_object->committer->when.time >= 
-						q->walk_commit->commit_object->committer->when.time)
-					e = p, p = p->next, p_size--;
+	for (i = 0; i < walk->memory_alloc.length; ++i)
+		free(git_vector_get(&walk->memory_alloc, i));
 
-				else
-					e = q, q = q->next, q_size--;
+	git_vector_free(&walk->memory_alloc);
+	free(walk);
+}
 
-				if (list->tail != NULL)
-					list->tail->next = e;
-				else
-					list->head = e;
+git_repository *git_revwalk_repository(git_revwalk *walk)
+{
+	assert(walk);
+	return walk->repo;
+}
 
-				e->prev = list->tail;
-				list->tail = e;
-			}
+void git_revwalk_sorting(git_revwalk *walk, unsigned int sort_mode)
+{
+	assert(walk);
 
-			p = q;
-		}
+	if (walk->walking)
+		git_revwalk_reset(walk);
 
-		list->tail->next = NULL;
-		in_size *= 2;
+	walk->sorting = sort_mode;
 
-	} while (merge_count > 1);
+	if (walk->sorting & GIT_SORT_TIME) {
+		walk->get_next = &revwalk_next_timesort;
+		walk->enqueue = &revwalk_enqueue_timesort;
+	} else {
+		walk->get_next = &revwalk_next_unsorted;
+		walk->enqueue = &revwalk_enqueue_unsorted;
+	}
 }
 
-void git_revwalk_list_toposort(git_revwalk_list *list)
+int git_revwalk_next(git_oid *oid, git_revwalk *walk)
 {
-	git_revwalk_commit *commit;
-	git_revwalk_list topo;
-	memset(&topo, 0x0, sizeof(git_revwalk_list));
+	int error;
+	commit_object *next;
 
-	while ((commit = git_revwalk_list_pop_back(list)) != NULL) {
-		git_revwalk_listnode *p;
+	assert(walk && oid);
 
-		if (commit->in_degree > 0) {
-			commit->topo_delay = 1;
-			continue;
-		}
+	if (!walk->walking) {
+		if ((error = prepare_walk(walk)) < GIT_SUCCESS)
+			return error;
+	}
 
-		for (p = commit->parents.head; p != NULL; p = p->next) {
-			p->walk_commit->in_degree--;
+	error = walk->get_next(&next, walk);
+	if (error < GIT_SUCCESS) {
+		if (error == GIT_EREVWALKOVER)
+			git_revwalk_reset(walk);
+		return error;
+	}
 
-			if (p->walk_commit->in_degree == 0 && p->walk_commit->topo_delay) {
-				p->walk_commit->topo_delay = 0;
-				git_revwalk_list_push_back(list, p->walk_commit);
-			}
-		}
+	git_oid_cpy(oid, &next->oid);
+	return GIT_SUCCESS;
+}
 
-		git_revwalk_list_push_back(&topo, commit);
-	}
+void git_revwalk_reset(git_revwalk *walk)
+{
+	const void *_unused;
+	commit_object *commit;
+
+	assert(walk);
+
+	GIT_HASHTABLE_FOREACH(walk->commits, _unused, commit,
+		commit->seen = 0;
+		commit->in_degree = 0;
+		commit->topo_delay = 0;
+	);
 
-	list->head = topo.head;
-	list->tail = topo.tail;
-	list->size = topo.size;
+	git_pqueue_clear(&walk->iterator_time);
+	commit_list_free(&walk->iterator_topo);
+	commit_list_free(&walk->iterator_rand);
+	commit_list_free(&walk->iterator_reverse);
+	walk->walking = 0;
 }