{"thread":{"id":"23346","subject":"[PATCH 6/7 (v5)] object name support","startedAt":"2010-04-05T19:58:44Z","lastAt":"2010-04-05T19:58:44Z","messageCount":1,"participants":["Nick Edelen"],"isPatch":true,"patchVersion":5,"patchTotal":7},"messages":[{"id":"138673","messageId":"4BBA40F4.8070807@gmail.com","threadId":"23346","inReplyTo":null,"subject":"[PATCH 6/7 (v5)] object name support","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2010-04-05T19:58:44Z","receivedAt":"2010-04-05T19:58:44Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"An update to caching mechanism, allowing path names to be cached for blob and\ntree objects.  A list of names appearing in each cache slice is appended to the\nend of the slice, which is referenced by variable-sized indexes per entry.\nThis allows pack-objects to more intelligently schedule unpacked/poorly packed\nobject, and enables proper duplication of rev-list's behaivor.\n\nSigned-off-by: Nick Edelen <sirnot@gmail.com>\n\n---\n builtin/rev-cache.c       |    3 +-\n rev-cache.c               |  349 ++++++++++++++++++++++++++++++++++++--------\n rev-cache.h               |   16 ++-\n revision.h                |    6 +-\n t/t6019-rev-cache-list.sh |    8 +-\n 5 files changed, 311 insertions(+), 71 deletions(-)\n\ndiff --git a/builtin/rev-cache.c b/builtin/rev-cache.c\nindex 7a79007..59fc833 100644\n--- a/builtin/rev-cache.c\n+++ b/builtin/rev-cache.c\n@@ -178,13 +178,14 @@ static int handle_walk(int argc, const char *argv[])\n \tfprintf(stderr, \"pending:\\n\");\n \tfor (i = 0; i < revs.pending.nr; i++) {\n \t\tstruct object *obj = revs.pending.objects[i].item;\n+\t\tconst char *name = revs.pending.objects[i].name;\n \n \t\t/* unfortunately, despite our careful generation, object duplication *is* a possibility...\n \t\t * (eg. same object introduced into two different branches) */\n \t\tif (obj->flags & SEEN)\n \t\t\tcontinue;\n \n-\t\tprintf(\"%s\\n\", sha1_to_hex(revs.pending.objects[i].item->sha1));\n+\t\tprintf(\"%s %s\\n\", sha1_to_hex(revs.pending.objects[i].item->sha1), name);\n \t\tobj->flags |= SEEN;\n \t}\n \ndiff --git a/rev-cache.c b/rev-cache.c\nindex af1a704..4f1ea34 100644\n--- a/rev-cache.c\n+++ b/rev-cache.c\n@@ -17,6 +17,14 @@ struct bad_slice {\n \tstruct bad_slice *next;\n };\n \n+struct name_list {\n+\tunsigned char sha1[20];\n+\tunsigned int len;\n+\tstruct name_list *next;\n+\n+\tchar buf[FLEX_ARRAY];\n+};\n+\n struct cache_slice_pointer {\n \tchar signature[8]; /* REVCOPTR */\n \tchar version;\n@@ -29,10 +37,13 @@ static uint32_t fanout[0xff + 2];\n static unsigned char *idx_map;\n static int idx_size;\n static struct rc_index_header idx_head;\n-static char no_idx, add_to_pending;\n-static struct bad_slice *bad_slices;\n+static char no_idx, add_to_pending, add_names;\n static unsigned char *idx_caches;\n \n+static struct bad_slice *bad_slices;\n+static struct name_list *name_lists, *cur_name_list;\n+\n+static struct strbuf *acc_name_buffer;\n static struct strbuf *acc_buffer;\n \n #define SLOP\t\t\t5\n@@ -60,7 +71,8 @@ static struct strbuf *acc_buffer;\n \t4 +\t\t\t\t\t\t\t\\\n \t2 +\t\t\t\t\t\t\t\\\n \t4 +\t\t\t\t\t\t\t\\\n-\t20\t\t\t\t\t\t\t\\\n+\t20 +\t\t\t\t\t\t\\\n+\t4\t\t\t\t\t\t\t\\\n )\n \n #define INDEX_HEADER_SIZE\t\t(\\\n@@ -147,8 +159,9 @@ struct rc_object_entry *from_disked_rc_object_entry(unsigned char *src, struct r\n \tdst->merge_nr = *(src + 21);\n \tdst->split_nr = *(src + 22);\n \n-\tdst->size_size = *(src + 23) >> 5;\n-\tdst->padding = *(src + 23) & 0x1f;\n+\tdst->size_size = *(src + 23) >> 5 & 0x03;\n+\tdst->name_size = *(src + 23) >> 2 & 0x03;\n+\tdst->padding = *(src + 23) & 0x02;\n \n \tdst->date = UNPACK_UINT32(src + 24);\n \tdst->path = UNPACK_UINT16(src + 28);\n@@ -182,6 +195,7 @@ unsigned char *to_disked_rc_object_entry(struct rc_object_entry *src, unsigned c\n \t*(dst + 22) = src->split_nr;\n \n \t*(dst + 23)  = (unsigned char)src->size_size << 5;\n+\t*(dst + 23) |= (unsigned char)src->name_size << 2;\n \t*(dst + 23) |= (unsigned char)src->padding;\n \n \tPACK_UINT32(dst + 24, src->date);\n@@ -252,6 +266,12 @@ static void cleanup_cache_slices(void)\n \t\tidx_map = 0;\n \t}\n \n+\twhile (name_lists) {\n+\t\tstruct name_list *nl = name_lists->next;\n+\t\tfree(name_lists);\n+\t\tname_lists = nl;\n+\t}\n+\n }\n \n static int init_index(void)\n@@ -384,7 +404,7 @@ static void handle_noncommit(struct rev_info *revs, struct commit *commit, unsig\n \tstruct blob *blob;\n \tstruct tree *tree;\n \tstruct object *obj;\n-\tunsigned long size;\n+\tunsigned long size, name_index;\n \n \tsize = decode_size(ptr + RC_ENTRY_SIZE_OFFSET(entry), entry->size_size);\n \tswitch (entry->type) {\n@@ -417,9 +437,23 @@ static void handle_noncommit(struct rev_info *revs, struct commit *commit, unsig\n \t\treturn;\n \t}\n \n+\tif (add_names && cur_name_list) {\n+\t\tname_index = decode_size(ptr + RC_ENTRY_NAME_OFFSET(entry), entry->name_size);\n+\n+\t\tif (name_index >= cur_name_list->len)\n+\t\t\tname_index = 0;\n+\t} else\n+\t\tname_index = 0;\n+\n \tobj->flags |= FACE_VALUE;\n-\tif (add_to_pending)\n-\t\tadd_pending_object(revs, obj, \"\");\n+\tif (add_to_pending) {\n+\t\tchar *name = \"\";\n+\n+\t\tif (name_index)\n+\t\t\tname = cur_name_list->buf + name_index;\n+\n+\t\tadd_pending_object(revs, obj, name);\n+\t}\n }\n \n struct entrance_point {\n@@ -803,19 +837,50 @@ end:\n \treturn retval;\n }\n \n-static int get_cache_slice_header(unsigned char *cache_sha1, unsigned char *map, int len, struct rc_slice_header *head)\n+static struct name_list *get_cache_slice_name_list(struct rc_slice_header *head, int fd)\n+{\n+\tstruct name_list *nl = name_lists;\n+\n+\twhile (nl) {\n+\t\tif (!hashcmp(nl->sha1, head->sha1))\n+\t\t\tbreak;\n+\t\tnl = nl->next;\n+\t}\n+\n+\tif (nl)\n+\t\treturn nl;\n+\n+\tnl = xcalloc(1, sizeof(struct name_list) + head->name_size);\n+\tnl->len = head->name_size;\n+\thashcpy(nl->sha1, head->sha1);\n+\n+\tlseek(fd, head->size, SEEK_SET);\n+\tread_in_full(fd, nl->buf, head->name_size);\n+\n+\tnl->next = name_lists;\n+\tname_lists = nl;\n+\n+\treturn nl;\n+}\n+\n+static int get_cache_slice_header(int fd, unsigned char *cache_sha1, int len, struct rc_slice_header *head)\n {\n \tint t;\n+\tunsigned char whead[SLICE_HEADER_SIZE];\n \n-\tmemcpy(head->signature, map, 8);\n-\thead->version = *(map + 8);\n-\thead->ofs_objects = UNPACK_UINT32(map + 9);\n+\tif (xread(fd, whead, SLICE_HEADER_SIZE) != SLICE_HEADER_SIZE)\n+\t\treturn -1;\n \n-\thead->object_nr = UNPACK_UINT32(map + 13);\n-\thead->path_nr = UNPACK_UINT16(map + 17);\n-\thead->size = UNPACK_UINT32(map + 19);\n+\tmemcpy(head->signature, whead, 8);\n+\thead->version = *(whead + 8);\n+\thead->ofs_objects = UNPACK_UINT32(whead + 9);\n+\n+\thead->object_nr = UNPACK_UINT32(whead + 13);\n+\thead->path_nr = UNPACK_UINT16(whead + 17);\n+\thead->size = UNPACK_UINT32(whead + 19);\n \n-\thashcpy(head->sha1, map + 23);\n+\thashcpy(head->sha1, whead + 23);\n+\thead->name_size = UNPACK_UINT32(whead + 43);\n \n \tif (memcmp(head->signature, \"REVCACHE\", 8))\n \t\treturn -1;\n@@ -824,10 +889,10 @@ static int get_cache_slice_header(unsigned char *cache_sha1, unsigned char *map,\n \tif (hashcmp(head->sha1, cache_sha1))\n \t\treturn -3;\n \tt = SLICE_HEADER_SIZE;\n-\tif (t != head->ofs_objects || t >= len)\n+\tif (t != head->ofs_objects)\n \t\treturn -4;\n-\n-\thead->size = len;\n+\tif (head->size + head->name_size != len)\n+\t\treturn -5;\n \n \treturn 0;\n }\n@@ -878,7 +943,7 @@ int traverse_cache_slice(struct rev_info *revs,\n \tunsigned long *date_so_far, int *slop_so_far,\n \tstruct commit_list ***queue, struct commit_list **work)\n {\n-\tint fd = -1, retval = -3;\n+\tint fd = -1, t, retval;\n \tstruct stat fi;\n \tstruct rc_slice_header head;\n \tstruct rev_cache_info *rci;\n@@ -894,26 +959,31 @@ int traverse_cache_slice(struct rev_info *revs,\n \t/* load options */\n \trci = &revs->rev_cache_info;\n \tadd_to_pending = rci->add_to_pending;\n+\tadd_names = rci->add_names;\n \n \tmemset(&head, 0, sizeof(struct rc_slice_header));\n+#\tdefine ERROR(x)\t\tdo { retval = (x); goto end; } while (0);\n \n \tfd = open_cache_slice(cache_sha1, O_RDONLY);\n \tif (fd == -1)\n-\t\tgoto end;\n+\t\tERROR(-1);\n \tif (fstat(fd, &fi) || fi.st_size < SLICE_HEADER_SIZE)\n-\t\tgoto end;\n+\t\tERROR(-2);\n+\n+\tif ((t = get_cache_slice_header(fd, cache_sha1, fi.st_size, &head)) < 0)\n+\t\tERROR(-t);\n+\tif (add_names)\n+\t\tcur_name_list = get_cache_slice_name_list(&head, fd);\n \n-\tmap = xmmap(0, fi.st_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\tmap = xmmap(0, head.size, PROT_READ, MAP_PRIVATE, fd, 0);\n \tif (map == MAP_FAILED)\n-\t\tgoto end;\n-\tif (get_cache_slice_header(cache_sha1, map, fi.st_size, &head))\n-\t\tgoto end;\n+\t\tERROR(-3);\n \n \tretval = traverse_cache_slice_1(&head, map, revs, commit, date_so_far, slop_so_far, queue, work);\n \n end:\n \tif (map != MAP_FAILED)\n-\t\tmunmap(map, fi.st_size);\n+\t\tmunmap(map, head.size);\n \tif (fd != -1)\n \t\tclose(fd);\n \n@@ -921,6 +991,7 @@ end:\n \tif (retval)\n \t\tmark_bad_slice(cache_sha1);\n \n+#\tundef ERROR\n \treturn retval;\n }\n \n@@ -1205,23 +1276,110 @@ static unsigned long decode_size(unsigned char *str, int len)\n \treturn size;\n }\n \n+\n+#define NL_HASH_TABLE_SIZE\t\t(0xffff + 1)\n+#define NL_HASH_NUMBER\t\t\t(NL_HASH_TABLE_SIZE >> 3)\n+\n+struct name_list_hash {\n+\tint ind;\n+\tstruct name_list_hash *next;\n+};\n+\n+static struct name_list_hash **nl_hash_table;\n+static unsigned char *nl_hashes;\n+\n+/* FNV-1a hash */\n+static unsigned int hash_name(const char *name)\n+{\n+\tunsigned int hash = 2166136261ul;\n+\tconst char *p = name;\n+\n+\twhile (*p) {\n+\t\thash ^= *p++;\n+\t\thash *= 16777619ul;\n+\t}\n+\n+\treturn hash & 0xffff;\n+}\n+\n+static int name_in_list(const char *name)\n+{\n+\tunsigned int h = hash_name(name);\n+\tstruct name_list_hash *entry = nl_hash_table[h];\n+\n+\twhile (entry && strcmp(acc_name_buffer->buf + entry->ind, name))\n+\t\tentry = entry->next;\n+\n+\tif (entry)\n+\t\treturn entry->ind;\n+\n+\t/* add name to buffer and create hash reference */\n+\tentry = xcalloc(1, sizeof(struct name_list_hash));\n+\tentry->ind = acc_name_buffer->len;\n+\tstrbuf_add(acc_name_buffer, name, strlen(name) + 1);\n+\n+\tentry->next = nl_hash_table[h];\n+\tnl_hash_table[h] = entry;\n+\n+\tnl_hashes[h / 8] |= h % 8;\n+\n+\treturn entry->ind;\n+}\n+\n+static void init_name_list_hash(void)\n+{\n+\tnl_hash_table = xcalloc(NL_HASH_TABLE_SIZE, sizeof(struct name_list_hash));\n+\tnl_hashes = xcalloc(NL_HASH_NUMBER, 1);\n+}\n+\n+static void cleanup_name_list_hash(void)\n+{\n+\tint i;\n+\n+\tfor (i = 0; i < NL_HASH_NUMBER; i++) {\n+\t\tint j, ind = nl_hashes[i];\n+\n+\t\tif (!ind)\n+\t\t\tcontinue;\n+\n+\t\tfor (j = 0; j < 8; j++) {\n+\t\t\tstruct name_list_hash **entryp;\n+\n+\t\t\tif (!(ind & 1 << j))\n+\t\t\t\tcontinue;\n+\n+\t\t\tentryp = &nl_hash_table[i * 8 + j];\n+\t\t\twhile (*entryp) {\n+\t\t\t\tstruct name_list_hash *t = (*entryp)->next;\n+\n+\t\t\t\tfree(*entryp);\n+\t\t\t\t*entryp = t;\n+\t\t\t}\n+\t\t}\n+\t} /* code overhang! */\n+\n+\tfree(nl_hashes);\n+\tfree(nl_hash_table);\n+}\n+\n static void add_object_entry(const unsigned char *sha1, struct rc_object_entry *entryp,\n-\tstruct strbuf *merge_str, struct strbuf *split_str)\n+\tstruct strbuf *merge_str, struct strbuf *split_str, char *name, unsigned long size)\n {\n \tstruct rc_object_entry entry;\n-\tunsigned char size_str[7];\n-\tunsigned long size;\n+\tunsigned char size_str[7], name_str[7];\n \tenum object_type type;\n \tvoid *data;\n \n \tif (entryp)\n \t\tsha1 = entryp->sha1;\n \n-\t/* retrieve size data */\n-\tdata = read_sha1_file(sha1, &type, &size);\n+\tif (!size) {\n+\t\t/* retrieve size data */\n+\t\tdata = read_sha1_file(sha1, &type, &size);\n \n-\tif (data)\n-\t\tfree(data);\n+\t\tif (data)\n+\t\t\tfree(data);\n+\t}\n \n \t/* initialize! */\n \tif (!entryp) {\n@@ -1239,6 +1397,9 @@ static void add_object_entry(const unsigned char *sha1, struct rc_object_entry *\n \n \tentryp->size_size = encode_size(size, size_str);\n \n+\tif (name)\n+\t\tentryp->name_size = encode_size(name_in_list(name), name_str);\n+\n \t/* write the muvabitch */\n \tstrbuf_add(acc_buffer, to_disked_rc_object_entry(entryp, 0), OBJECT_ENTRY_SIZE);\n \n@@ -1248,25 +1409,36 @@ static void add_object_entry(const unsigned char *sha1, struct rc_object_entry *\n \t\tstrbuf_add(acc_buffer, split_str->buf, split_str->len);\n \n \tstrbuf_add(acc_buffer, size_str, entryp->size_size);\n+\n+\tif (name)\n+\t\tstrbuf_add(acc_buffer, name_str, entryp->name_size);\n }\n \n /* returns non-zero to continue parsing, 0 to skip */\n typedef int (*dump_tree_fn)(const unsigned char *, const char *, unsigned int); /* sha1, path, mode */\n \n /* we need to walk the trees by hash, so unfortunately we can't use traverse_trees in tree-walk.c */\n-static int dump_tree(struct tree *tree, dump_tree_fn fn)\n+static int dump_tree(struct tree *tree, dump_tree_fn fn, char *base)\n {\n \tstruct tree_desc desc;\n \tstruct name_entry entry;\n \tstruct tree *subtree;\n-\tint r;\n+\tchar concatpath[PATH_MAX];\n+\tint r, baselen;\n \n \tif (parse_tree(tree))\n \t\treturn -1;\n \n+\tbaselen = strlen(base);\n+\tstrcpy(concatpath, base);\n+\n \tinit_tree_desc(&desc, tree->buffer, tree->size);\n \twhile (tree_entry(&desc, &entry)) {\n-\t\tswitch (fn(entry.sha1, entry.path, entry.mode)) {\n+\t\tif (baselen + strlen(entry.path) + 1 >= PATH_MAX)\n+\t\t\tdie(\"we have a problem: %s%s is too big for me to handle\", base, entry.path);\n+\t\tstrcpy(concatpath + baselen, entry.path);\n+\n+\t\tswitch (fn(entry.sha1, concatpath, entry.mode)) {\n \t\tcase 0:\n \t\t\tgoto continue_loop;\n \t\tdefault:\n@@ -1278,7 +1450,8 @@ static int dump_tree(struct tree *tree, dump_tree_fn fn)\n \t\t\tif (!subtree)\n \t\t\t\treturn -2;\n \n-\t\t\tif ((r = dump_tree(subtree, fn)) < 0)\n+\t\t\tstrcat(concatpath, \"/\");\n+\t\t\tif ((r = dump_tree(subtree, fn, concatpath)) < 0)\n \t\t\t\treturn r;\n \t\t}\n \n@@ -1292,6 +1465,9 @@ continue_loop:\n static int dump_tree_callback(const unsigned char *sha1, const char *path, unsigned int mode)\n {\n \tstrbuf_add(acc_buffer, sha1, 20);\n+\tstrbuf_add(acc_buffer, (char *)&acc_name_buffer->len, sizeof(size_t));\n+\n+\tstrbuf_add(acc_name_buffer, path, strlen(path) + 1);\n \n \treturn 1;\n }\n@@ -1302,6 +1478,9 @@ static void tree_addremove(struct diff_options *options,\n \tconst char *concatpath, unsigned dirty_sub)\n {\n \tstrbuf_add(acc_buffer, sha1, 20);\n+\tstrbuf_add(acc_buffer, (char *)&acc_name_buffer->len, sizeof(size_t));\n+\n+\tstrbuf_add(acc_name_buffer, concatpath, strlen(concatpath) + 1);\n }\n \n static void tree_change(struct diff_options *options,\n@@ -1312,12 +1491,15 @@ static void tree_change(struct diff_options *options,\n \tunsigned old_dirty_sub, unsigned new_dirty_sub)\n {\n \tstrbuf_add(acc_buffer, new_sha1, 20);\n+\tstrbuf_add(acc_buffer, (char *)&acc_name_buffer->len, sizeof(size_t));\n+\n+\tstrbuf_add(acc_name_buffer, concatpath, strlen(concatpath) + 1);\n }\n \n static int add_unique_objects(struct commit *commit)\n {\n \tstruct commit_list *list;\n-\tstruct strbuf os, ost, *orig_buf;\n+\tstruct strbuf os, ost, names, *orig_name_buf, *orig_buf;\n \tstruct diff_options opts;\n \tint i, j, next;\n \tchar is_first = 1;\n@@ -1325,13 +1507,17 @@ static int add_unique_objects(struct commit *commit)\n \t/* ...no, calculate unique objects */\n \tstrbuf_init(&os, 0);\n \tstrbuf_init(&ost, 0);\n+\tstrbuf_init(&names, 0);\n \torig_buf = acc_buffer;\n+\torig_name_buf = acc_name_buffer;\n+\tacc_name_buffer = &names;\n \n \tdiff_setup(&opts);\n \tDIFF_OPT_SET(&opts, RECURSIVE);\n \tDIFF_OPT_SET(&opts, TREE_IN_RECURSIVE);\n \topts.change = tree_change;\n \topts.add_remove = tree_addremove;\n+#\tdefine ENTRY_SIZE (20 + sizeof(size_t))\n \n \t/* this is only called for non-ends (ie. all parents interesting) */\n \tfor (list = commit->parents; list; list = list->next) {\n@@ -1342,20 +1528,20 @@ static int add_unique_objects(struct commit *commit)\n \n \t\tstrbuf_setlen(acc_buffer, 0);\n \t\tdiff_tree_sha1(list->item->tree->object.sha1, commit->tree->object.sha1, \"\", &opts);\n-\t\tqsort(acc_buffer->buf, acc_buffer->len / 20, 20, (int (*)(const void *, const void *))hashcmp);\n+\t\tqsort(acc_buffer->buf, acc_buffer->len / ENTRY_SIZE, ENTRY_SIZE, (int (*)(const void *, const void *))hashcmp);\n \n \t\t/* take intersection */\n \t\tif (!is_first) {\n-\t\t\tfor (next = i = j = 0; i < os.len; i += 20) {\n+\t\t\tfor (next = i = j = 0; i < os.len; i += ENTRY_SIZE) {\n \t\t\t\twhile (j < ost.len && hashcmp((unsigned char *)(ost.buf + j), (unsigned char *)(os.buf + i)) < 0)\n-\t\t\t\t\tj += 20;\n+\t\t\t\t\tj += ENTRY_SIZE;\n \n \t\t\t\tif (j >= ost.len || hashcmp((unsigned char *)(ost.buf + j), (unsigned char *)(os.buf + i)))\n \t\t\t\t\tcontinue;\n \n \t\t\t\tif (next != i)\n-\t\t\t\t\tmemcpy(os.buf + next, os.buf + i, 20);\n-\t\t\t\tnext += 20;\n+\t\t\t\t\tmemcpy(os.buf + next, os.buf + i, ENTRY_SIZE);\n+\t\t\t\tnext += ENTRY_SIZE;\n \t\t\t}\n \n \t\t\tif (next != i)\n@@ -1367,29 +1553,37 @@ static int add_unique_objects(struct commit *commit)\n \t/* no parents (!) */\n \tif (is_first) {\n \t\tacc_buffer = &os;\n-\t\tdump_tree(commit->tree, dump_tree_callback);\n+\t\tdump_tree(commit->tree, dump_tree_callback, \"\");\n \t}\n \n \t/* the ordering of non-commit objects dosn't really matter, so we're not gonna bother */\n \tacc_buffer = orig_buf;\n-\tfor (i = 0; i < os.len; i += 20)\n-\t\tadd_object_entry((unsigned char *)(os.buf + i), 0, 0, 0);\n+\tacc_name_buffer = orig_name_buf;\n+\tfor (i = 0; i < os.len; i += ENTRY_SIZE)\n+\t\tadd_object_entry((unsigned char *)(os.buf + i), 0, 0, 0, names.buf + *(size_t *)(os.buf + i + 20), 0);\n \n \t/* last but not least, the main tree */\n-\tadd_object_entry(commit->tree->object.sha1, 0, 0, 0);\n+\tadd_object_entry(commit->tree->object.sha1, 0, 0, 0, 0, 0);\n \n-\treturn i / 20 + 1;\n+\tstrbuf_release(&ost);\n+\tstrbuf_release(&os);\n+\tstrbuf_release(&names);\n+\n+\treturn i / ENTRY_SIZE + 1;\n+#\tundef ENTRY_SIZE\n }\n \n static int add_objects_verbatim_1(struct rev_cache_slice_map *mapping, int *index)\n {\n-\tunsigned char *map = mapping->map;\n \tint i = *index, object_nr = 0;\n+\tunsigned char *map = mapping->map;\n \tstruct rc_object_entry *entry = RC_OBTAIN_OBJECT_ENTRY(map + i);\n+\tunsigned long size;\n \n \ti += RC_ACTUAL_OBJECT_ENTRY_SIZE(entry);\n \twhile (i < mapping->size) {\n-\t\tint pos = i;\n+\t\tchar *name;\n+\t\tint name_index, pos = i;\n \n \t\tentry = RC_OBTAIN_OBJECT_ENTRY(map + i);\n \t\ti += RC_ACTUAL_OBJECT_ENTRY_SIZE(entry);\n@@ -1399,7 +1593,15 @@ static int add_objects_verbatim_1(struct rev_cache_slice_map *mapping, int *inde\n \t\t\treturn object_nr;\n \t\t}\n \n-\t\tstrbuf_add(acc_buffer, map + pos, i - pos);\n+\t\tname_index = decode_size(map + pos + RC_ENTRY_NAME_OFFSET(entry), entry->name_size);\n+\t\tif (name_index && name_index < mapping->name_size)\n+\t\t\tname = mapping->names + name_index;\n+\t\telse\n+\t\t\tname = 0;\n+\n+\t\tsize = decode_size(map + pos + RC_ENTRY_SIZE_OFFSET(entry), entry->size_size);\n+\n+\t\tadd_object_entry(0, entry, 0, 0, name, size);\n \t\tobject_nr++;\n \t}\n \n@@ -1484,6 +1686,7 @@ void init_rev_cache_info(struct rev_cache_info *rci)\n \trci->overwrite_all = 0;\n \n \trci->add_to_pending = 1;\n+\trci->add_names = 1;\n \n \trci->ignore_size = 0;\n }\n@@ -1508,9 +1711,9 @@ int make_cache_slice(struct rev_cache_info *rci,\n \tstruct rc_slice_header head;\n \tstruct commit *commit;\n \tunsigned char sha1[20], whead[SLICE_HEADER_SIZE];\n-\tstruct strbuf merge_paths, split_paths;\n+\tstruct strbuf merge_paths, split_paths, namelist;\n \tint object_nr, total_sz, fd;\n-\tchar file[PATH_MAX], *newfile;\n+\tchar file[PATH_MAX], null, *newfile;\n \tstruct rev_cache_info *trci;\n \tgit_SHA_CTX ctx;\n \n@@ -1525,7 +1728,13 @@ int make_cache_slice(struct rev_cache_info *rci,\n \tstrbuf_init(&endlist, 0);\n \tstrbuf_init(&merge_paths, 0);\n \tstrbuf_init(&split_paths, 0);\n+\tstrbuf_init(&namelist, 0);\n \tacc_buffer = &buffer;\n+\tacc_name_buffer = &namelist;\n+\n+\tnull = 0;\n+\tstrbuf_add(&namelist, &null, 1);\n+\tinit_name_list_hash();\n \n \tif (!revs) {\n \t\trevs = &therevs;\n@@ -1557,6 +1766,7 @@ int make_cache_slice(struct rev_cache_info *rci,\n \ttrci = &revs->rev_cache_info;\n \tinit_rev_cache_info(trci);\n \ttrci->add_to_pending = 0;\n+\ttrci->add_names = 0;\n \n \tsetup_revisions(0, 0, revs, 0);\n \tif (prepare_revision_walk(revs))\n@@ -1597,7 +1807,7 @@ int make_cache_slice(struct rev_cache_info *rci,\n \n \t\tcommit->indegree = 0;\n \n-\t\tadd_object_entry(0, &object, &merge_paths, &split_paths);\n+\t\tadd_object_entry(0, &object, &merge_paths, &split_paths, 0, 0);\n \t\tobject_nr++;\n \n \t\tif (rci->objects && !object.is_end) {\n@@ -1623,10 +1833,16 @@ int make_cache_slice(struct rev_cache_info *rci,\n \t\ttotal_sz += buffer.len;\n \t}\n \n+\t/* write path name lookup list */\n+\thead.name_size = namelist.len;\n+\twrite_in_full(fd, namelist.buf, namelist.len);\n+\n \t/* go ahead a free some stuff... */\n \tstrbuf_release(&buffer);\n \tstrbuf_release(&merge_paths);\n \tstrbuf_release(&split_paths);\n+\tstrbuf_release(&namelist);\n+\tcleanup_name_list_hash();\n \tif (path_sz)\n \t\tfree(paths);\n \twhile (path_track_alloc)\n@@ -1658,6 +1874,8 @@ int make_cache_slice(struct rev_cache_info *rci,\n \tPACK_UINT32(whead + 19, head.size);\n \thashcpy(whead + 23, head.sha1);\n \n+\tPACK_UINT32(whead + 43, head.name_size);\n+\n \t/* some info! */\n \tfprintf(stderr, \"objects: %d\\n\", object_nr);\n \tfprintf(stderr, \"paths: %d\\n\", path_nr);\n@@ -2095,6 +2313,7 @@ int fuse_cache_slices(struct rev_cache_info *rci, struct rev_info *revs)\n \tfor (i = idx_head.cache_nr - 1; i >= 0; i--) {\n \t\tstruct rev_cache_slice_map *map = rci->maps + i;\n \t\tstruct stat fi;\n+\t\tstruct rc_slice_header head;\n \t\tint fd;\n \n \t\tif (!map->size)\n@@ -2107,13 +2326,20 @@ int fuse_cache_slices(struct rev_cache_info *rci, struct rev_info *revs)\n \t\t\tcontinue;\n \t\tif (fi.st_size < sizeof(struct rc_slice_header))\n \t\t\tcontinue;\n+\t\tif (get_cache_slice_header(fd, idx_caches + i * 20, fi.st_size, &head))\n+\t\t\tcontinue;\n \n-\t\tmap->map = xmmap(0, fi.st_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\t\tmap->map = xmmap(0, head.size, PROT_READ, MAP_PRIVATE, fd, 0);\n \t\tif (map->map == MAP_FAILED)\n \t\t\tcontinue;\n \n+\t\tlseek(fd, head.size, SEEK_SET);\n+\t\tmap->names = xcalloc(head.name_size, 1);\n+\t\tread_in_full(fd, map->names, head.name_size);\n+\n \t\tclose(fd);\n-\t\tmap->size = fi.st_size;\n+\t\tmap->size = head.size;\n+\t\tmap->name_size = head.name_size;\n \t}\n \n \trci->make_index = 0;\n@@ -2130,6 +2356,7 @@ int fuse_cache_slices(struct rev_cache_info *rci, struct rev_info *revs)\n \t\tif (!map->size)\n \t\t\tcontinue;\n \n+\t\tfree(map->names);\n \t\tmunmap(map->map, map->size);\n \t}\n \tfree(rci->maps);\n@@ -2151,7 +2378,6 @@ static int verify_cache_slice(const char *slice_path, unsigned char *sha1)\n {\n \tstruct rc_slice_header head;\n \tint fd, len, retval = -1;\n-\tunsigned char *map = MAP_FAILED;\n \tstruct stat fi;\n \n \tlen = strlen(slice_path);\n@@ -2166,17 +2392,12 @@ static int verify_cache_slice(const char *slice_path, unsigned char *sha1)\n \tif (fstat(fd, &fi) || fi.st_size < sizeof(head))\n \t\tgoto end;\n \n-\tmap = xmmap(0, sizeof(head), PROT_READ, MAP_PRIVATE, fd, 0);\n-\tif (map == MAP_FAILED)\n-\t\tgoto end;\n-\tif (get_cache_slice_header(sha1, map, fi.st_size, &head))\n+\tif (get_cache_slice_header(fd, sha1, fi.st_size, &head))\n \t\tgoto end;\n \n \tretval = 0;\n \n end:\n-\tif (map != MAP_FAILED)\n-\t\tmunmap(map, sizeof(head));\n \tif (fd > 0)\n \t\tclose(fd);\n \ndiff --git a/rev-cache.h b/rev-cache.h\nindex 6e3a895..6ee2ba1 100644\n--- a/rev-cache.h\n+++ b/rev-cache.h\n@@ -10,8 +10,14 @@\n #define RC_OBTAIN_OBJECT_ENTRY(p)\t\t\tfrom_disked_rc_object_entry((unsigned char *)(p), 0)\n #define RC_OBTAIN_INDEX_ENTRY(p)\t\t\tfrom_disked_rc_index_entry((unsigned char *)(p), 0)\n \n-#define RC_ACTUAL_OBJECT_ENTRY_SIZE(e)\t\t(OBJECT_ENTRY_SIZE + RC_PATH_SIZE((e)->merge_nr + (e)->split_nr) + (e)->size_size)\n-#define RC_ENTRY_SIZE_OFFSET(e)\t\t\t\t(RC_ACTUAL_OBJECT_ENTRY_SIZE(e) - (e)->size_size)\n+#define RC_ACTUAL_OBJECT_ENTRY_SIZE(e)\t(\\\n+\tOBJECT_ENTRY_SIZE + \\\n+\tRC_PATH_SIZE((e)->merge_nr + (e)->split_nr) + \\\n+\t(e)->size_size + \\\n+\t(e)->name_size\\\n+)\n+#define RC_ENTRY_SIZE_OFFSET(e)\t\t\t(RC_ACTUAL_OBJECT_ENTRY_SIZE(e) - (e)->name_size - (e)->size_size)\n+#define RC_ENTRY_NAME_OFFSET(e)\t\t\t(RC_ACTUAL_OBJECT_ENTRY_SIZE(e) - (e)->name_size)\n \n /* single index maps objects to cache files */\n struct rc_index_header {\n@@ -50,6 +56,8 @@ struct rc_slice_header {\n \tuint32_t size;\n \n \tunsigned char sha1[20];\n+\n+\tuint32_t name_size;\n };\n \n struct rc_object_entry_ondisk {\n@@ -75,7 +83,8 @@ struct rc_object_entry {\n \tunsigned char merge_nr; /* : 7 */\n \tunsigned char split_nr; /* : 7 */\n \tunsigned size_size:3;\n-\tunsigned padding:5;\n+\tunsigned name_size:3;\n+\tunsigned padding:2;\n \n \tuint32_t date;\n \tuint16_t path;\n@@ -83,6 +92,7 @@ struct rc_object_entry {\n \t/* merge paths */\n \t/* split paths */\n \t/* size */\n+\t/* name id */\n };\n \n struct rc_index_entry *from_disked_rc_index_entry(unsigned char *src, struct rc_index_entry *dst);\ndiff --git a/revision.h b/revision.h\nindex 825a9dd..7a0bbf3 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -28,6 +28,9 @@ struct rev_cache_slice_map {\n \tunsigned char *map;\n \tint size;\n \tint last_index;\n+\n+\tchar *names;\n+\tint name_size;\n };\n \n struct rev_cache_info {\n@@ -41,7 +44,8 @@ struct rev_cache_info {\n \tunsigned overwrite_all : 1;\n \n \t/* traversal flags */\n-\tunsigned add_to_pending : 1;\n+\tunsigned add_to_pending : 1,\n+\t\tadd_names : 1;\n \n \t/* fuse options */\n \tunsigned int ignore_size;\ndiff --git a/t/t6019-rev-cache-list.sh b/t/t6019-rev-cache-list.sh\nindex 77cd191..b7eff3f 100644\n--- a/t/t6019-rev-cache-list.sh\n+++ b/t/t6019-rev-cache-list.sh\n@@ -4,8 +4,10 @@ test_description='git rev-cache tests'\n . ./test-lib.sh\n \n test_cmp_sorted() {\n-\tgrep -io \"[a-f0-9]*\" $1 | sort >.tmpfile1 &&\n-\tgrep -io \"[a-f0-9]*\" $2 | sort >.tmpfile2 &&\n+# note that we're tip-toeing around the corner case of two objects/names\n+# for the same SHA-1 => discrepencies between cached and non-cached walks\n+\tsort $1 >.tmpfile1 &&\n+\tsort $2 >.tmpfile2 &&\n \ttest_cmp .tmpfile1 .tmpfile2\n }\n \n@@ -15,6 +17,8 @@ test_cmp_sorted() {\n # reuse\n test_expect_success 'init repo' '\n \techo bla >file &&\n+\tmkdir amaindir &&\n+\techo watskeburt >amaindir/file &&\n \tgit add . &&\n \tgit commit -m \"bla\" &&\n \n-- \ntg: (dc38674..) t/rc/names (depends on: t/rc/int)\n"}]}