git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH v2 11/21] bisect: use struct node_data array instead of int array

From
Stephan Beyer <s-beyer@gmx.net>
Date
Apr 10, 2016, 13:19 UTC
Message-ID
<1460294354-7031-12-git-send-email-s-beyer@gmx.net>
In-Reply-To
<1460294354-7031-1-git-send-email-s-beyer@gmx.net>

This is a preparation for subsequent changes. During a bisection process, we want to augment commits with further information to improve speed.

Signed-off-by: Stephan Beyer <s-beyer@gmx.net>
---
 bisect.c | 61 ++++++++++++++++++++++++++++++-------------------------------
 1 file changed, 30 insertions(+), 31 deletions(-)
diff --git a/bisect.c b/bisect.c
index 16bbfa6..bc1bfbd 100644
--- a/bisect.c
+++ b/bisect.c
@@ -23,9 +23,21 @@ static const char *argv_show_branch[] = {"show-branch", NULL, NULL};
 static const char *term_bad;
 static const char *term_good;
 
+struct node_data {
+	int weight;
+};
+
 /* Remember to update object flag allocation in object.h */
 #define COUNTED		(1u<<16)
 
+#define DEBUG_BISECT 0
+
+static inline struct node_data *node_data(struct commit *elem)
+{
+	assert(elem->util);
+	return (struct node_data *)elem->util;
+}
+
 static int count_distance(struct commit_list *entry)
 {
 	int nr = 0;
@@ -59,18 +71,6 @@ static void clear_distance(struct commit_list *list)
 	}
 }
 
