]> git.ipfire.org Git - thirdparty/git.git/commit
ewah: implement `ewah_bitmap_is_subset()`
authorTaylor Blau <me@ttaylorr.com>
Thu, 23 May 2024 21:26:20 +0000 (17:26 -0400)
committerJunio C Hamano <gitster@pobox.com>
Fri, 24 May 2024 18:40:41 +0000 (11:40 -0700)
commit10a96af8dc22ec890ffacafca52959bd61bd1a28
tree961f95e23a097272f13300baab86a798900f7e23
parent2bfc24ecf60e21b4cc4b849ad48a44d42ada36c3
ewah: implement `ewah_bitmap_is_subset()`

In order to know whether a given pseudo-merge (comprised of a "parents"
and "objects" bitmaps) is "satisfied" and can be OR'd into the bitmap
result, we need to be able to quickly determine whether the "parents"
bitmap is a subset of the current set of objects reachable on either
side of a traversal.

Implement a helper function to prepare for that, which determines
whether an EWAH bitmap (the parents bitmap from the pseudo-merge) is a
subset of a non-EWAH bitmap (in this case, the results bitmap from
either side of the traversal).

This function makes use of the EWAH iterator to avoid inflating any part
of the EWAH bitmap after we determine it is not a subset of the non-EWAH
bitmap. This "fail-fast" allows us to avoid a potentially large amount
of wasted effort.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
ewah/bitmap.c
ewah/ewok.h