From: Jeff King <hidden> Date: 2016-06-15 23:01:44
Once upon a time we checked "tag --contains" by doing N merge-base
traversals, one per tag. That turned out to be really slow.
Later, I added a single traversal in ffc4b80 (tag: speed up --contains
calculation, 2011-06-11) that works in a depth-first way. That's fast
for the common case of tags spread throughout history, but slow when all
of the tags are close to the searched-for commit (which would be more
likely with branches, since they advance). That, plus the general
hacky-ness of the implementation, prevented it from being used for "git
branch" or in other places.
Over a year ago, Junio and I worked on the commit-slab code. The
original point of it[1] was to be able to do a merge-base traversal like
this, where we kept one bit per tip in each commit (so that we know not
only what the merge base is, but _which_ tip hit each commit). So now I
finally got around to it. :)
Timings are in the final patch, but the short of it is: it's about as
fast as the depth-first code for the normal tag case (tags spread out
through history), but way faster for the branch-like case (tags close to
the commit).
This series stops short of moving "git branch" over to it. My next goal
once this is solid is to factor the logic out so that "tag -l", "branch
-l", and "for-each-ref" all use the same code. I got stuck on that
earlier because I just couldn't justify sharing the tag-contains
implementation with the others.
[1/8]: tag: allow --sort with -n
[2/8]: tag: factor out decision to stream tags
[3/8]: paint_down_to_common: use prio_queue
[4/8]: add functions for memory-efficient bitmaps
[5/8]: string-list: add pos to iterator callback
[6/8]: commit: provide a fast multi-tip contains function
[7/8]: tag: use commit_contains
[8/8]: perf: add tests for tag --contains
-Peff
[1] http://article.gmane.org/gmane.comp.version-control.git/220545
From: Jeff King <hidden> Date: 2016-06-15 23:01:44
When we are listing tags, we print each one as it is
processed by for_each_ref. We can't do that with --sort, of
course, as we need to see the whole list to sort. For the
--sort code path, we store each tag in a string_list, and
then print them all at the end.
This interacts badly with "-n", which needs not only the
name of the tag, but also the object itself. We simply
punted on handling this, and disallowed the combination.
This patch remedies that by storing the sha1 of each object
in the "util" field of the string list. We can then factor
out the printing to a helper function and call that function
either when we first see each tag, or after we have sorted.
Signed-off-by: Jeff King <redacted>
---
builtin/tag.c | 42 +++++++++++++++++++++++++-----------------
cache.h | 7 +++++++
t/t7004-tag.sh | 18 ++++++++++++++++++
3 files changed, 50 insertions(+), 17 deletions(-)
@@ -1423,6 +1423,24 @@ EOFtest_cmpexpectactual'+test_expect_success'sorting works with -n''+cat>msg<<-\EOF&&+multiline+tag+message+EOF+gittag-Fmsgfoo-long&&+gittag-l--sort=-refname-n2"foo*">actual&&+cat>expect<<-\EOF&&+foo1.6Mergebranch'\''master'\''intostable+foo1.3Mergebranch'\''master'\''intostable+foo1.10Mergebranch'\''master'\''intostable+foo-longmultiline+tag+EOF+test_cmpexpectactual+'+ run_with_limited_stack(){(ulimit-s64&&"$@")}
From: Jeff King <hidden> Date: 2016-06-15 23:01:44
Right now we stream tags if we are not sorting. If we are
sorting, we save them in a list and print them at the end.
Let's abstract this decision into a function to make it
easier to add more cases where we use the list.
Signed-off-by: Jeff King <redacted>
---
builtin/tag.c | 15 ++++++++++-----
1 file changed, 10 insertions(+), 5 deletions(-)
From: Jeff King <hidden> Date: 2016-06-15 23:01:45
When we are traversing to find merge bases, we keep our
usual commit_list of commits to process, sorted by their
commit timestamp. As we add each parent to the list, we have
to spend "O(width of history)" to do the insertion, where
the width of history is the number of simultaneous lines of
development.
If we instead use a heap-based priority queue, we can do
these insertions in "O(log width)" time. This provides minor
speedups to merge-base calculations (timings in linux.git,
warm cache, best-of-five):
[before]
$ git merge-base HEAD v2.6.12
real 0m3.251s
user 0m3.148s
sys 0m0.104s
[after]
$ git merge-base HEAD v2.6.12
real 0m3.234s
user 0m3.108s
sys 0m0.128s
That's only an 0.5% speedup, but it does help protect us
against pathological cases.
The downside is that our priority queue is not stable, which
means that commits with the same timestamp may not come out
in the order we put them in. You can see this in the test
update in t6024. That test does a recursive merge across a
set of commits that all have the same timestamp. For the
virtual ancestor, the test currently ends up with blob like
this:
<<<<<<< Temporary merge branch 1
<<<<<<< Temporary merge branch 1
C
=======
B
>>>>>>> Temporary merge branch 2
=======
A
>>>>>>> Temporary merge branch 2
but with this patch, the positions of B and A are swapped.
This is probably fine, as the order is an internal
implementation detail anyway (it would _not_ be fine if we
were using a priority queue for "git log" traversal, which
should show commits in parent order).
While we are munging the "interesting" function, we also
take the opportunity to give it a more descriptive name, and
convert the return value to an int (we returned the first
interesting commit, but nobody ever looked at it).
Signed-off-by: Jeff King <redacted>
---
This one is not strictly required for the series; it's just that I'm
adding what is essentially a clone of paint_down_to_common later in the
series. I wanted to use the priority queue there, too, so I looked into
using it here.
I'm slightly hesitant because of the stability thing mentioned above. I
_think_ it's probably fine. But we could also implement a
stable_prio_queue on top of the existing prio_queue if we're concerned
(and that may be something we want to do anyway, because "git log" would
want that if it switched to a priority queue).
I had no recollection while writing this patch, but after searching the
list for "stable priority queue", I realized that Junio and I discussed
it quite extensively a few years ago:
http://thread.gmane.org/gmane.comp.version-control.git/204386/focus=204534
I think the conclusion there is that what this patch does is acceptable.
commit.c | 42 +++++++++++++++++++-----------------------
t/t6024-recursive-merge.sh | 2 +-
2 files changed, 20 insertions(+), 24 deletions(-)
@@ -729,45 +729,41 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order sostaticconstunsignedall_flags=(PARENT1|PARENT2|STALE|RESULT);-staticstructcommit*interesting(structcommit_list*list)+staticintqueue_has_nonstale(structprio_queue*queue){-while(list){-structcommit*commit=list->item;-list=list->next;-if(commit->object.flags&STALE)-continue;-returncommit;+inti;+for(i=0;i<queue->nr;i++){+structcommit*commit=queue->array[i];+if(!(commit->object.flags&STALE))+return1;}-returnNULL;+return0;}/* all input commits in one and twos[] must have been parsed! */staticstructcommit_list*paint_down_to_common(structcommit*one,intn,structcommit**twos){-structcommit_list*list=NULL;+structprio_queuequeue={compare_commits_by_commit_date};structcommit_list*result=NULL;inti;one->object.flags|=PARENT1;-commit_list_insert_by_date(one,&list);-if(!n)-returnlist;+if(!n){+commit_list_append(one,&result);+returnresult;+}+prio_queue_put(&queue,one);+for(i=0;i<n;i++){twos[i]->object.flags|=PARENT2;-commit_list_insert_by_date(twos[i],&list);+prio_queue_put(&queue,twos[i]);}-while(interesting(list)){-structcommit*commit;+while(queue_has_nonstale(&queue)){+structcommit*commit=prio_queue_get(&queue);structcommit_list*parents;-structcommit_list*next;intflags;-commit=list->item;-next=list->next;-free(list);-list=next;-flags=commit->object.flags&(PARENT1|PARENT2|STALE);if(flags==(PARENT1|PARENT2)){if(!(commit->object.flags&RESULT)){
@@ -786,11 +782,11 @@ static struct commit_list *paint_down_to_common(struct commit *one, int n, strucif(parse_commit(p))returnNULL;p->object.flags|=flags;-commit_list_insert_by_date(p,&list);+prio_queue_put(&queue,p);}}-free_commit_list(list);+clear_prio_queue(&queue);returnresult;}
From: Jeff King <hidden> Date: 2016-06-15 23:01:45
We already have a nice-to-use bitmap implementation in
ewah/bitmap.c. It pretends to be infinitely long when asking
for a bit (and just returns 0 for bits that haven't been
allocated or set), and dynamically resizes as appropriate
when you set bits.
The cost to this is that each bitmap must store its own
pointer and length, using up to 16 bytes per bitmap on top
of the actual bit storage. This is a lot of storage (not to
mention an extra level of pointer indirection) if you are
going to store one bitmap per commit in a traversal.
These functions provide an alternative bitmap implementation
that can be used when you have a large number of fixed-size
bitmaps. See the documentation in the header file for
details and examples.
Signed-off-by: Jeff King <redacted>
---
Makefile | 1 +
bitset.h | 113 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 114 insertions(+)
create mode 100644 bitset.h
From: Jeff King <hidden> Date: 2016-06-15 23:01:45
When we are running a string-list foreach or filter, the
callback function sees only the string_list_item, along with
a void* data pointer provided by the caller. This is
sufficient for most purposes.
However, it can also be useful to know the position of the
item within the string (for example, if the data pointer
points to a secondary array in which each element
corresponds to part of the string list). We can help this
use case by providing the position to each callback.
Signed-off-by: Jeff King <redacted>
---
The diff here is noisy, and I expect in the long run that the one caller
I add to builtin/tag.c later in the series will eventually stop using
string_list entirely (in favor of a custom struct), which may leave us
with no callers that actually use the new field.
I do think the logic above is sound, though, and it's a potentially
useful thing. There may be other sites that avoid the for_each wrapper
in favor of iterating themselves simply _because_ they needed to know
the position (I would just do the same here, except that my new caller
wants to use filter_string_list, which is a little more complicated).
builtin/clone.c | 2 +-
builtin/remote.c | 12 ++++++------
notes.c | 1 +
setup.c | 1 +
string-list.c | 6 +++---
string-list.h | 9 +++++++--
test-path-utils.c | 2 +-
test-string-list.c | 2 +-
8 files changed, 21 insertions(+), 14 deletions(-)
@@ -26,8 +26,13 @@ void string_list_clear(struct string_list *list, int free_util);typedefvoid(*string_list_clear_func_t)(void*p,constchar*str);voidstring_list_clear_func(structstring_list*list,string_list_clear_func_tclearfunc);-/* Use this function or the macro below to iterate over each item */-typedefint(*string_list_each_func_t)(structstring_list_item*,void*);+/*+*Usethisfunctionorthemacrobelowtoiterateovereachitem.Eachitem+*ispassedasthefirstargumenttoaninvocationofthecallback.Thesecond+*argument,"pos",isthenumericpositionofthefirstargumentwithinthe+*list(_not_anoffsetfromthefirstitem).+*/+typedefint(*string_list_each_func_t)(structstring_list_item*,intpos,void*);intfor_each_string_list(structstring_list*list,string_list_each_func_t,void*cb_data);#define for_each_string_list_item(item,list) \
From: Jeff King <hidden> Date: 2016-06-15 23:01:45
When commands like "git branch --contains" want to know
which branches contain a particular commit, they run a
series of merge-base calculations, one per branch. This can
be very slow if you have a large number of branches.
We made "tag --contains" faster in ffc4b80 (tag: speed up
--contains calculation, 2011-06-11) by switching to a
different algorithm that caches intermediate "contains"
information from each tag we check. The downside of the new
algorithm is that it moves depth-first through the graph. So
it tends to go all the way to the roots, even if the
contained commit is near the top of history. That works OK
for tags, because repositories tend to have tags near the
roots anyway (e.g., a v0.1 or similar). The number of
commits we look at increased a little bit, but since we
avoid traversing over the same parts of history repeatedly,
it was a huge net win.
For "branch --contains", it is less clear that this is a
win. Most branches stay up to date, so we can bound a search
for a recent commit when we hit the merge base between the
commit and the branches.
The ideal would be to use the merge-base-style breadth-first
traversal, but to perform a single traversal for all tips.
The problem is that we need one bit of storage per tip in
each commit, and "struct commit" has only a fixed number of
bits. We can solve that by using a process similar to
paint_down_to_common, but instead of storing PARENT1 and
PARENT2 flags, using a commit slab to store one bit per tip.
Signed-off-by: Jeff King <redacted>
---
This is the interesting commit, and I'd really love some eyes on the
logic. It's basically paint_down_to_common but with the PARENT1 and
PARENT2 flags replaced with larger bitfields.
I haven't quite convinced myself that the stale logic in the middle is
right. The origin paint_down function checks "PARENT1 | PARENT2" to see
if we found a merge base (even though PARENT2 may represent many tips).
Here I check whether we have _any_ "left" parent flag and _any_ "right"
parent flag. I'm not sure if I actually need to be finding the merge
base of _all_ of the commits. I don't think so, and I can't find a case
where this doesn't work, but perhaps I am not being imaginative enough.
commit.c | 102 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
commit.h | 17 +++++++++++
2 files changed, 119 insertions(+)
From: Jeff King <hidden> Date: 2016-06-15 23:01:45
The newly added commit_contains function should do a better
job than our custom depth-first traversal. It should be the
same speed when going close to the roots, but much faster
when all tags are close to the searched-for commit (this
usually isn't the case, but could be if you limit the tags
with a pattern).
It also cleans up some of the more egregious pitfalls of the
original implementation, including an abuse of the
UNINTERESTING and TMP_MARK flags, an utterly confusing
calling convention (it silently caches the bits between
calls, with no checks that our "with_commit" was the same
for each call), and a failure to clean up after itself
(tainting any further traversals).
Signed-off-by: Jeff King <redacted>
---
The code to use the new contains function ends up disappointingly longer
than I would have hoped, but it has to massage our string_list of tag
names into a list of commits, and then massage the output back into a
filtered string list. It's not too bad, though. And as I mentioned, I
hope to eventually factor this out to share with for-each-ref and
branch.
builtin/tag.c | 161 +++++++++++++++++-----------------------------------------
1 file changed, 48 insertions(+), 113 deletions(-)
@@ -72,108 +72,6 @@ static const unsigned char *match_points_at(const char *refname,returnNULL;}-staticintin_commit_list(conststructcommit_list*want,structcommit*c)-{-for(;want;want=want->next)-if(!hashcmp(want->item->object.sha1,c->object.sha1))-return1;-return0;-}--enumcontains_result{-CONTAINS_UNKNOWN=-1,-CONTAINS_NO=0,-CONTAINS_YES=1,-};--/*-*Testwhetherthecandidateoroneofitsparentsiscontainedinthelist.-*Donotrecursetofindout,though,butreturn-1ifinconclusive.-*/-staticenumcontains_resultcontains_test(structcommit*candidate,-conststructcommit_list*want)-{-/* was it previously marked as containing a want commit? */-if(candidate->object.flags&TMP_MARK)-return1;-/* or marked as not possibly containing a want commit? */-if(candidate->object.flags&UNINTERESTING)-return0;-/* or are we it? */-if(in_commit_list(want,candidate)){-candidate->object.flags|=TMP_MARK;-return1;-}--if(parse_commit(candidate)<0)-return0;--return-1;-}--/*-*Mimickingtherealstack,thisstacklivesontheheap,avoidingstack-*overflows.-*-*Ateachrecursionstep,thestackitemspointstothecommitswhose-*ancestorsaretobeinspected.-*/-structstack{-intnr,alloc;-structstack_entry{-structcommit*commit;-structcommit_list*parents;-}*stack;-};--staticvoidpush_to_stack(structcommit*candidate,structstack*stack)-{-intindex=stack->nr++;-ALLOC_GROW(stack->stack,stack->nr,stack->alloc);-stack->stack[index].commit=candidate;-stack->stack[index].parents=candidate->parents;-}--staticenumcontains_resultcontains(structcommit*candidate,-conststructcommit_list*want)-{-structstackstack={0,0,NULL};-intresult=contains_test(candidate,want);--if(result!=CONTAINS_UNKNOWN)-returnresult;--push_to_stack(candidate,&stack);-while(stack.nr){-structstack_entry*entry=&stack.stack[stack.nr-1];-structcommit*commit=entry->commit;-structcommit_list*parents=entry->parents;--if(!parents){-commit->object.flags|=UNINTERESTING;-stack.nr--;-}-/*-*Ifwejustpoppedthestack,parents->itemhasbeenmarked,-*thereforecontains_testwillreturnameaningful0or1.-*/-elseswitch(contains_test(parents->item,want)){-caseCONTAINS_YES:-commit->object.flags|=TMP_MARK;-stack.nr--;-break;-caseCONTAINS_NO:-entry->parents=parents->next;-break;-caseCONTAINS_UNKNOWN:-push_to_stack(parents->item,&stack);-break;-}-}-free(stack.stack);-returncontains_test(candidate,want);-}-staticvoidshow_tag_lines(constunsignedchar*sha1,intlines){inti;
From: Jeff King <hidden> Date: 2016-06-15 23:01:45
These tests can demonstrate the changes in "tag --contains"
speed over time. The interesting points in history are:
- pre-ffc4b80, where we used a series of N merge-base
traversals
- ffc4b80 up to the current master, where we moved to a
single depth-first traversal
- the previous commit, where we moved from depth-first to
a multi-tip merge-base
The interesting cases to measure are:
- checking which tags contain a recent commit (we use
HEAD~100 here)
- checking which tags contain a very ancient commit (we
use the last commit output by rev-list)
- checking which tags contain a commit in the middle (we
use HEAD~5000, which goes back 5 years in git.git)
- all of the above, but instead of looking at all commits,
considering only recent ones (we pick the most recent
tag by its tagger date)
Here are the timings for git.git:
Test ffc4b80^ origin/master HEAD
----------------------------------------------------------------------------------------------------
7000.3: contains recent/all 1.97(1.96+0.01) 0.26(0.25+0.00) -86.8% 0.27(0.26+0.00) -86.3%
7000.4: contains recent/v2.0.1 0.08(0.08+0.00) 0.25(0.24+0.01) +212.5% 0.02(0.02+0.00) -75.0%
7000.5: contains old/all 0.90(0.89+0.00) 0.18(0.17+0.00) -80.0% 0.27(0.26+0.00) -70.0%
7000.6: contains old/v2.0.1 0.25(0.23+0.02) 0.03(0.03+0.00) -88.0% 0.25(0.24+0.00) +0.0%
7000.7: contains ancient/all 1.98(1.97+0.01) 0.26(0.24+0.01) -86.9% 0.28(0.25+0.02) -85.9%
7000.8: contains ancient/v2.0.1 1.95(1.94+0.00) 0.26(0.24+0.01) -86.7% 0.27(0.26+0.00) -86.2%
You can see that ffc4b80 vastly improved the normal case of
checking all tags. This is because we avoid walking over the
same parts of history over and over. However, when looking
only for a recent tag (v2.0.1 in these tests), it sometimes
performs much worse than the original. This is not
surprising. For a merge-base solution, we can quit when we
hit history shared between the contained commit and the tag.
For ffc4b80's depth-first approach, we typically go all the
way to the roots before backtracking. For the ancient/v2.0.1
case, that's not a big deal, because the merge base requires
us doing that anyway. But for recent/v2.0.1, the merge-base
answer should involve only recent history.
The new traversal code performs about as well as the
depth-first code in the normal case, but fixes the
regression in the recent/v2.0.1 case.
Signed-off-by: Jeff King <redacted>
---
There are still two things about the timings that puzzle me a bit.
One is that the old/all case gets slower moving from the depth-first
traversal to the merge-base one. I think this is simply because the
depth-first one may get "lucky" sometimes, and hit the commit we are
looking for on the way down. So its average case is somewhat better than
its worst case (and I would not be surprised if my choice of HEAD~5000
helps it, because it follows first parents first).
The second question is why ffc4b80^ is so much slower on the v2.0.1
tests than the new code. They should both be doing a single merge-base
traversal, and I'd expect them to take about the same amount of time
(for that matter, ancient/v2.0.1 should take the same amount of time as
the depth-first code, since they all basically have to read all of the
commits once). My guess is that there's some other speedup that has
happened in the years between ffc4b80 and now.
t/perf/p7000-tag-contains.sh | 30 ++++++++++++++++++++++++++++++
1 file changed, 30 insertions(+)
create mode 100755 t/perf/p7000-tag-contains.sh
@@ -0,0 +1,30 @@+#!/bin/sh++test_description='speed of tag --contains lookups'+../perf-lib.sh++test_perf_default_repo++test_expect_success'find reference points''+recent=$(gitrev-parseHEAD~100)&&+old=$(gitrev-parseHEAD~5000)&&+ancient=$(gitrev-list|tail-n1)+'++test_expect_success'find most recent tag''+tag=$(gitfor-each-ref--sort=-taggerdate\+--format="%(refname:short)"\+refs/tags|+head-n1)+'++fordistanceinrecentoldancient;do+contains=$(evalecho\$$distance)+formatchin"""$tag";do+test_perf"contains $distance/${match:-all}""+gittag-l--contains$contains$match+"+done+done++test_done
$ancient will always be empty, as rev-list needs a "HEAD" argument.
I also think HEAD~100 is probably _too_ recent, as it is not enough to
match any tags at all right now.
So with this patch:
Oh, hmph. The "bad" case in recent/v2.0.1 for origin/master goes away
then. Because we get "lucky" again, and the depth-first one does not
have to go all the way to the roots. So it's probably a better example
to use the original HEAD~100, which isn't actually in v2.0.1.
-Peff
Just a general question about the usage of "int" here (and at other places):
Is there a special reason for new code to allow num_bits to be negative ?
To my knowledge all the size_t definitions these days are positive,
because a size can not be negative.
As a reader of the code I always wonder if there is a special meaning with
negative values, (as the result of read() to indicate an error) but there isn't.
Should we use
"unsigned" here ?
or "unsigned int" ?
or "size_t" (Which may use 64 bits, which feels like a overkill)
Just a general question about the usage of "int" here (and at other places):
Is there a special reason for new code to allow num_bits to be negative ?
No. I usually choose "int" when the word size is not likely to matter
(i.e., we do not expect it to overflow a 32-bit integer, nor to have so
many that I need to be careful not to waste space).
Probably "unsigned int" would be a more descriptive choice.
It may also help the compiler optimize better. Assuming CHAR_BIT is 8
(i.e., most everywhere), we get:
(num_bits + 7) / 8
Presumably the compiler implements the division with a right-shift.
Marking num_bits as unsigned should let us do just a logical shift,
without worrying about the sign. And indeed, here are the signed and
unsigned versions produced by "gcc -S -O2" (for an equivalent
non-inlined function):
[signed]
leal 14(%rdi), %edx
movl %edi, %eax
addl $7, %eax
cmovs %edx, %eax
sarl $3, %eax
ret
[unsigned]
leal 7(%rdi), %eax
shrl $3, %eax
ret
Much simpler, though see below for practical considerations.
To my knowledge all the size_t definitions these days are positive,
because a size can not be negative.
size_t is perhaps a reasonable choice for the return value, given the name
"sizeof". But if you really care about using the whole range of bits there, you
need a data type for num_bits that is CHAR_BIT times larger.
Should we use
"unsigned" here ?
or "unsigned int" ?
Yes, I think so. Both are the same to the compiler. I have a vague
recollection that we prefer one over the other, but grepping seems to
find many examples of each in our code.
I'm squashing in the patch below. I couldn't measure any speed
improvement. I'm guessing because the functions are all inlined, which
means we likely get away with calculating bitset_sizeof once outside of
our loop. I think the result is still more obvious to read, though.
-Peff
---
From: Eric Sunshine <hidden> Date: 2016-06-15 23:01:46
On Wed, Jun 25, 2014 at 7:40 PM, Jeff King [off-list ref] wrote:
quoted hunk
We already have a nice-to-use bitmap implementation in
ewah/bitmap.c. It pretends to be infinitely long when asking
for a bit (and just returns 0 for bits that haven't been
allocated or set), and dynamically resizes as appropriate
when you set bits.
The cost to this is that each bitmap must store its own
pointer and length, using up to 16 bytes per bitmap on top
of the actual bit storage. This is a lot of storage (not to
mention an extra level of pointer indirection) if you are
going to store one bitmap per commit in a traversal.
These functions provide an alternative bitmap implementation
that can be used when you have a large number of fixed-size
bitmaps. See the documentation in the header file for
details and examples.
Signed-off-by: Jeff King <redacted>
---
Is it intentional or an oversight that there is no way to clear a bit
in the set?
+/*
+ * Return the bit at position "n" (see bitset_set for a description of "n").
+ */
+static inline int bitset_get(unsigned char *bits, int n)
+{
+ return !!(bits[n / CHAR_BIT] & (1 << (n % CHAR_BIT)));
+}
+
+/*
+ * Return true iff the bitsets contain the same bits. Each bitset should be the
+ * same size, and should have been allocated using bitset_sizeof(max).
+ *
+ * Note that it is not safe to check partial equality by providing a smaller
+ * "max" (we assume any bits beyond "max" up to the next CHAR_BIT boundary are
+ * zeroed padding).
+ */
+static inline int bitset_equal(unsigned char *a, unsigned char *b, int max)
+{
+ int i;
+ for (i = bitset_sizeof(max); i > 0; i--)
+ if (*a++ != *b++)
+ return 0;
+ return 1;
+}
+
+/*
+ * Bitwise-or the bitsets in "dst" and "src", and store the result in "dst".
+ *
+ * See bitset_equal for the definition of "max".
+ */
+static inline void bitset_or(unsigned char *dst, const unsigned char *src, int max)
+{
+ int i;
+ for (i = bitset_sizeof(max); i > 0; i--)
+ *dst++ |= *src++;
+}
+
+/*
+ * Returns true iff the bitset contains all zeroes.
+ *
+ * See bitset_equal for the definition of "max".
+ */
+static inline int bitset_empty(const unsigned char *bits, int max)
+{
+ int i;
+ for (i = bitset_sizeof(max); i > 0; i--, bits++)
+ if (*bits)
+ return 0;
+ return 1;
+}
+
+#endif /* BITSET_H */
--
2.0.0.566.gfe3e6b2
Is it intentional or an oversight that there is no way to clear a bit
in the set?
Intentional in the sense that I had no need for it in my series, and I
didn't think about it. I doubt many callers would want it, since commit
traversals tend to propagate bits through the graph, and then clean them
up all at once. And the right way to clean up slabbed data like this is
to just clear the slab.
Of course somebody may use the code for something besides commit
traversals. But I'd rather avoid adding dead code on the off chance that
somebody uses it later (and then gets to find out whether it even works
or not!).
-Peff