From cc1cbe0e2f168b127af3a83c58462408a133a8ce Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Tue, 30 Apr 2013 09:34:15 -0700 Subject: show-branch: use commit slab to represent bitflags of arbitrary width 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 --- builtin/show-branch.c | 142 +++++++++++++++++++++++++++++++++++++++++--------- 1 file 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[=] | --no-color] [--sparse] [--more= | --list | --independent | --merge-base] [--no-name | --sha1-name] [--topics] [( | )...]"), @@ -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); -- cgit v1.2.1