| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
Currently, when looking for a packed object from the pack idx, a
simple binary search is used.
A conventional binary search loop looks like this:
unsigned lo, hi;
do {
unsigned mi = (lo + hi) / 2;
int cmp = "entry pointed at by mi" minus "target";
if (!cmp)
return mi; "mi is the wanted one"
if (cmp > 0)
hi = mi; "mi is larger than target"
else
lo = mi+1; "mi is smaller than target"
} while (lo < hi);
"did not find what we wanted"
The invariants are:
- When entering the loop, 'lo' points at a slot that is never
above the target (it could be at the target), 'hi' points at
a slot that is guaranteed to be above the target (it can
never be at the target).
- We find a point 'mi' between 'lo' and 'hi' ('mi' could be
the same as 'lo', but never can be as high as 'hi'), and
check if 'mi' hits the target. There are three cases:
- if it is a hit, we have found what we are looking for;
- if it is strictly higher than the target, we set it to
'hi', and repeat the search.
- if it is strictly lower than the target, we update 'lo'
to one slot after it, because we allow 'lo' to be at the
target and 'mi' is known to be below the target.
If the loop exits, there is no matching entry.
When choosing 'mi', we do not have to take the "middle" but
anywhere in between 'lo' and 'hi', as long as lo <= mi < hi is
satisfied. When we somehow know that the distance between the
target and 'lo' is much shorter than the target and 'hi', we
could pick 'mi' that is much closer to 'lo' than (hi+lo)/2,
which a conventional binary search would pick.
This patch takes advantage of the fact that the SHA-1 is a good
hash function, and as long as there are enough entries in the
table, we can expect uniform distribution. An entry that begins
with for example "deadbeef..." is much likely to appear much
later than in the midway of a reasonably populated table. In
fact, it can be expected to be near 87% (222/256) from the top
of the table.
This is a work-in-progress and has switches to allow easier
experiments and debugging. Exporting GIT_USE_LOOKUP environment
variable enables this code.
On my admittedly memory starved machine, with a partial KDE
repository (3.0G pack with 95M idx):
$ GIT_USE_LOOKUP=t git log -800 --stat HEAD >/dev/null
3.93user 0.16system 0:04.09elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+55588minor)pagefaults 0swaps
Without the patch, the numbers are:
$ git log -800 --stat HEAD >/dev/null
4.00user 0.15system 0:04.17elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+60258minor)pagefaults 0swaps
In the same repository:
$ GIT_USE_LOOKUP=t git log -2000 HEAD >/dev/null
0.12user 0.00system 0:00.12elapsed 97%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+4241minor)pagefaults 0swaps
Without the patch, the numbers are:
$ git log -2000 HEAD >/dev/null
0.05user 0.01system 0:00.07elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+8506minor)pagefaults 0swaps
There isn't much time difference, but the number of minor faults
seems to show that we are touching much smaller number of pages,
which is expected.
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
The earlier one did not correctly propagate GITWEB_CONFIG_SYSTEM from
Makefile to generated gitweb.cgi script.
Signed-off-by: Gerrit Pape <pape@smarden.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
From a distribution point of view, configuration files for applications
should reside in /etc/. On the other hand it's convenient for multiple
instances of gitweb (e.g. virtual web servers on a single machine) to have
a per-instance configuration file, just as gitweb currently supports
through the file gitweb_config.perl next to the cgi.
To support both at runtime, this commit introduces GITWEB_CONFIG_SYSTEM as
a system-wide configuration file which will be used as a fallback if the
config file sprecified throug GITWEB_CONFIG does not exist.
See also
http://bugs.debian.org/450592
Signed-off-by: Gerrit Pape <pape@smarden.org>
Acked-by: Jakub Narebski <jnareb@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
* jc/makefile:
Makefile: flatten enumeration of headers, objects and programs
Makefile: DIFF_OBJS is not special at all these days
|
|
On some systems, 'sh' isn't very friendly. In particular,
t7003 fails on Solaris because it doesn't understand $().
Instead, use the specified SHELL_PATH to run shell code.
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Previously, we just chose whether to allow external grep
based on the __unix__ define. However, there are systems
which define this macro but which have an inferior group
(e.g., one that does not support all options used by t7002).
This allows users to accept the potential speed penalty to
get a more consistent grep experience (and to pass the
testsuite).
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
With flattened one-line-per-item list that is sorted, hopefully we will
have less merge conflicts when various topics are merged.
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
It used to make sense back when nothing but diff-files, diff-index and
friends depended on diffcore infrastructure, but pretty much everything
depends on revision infrastructure which in turn depends on DIFF_OBJS.
There is no reason to treat them any differently in the Makefile.
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
* js/remote:
"remote update": print remote name being fetched from
builtin remote rm: remove symbolic refs, too
remote: fix "update [group...]"
remote show: Clean up connection correctly if object fetch wasn't done
builtin-remote: prune remotes correctly that were added with --mirror
Make git-remote a builtin
Test "git remote show" and "git remote prune"
parseopt: add flag to stop on first non option
path-list: add functions to work with unsorted lists
Conflicts:
parse-options.c
|
|
* 'jc/cherry-pick' (early part):
expose a helper function peel_to_type().
merge-recursive: split low-level merge functions out.
Conflicts:
Makefile
builtin-merge-recursive.c
sha1_name.c
|
|
* mr/compat-snprintf:
Add compat/snprintf.c for systems that return bogus
|
|
Some systems (namely HPUX and Windows) return -1 when maxsize in snprintf()
and in vsnprintf() is reached. So replace snprintf() and vsnprintf()
functions with our own ones that return correct value upon overflow.
[jc: verified that review comments by J6t have been incorporated, and
tightened the check to verify the resulting buffer contents, suggested
by Wayne Davison]
Signed-off-by: Michal Rokos <michal.rokos@nextsoft.cz>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
It does not allow changing the bit to a non-root user.
This fixes t1301-shared-repo.sh on the platform.
Signed-off-by: Alex Riesen <raa.lkml@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
* np/verify-pack:
add storage size output to 'git verify-pack -v'
fix unimplemented packed_object_info_detail() features
make verify_one_pack() a bit less wrong wrt packed_git structure
factorize revindex code out of builtin-pack-objects.c
Conflicts:
Makefile
|
|
* mk/maint-parse-careful:
receive-pack: use strict mode for unpacking objects
index-pack: introduce checking mode
unpack-objects: prevent writing of inconsistent objects
unpack-object: cache for non written objects
add common fsck error printing function
builtin-fsck: move common object checking code to fsck.c
builtin-fsck: reports missing parent commits
Remove unused object-ref code
builtin-fsck: move away from object-refs to fsck_walk
add generic, type aware object chain walker
Conflicts:
Makefile
builtin-fsck.c
|
|
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
No functional change. This is needed to fix verify-pack in a later patch.
Signed-off-by: Nicolas Pitre <nico@cam.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
The top-level Makefile now creates a GIT-BUILD-OPTIONS file
which stores any options selected by the make process that
may be of use to further parts of the build process.
Specifically, we store the SHELL_PATH so that it can be used
by tests to construct shell scripts on the fly.
The format of the GIT-BUILD-OPTIONS file is Bourne shell,
and it is sourced by test-lib.sh; all tests can rely on just
having $SHELL_PATH correctly set in the environment.
The GIT-BUILD-OPTIONS file is written every time the
toplevel 'make' is invoked. Since the only users right now
are the test scripts, there's no drawback to updating its
timestamp. If something build-related depends on this, we
can do a trick similar to the one used by GIT-CFLAGS.
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
* db/checkout: (21 commits)
checkout: error out when index is unmerged even with -m
checkout: show progress when checkout takes long time while switching branches
Add merge-subtree back
checkout: updates to tracking report
builtin-checkout.c: Remove unused prefix arguments in switch_branches path
checkout: work from a subdirectory
checkout: tone down the "forked status" diagnostic messages
Clean up reporting differences on branch switch
builtin-checkout.c: fix possible usage segfault
checkout: notice when the switched branch is behind or forked
Build in checkout
Move code to clean up after a branch change to branch.c
Library function to check for unmerged index entries
Use diff -u instead of diff in t7201
Move create_branch into a library file
Build-in merge-recursive
Add "skip_unmerged" option to unpack_trees.
Discard "deleted" cache entries after using them to update the working tree
Send unpack-trees debugging output to stderr
Add flag to make unpack_trees() not print errors.
...
Conflicts:
Makefile
|
|
* jk/help-alias:
help: respect aliases
make alias lookup a public, procedural function
help: use parseopt
|
|
* ae/pack-autothread:
Revert "pack-objects: Print a message describing the number of threads for packing"
pack-objects: Print a message describing the number of threads for packing
pack-objects: Add runtime detection of online CPU's
|
|
Signed-off-by: Martin Koegler <mkoegler@auto.tuwien.ac.at>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
The requirements are:
* it may not crash on NULL pointers
* a callback function is needed, as index-pack/unpack-objects
need to do different things
* the type information is needed to check the expected <-> real type
and print better error messages
Signed-off-by: Martin Koegler <mkoegler@auto.tuwien.ac.at>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
This converts git_config_alias to the public alias_lookup
function. Because of the nature of our config parser, we
still have to rely on setting static data. However, that
interface is wrapped so that you can just say
value = alias_lookup(key);
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
* maint:
Protect peel_ref fallback case from NULL parse_object result
Ensure 'make dist' compiles git-archive.exe on Cygwin
|
|
On Cygwin we have to use git-archive.exe as the target, otherwise
running 'make dist' does not compile git-archive in the current
directory. That may cause 'make dist' to fail on a clean source
tree that has never been built before.
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Packing objects can be done in parallell nowadays, but it's
only done if the config option pack.threads is set to a value
above 1. Because of that, the code-path used is often not the
most optimal one.
This patch adds a routine to detect the number of online CPU's
at runtime (online_cpus()). When pack.threads (or --threads=) is
given a value of 0, the number of threads is set to the number of
online CPU's. This feature is also documented.
As per Nicolas Pitre's recommendations, the default is still to
run pack-objects single-threaded unless explicitly activated,
either by configuration or by command line parameter.
The routine online_cpus() is a rework of "numcpus.c", written by
one Philip Willoughby <pgw99@doc.ic.ac.uk>. numcpus.c is in the
public domain and can presently be downloaded from
http://csgsoft.doc.ic.ac.uk/numcpus/
Signed-off-by: Andreas Ericsson <ae@op5.se>
Signed-off-by: Brandon Casey <casey@nrlssc.navy.mil>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
An earlier commit e1b3a2c (Build-in merge-recursive) made the
subtree merge strategy backend unavailable. This resurrects
it.
A new test t6029 currently only tests the strategy is available,
but it should be enhanced to check the real "subtree" case.
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
* bc/fopen:
Add compat/fopen.c which returns NULL on attempt to open directory
|
|
This moves low-level merge functions out of merge-recursive.c and
places them in a new separate file, ll-merge.c
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
* bd/qsort:
compat: Add simplified merge sort implementation from glibc
|
|
The only differences in behavior should be:
- git checkout -m with non-trivial merging won't print out
merge-recursive messages (see the change in t7201-co.sh)
- git checkout -- paths... will give a sensible error message if
HEAD is invalid as a commit.
- some intermediate states which were written to disk in the shell
version (in particular, index states) are only kept in memory in
this version, and therefore these can no longer be revealed by
later write operations becoming impossible.
- when we change branches, we discard MERGE_MSG, SQUASH_MSG, and
rr-cache/MERGE_RR, like reset always has.
I'm not 100% sure I got the merge recursive setup exactly right; the
base for a non-trivial merge in the shell code doesn't seem
theoretically justified to me, but I tried to match it anyway, and the
tests all pass this way.
Other than these items, the results should be identical to the shell
version, so far as I can tell.
[jc: squashed lock-file fix from Dscho in]
Signed-off-by: Daniel Barkalow <barkalow@iabervon.org>
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Some systems do not fail as expected when fread et al. are called on
a directory stream. Replace fopen on such systems which will fail
when the supplied path is a directory.
Signed-off-by: Brandon Casey <casey@nrlssc.navy.mil>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
You can also create branches, in exactly the same way, with checkout -b.
This introduces branch.{c,h} library files for doing porcelain-level
operations on branches (such as creating them with their appropriate
default configuration).
Signed-off-by: Daniel Barkalow <barkalow@iabervon.org>
|
|
This makes write_tree_from_memory(), which writes the active cache as
a tree and returns the struct tree for it, available to other code. It
also makes available merge_trees(), which does the internal merge of
two trees with a known base, and merge_recursive(), which does the
recursive internal merge of two commits with a list of common
ancestors.
The first two of these will be used by checkout -m, and the third is
presumably useful in general, although the implementation of checkout
-m which entirely matches the behavior of the shell version does not
use it (since it ignores the difference of ancestry between the old
branch and the new branch).
Signed-off-by: Daniel Barkalow <barkalow@iabervon.org>
|
|
qsort in Windows 2000 (and various other C libraries) is a Quicksort
with the usual O(n^2) worst case. Unfortunately, sorting Git trees
seems to get very close to that worst case quite often:
$ /git/gitbad runstatus
# On branch master
qsort, nmemb = 30842
done, 237838087 comparisons.
This patch adds a simplified version of the merge sort that is glibc's
qsort(3). As a merge sort, this needs a temporary array equal in size
to the array that is to be sorted, but has a worst-case performance of
O(n log n).
The complexity that was removed is:
* Doing direct stores for word-size and -aligned data.
* Falling back to quicksort if the allocation required to perform the
merge sort would likely push the machine into swap.
Even with these simplifications, this seems to outperform the Windows
qsort(3) implementation, even in Windows XP (where it is "fixed" and
doesn't trigger O(n^2) complexity on trees).
[jes: moved into compat/qsort.c, as per Johannes Sixt's suggestion]
[bcd: removed gcc-ism, thanks to Edgar Toernig. renamed make variable
per Junio's comment.]
Signed-off-by: Brian Downing <bdowning@lavos.net>
Signed-off-by: Steffen Prohaska <prohaska@zib.de>
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
"git-help--browse" helper is to launch a browser of the user's choice
to view the HTML version of git documentation for a given command. It
used to take the name of a command, convert it to the path of the
documentation by prefixing the directory name and appending the
".html" suffix, and start the browser on the path.
This updates the division of labor between the caller in help.c and
git-help--browser helper. The helper is now responsible for launching
a browser of the user's choice on given URLs, and it is the caller's
responsibility to tell it the paths to documentation files.
This is in preparation to reuse the logic to choose user's preferred
browser in instaweb.
The helper had a provision for running it without any command name, in
which case it showed the toplevel "git(7)" documentation, but the
caller in help.c never makes such a call. The helper now exits with a
usage message when no path is given.
Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Signed-off-by: Mike Hommey <mh@glandium.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Signed-off-by: Robert Schiele <rschiele@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
POSIX.1-2001 has declaration of select(2) in <sys/select.h>, but
in the previous version of SUS, it was declared in <sys/time.h>
(which is already included in git-compat-util.h).
This introduces NO_SYS_SELECT_H macro in the Makefile to be set
on older systems, to skip inclusion of <sys/select.h> that does
not exist on them.
We could check _POSIX_VERSION with 200112L and do this
automatically, but earlier it was reported that the approach
does not work well on some vintage of HP-UX. Other systems may
get _POSIX_VERSION itself wrong. At least for now, this manual
configuration is safer.
Signed-off-by: Robert Schiele <rschiele@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
When the specfile (export-subst) attribute was introduced, it added a
dependency from archive-{tar|zip}.c to builtin-archive.c. This broke the
support for archive-operations in libgit.a since builtin-archive.o doesn't
belong in libgit.a.
This patch moves the functions required by libgit.a from builtin-archive.c
to the new file archive.c (which becomes part of libgit.a).
Signed-off-by: Lars Hjemli <hjemli@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Update configure.ac (and config.mak.in) by adding test for unsetenv
(NO_UNSETENV). Add comment about NO_UNSETENV to Makefile header, as
original commit 731043fd adding compat/unsetenv.c didn't do that.
Signed-off-by: Jakub Narebski <jnareb@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
rerere.enabled is _not_ on by default. The command is enabled if rr-cache
exists even when rerere.enabled is missing, and enabled or disabled by
explicitly setting the rerere.enabled variable.
|
|
This page should hold every information about the git ways to parse command
lines, and best practices to be used for scripting.
Signed-off-by: Pierre Habouzit <madcoder@debian.org>
|
|
git-instaweb relied on a pipe in a sed script, but this is not supported
by MacOS X sed when using BREs. git-instaweb relies on a working perl
in any case, and perl re are more consistent between platforms, so
replace sed invocation with an equivalent perl invocation.
Also, fix the documented -b "" to work without giving a spurious 'command
not found' error.
Signed-off-by: Charles Bailey <charles@hashpling.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
The convention for helper scripts has been
git-$TOOL--$HELPER. Since this is a "browse" helper for the
"help" tool, git-help--browse is a more sensible name.
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
The command was removed from the builtin command list and there was no
way to invoke it, but the code was still there.
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
Junio C Hamano
Gerrit Pape
Jeff King
Michal Rokos
Alex Riesen
Johannes Schindelin
Nicolas Pitre
Martin Koegler
Shawn O. Pearce
Andreas Ericsson
Daniel Barkalow
Brandon Casey
Brian Downing
Christian Couder
Mike Hommey
Robert Schiele
Lars Hjemli
Jakub Narebski
Pierre Habouzit
Charles Bailey