po/git.pot is normally used as-is and not regenerated by people
building git, so it is okay if an explicit "make po/git.pot" always
automatically regenerates it.  Depend on the magic FORCE target
instead of explicitly keeping track of dependencies.

This simplifies the makefile, in particular preparing for a moment
when $(LIB_H), which is part of $(LOCALIZED_C), can be computed on the
fly. It also fixes a slight breakage in which changes to perl and shell
scripts did not trigger a rebuild of po/git.pot.

We still need a dependency on GENERATED_H, to force those files to be
built when regenerating git.pot.
Signed-off-by: NJonathan Nieder <jrnieder@gmail.com>
Signed-off-by: NJeff King <peff@peff.net>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Add a getnanotime() function that returns nanoseconds since 01/01/1970 as
unsigned 64-bit integer (i.e. overflows in july 2554). This is easier to
work with than e.g. struct timeval or struct timespec. Basing the timer on
the epoch allows using the results with other time-related APIs.

To simplify adaption to different platforms, split the implementation into
a common getnanotime() and a platform-specific highres_nanos() function.

The common getnanotime() function handles errors, falling back to
gettimeofday() if highres_nanos() isn't implemented or doesn't work.

getnanotime() is also responsible for normalizing to the epoch. The offset
to the system clock is calculated only once on initialization, i.e.
manually setting the system clock has no impact on the timer (except if
the fallback gettimeofday() is in use). Git processes are typically short
lived, so we don't need to handle clock drift.

The highres_nanos() function returns monotonically increasing nanoseconds
relative to some arbitrary point in time (e.g. system boot), or 0 on
failure. Providing platform-specific implementations should be relatively
easy, e.g. adapting to clock_gettime() as defined by the POSIX realtime
extensions is seven lines of code.

This version includes highres_nanos() implementations for:
 * Linux: using clock_gettime(CLOCK_MONOTONIC)
 * Windows: using QueryPerformanceCounter()

Todo:
 * enable clock_gettime() on more platforms
 * add Mac OSX version, e.g. using mach_absolute_time + mach_timebase_info
Signed-off-by: NKarsten Blees <blees@dcon.de>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Profile feedback always failed for me with -jN. The problem
was that there was no implicit ordering between the profile generate
stage and the profile use stage. So some objects in the later stage
would be linked with profile generate objects, and fail due
to the missing -lgcov.

This adds a new profile target that implicitely enforces the
correct ordering by using submakes. Plus a profile-install target
to also install. This is also nicer to type that PROFILE=...

Plus I always run the performance test suite now for the full
profile run.

In addition I also added a profile-fast / profile-fast-install
target the only runs the performance test suite instead of the
whole test suite. This significantly speeds up the profile build,
which was totally dominated by test suite run time. However
it may have less coverage of course.
Signed-off-by: NAndi Kleen <ak@linux.intel.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Signed-off-by: NAndi Kleen <ak@linux.intel.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Use BASIC_CFLAGS instead of CFLAGS to set up the profile feedback
option in the Makefile.

This allows still overriding CFLAGS on the make command line
without disabling profile feedback.
Signed-off-by: NAndi Kleen <ak@linux.intel.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Commit signatures can be verified using "git show -s --show-signature"
or the "%G?" pretty format and parsing the output, which is well suited
for user inspection, but not for scripting.

Provide a command "verify-commit" which is analogous to "verify-tag": It
returns 0 for good signatures and non-zero otherwise, has the gpg output
on stderr and (optionally) the commit object on stdout, sans the
signature, just like "verify-tag" does.
Signed-off-by: NMichael J Gruber <git@drmicha.warpmail.net>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Signed-off-by: NNguyễn Thái Ngọc Duy <pclouds@gmail.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

This split-index mode is designed to keep write cost proportional to
the number of changes the user has made, not the size of the work
tree. (Read cost is another matter, to be dealt separately.)

This mode stores index info in a pair of $GIT_DIR/index and
$GIT_DIR/sharedindex.<SHA-1>. sharedindex is large and unchanged over
time while "index" is smaller and updated often. Format details are in
index-format.txt, although not everything is implemented in this
patch.

Shared indexes are not automatically removed, because it's unclear if
the shared index is needed by any (even temporary) indexes by just
looking at it. After a while you'll collect stale shared indexes. The
good news is one shared index is useable for long, until
$GIT_DIR/index becomes too big and sluggish that the new shared index
must be created.

