{"thread":{"id":"3950","subject":"[PATCH 2/4] Add cache-tree.","startedAt":"2006-04-23T23:52:20Z","lastAt":"2006-04-23T23:52:20Z","messageCount":1,"participants":["Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"19024","messageId":"7vhd4jetor.fsf@assigned-by-dhcp.cox.net","threadId":"3950","inReplyTo":null,"subject":"[PATCH 2/4] Add cache-tree.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-04-23T23:52:20Z","receivedAt":"2006-04-23T23:52:20Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"The cache_tree data structure is to cache tree object names that\nwould result from the current index file.\n\nThe idea is to have an optional file to record each tree object\nname that corresponds to a directory path in the cache when we\nrun write_cache(), and read it back when we run read_cache().\nDuring various index manupulations, we selectively invalidate\nthe parts so that the next write-tree can bypass regenerating\ntree objects for unchanged parts of the directory hierarchy.\n\nWe could perhaps make the cache-tree data an optional part of\nthe index file, but that would involve the index format updates,\nso unless we need it for performance reasons, the current plan\nis to use a separate file, $GIT_DIR/index.aux to store this\ninformation and link it with the index file with the checksum\nthat is already used for index file integrity check.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n\n---\n\n * This is just the data structure and its maintenance, and not\n   tied to the rest of the system yet, which will be done with\n   the next two patches.\n\n Makefile     |    2 \n cache-tree.c |  522 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n cache-tree.h |   29 +++\n 3 files changed, 552 insertions(+), 1 deletions(-)\n create mode 100644 cache-tree.c\n create mode 100644 cache-tree.h\n\nc37a2dc93fb49dada5eec78f002eea9354e4fb4f\ndiff --git a/Makefile b/Makefile\nindex d9a3a82..518c3c1 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -204,7 +204,7 @@ DIFF_OBJS = \\\n \tdiffcore-delta.o log-tree.o\n \n LIB_OBJS = \\\n-\tblob.o commit.o connect.o csum-file.o \\\n+\tblob.o commit.o connect.o csum-file.o cache-tree.o \\\n \tdate.o diff-delta.o entry.o exec_cmd.o ident.o index.o \\\n \tobject.o pack-check.o patch-delta.o path.o pkt-line.o \\\n \tquote.o read-cache.o refs.o run-command.o \\\ndiff --git a/cache-tree.c b/cache-tree.c\nnew file mode 100644\nindex 0000000..c79da33\n--- /dev/null\n+++ b/cache-tree.c\n@@ -0,0 +1,522 @@\n+#include \"cache.h\"\n+#include \"tree.h\"\n+#include \"cache-tree.h\"\n+\n+#define DEBUG 0\n+\n+struct cache_tree *cache_tree(void)\n+{\n+\tstruct cache_tree *it = xcalloc(1, sizeof(struct cache_tree));\n+\tit->entry_count = -1; \n+\treturn it;\n+}\n+\n+void cache_tree_free(struct cache_tree *it)\n+{\n+\tint i;\n+\n+\tif (!it)\n+\t\treturn;\n+\tfor (i = 0; i < it->subtree_nr; i++)\n+\t\tcache_tree_free(it->down[i]->cache_tree);\n+\tfree(it->down);\n+\tfree(it);\n+}\n+\n+static struct cache_tree_sub *find_subtree(struct cache_tree *it,\n+\t\t\t\t\t   const char *path,\n+\t\t\t\t\t   int pathlen,\n+\t\t\t\t\t   int create)\n+{\n+\tint i;\n+\tstruct cache_tree_sub *down;\n+\tfor (i = 0; i < it->subtree_nr; i++) {\n+\t\tdown = it->down[i];\n+\t\tif (down->namelen == pathlen &&\n+\t\t    !memcmp(down->name, path, pathlen))\n+\t\t\treturn down;\n+\t}\n+\tif (!create)\n+\t\treturn NULL;\n+\tif (it->subtree_alloc <= it->subtree_nr) {\n+\t\tit->subtree_alloc = alloc_nr(it->subtree_alloc);\n+\t\tit->down = xrealloc(it->down, it->subtree_alloc *\n+\t\t\t\t    sizeof(*it->down));\n+\t}\n+\tdown = xmalloc(sizeof(*down) + pathlen + 1);\n+\tdown->cache_tree = NULL; /* cache_tree(); */\n+\tdown->namelen = pathlen;\n+\tmemcpy(down->name, path, pathlen);\n+\tdown->name[pathlen] = 0; /* not strictly needed */\n+\tit->down[it->subtree_nr++] = down;\n+\treturn down;\n+}\n+\n+void cache_tree_invalidate_path(struct cache_tree *it, const char *path)\n+{\n+\t/* a/b/c\n+\t * ==> invalidate self\n+\t * ==> find \"a\", have it invalidate \"b/c\"\n+\t * a\n+\t * ==> invalidate self\n+\t * ==> if \"a\" exists as a subtree, remove it.\n+\t */\n+\tconst char *slash;\n+\tint namelen;\n+\tstruct cache_tree_sub *down;\n+\n+\tif (!it)\n+\t\treturn;\n+\tslash = strchr(path, '/');\n+\tit->entry_count = -1; \n+\tif (!slash) {\n+\t\tint i;\n+\t\tnamelen = strlen(path);\n+\t\tfor (i = 0; i < it->subtree_nr; i++) {\n+\t\t\tif (it->down[i]->namelen == namelen &&\n+\t\t\t    !memcmp(it->down[i]->name, path, namelen))\n+\t\t\t\tbreak;\n+\t\t}\n+\t\tif (i < it->subtree_nr) {\n+\t\t\tcache_tree_free(it->down[i]->cache_tree);\n+\t\t\tfree(it->down[i]);\n+\t\t\t/* 0 1 2 3 4 5\n+\t\t\t *       ^     ^subtree_nr = 6\n+\t\t\t *       i\n+\t\t\t * move 4 and 5 up one place (2 entries)\n+\t\t\t * 2 = 6 - 3 - 1 = subtree_nr - i - 1\n+\t\t\t */\n+\t\t\tmemmove(it->down+i, it->down+i+1,\n+\t\t\t\tsizeof(struct cache_tree_sub *) *\n+\t\t\t\t(it->subtree_nr - i - 1));\n+\t\t\tit->subtree_nr--;\n+\t\t}\n+\t\treturn;\n+\t}\n+\tnamelen = slash - path;\n+\tdown = find_subtree(it, path, namelen, 0);\n+\tif (down)\n+\t\tcache_tree_invalidate_path(down->cache_tree, slash + 1);\n+}\n+\n+static int verify_cache(struct cache_entry **cache,\n+\t\t\tint entries)\n+{\n+\tint i, funny;\n+\n+\t/* Verify that the tree is merged */\n+\tfunny = 0;\n+\tfor (i = 0; i < entries; i++) {\n+\t\tstruct cache_entry *ce = cache[i];\n+\t\tif (ce_stage(ce)) {\n+\t\t\tif (10 < ++funny) {\n+\t\t\t\tfprintf(stderr, \"...\\n\");\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tfprintf(stderr, \"%s: unmerged (%s)\\n\",\n+\t\t\t\tce->name, sha1_to_hex(ce->sha1));\n+\t\t}\n+\t}\n+\tif (funny)\n+\t\treturn -1;\n+\n+\t/* Also verify that the cache does not have path and path/file\n+\t * at the same time.  At this point we know the cache has only\n+\t * stage 0 entries.\n+\t */\n+\tfunny = 0;\n+\tfor (i = 0; i < entries - 1; i++) {\n+\t\t/* path/file always comes after path because of the way\n+\t\t * the cache is sorted.  Also path can appear only once,\n+\t\t * which means conflicting one would immediately follow.\n+\t\t */\n+\t\tconst char *this_name = cache[i]->name;\n+\t\tconst char *next_name = cache[i+1]->name;\n+\t\tint this_len = strlen(this_name);\n+\t\tif (this_len < strlen(next_name) &&\n+\t\t    strncmp(this_name, next_name, this_len) == 0 &&\n+\t\t    next_name[this_len] == '/') {\n+\t\t\tif (10 < ++funny) {\n+\t\t\t\tfprintf(stderr, \"...\\n\");\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tfprintf(stderr, \"You have both %s and %s\\n\",\n+\t\t\t\tthis_name, next_name);\n+\t\t}\n+\t}\n+\tif (funny)\n+\t\treturn -1;\n+\treturn 0;\n+}\n+\n+static void discard_unused_subtrees(struct cache_tree *it)\n+{\n+\tstruct cache_tree_sub **down = it->down;\n+\tint nr = it->subtree_nr;\n+\tint dst, src;\n+\tfor (dst = src = 0; src < nr; src++) {\n+\t\tstruct cache_tree_sub *s = down[src];\n+\t\tif (s->used)\n+\t\t\tdown[dst++] = s;\n+\t\telse {\n+\t\t\tcache_tree_free(s->cache_tree);\n+\t\t\tfree(s);\n+\t\t\tit->subtree_nr--;\n+\t\t}\n+\t}\n+}\n+\n+static int update_one(struct cache_tree *it,\n+\t\t      struct cache_entry **cache,\n+\t\t      int entries,\n+\t\t      const char *base,\n+\t\t      int baselen,\n+\t\t      int missing_ok)\n+{\n+\tunsigned long size, offset;\n+\tchar *buffer;\n+\tint i;\n+\n+\tif (0 <= it->entry_count)\n+\t\treturn it->entry_count;\n+\n+\t/*\n+\t * We first scan for subtrees and update them; we start by\n+\t * marking existing subtrees -- the ones that are unmarked\n+\t * should not be in the result.\n+\t */\n+\tfor (i = 0; i < it->subtree_nr; i++)\n+\t\tit->down[i]->used = 0;\n+\n+\t/*\n+\t * Find the subtrees and update them.\n+\t */\n+\tfor (i = 0; i < entries; i++) {\n+\t\tstruct cache_entry *ce = cache[i];\n+\t\tstruct cache_tree_sub *sub;\n+\t\tconst char *path, *slash;\n+\t\tint pathlen, sublen, subcnt;\n+\n+\t\tpath = ce->name;\n+\t\tpathlen = ce_namelen(ce);\n+\t\tif (pathlen <= baselen || memcmp(base, path, baselen))\n+\t\t\tbreak; /* at the end of this level */\n+\n+\t\tslash = strchr(path + baselen, '/');\n+\t\tif (!slash)\n+\t\t\tcontinue;\n+\t\t/*\n+\t\t * a/bbb/c (base = a/, slash = /c)\n+\t\t * ==>\n+\t\t * path+baselen = bbb/c, sublen = 3\n+\t\t */\n+\t\tsublen = slash - (path + baselen);\n+\t\tsub = find_subtree(it, path + baselen, sublen, 1);\n+\t\tif (!sub->cache_tree)\n+\t\t\tsub->cache_tree = cache_tree();\n+\t\tsubcnt = update_one(sub->cache_tree,\n+\t\t\t\t    cache + i, entries - i,\n+\t\t\t\t    path,\n+\t\t\t\t    baselen + sublen + 1,\n+\t\t\t\t    missing_ok);\n+\t\ti += subcnt - 1;\n+\t\tsub->used = 1;\n+\t}\n+\n+\tdiscard_unused_subtrees(it);\n+\n+\t/*\n+\t * Then write out the tree object for this level.\n+\t */\n+\tsize = 8192;\n+\tbuffer = xmalloc(size);\n+\toffset = 0;\n+\n+\tfor (i = 0; i < entries; i++) {\n+\t\tstruct cache_entry *ce = cache[i];\n+\t\tstruct cache_tree_sub *sub;\n+\t\tconst char *path, *slash;\n+\t\tint pathlen, entlen;\n+\t\tconst unsigned char *sha1;\n+\t\tunsigned mode;\n+\n+\t\tpath = ce->name;\n+\t\tpathlen = ce_namelen(ce);\n+\t\tif (pathlen <= baselen || memcmp(base, path, baselen))\n+\t\t\tbreak; /* at the end of this level */\n+\n+\t\tslash = strchr(path + baselen, '/');\n+\t\tif (slash) {\n+\t\t\tentlen = slash - (path + baselen);\n+\t\t\tsub = find_subtree(it, path + baselen, entlen, 0);\n+\t\t\tif (!sub)\n+\t\t\t\tdie(\"cache-tree.c: '%.*s' in '%s' not found\",\n+\t\t\t\t    entlen, path + baselen, path);\n+\t\t\ti += sub->cache_tree->entry_count - 1;\n+\t\t\tsha1 = sub->cache_tree->sha1;\n+\t\t\tmode = S_IFDIR;\n+\t\t}\n+\t\telse {\n+\t\t\tsha1 = ce->sha1;\n+\t\t\tmode = ntohl(ce->ce_mode);\n+\t\t\tentlen = pathlen - baselen;\n+\t\t}\n+\t\tif (!missing_ok && !has_sha1_file(sha1))\n+\t\t\treturn error(\"invalid object %s\", sha1_to_hex(sha1));\n+\n+\t\tif (!ce->ce_mode)\n+\t\t\tcontinue; /* entry being removed */\n+\n+\t\tif (size < offset + entlen + 100) {\n+\t\t\tsize = alloc_nr(offset + entlen + 100);\n+\t\t\tbuffer = xrealloc(buffer, size);\n+\t\t}\n+\t\toffset += sprintf(buffer + offset,\n+\t\t\t\t  \"%o %.*s\", mode, entlen, path + baselen);\n+\t\tbuffer[offset++] = 0;\n+\t\tmemcpy(buffer + offset, sha1, 20);\n+\t\toffset += 20;\n+\n+#if DEBUG\n+\t\tfprintf(stderr, \"cache-tree %o %.*s\\n\",\n+\t\t\tmode, entlen, path + baselen);\n+#endif\n+\t}\n+\n+\twrite_sha1_file(buffer, offset, tree_type, it->sha1);\n+\tfree(buffer);\n+\tit->entry_count = i;\n+#if DEBUG\n+\tfprintf(stderr, \"cache-tree (%d ent, %d subtree) %s\\n\",\n+\t\tit->entry_count, it->subtree_nr,\n+\t\tsha1_to_hex(it->sha1));\n+#endif\n+\treturn i;\n+}\n+\n+int cache_tree_update(struct cache_tree *it,\n+\t\t      struct cache_entry **cache,\n+\t\t      int entries,\n+\t\t      int missing_ok)\n+{\n+\tint i;\n+\ti = verify_cache(cache, entries);\n+\tif (i)\n+\t\treturn i;\n+\ti = update_one(it, cache, entries, \"\", 0, missing_ok);\n+\tif (i < 0)\n+\t\treturn i;\n+\treturn 0;\n+}\n+\n+static void *write_one(struct cache_tree *it,\n+\t\t       char *path,\n+\t\t       int pathlen,\n+\t\t       char *buffer,\n+\t\t       unsigned long *size,\n+\t\t       unsigned long *offset)\n+{\n+\tint i;\n+\n+\t/* One \"cache-tree\" entry consists of the following:\n+\t * path (NUL terminated)\n+\t * entry_count, subtree_nr (\"%d %d\\n\")\n+\t * tree-sha1 (missing if invalid)\n+\t * subtree_nr \"cache-tree\" entries for subtrees.\n+\t */\n+\tif (*size < *offset + pathlen + 100) {\n+\t\t*size = alloc_nr(*offset + pathlen + 100);\n+\t\tbuffer = xrealloc(buffer, *size);\n+\t}\n+\t*offset += sprintf(buffer + *offset, \"%.*s%c%d %d\\n\",\n+\t\t\t   pathlen, path, 0,\n+\t\t\t   it->entry_count, it->subtree_nr);\n+\n+#if DEBUG\n+\tif (0 <= it->entry_count)\n+\t\tfprintf(stderr, \"cache-tree <%.*s> (%d ent, %d subtree) %s\\n\",\n+\t\t\tpathlen, path, it->entry_count, it->subtree_nr,\n+\t\t\tsha1_to_hex(it->sha1));\n+\telse\n+\t\tfprintf(stderr, \"cache-tree <%.*s> (%d subtree) invalid\\n\",\n+\t\t\tpathlen, path, it->subtree_nr);\n+#endif\n+\n+\tif (0 <= it->entry_count) {\n+\t\tmemcpy(buffer + *offset, it->sha1, 20);\n+\t\t*offset += 20;\n+\t}\n+\tfor (i = 0; i < it->subtree_nr; i++) {\n+\t\tstruct cache_tree_sub *down = it->down[i];\n+\t\tint len = pathlen + down->namelen;\n+\t\tmemcpy(path + pathlen, down->name, down->namelen);\n+\t\tpath[len] = '/';\n+\t\tbuffer = write_one(down->cache_tree, path, len+1,\n+\t\t\t\t   buffer, size, offset);\n+\t}\n+\treturn buffer;\n+}\n+\n+static void *cache_tree_write(const unsigned char *cache_sha1,\n+\t\t\t      struct cache_tree *root,\n+\t\t\t      unsigned long *offset_p)\n+{\n+\tchar path[PATH_MAX];\n+\tunsigned long size = 8192;\n+\tchar *buffer = xmalloc(size);\n+\n+\t/* the cache checksum of the corresponding index file. */\n+\tmemcpy(buffer, cache_sha1, 20);\n+\t*offset_p = 20;\n+\tpath[0] = 0;\n+\treturn write_one(root, path, 0, buffer, &size, offset_p);\n+}\n+\n+static struct cache_tree *read_one(const char **buffer, unsigned long *size_p)\n+{\n+\tconst char *buf = *buffer;\n+\tunsigned long size = *size_p;\n+\tstruct cache_tree *it;\n+\tint i, subtree_nr;\n+\n+\tit = NULL;\n+\t/* skip name, but make sure name exists */\n+\twhile (size && *buf) {\n+\t\tsize--;\n+\t\tbuf++;\n+\t}\n+\tif (!size)\n+\t\tgoto free_return;\n+\tbuf++; size--;\n+\tit = cache_tree();\n+\tif (sscanf(buf, \"%d %d\\n\", &it->entry_count, &subtree_nr) != 2)\n+\t\tgoto free_return;\n+\twhile (size && *buf && *buf != '\\n') {\n+\t\tsize--;\n+\t\tbuf++;\n+\t}\n+\tif (!size)\n+\t\tgoto free_return;\n+\tbuf++; size--;\n+\tif (0 <= it->entry_count) {\n+\t\tif (size < 20)\n+\t\t\tgoto free_return;\n+\t\tmemcpy(it->sha1, buf, 20);\n+\t\tbuf += 20;\n+\t\tsize -= 20;\n+\t}\n+\n+#if DEBUG\n+\tif (0 <= it->entry_count)\n+\t\tfprintf(stderr, \"cache-tree <%s> (%d ent, %d subtree) %s\\n\",\n+\t\t\t*buffer, it->entry_count, subtree_nr,\n+\t\t\tsha1_to_hex(it->sha1));\n+\telse\n+\t\tfprintf(stderr, \"cache-tree <%s> (%d subtrees) invalid\\n\",\n+\t\t\t*buffer, subtree_nr);\n+#endif\n+\n+\t/*\n+\t * Just a heuristic -- we do not add directories that often but\n+\t * we do not want to have to extend it immediately when we do,\n+\t * hence +2.\n+\t */\n+\tit->subtree_alloc = subtree_nr + 2;\n+\tit->down = xcalloc(it->subtree_alloc, sizeof(struct cache_tree_sub *));\n+\tfor (i = 0; i < subtree_nr; i++) {\n+\t\t/* read each subtree */\n+\t\tstruct cache_tree *sub;\n+\t\tconst char *name = buf;\n+\t\tint namelen;\n+\t\tsub = read_one(&buf, &size);\n+\t\tif (!sub)\n+\t\t\tgoto free_return;\n+\t\tnamelen = strlen(name);\n+\t\tit->down[i] = find_subtree(it, name, namelen, 1);\n+\t\tit->down[i]->cache_tree = sub;\n+\t}\n+\tif (subtree_nr != it->subtree_nr)\n+\t\tdie(\"cache-tree: internal error\");\n+\t*buffer = buf;\n+\t*size_p = size;\n+\treturn it;\n+\n+ free_return:\n+\tcache_tree_free(it);\n+\treturn NULL;\n+}\n+\n+static struct cache_tree *cache_tree_read(unsigned char *sha1,\n+\t\t\t\t\t  const char *buffer,\n+\t\t\t\t\t  unsigned long size)\n+{\n+\t/* check the cache-tree matches the index */\n+\tif (memcmp(buffer, sha1, 20))\n+\t\treturn NULL; /* checksum mismatch */\n+\tif (buffer[20])\n+\t\treturn NULL; /* not the whole tree */\n+\tbuffer += 20;\n+\tsize -= 20;\n+\treturn read_one(&buffer, &size);\n+}\n+\n+struct cache_tree *read_cache_tree(unsigned char *sha1)\n+{\n+\tint fd;\n+\tstruct stat st;\n+\tchar path[PATH_MAX];\n+\tunsigned long size = 0;\n+\tvoid *map;\n+\tstruct cache_tree *it;\n+\n+\tsprintf(path, \"%s.aux\", get_index_file());\n+\tfd = open(path, O_RDONLY);\n+\tif (fd < 0)\n+\t\treturn cache_tree();\n+\n+\tif (fstat(fd, &st))\n+\t\treturn cache_tree();\n+\tsize = st.st_size;\n+\tmap = mmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\tclose(fd);\n+\tif (map == MAP_FAILED)\n+\t\treturn cache_tree();\n+\tit = cache_tree_read(sha1, map, size);\n+\tmunmap(map, size);\n+\tif (!it)\n+\t\treturn cache_tree();\n+\treturn it;\n+}\n+\n+int write_cache_tree(const unsigned char *sha1, struct cache_tree *root)\n+{\n+\tchar path[PATH_MAX];\n+\tunsigned long size = 0;\n+\tvoid *buf, *buffer;\n+\tint fd, ret = -1;\n+\n+\tsprintf(path, \"%s.aux\", get_index_file());\n+\tif (!root) {\n+\t\tunlink(path);\n+\t\treturn -1;\n+\t}\n+\tfd = open(path, O_WRONLY|O_CREAT, 0666);\n+\tif (fd < 0)\n+\t\treturn -1;\n+\tbuffer = buf = cache_tree_write(sha1, root, &size);\n+\twhile (size) {\n+\t\tint written = xwrite(fd, buf, size);\n+\t\tif (written <= 0)\n+\t\t\tgoto fail;\n+\t\tbuf += written;\n+\t\tsize -= written;\n+\t}\n+\tret = 0;\n+\n+ fail:\n+\tclose(fd);\n+\tfree(buffer);\n+\tif (ret)\n+\t\tunlink(path);\n+\treturn ret;\n+}\ndiff --git a/cache-tree.h b/cache-tree.h\nnew file mode 100644\nindex 0000000..7b149af\n--- /dev/null\n+++ b/cache-tree.h\n@@ -0,0 +1,29 @@\n+#ifndef CACHE_TREE_H\n+#define CACHE_TREE_H\n+\n+struct cache_tree;\n+struct cache_tree_sub {\n+\tstruct cache_tree *cache_tree;\n+\tint namelen;\n+\tint used;\n+\tchar name[FLEX_ARRAY];\n+};\n+\n+struct cache_tree {\n+\tint entry_count; /* negative means \"invalid\" */\n+\tunsigned char sha1[20];\n+\tint subtree_nr;\n+\tint subtree_alloc;\n+\tstruct cache_tree_sub **down;\n+};\n+\n+struct cache_tree *cache_tree(void);\n+void cache_tree_free(struct cache_tree *);\n+void cache_tree_invalidate_path(struct cache_tree *, const char *);\n+\n+int write_cache_tree(const unsigned char *, struct cache_tree *);\n+struct cache_tree *read_cache_tree(unsigned char *);\n+int cache_tree_update(struct cache_tree *, struct cache_entry **, int, int);\n+\n+\n+#endif\n-- \n1.3.0.g623a\n"}]}