-#define DEBUG_BISECT 0
-
-static inline int weight(struct commit_list *elem)
-{
-	return *((int*)(elem->item->util));
-}
-
-static inline void weight_set(struct commit_list *elem, int weight)
-{
-	*((int*)(elem->item->util)) = weight;
-}
-
 static int count_interesting_parents(struct commit *commit)
 {
 	struct commit_list *p;
@@ -95,7 +95,7 @@ static inline int halfway(struct commit_list *p, int nr)
 	 * 2 and 3 are halfway of 5.
 	 * 3 is halfway of 6 but 2 and 4 are not.
 	 */
-	switch (2 * weight(p) - nr) {
+	switch (2 * node_data(p->item)->weight - nr) {
 	case -1: case 0: case 1:
 		return 1;
 	default:
@@ -128,7 +128,7 @@ static void show_list(const char *debug, int counted, int nr,
 			(flags & UNINTERESTING) ? 'U' : ' ',
 			(flags & COUNTED) ? 'C' : ' ');
 		if (commit->util)
-			fprintf(stderr, "%3d", weight(p));
+			fprintf(stderr, "%3d", node_data(commit)->weight);
 		else
 			fprintf(stderr, "---");
 		fprintf(stderr, " %.*s", 8, sha1_to_hex(commit->object.oid.hash));
@@ -156,7 +156,7 @@ static struct commit_list *best_bisection(struct commit_list *list, int nr)
 
 		if (flags & TREESAME)
 			continue;
-		distance = weight(p);
+		distance = node_data(p->item)->weight;
 		if (nr - distance < distance)
 			distance = nr - distance;
 		if (distance > best_distance) {
@@ -196,7 +196,7 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n
 
 		if (flags & TREESAME)
 			continue;
-		distance = weight(p);
+		distance = node_data(p->item)->weight;
 		if (nr - distance < distance)
 			distance = nr - distance;
 		array[cnt].commit = p->item;
@@ -234,7 +234,7 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n
  * or positive distance.
  */
 static struct commit_list *do_find_bisection(struct commit_list *list,
-					     int nr, int *weights,
+					     int nr, struct node_data *weights,
 					     int find_all)
 {
 	int n, counted;
@@ -246,11 +246,11 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 		struct commit *commit = p->item;
 		unsigned flags = commit->object.flags;
 
-		p->item->util = &weights[n++];
+		commit->util = &weights[n++];
 		switch (count_interesting_parents(commit)) {
 		case 0:
 			if (!(flags & TREESAME)) {
-				weight_set(p, 1);
+				node_data(commit)->weight = 1;
 				counted++;
 				show_list("bisection 2 count one",
 					  counted, nr, list);
@@ -261,10 +261,10 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 			 */
 			break;
 		case 1:
-			weight_set(p, -1);
+			node_data(commit)->weight = -1;
 			break;
 		default:
-			weight_set(p, -2);
+			node_data(commit)->weight = -2;
 			break;
 		}
 	}
@@ -287,8 +287,8 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 	 */
 	for (p = list; p; p = p->next) {
 		if (!(p->item->object.flags & UNINTERESTING)
-		 && (weight(p) == -2)) {
-			weight_set(p, count_distance(p));
+		 && (node_data(p->item)->weight == -2)) {
+			node_data(p->item)->weight = count_distance(p);
 			clear_distance(list);
 
 			/* Does it happen to be at exactly half-way? */
@@ -305,12 +305,12 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 			struct commit_list *q;
 			unsigned flags = p->item->object.flags;
 
-			if (0 <= weight(p))
+			if (0 <= node_data(p->item)->weight)
 				continue;
 			for (q = p->item->parents; q; q = q->next) {
 				if (q->item->object.flags & UNINTERESTING)
 					continue;
-				if (0 <= weight(q))
+				if (0 <= node_data(q->item)->weight)
 					break;
 			}
 			if (!q)
@@ -321,14 +321,13 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 			 * add one for p itself if p is to be counted,
 			 * otherwise inherit it from q directly.
 			 */
+			node_data(p->item)->weight = node_data(q->item)->weight;
 			if (!(flags & TREESAME)) {
-				weight_set(p, weight(q)+1);
+				node_data(p->item)->weight++;
 				counted++;
 				show_list("bisection 2 count one",
 					  counted, nr, list);
 			}
-			else
-				weight_set(p, weight(q));
 
 			/* Does it happen to be at exactly half-way? */
 			if (!find_all && halfway(p, nr))
@@ -350,7 +349,7 @@ struct commit_list *find_bisection(struct commit_list *list,
 {
 	int nr, on_list;
 	struct commit_list *p, *best, *next, *last;
-	int *weights;
+	struct node_data *weights;
 
 	show_list("bisection 2 entry", 0, 0, list);
 
@@ -376,14 +375,14 @@ struct commit_list *find_bisection(struct commit_list *list,
 	show_list("bisection 2 sorted", 0, nr, list);
 
 	*all = nr;
-	weights = xcalloc(on_list, sizeof(*weights));
+	weights = (struct node_data *)xcalloc(on_list, sizeof(*weights));
 
 	/* Do the real work of finding bisection commit. */
 	best = do_find_bisection(list, nr, weights, find_all);
 	if (best) {
 		if (!find_all)
 			best->next = NULL;
-		*reaches = weight(best);
+		*reaches = node_data(best->item)->weight;
 	}
 	free(weights);
 	return best;

-- 
2.8.1.137.g522756c
Previous: Junio C HamanoNext: Christian Couder
Message 28 of 56 in “git bisect improvements”
  1. 00/21 git bisect improvementsStephan Beyer, Apr 10, 2016
  2. 01/21 bisect: write about `bisect next` in documentationStephan Beyer, Apr 10, 2016
  3. 02/21 bisect: allow 'bisect run' if no good commit is knownStephan Beyer, Apr 10, 2016
  4. 03/21 t/test-lib-functions.sh: generalize test_cmp_revStephan Beyer, Apr 10, 2016
  5. Eric SunshineApr 11, 2016
  6. Junio C HamanoApr 15, 2016
  7. Stephan BeyerApr 24, 2016
  8. Junio C HamanoApr 25, 2016
  9. 04/21 t: use test_cmp_rev() where appropriateStephan Beyer, Apr 10, 2016
  10. Eric SunshineApr 11, 2016
  11. Junio C HamanoApr 15, 2016
  12. 05/21 t6030: generalize test to not rely on current implementationStephan Beyer, Apr 10, 2016
  13. Torsten BögershausenApr 10, 2016
  14. Junio C HamanoApr 10, 2016
  15. Stephan BeyerApr 10, 2016
  16. Eric SunshineApr 11, 2016
  17. Junio C HamanoApr 15, 2016
  18. 06/21 bisect: add test for the bisect algorithmStephan Beyer, Apr 10, 2016
  19. Junio C HamanoApr 15, 2016
  20. 07/21 bisect: plug the biggest memory leakStephan Beyer, Apr 10, 2016
  21. Junio C HamanoApr 15, 2016
  22. 08/21 bisect: make bisect compile if DEBUG_BISECT is setStephan Beyer, Apr 10, 2016
  23. Junio C HamanoApr 15, 2016
  24. 09/21 bisect: make algorithm behavior independent of DEBUG_BISECTStephan Beyer, Apr 10, 2016
  25. Junio C HamanoApr 15, 2016
  26. 10/21 bisect: get rid of recursion in count_distance()Stephan Beyer, Apr 10, 2016
  27. Junio C HamanoApr 15, 2016
  28. 11/21 bisect: use struct node_data array instead of int arrayStephan Beyer, Apr 10, 2016
  29. Christian CouderApr 12, 2016
  30. Junio C HamanoApr 15, 2016
  31. 12/21 bisect: replace clear_distance() by unique markersStephan Beyer, Apr 10, 2016
  32. Christian CouderApr 12, 2016
  33. Junio C HamanoApr 15, 2016
  34. 13/21 bisect: use commit instead of commit list as arguments when appropriateStephan Beyer, Apr 10, 2016
  35. Junio C HamanoApr 15, 2016
  36. 14/21 bisect: extract get_distance() function from code duplicationStephan Beyer, Apr 10, 2016
  37. Junio C HamanoApr 15, 2016
  38. 15/21 bisect: introduce distance_direction()Stephan Beyer, Apr 10, 2016
  39. Junio C HamanoApr 15, 2016
  40. 16/21 bisect: make total number of commits globalStephan Beyer, Apr 10, 2016
  41. Christian CouderApr 13, 2016
  42. Junio C HamanoApr 15, 2016
  43. Junio C HamanoApr 16, 2016
  44. 17/21 bisect: rename count_distance() to compute_weight()Stephan Beyer, Apr 10, 2016
  45. Christian CouderApr 13, 2016
  46. Junio C HamanoApr 15, 2016
  47. 18/21 bisect: prepare for different algorithms based on find_allStephan Beyer, Apr 10, 2016
  48. Junio C HamanoApr 15, 2016
  49. 19/21 bisect: use a bottom-up traversal to find relevant weightsStephan Beyer, Apr 10, 2016
  50. Christian CouderApr 13, 2016
  51. Junio C HamanoApr 15, 2016
  52. Junio C HamanoApr 15, 2016
  53. Junio C HamanoApr 26, 2016
  54. 20/21 bisect: compute best bisection in compute_relevant_weights()Stephan Beyer, Apr 10, 2016
  55. 21/21 bisect: get back halfway shortcutStephan Beyer, Apr 10, 2016
  56. Junio C HamanoApr 15, 2016

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.