path: root/ewah/bitmap.c
AgeCommit message (Collapse)Author
2018-06-18ewah/bitmap.c: delete unused 'bitmap_each_bit()'Derrick Stolee
Reported-by: Ramsay Jones <> Signed-off-by: Derrick Stolee <> Signed-off-by: Junio C Hamano <>
2018-06-18ewah/bitmap.c: delete unused 'bitmap_clear()'Derrick Stolee
Reported-by: Ramsay Jones <> Signed-off-by: Derrick Stolee <> Signed-off-by: Junio C Hamano <>
2017-11-09Replace Free Software Foundation address in license noticesTodd Zullinger
The mailing address for the FSF has changed over the years. Rather than updating the address across all files, refer readers to, 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 <> Signed-off-by: Junio C Hamano <>
2016-02-22ewah: convert to REALLOC_ARRAY, etcJeff King
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 <> Signed-off-by: Junio C Hamano <>
2016-02-22convert ewah/bitmap code to use xmallocJeff King
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 <> Signed-off-by: Junio C Hamano <>
2015-06-03ewah: use less generic macro nameJeff King
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 <> Reviewed-by: Eric Sunshine <> Signed-off-by: Junio C Hamano <>
2015-06-03ewah/bitmap: silence warning about MASK macro redefinitionEric Sunshine
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 <> Signed-off-by: Jeff King <> Signed-off-by: Junio C Hamano <>
2013-12-30ewah: compressed bitmap implementationVicent Marti
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: The original Java implementation can also be found on GitHub: [jc: stripped debug-only code per Peff's $gmane/239768] Signed-off-by: Vicent Marti <> Signed-off-by: Jeff King <> Helped-by: Ramsay Jones <> Signed-off-by: Junio C Hamano <>