Consolidate reachability logic

359 lines not on this page · raw message

41 lines not on this page · raw message

364 lines not on this page · raw message

index c74ee8869..79b032644 100644
@@ -10,6 +10,7 @@
 #include "refspec.h"
 #include "object-store.h"
 #include "argv-array.h"
+#include "commit-reach.h"
 
 static const char * const builtin_remote_usage[] = {
 	N_("git remote [-v | --verbose]"),

62 lines not on this page · raw message

index 244f48c5f..35ec9f0dd 100644
@@ -38,4 +38,6 @@ struct commit_list *reduce_heads(struct commit_list *heads);
  */
 void reduce_heads_replace(struct commit_list **heads);
 
+int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid);
+
 #endif

index 5eaf551b5..e007cb5a6 100644
@@ -14,6 +14,7 @@
 #include "argv-array.h"
 #include "packfile.h"
 #include "object-store.h"
+#include "commit-reach.h"
 
 
 #ifdef EXPAT_NEEDS_XMLPARSE_H

62 lines not on this page · raw message

index 45ecc6cef..56fb9cbb2 100644
@@ -149,7 +149,6 @@ extern struct ref **get_remote_refs(int fd_out, struct packet_reader *reader,
 				    const struct string_list *server_options);
 
 int resolve_remote_symref(struct ref *ref, struct ref *list);
-int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid);
 
 /*
  * Remove and free all but the first of any entries in the input list

index a6bc4781a..9e56f90ea 100644
@@ -1,5 +1,6 @@
 #include "cache.h"
 #include "commit.h"
+#include "commit-graph.h"
 #include "decorate.h"
 #include "prio-queue.h"
 #include "tree.h"

@@ -411,3 +412,122 @@ int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid)
 	unmark_and_free(used, TMP_MARK);
 	return found;
 }
+
+/*
+ * Mimicking the real stack, this stack lives on the heap, avoiding stack
+ * overflows.
+ *
+ * At each recursion step, the stack items points to the commits whose
+ * ancestors are to be inspected.
+ */
+struct contains_stack {
+	int nr, alloc;
+	struct contains_stack_entry {
+		struct commit *commit;
+		struct commit_list *parents;
+	} *contains_stack;
+};
+
+static int in_commit_list(const struct commit_list *want, struct commit *c)
+{
+	for (; want; want = want->next)
+		if (!oidcmp(&want->item->object.oid, &c->object.oid))
+			return 1;
+	return 0;
+}
+
+/*
+ * Test whether the candidate is contained in the list.
+ * Do not recurse to find out, though, but return -1 if inconclusive.
+ */
+static enum contains_result contains_test(struct commit *candidate,
+					  const struct commit_list *want,
+					  struct contains_cache *cache,
+					  uint32_t cutoff)
+{
+	enum contains_result *cached = contains_cache_at(cache, candidate);
+
+	/* If we already have the answer cached, return that. */
+	if (*cached)
+		return *cached;
+
+	/* or are we it? */
+	if (in_commit_list(want, candidate)) {
+		*cached = CONTAINS_YES;
+		return CONTAINS_YES;
+	}
+
+	/* Otherwise, we don't know; prepare to recurse */
+	parse_commit_or_die(candidate);
+
+	if (candidate->generation < cutoff)
+		return CONTAINS_NO;
+
+	return CONTAINS_UNKNOWN;
+}
+
+static void push_to_contains_stack(struct commit *candidate, struct contains_stack *contains_stack)
+{
+	ALLOC_GROW(contains_stack->contains_stack, contains_stack->nr + 1, contains_stack->alloc);
+	contains_stack->contains_stack[contains_stack->nr].commit = candidate;
+	contains_stack->contains_stack[contains_stack->nr++].parents = candidate->parents;
+}
+
+static enum contains_result contains_tag_algo(struct commit *candidate,
+					      const struct commit_list *want,
+					      struct contains_cache *cache)
+{
+	struct contains_stack contains_stack = { 0, 0, NULL };
+	enum contains_result result;
+	uint32_t cutoff = GENERATION_NUMBER_INFINITY;
+	const struct commit_list *p;
+
+	for (p = want; p; p = p->next) {
+		struct commit *c = p->item;
+		load_commit_graph_info(the_repository, c);
+		if (c->generation < cutoff)
+			cutoff = c->generation;
+	}
+
+	result = contains_test(candidate, want, cache, cutoff);
+	if (result != CONTAINS_UNKNOWN)
+		return result;
+
+	push_to_contains_stack(candidate, &contains_stack);
+	while (contains_stack.nr) {
+		struct contains_stack_entry *entry = &contains_stack.contains_stack[contains_stack.nr - 1];
+		struct commit *commit = entry->commit;
+		struct commit_list *parents = entry->parents;
+
+		if (!parents) {
+			*contains_cache_at(cache, commit) = CONTAINS_NO;
+			contains_stack.nr--;
+		}
+		/*
+		 * If we just popped the stack, parents->item has been marked,
+		 * therefore contains_test will return a meaningful yes/no.
+		 */
+		else switch (contains_test(parents->item, want, cache, cutoff)) {
+		case CONTAINS_YES:
+			*contains_cache_at(cache, commit) = CONTAINS_YES;
+			contains_stack.nr--;
+			break;
+		case CONTAINS_NO:
+			entry->parents = parents->next;
+			break;
+		case CONTAINS_UNKNOWN:
+			push_to_contains_stack(parents->item, &contains_stack);
+			break;
+		}
+	}
+	free(contains_stack.contains_stack);
+	return contains_test(candidate, want, cache, cutoff);
+}
+
+int commit_contains(struct ref_filter *filter, struct commit *commit,
+		    struct commit_list *list, struct contains_cache *cache)
+{
+	if (filter->with_commit_tag_algo)
+		return contains_tag_algo(commit, list, cache) == CONTAINS_YES;
+	return is_descendant_of(commit, list);
+}

index 35ec9f0dd..925cb05d7 100644
@@ -2,6 +2,8 @@
 #define __COMMIT_REACH_H__
 
 #include "commit.h"
+#include "commit-slab.h"
+#include "ref-filter.h"
 
 struct commit_list *get_merge_bases_many(struct commit *one,
 					 int n,

@@ -19,7 +21,6 @@ int is_descendant_of(struct commit *commit, struct commit_list *with_commit);
 int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit **reference);
 int in_merge_bases(struct commit *commit, struct commit *reference);
 
-
 /*
  * Takes a list of commits and returns a new list where those
  * have been removed that can be reached from other commits in

@@ -40,4 +41,19 @@ void reduce_heads_replace(struct commit_list **heads);
 
 int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid);
 
+/*
+ * Unknown has to be "0" here, because that's the default value for
+ * contains_cache slab entries that have not yet been assigned.
+ */
+enum contains_result {
+	CONTAINS_UNKNOWN = 0,
+	CONTAINS_NO,
+	CONTAINS_YES
+};
+
+define_commit_slab(contains_cache, enum contains_result);
+
+int commit_contains(struct ref_filter *filter, struct commit *commit,
+		    struct commit_list *list, struct contains_cache *cache);
+
 #endif

index 3ea578102..4a93df383 100644
@@ -171,6 +171,7 @@ Format of STDIN stream:
 #include "packfile.h"
 #include "object-store.h"
 #include "mem-pool.h"
