commit: allow associating auxiliary info on-demand

The "indegree" field in the commit object is only used while sorting
a list of commits in topological order, and wasting memory otherwise.

We would prefer to shrink the size of individual commit objects,
which we may have to hold thousands of in-core. We could eject
"indegree" field out from the commit object and represent it as a
dynamic table based on the decoration infrastructure, but the
decoration is meant for sparse annotation and is not a good match.

Instead, let's try a different approach.

 - Assign an integer (commit->index) to each commit we keep in-core
   (reuse the space of "indegree" field for it);

 - When running the topological sort, allocate an array of integers
   in bulk (called "slab"), use the commit->index as an index into
   this array, and store the "indegree" information there.

This does _not_ reduce the memory footprint of a commit object, but
the commit->index can be used as the index to dynamically associate
commits with other kinds of information as needed.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
commit-slab: avoid large realloc

Instead of using a single "slab" and keep reallocating it as we find
that we need to deal with commits with larger values of commit->index,
make a "slab" an array of many "slab_piece"s. Each access may need
two levels of indirections, but we only need to reallocate the first
level array of pointers when we have to grow the table this way.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
Makefile: Do not use OLD_ICONV on MINGW anymore

We are building libiconv now the same way as upstream MinGW does, so we do
not need OLD_ICONV anymore when compiling Git either in msysGit or
mingwGitDevEnv.

Signed-off-by: Sebastian Schuberth <sschuberth@gmail.com>
Define NO_GETTEXT for Git for Windows

The dreaded "your vnsprintf is broken (returned -1)" error is back. At
least with the libintl version we have. So for the moment, just work
around the issue by _not_ using gettext.

Ah, I wish that my attempt at implementing a custom strbuf_vaddf() would
not have been brushed aside so rashly. Oh well. Time saved on maintaining
that thing, I guess (although more time went into working around coping
with existing implementations).

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
msysgit: Add the --large-address-aware linker directive to the makefile.

This has the effect of increasing the address space from 2GB to 4GB under
64-bit Windows, reducing the likelihood of an "out of memory" error when
e.g.  repacking a large repository.  The test suite passes with this
patch, with and without the MEM_TOP_DOWN flag added to all VirtualAlloc
calls.  While this is no guarantee that there are no issues with large
memory support (it could break Git on other setups than mine, for
example), it at least increases the chance that nothing obvious goes wrong
(such as errors introduced by faulty sign extension, say, with ssize_t).

