1. 21 Jun, 2018 1 commit
  2. 09 Nov, 2017 1 commit
  3. 30 Dec, 2013 1 commit
    • Vicent Marti's avatar
      ewah: compressed bitmap implementation · e1273106
      Vicent Marti authored
      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: default avatarVicent Marti <tanoku@gmail.com>
      Signed-off-by: default avatarJeff King <peff@peff.net>
      Helped-by: default avatarRamsay Jones <ramsay@ramsay1.demon.co.uk>
      Signed-off-by: default avatarJunio C Hamano <gitster@pobox.com>
      e1273106