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, 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: Karsten Blees <blees@dcon.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
buitin/describe.c: use new hash map implementation

Signed-off-by: Karsten Blees <blees@dcon.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
diffcore-rename.c: move code around to prepare for the next patch

No actual code changes, just move hash_filespec up and outdent part of
find_identical_files.

Signed-off-by: Karsten Blees <blees@dcon.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
diffcore-rename.c: simplify finding exact renames

The find_exact_renames function currently only uses the hash table for
grouping, i.e.:

1. add sources
2. add destinations
3. iterate all buckets, per bucket:
4. split sources from destinations
5. iterate destinations, per destination:
6. iterate sources to find best match

This can be simplified by utilizing the lookup functionality of the hash
table, i.e.:

1. add sources
2. iterate destinations, per destination:
3. lookup sources matching the current destination
4. iterate sources to find best match

This saves several iterations and file_similarity allocations for the
destinations.

Signed-off-by: Karsten Blees <blees@dcon.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
diffcore-rename.c: use new hash map implementation

Signed-off-by: Karsten Blees <blees@dcon.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
name-hash.c: use new hash map implementation for directories

Signed-off-by: Karsten Blees <blees@dcon.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
name-hash.c: remove unreferenced directory entries

The new hashmap implementation supports remove, so remove and free
directory entries that are no longer referenced by active cache entries.

Signed-off-by: Karsten Blees <blees@dcon.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
name-hash.c: use new hash map implementation for cache entries

Note: the "ce->next = NULL;" in unpack-trees.c::do_add_entry can safely be
removed, as ce->next (now ce->ent.next) is always properly initialized in
name-hash.c::hash_index_entry.

Signed-off-by: Karsten Blees <blees@dcon.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
name-hash.c: remove cache entries instead of marking them CE_UNHASHED

The new hashmap implementation supports remove, so really remove unused
cache entries from the name hashmap instead of just marking them.

The CE_UNHASHED flag and CE_STATE_MASK are no longer needed.

Keep the CE_HASHED flag to prevent adding entries twice.

Signed-off-by: Karsten Blees <blees@dcon.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
read-cache.c: fix memory leaks caused by removed cache entries

When cache_entry structs are removed from index_state.cache, they are not
properly freed. Freeing those entries wasn't possible before because we
couldn't remove them from index_state.name_hash.

Now that we _do_ remove the entries from name_hash, we can also free them.
Add free(cache_entry) to all call sites of name-hash.c::remove_name_hash in
read-cache.c, as name-hash.c isn't concerned with cache_entry allocation.

cmd_rm and unmerge_index_entry_at use cache_entry.name after removing the
entry. Copy the name so that we don't access memory that has been freed.

Signed-off-by: Karsten Blees <blees@dcon.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
remove old hash.[ch] implementation

Signed-off-by: Karsten Blees <blees@dcon.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
SQUASH??? submodule.c: do not use ce after it gets freed by remove-cache-entry

Signed-off-by: Junio C Hamano <gitster@pobox.com>
gc: remove gc.pid file at end of execution

This file isn't really harmful, but isn't useful either, and can create
minor annoyance for the user:

* It's confusing, as the presence of a *.pid file often implies that a
  process is currently running. A user running "ls .git/" and finding
  this file may incorrectly guess that a "git gc" is currently running.

* Leaving this file means that a "git gc" in an already gc-ed repo is
  no-longer a no-op. A user running "git gc" in a set of repositories,
  and then synchronizing this set (e.g. rsync -av, unison, ...) will see
  all the gc.pid files as changed, which creates useless noise.

This patch unlinks the file after the garbage collection is done, so that
gc.pid is actually present only during execution.