The safest way to clean shared indexes is to turn off split index
mode, so shared files are all garbage, delete them all, then turn on
split index mode again.
Signed-off-by: NNguyễn Thái Ngọc Duy <pclouds@gmail.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

The function git_wcwidth() returns for a given unicode code point the
width on the display:

 -1 for control characters,
  0 for combining or other non-visible code points
  1 for e.g. ASCII
  2 for double-width code points.

This table had been originally been extracted for one Unicode
version, probably 3.2.

We now use two tables these days, one for zero-width and another for
double-width.  Make it easier to update these tables to a later
version of Unicode by factoring out the table from utf8.c into
unicode_width.h and add the script update_unicode.sh to update the
table based on the latest Unicode specification files.

Thanks to Peter Krefting <peter@softwolves.pp.se> and Kevin Bracey
<kevin@bracey.fi> for helping with their Unicode knowledge.
Signed-off-by: NTorsten Bögershausen <tboegi@web.de>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Postpone this a bit during the feature freeze and retry the effort
in the next cycle.

The original implementation of CURL_CONFIG support did not match the
original behavior of using -lcurl when CURLDIR was not set. This broke
implementations that were lacking curl-config but did have libcurl
installed along system libraries, such as MSysGit. In other words, the
assumption that curl-config is always installed was incorrect.

Instead, if CURL_CONFIG is empty or returns an empty result (e.g. due
to curl-config being missing), use the old behavior of falling back to
-lcurl.
Signed-off-by: NDave Borowitz <dborowitz@google.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

When extract l10n messages, we use "--add-comments" option to keep
comments right above the l10n messages for references.  But sometimes
irrelevant comments are also extracted.  For example in the following
code block, the comment in line 2 will be extracted as comment for the
l10n message in line 3, but obviously it's wrong.

        { OPTION_CALLBACK, 0, "ignore-removal", &addremove_explicit,
          NULL /* takes no arguments */,
          N_("ignore paths removed in the working tree (same as
          --no-all)"),
          PARSE_OPT_NOARG, ignore_removal_cb },

Since almost all comments for l10n translators are marked with the same
prefix (tag): "TRANSLATORS:", it's safe to only extract comments with
this special tag.  I.E. it's better to call xgettext as:

        xgettext --add-comments=TRANSLATORS: ...

Also tweaks the multi-line comment in "init-db.c", to make it start with
the proper tag, not "* TRANSLATORS:" (which has a star before the tag).
Signed-off-by: NJiang Xin <worldhello.net@gmail.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Multi-threaing of index-pack was disabled with c0f86547
(index-pack: Disable threading on cygwin - 2012-06-26), because
pread() implementations for Cygwin and MSYS were not thread
safe.  Recent Cygwin does offer usable pread() and we enabled
multi-threading with 103d530f (Cygwin 1.7 has thread-safe pread,
2013-07-19).

Work around this problem on platforms with a thread-unsafe
pread() emulation by opening one file handle per thread; it
would prevent parallel pread() on different file handles from
stepping on each other.

Also remove NO_THREAD_SAFE_PREAD that was introduced in c0f86547
because it's no longer used anywhere.

This workaround is unconditional, even for platforms with
thread-safe pread() because the overhead is small (a couple file
handles more) and not worth fragmenting the code.
Signed-off-by: NNguyễn Thái Ngọc Duy <pclouds@gmail.com>
Tested-by: NJohannes Sixt <j6t@kdbg.org>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

This requires more flags than can be guessed with the old-style
CURLDIR and related options, so is only supported when curl-config is
present.
Signed-off-by: NDave Borowitz <dborowitz@google.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

curl-config should always be installed alongside a curl distribution,
and its purpose is to provide flags for building against libcurl, so
use it instead of guessing flags and dependent libraries.

Allow overriding CURL_CONFIG to a custom path to curl-config, to
compile against a curl installation other than the first in PATH.

Depending on the set of features curl is compiled with, there may be
more libraries required than the previous two options of -lssl and
-lidn. For example, with a vanilla build of libcurl-7.36.0 on Mac OS X
10.9:

$ ~/d/curl-out-7.36.0/lib/curl-config --libs
-L/Users/dborowitz/d/curl-out-7.36.0/lib -lcurl -lgssapi_krb5 -lresolv -lldap -lz