[PT: Resolves github issue #12]

Signed-off-by: Pierre le Riche <github@pleasedontspam.me>
Signed-off-by: Pat Thoyts <patthoyts@users.sourceforge.net>
Provide a Windows version resource for the git executables.

Embeds the git version and description into the git executable thus
implementing the request in issue #5.

Acked-by: Heiko Voigt <hvoigt@hvoigt.net>
Acked-by: Sebastian Schuberth <sschuberth@gmail.com>
Acked-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: Pat Thoyts <patthoyts@users.sourceforge.net>
Windows resource: handle dashes in the Git version gracefully

Reported by postiffm as issue #14.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Ensure the resource file is rebuilt when the version changes.

Acked-by: Erik Faye-Lund <kusmabite@gmail.com>
Acked-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: Pat Thoyts <patthoyts@users.sourceforge.net>
Set the default help format to html for msys builds.

This resolves issue #19 by setting the compiled default to html in msys
builds following the changes introduced by commit
1cc8af0 "help: use HTML as the default help format on Windows"

Signed-off-by: Pat Thoyts <patthoyts@users.sourceforge.net>
Merge tag 'post183-for-junio' of http://github.com/msysgit/git

Collected msysgit build patches for upstream

This set of patches collects a number of build fixes that have been
used on the msysgit port for a while and merging upstream should
simplify future maintenance.

* tag 'post183-for-junio' of http://github.com/msysgit/git:
  Set the default help format to html for msys builds.
  Ensure the resource file is rebuilt when the version changes.
  Windows resource: handle dashes in the Git version gracefully
  Provide a Windows version resource for the git executables.
  msysgit: Add the --large-address-aware linker directive to the makefile.
  Define NO_GETTEXT for Git for Windows
  Makefile: Do not use OLD_ICONV on MINGW anymore
fetch-options.txt: prevent a wildcard refspec from getting misformatted

When explaining the "--tags" option as an equivalent to giving an
explicit "refs/tags/*:refs/tags/*" refspec, the two asterisks were
misinterpreted by AsciiDoc as a request to typeset the string
segment between them in bold.

We could fix it in two ways.  We can replace them with {asterisk}s
while keeping the string as body text, or we can mark it as a
literal string with backquotes around it.

Let's do the latter, as it is teaching the user an "exactly as
typed" alternative.

Noticed-by: Ramkumar Ramachandra <artagnon@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
gitweb: fix problem causing erroneous project list

The bug is manifest when running gitweb in a persistent process (e.g.
FastCGI, PSGI), and it's easy to reproduce.  If a gitweb request
includes the searchtext parameter (i.e. s), subsequent requests using
the project_list action--which is the default action--and without
a searchtext parameter will be filtered by the searchtext value of the
first request.  This is because the value of the $search_regexp global
(the value of which is based on the searchtext parameter) is currently
being persisted between requests.

Instead, clear $search_regexp before dispatching each request.

Signed-off-by: Charles McGarvey <chazmcgarvey@brokenzipper.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
commit-slab: introduce a macro to define a slab for new type

Introduce a header file to define a macro that can define the struct
type, initializer, accessor and cleanup functions to manage a commit
slab.  Update the "indegree" topological sort facility using it.

To associate 32 flag bits with each commit, you can write:

	define_commit_slab(flag32, uint32);

to declare "struct flag32" type, define an instance of it with

	struct flag32 flags;

and initialize it by calling

	init_flag32(&flags);

After that, a call to flag32_at() function

	uint32 *fp = flag32_at(&flags, commit);

will return a pointer pointing at a uint32 for that commit.  Once
you are done with these flags, clean them up with

	clear_flag32(&flags);

Callers that cannot hard-code how wide the data to be associated
with the commit be at compile time can use the "_with_stride"
variant to initialize the slab.

Suppose you want to give one bit per existing ref, and paint commits
down to find which refs are descendants of each commit.  Saying

	typedef uint32 bits320[5];
	define_commit_slab(flagbits, bits320);

at compile time will still limit your code with hard-coded limit,
because you may find that you have more than 320 refs at runtime.

The code can declare a commit slab "struct flagbits" like this
instead:

	define_commit_slab(flagbits, unsigned char);
	struct flagbits flags;

and initialize it by:

	nrefs = ... count number of refs ...
	init_flagbits_with_stride(&flags, (nrefs + 7) / 8);

so that

	unsigned char *fp = flagbits_at(&flags, commit);

will return a pointer pointing at an array of 40 "unsigned char"s
associated with the commit, once you figure out nrefs is 320 at
runtime.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
toposort: rename "lifo" field

The primary invariant of sort_in_topological_order() is that a
parent commit is not emitted untile all children of it are.  When
traversing a forked history like this with "git log C E":

    A----B----C
     \
      D----E

we ensure that A is emitted after all of B, C, D, and E are done, B
has to wait until C is done, and D has to wait until E is done.

In some applications, however, we would further want to control how
these child commits B, C, D and E on two parallel ancestry chains
are shown.

Most of the time, we would want to see C and B emitted together, and
then E and D, and finally A (i.e. the --topo-order output).  The
"lifo" parameter of the sort_in_topological_order() function is used
to control this behaviour.  We start the traversal by knowing two
commits, C and E.  While keeping in mind that we also need to
inspect E later, we pick C first to inspect, and we notice and
record that B needs to be inspected.  By structuring the "work to be
done" set as a LIFO stack, we ensure that B is inspected next,
before other in-flight commits we had known that we will need to
inspect, e.g. E.

When showing in --date-order, we would want to see commits ordered
by timestamps, i.e. show C, E, B and D in this order before showing
A, possibly mixing commits from two parallel histories together.
When "lifo" parameter is set to false, the function keeps the "work
to be done" set sorted in the date order to realize this semantics.
After inspecting C, we add B to the "work to be done" set, but the
next commit we inspect from the set is E which is newer than B.

The name "lifo", however, is too strongly tied to the way how the
function implements its behaviour, and does not describe what the
behaviour _means_.

Replace this field with an enum rev_sort_order, with two possible
values: REV_SORT_IN_GRAPH_ORDER and REV_SORT_BY_COMMIT_DATE, and
update the existing code.  The mechanical replacement rule is:

  "lifo == 0" is equivalent to "sort_order == REV_SORT_BY_COMMIT_DATE"
  "lifo == 1" is equivalent to "sort_order == REV_SORT_IN_GRAPH_ORDER"

Signed-off-by: Junio C Hamano <gitster@pobox.com>
commit-queue: LIFO or priority queue of commits

Traditionally we used a singly linked list of commits to hold a set
of in-flight commits while traversing history.  The most typical use
of the list is to add commits that are newly discovered to it, keep
the list sorted by commit timestamp, pick up the newest one from the
list, and keep digging.  The cost of keeping the singly linked list
sorted is nontrivial, and this typical use pattern better matches a
priority queue.

Introduce a commit-queue structure, that can be used either as a
LIFO stack, or a priority queue.  This will be used in the next
patch to hold in-flight commits during sort-in-topological-order.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
sort-in-topological-order: use commit-queue

Use the commit-queue data structure to implement a priority queue
of commits sorted by committer date, when handling --date-order.
The commit-queue structure can also be used as a simple LIFO stack,
which is a good match for --topo-order processing.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
log: --author-date-order

Sometimes people would want to view the commits in parallel
histories in the order of author dates, not committer dates.

Teach "topo-order" sort machinery to do so, using a commit-info slab
to record the author dates of each commit, and commit-queue to sort
them.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
Merge branch 'rr/die-on-missing-upstream' into jch

When a reflog notation is used for implicit "current branch", we
did not say which branch and worse said "branch ''".

* rr/die-on-missing-upstream:
  sha1_name: fix error message for @{<N>}, @{<date>}
  sha1_name: fix error message for @{u}
Merge branch 'jk/test-exit-code-by-signal' into jch

* jk/test-exit-code-by-signal:
  t0005: skip signal death exit code test on Windows
  t0005: test git exit code from signal death
Merge branch 'rs/unpack-trees-plug-leak' into jch

* rs/unpack-trees-plug-leak:
  unpack-trees: free cache_entry array members for merges
  diff-lib, read-tree, unpack-trees: mark cache_entry array paramters const
  diff-lib, read-tree, unpack-trees: mark cache_entry pointers const
  unpack-trees: create working copy of merge entry in merged_entry
  unpack-trees: factor out dup_entry
  read-cache: mark cache_entry pointers const
  cache: mark cache_entry pointers const