All of lore.kernel.org
 help / color / mirror / Atom feed
From: Stephan Beyer <s-beyer@gmx.net>
To: git@vger.kernel.org
Cc: Stephan Beyer <s-beyer@gmx.net>,
	Christian Couder <chriscool@tuxfamily.org>
Subject: [PATCH 06/16] bisect: use struct node_data array instead of int array
Date: Fri, 26 Feb 2016 03:04:32 +0100	[thread overview]
Message-ID: <1456452282-10325-7-git-send-email-s-beyer@gmx.net> (raw)
In-Reply-To: <1456452282-10325-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 03e7660..bcb58ed 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.7.1.354.gd492730.dirty

  parent reply	other threads:[~2016-02-26  2:06 UTC|newest]

Thread overview: 34+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2016-02-26  2:04 [PATCH 00/16] git bisect improvements Stephan Beyer
2016-02-26  2:04 ` [PATCH 01/16] bisect: write about `bisect next` in documentation Stephan Beyer
2016-02-26  8:02   ` Jacob Keller
2016-02-26 18:47   ` Junio C Hamano
2016-02-27 13:45     ` Stephan Beyer
2016-02-27 18:03       ` Junio C Hamano
2016-02-27 19:38         ` Stephan Beyer
2016-02-28 18:28           ` Junio C Hamano
2016-02-26  2:04 ` [PATCH 02/16] bisect: add test for the bisect algorithm Stephan Beyer
2016-02-26  6:53   ` Christian Couder
2016-02-26 21:38     ` Stephan Beyer
2016-02-27 11:40       ` Christian Couder
2016-02-27 12:42         ` Matthieu Moy
2016-02-26  2:04 ` [PATCH 03/16] bisect: make bisect compile if DEBUG_BISECT is set Stephan Beyer
2016-02-26  2:04 ` [PATCH 04/16] bisect: make algorithm behavior independent of DEBUG_BISECT Stephan Beyer
2016-02-26  2:04 ` [PATCH 05/16] bisect: get rid of recursion in count_distance() Stephan Beyer
2016-02-26  2:04 ` Stephan Beyer [this message]
2016-02-26  2:04 ` [PATCH 07/16] bisect: replace clear_distance() by unique markers Stephan Beyer
2016-02-26  2:04 ` [PATCH 08/16] bisect: use commit instead of commit list as arguments when appropriate Stephan Beyer
2016-02-26  3:10   ` Junio C Hamano
2016-02-26  2:04 ` [PATCH 09/16] bisect: extract get_distance() function from code duplication Stephan Beyer
2016-02-26  2:04 ` [PATCH 10/16] bisect: introduce distance_direction() Stephan Beyer
2016-02-26  2:04 ` [PATCH 11/16] bisect: make total number of commits global Stephan Beyer
2016-02-26  2:04 ` [PATCH 12/16] bisect: rename count_distance() to compute_weight() Stephan Beyer
2016-02-26  2:04 ` [PATCH 13/16] bisect: prepare for different algorithms based on find_all Stephan Beyer
2016-02-26  2:04 ` [PATCH 14/16] bisect: use a modified breadth-first search to find relevant weights Stephan Beyer
2016-02-26  3:09   ` Junio C Hamano
2016-02-26 20:55     ` Stephan Beyer
2016-02-26  2:04 ` [PATCH 15/16] bisect: compute best bisection in compute_relevant_weights() Stephan Beyer
2016-02-26  2:04 ` [PATCH 16/16] bisect: get back halfway shortcut Stephan Beyer
2016-03-20 18:50 ` [PATCH 00/16] git bisect improvements Pranit Bauva
2016-03-21 22:22   ` Stephan Beyer
2016-03-22  7:35     ` Christian Couder
2016-03-22 11:35     ` Pranit Bauva

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=1456452282-10325-7-git-send-email-s-beyer@gmx.net \
    --to=s-beyer@gmx.net \
    --cc=chriscool@tuxfamily.org \
    --cc=git@vger.kernel.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body. 
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.