read-cache: add index reading api

Add an api for access to the index file.  Currently there is only a very
basic api for accessing the index file, which only allows a full read of
the index, and lets the users of the data filter it.  The new index api
gives the users the possibility to use only part of the api and provides
functions for iterating over the cache entries.

Functions of the api, that read the index filtered can only be used by
commands that don't need to write the index afterwards.  They will be
used by other commands only after a api for writing is implemented.

The api consists of the following functions:

cache_open():
  Open the index at its default location and do the basic checking if
  the index is not currupt and has the right version.

cache_open_from(char *path):
  Open the cache from a specified path and do the same checking as
  cache_open().

read_cache_full():
  Read the whole index, as the current read_cache() function but the
  index has to be opened before.  read_cache_full() will fail otherwise.

read_cache_filtered(opts):
  Read the index filtered by the opts given.

for_each_cached_entry(ce, i):
  Iterate over all the index entries that are in the in-memory index.
  ce: the current cache_entry
  i: the number of the current cache_entry

for_each_cache_entry(ce, i):
  Open and read the index and then iterate over all the index entries.
  ce: the current cache_entry
  i: the number of the current cache_entry

for_each_cache_entry_filtered(ce, i, opts)
  Open and read the index filtered by the opts given and iterate over
  the read entries.

opts are the parameters by which the index will be filtered.
The following options are supported:

pathspec: The pathspec with which the entries will be matched.
seen: A mark is left in this array, for each pathspec element that actually
  matched something.
prefix: A prefix, which doesn't have to be checked (will usually be 0)
read_staged: If 0 no entries with a stage will be read, if 1 all entries
  will be read
read_cache_tree: Read the cache tree data
read_resolve_undo: Read the resolve undo data

Signed-off-by: Thomas Gummerer <t.gummerer@gmail.com>

fixup

fixup for api

index api fixup
read-cache: make read_index() use index api

Make the read_cache() funtion use the index api, instead of its own
code.  This provides no runtime penalty, and removes some code, which
would be redundand with the api.  The function still needs to be
around for compatibility reasons, until all code uses the index api.

Test                                        bfd742c           25e39df
------------------------------------------------------------------------------------
0002.2: v[23]: update-index                 0.10(0.07+0.02)   0.10(0.07+0.02) +0.0%
0002.3: v[23]: grep nonexistent -- subdir   0.11(0.08+0.02)   0.11(0.09+0.02) +0.0%
0002.4: v[23]: ls-files -- subdir           0.10(0.06+0.02)   0.10(0.08+0.02) +0.0%
0002.6: v4: update-index                    0.08(0.05+0.02)   0.08(0.05+0.02) +0.0%
0002.7: v4: grep nonexistent -- subdir      0.10(0.07+0.02)   0.09(0.07+0.02) -10.0%
0002.8: v4: ls-files -- subdir              0.08(0.05+0.03)   0.08(0.06+0.02) +0.0%

Signed-off-by: Thomas Gummerer <t.gummerer@gmail.com>
grep: Use index api

Make grep use the new index reading api, instead of the old read_cache()
function.

Signed-off-by: Thomas Gummerer <t.gummerer@gmail.com>
ls-files: use the index api

Make git ls-files use the new index reading api.

Signed-off-by: Thomas Gummerer <t.gummerer@gmail.com>
t2104: Don't fail for index versions other than [23]

t2104 currently checks for the exact index version 2 or 3,
depending if there is a skip-worktree flag or not. Other
index versions do not use extended flags and thus cannot
be tested for version changes.

Make this test update the index to version 2 at the beginning
of the test. Testing the skip-worktree flags for the default
index format is still covered by t7011 and t7012.

Signed-off-by: Thomas Gummerer <t.gummerer@gmail.com>
Add documentation of the index-v5 file format

Add a documentation of the index file format version 5 to
Documentation/technical.

Helped-by: Michael Haggerty <mhagger@alum.mit.edu>
Helped-by: Junio C Hamano <gitster@pobox.com>
Helped-by: Thomas Rast <trast@student.ethz.ch>
Helped-by: Nguyen Thai Ngoc Duy <pclouds@gmail.com>
Helped-by: Robin Rosenberg <robin.rosenberg@dewire.com>
Signed-off-by: Thomas Gummerer <t.gummerer@gmail.com>
Make in-memory format aware of stat_crc