Future versions of Git may want to use the information left in the gc.pid
file (e.g. for policies like "don't attempt to run a gc if one has
already been ran less than X hours ago"). If so, this patch can safely be
reverted. For now, let's not bother the users.

Explained-by: Matthieu Moy <Matthieu.Moy@imag.fr>
Signed-off-by: Jonathan Nieder <jrnieder@gmail.com>
Improved-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
graph: fix coloring around octopus merges

When drawing the graph of an octopus merge, we draw a horizontal line
from parents 3 and above into the asterisk representing the commit. The
sections of this line should be colored to match the graph lines coming
in from above.

However, if the commit is not in the left-most column we do not take
into account the columns to the left of the commit when calculating
these colors. Fix this by adding the appropriate offset to the column
index used for calculating the color.

Signed-off-by: Hemmo Nieminen <hemmo.nieminen@iki.fi>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
checkout: allow dwim for branch creation for "git checkout $branch --"

The "--" notation disambiguates files and branches, but as a side-effect
of the previous implementation, also disabled the branch auto-creation
when $branch does not exist.

A possible scenario is then:

git checkout $branch
=> fails if $branch is both a ref and a file, and suggests --

git checkout $branch --
=> refuses to create the $branch

This patch allows the second form to create $branch, and since the -- is
provided, it does not look for file named $branch.

Signed-off-by: Matthieu Moy <Matthieu.Moy@imag.fr>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
checkout: proper error message on 'git checkout foo bar --'

The previous code was detecting the presence of "--" by looking only at
argument 1. As a result, "git checkout foo bar --" was interpreted as an
ambiguous file/revision list, and errored out with:

error: pathspec 'foo' did not match any file(s) known to git.
error: pathspec 'bar' did not match any file(s) known to git.
error: pathspec '--' did not match any file(s) known to git.

This patch fixes it by walking through the argument list to find the
"--", and now complains about the number of references given.

Signed-off-by: Matthieu Moy <Matthieu.Moy@imag.fr>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
diff.c: keep arrow(=>) on show_stats()'s shortened filename part to make rename visible

"git diff -M --stat" can detect rename and show renamed file name like
"foofoofoo => barbarbar".

Before this commit, this output is shortened always by omitting left most
part like "...foo => barbarbar". So, if the destination filename is too long,
source filename putting left or arrow can be totally omitted like
"...barbarbar", without including any of "foofoofoo =>".
In such a case where arrow symbol is omitted, there is no way to know
whether the file is renamed or existed in the original.

Make sure there is always an arrow, like "...foo => ...bar".

The output can contain curly braces('{','}') for grouping.
So, in general, the output format is "<pfx>{<mid_a> => <mid_b>}<sfx>"

To keep arrow("=>"), try to omit <pfx> as long as possible at first
because later part or changing part will be the more important part.
If it is not enough, shorten <mid_a>, <mid_b> trying to have the same
maximum length.
If it is not enough yet, omit <sfx>.

Signed-off-by: Tsuneo Yoshioka <yoshiokatsuneo@gmail.com>
Test-added-by: Thomas Rast <trast@inf.ethz.ch>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
SQUASH??? style fixes and s/omit/shorten/ where appropriate

Signed-off-by: Junio C Hamano <gitster@pobox.com>
Merge branch 'po/dot-url' into jch

Explain how '.' can be used to refer to the "current repository"
in the documentation.

* po/dot-url:
  doc/cli: make "dot repository" an independent bullet point
  config doc: update dot-repository notes
  doc: command line interface (cli) dot-repository dwimmery
Merge branch 'jc/upload-pack-send-symref' into jch

One long-standing flaw in the pack transfer protocol used by "git
clone" was that there was no way to tell the other end which branch
"HEAD" points at, and the receiving end needed to guess.  A new
capability has been defined in the pack protocol to convey this
information so that cloning from a repository with more than one
branches pointing at the same commit where the HEAD is at now
reliably sets the initial branch in the resulting repository.

* jc/upload-pack-send-symref:
  clone: test the new HEAD detection logic
  connect: annotate refs with their symref information in get_remote_head()
  connect.c: make parse_feature_value() static
  upload-pack: send non-HEAD symbolic refs
  upload-pack: send symbolic ref information as capability
  upload-pack.c: do not pass confusing cb_data to mark_our_ref()
  t5505: fix "set-head --auto with ambiguous HEAD" test