Use this only when CURLDIR is not explicitly specified, to continue
supporting older builds.
Signed-off-by: NDave Borowitz <dborowitz@google.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Most gmtime implementations return a NULL value when they
encounter an error (and this behavior is specified by ANSI C
and POSIX).  FreeBSD's implementation, however, will simply
leave the "struct tm" untouched.  Let's also recognize this
and convert it to a NULL (with this patch, t4212 should pass
on FreeBSD).
Reported-by: NRené Scharfe <l.s.r@web.de>
Signed-off-by: NJeff King <peff@peff.net>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Signed-off-by: NJustin Lebar <jlebar@google.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

In the next patch we'll have to use alloca() for performance reasons,
but since alloca is non-standardized and is not portable, let's have a
trick with compatibility wrappers:

1. at configure time, determine, do we have working alloca() through
   alloca.h, and define

    #define HAVE_ALLOCA_H

   if yes.

2. in code

    #ifdef HAVE_ALLOCA_H
    # include <alloca.h>
    # define xalloca(size)      (alloca(size))
    # define xalloca_free(p)    do {} while(0)
    #else
    # define xalloca(size)      (xmalloc(size))
    # define xalloca_free(p)    (free(p))
    #endif

   and use it like

   func() {
       p = xalloca(size);
       ...

       xalloca_free(p);
   }

This way, for systems, where alloca is available, we'll have optimal
on-stack allocations with fast executions. On the other hand, on
systems, where alloca is not available, this gracefully fallbacks to
xmalloc/free.

Both autoconf and config.mak.uname configurations were updated. For
autoconf, we are not bothering considering cases, when no alloca.h is
available, but alloca() works some other way - its simply alloca.h is
available and works or not, everything else is deep legacy.

For config.mak.uname, I've tried to make my almost-sure guess for where
alloca() is available, but since I only have access to Linux it is the
only change I can be sure about myself, with relevant to other changed
systems people Cc'ed.

NOTE

SunOS and Windows had explicit -DHAVE_ALLOCA_H in their configurations.
I've changed that to now-common HAVE_ALLOCA_H=YesPlease which should be
correct.

Cc: Brandon Casey <drafnel@gmail.com>
Cc: Marius Storm-Olsen <mstormo@gmail.com>
Cc: Johannes Sixt <j6t@kdbg.org>
Cc: Johannes Schindelin <Johannes.Schindelin@gmx.de>
Cc: Ramsay Jones <ramsay@ramsay1.demon.co.uk>
Cc: Gerrit Pape <pape@smarden.org>
Cc: Petr Salinger <Petr.Salinger@seznam.cz>
Cc: Jonathan Nieder <jrnieder@gmail.com>
Acked-by: Thomas Schwinge <thomas@codesourcery.com> (GNU Hurd changes)
Signed-off-by: NKirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

The original explanation was not even grammatically correct or
readable.
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

--sort=version:refname (or --sort=v:refname for short) sorts tags as
if they are versions. --sort=-refname reverses the order (with or
without ":version").

versioncmp() is copied from string/strverscmp.c in glibc commit
ee9247c38a8def24a59eb5cfb7196a98bef8cfdc, reformatted to Git coding
style. The implementation is under LGPL-2.1 and according to [1] I can
relicense it to GPLv2.

[1] http://www.gnu.org/licenses/gpl-faq.html#AllCompatibilitySigned-off-by: NNguyễn Thái Ngọc Duy <pclouds@gmail.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Allow adding a TEST_GIT_INDEX_VERSION variable to config.mak to set the
index version with which the test suite should be run.

If it isn't set, the default version given in the source code is
used (currently version 3).

To avoid breakages with index versions other than [23], also set the
index version under which t2104 is run to 3.  This test only tests
functionality specific to version 2 and 3 of the index file and would
fail if the test suite is run with any other version.
Helped-by: NJunio C Hamano <gitster@pobox.com>
Signed-off-by: NThomas Gummerer <t.gummerer@gmail.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Since v1.8.4 (about six months ago) wildmatch is used as default
replacement for fnmatch. We have seen only one fix since so wildmatch
probably has done a good job as fnmatch replacement. This concludes
the fnmatch->wildmatch transition by no longer relying on fnmatch.
Signed-off-by: NNguyễn Thái Ngọc Duy <pclouds@gmail.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