+#include "commit-reach.h"
 
 #define PACK_ID_BITS 16
 #define MAX_PACK_ID ((1<<PACK_ID_BITS)-1)

165 lines not on this page · raw message

index 4ca052d0b..0ed470713 100644
@@ -336,17 +336,17 @@ static int got_oid(const char *hex, struct object_id *oid)
 	return 0;
 }
 
-static int reachable(struct commit *want)
+static int reachable(struct commit *from, int with_flag, int assign_flag)
 {
 	struct prio_queue work = { compare_commits_by_commit_date };
 
-	prio_queue_put(&work, want);
+	prio_queue_put(&work, from);
 	while (work.nr) {
 		struct commit_list *list;
 		struct commit *commit = prio_queue_get(&work);
 
-		if (commit->object.flags & THEY_HAVE) {
-			want->object.flags |= COMMON_KNOWN;
+		if (commit->object.flags & with_flag) {
+			from->object.flags |= assign_flag;
 			break;
 		}
 		if (!commit->object.parsed)

@@ -362,10 +362,10 @@ static int reachable(struct commit *want)
 				prio_queue_put(&work, parent);
 		}
 	}
-	want->object.flags |= REACHABLE;
-	clear_commit_marks(want, REACHABLE);
+	from->object.flags |= REACHABLE;
+	clear_commit_marks(from, REACHABLE);
 	clear_prio_queue(&work);
-	return (want->object.flags & COMMON_KNOWN);
+	return (from->object.flags & assign_flag);
 }
 
 static int ok_to_give_up(void)

@@ -390,7 +390,7 @@ static int ok_to_give_up(void)
 			want_obj.objects[i].item->flags |= COMMON_KNOWN;
 			continue;
 		}
-		if (!reachable((struct commit *)want))
+		if (!reachable((struct commit *)want, THEY_HAVE, COMMON_KNOWN))
 			return 0;
 	}
 	return 1;

index 0ed470713..e7ad7f24b 100644
@@ -368,34 +368,45 @@ static int reachable(struct commit *from, int with_flag, int assign_flag)
 	return (from->object.flags & assign_flag);
 }
 
