Revert "upload-pack: send non-HEAD symbolic refs"

This reverts commit 5e7dcad771cb873e278a0571b46910d7c32e2f6c; there
may be unbounded number of symbolic refs in the repository, but the
capability header line in the on-wire protocol has a rather low
length limit.
branch: fix --verbose output column alignment

Commit f2e0873 (branch: report invalid tracking branch as gone) removed
an early return from fill_tracking_info() in the path taken when 'git
branch -v' lists a branch in sync with its upstream. This resulted in an
unconditionally added space in front of the subject line:

    $ git branch -v
    * master f5eb3da  commit pushed to upstream
      topic  f935eb6 unpublished topic

Instead, only add the trailing space if a decoration have been added.

To catch this kind of whitespace breakage in the tests, be a bit less
smart when filtering the output through sed.

Signed-off-by: Torstein Hegge <hegge@resisty.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Merge branch 'jx/branch-vv-always-compare-with-upstream'

Hot-fix for a regression.

* jx/branch-vv-always-compare-with-upstream:
  branch: fix --verbose output column alignment
Merge branch 'maint'

Hotfix for recent regression while talking to upload-pack
in a repository with many symbolic refs.

* maint:
  Revert "upload-pack: send non-HEAD symbolic refs"
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>
remove old hash.[ch] implementation

Signed-off-by: Karsten Blees <blees@dcon.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
fix 'git update-index --verbose --again' output

'git update-index --verbose' consistently reports paths relative to the
work-tree root. The only exception is the '--again' option, which reports
paths relative to the current working directory.

Change do_reupdate to use non-prefixed paths.

Signed-off-by: Karsten Blees <blees@dcon.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
builtin/update-index.c: cleanup update_one

do_reupdate calls update_one with a cache_entry.name, there's no need for
the extra sanitation / normalization that happens in prefix_path.
cmd_update_index calls update_one with an already prefixed path, no need to
prefix_path twice.

Remove the extra prefix_path from update_one. Also remove the now unused
'prefix' and 'prefix_length' parameters.

As of d089eba "setup: sanitize absolute and funny paths in get_pathspec()",
prefix_path uncoditionally returns a copy, even if the passed in path isn't
changed. Lets unconditionally free() the result.

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 (we could free() directly in remove_name_hash(), but
name-hash.c isn't concerned with cache_entry allocation at all).

Accessing a cache_entry after removing it from the index is now no longer
allowed, as the memory has been freed. The following functions need minor
fixes (typically by copying ce->name before use):
 - builtin/rm.c::cmd_rm
 - builtin/update-index.c::do_reupdate
 - read-cache.c::read_index_unmerged
 - resolve-undo.c::unmerge_index_entry_at

Signed-off-by: Karsten Blees <blees@dcon.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
State correct usage of literal examples in man pages in the coding standards

The man pages contain inconsistent usage of backticks vs. single quotes
around options, commands, etc. that are in paragraphs. This commit states
that backticks should always be used around literal examples.

This commit states that "--" and friends should not be escaped
(e.g. use `--pretty=oneline` instead of `\--pretty=oneline`).

This commit also states correct usage for typesetting command usage
examples with inline substitutions.

Thanks-to: Ramkumar Ramachandra <artagnon@gmail.com>
Thanks-to: Stuart Rackham <srackham@gmail.com>
Thanks-to: Junio C Hamano <gitster@pobox.com>
Signed-off-by: Jason St. John <jstjohn@purdue.edu>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Documentation/rev-list-options.txt: fix mark-up

Some the labeled list entries have a blank line between the label
and the body text, and some don't.  Use the latter style for
consistency; incidentally, syntax highlighting in Vim works better
if there is no blank line there.

Typeset literal options, commands, and path names in monospace.
When using `literal string` mark-up to do so, there is no need to
escape AsciiDoc special characters with backslashes, so make sure we
don't do so.

Replace some double quotes with proper AsciiDoc quotes
(e.g. ``foo'').

Signed-off-by: Jason St. John <jstjohn@purdue.edu>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Documentation/rev-list-options.txt: fix some grammatical issues and typos

Various fixes:

 - fix typos (e.g. "show" -> "shown")
 - use "regular expression(s)" instead of "regexp" where appropriate
 - reword some sentences for easier reading
 - fix/improve some grammatical issues (e.g. comma usage)
 - add missing articles (e.g. "the")
 - change "E-mail" to "email"

Signed-off-by: Jason St. John <jstjohn@purdue.edu>
Signed-off-by: Junio C Hamano <gitster@pobox.com>