git-send-email: add optional 'choices' parameter to the ask sub

Make it possible for callers of ask() to provide a list of
choices. Entering an appropriate integer chooses from that list,
otherwise the input is treated as usual.

Each choice can either be a single string, which is used both for the
prompt and for the return value, or a two-element array ref, where the
zeroth element is the choice and the first is used for the prompt.

Signed-off-by: Rasmus Villemoes <rv@rasmusvillemoes.dk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
git-send-email: Cache generated message-ids, use them when prompting

Allow the user to specify a file (sendemail.msgidcachefile) in which
to store the message-ids generated by git-send-email, along with time
and subject information. When prompting for a Message-ID to be used in
In-Reply-To, that file can be used to generate a list of options.

When composing v2 or v3 of a patch or patch series, this avoids the
need to get one's MUA to display the Message-ID of the earlier email
(which is cumbersome in some MUAs) and then copy-paste that.

Listing all previously sent emails is useless, so currently only the
10 most "relevant" emails. "Relevant" is based on a simple scoring,
which might need to be revised: Count the words in the old subject
which also appear in the subject of the first email to be sent; add a
bonus if the old email was first in a batch (that is, [00/74] is more
likely to be relevant than [43/74]). Resort to comparing timestamps
(newer is more relevant) when the scores tie.

To limit disk usage, the oldest half of the cached entries are
expunged when the cache file exceeds sendemail.msgidcachemaxsize
(default 100kB). This also ensures that we will never have to read,
score, and sort 1000s of entries on each invocation of git-send-email.

Signed-off-by: Rasmus Villemoes <rv@rasmusvillemoes.dk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
revision: introduce --exclude=<glob> to tame wildcards

People often find "git log --branches" etc. that includes _all_
branches is cumbersome to use when they want to grab most but except
some.  The same applies to --tags, --all and --glob.

Teach the revision machinery to remember patterns, and then upon the
next such a globbing option, exclude those that match the pattern.

With this, I can view only my integration branches (e.g. maint,
master, etc.) without topic branches, which are named after two
letters from primary authors' names, slash and topic name.

    git rev-list --no-walk --exclude=??/* --branches |
    git name-rev --refs refs/heads/* --stdin

This one shows things reachable from local and remote branches that
have not been merged to the integration branches.

    git log --remotes --branches --not --exclude=??/* --branches

It may be a bit rough around the edges, in that the pattern to give
the exclude option depends on what globbing option follows.  In
these examples, the pattern "??/*" is used, not "refs/heads/??/*",
because the globbing option that follows the -"-exclude=<pattern>"
is "--branches".  As each use of globbing option resets previously
set "--exclude", this may not be such a bad thing, though.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
perf-lib: split starting the test from the execution

Separate the execution part to make future changes to the tests simpler.

Signed-off-by: Thomas Gummerer <t.gummerer@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
perf-lib: add test_perf_cleanup target

Currently there is no way to clean up the changes that have been made
with test_perf for the next run.  Add a way to reset the repository to
the state before the test for testing commands that modify the git
repository, e.g. for perf testing git add.

Signed-off-by: Thomas Gummerer <t.gummerer@gmail.com>
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>
submodule: don't access the .gitmodules cache entry after removing it

Commit 5fee995244e introduced the stage_updated_gitmodules() function to
add submodule configuration updates to the index. It assumed that even
after calling remove_cache_entry_at() the same cache entry would still be
valid. This was true in the old days, as cache entries could never be
freed, but that is not so sure in the present as there is ongoing work to
free removed cache entries, which makes this code segfault.

Fix that by calling add_file_to_cache() instead of open coding it. Also
remove the "could not find .gitmodules in index" warning, as that won't
happen in regular use cases (and by then just silently adding it to the
index we do the right thing).

Thanks-to: Karsten Blees <karsten.blees@gmail.com>
Signed-off-by: Jens Lehmann <Jens.Lehmann@web.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
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>
t5510: use the correct tag name in test

Fix an apparent copy-paste error: A few lines earlier, a tag
"refs/tags/sometag" is created.  Check for the (non-)existence of that
tag, not "somebranch", which is otherwise never mentioned in the
script.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: Junio C Hamano <gitster@pobox.com>