Make the in-memory format aware of the stat_crc used by index-v5.
It is simply ignored by index version prior to v5.

Signed-off-by: Thomas Gummerer <t.gummerer@gmail.com>
Read index-v5

Make git read the index file version 5 without complaining.

This version of the reader doesn't read neither the cache-tree
nor the resolve undo data, but doesn't choke on an index that
includes such data.

Helped-by: Junio C Hamano <gitster@pobox.com>
Helped-by: Nguyen Thai Ngoc Duy <pclouds@gmail.com>
Helped-by: Thomas Rast <trast@student.ethz.ch>
Signed-off-by: Thomas Gummerer <t.gummerer@gmail.com>
Read resolve-undo data

Make git read the resolve-undo data from the index.

Since the resolve-undo data is joined with the conflicts in
the ondisk format of the index file version 5, conflicts and
resolved data is read at the same time, and the resolve-undo
data is then converted to the in-memory format.

Helped-by: Thomas Rast <trast@student.ethz.ch>
Signed-off-by: Thomas Gummerer <t.gummerer@gmail.com>
Read cache-tree in index-v5

Since the cache-tree data is saved as part of the directory data,
we already read it at the beginning of the index. The cache-tree
is only converted from this directory data.

The cache-tree data is arranged in a tree, with the children sorted by
pathlen at each node, while the ondisk format is sorted lexically.
So we have to rebuild this format from the on-disk directory list.

Signed-off-by: Thomas Gummerer <t.gummerer@gmail.com>
Write index-v5

Write the index version 5 file format to disk. This version doesn't
write the cache-tree data and resolve-undo data to the file.

The main work is done when filtering out the directories from the
current in-memory format, where in the same turn also the conflicts
and the file data is calculated.

Helped-by: Nguyen Thai Ngoc Duy <pclouds@gmail.com>
Helped-by: Thomas Rast <trast@student.ethz.ch>
Signed-off-by: Thomas Gummerer <t.gummerer@gmail.com>
Write index-v5 cache-tree data

Write the cache-tree data for the index version 5 file format. The
in-memory cache-tree data is converted to the ondisk format, by adding
it to the directory entries, that were compiled from the cache-entries
in the step before.

Signed-off-by: Thomas Gummerer <t.gummerer@gmail.com>
Write resolve-undo data for index-v5

Make git read the resolve-undo data from the index.

Since the resolve-undo data is joined with the conflicts in
the ondisk format of the index file version 5, conflicts and
resolved data is read at the same time, and the resolve-undo
data is then converted to the in-memory format.

Helped-by: Thomas Rast <trast@student.ethz.ch>
Signed-off-by: Thomas Gummerer <t.gummerer@gmail.com>
update-index.c: rewrite index when index-version is given

Make update-index always rewrite the index when a index-version
is given, even if the index already has the right version.
This option is used for performance testing the writer and
reader.

Signed-off-by: Thomas Gummerer <t.gummerer@gmail.com>
p0002-index.sh: add perf test for the index formats

Add a performance test for index version [23]/4/5 by using
git update-index --index-version=x, thus testing both the reader
and the writer speed of all index formats.

Signed-off-by: Thomas Rast <trast@student.ethz.ch>
Signed-off-by: Thomas Gummerer <t.gummerer@gmail.com>
read-cache-v5: add index reading api for index v5

Add the index reading api for the index v5 format, which really takes
advantage of it, by only loading the part of the index file that is
necessary.  Following are the times from the p0002-index performance
test, using the Webkit repository.

Test                                        this tree
-----------------------------------------------------------
0002.2: v[23]: update-index                 0.21(0.16+0.03)
0002.3: v[23]: grep nonexistent -- subdir   0.10(0.07+0.02)
0002.4: v[23]: ls-files -- subdir           0.10(0.08+0.01)
0002.6: v4: update-index                    0.18(0.14+0.03)
0002.7: v4: grep nonexistent -- subdir      0.08(0.05+0.02)
0002.8: v4: ls-files -- subdir              0.08(0.05+0.02)
0002.10: v5: update-index                   0.14(0.11+0.02)
0002.11: v5: grep nonexistent -- subdir     0.01(0.00+0.00)
0002.12: v5: ls-files -- subdir             0.00(0.00+0.00)

Helped-by: Thomas Rast <trast@student.ethz.ch>
Signed-off-by: Thomas Gummerer <t.gummerer@gmail.com>