path: root/ewah/ewok.h
AgeCommit message (Collapse)Author
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-24Merge branch 'es/osx-header-pollutes-mask-macro'Junio C Hamano
* es/osx-header-pollutes-mask-macro: ewah: use less generic macro name ewah/bitmap: silence warning about MASK macro redefinition
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-03-12ewah: add convenient wrapper ewah_serialize_strbuf()Nguyễn Thái Ngọc Duy
Signed-off-by: Nguyễn Thái Ngọc Duy <> Signed-off-by: Junio C Hamano <>
2015-02-18Merge branch 'jk/pack-bitmap'Junio C Hamano
The pack bitmap support did not build with older versions of GCC. * jk/pack-bitmap: ewah: fix building with gcc < 3.4.0
2015-02-04ewah: fix building with gcc < 3.4.0Tom G. Christensen
The __builtin_ctzll function was added in gcc 3.4.0. This extends the check for gcc so that use of __builtin_ctzll is only enabled if gcc >= 3.4.0. Signed-off-by: Tom G. Christensen <> Reviewed-by: Jeff King <> Signed-off-by: Junio C Hamano <>
2014-04-29ewah: delete unused ewah_read_mmap_native declarationNguyễn Thái Ngọc Duy
Signed-off-by: Nguyễn Thái Ngọc Duy <> Signed-off-by: Junio C Hamano <>
2014-04-29ewah: fix constness of ewah_read_mmapNguyễn Thái Ngọc Duy
Signed-off-by: Nguyễn Thái Ngọc Duy <> 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 <>