-static int ok_to_give_up(void)
+/*
+ * Determine if every commit in 'from' can reach at least one commit
+ * that is marked with 'with_flag'. As we traverse, use 'assign_flag'
+ * as a marker for commits that are already visited.
+ */
+static int can_all_from_reach_with_flag(struct object_array *from,
+					int with_flag, int assign_flag)
 {
 	int i;
 
-	if (!have_obj.nr)
-		return 0;
-
-	for (i = 0; i < want_obj.nr; i++) {
-		struct object *want = want_obj.objects[i].item;
+	for (i = 0; i < from->nr; i++) {
+		struct object *from_one = from->objects[i].item;
 
-		if (want->flags & COMMON_KNOWN)
+		if (from_one->flags & assign_flag)
 			continue;
-		want = deref_tag(the_repository, want, "a want line", 0);
-		if (!want || want->type != OBJ_COMMIT) {
+		from_one = deref_tag(the_repository, from_one, "a from object", 0);
+		if (!from_one || from_one->type != OBJ_COMMIT) {
 			/* no way to tell if this is reachable by
 			 * looking at the ancestry chain alone, so
 			 * leave a note to ourselves not to worry about
 			 * this object anymore.
 			 */
-			want_obj.objects[i].item->flags |= COMMON_KNOWN;
+			from->objects[i].item->flags |= assign_flag;
 			continue;
 		}
-		if (!reachable((struct commit *)want, THEY_HAVE, COMMON_KNOWN))
+		if (!reachable((struct commit *)from_one, with_flag, assign_flag))
 			return 0;
 	}
 	return 1;
 }
 
+static int ok_to_give_up(void)
+{
+	if (!have_obj.nr)
+		return 0;
+
+	return can_all_from_reach_with_flag(&want_obj, THEY_HAVE, COMMON_KNOWN);
+}
+
 static int get_common_commits(void)
 {
 	struct object_id oid;

index e7ad7f24b..96298e50e 100644
@@ -336,7 +336,8 @@ static int got_oid(const char *hex, struct object_id *oid)
 	return 0;
 }
 
-static int reachable(struct commit *from, int with_flag, int assign_flag)
+static int reachable(struct commit *from, int with_flag, int assign_flag,
+		     time_t min_commit_date)
 {
 	struct prio_queue work = { compare_commits_by_commit_date };
 

@@ -354,7 +355,7 @@ static int reachable(struct commit *from, int with_flag, int assign_flag)
 		if (commit->object.flags & REACHABLE)
 			continue;
 		commit->object.flags |= REACHABLE;
-		if (commit->date < oldest_have)
+		if (commit->date < min_commit_date)
 			continue;
 		for (list = commit->parents; list; list = list->next) {
 			struct commit *parent = list->item;

@@ -371,10 +372,12 @@ static int reachable(struct commit *from, int with_flag, int assign_flag)
 /*
  * Determine if every commit in 'from' can reach at least one commit
  * that is marked with 'with_flag'. As we traverse, use 'assign_flag'
- * as a marker for commits that are already visited.
+ * as a marker for commits that are already visited. Do not walk
+ * commits with date below 'min_commit_date'.
  */
 static int can_all_from_reach_with_flag(struct object_array *from,
-					int with_flag, int assign_flag)
+					int with_flag, int assign_flag,
+					time_t min_commit_date)
 {
 	int i;
 

@@ -393,7 +396,8 @@ static int can_all_from_reach_with_flag(struct object_array *from,
 			from->objects[i].item->flags |= assign_flag;
 			continue;
 		}
-		if (!reachable((struct commit *)from_one, with_flag, assign_flag))
+		if (!reachable((struct commit *)from_one, with_flag, assign_flag,
+			       min_commit_date))
 			return 0;
 	}
 	return 1;

@@ -404,7 +408,8 @@ static int ok_to_give_up(void)
 	if (!have_obj.nr)
 		return 0;
 
-	return can_all_from_reach_with_flag(&want_obj, THEY_HAVE, COMMON_KNOWN);
+	return can_all_from_reach_with_flag(&want_obj, THEY_HAVE,
+					    COMMON_KNOWN, oldest_have);
 }
 
 static int get_common_commits(void)

index 9e56f90ea..e07ff993f 100644
@@ -9,6 +9,7 @@
 #include "commit-reach.h"
 
 /* Remember to update object flag allocation in object.h */
+#define REACHABLE       (1u<<15)
 #define PARENT1		(1u<<16)
 #define PARENT2		(1u<<17)
 #define STALE		(1u<<18)

@@ -531,3 +532,64 @@ int commit_contains(struct ref_filter *filter, struct commit *commit,
 		return contains_tag_algo(commit, list, cache) == CONTAINS_YES;
 	return is_descendant_of(commit, list);
 }
+
+int reachable(struct commit *from, int with_flag, int assign_flag,
+	      time_t min_commit_date)
+{
+	struct prio_queue work = { compare_commits_by_commit_date };
+
+	prio_queue_put(&work, from);
+	while (work.nr) {
+		struct commit_list *list;
+		struct commit *commit = prio_queue_get(&work);
+
+		if (commit->object.flags & with_flag) {
+			from->object.flags |= assign_flag;
+			break;
+		}
+		if (!commit->object.parsed)
+			parse_object(the_repository, &commit->object.oid);
+		if (commit->object.flags & REACHABLE)
+			continue;
+		commit->object.flags |= REACHABLE;
+		if (commit->date < min_commit_date)
+			continue;
+		for (list = commit->parents; list; list = list->next) {
+			struct commit *parent = list->item;
+			if (!(parent->object.flags & REACHABLE))
+				prio_queue_put(&work, parent);
+		}
+	}
+	from->object.flags |= REACHABLE;
+	clear_commit_marks(from, REACHABLE);
+	clear_prio_queue(&work);
+	return (from->object.flags & assign_flag);
+}
+
+int can_all_from_reach_with_flag(struct object_array *from,
+				 int with_flag, int assign_flag,
+				 time_t min_commit_date)
+{
+	int i;
+
+	for (i = 0; i < from->nr; i++) {
+		struct object *from_one = from->objects[i].item;
+
+		if (from_one->flags & assign_flag)
+			continue;
+		from_one = deref_tag(the_repository, from_one, "a from object", 0);
+		if (!from_one || from_one->type != OBJ_COMMIT) {
+			/* no way to tell if this is reachable by
+			 * looking at the ancestry chain alone, so
+			 * leave a note to ourselves not to worry about
+			 * this object anymore.
+			 */
+			from->objects[i].item->flags |= assign_flag;
+			continue;
+		}
+		if (!reachable((struct commit *)from_one, with_flag, assign_flag,
+			       min_commit_date))
+			return 0;
+	}
+	return 1;
+}

index 925cb05d7..ce3b963e6 100644
@@ -56,4 +56,17 @@ define_commit_slab(contains_cache, enum contains_result);
 int commit_contains(struct ref_filter *filter, struct commit *commit,
 		    struct commit_list *list, struct contains_cache *cache);
 
+int reachable(struct commit *from, int with_flag, int assign_flag,
+	      time_t min_commit_date);
+
+/*
+ * Determine if every commit in 'from' can reach at least one commit
+ * that is marked with 'with_flag'. As we traverse, use 'assign_flag'
+ * as a marker for commits that are already visited. Do not walk
+ * commits with date below 'min_commit_date'.
+ */
+int can_all_from_reach_with_flag(struct object_array *from,
+				 int with_flag, int assign_flag,
+				 time_t min_commit_date);
+
 #endif

87 lines not on this page · raw message

62 lines not on this page · raw message

index dafc91c24..582d02adf 100644
@@ -26,6 +26,7 @@ static struct test_cmd cmds[] = {
 	{ "online-cpus", cmd__online_cpus },
 	{ "path-utils", cmd__path_utils },
 	{ "prio-queue", cmd__prio_queue },
+	{ "reach", cmd__reach },
 	{ "read-cache", cmd__read_cache },
 	{ "ref-store", cmd__ref_store },
 	{ "regex", cmd__regex },

index 80cbcf085..a7e53c420 100644
@@ -20,6 +20,7 @@ int cmd__mktemp(int argc, const char **argv);
 int cmd__online_cpus(int argc, const char **argv);
 int cmd__path_utils(int argc, const char **argv);
 int cmd__prio_queue(int argc, const char **argv);
+int cmd__reach(int argc, const char **argv);
 int cmd__read_cache(int argc, const char **argv);
 int cmd__ref_store(int argc, const char **argv);
 int cmd__regex(int argc, const char **argv);

index 8cc570f3b..29104d41a 100644
@@ -8,6 +8,7 @@
 int cmd__reach(int ac, const char **av)
 {
 	struct object_id oid_A, oid_B;
+	struct commit *A, *B;
 	struct strbuf buf = STRBUF_INIT;
 	struct repository *r = the_repository;
 

@@ -16,6 +17,7 @@ int cmd__reach(int ac, const char **av)
 	if (ac < 2)
 		exit(1);
 
+	A = B = NULL;
 
 	while (strbuf_getline(&buf, stdin) != EOF) {
 		struct object_id oid;

@@ -43,10 +45,12 @@ int cmd__reach(int ac, const char **av)
 		switch (buf.buf[0]) {
 			case 'A':
 				oidcpy(&oid_A, &oid);
+				A = c;
 				break;
 
 			case 'B':
 				oidcpy(&oid_B, &oid);
+				B = c;
 				break;
 
 			default:

@@ -57,6 +61,8 @@ int cmd__reach(int ac, const char **av)
 
 	if (!strcmp(av[1], "ref_newer"))
 		printf("%s:%d\n", av[1], ref_newer(&oid_A, &oid_B));
+	else if (!strcmp(av[1], "in_merge_bases"))
+		printf("%s(A,B):%d\n", av[1], in_merge_bases(A, B));
 
 	exit(0);
 }

index 29104d41a..149e8f32c 100644
@@ -9,6 +9,7 @@ int cmd__reach(int ac, const char **av)
 {
 	struct object_id oid_A, oid_B;
 	struct commit *A, *B;
+	struct commit_list *X;
 	struct strbuf buf = STRBUF_INIT;
 	struct repository *r = the_repository;
 

@@ -18,6 +19,7 @@ int cmd__reach(int ac, const char **av)
 		exit(1);
 
 	A = B = NULL;
+	X = NULL;
 
 	while (strbuf_getline(&buf, stdin) != EOF) {
 		struct object_id oid;

@@ -53,6 +55,10 @@ int cmd__reach(int ac, const char **av)
 				B = c;
 				break;
 
+			case 'X':
+				commit_list_insert(c, &X);
+				break;
+
 			default:
 				die("unexpected start of line: %c", buf.buf[0]);
 		}

@@ -63,6 +69,8 @@ int cmd__reach(int ac, const char **av)
 		printf("%s:%d\n", av[1], ref_newer(&oid_A, &oid_B));
 	else if (!strcmp(av[1], "in_merge_bases"))
 		printf("%s(A,B):%d\n", av[1], in_merge_bases(A, B));
+	else if (!strcmp(av[1], "is_descendant_of"))
+		printf("%s(A,X):%d\n", av[1], is_descendant_of(A, X));
 
 	exit(0);
 }

index 149e8f32c..97c726040 100644
@@ -10,6 +10,8 @@ int cmd__reach(int ac, const char **av)
 	struct object_id oid_A, oid_B;
 	struct commit *A, *B;
 	struct commit_list *X;
+	struct commit **X_array;
+	int X_nr, X_alloc;
 	struct strbuf buf = STRBUF_INIT;
 	struct repository *r = the_repository;
 

@@ -20,6 +22,9 @@ int cmd__reach(int ac, const char **av)
 
 	A = B = NULL;
 	X = NULL;
+	X_nr = 0;
+	X_alloc = 16;
+	ALLOC_ARRAY(X_array, X_alloc);
 
 	while (strbuf_getline(&buf, stdin) != EOF) {
 		struct object_id oid;

@@ -57,6 +62,8 @@ int cmd__reach(int ac, const char **av)
 
 			case 'X':
 				commit_list_insert(c, &X);
+				ALLOC_GROW(X_array, X_nr + 1, X_alloc);
+				X_array[X_nr++] = c;
 				break;
 
 			default:

@@ -71,6 +78,14 @@ int cmd__reach(int ac, const char **av)
 		printf("%s(A,B):%d\n", av[1], in_merge_bases(A, B));
 	else if (!strcmp(av[1], "is_descendant_of"))
 		printf("%s(A,X):%d\n", av[1], is_descendant_of(A, X));
+	else if (!strcmp(av[1], "get_merge_bases_many")) {
+		struct commit_list *list = get_merge_bases_many(A, X_nr, X_array);
+		printf("%s(A,X):\n", av[1]);
+		while (list) {
+			printf("%s\n", oid_to_hex(&list->item->object.oid));
+			list = list->next;
+		}
+	}
 
 	exit(0);
 }

index 97c726040..73cb55208 100644
@@ -85,6 +85,13 @@ int cmd__reach(int ac, const char **av)
 			printf("%s\n", oid_to_hex(&list->item->object.oid));
 			list = list->next;
 		}
+	} else if (!strcmp(av[1], "reduce_heads")) {
+		struct commit_list *list = reduce_heads(X);
+		printf("%s(X):\n", av[1]);
+		while (list) {
+			printf("%s\n", oid_to_hex(&list->item->object.oid));
+			list = list->next;
+		}
 	}
 
 	exit(0);

index e07ff993f..c5e89a2de 100644
@@ -593,3 +593,50 @@ int can_all_from_reach_with_flag(struct object_array *from,
 	}
 	return 1;
 }
+
+int can_all_from_reach(struct commit_list *from, struct commit_list *to,
+		       int cutoff_by_min_date)
+{
+	struct object_array from_objs = OBJECT_ARRAY_INIT;
+	time_t min_commit_date = cutoff_by_min_date ? from->item->date : 0;
+	struct commit_list *from_iter = from, *to_iter = to;
+	int result;
+
+	while (from_iter) {
+		add_object_array(&from_iter->item->object, NULL, &from_objs);
+
+		if (!parse_commit(from_iter->item)) {
+			if (from_iter->item->date < min_commit_date)
+				min_commit_date = from_iter->item->date;
+		}
+
+		from_iter = from_iter->next;
+	}
+
+	while (to_iter) {
+		if (!parse_commit(to_iter->item)) {
+			if (to_iter->item->date < min_commit_date)
+				min_commit_date = to_iter->item->date;
+		}
+
+		to_iter->item->object.flags |= PARENT2;
+
+		to_iter = to_iter->next;
+	}
+
+	result = can_all_from_reach_with_flag(&from_objs, PARENT2, PARENT1,
+					      min_commit_date);
+
+	while (from) {
+		clear_commit_marks(from->item, PARENT1);
+		from = from->next;
+	}
+
+	while (to) {
+		clear_commit_marks(to->item, PARENT2);
+		to = to->next;
+	}
+
+	object_array_clear(&from_objs);
+	return result;
+}

index ce3b963e6..58de0df56 100644
@@ -68,5 +68,7 @@ int reachable(struct commit *from, int with_flag, int assign_flag,
 int can_all_from_reach_with_flag(struct object_array *from,
 				 int with_flag, int assign_flag,
 				 time_t min_commit_date);
+int can_all_from_reach(struct commit_list *from, struct commit_list *to,
+		       int commit_date_cutoff);
 
 #endif

index 73cb55208..dc9710099 100644
@@ -9,7 +9,7 @@ int cmd__reach(int ac, const char **av)
 {
 	struct object_id oid_A, oid_B;
 	struct commit *A, *B;
-	struct commit_list *X;
+	struct commit_list *X, *Y;
 	struct commit **X_array;
 	int X_nr, X_alloc;
 	struct strbuf buf = STRBUF_INIT;

@@ -21,7 +21,7 @@ int cmd__reach(int ac, const char **av)
 		exit(1);
 
 	A = B = NULL;
-	X = NULL;
+	X = Y = NULL;
 	X_nr = 0;
 	X_alloc = 16;
 	ALLOC_ARRAY(X_array, X_alloc);

@@ -66,6 +66,10 @@ int cmd__reach(int ac, const char **av)
 				X_array[X_nr++] = c;
 				break;
 
+			case 'Y':
+				commit_list_insert(c, &Y);
+				break;
+
 			default:
 				die("unexpected start of line: %c", buf.buf[0]);
 		}

@@ -92,6 +96,8 @@ int cmd__reach(int ac, const char **av)
 			printf("%s\n", oid_to_hex(&list->item->object.oid));
 			list = list->next;
 		}
+	} else if (!strcmp(av[1], "can_all_from_reach")) {
+		printf("%s(X,Y):%d\n", av[1], can_all_from_reach(X, Y, 1));
 	}
 
 	exit(0);

index c5e89a2de..c58e50fbb 100644
@@ -365,20 +365,11 @@ void reduce_heads_replace(struct commit_list **heads)
 	*heads = result;
 }
 
