git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH 11/16] Read cache-tree in index-v5

From
Thomas Gummerer <t.gummerer@gmail.com>
Date
Aug 2, 2012, 11:02 UTC
Message-ID
<1343905326-23790-12-git-send-email-t.gummerer@gmail.com>
In-Reply-To
<1343905326-23790-1-git-send-email-t.gummerer@gmail.com>

Since the cache-tree data is saved as part of the directory data, we have already read it, when we want to read the cache-tree. The cache-tree then only has to be converted from the directory data.

The cache-tree isn't lexically sorted, but after the pathlen at each level, therefore the directories have to be reordered with respect to the ondisk layout.

Signed-off-by: Thomas Gummerer <t.gummerer@gmail.com>
---
 cache-tree.c | 93 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 cache-tree.h |  6 ++++
 read-cache.c |  1 +
 3 files changed, 100 insertions(+)
diff --git a/cache-tree.c b/cache-tree.c
index 28ed657..6a314aa 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -519,6 +519,99 @@ struct cache_tree *cache_tree_read(const char *buffer, unsigned long size)
 	return read_one(&buffer, &size);
 }
 
+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;
+}
+
+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 struct cache_tree *cache_tree_find(struct cache_tree *it, const char *path)
 {
 	if (!it)
diff --git a/cache-tree.h b/cache-tree.h
index d8cb2e9..f4131a6 100644
--- a/cache-tree.h
+++ b/cache-tree.h
@@ -20,6 +20,11 @@ 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 *);
@@ -27,6 +32,7 @@ struct cache_tree_sub *cache_tree_sub(struct cache_tree *, const char *);
 
 void cache_tree_write(struct strbuf *, struct cache_tree *root);
 struct cache_tree *cache_tree_read(const char *buffer, unsigned long size);
+struct cache_tree *cache_tree_convert_v5(struct directory_entry *de);
 
 int cache_tree_fully_valid(struct cache_tree *);
 int cache_tree_update(struct cache_tree *, struct cache_entry **, int, int);
diff --git a/read-cache.c b/read-cache.c
index cef9a4e..fd095ec 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -2054,6 +2054,7 @@ void read_index_v5(struct index_state *istate, void *mmap, int mmap_size, int fd
 	while (de)
 		de = read_entries_v5(istate, de, &entry_offset,
 				&mmap, mmap_size, &nr, &foffsetblock, fd);
+	istate->cache_tree = cache_tree_convert_v5(root_directory);
 }
 
 /* remember to discard_cache() before reading a different cache! */

-- 
1.7.10.886.gdf6792c.dirty
Previous: Thomas GummererNext: Thomas Rast
Message 22 of 38 in “[RFC 0/16] Introduce index file format version 5”
  1. Thomas GummererAug 2, 2012
  2. 01/16 Modify cache_header to prepare for other index formatsThomas Gummerer, Aug 2, 2012
  3. Nguyen Thai Ngoc DuyAug 2, 2012
  4. 02/16 Modify read functions to prepare for other index formatsThomas Gummerer, Aug 2, 2012
  5. 03/16 Modify match_stat_basic to prepare for other index formatsThomas Gummerer, Aug 2, 2012
  6. Nguyen Thai Ngoc DuyAug 2, 2012
  7. Thomas GummererAug 2, 2012
  8. 04/16 Modify write functions to prepare for other index formatsThomas Gummerer, Aug 2, 2012
  9. Nguyen Thai Ngoc DuyAug 2, 2012
  10. Thomas GummererAug 2, 2012
  11. 05/16 t2104: Don't fail when index version is 5Thomas Gummerer, Aug 2, 2012
  12. Thomas RastAug 3, 2012
  13. Thomas GummererAug 3, 2012
  14. Junio C HamanoAug 3, 2012
  15. 06/16 t3700: sleep for 1 second, to avoid interfering with the racy codeThomas Gummerer, Aug 2, 2012
  16. 07/16 Add documentation of the index-v5 file formatThomas Gummerer, Aug 2, 2012
  17. 08/16 Make in-memory format aware of stat_crcThomas Gummerer, Aug 2, 2012
  18. 09/16 Read index-v5Thomas Gummerer, Aug 2, 2012
  19. Nguyen Thai Ngoc DuyAug 2, 2012
  20. Thomas GummererAug 2, 2012
  21. 10/16 Read resolve-undo dataThomas Gummerer, Aug 2, 2012
  22. 11/16 Read cache-tree in index-v5Thomas Gummerer, Aug 2, 2012
  23. Thomas RastAug 3, 2012
  24. Thomas GummererAug 3, 2012
  25. 12/16 Write index-v5Thomas Gummerer, Aug 2, 2012
  26. 13/16 Write index-v5 cache-tree dataThomas Gummerer, Aug 2, 2012
  27. 14/16 Write resolve-undo data for index-v5Thomas Gummerer, Aug 2, 2012
  28. 15/16 update-index.c: add a force-rewrite optionThomas Gummerer, Aug 2, 2012
  29. 16/16 p0002-index.sh: add perf test for the index formatsThomas Gummerer, Aug 2, 2012
  30. Nguyen Thai Ngoc DuyAug 2, 2012
  31. Thomas GummererAug 2, 2012
  32. Nguyen Thai Ngoc DuyAug 2, 2012
  33. Thomas GummererAug 2, 2012
  34. Nguyen Thai Ngoc DuyAug 2, 2012
  35. Nguyen Thai Ngoc DuyAug 3, 2012
  36. Thomas GummererAug 3, 2012
  37. Thomas RastAug 3, 2012
  38. Thomas GummererAug 3, 2012

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.