| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
When overriding the identifier "stat" so that "struct stat" will be
substituted with "struct _stati64" everywhere, I tried to fix the calls
to the _function_ stat(), too, but I forgot to change the earlier
attempt "stat64" to "_stati64" there.
So, the stat() calls were overridden by calls to _stati64() instead.
Unfortunately, there is a function _stati64() so that I missed that
calls to stat() were not actually overridden by calls to mingw_lstat(),
but t4200-rerere.sh showed the error.
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Acked-by: Johannes Sixt <j6t@kdbg.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
The type 'off_t' should be used everywhere so that the bit-depth of that
type can be adjusted in the standard C library, and you just need to
recompile your program to benefit from the extended precision.
Only that it was not done that way in the MS runtime library.
This patch reroutes off_t to off64_t and provides the other necessary
changes so that finally, clones larger than 2 gigabyte work on Windows
(provided you are on a file system that allows files larger than 2gb).
Initial patch by Sickboy <sb@dev-heaven.net>.
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Acked-by: Johannes Sixt <j6t@kdbg.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
We had defined some SIG_FOO macros that appear in the code, but that are
not supported on Windows, in order to make the code compile. But a
subsequent change will assert that a signal number is non-zero. We now
use the signal numbers that are commonly used on POSIX systems.
Signed-off-by: Johannes Sixt <j6t@kdbg.org>
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
* js/mingw-rename-fix:
compat/mingw.c: Teach mingw_rename() to replace read-only files
|
|
On POSIX, rename() can replace files that are not writable. On Windows,
however, read-only files cannot be replaced without additional efforts:
We have to make the destination writable first.
Since the situations where the destination is read-only are rare, we do not
make the destination writable on every invocation, but only if the first
try to rename a file failed with an "access denied" error.
Signed-off-by: Johannes Sixt <j6t@kdbg.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Apparently, CREATE_NO_WINDOW makes the OS tell the process
that it has a console, but without actually creating the
window. As a result, when git is started from GUI, ssh
tries to ask its questions on the invisible console.
This patch uses DETACHED_PROCESS instead, which clearly
means that the process should be left without a console.
The downside is that if the process manually calls
AllocConsole, the window will appear. A similar thing
might occur if it calls another console executable.
Signed-off-by: Alexander Gavrilov <angavrilov@gmail.com>
Acked-by: Johannes Sixt <johannes.sixt@telecom.at>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
The original patch that lead to an earlier commit adbc0b6 (cygwin: Use
native Win32 API for stat, 2008-09-30) did not call git_default_config()
and it was a good thing. The lazy config reading when lstat/stat is
called for the first time to find out if core.filemode is set can happen
anytime in the calling program. If it happens after the calling program
parsed the configuration file to prime its default parameter settings and
processed its command line parameters to tweak them, this will overwrite
the values set by the program with the values read from the config file.
This essentially reverts the code to the version as submitted by Mark,
with a bit more comments to clarify why we do not fall back on the default
configuration parser from git_cygwin_config().
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Cygwin's POSIX emulation allows use of core.filemode true, unlike native
Window's implementation of stat / lstat, and Cygwin/git users who have
configured core.filemode true in various repositories will be very
unpleasantly surprised to find that git is no longer honoring that option.
So, this patch forces use of Cygwin's stat functions if core.filemode is
set true, regardless of any other considerations.
Signed-off-by: Mark Levedahl <mlevedahl@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
lstat/stat functions in Cygwin are very slow, because they try to emulate
some *nix things that Git does not actually need. This patch adds Win32
specific implementation of these functions for Cygwin.
This implementation handles most situation directly but in some rare cases
it falls back on the implementation provided for Cygwin. This is necessary
for two reasons:
- Cygwin has its own file hierarchy, so absolute paths used in Cygwin is
not suitable to be used Win32 API. cygwin_conv_to_win32_path can not be
used because it automatically dereference Cygwin symbol links, also it
causes extra syscall. Fortunately Git rarely use absolute paths, so we
always use Cygwin implementation for absolute paths.
- Support of symbol links. Cygwin stores symbol links as ordinary using
one of two possible formats. Therefore, the fast implementation falls
back to Cygwin functions if it detects potential use of symbol links.
The speed of this implementation should be the same as mingw_lstat for
common cases, but it is considerable slower when the specified file name
does not exist.
Despite all efforts to make the fast implementation as robust as possible,
it may not work well for some very rare situations. I am aware only one
situation: use Cygwin mount to bind unrelated paths inside repository
together. Therefore, the core.ignoreCygwinFSTricks configuration option is
provided, which controls whether native or Cygwin version of stat is used.
Signed-off-by: Dmitry Potapov <dpotapov@gmail.com>
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
|
|
Some small Win32 specific functions will be shared by MinGW and
Cygwin compatibility layer. Place them into a separate header.
Signed-off-by: Dmitry Potapov <dpotapov@gmail.com>
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
|
|
The field device is not used by Git, and putting the number of the
current device is meaningless anyway.
Signed-off-by: Dmitry Potapov <dpotapov@gmail.com>
Acked-by: Johannes Sixt <johannes.sixt@telecom.at>
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
|
|
Our poll() emulation did not support the timeout argument. With this patch
we support it for the simple case where poll() does not need to wait on
file descriptors as well because this case amounts to a mere Sleep().
This is needed if the user sets help.autocorrect is set to a positive
value.
Signed-off-by: Johannes Sixt <johannes.sixt@telecom.at>
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
|
|
* maint:
Update draft release notes for 1.6.0.2
Use compatibility regex library for OSX/Darwin
git-svn: Fixes my() parameter list syntax error in pre-5.8 Perl
Git.pm: Use File::Temp->tempfile instead of ->new
t7501: always use test_cmp instead of diff
Conflicts:
Makefile
|
|
The standard libc regex library on OSX does not support alternation
in POSIX Basic Regular Expression mode. This breaks the diff.funcname
functionality on OSX.
To fix this, we use the GNU regex library which is already present in
the compat/ diretory for the MinGW port. However, simply adding compat/
to the COMPAT_CFLAGS variable causes a conflict between the system
fnmatch.h and the one present in compat/. To remedy this, move the
regex and fnmatch functionality to their own subdirectories in compat/
so they can be included seperately.
Signed-off-by: Arjen Laarhoven <arjen@yaph.org>
Tested-by: Mike Ralphson <mike@abacus.co.uk> (AIX)
Tested-by: Johannes Sixt <johannes.sixt@telecom.at> (MinGW)
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
* maint:
compat/snprintf.c: handle snprintf's that always return the # chars transmitted
git-svn: fix dcommit to urls with embedded usernames
revision.h: make show_early_output an extern which is defined in revision.c
|
|
Some platforms provide a horribly broken snprintf. More broken than the
platforms that return -1 when there is too little space in the target buffer
for the formatted string. Some platforms provide an snprintf which _always_
returns the number of characters transmitted to the buffer, regardless of
whether there was enough space or not.
IRIX 6.5 is such a platform. IRIX does have a working snprintf(), but it
is only provided when _NO_XOPEN5 evaluates to zero, and this only happens
if _XOPEN_SOURCE is defined, but definition of _XOPEN_SOURCE prevents
inclusion of many other common functions and defines. So it must be avoided.
Work around these horribly broken snprintf implementations by detecting an
snprintf call which results in the number of transmitted characters exactly
equal to the length of our buffer and retrying with a larger buffer just to
be safe.
Signed-off-by: Brandon Casey <casey@nrlssc.navy.mil>
Acked-by: Johannes Sixt <johannes.sixt@telecom.at>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
member."
This reverts commit fc2ded5b08e071beed974117c0148781b1acc94a.
As we do not need the member in struct stat, we do not need to have a
custom "struct mingw_stat" anymore.
Signed-off-by: Johannes Sixt <johannes.sixt@telecom.at>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Some platforms do not have st_blocks member in "struct stat"; mingw
already emulates it by rounding it up to closest 512-byte blocks (even
though it could overcount when a file has holes).
The reason to use the member is only to figure out how many kilobytes the
files occupy on-disk, so give a helper function in git-compat-util.h to
compute this value.
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Acked-by: Johannes Sixt <johannes.sixt@telecom.at>
|
|
With MinGW's
gcc.exe (GCC) 3.4.5 (mingw special)
GNU ld version 2.17.50 20060824
the old define caused link errors:
git.o: In function `main':
C:/msysgit/git/git.c:500: undefined reference to `mingw_main'
collect2: ld returned 1 exit status
The modified define works.
Signed-off-by: Steffen Prohaska <prohaska@zib.de>
Acked-by: Johannes Sixt <johannes.sixt@telecom.at>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Since the exec-path on Windows is derived from the program invocation path,
we must ensure that argv[0] always has a path. Unfortunately, if a program
is invoked from CMD, argv[0] has no path. But on the other hand, the
C runtime offers a global variable, _pgmptr, that always has the full path
to the program. We hook into main() with a preprocessor macro, where we
replace argv[0].
Signed-off-by: Johannes Sixt <johannes.sixt@telecom.at>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
This adds only the minimum necessary to keep git pull/merge's diffstat from
wrapping. Notably absent is support for the K (erase) operation, and support
for POSIX write.
Signed-off-by: Peter Harris <git@peter.is-a-geek.org>
Signed-off-by: Johannes Sixt <johannes.sixt@telecom.at>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Without this simple fix "git gui" in the git source directory
finds the git-gui directory instead of the tcl script in /usr/bin.
Signed-off-by: Eric Raible <raible@gmail.com>
Signed-off-by: Johannes Sixt <johannes.sixt@telecom.at>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
The system's default browser for displaying HTML help pages is now used
directly on Windows, instead of launching git-web--browser, which
requires a Unix shell. Avoiding MSYS' bash when possible is good
because it avoids potential path translation issues. In this case it is
not too hard to avoid launching a shell, so let's avoid it.
The Windows-specific code is implemented in compat/mingw.c to avoid
platform-specific code in the main code base. On Windows, open_html is
provided as a define. If open_html is not defined, git-web--browse is
used. This approach avoids platform-specific ifdefs by using
per-function ifdefs. The "ifndef open_html" together with the
introductory comment should sufficiently warn developers, so that they
hopefully will not break this mechanism.
Signed-off-by: Steffen Prohaska <prohaska@zib.de>
Signed-off-by: Johannes Sixt <johannes.sixt@telecom.at>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
On Windows, ntohl() returns unsigned long. On Unix it returns
uint32_t. This makes choosing a suitable printf format string
hard.
This commit introduces a mingw specific helper function
git_ntohl() that casts to unsigned int before returning. This
makes gcc's printf format check happy. It should be safe because
we expect ntohl to use 32-bit numbers.
Signed-off-by: Steffen Prohaska <prohaska@zib.de>
Signed-off-by: Johannes Sixt <johannes.sixt@telecom.at>
|
|
Signed-off-by: Johannes Sixt <johannes.sixt@telecom.at>
|
|
Windows's struct stat does not have a st_blocks member. Since we already
have our own stat/lstat/fstat implementations, we can just as well use
a customized struct stat. This patch introduces just that, and also fills
in the st_blocks member. On the other hand, we don't provide members that
are never used.
Signed-off-by: Johannes Sixt <johannes.sixt@telecom.at>
|
|
This is a necessary pendant to our lstat implementation: MSVCRT's
implementations of lstat and utime do some adjustments if daylight
saving time is in effect, but our lstat implementation doesn't do these
adjustments and report the correct UTC time. With this implementation
we omit the adjustments in utime() as well and always write UTC.
Signed-off-by: Johannes Sixt <johannes.sixt@telecom.at>
|
|
This gives us a significant speedup when adding, committing and stat'ing files.
Also, since Windows doesn't really handle symlinks, we let stat just uses lstat.
We also need to replace fstat, since our implementation and the standard stat()
functions report slightly different timestamps, possibly due to timezones.
We simply report UTC in our implementation, and do our FILETIME to time_t
conversion based on the document at http://support.microsoft.com/kb/167296.
With Moe's repo structure (100K files in 100 dirs, containing 2-4 bytes)
mkdir bummer && cd bummer; for ((i=0;i<100;i++)); do
mkdir $i && pushd $i;
for ((j=0;j<1000;j++)); do echo "$j" >$j; done;
popd;
done
We get the following performance boost:
With normal lstat & stat Custom lstat/fstat
------------------------ ------------------------
Command: git init Command: git init
------------------------ ------------------------
real 0m 0.047s real 0m 0.063s
user 0m 0.031s user 0m 0.015s
sys 0m 0.000s sys 0m 0.015s
------------------------ ------------------------
Command: git add . Command: git add .
------------------------ ------------------------
real 0m19.390s real 0m12.031s 1.6x
user 0m 0.015s user 0m 0.031s
sys 0m 0.030s sys 0m 0.000s
------------------------ ------------------------
Command: git commit -a.. Command: git commit -a..
------------------------ ------------------------
real 0m30.812s real 0m16.875s 1.8x
user 0m 0.015s user 0m 0.015s
sys 0m 0.000s sys 0m 0.015s
------------------------ ------------------------
3x Command: git-status 3x Command: git-status
------------------------ ------------------------
real 0m11.860s real 0m 5.266s 2.2x
user 0m 0.015s user 0m 0.015s
sys 0m 0.015s sys 0m 0.015s
real 0m11.703s real 0m 5.234s
user 0m 0.015s user 0m 0.015s
sys 0m 0.000s sys 0m 0.000s
real 0m11.672s real 0m 5.250s
user 0m 0.031s user 0m 0.015s
sys 0m 0.000s sys 0m 0.000s
------------------------ ------------------------
Command: git commit... Command: git commit...
(single file) (single file)
------------------------ ------------------------
real 0m14.234s real 0m 7.735s 1.8x
user 0m 0.015s user 0m 0.031s
sys 0m 0.000s sys 0m 0.000s
Signed-off-by: Marius Storm-Olsen <mstormo_git@storm-olsen.com>
Signed-off-by: Johannes Sixt <johannes.sixt@telecom.at>
|
|
The problem with Windows's own implementation is that it tries to be
clever when a console program is invoked from a GUI application: In this
case it sometimes automatically allocates a new console window. As a
consequence, the IO channels of the spawned program are directed to the
console, but the invoking application listens on channels that are now
directed to nowhere.
In this implementation we use the lowlevel facilities of CreateProcess(),
which offers a flag to tell the system not to open a console. As a side
effect, only stdin, stdout, and stderr channels will be accessible from
C programs that are spawned. Other channels (file handles, pipe handles,
etc.) are still inherited by the spawned program, but it doesn't get
enough information to access them.
Johannes Schindelin integrated path quoting and unified the various
*execv* and *spawnv* helpers. Eric Raible suggested to also quote '{'.
Signed-off-by: Johannes Sixt <johannes.sixt@telecom.at>
|
|
gethostbyname() is the first function that calls into the Winsock library,
and it is wrapped only to initialize the library.
socket() is wrapped for two reasons:
- Windows's socket() creates things that are like low-level file handles,
and they must be converted into file descriptors first.
- And these handles cannot be used with plain ReadFile()/WriteFile()
because they are opened for "overlapped IO". We have to use WSASocket()
to create non-overlapped IO sockets.
connect() must be wrapped because Windows's connect() expects the low-level
sockets, not file descriptors, and we must first unwrap the file descriptor
before we can pass it on to Windows's connect().
Signed-off-by: Johannes Sixt <johannes.sixt@telecom.at>
|
|
This emulation of poll() is by far not general. It assumes that the
fds that are to be waited for are connected to pipes. The pipes are
polled in a loop until data becomes available in at least one of them.
If only a single fd is waited for, the implementation actually does
not wait at all, but assumes that a subsequent read() will block.
In order not to needlessly burn CPU time, the CPU is yielded to other
processes before the next round in the poll loop using Sleep(0). Note that
any sleep timeout greater than zero will reduce the efficiency by a
magnitude.
Signed-off-by: Johannes Sixt <johannes.sixt@telecom.at>
|
|
On Windows, we have spawnv() variants to run a child process instead of
fork()/exec(). In order to attach pipe ends to stdin, stdout, and stderr,
we have to use this idiom:
save1 = dup(1);
dup2(pipe[1], 1);
spawnv();
dup2(save1, 1);
close(pipe[1]);
assuming that the descriptors created by pipe() are not inheritable.
Signed-off-by: Johannes Sixt <johannes.sixt@telecom.at>
|
|
On Unix the idiom to use a pipe is as follows:
pipe(fd);
pid = fork();
if (!pid) {
dup2(fd[1], 1);
close(fd[1]);
close(fd[0]);
...
}
close(fd[1]);
i.e. the child process closes the both pipe ends after duplicating one
to the file descriptors where they are needed.
On Windows, which does not have fork(), we never have an opportunity to
(1) duplicate a pipe end in the child, (2) close unused pipe ends. Instead,
we must use this idiom:
save1 = dup(1);
pipe(fd);
dup2(fd[1], 1);
spawn(...);
dup2(save1, 1);
close(fd[1]);
i.e. save away the descriptor at the destination slot, replace by the pipe
end, spawn process, restore the saved file.
But there is a problem: Notice that the child did not only inherit the
dup2()ed descriptor, but also *both* original pipe ends. Although the one
end that was dup()ed could be closed before the spawn(), we cannot close
the other end - the child inherits it, no matter what.
The solution is to generate non-inheritable pipes. At the first glance,
this looks strange: The purpose of pipes is usually to be inherited to
child processes. But notice that in the course of actions as outlined
above, the pipe descriptor that we want to inherit to the child is
dup2()ed, and as it so happens, Windows's dup2() creates inheritable
duplicates.
Signed-off-by: Johannes Sixt <johannes.sixt@telecom.at>
|
|
When an external git command is invoked, it can be a Bourne shell script.
This patch looks into the command file to see whether it is one.
In this case, the command line is rearranged to invoke the shell
with the proper arguments.
With this change, scripted git commands work. Command line arguments
to those scripts cannot be complex (contain spaces or double-quotes), yet.
Signed-off-by: Johannes Sixt <johannes.sixt@telecom.at>
|
|
The timer is implemented using a thread that calls the signal handler
at regular intervals.
We also replace Windows's signal() function because we must intercept
that SIGALRM is set (which is used when a timer is canceled).
Signed-off-by: Johannes Sixt <johannes.sixt@telecom.at>
|
|
Since GIT calls into Microsoft's MSVCRT.DLL, it must use the printf
format that this DLL uses for 64-bit integers, which is %I64u instead
of %llu.
Signed-off-by: Johannes Sixt <johannes.sixt@telecom.at>
|
|
Signed-off-by: Johannes Sixt <johannes.sixt@telecom.at>
|
|
Windows's rename() is based on the MoveFile() API, which fails if the
destination exists. Here we work around the problem by using MoveFileEx().
Furthermore, the posixly correct error is returned if the destination is
a directory.
The implementation is still slightly incomplete, however, because of the
missing error code translation: We assume that the failure is due to
permissions.
Signed-off-by: Johannes Sixt <johannes.sixt@telecom.at>
|
|
On Windows, read-only files cannot be deleted. To make sure that
deletion does not fail because of this, always call chmod() before
unlink().
Signed-off-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>
Signed-off-by: Johannes Sixt <johannes.sixt@telecom.at>
|
|
getpwuid() is implemented just enough that GIT does not issue errors.
Since the information that it returns is not very useful, users are
required to set up user.name and user.email configuration.
All uses of getpwuid() are like getpwuid(getuid()), hence, the return value
of getuid() is irrelevant and the uid parameter is not even looked at.
Side note: getpwnam() is only used to resolve '~' and '~username' paths,
which is an idiom not known on Windows, hence, we don't implement it.
Signed-off-by: Johannes Sixt <johannes.sixt@telecom.at>
|
|
The wrapper does two things:
- Requests to open /dev/null are redirected to open the nul pseudo file.
- A request to open a file that currently exists as a directory on
Windows fails with EACCES; this is changed to EISDIR.
Signed-off-by: Johannes Sixt <johannes.sixt@telecom.at>
|
|
GIT's guts work with a forward slash as a path separators. We do not change
that. Rather we make sure that only "normalized" paths enter the depths
of the machinery.
We have to translate backslashes to forward slashes in the prefix and in
command line arguments. Fortunately, all of them are passed through
functions in setup.c.
A macro has_dos_drive_path() is defined that checks whether a path begins
with a drive letter+colon combination. This predicate is always false on
Unix. Another macro is_dir_sep() abstracts that a backslash is also a
directory separator on Windows.
Signed-off-by: Johannes Sixt <johannes.sixt@telecom.at>
|
|
Signed-off-by: Johannes Sixt <johannes.sixt@telecom.at>
|
|
With this change GIT can be compiled and linked using MinGW. Builtins
that only read the repository such as the log family and grep already
work.
Simple stubs are provided for a number of functions that the Windows C
runtime does not offer. They will be completed in later patches.
However, a fix for the snprintf/vsnprintf replacement is applied here
to avoid buffer overflows.
Dmitry Kakurin pointed out that access(..., X_OK) would always fails on
Vista and suggested the -D__USE_MINGW_ACCESS workaround.
Signed-off-by: Johannes Sixt <johannes.sixt@telecom.at>
|
|
We don't have fnmatch and regular expressions on Windows. We borrow
fnmatch.[ch] from the GNU C library (license is LGPL 2 or later) and
GNU regexp (regexp.c[ch], license is GPL 2 or later). Note that regexp.c
was changed slightly to avoid warnings with gcc.
We make the addition of these files an extra commit so as not to clutter
the next commits.
Signed-off-by: Johannes Sixt <johannes.sixt@telecom.at>
|
|
Some systems define fopen as a macro based on compiler settings.
The previous technique for reverting to the system fopen function
by merely undefining fopen is inadequate in this case. Instead,
avoid defining fopen entirely when compiling this source file.
Signed-off-by: Brandon Casey <casey@nrlssc.navy.mil>
Tested-by: Mike Ralphson <mike@abacus.co.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
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>
|
|
* bc/fopen:
Add compat/fopen.c which returns NULL on attempt to open directory
|
|
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>
|
|
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>
|
Johannes Schindelin
Johannes Sixt
Junio C Hamano
Alexander Gavrilov
Mark Levedahl
Dmitry Potapov
Johannes Sixt
Arjen Laarhoven
Brandon Casey
Steffen Prohaska
Peter Harris
Eric Raible
Marius Storm-Olsen
Michal Rokos
Brian Downing