-static void unmark_and_free(struct commit_list *list, unsigned int mark)
-{
-	while (list) {
-		struct commit *commit = pop_commit(&list);
-		commit->object.flags &= ~mark;
-	}
-}
-
 int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid)
 {
 	struct object *o;
 	struct commit *old_commit, *new_commit;
-	struct commit_list *list, *used;
-	int found = 0;
+	struct commit_list *old_commit_list = NULL;
 
 	/*
 	 * Both new_commit and old_commit must be commit-ish and new_commit is descendant of

@@ -399,19 +390,8 @@ int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid)
 	if (parse_commit(new_commit) < 0)
 		return 0;
 
-	used = list = NULL;
-	commit_list_insert(new_commit, &list);
-	while (list) {
-		new_commit = pop_most_recent_commit(&list, TMP_MARK);
-		commit_list_insert(new_commit, &used);
-		if (new_commit == old_commit) {
-			found = 1;
-			break;
-		}
-	}
-	unmark_and_free(list, TMP_MARK);
-	unmark_and_free(used, TMP_MARK);
-	return found;
+	commit_list_insert(old_commit, &old_commit_list);
+	return is_descendant_of(new_commit, old_commit_list);
 }
 
 /*

index c58e50fbb..ac132c8e4 100644
@@ -513,65 +513,88 @@ int commit_contains(struct ref_filter *filter, struct commit *commit,
 	return is_descendant_of(commit, list);
 }
 
-int reachable(struct commit *from, int with_flag, int assign_flag,
-	      time_t min_commit_date)
+static int compare_commits_by_gen(const void *_a, const void *_b)
 {
-	struct prio_queue work = { compare_commits_by_commit_date };
+	const struct commit *a = (const struct commit *)_a;
+	const struct commit *b = (const struct commit *)_b;
 
-	prio_queue_put(&work, from);
-	while (work.nr) {
-		struct commit_list *list;
-		struct commit *commit = prio_queue_get(&work);
-
-		if (commit->object.flags & with_flag) {
-			from->object.flags |= assign_flag;
-			break;
-		}
-		if (!commit->object.parsed)
-			parse_object(the_repository, &commit->object.oid);
-		if (commit->object.flags & REACHABLE)
-			continue;
-		commit->object.flags |= REACHABLE;
-		if (commit->date < min_commit_date)
-			continue;
-		for (list = commit->parents; list; list = list->next) {
-			struct commit *parent = list->item;
-			if (!(parent->object.flags & REACHABLE))
-				prio_queue_put(&work, parent);
-		}
-	}
-	from->object.flags |= REACHABLE;
-	clear_commit_marks(from, REACHABLE);
-	clear_prio_queue(&work);
-	return (from->object.flags & assign_flag);
+	if (a->generation < b->generation)
+		return -1;
+	if (a->generation > b->generation)
+		return 1;
+	return 0;
 }
 
 int can_all_from_reach_with_flag(struct object_array *from,
 				 int with_flag, int assign_flag,
-				 time_t min_commit_date)
+				 time_t min_commit_date,
+				 uint32_t min_generation)
 {
+	struct commit **list = NULL;
 	int i;
+	int result = 1;
 
+	ALLOC_ARRAY(list, from->nr);
 	for (i = 0; i < from->nr; i++) {
-		struct object *from_one = from->objects[i].item;
+		list[i] = (struct commit *)from->objects[i].item;
 
-		if (from_one->flags & assign_flag)
-			continue;
-		from_one = deref_tag(the_repository, from_one, "a from object", 0);
-		if (!from_one || from_one->type != OBJ_COMMIT) {
-			/* no way to tell if this is reachable by
-			 * looking at the ancestry chain alone, so
-			 * leave a note to ourselves not to worry about
-			 * this object anymore.
-			 */
-			from->objects[i].item->flags |= assign_flag;
-			continue;
-		}
-		if (!reachable((struct commit *)from_one, with_flag, assign_flag,
-			       min_commit_date))
+		parse_commit(list[i]);
+
+		if (list[i]->generation < min_generation)
 			return 0;
 	}