revision.o is included in libgit.a which is in $(GITLIBS), so we don't
need to include is separately.  This fixes compilation with
"-fwhole-program" which otherwise fails with messages like this:

  libgit.a(revision.o): In function `mark_tree_uninteresting':
  /home/john/src/git/revision.c:108: multiple definition of `mark_tree_uninteresting'
  /tmp/ccKQRkZV.ltrans2.ltrans.o:/home/john/src/git/revision.c:108: first defined here
Signed-off-by: NJohn Keeping <john@keeping.me.uk>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

If the git version number consists of less than three period
separated numbers, then the Windows resource file compilation
issues a syntax error:

  $ touch git.rc
  $ make V=1 git.res
  GIT_VERSION = 1.9.rc0
  windres -O coff \
            -DMAJOR=1 -DMINOR=9 -DPATCH=rc0 \
            -DGIT_VERSION="\\\"1.9.rc0\\\"" git.rc -o git.res
  C:\msysgit\msysgit\mingw\bin\windres.exe: git.rc:2: syntax error
  make: *** [git.res] Error 1
  $

Note that -DPATCH=rc0.

The values passed via -DMAJOR=, -DMINOR=, and -DPATCH= are used in
FILEVERSION and PRODUCTVERSION statements, which expect up to four numeric
values. These version numbers are intended for machine consumption. They
are typically inspected by installers to decide whether a file to be
installed is newer than one that exists on the system, but are not used
for much else.

We can be pretty certain that there are no tools that look at these
version numbers, not even the installer of Git for Windows does.
Therefore, to fix the syntax error, fill in only the first two numbers,
which we are guaranteed to find in Git version numbers.
Signed-off-by: NJohannes Sixt <j6t@kdbg.org>
Acked-by: NPat Thoyts <patthoyts@users.sourceforge.net>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

This commit extends more the functionality of `pack-objects` by allowing
it to write out a `.bitmap` index next to any written packs, together
with the `.idx` index that currently gets written.

If bitmap writing is enabled for a given repository (either by calling
`pack-objects` with the `--write-bitmap-index` flag or by having
`pack.writebitmaps` set to `true` in the config) and pack-objects is
writing a packfile that would normally be indexed (i.e. not piping to
stdout), we will attempt to write the corresponding bitmap index for the
packfile.

