From: Thomas Gummerer <t.gummerer@gmail.com>
To: git@vger.kernel.org
Cc: t.gummerer@gmail.com, trast@inf.ethz.ch, mhagger@alum.mit.edu,
gitster@pobox.com, pclouds@gmail.com, robin.rosenberg@dewire.com,
sunshine@sunshineco.com
Subject: [PATCH v2 14/19] read-cache: read cache-tree in index-v5
Date: Fri, 12 Jul 2013 19:26:59 +0200 [thread overview]
Message-ID: <1373650024-3001-15-git-send-email-t.gummerer@gmail.com> (raw)
In-Reply-To: <1373650024-3001-1-git-send-email-t.gummerer@gmail.com>
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>
---
cache-tree.c | 2 +-
cache-tree.h | 6 ++++
read-cache-v5.c | 100 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 107 insertions(+), 1 deletion(-)
diff --git a/cache-tree.c b/cache-tree.c
index 37e4d00..f4b0917 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -31,7 +31,7 @@ void cache_tree_free(struct cache_tree **it_p)
*it_p = NULL;
}
-static int subtree_name_cmp(const char *one, int onelen,
+int subtree_name_cmp(const char *one, int onelen,
const char *two, int twolen)
{
if (onelen < twolen)
diff --git a/cache-tree.h b/cache-tree.h
index 55d0f59..9aac493 100644
--- a/cache-tree.h
+++ b/cache-tree.h
@@ -21,10 +21,16 @@ struct cache_tree {
struct cache_tree_sub **down;
};
+struct directory_queue {
+ struct directory_queue *down;
+ struct directory_entry *de;
+};
+
struct cache_tree *cache_tree(void);
void cache_tree_free(struct cache_tree **);
void cache_tree_invalidate_path(struct cache_tree *, const char *);
struct cache_tree_sub *cache_tree_sub(struct cache_tree *, const char *);
+int subtree_name_cmp(const char *, int, const char *, int);
void cache_tree_write(struct strbuf *, struct cache_tree *root);
struct cache_tree *cache_tree_read(const char *buffer, unsigned long size);
diff --git a/read-cache-v5.c b/read-cache-v5.c
index 853b97d..0b9c320 100644
--- a/read-cache-v5.c
+++ b/read-cache-v5.c
@@ -448,6 +448,103 @@ static int read_conflicts(struct conflict_entry **head,
return 0;
}
+static struct cache_tree *convert_one(struct directory_queue *queue, int dirnr)
+{
+ int i, subtree_nr;
+ struct cache_tree *it;
+ struct directory_queue *down;
+
+ it = cache_tree();
+ it->entry_count = queue[dirnr].de->de_nentries;
+ subtree_nr = queue[dirnr].de->de_nsubtrees;
+ if (0 <= it->entry_count)
+ hashcpy(it->sha1, queue[dirnr].de->sha1);
+
+ /*
+ * Just a heuristic -- we do not add directories that often but
+ * we do not want to have to extend it immediately when we do,
+ * hence +2.
+ */
+ it->subtree_alloc = subtree_nr + 2;
+ it->down = xcalloc(it->subtree_alloc, sizeof(struct cache_tree_sub *));
+ down = queue[dirnr].down;
+ for (i = 0; i < subtree_nr; i++) {
+ struct cache_tree *sub;
+ struct cache_tree_sub *subtree;
+ char *buf, *name;
+
+ name = "";
+ buf = strtok(down[i].de->pathname, "/");
+ while (buf) {
+ name = buf;
+ buf = strtok(NULL, "/");
+ }
+ sub = convert_one(down, i);
+ if(!sub)
+ goto free_return;
+ subtree = cache_tree_sub(it, name);
+ subtree->cache_tree = sub;
+ }
+ if (subtree_nr != it->subtree_nr)
+ die("cache-tree: internal error");
+ return it;
+ free_return:
+ cache_tree_free(&it);
+ return NULL;
+}
+
+static int compare_cache_tree_elements(const void *a, const void *b)
+{
+ const struct directory_entry *de1, *de2;
+
+ de1 = ((const struct directory_queue *)a)->de;
+ de2 = ((const struct directory_queue *)b)->de;
+ return subtree_name_cmp(de1->pathname, de1->de_pathlen,
+ de2->pathname, de2->de_pathlen);
+}
+
+static struct directory_entry *sort_directories(struct directory_entry *de,
+ struct directory_queue *queue)
+{
+ int i, nsubtrees;
+
+ nsubtrees = de->de_nsubtrees;
+ for (i = 0; i < nsubtrees; i++) {
+ struct directory_entry *new_de;
+ de = de->next;
+ new_de = xmalloc(directory_entry_size(de->de_pathlen));
+ memcpy(new_de, de, directory_entry_size(de->de_pathlen));
+ queue[i].de = new_de;
+ if (de->de_nsubtrees) {
+ queue[i].down = xcalloc(de->de_nsubtrees,
+ sizeof(struct directory_queue));
+ de = sort_directories(de,
+ queue[i].down);
+ }
+ }
+ qsort(queue, nsubtrees, sizeof(struct directory_queue),
+ compare_cache_tree_elements);
+ return de;
+}
+
+/*
+ * This function modifies the directory argument that is given to it.
+ * Don't use it if the directory entries are still needed after.
+ */
+static struct cache_tree *cache_tree_convert_v5(struct directory_entry *de)
+{
+ struct directory_queue *queue;
+
+ if (!de->de_nentries)
+ return NULL;
+ queue = xcalloc(1, sizeof(struct directory_queue));
+ queue[0].de = de;
+ queue[0].down = xcalloc(de->de_nsubtrees, sizeof(struct directory_queue));
+
+ sort_directories(de, queue[0].down);
+ return convert_one(queue, 0);
+}
+
static void resolve_undo_convert_v5(struct index_state *istate,
struct conflict_entry *conflict)
{
@@ -644,6 +741,7 @@ static int read_index_filtered_v5(struct index_state *istate, void *mmap,
} else
de = de->next;
}
+ istate->cache_tree = cache_tree_convert_v5(root_directory);
istate->cache_nr = nr;
return 0;
}
@@ -665,6 +763,8 @@ static int read_index_v5(struct index_state *istate, void *mmap,
if (read_entries(istate, &de, &entry_offset, &mmap,
mmap_size, &nr, &foffsetblock) < 0)
return -1;
+
+ istate->cache_tree = cache_tree_convert_v5(root_directory);
istate->cache_nr = nr;
return 0;
}
--
1.8.3.453.g1dfc63d
next prev parent reply other threads:[~2013-07-12 17:31 UTC|newest]
Thread overview: 51+ messages / expand[flat|nested] mbox.gz Atom feed top
2013-07-12 17:26 [PATCH v2 00/19] Index-v5 Thomas Gummerer
2013-07-12 17:26 ` [PATCH v2 01/19] t2104: Don't fail for index versions other than [23] Thomas Gummerer
2013-07-12 17:26 ` [PATCH v2 02/19] read-cache: split index file version specific functionality Thomas Gummerer
2013-07-12 17:26 ` [PATCH v2 03/19] read-cache: move index v2 specific functions to their own file Thomas Gummerer
2013-07-14 3:10 ` Duy Nguyen
2013-07-19 14:53 ` Thomas Gummerer
2013-07-12 17:26 ` [PATCH v2 04/19] read-cache: Re-read index if index file changed Thomas Gummerer
2013-07-12 17:26 ` [PATCH v2 05/19] Add documentation for the index api Thomas Gummerer
2013-07-12 17:26 ` [PATCH v2 06/19] read-cache: add index reading api Thomas Gummerer
2013-07-14 3:21 ` Duy Nguyen
2013-07-12 17:26 ` [PATCH v2 07/19] make sure partially read index is not changed Thomas Gummerer
2013-07-14 3:29 ` Duy Nguyen
2013-07-17 12:56 ` Thomas Gummerer
2013-07-12 17:26 ` [PATCH v2 08/19] grep.c: Use index api Thomas Gummerer
2013-07-14 3:32 ` Duy Nguyen
2013-07-15 9:51 ` Thomas Gummerer
2013-07-12 17:26 ` [PATCH v2 09/19] ls-files.c: use " Thomas Gummerer
2013-07-14 3:39 ` Duy Nguyen
2013-07-17 8:07 ` Thomas Gummerer
2013-07-12 17:26 ` [PATCH v2 10/19] documentation: add documentation of the index-v5 file format Thomas Gummerer
2013-07-14 3:59 ` Duy Nguyen
2013-07-17 8:09 ` Thomas Gummerer
2013-08-04 11:26 ` Duy Nguyen
2013-08-04 17:58 ` Thomas Gummerer
2013-07-12 17:26 ` [PATCH v2 11/19] read-cache: make in-memory format aware of stat_crc Thomas Gummerer
2013-07-12 17:26 ` [PATCH v2 12/19] read-cache: read index-v5 Thomas Gummerer
2013-07-14 4:42 ` Duy Nguyen
2013-08-07 8:13 ` Thomas Gummerer
2013-07-15 10:12 ` Duy Nguyen
2013-07-17 8:11 ` Thomas Gummerer
2013-08-08 2:00 ` Duy Nguyen
2013-08-08 13:28 ` Thomas Gummerer
2013-08-09 13:10 ` Thomas Gummerer
2013-08-07 8:23 ` Thomas Gummerer
2013-08-08 2:09 ` Duy Nguyen
2013-07-12 17:26 ` [PATCH v2 13/19] read-cache: read resolve-undo data Thomas Gummerer
2013-07-12 17:26 ` Thomas Gummerer [this message]
2013-07-12 17:27 ` [PATCH v2 15/19] read-cache: write index-v5 Thomas Gummerer
2013-07-12 17:27 ` [PATCH v2 16/19] read-cache: write index-v5 cache-tree data Thomas Gummerer
2013-07-12 17:27 ` [PATCH v2 17/19] read-cache: write resolve-undo data for index-v5 Thomas Gummerer
2013-07-12 17:27 ` [PATCH v2 18/19] update-index.c: rewrite index when index-version is given Thomas Gummerer
2013-07-12 17:27 ` [PATCH v2 19/19] p0003-index.sh: add perf test for the index formats Thomas Gummerer
2013-07-14 2:59 ` [PATCH v2 00/19] Index-v5 Duy Nguyen
2013-07-15 9:30 ` Thomas Gummerer
2013-07-15 9:38 ` Duy Nguyen
2013-07-17 8:12 ` Thomas Gummerer
2013-07-17 23:58 ` Junio C Hamano
2013-07-19 17:37 ` Thomas Gummerer
2013-07-19 18:25 ` Junio C Hamano
2013-07-16 21:03 ` Ramsay Jones
2013-07-17 8:04 ` Thomas Gummerer
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1373650024-3001-15-git-send-email-t.gummerer@gmail.com \
--to=t.gummerer@gmail.com \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=mhagger@alum.mit.edu \
--cc=pclouds@gmail.com \
--cc=robin.rosenberg@dewire.com \
--cc=sunshine@sunshineco.com \
--cc=trast@inf.ethz.ch \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).