show-branch: use commit slab to represent bitflags of arbitrary widthjc/show-branch

We still haven't lifted the total number of revs limit that is
hardcoded, but the underlying data structure can now represent
arbitrary number of refs.

Signed-off-by: Junio C Hamano <gitster@pobox.com>

1 files changed, 118 insertions, 24 deletions

diff --git a/builtin/show-branch.c b/builtin/show-branch.c
index dcfcd67eee..adc3569e3f 100644
--- a/builtin/show-branch.c
+++ b/builtin/show-branch.c
@@ -4,6 +4,7 @@
 #include "builtin.h"
 #include "color.h"
 #include "parse-options.h"
+#include "commit-slab.h"
 
 static const char* show_branch_usage[] = {
     N_("git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order] [--current] [--color[=<when>] | --no-color] [--sparse] [--more=<n> | --list | --independent | --merge-base] [--no-name | --sha1-name] [--topics] [(<rev> | <glob>)...]"),
@@ -22,74 +23,170 @@ static const char **default_arg;
 #define REV_SHIFT	 2
 #define MAX_REVS	(FLAG_BITS - REV_SHIFT) /* should not exceed bits_per_int - REV_SHIFT */
 
-static unsigned int all_revs;
-static unsigned int rev_mask[MAX_REVS];
 
-static void prepare_all_flags(int num_rev, struct commit **rev)
+define_commit_slab(reachable_cslab, unsigned char);
+
+struct reachable {
+	int numbits;
+	unsigned char *all_revs;
+	unsigned char *rev_mask;
+	struct reachable_cslab cslab;
+};
+
+static struct reachable reachable;
+
+static void init_reachable(int numbits)
+{
+	int numbytes = (numbits + 7) / 8;
+
+	reachable.numbits = numbits;
+	reachable.all_revs = xcalloc(numbytes, 1);
+	reachable.rev_mask = xcalloc(numbits, numbytes);
+
+	init_reachable_cslab(&reachable.cslab);
+	clear_reachable_cslab(&reachable.cslab);
+
+	init_reachable_cslab_with_stride(&reachable.cslab, numbytes);
+}
+
+static void set_nth_bit_in_bytearray(unsigned char *barray, int n)
+{
+	barray[n/8] |= (1 << (n % 8));
+}
+
+static int tst_nth_bit_in_bytearray(unsigned char *barray, int n)
+{
+	return barray[n/8] & (1 << (n % 8));
+}
+
+static int has_any_bit_set(struct commit *commit)
 {
+	unsigned char *at;
+	int numbytes = (reachable.numbits + 7) / 8;
 	int i;
 
-	all_revs = ((1u << (REV_SHIFT + num_rev)) - 1) & ~((1u << REV_SHIFT) - 1);
-	for (i = 0; i < num_rev; i++)
-		rev_mask[i] = rev[i]->object.flags;
+	/* Yeah, I know accessing a word at a time may be faster */
+	at = reachable_cslab_at(&reachable.cslab, commit);
+	for (i = 0; i < numbytes; i++) {
+		if (*at)
+			return 1;
+		at++;
+	}
+	return 0;
+}
+
+static void prepare_all_flags(int num_rev, struct commit **rev)
+{
+	int i;
+	unsigned char *at;
+	int numbytes = (reachable.numbits + 7) / 8;
+
+	for (i = 0; i < reachable.numbits; i++)
+		set_nth_bit_in_bytearray(reachable.all_revs, i);
+	for (i = 0; i < reachable.numbits; i++) {
+		at = reachable_cslab_at(&reachable.cslab, rev[i]);
+		memcpy(reachable.rev_mask + i * numbytes, at, numbytes);
+	}
 }
 
 static int commit_seen(struct commit *commit)
 {
-	return commit->object.flags;
+	return ((commit->object.flags & UNINTERESTING) ||
+		has_any_bit_set(commit));
+}
+
+static int all_bits_set(const unsigned char *bits, const unsigned char *mask)
+{
+	int numbytes = (reachable.numbits + 7) / 8;
+	int i;
+
+	for (i = 0; i < numbytes; i++)
+		if ((bits[i] & mask[i]) != mask[i])
+			return 0;
+	return 1;
 }
 
 static int reachable_from_all(struct commit *commit)
 {
-	unsigned flags = commit->object.flags;
-	return (flags & all_revs) == all_revs;
+	unsigned char *at = reachable_cslab_at(&reachable.cslab, commit);
+
+	return all_bits_set(at, reachable.all_revs);
 }
 
 static int already_reachable(struct commit *this, struct commit *other, int uninteresting)
 {
-	unsigned this_flag = this->object.flags & ~UNINTERESTING;
-	unsigned flag = other->object.flags & ~UNINTERESTING;
+	unsigned char *this_at, *other_at;
 
 	if (!!(this->object.flags & UNINTERESTING) != uninteresting)
 		return 0;
 
-	return (this_flag & flag) == flag;
+	this_at = reachable_cslab_at(&reachable.cslab, this);
+	other_at = reachable_cslab_at(&reachable.cslab, other);
+
+	return all_bits_set(this_at, other_at);
 }
 
 static void propagate_mark(struct commit *this, struct commit *other, int uninteresting)
 {
+	int numbytes = (reachable.numbits + 7) / 8;
+	int i;
+	unsigned char *this_at, *other_at;
+
 	if (uninteresting)
 		this->object.flags |= UNINTERESTING;
-	this->object.flags |= (other->object.flags & ~UNINTERESTING);
+
+	this_at = reachable_cslab_at(&reachable.cslab, this);
+	other_at = reachable_cslab_at(&reachable.cslab, other);
+	for (i = 0; i < numbytes; i++)
+		this_at[i] |= other_at[i];
 }
 
 static int has_independent_mask(struct commit *commit, int i)
 {
-	return commit->object.flags == rev_mask[i];
+	int numbytes = (reachable.numbits + 7) / 8;
+	unsigned char *at = reachable_cslab_at(&reachable.cslab, commit);
+
+	return !memcmp(at, reachable.rev_mask + i * numbytes, numbytes);
 }
 
 static int count_set_bits(struct commit *commit, int num_rev)
 {
 	int i, count;
+	unsigned char *at = reachable_cslab_at(&reachable.cslab, commit);
+
+	if (num_rev != reachable.numbits)
+		die("BUG: num-rev different from numbits");
+
 	for (i = count = 0; i < num_rev; i++)
-		if (commit->object.flags & (1u << (i + REV_SHIFT)))
+		if (tst_nth_bit_in_bytearray(at, i))
 			count++;
 	return count;
 }
 
 static void set_nth_bit(struct commit *commit, int n)
 {
-	commit->object.flags |= (1u << (n + REV_SHIFT));
+	unsigned char *at = reachable_cslab_at(&reachable.cslab, commit);
+	set_nth_bit_in_bytearray(at, n);
 }
 
 static int has_nth_bit_only(struct commit *commit, int n)
 {
-	return commit->object.flags == (1u << (n + REV_SHIFT));
+	int i;
+	unsigned char *at = reachable_cslab_at(&reachable.cslab, commit);
+
+	for (i = 0; i < n; i++)
+		if (tst_nth_bit_in_bytearray(at, i))
+			return 0;
+	for (i = n + 1; i < reachable.numbits; i++)
+		if (tst_nth_bit_in_bytearray(at, i))
+			return 0;
+	return tst_nth_bit_in_bytearray(at, n);
 }
 
 static int has_nth_bit(struct commit *commit, int n)
 {
-	return !!(commit->object.flags & (1u << (n + REV_SHIFT)));
+	unsigned char *at = reachable_cslab_at(&reachable.cslab, commit);
+	return tst_nth_bit_in_bytearray(at, n);
 }
 
 #define DEFAULT_REFLOG	4
@@ -280,7 +377,7 @@ static void join_revs(struct commit_list **list_p,
 		struct commit_list *parents;
 		int still_interesting = !!interesting(*list_p);
 		struct commit *commit = pop_one_commit(list_p);
-		int mark_uninteresting = 0;
+		int mark_uninteresting = !!(commit->object.flags & UNINTERESTING);
 
 		if (!still_interesting && extra <= 0)
 			break;
@@ -886,6 +983,8 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)
 		exit(0);
 	}
 
+	init_reachable(ref_name_cnt);
+
 	for (num_rev = 0; ref_name[num_rev]; num_rev++) {
 		unsigned char revkey[20];
 
@@ -900,11 +999,6 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)
 		parse_commit(commit);
 		mark_seen(commit, &seen);
 
-		/*
-		 * rev#0 uses bit REV_SHIFT, rev#1 uses bit REV_SHIFT+1,
-		 * and so on.  REV_SHIFT bits from bit 0 are used for
-		 * internal bookkeeping.
-		 */
 		set_nth_bit(commit, num_rev);
 		if (has_nth_bit_only(commit, num_rev))
 			commit_list_insert_by_date(commit, &list);