Bitmap index writing happens after the packfile and its index has been
successfully written to disk (`finish_tmp_packfile`). The process is
performed in several steps:

    1. `bitmap_writer_set_checksum`: this call stores the partial
       checksum for the packfile being written; the checksum will be
       written in the resulting bitmap index to verify its integrity

    2. `bitmap_writer_build_type_index`: this call uses the array of
       `struct object_entry` that has just been sorted when writing out
       the actual packfile index to disk to generate 4 type-index bitmaps
       (one for each object type).

       These bitmaps have their nth bit set if the given object is of
       the bitmap's type. E.g. the nth bit of the Commits bitmap will be
       1 if the nth object in the packfile index is a commit.

       This is a very cheap operation because the bitmap writing code has
       access to the metadata stored in the `struct object_entry` array,
       and hence the real type for each object in the packfile.

    3. `bitmap_writer_reuse_bitmaps`: if there exists an existing bitmap
       index for one of the packfiles we're trying to repack, this call
       will efficiently rebuild the existing bitmaps so they can be
       reused on the new index. All the existing bitmaps will be stored
       in a `reuse` hash table, and the commit selection phase will
       prioritize these when selecting, as they can be written directly
       to the new index without having to perform a revision walk to
       fill the bitmap. This can greatly speed up the repack of a
       repository that already has bitmaps.

    4. `bitmap_writer_select_commits`: if bitmap writing is enabled for
       a given `pack-objects` run, the sequence of commits generated
       during the Counting Objects phase will be stored in an array.

       We then use that array to build up the list of selected commits.
       Writing a bitmap in the index for each object in the repository
       would be cost-prohibitive, so we use a simple heuristic to pick
       the commits that will be indexed with bitmaps.

       The current heuristics are a simplified version of JGit's
       original implementation. We select a higher density of commits
       depending on their age: the 100 most recent commits are always
       selected, after that we pick 1 commit of each 100, and the gap
       increases as the commits grow older. On top of that, we make sure
       that every single branch that has not been merged (all the tips
       that would be required from a clone) gets their own bitmap, and
       when selecting commits between a gap, we tend to prioritize the
       commit with the most parents.

       Do note that there is no right/wrong way to perform commit
       selection; different selection algorithms will result in
       different commits being selected, but there's no such thing as
       "missing a commit". The bitmap walker algorithm implemented in
       `prepare_bitmap_walk` is able to adapt to missing bitmaps by
       performing manual walks that complete the bitmap: the ideal
       selection algorithm, however, would select the commits that are
       more likely to be used as roots for a walk in the future (e.g.
       the tips of each branch, and so on) to ensure a bitmap for them
       is always available.

    5. `bitmap_writer_build`: this is the computationally expensive part
       of bitmap generation. Based on the list of commits that were
       selected in the previous step, we perform several incremental
       walks to generate the bitmap for each commit.

       The walks begin from the oldest commit, and are built up
       incrementally for each branch. E.g. consider this dag where A, B,
       C, D, E, F are the selected commits, and a, b, c, e are a chunk
       of simplified history that will not receive bitmaps.

            A---a---B--b--C--c--D
                     \
                      E--e--F

       We start by building the bitmap for A, using A as the root for a
       revision walk and marking all the objects that are reachable
       until the walk is over. Once this bitmap is stored, we reuse the
       bitmap walker to perform the walk for B, assuming that once we
       reach A again, the walk will be terminated because A has already
       been SEEN on the previous walk.

       This process is repeated for C, and D, but when we try to
       generate the bitmaps for E, we can reuse neither the current walk
       nor the bitmap we have generated so far.

       What we do now is resetting both the walk and clearing the
       bitmap, and performing the walk from scratch using E as the
       origin. This new walk, however, does not need to be completed.
       Once we hit B, we can lookup the bitmap we have already stored
       for that commit and OR it with the existing bitmap we've composed
       so far, allowing us to limit the walk early.

       After all the bitmaps have been generated, another iteration
       through the list of commits is performed to find the best XOR
       offsets for compression before writing them to disk. Because of
       the incremental nature of these bitmaps, XORing one of them with
       its predecesor results in a minimal "bitmap delta" most of the
       time. We can write this delta to the on-disk bitmap index, and
       then re-compose the original bitmaps by XORing them again when
       loaded.

       This is a phase very similar to pack-object's `find_delta` (using
       bitmaps instead of objects, of course), except the heuristics
       have been greatly simplified: we only check the 10 bitmaps before
       any given one to find best compressing one. This gives good
       results in practice, because there is locality in the ordering of
       the objects (and therefore bitmaps) in the packfile.

     6. `bitmap_writer_finish`: the last step in the process is
	serializing to disk all the bitmap data that has been generated
	in the two previous steps.

	The bitmap is written to a tmp file and then moved atomically to
	its final destination, using the same process as
	`pack-write.c:write_idx_file`.
Signed-off-by: NVicent Marti <tanoku@gmail.com>
Signed-off-by: NJeff King <peff@peff.net>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

A bitmap index is a `.bitmap` file that can be found inside
`$GIT_DIR/objects/pack/`, next to its corresponding packfile, and
contains precalculated reachability information for selected commits.
The full specification of the format for these bitmap indexes can be found
in `Documentation/technical/bitmap-format.txt`.

For a given commit SHA1, if it happens to be available in the bitmap
index, its bitmap will represent every single object that is reachable
from the commit itself. The nth bit in the bitmap is the nth object in
the packfile; if it's set to 1, the object is reachable.

By using the bitmaps available in the index, this commit implements
several new functions:

	- `prepare_bitmap_git`
	- `prepare_bitmap_walk`
	- `traverse_bitmap_commit_list`
	- `reuse_partial_packfile_from_bitmap`

The `prepare_bitmap_walk` function tries to build a bitmap of all the
objects that can be reached from the commit roots of a given `rev_info`
struct by using the following algorithm:

- If all the interesting commits for a revision walk are available in
the index, the resulting reachability bitmap is the bitwise OR of all
the individual bitmaps.

- When the full set of WANTs is not available in the index, we perform a
partial revision walk using the commits that don't have bitmaps as
roots, and limiting the revision walk as soon as we reach a commit that
has a corresponding bitmap. The earlier OR'ed bitmap with all the
indexed commits can now be completed as this walk progresses, so the end
result is the full reachability list.