-	return 1;
+
+	QSORT(list, from->nr, compare_commits_by_gen);
+
+	for (i = 0; i < from->nr; i++) {
+		/* DFS from list[i] */
+		struct commit_list *stack = NULL;
+
+		list[i]->object.flags |= assign_flag;
+		commit_list_insert(list[i], &stack);
+
+		while (stack) {
+			struct commit_list *parent;
+
+			if (stack->item->object.flags & with_flag) {
+				pop_commit(&stack);
+				continue;
+			}
+
+			for (parent = stack->item->parents; parent; parent = parent->next) {
+				if (parent->item->object.flags & (with_flag | RESULT))
+					stack->item->object.flags |= RESULT;
+
+				if (!(parent->item->object.flags & assign_flag)) {
+					parent->item->object.flags |= assign_flag;
+
+					parse_commit(parent->item);
+
+					if (parent->item->date < min_commit_date ||
+					    parent->item->generation < min_generation)
+						continue;
+
+					commit_list_insert(parent->item, &stack);
+					break;
+				}
+			}
+
+			if (!parent)
+				pop_commit(&stack);
+		}
+
+		if (!(list[i]->object.flags & (with_flag | RESULT))) {
+			result = 0;
+			goto cleanup;
+		}
+	}
+
+cleanup:
+	for (i = 0; i < from->nr; i++) {
+		clear_commit_marks(list[i], RESULT);
+		clear_commit_marks(list[i], assign_flag);
+	}
+	return result;
 }
 
 int can_all_from_reach(struct commit_list *from, struct commit_list *to,

@@ -581,6 +604,7 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,
 	time_t min_commit_date = cutoff_by_min_date ? from->item->date : 0;
 	struct commit_list *from_iter = from, *to_iter = to;
 	int result;
+	uint32_t min_generation = GENERATION_NUMBER_INFINITY;
 
 	while (from_iter) {
 		add_object_array(&from_iter->item->object, NULL, &from_objs);

@@ -588,6 +612,9 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,
 		if (!parse_commit(from_iter->item)) {
 			if (from_iter->item->date < min_commit_date)
 				min_commit_date = from_iter->item->date;
+
+			if (from_iter->item->generation < min_generation)
+				min_generation = from_iter->item->generation;
 		}
 
 		from_iter = from_iter->next;

@@ -597,6 +624,9 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,
 		if (!parse_commit(to_iter->item)) {
 			if (to_iter->item->date < min_commit_date)
 				min_commit_date = to_iter->item->date;
+
+			if (to_iter->item->generation < min_generation)
+				min_generation = to_iter->item->generation;
 		}
 
 		to_iter->item->object.flags |= PARENT2;

@@ -605,7 +635,7 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,
 	}
 
 	result = can_all_from_reach_with_flag(&from_objs, PARENT2, PARENT1,
-					      min_commit_date);
+					      min_commit_date, min_generation);
 
 	while (from) {
 		clear_commit_marks(from->item, PARENT1);

index 58de0df56..482d9eb5d 100644
@@ -63,11 +63,13 @@ int reachable(struct commit *from, int with_flag, int assign_flag,
  * Determine if every commit in 'from' can reach at least one commit
  * that is marked with 'with_flag'. As we traverse, use 'assign_flag'
  * as a marker for commits that are already visited. Do not walk
- * commits with date below 'min_commit_date'.
+ * commits with date below 'min_commit_date' or generation below
+ * 'min_generation'.
  */
 int can_all_from_reach_with_flag(struct object_array *from,
 				 int with_flag, int assign_flag,
-				 time_t min_commit_date);
+				 time_t min_commit_date,
+				 uint32_t min_generation);
 int can_all_from_reach(struct commit_list *from, struct commit_list *to,
 		       int commit_date_cutoff);
 

index 11c426685..1e498f118 100644
@@ -338,11 +338,14 @@ static int got_oid(const char *hex, struct object_id *oid)
 
 static int ok_to_give_up(void)
 {
+	uint32_t min_generation = GENERATION_NUMBER_ZERO;
+
 	if (!have_obj.nr)
 		return 0;
 
 	return can_all_from_reach_with_flag(&want_obj, THEY_HAVE,
-					    COMMON_KNOWN, oldest_have);
+					    COMMON_KNOWN, oldest_have,
+					    min_generation);
 }
 
 static int get_common_commits(void)

index e8b17cf7e1..06be3a3c15 100644
@@ -192,16 +192,11 @@ struct commit_dist {
 	int distance;
 };
 
-static int compare_commit_dist(const void *a_, const void *b_)
-{
-	struct commit_dist *a, *b;
-
-	a = (struct commit_dist *)a_;
-	b = (struct commit_dist *)b_;
+DEFINE_SORT(sort_by_commit_dist, struct commit_dist, a, b, {
 	if (a->distance != b->distance)
 		return b->distance - a->distance; /* desc sort */
 	return oidcmp(&a->commit->object.oid, &b->commit->object.oid);
-}
+})
 
 static struct commit_list *best_bisection_sorted(struct commit_list *list, int nr)
 {

@@ -223,7 +218,7 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n
 		array[cnt].distance = distance;
 		cnt++;
 	}
-	QSORT(array, cnt, compare_commit_dist);
+	sort_by_commit_dist(array, cnt);
 	for (p = list, i = 0; i < cnt; i++) {
 		struct object *obj = &(array[i].commit->object);
 

index 7f4519ec3b..a2202414e0 100644
@@ -550,12 +550,7 @@ static void write_graph_chunk_large_edges(struct hashfile *f,
 	}
 }
 
