add a hashtable implementation that supports O(1) removal

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, put, 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 meant to be piggybacked
onto 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 twice as fast (due to less frequent resizing).

Signed-off-by: Karsten Blees <blees@dcon.de>
Win32: add a cache below mingw's lstat and readdir implementations

Checking the work tree status is quite slow on Windows, due to slow lstat
emulation (git calls lstat once for each file in the index). Windows
operating system APIs seem to be much better at scanning the status
of entire directories than checking single files.

Add an lstat implementation that uses a cache for lstat data. Cache misses
read the entire parent directory and add it to the cache. Subsequent lstat
calls for the same directory are served directly from the cache.

Also implement opendir / readdir / closedir so that they create and use
directory listings in the cache.

The cache doesn't track file system changes and doesn't plug into any
modifying file APIs, so it has to be explicitly enabled for git functions
that don't modify the working copy. For a start, enable the cache for the
entire 'git status' command and the core.preloadIndex feature.

The cache can be disabled at runtime by setting environment variable
GIT_NOFSCACHE, or at compile time by unsetting USE_FSCACHE in the Makefile.

Note: in an earlier version of this patch, the cache was always active and
tracked file system changes via ReadDirectoryChangesW. However, this was
much more complex and had negative impact on the performance of modifying
git commands such as 'git checkout'.

Signed-off-by: Karsten Blees <blees@dcon.de>
Win32: add high resolution timer function to debug performance issues

Add a high resolution timer function as basis for performance debugging.

Simple use case (measure one code section):
doube start = ticks();
/* measure this */
fprintf(stderr, "time: %g s\n", (ticks() - start));

Complex use case (measure several code sections):
double t = 0;
for (;;) {
  /* ignore */
  t -= ticks();
  /* measure this */
  t += ticks();
  /* ignore */
}
fprintf(stderr, "time: %g s\n", t);

Signed-off-by: Karsten Blees <blees@dcon.de>
Win32: add trace_performance facility to debug performance issues

Add trace_performance and trace_performance_since macros that print file
name, line number, time and an optional printf-formatted text to the file
specified in environment variable GIT_TRACE_PERFORMANCE.

Unless enabled via GIT_TRACE_PERFORMANCE, these macros have no noticeable
impact on performance, so that test code may be shipped in release builds.

MSVC: variadic macros (__VA_ARGS__) require VC++ 2005 or newer.

Simple use case (measure one code section):
doube start = ticks();
/* measure this */
trace_performance_since(start, "foobar");

Medium use case (measure consecutive code sections):
doube start = ticks();
/* measure this */
start = trace_performance_since(start, "foobar1");
/* measure this */
trace_performance_since(start, "foobar2");

Complex use case (measure several code sections):
double t = 0;
for (;;) {
  /* ignore */
  t -= ticks();
  /* measure this */
  t += ticks();
  /* ignore */
}
trace_performance(t, "frotz");

Signed-off-by: Karsten Blees <blees@dcon.de>
Win32: add command performance tracing to debug scripted commands

Especially scripted git commands are still quite slow on Windows. Add
performance tracing to identify which commands are called by a script and
how long they execute.

Usage: > GIT_TRACE_PERFORMANCE=C:/git.log git svn rebase
creates a log file like this:
trace: at compat/mingw.c:2068, time: 0.001000 s: command: git.exe rev-parse --show-prefix
trace: at compat/mingw.c:2068, time: 0.001219 s: command: git.exe config --bool --get svn.fetchall
...

Signed-off-by: Karsten Blees <blees@dcon.de>
Merge branch 'kb/performance-tracing-v3' into kb/devel
Merge branch 'kb/fix-segfault-in-gdb' into kb/devel