- For revision walks with a HAVEs set (a set of commits that are deemed
uninteresting), first we perform the same method as for the WANTs, but
using our HAVEs as roots, in order to obtain a full reachability bitmap
of all the uninteresting commits. This bitmap then can be used to:

	a) limit the subsequent walk when building the WANTs bitmap
	b) finding the final set of interesting commits by performing an
	   AND-NOT of the WANTs and the HAVEs.

If `prepare_bitmap_walk` runs successfully, the resulting bitmap is
stored and the equivalent of a `traverse_commit_list` call can be
performed by using `traverse_bitmap_commit_list`; the bitmap version
of this call yields the objects straight from the packfile index
(without having to look them up or parse them) and hence is several
orders of magnitude faster.

As an extra optimization, when `prepare_bitmap_walk` succeeds, the
`reuse_partial_packfile_from_bitmap` call can be attempted: it will find
the amount of objects at the beginning of the on-disk packfile that can
be reused as-is, and return an offset into the packfile. The source
packfile can then be loaded and the bytes up to `offset` can be written
directly to the result without having to consider the entires inside the
packfile individually.

If the `prepare_bitmap_walk` call fails (e.g. because no bitmap files
are available), the `rev_info` struct is left untouched, and can be used
to perform a manual rev-walk using `traverse_commit_list`.

Hence, this new set of functions are a generic API that allows to
perform the equivalent of

	git rev-list --objects [roots...] [^uninteresting...]

for any set of commits, even if they don't have specific bitmaps
generated for them.

In further patches, we'll use this bitmap traversal optimization to
speed up the `pack-objects` and `rev-list` commands.
Signed-off-by: NVicent Marti <tanoku@gmail.com>
Signed-off-by: NJeff King <peff@peff.net>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

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: NVicent Marti <tanoku@gmail.com>
Signed-off-by: NJeff King <peff@peff.net>
Helped-by: NRamsay Jones <ramsay@ramsay1.demon.co.uk>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

When the built-in "git tar-tree" command (a thin wrapper around "git
archive") was removed in 925ceccf (tar-tree: remove deprecated
command, 2013-11-10), the build continued to install a non-functioning
git-tar-tree command in gitexecdir by mistake:

	$ PATH=$(git --exec-path):$PATH
	$ git-tar-tree -h
	fatal: cannot handle tar-tree internally

The list of links in gitexecdir is populated from BUILTIN_OBJS, which
includes builtin/tar-tree.o to implement "git get-tar-commit-id".
Rename the get-tar-commit-id source file to builtin/get-tar-commit-id.c
to reflect its purpose and fix 'make install'.
Signed-off-by: NJonathan Nieder <jrnieder@gmail.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Some platforms ship Perl modules used by git scripts outside the
default perl path (e.g., on Mac OS X, Subversion's perl bindings live
in a separate xcode perl path).  Add an PERLLIB_EXTRA variable to hold
a colon-separated list of extra directories to add to the perl path in
git's scripts, as a convenience for packagers.
Requested-by: NDave Borowitz <dborowitz@google.com>
Signed-off-by: NJonathan Nieder <jrnieder@gmail.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Signed-off-by: NJonathan Nieder <jrnieder@gmail.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Signed-off-by: NKarsten Blees <blees@dcon.de>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

The existing hashtable implementation (in hash.[ch]) uses open addressing
(i.e. resolve hash collisions by distributing entries across the table).
Thus, removal is difficult to implement with less than O(n) complexity.
Resolving collisions of entries with identical hashes (e.g. via chaining)
is left to the client code.

Add a hashtable implementation that supports O(1) removal and is slightly
easier to use due to builtin entry chaining.

Supports all basic operations init, free, get, add, remove and iteration.

