summaryrefslogtreecommitdiff
path: root/ewah/bitmap.c
AgeCommit message (Collapse)AuthorFilesLines
2020-03-02Merge branch 'jk/object-filter-with-bitmap'Libravatar Junio C Hamano1-0/+8
The object reachability bitmap machinery and the partial cloning machinery were not prepared to work well together, because some object-filtering criteria that partial clones use inherently rely on object traversal, but the bitmap machinery is an optimization to bypass that object traversal. There however are some cases where they can work together, and they were taught about them. * jk/object-filter-with-bitmap: rev-list --count: comment on the use of count_right++ pack-objects: support filters with bitmaps pack-bitmap: implement BLOB_LIMIT filtering pack-bitmap: implement BLOB_NONE filtering bitmap: add bitmap_unset() function rev-list: use bitmap filters for traversal pack-bitmap: basic noop bitmap filter infrastructure rev-list: allow commit-only bitmap traversals t5310: factor out bitmap traversal comparison rev-list: allow bitmaps when counting objects rev-list: make --count work with --objects rev-list: factor out bitmap-optimized routines pack-bitmap: refuse to do a bitmap traversal with pathspecs rev-list: fallback to non-bitmap traversal when filtering pack-bitmap: fix leak of haves/wants object lists pack-bitmap: factor out type iterator initialization
2020-02-14bitmap: add bitmap_unset() functionLibravatar Jeff King1-0/+8
We've never needed to unset an individual bit in a bitmap until now. Typically they start with all bits unset and we bitmap_set() them, or we are applying another bitmap as a mask. But the easiest way to apply an object filter to a bitmap result will be to unset the individual bits. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2020-01-23ewah/bitmap: introduce bitmap_word_alloc()Libravatar Jeff King1-4/+9
In a following commit we will need to allocate a variable number of bitmap words, instead of always 32, so let's add bitmap_word_alloc() for this purpose. Note that we have to adjust the block growth in bitmap_set(), since a caller could now use an initial size of "0" (we don't plan to do that, but it doesn't hurt to be defensive). Helped-by: Jonathan Tan <jonathantanmy@google.com> Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Christian Couder <chriscool@tuxfamily.org> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2018-06-18ewah/bitmap.c: delete unused 'bitmap_each_bit()'Libravatar Derrick Stolee1-24/+0
Reported-by: Ramsay Jones <ramsay@ramsayjones.plus.com> Signed-off-by: Derrick Stolee <dstolee@microsoft.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2018-06-18ewah/bitmap.c: delete unused 'bitmap_clear()'Libravatar Derrick Stolee1-8/+0
Reported-by: Ramsay Jones <ramsay@ramsayjones.plus.com> Signed-off-by: Derrick Stolee <dstolee@microsoft.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2017-11-09Replace Free Software Foundation address in license noticesLibravatar Todd Zullinger1-2/+1
The mailing address for the FSF has changed over the years. Rather than updating the address across all files, refer readers to gnu.org, as the GNU GPL documentation now suggests for license notices. The mailing address is retained in the full license files (COPYING and LGPL-2.1). The old address is still present in t/diff-lib/COPYING. This is intentional, as the file is used in tests and the contents are not expected to change. Signed-off-by: Todd Zullinger <tmz@pobox.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2016-02-22ewah: convert to REALLOC_ARRAY, etcLibravatar Jeff King1-12/+4
Now that we're built around xmalloc and friends, we can use helpers like REALLOC_ARRAY, ALLOC_GROW, and so on to make the code shorter and protect against integer overflow. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2016-02-22convert ewah/bitmap code to use xmallocLibravatar Jeff King1-6/+6
This code was originally written with the idea that it could be spun off into its own ewah library, and uses the overrideable ewah_malloc to do allocations. We plug in xmalloc as our ewah_malloc, of course. But over the years the ewah code itself has become more entangled with git, and the return value of many ewah_malloc sites is not checked. Let's just drop the level of indirection and use xmalloc and friends directly. This saves a few lines, and will let us adapt these sites to our more advanced malloc helpers. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2015-06-03ewah: use less generic macro nameLibravatar Jeff King1-6/+6
The ewah/ewok.h header pollutes the global namespace with "BITS_IN_WORD", without any specific notion that we are talking about the bits in an eword_t. We can give this the more specific name "BITS_IN_EWORD". Signed-off-by: Jeff King <peff@peff.net> Reviewed-by: Eric Sunshine <sunshine@sunshineco.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2015-06-03ewah/bitmap: silence warning about MASK macro redefinitionLibravatar Eric Sunshine1-8/+8
On PowerPC Mac OS X (10.5.8 "Leopard" with Xcode 3.1), system header /usr/include/ppc/param.h[1] pollutes the preprocessor namespace with a macro generically named MASK. This conflicts with the same-named macro in ewah/bitmap.c. We can avoid this conflict by using a more specific name. [1]: Included indirectly via: git-compat-util.h -> sys/sysctl.h -> sys/ucred.h -> sys/param.h -> machine/param.h -> ppc/param.h Signed-off-by: Eric Sunshine <sunshine@sunshineco.com> Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2013-12-30ewah: compressed bitmap implementationLibravatar Vicent Marti1-0/+221
EWAH is a word-aligned compressed variant of a bitset (i.e. a data structure that acts as a 0-indexed boolean array for many entries). It uses a 64-bit run-length encoding (RLE) compression scheme, trading some compression for better processing speed. The goal of this word-aligned implementation is not to achieve the best compression, but rather to improve query processing time. As it stands right now, this EWAH implementation will always be more efficient storage-wise than its uncompressed alternative. EWAH arrays will be used as the on-disk format to store reachability bitmaps for all objects in a repository while keeping reasonable sizes, in the same way that JGit does. This EWAH implementation is a mostly straightforward port of the original `javaewah` library that JGit currently uses. The library is self-contained and has been embedded whole (4 files) inside the `ewah` folder to ease redistribution. The library is re-licensed under the GPLv2 with the permission of Daniel Lemire, the original author. The source code for the C version can be found on GitHub: https://github.com/vmg/libewok The original Java implementation can also be found on GitHub: https://github.com/lemire/javaewah [jc: stripped debug-only code per Peff's $gmane/239768] Signed-off-by: Vicent Marti <tanoku@gmail.com> Signed-off-by: Jeff King <peff@peff.net> Helped-by: Ramsay Jones <ramsay@ramsay1.demon.co.uk> Signed-off-by: Junio C Hamano <gitster@pobox.com>
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-10 23:45:16 +0000