-static int commit_compare(const void *_a, const void *_b)
-{
-	const struct object_id *a = (const struct object_id *)_a;
-	const struct object_id *b = (const struct object_id *)_b;
-	return oidcmp(a, b);
-}
+DEFINE_SORT(sort_oids, struct object_id, a, b, return oidcmp(a, b))
 
 struct packed_commit_list {
 	struct commit **list;

@@ -780,7 +775,7 @@ void write_commit_graph(const char *obj_dir,
 
 	close_reachable(&oids);
 
-	QSORT(oids.list, oids.nr, commit_compare);
+	sort_oids(oids.list, oids.nr);
 
 	count_distinct = 1;
 	for (i = 1; i < oids.nr; i++) {

index 2f5e592d16..3aef47c3dd 100644
@@ -527,17 +527,15 @@ int commit_contains(struct ref_filter *filter, struct commit *commit,
 	return is_descendant_of(commit, list);
 }
 
-static int compare_commits_by_gen(const void *_a, const void *_b)
-{
-	const struct commit *a = *(const struct commit * const *)_a;
-	const struct commit *b = *(const struct commit * const *)_b;
-
+DEFINE_SORT(sort_commits_by_gen, struct commit *, ap, bp, {
+	const struct commit *a = *ap;
+	const struct commit *b = *bp;
 	if (a->generation < b->generation)
 		return -1;
 	if (a->generation > b->generation)
 		return 1;
 	return 0;
-}
+})
 
 int can_all_from_reach_with_flag(struct object_array *from,
 				 unsigned int with_flag,

@@ -580,7 +578,7 @@ int can_all_from_reach_with_flag(struct object_array *from,
 		nr_commits++;
 	}
 
-	QSORT(list, nr_commits, compare_commits_by_gen);
+	sort_commits_by_gen(list, nr_commits);
 
 	for (i = 0; i < nr_commits; i++) {
 		/* DFS from list[i] */

index 5f2e90932f..f9e78d69a2 100644
@@ -1066,6 +1066,18 @@ static inline void sane_qsort(void *base, size_t nmemb, size_t size,
 		qsort(base, nmemb, size, compar);
 }
 
+#define DEFINE_SORT(name, elemtype, one, two, code)			\
+static int name##_compare(const void *one##_v_, const void *two##_v_)	\
+{									\
+	elemtype const *one = one##_v_;					\
+	elemtype const *two = two##_v_;					\
+	code;								\
+}									\
+static void name(elemtype *array, size_t n)				\
+{									\
+	QSORT(array, n, name##_compare);				\
+}
+
 #ifndef HAVE_ISO_QSORT_S
 int git_qsort_s(void *base, size_t nmemb, size_t size,
 		int (*compar)(const void *, const void *, void *), void *ctx);

index e8b17cf7e1..1fc6278c6b 100644
@@ -192,17 +192,16 @@ struct commit_dist {
 	int distance;
 };
 
-static int compare_commit_dist(const void *a_, const void *b_)
+static int compare_commit_dist(const struct commit_dist *a,
+			       const struct commit_dist *b)
 {
-	struct commit_dist *a, *b;
-
-	a = (struct commit_dist *)a_;
-	b = (struct commit_dist *)b_;
 	if (a->distance != b->distance)
 		return b->distance - a->distance; /* desc sort */
 	return oidcmp(&a->commit->object.oid, &b->commit->object.oid);
 }
 
+DEFINE_SORT(sort_by_commit_dist, struct commit_dist *, compare_commit_dist)
+
 static struct commit_list *best_bisection_sorted(struct commit_list *list, int nr)
 {
 	struct commit_list *p;

@@ -223,7 +222,7 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n
 		array[cnt].distance = distance;
 		cnt++;
 	}
-	QSORT(array, cnt, compare_commit_dist);
+	sort_by_commit_dist(array, cnt);
 	for (p = list, i = 0; i < cnt; i++) {
 		struct object *obj = &(array[i].commit->object);
 

index 7f4519ec3b..07d302fefd 100644
@@ -550,13 +550,13 @@ static void write_graph_chunk_large_edges(struct hashfile *f,
 	}
 }
 
-static int commit_compare(const void *_a, const void *_b)
+static int commit_compare(const struct object_id *a, const struct object_id *b)
 {
-	const struct object_id *a = (const struct object_id *)_a;
-	const struct object_id *b = (const struct object_id *)_b;
 	return oidcmp(a, b);
 }
 
+DEFINE_SORT(sort_oids, struct object_id *, commit_compare)
+
 struct packed_commit_list {
 	struct commit **list;
 	int nr;

@@ -780,7 +780,7 @@ void write_commit_graph(const char *obj_dir,
 
 	close_reachable(&oids);
 
-	QSORT(oids.list, oids.nr, commit_compare);
+	sort_oids(oids.list, oids.nr);
 
 	count_distinct = 1;
 	for (i = 1; i < oids.nr; i++) {

index 2f5e592d16..496c4201af 100644
@@ -527,11 +527,11 @@ int commit_contains(struct ref_filter *filter, struct commit *commit,
 	return is_descendant_of(commit, list);
 }
 
-static int compare_commits_by_gen(const void *_a, const void *_b)
+static int compare_commits_by_gen(const struct commit * const *ap,
+				  const struct commit * const *bp)
 {
-	const struct commit *a = *(const struct commit * const *)_a;
-	const struct commit *b = *(const struct commit * const *)_b;
-
+	const struct commit *a = *ap;
+	const struct commit *b = *bp;
 	if (a->generation < b->generation)
 		return -1;
 	if (a->generation > b->generation)

@@ -539,6 +539,8 @@ static int compare_commits_by_gen(const void *_a, const void *_b)
 	return 0;
 }
 
+DEFINE_SORT(sort_commits_by_gen, struct commit **, compare_commits_by_gen)
+
 int can_all_from_reach_with_flag(struct object_array *from,
 				 unsigned int with_flag,
 				 unsigned int assign_flag,

@@ -580,7 +582,7 @@ int can_all_from_reach_with_flag(struct object_array *from,
 		nr_commits++;
 	}
 
-	QSORT(list, nr_commits, compare_commits_by_gen);
+	sort_commits_by_gen(list, nr_commits);
 
 	for (i = 0; i < nr_commits; i++) {
 		/* DFS from list[i] */

index 5f2e90932f..2462173790 100644
@@ -1066,6 +1066,20 @@ static inline void sane_qsort(void *base, size_t nmemb, size_t size,
 		qsort(base, nmemb, size, compar);
 }
 
+#define DEFINE_SORT(name, type, compare)				\
+static int compare##_void(const void *one, const void *two)		\
+{									\
+	return compare(one, two);					\
+}									\
+static void name(type base, size_t nmemb)				\
+{									\
+	const type dummy = NULL;					\
+	if (nmemb > 1)							\
+		qsort(base, nmemb, sizeof(base[0]), compare##_void);	\
+	else if (0)							\
+		compare(dummy, dummy);					\
+}
+
 #ifndef HAVE_ISO_QSORT_S
 int git_qsort_s(void *base, size_t nmemb, size_t size,
 		int (*compar)(const void *, const void *, void *), void *ctx);

index e8b17cf7e1..25257c2e69 100644
@@ -192,12 +192,8 @@ struct commit_dist {
 	int distance;
 };
 
-static int compare_commit_dist(const void *a_, const void *b_)
+DEFINE_SORT(static, sort_by_commit_dist, struct commit_dist *, a, b)
 {
-	struct commit_dist *a, *b;
-
-	a = (struct commit_dist *)a_;
-	b = (struct commit_dist *)b_;
 	if (a->distance != b->distance)
 		return b->distance - a->distance; /* desc sort */
 	return oidcmp(&a->commit->object.oid, &b->commit->object.oid);

@@ -223,7 +219,7 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n
 		array[cnt].distance = distance;
 		cnt++;
 	}
-	QSORT(array, cnt, compare_commit_dist);
+	sort_by_commit_dist(array, cnt);
 	for (p = list, i = 0; i < cnt; i++) {
 		struct object *obj = &(array[i].commit->object);
 

index 22c0541da5..44eaadf0a0 100644
@@ -220,10 +220,8 @@ struct possible_tag {
 	unsigned flag_within;
 };
 
-static int compare_pt(const void *a_, const void *b_)
+DEFINE_SORT(static, sort_pt, struct possible_tag *, a, b)
 {
-	struct possible_tag *a = (struct possible_tag *)a_;
-	struct possible_tag *b = (struct possible_tag *)b_;
 	if (a->depth != b->depth)
 		return a->depth - b->depth;
 	if (a->found_order != b->found_order)

@@ -410,7 +408,7 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)
 			    oid_to_hex(cmit_oid));
 	}
 
-	QSORT(all_matches, match_cnt, compare_pt);
+	sort_pt(all_matches, match_cnt);
 
 	if (gave_up_on) {
 		commit_list_insert_by_date(gave_up_on, &list);

index 59a40342b6..2c84349a1b 100644
@@ -268,9 +268,9 @@ static void record_person(int which, struct string_list *people,
 	unuse_commit_buffer(commit, buffer);
 }
 
-static int cmp_string_list_util_as_integral(const void *a_, const void *b_)
+DEFINE_SORT(static, sort_string_list_by_util_as_integral,
+	    struct string_list_item *, a, b)
 {
-	const struct string_list_item *a = a_, *b = b_;
 	return util_as_integral(b) - util_as_integral(a);
 }
 

@@ -319,10 +319,8 @@ static void add_people_info(struct strbuf *out,
 			    struct string_list *authors,
 			    struct string_list *committers)
 {
-	QSORT(authors->items, authors->nr,
-	      cmp_string_list_util_as_integral);
-	QSORT(committers->items, committers->nr,
-	      cmp_string_list_util_as_integral);
+	sort_string_list_by_util_as_integral(authors->items, authors->nr);
+	sort_string_list_by_util_as_integral(committers->items, committers->nr);
 
 	credit_people(out, authors, 'a');
 	credit_people(out, committers, 'c');

index 2004e25da2..d3e91afb50 100644
@@ -1066,21 +1066,15 @@ static void find_unresolved_deltas(struct base_data *base)
 	}
 }
 
-static int compare_ofs_delta_entry(const void *a, const void *b)
+DEFINE_SORT(static, sort_by_offset, struct ofs_delta_entry *, delta_a, delta_b)
 {
-	const struct ofs_delta_entry *delta_a = a;
-	const struct ofs_delta_entry *delta_b = b;
-
 	return delta_a->offset < delta_b->offset ? -1 :
 	       delta_a->offset > delta_b->offset ?  1 :
 	       0;
 }
 
-static int compare_ref_delta_entry(const void *a, const void *b)
+DEFINE_SORT(static, sort_by_oid, struct ref_delta_entry *, delta_a, delta_b)
 {
-	const struct ref_delta_entry *delta_a = a;
-	const struct ref_delta_entry *delta_b = b;
-
 	return oidcmp(&delta_a->oid, &delta_b->oid);
 }
 

@@ -1206,8 +1200,8 @@ static void resolve_deltas(void)
 		return;
 
 	/* Sort deltas by base SHA1/offset for fast searching */
-	QSORT(ofs_deltas, nr_ofs_deltas, compare_ofs_delta_entry);
-	QSORT(ref_deltas, nr_ref_deltas, compare_ref_delta_entry);
+	sort_by_offset(ofs_deltas, nr_ofs_deltas);
+	sort_by_oid(ref_deltas, nr_ref_deltas);
 
 	if (verbose || show_resolving_progress)
 		progress = start_progress(_("Resolving deltas"),

index f1cb45c227..e8d2da1101 100644
@@ -196,9 +196,8 @@ static void add_to_tip_table(const struct object_id *oid, const char *refname,
 	tip_table.sorted = 0;
 }
 
-static int tipcmp(const void *a_, const void *b_)
+DEFINE_SORT(static, sort_by_oid, struct tip_table_entry *, a, b)
 {
-	const struct tip_table_entry *a = a_, *b = b_;
 	return oidcmp(&a->oid, &b->oid);
 }
 

@@ -293,7 +292,7 @@ static const char *get_exact_ref_match(const struct object *o)
 		return NULL;
 
 	if (!tip_table.sorted) {
-		QSORT(tip_table.table, tip_table.nr, tipcmp);
+		sort_by_oid(tip_table.table, tip_table.nr);
 		tip_table.sorted = 1;
 	}
 

index e6316d294d..fc37ae186f 100644
@@ -2868,11 +2868,8 @@ static void mark_in_pack_object(struct object *object, struct packed_git *p, str
  * Compare the objects in the offset order, in order to emulate the
  * "git rev-list --objects" output that produced the pack originally.
  */
-static int ofscmp(const void *a_, const void *b_)
+DEFINE_SORT(static, sort_in_pack_objects, struct in_pack_object *, a, b)
 {
-	struct in_pack_object *a = (struct in_pack_object *)a_;
-	struct in_pack_object *b = (struct in_pack_object *)b_;
-
 	if (a->offset < b->offset)
 		return -1;
 	else if (a->offset > b->offset)

@@ -2912,7 +2909,7 @@ static void add_objects_in_unpacked_packs(struct rev_info *revs)
 	}
 
 	if (in_pack.nr) {
-		QSORT(in_pack.array, in_pack.nr, ofscmp);
+		sort_in_pack_objects(in_pack.array, in_pack.nr);
 		for (i = 0; i < in_pack.nr; i++) {
 			struct object *o = in_pack.array[i].object;
 			add_object_entry(&o->oid, o->type, "", 0);

index f7edf7f2cb..0f9e70d445 100644
@@ -1011,10 +1011,8 @@ static int add_push_to_show_info(struct string_list_item *push_item, void *cb_da
  * Sorting comparison for a string list that has push_info
  * structs in its util field
  */
-static int cmp_string_with_push(const void *va, const void *vb)
+DEFINE_SORT(static, sort_by_push_info, struct string_list_item *, a, b)
 {
-	const struct string_list_item *a = va;
-	const struct string_list_item *b = vb;
 	const struct push_info *a_push = a->util;
 	const struct push_info *b_push = b->util;
 	int cmp = strcmp(a->string, b->string);

@@ -1216,7 +1214,7 @@ static int show(int argc, const char **argv)
 
 		info.width = info.width2 = 0;
 		for_each_string_list(&states.push, add_push_to_show_info, &info);
-		QSORT(info.list->items, info.list->nr, cmp_string_with_push);
+		sort_by_push_info(info.list->items, info.list->nr);
 		if (info.list->nr)
 			printf_ln(Q_("  Local ref configured for 'git push'%s:",
 				     "  Local refs configured for 'git push'%s:",

index 3898a2c9c4..ec1ace6ed5 100644
@@ -29,15 +29,13 @@ static char const * const shortlog_usage[] = {
  */
 #define UTIL_TO_INT(x) ((intptr_t)(x)->util)
 
-static int compare_by_counter(const void *a1, const void *a2)
+DEFINE_SORT(static, sort_by_counter, struct string_list_item *, i1, i2)
 {
-	const struct string_list_item *i1 = a1, *i2 = a2;
 	return UTIL_TO_INT(i2) - UTIL_TO_INT(i1);
 }
 
-static int compare_by_list(const void *a1, const void *a2)
+DEFINE_SORT(static, sort_by_list, struct string_list_item *, i1, i2)
 {
-	const struct string_list_item *i1 = a1, *i2 = a2;
 	const struct string_list *l1 = i1->util, *l2 = i2->util;
 
 	if (l1->nr < l2->nr)

@@ -338,9 +336,12 @@ void shortlog_output(struct shortlog *log)
 	int i, j;
 	struct strbuf sb = STRBUF_INIT;
 
-	if (log->sort_by_number)
-		QSORT(log->list.items, log->list.nr,
-		      log->summary ? compare_by_counter : compare_by_list);
+	if (log->sort_by_number) {
+		if (log->summary)
+			sort_by_counter(log->list.items, log->list.nr);
+		else
+			sort_by_list(log->list.items, log->list.nr);
+	}
 	for (i = 0; i < log->list.nr; i++) {
 		const struct string_list_item *item = &log->list.items[i];
 		if (log->summary) {

index 7f4519ec3b..fc2fbf22b4 100644
@@ -550,10 +550,8 @@ static void write_graph_chunk_large_edges(struct hashfile *f,
 	}
 }
 
-static int commit_compare(const void *_a, const void *_b)
+DEFINE_SORT(static, sort_oids, struct object_id *, a, b)
 {
-	const struct object_id *a = (const struct object_id *)_a;
-	const struct object_id *b = (const struct object_id *)_b;
 	return oidcmp(a, b);
 }
 

@@ -780,7 +778,7 @@ void write_commit_graph(const char *obj_dir,
 
 	close_reachable(&oids);
 
-	QSORT(oids.list, oids.nr, commit_compare);
+	sort_oids(oids.list, oids.nr);
 
 	count_distinct = 1;
 	for (i = 1; i < oids.nr; i++) {

index 8e5018e406..29232831d4 100644
@@ -229,11 +229,9 @@ struct tree_islands_todo {
 	unsigned int depth;
 };
 
-static int tree_depth_compare(const void *a, const void *b)
+DEFINE_SORT(static, sort_by_tree_depth, struct tree_islands_todo *,
+	    todo_a, todo_b)
 {
-	const struct tree_islands_todo *todo_a = a;
-	const struct tree_islands_todo *todo_b = b;
-
 	return todo_a->depth - todo_b->depth;
 }
 

@@ -262,7 +260,7 @@ void resolve_tree_islands(int progress, struct packing_data *to_pack)
 			nr++;
 		}
 	}
-	QSORT(todo, nr, tree_depth_compare);
+	sort_by_tree_depth(todo, nr);
 
 	if (progress)
 		progress_state = start_progress(_("Propagating island marks"), nr);

index f0c7557b40..ecb1961173 100644
@@ -2924,10 +2924,8 @@ static long gather_dirstat(struct diff_options *opt, struct dirstat_dir *dir,
 	return sum_changes;
 }
 
-static int dirstat_compare(const void *_a, const void *_b)
+DEFINE_SORT(static, sort_by_name, struct dirstat_file *, a, b)
 {
-	const struct dirstat_file *a = _a;
-	const struct dirstat_file *b = _b;
 	return strcmp(a->name, b->name);
 }
 

@@ -3021,7 +3019,7 @@ static void show_dirstat(struct diff_options *options)
 		return;
 
 	/* Show all directories with more than x% of the changes */
-	QSORT(dir.files, dir.nr, dirstat_compare);
+	sort_by_name(dir.files, dir.nr);
 	gather_dirstat(options, &dir, changed, "", 0);
 }
 

@@ -3065,7 +3063,7 @@ static void show_dirstat_by_line(struct diffstat_t *data, struct diff_options *o
 		return;
 
 	/* Show all directories with more than x% of the changes */
-	QSORT(dir.files, dir.nr, dirstat_compare);
+	sort_by_name(dir.files, dir.nr);
 	gather_dirstat(options, &dir, changed, "", 0);
 }
 

index c83d45a047..53ed2d5766 100644
@@ -107,11 +107,8 @@ static struct spanhash_top *add_spanhash(struct spanhash_top *top,
 	}
 }
 
-static int spanhash_cmp(const void *a_, const void *b_)
+DEFINE_SORT(static, sort_by_spanhash, struct spanhash *, a, b)
 {
-	const struct spanhash *a = a_;
-	const struct spanhash *b = b_;
-
 	/* A count of zero compares at the end.. */
 	if (!a->cnt)
 		return !b->cnt ? 0 : 1;

@@ -158,7 +155,7 @@ static struct spanhash_top *hash_chars(struct diff_filespec *one)
 		n = 0;
 		accum1 = accum2 = 0;
 	}
-	QSORT(hash->data, 1ul << hash->alloc_log2, spanhash_cmp);
+	sort_by_spanhash(hash->data, 1ul << hash->alloc_log2);
 	return hash;
 }
 

index 19e73311f9..e8abd84242 100644
@@ -78,11 +78,8 @@ static int match_order(const char *path)
 	return order_cnt;
 }
 
-static int compare_objs_order(const void *a_, const void *b_)
+DEFINE_SORT(static, sort_by_order, struct obj_order *, a, b)
 {
-	struct obj_order const *a, *b;
-	a = (struct obj_order const *)a_;
-	b = (struct obj_order const *)b_;
 	if (a->order != b->order)
 		return a->order - b->order;
 	return a->orig_order - b->orig_order;

@@ -101,7 +98,7 @@ void order_objects(const char *orderfile, obj_path_fn_t obj_path,
 		objs[i].orig_order = i;
 		objs[i].order = match_order(obj_path(objs[i].obj));
 	}
-	QSORT(objs, nr, compare_objs_order);
+	sort_by_order(objs, nr);
 }
 
 static const char *pair_pathtwo(void *obj)

index daddd9b28a..0e256377db 100644
@@ -234,10 +234,8 @@ static void record_rename_pair(int dst_index, int src_index, int score)
  * We sort the rename similarity matrix with the score, in descending
  * order (the most similar first).
  */
-static int score_compare(const void *a_, const void *b_)
+static int score_compare(const struct diff_score *a, const struct diff_score *b)
 {
-	const struct diff_score *a = a_, *b = b_;
-
 	/* sink the unused ones to the bottom */
 	if (a->dst < 0)
 		return (0 <= b->dst);