Also includes ready-to-use hash functions based on the public domain FNV-1
algorithm (http://www.isthe.com/chongo/tech/comp/fnv).

The per-entry data structure (hashmap_entry) is piggybacked in front of
the client's data structure to save memory. See test-hashmap.c for usage
examples.

The hashtable is resized by a factor of four when 80% full. With these
settings, average memory consumption is about 2/3 of hash.[ch], and
insertion is about twice as fast due to less frequent resizing.

Lookups are also slightly faster, because entries are strictly confined to
their bucket (i.e. no data of other buckets needs to be traversed).
Signed-off-by: NKarsten Blees <blees@dcon.de>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Signed-off-by: NMasanari Iida <standby24x7@gmail.com>
Signed-off-by: NPat Thoyts <patthoyts@users.sourceforge.net>

This has been deprecated since commit 87194d26 (Deprecate peek-remote,
2007-11-24), included in version 1.5.4.
Signed-off-by: NJohn Keeping <john@keeping.me.uk>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

"git lost-found" has been deprecated since commit fc8b5f03 (Deprecate
git-lost-found, 2007-11-08), included in version 1.5.4.
Signed-off-by: NJohn Keeping <john@keeping.me.uk>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

The release notes for Git 1.5.4 say that "git repo-config" will be
removed in the next feature release.  Since Git 2.0 is nearly here,
remove it.
Signed-off-by: NJohn Keeping <john@keeping.me.uk>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

The hash table that stores the packing list for a given `pack-objects`
run was tightly coupled to the pack-objects code.

In this commit, we refactor the hash table and the underlying storage
array into a `packing_data` struct. The functionality for accessing and
adding entries to the packing list is hence accessible from other parts
of Git besides the `pack-objects` builtin.

This refactoring is a requirement for further patches in this series
that will require accessing the commit packing list from outside of
`pack-objects`.

The hash table implementation has been minimally altered: we now
use table sizes which are always a power of two, to ensure a uniform
index distribution in the array.
Signed-off-by: NVicent Marti <tanoku@gmail.com>
Signed-off-by: NJeff King <peff@peff.net>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Sparse issues an "using sizeof on a function" warning for each
call to curl_easy_setopt() which sets an option that takes a
function pointer parameter. (currently 12 such warnings over 4
files.)

The warnings relate to the use of the "typecheck-gcc.h" header
file which adds a layer of type-checking macros to the curl
function invocations (for gcc >= 4.3 and !__cplusplus). As part
of the type-checking layer, 'sizeof' is applied to the function
parameter of curl_easy_setopt(). Note that, in the context of
sizeof, the function to function pointer conversion is not
performed and that sizeof(f) != sizeof(&f).

A simple solution, therefore, would be to replace the function
name in each such call to curl_easy_setopt() with an explicit
function pointer expression (i.e. replace f with &f).

However, the "typecheck-gcc.h" header file is only conditionally
included, in addition to the gcc and C++ checks mentioned above,
depending on the CURL_DISABLE_TYPECHECK preprocessor variable.

In order to suppress the warnings, we use target-specific variable
assignments to add -DCURL_DISABLE_TYPECHECK to SPARSE_FLAGS for
each file affected (http-push.c, http.c, http-walker.c and
remote-curl.c).
Signed-off-by: NRamsay Jones <ramsay@ramsay1.demon.co.uk>
Signed-off-by: NJonathan Nieder <jrnieder@gmail.com>

The motivation of this patch is to get closer to a goal of being
able to have a core subset of git functionality built in to git.
That would mean

 * people on Windows could get a copy of at least the core parts
   of Git without having to install a Unix-style shell

 * people using git in on servers with chrooted environments
   do not need to worry about standard tools lacking for shell
   scripts.

This patch is meant to be mostly a literal translation of the
git-repack script; the intent is that later patches would start using
more library facilities, but this patch is meant to be as close to a
no-op as possible so it doesn't do that kind of thing.
Signed-off-by: NStefan Beller <stefanbeller@googlemail.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

When it was originally added, the git_remote_helpers library was used as
part of the tests of the remote-helper interface, but since commit
fc407f98 (Add new simplified git-remote-testgit, 2012-11-28) a simple
shell script is used for this.

A search on Ohloh [1] indicates that this library isn't used by any
external projects and even the Python remote helpers in contrib/ don't
use this library, so it is only used by its own test suite.

Since this is the only Python library in Git, removing it will make
packaging easier as the Python scripts only need to be installed for one
version of Python, whereas the library should be installed for all
available versions.

[1] http://code.ohloh.net/search?s=%22git_remote_helpers%22Signed-off-by: NJohn Keeping <john@keeping.me.uk>
Acked-by: NSverre Rabbelier <srabbelier@gmail.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>