{"thread":{"id":"1782","subject":"[PATCH 21/22] teach the merge algorithm about cache iterators","startedAt":"2005-09-12T14:55:43Z","lastAt":"2005-09-15T14:01:16Z","messageCount":49,"participants":["Chuck Lever","A Large Angry SCM","Junio C Hamano","Daniel Barkalow","Linus Torvalds","Tim Ottinger","Catalin Marinas"],"isPatch":true,"patchVersion":1,"patchTotal":22},"messages":[{"id":"8388","messageId":"20050912145543.28120.7086.stgit@dexter.citi.umich.edu","threadId":"1782","inReplyTo":null,"subject":"[PATCH 00/22] cache cursors: an introduction","fromName":"Chuck Lever","fromEmail":"cel@citi.umich.edu","sentAt":"2005-09-12T14:55:43Z","receivedAt":"2005-09-12T14:55:43Z","isPatch":true,"sender":{"key":"cel@citi.umich.edu","avatar":null},"body":"\n[ This series is posted for review and comments. ]\n\nThe following patch series introduces an abstraction called a \"cache\ncursor\" that will eventually allow us to replace the current\nactive_cache array with something else.\n\nA cache cursor represents a position inside the cache. This position\nhas a cache_entry associated with it, of course, but since the cache\nis ordered, a cache cursor also has the concept of next, previous,\nand end-of-cache.\n\nWith a cache cursor we can build a simple iterator mechanism that\ncalls a particular function for every entry in the cache, in order.\nThis allows us to hide further the specifics of the active cache\nimplementation -- the function gets to see the cache cursor and\nan element, but does not have direct access to the cache and cannot\nassume it has a particular structure.\n\nCurrently the cache cursor type is just a structure with an integer\nin it, so it largely mimics the existing implementation.\n\nThis patch series is against the \"proposed updates\" branch, as of\na couple of days ago. It has been tested via \"make test\" and I'm\ncurrently using it for my own work without issue.\n\nSigned-off-by: Chuck Lever \n--\n"},{"id":"8389","messageId":"20050912145545.28120.61764.stgit@dexter.citi.umich.edu","threadId":"1782","inReplyTo":"20050912145543.28120.7086.stgit@dexter.citi.umich.edu","subject":"[PATCH 01/22] introduce facility to walk through the active cache","fromName":"Chuck Lever","fromEmail":"cel@netapp.com","sentAt":"2005-09-12T14:55:45Z","receivedAt":"2005-09-12T14:55:45Z","isPatch":true,"sender":{"key":"cel@netapp.com","avatar":null},"body":"Introduce a mechanism that allows functions to walk through entries\nin the active cache in order and execute an function on each entry.\n\nWe also introduce the concept of \"cache cursor\". A cursor is simply\na type-independent way of referring to a unique position in the cache.\nThe cache is strongly ordered, so cursors also provide a type-\nindependent way of exposing the ordering of the cache positions:\nie next, previous, and eof?\n\nThis facility makes no changes to struct cache_entry, which also\nhappens to be the on-disk format of a cache entry. By mmapping the\nfile that contains the cache entries, no data copying is required\nto read in the cache.\n\nSigned-off-by: Chuck Lever \n---\n\n cache.h | 75 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n 1 files changed, 75 insertions(+), 0 deletions(-)\n\ndiff --git a/cache.h b/cache.h\n--- a/cache.h\n+++ b/cache.h\n@@ -130,6 +130,12 @@ static inline unsigned int create_ce_mod\n extern struct cache_entry **active_cache;\n extern unsigned int active_nr, active_alloc, active_cache_changed;\n \n+struct cache_cursor {\n+\tint pos;\n+};\n+\n+typedef int (*cache_iterator_fn_t) (struct cache_cursor *cc, struct cache_entry *ce);\n+\n #define GIT_DIR_ENVIRONMENT \"GIT_DIR\"\n #define DEFAULT_GIT_DIR_ENVIRONMENT \".git\"\n #define DB_ENVIRONMENT \"GIT_OBJECT_DIRECTORY\"\n@@ -273,6 +279,75 @@ static inline void *xcalloc(size_t nmemb\n \treturn ret;\n }\n \n+static inline void init_cc(struct cache_cursor *cc)\n+{\n+\tcc->pos = 0;\n+}\n+\n+static inline void next_cc(struct cache_cursor *cc)\n+{\n+\tcc->pos++;\n+}\n+\n+static inline void prev_cc(struct cache_cursor *cc)\n+{\n+\tcc->pos--;\n+}\n+\n+static inline struct cache_entry *cc_to_ce(struct cache_cursor *cc)\n+{\n+\treturn active_cache[cc->pos];\n+}\n+\n+static inline void set_ce_at_cursor(struct cache_cursor *cc, struct cache_entry *new)\n+{\n+\tactive_cache[cc->pos] = new;\n+\tactive_cache_changed = 1;\n+}\n+\n+static inline int cache_empty(void)\n+{\n+\treturn active_cache == NULL;\n+}\n+\n+static inline int cache_eof(struct cache_cursor *cc)\n+{\n+\tif (cc->pos < active_nr)\n+\t\treturn 0;\n+\treturn -1;\n+}\n+\n+static inline int read_cache_needed(void)\n+{\n+\treturn cache_empty();\n+}\n+\n+static inline void next_name(struct cache_cursor *cc, struct cache_entry *ce)\n+{\n+\tdo {\n+\t\tnext_cc(cc);\n+\t} while (!cache_eof(cc) && ce_same_name(ce, cc_to_ce(cc)));\n+}\n+\n+/*\n+ * Walk the entire active cache, invoking \"func\" on each entry\n+ *\n+ * \"func\" is responsible for updating the cache_cursor. To break\n+ * out of the loop, \"func\" can return a negative result.\n+ */\n+static inline int walk_cache(cache_iterator_fn_t func)\n+{\n+\tstruct cache_cursor cc;\n+\n+\tinit_cc(&cc);\n+\twhile (!cache_eof(&cc)) {\n+\t\tint status = func(&cc, cc_to_ce(&cc));\n+\t\tif (status < 0)\n+\t\t\treturn status;\n+\t}\n+\treturn 0;\n+}\n+\n struct checkout {\n \tconst char *base_dir;\n \tint base_dir_len;\n"},{"id":"8394","messageId":"20050912145547.28120.22685.stgit@dexter.citi.umich.edu","threadId":"1782","inReplyTo":"20050912145543.28120.7086.stgit@dexter.citi.umich.edu","subject":"[PATCH 02/22] use cache iterator in checkout-index.c","fromName":"Chuck Lever","fromEmail":"cel@netapp.com","sentAt":"2005-09-12T14:55:47Z","receivedAt":"2005-09-12T14:55:47Z","isPatch":true,"sender":{"key":"cel@netapp.com","avatar":null},"body":"Signed-off-by: Chuck Lever \n---\n\n checkout-index.c | 16 +++++-----------\n 1 files changed, 5 insertions(+), 11 deletions(-)\n\ndiff --git a/checkout-index.c b/checkout-index.c\n--- a/checkout-index.c\n+++ b/checkout-index.c\n@@ -61,17 +61,12 @@ static int checkout_file(const char *nam\n \treturn checkout_entry(active_cache[pos], &state);\n }\n \n-static int checkout_all(void)\n+static int checkout_one(struct cache_cursor *cc, struct cache_entry *ce)\n {\n-\tint i;\n-\n-\tfor (i = 0; i < active_nr ; i++) {\n-\t\tstruct cache_entry *ce = active_cache[i];\n-\t\tif (ce_stage(ce))\n-\t\t\tcontinue;\n+\tif (!ce_stage(ce))\n \t\tif (checkout_entry(ce, &state) < 0)\n \t\t\treturn -1;\n-\t}\n+\tnext_cc(cc);\n \treturn 0;\n }\n \n@@ -85,15 +80,14 @@ int main(int argc, char **argv)\n \tint i, force_filename = 0;\n \tint newfd = -1;\n \n-\tif (read_cache() < 0) {\n+\tif (read_cache() < 0)\n \t\tdie(\"invalid cache\");\n-\t}\n \n \tfor (i = 1; i < argc; i++) {\n \t\tconst char *arg = argv[i];\n \t\tif (!force_filename) {\n \t\t\tif (!strcmp(arg, \"-a\")) {\n-\t\t\t\tcheckout_all();\n+\t\t\t\twalk_cache(checkout_one);\n \t\t\t\tcontinue;\n \t\t\t}\n \t\t\tif (!strcmp(arg, \"--\")) {\n"},{"id":"8387","messageId":"20050912145549.28120.8321.stgit@dexter.citi.umich.edu","threadId":"1782","inReplyTo":"20050912145543.28120.7086.stgit@dexter.citi.umich.edu","subject":"[PATCH 03/22] teach diff.c about cache iterators","fromName":"Chuck Lever","fromEmail":"cel@netapp.com","sentAt":"2005-09-12T14:55:50Z","receivedAt":"2005-09-12T14:55:50Z","isPatch":true,"sender":{"key":"cel@netapp.com","avatar":null},"body":"Signed-off-by: Chuck Lever \n---\n\n diff.c | 6 +++---\n 1 files changed, 3 insertions(+), 3 deletions(-)\n\ndiff --git a/diff.c b/diff.c\n--- a/diff.c\n+++ b/diff.c\n@@ -258,7 +258,7 @@ static int work_tree_matches(const char \n \t * by diff-cache --cached, which does read the cache before\n \t * calling us.\n \t */\n-\tif (!active_cache)\n+\tif (read_cache_needed())\n \t\treturn 0;\n \n \tlen = strlen(name);\n@@ -677,12 +677,12 @@ void diff_setup(int flags)\n \tif (flags & DIFF_SETUP_REVERSE)\n \t\treverse_diff = 1;\n \tif (flags & DIFF_SETUP_USE_CACHE) {\n-\t\tif (!active_cache)\n+\t\tif (read_cache_needed())\n \t\t\t/* read-cache does not die even when it fails\n \t\t\t * so it is safe for us to do this here. Also\n \t\t\t * it does not smudge active_cache or active_nr\n \t\t\t * when it fails, so we do not have to worry about\n-\t\t\t * cleaning it up oufselves either.\n+\t\t\t * cleaning it up ourselves either.\n \t\t\t */\n \t\t\tread_cache();\n \t}\n"},{"id":"8398","messageId":"20050912145552.28120.21880.stgit@dexter.citi.umich.edu","threadId":"1782","inReplyTo":"20050912145543.28120.7086.stgit@dexter.citi.umich.edu","subject":"[PATCH 04/22] teach diff-index.c about cache iterators","fromName":"Chuck Lever","fromEmail":"cel@netapp.com","sentAt":"2005-09-12T14:55:52Z","receivedAt":"2005-09-12T14:55:52Z","isPatch":true,"sender":{"key":"cel@netapp.com","avatar":null},"body":"Signed-off-by: Chuck Lever \n---\n\n diff-index.c | 126 +++++++++++++++++++++++++++++-----------------------------\n 1 files changed, 62 insertions(+), 64 deletions(-)\n\ndiff --git a/diff-index.c b/diff-index.c\n--- a/diff-index.c\n+++ b/diff-index.c\n@@ -14,9 +14,10 @@ static int pickaxe_opts = 0;\n static int diff_break_opt = -1;\n static const char *orderfile = NULL;\n static const char *diff_filter = NULL;\n+static const char **pathspec = NULL;\n \n /* A file entry went away or appeared */\n-static void show_file(const char *prefix, struct cache_entry *ce, unsigned char *sha1, unsigned int mode)\n+static inline void show_file(const char *prefix, struct cache_entry *ce, unsigned char *sha1, unsigned int mode)\n {\n \tdiff_addremove(prefix[0], ntohl(mode), sha1, ce->name, NULL);\n }\n@@ -88,62 +89,63 @@ static int show_modified(struct cache_en\n \treturn 0;\n }\n \n-static int diff_cache(struct cache_entry **ac, int entries, const char **pathspec)\n+static int diff_one(struct cache_cursor *cc, struct cache_entry *ce)\n {\n-\twhile (entries) {\n-\t\tstruct cache_entry *ce = *ac;\n-\t\tint same = (entries > 1) && ce_same_name(ce, ac[1]);\n-\n-\t\tif (!ce_path_match(ce, pathspec))\n-\t\t\tgoto skip_entry;\n-\n-\t\tswitch (ce_stage(ce)) {\n-\t\tcase 0:\n-\t\t\t/* No stage 1 entry? That means it's a new file */\n-\t\t\tif (!same) {\n-\t\t\t\tshow_new_file(ce);\n-\t\t\t\tbreak;\n-\t\t\t}\n-\t\t\t/* Show difference between old and new */\n-\t\t\tshow_modified(ac[1], ce, 1);\n+\tstruct cache_entry *next;\n+\tint same;\n+\n+\tif (!ce_path_match(ce, pathspec))\n+\t\tgoto skip_entry;\n+\n+\tnext_cc(cc);\n+\tnext = cc_to_ce(cc);\n+\t/* check eof here to skip the last entry in the cache */\n+\tsame = (!cache_eof(cc) && ce_same_name(ce, next));\n+\tprev_cc(cc);\n+\n+\tswitch (ce_stage(ce)) {\n+\tcase 0:\n+\t\t/* No stage 1 entry? That means it's a new file */\n+\t\tif (!same) {\n+\t\t\tshow_new_file(ce);\n \t\t\tbreak;\n-\t\tcase 1:\n-\t\t\t/* No stage 3 (merge) entry? That means it's been deleted */\n-\t\t\tif (!same) {\n-\t\t\t\tshow_file(\"-\", ce, ce->sha1, ce->ce_mode);\n-\t\t\t\tbreak;\n-\t\t\t}\n-\t\t\t/* We come here with ce pointing at stage 1\n-\t\t\t * (original tree) and ac[1] pointing at stage\n-\t\t\t * 3 (unmerged). show-modified with\n-\t\t\t * report-mising set to false does not say the\n-\t\t\t * file is deleted but reports true if work\n-\t\t\t * tree does not have it, in which case we\n-\t\t\t * fall through to report the unmerged state.\n-\t\t\t * Otherwise, we show the differences between\n-\t\t\t * the original tree and the work tree.\n-\t\t\t */\n-\t\t\tif (!cached_only && !show_modified(ce, ac[1], 0))\n-\t\t\t\tbreak;\n-\t\t\t/* fallthru */\n-\t\tcase 3:\n-\t\t\tdiff_unmerge(ce->name);\n+\t\t}\n+\t\t/* Show difference between old and new */\n+\t\tshow_modified(next, ce, 1);\n+\t\tbreak;\n+\tcase 1:\n+\t\t/* No stage 3 (merge) entry? That means it's been deleted */\n+\t\tif (!same) {\n+\t\t\tshow_file(\"-\", ce, ce->sha1, ce->ce_mode);\n \t\t\tbreak;\n-\n-\t\tdefault:\n-\t\t\tdie(\"impossible cache entry stage\");\n \t\t}\n-\n-skip_entry:\n-\t\t/*\n-\t\t * Ignore all the different stages for this file,\n-\t\t * we've handled the relevant cases now.\n+\t\t/* We come here with ce pointing at stage 1\n+\t\t * (original tree) and next pointing at stage\n+\t\t * 3 (unmerged). show-modified with\n+\t\t * report-mising set to false does not say the\n+\t\t * file is deleted but reports true if work\n+\t\t * tree does not have it, in which case we\n+\t\t * fall through to report the unmerged state.\n+\t\t * Otherwise, we show the differences between\n+\t\t * the original tree and the work tree.\n \t\t */\n-\t\tdo {\n-\t\t\tac++;\n-\t\t\tentries--;\n-\t\t} while (entries && ce_same_name(ce, ac[0]));\n+\t\tif (!cached_only && !show_modified(ce, next, 0))\n+\t\t\tbreak;\n+\t\t/* fallthru */\n+\tcase 3:\n+\t\tdiff_unmerge(ce->name);\n+\t\tbreak;\n+\tdefault:\n+\t\tdie(\"impossible cache entry stage\");\n+\t\tbreak;\n \t}\n+\n+skip_entry:\n+\t/*\n+\t * Ignore all the different stages for this file,\n+\t * we've handled the relevant cases now.\n+\t */\n+\tnext_name(cc, ce);\n \treturn 0;\n }\n \n@@ -152,15 +154,12 @@ skip_entry:\n * when we read in the new tree (into \"stage 1\"), we won't lose sight\n * of the fact that we had unmerged entries.\n */\n-static void mark_merge_entries(void)\n+static int mark_one_entry(struct cache_cursor *cc, struct cache_entry *ce)\n {\n-\tint i;\n-\tfor (i = 0; i < active_nr; i++) {\n-\t\tstruct cache_entry *ce = active_cache[i];\n-\t\tif (!ce_stage(ce))\n-\t\t\tcontinue;\n+\tif (ce_stage(ce))\n \t\tce->ce_flags |= htons(CE_STAGEMASK);\n-\t}\n+\tnext_cc(cc);\n+\treturn 0;\n }\n \n static const char diff_cache_usage[] =\n@@ -173,10 +172,8 @@ int main(int argc, char **argv)\n \tconst char *tree_name = NULL;\n \tunsigned char sha1[20];\n \tconst char *prefix = setup_git_directory();\n-\tconst char **pathspec = NULL;\n \tvoid *tree;\n \tunsigned long size;\n-\tint ret;\n \tint allow_options = 1;\n \tint i;\n \n@@ -271,12 +268,13 @@ int main(int argc, char **argv)\n \tif (!tree_name || get_sha1(tree_name, sha1))\n \t\tusage(diff_cache_usage);\n \n-\tread_cache();\n+\tif (read_cache() < 0)\n+\t\tdie(\"unable to read index file\");\n \n \t/* The rest is for paths restriction. */\n \tdiff_setup(diff_setup_opt);\n \n-\tmark_merge_entries();\n+\twalk_cache(mark_one_entry);\n \n \ttree = read_object_with_reference(sha1, \"tree\", &size, NULL);\n \tif (!tree)\n@@ -284,7 +282,7 @@ int main(int argc, char **argv)\n \tif (read_tree(tree, size, 1, pathspec))\n \t\tdie(\"unable to read tree object %s\", tree_name);\n \n-\tret = diff_cache(active_cache, active_nr, pathspec);\n+\twalk_cache(diff_one);\n \n \tdiffcore_std(pathspec,\n \t\t detect_rename, diff_score_opt,\n@@ -292,5 +290,5 @@ int main(int argc, char **argv)\n \t\t diff_break_opt,\n \t\t orderfile, diff_filter);\n \tdiff_flush(diff_output_format, diff_line_termination);\n-\treturn ret;\n+\treturn 0;\n }\n"},{"id":"8393","messageId":"20050912145554.28120.4307.stgit@dexter.citi.umich.edu","threadId":"1782","inReplyTo":"20050912145543.28120.7086.stgit@dexter.citi.umich.edu","subject":"[PATCH 05/22] teach diff-files.c about cache iterators","fromName":"Chuck Lever","fromEmail":"cel@netapp.com","sentAt":"2005-09-12T14:55:54Z","receivedAt":"2005-09-12T14:55:54Z","isPatch":true,"sender":{"key":"cel@netapp.com","avatar":null},"body":"Signed-off-by: Chuck Lever \n---\n\n diff-files.c | 79 ++++++++++++++++++++++++++++++----------------------------\n 1 files changed, 41 insertions(+), 38 deletions(-)\n\ndiff --git a/diff-files.c b/diff-files.c\n--- a/diff-files.c\n+++ b/diff-files.c\n@@ -11,6 +11,7 @@ static const char diff_files_usage[] =\n \"[] [...]\"\n COMMON_DIFF_OPTIONS_HELP;\n \n+static const unsigned char null_sha1[20] = { 0, };\n static int diff_output_format = DIFF_FORMAT_RAW;\n static int diff_line_termination = '\\n';\n static int detect_rename = 0;\n@@ -22,6 +23,7 @@ static int pickaxe_opts = 0;\n static int diff_break_opt = -1;\n static const char *orderfile = NULL;\n static const char *diff_filter = NULL;\n+static const char **pathspec;\n static int silent = 0;\n \n static void show_unmerge(const char *path)\n@@ -41,12 +43,47 @@ static void show_modified(int oldmode, i\n \tdiff_change(oldmode, mode, old_sha1, sha1, path, NULL);\n }\n \n+static int diff_one_file(struct cache_cursor *cc, struct cache_entry *ce)\n+{\n+\tstruct stat st;\n+\tunsigned int oldmode;\n+\tint changed;\n+\n+\tif (!ce_path_match(ce, pathspec))\n+\t\tgoto out;\n+\n+\tif (ce_stage(ce)) {\n+\t\tshow_unmerge(ce->name);\n+\t\tnext_name(cc, ce);\n+\t\treturn 0;\n+\t}\n+\n+\tif (lstat(ce->name, &st) < 0) {\n+\t\tif (errno != ENOENT && errno != ENOTDIR) {\n+\t\t\tperror(ce->name);\n+\t\t\tgoto out;\n+\t\t}\n+\t\tif (silent)\n+\t\t\tgoto out;\n+\t\tshow_file('-', ce);\n+\t\tgoto out;\n+\t}\n+\tchanged = ce_match_stat(ce, &st);\n+\tif (!changed && !find_copies_harder)\n+\t\tgoto out;\n+\toldmode = ntohl(ce->ce_mode);\n+\tshow_modified(oldmode, DIFF_FILE_CANON_MODE(st.st_mode),\n+\t\t ce->sha1, (changed ? null_sha1 : ce->sha1),\n+\t\t ce->name);\n+out:\n+\tnext_cc(cc);\n+\treturn 0;\n+}\n+\n int main(int argc, char **argv)\n {\n-\tstatic const unsigned char null_sha1[20] = { 0, };\n-\tconst char **pathspec;\n \tconst char *prefix = setup_git_directory();\n-\tint entries, i;\n+\tint entries;\n \n \twhile (1 < argc && argv[1][0] == '-') {\n \t\tif (!strcmp(argv[1], \"-p\") || !strcmp(argv[1], \"-u\"))\n@@ -112,42 +149,8 @@ int main(int argc, char **argv)\n \n \tdiff_setup(diff_setup_opt);\n \n-\tfor (i = 0; i < entries; i++) {\n-\t\tstruct stat st;\n-\t\tunsigned int oldmode;\n-\t\tstruct cache_entry *ce = active_cache[i];\n-\t\tint changed;\n-\n-\t\tif (!ce_path_match(ce, pathspec))\n-\t\t\tcontinue;\n-\n-\t\tif (ce_stage(ce)) {\n-\t\t\tshow_unmerge(ce->name);\n-\t\t\twhile (i < entries &&\n-\t\t\t !strcmp(ce->name, active_cache[i]->name))\n-\t\t\t\ti++;\n-\t\t\ti--; /* compensate for loop control increments */\n-\t\t\tcontinue;\n-\t\t}\n+\twalk_cache(diff_one_file);\n \n-\t\tif (lstat(ce->name, &st) < 0) {\n-\t\t\tif (errno != ENOENT && errno != ENOTDIR) {\n-\t\t\t\tperror(ce->name);\n-\t\t\t\tcontinue;\n-\t\t\t}\n-\t\t\tif (silent)\n-\t\t\t\tcontinue;\n-\t\t\tshow_file('-', ce);\n-\t\t\tcontinue;\n-\t\t}\n-\t\tchanged = ce_match_stat(ce, &st);\n-\t\tif (!changed && !find_copies_harder)\n-\t\t\tcontinue;\n-\t\toldmode = ntohl(ce->ce_mode);\n-\t\tshow_modified(oldmode, DIFF_FILE_CANON_MODE(st.st_mode),\n-\t\t\t ce->sha1, (changed ? null_sha1 : ce->sha1),\n-\t\t\t ce->name);\n-\t}\n \tdiffcore_std(pathspec, \n \t\t detect_rename, diff_score_opt,\n \t\t pickaxe, pickaxe_opts,\n"},{"id":"8391","messageId":"20050912145556.28120.64001.stgit@dexter.citi.umich.edu","threadId":"1782","inReplyTo":"20050912145543.28120.7086.stgit@dexter.citi.umich.edu","subject":"[PATCH 06/22] teach diff-stages.c about cache iterators","fromName":"Chuck Lever","fromEmail":"cel@netapp.com","sentAt":"2005-09-12T14:55:56Z","receivedAt":"2005-09-12T14:55:56Z","isPatch":true,"sender":{"key":"cel@netapp.com","avatar":null},"body":"Signed-off-by: Chuck Lever \n---\n\n diff-stages.c | 73 +++++++++++++++++++++++++++++----------------------------\n 1 files changed, 37 insertions(+), 36 deletions(-)\n\ndiff --git a/diff-stages.c b/diff-stages.c\n--- a/diff-stages.c\n+++ b/diff-stages.c\n@@ -17,54 +17,55 @@ static int diff_break_opt = -1;\n static const char *orderfile = NULL;\n static const char *diff_filter = NULL;\n \n+static int stage1, stage2;\n+\n static const char diff_stages_usage[] =\n \"git-diff-stages [] [...]\"\n COMMON_DIFF_OPTIONS_HELP;\n \n-static void diff_stages(int stage1, int stage2)\n+static int diff_one(struct cache_cursor *cc, struct cache_entry *ce)\n {\n-\tint i = 0;\n-\twhile (i < active_nr) {\n-\t\tstruct cache_entry *ce, *stages[4] = { NULL, };\n-\t\tstruct cache_entry *one, *two;\n-\t\tconst char *name;\n-\t\tint len;\n-\t\tce = active_cache[i];\n-\t\tlen = ce_namelen(ce);\n-\t\tname = ce->name;\n-\t\tfor (;;) {\n-\t\t\tint stage = ce_stage(ce);\n-\t\t\tstages[stage] = ce;\n-\t\t\tif (active_nr <= ++i)\n-\t\t\t\tbreak;\n-\t\t\tce = active_cache[i];\n-\t\t\tif (ce_namelen(ce) != len ||\n-\t\t\t memcmp(name, ce->name, len))\n-\t\t\t\tbreak;\n-\t\t}\n-\t\tone = stages[stage1];\n-\t\ttwo = stages[stage2];\n-\t\tif (!one && !two)\n-\t\t\tcontinue;\n-\t\tif (!one)\n-\t\t\tdiff_addremove('+', ntohl(two->ce_mode),\n-\t\t\t\t two->sha1, name, NULL);\n-\t\telse if (!two)\n-\t\t\tdiff_addremove('-', ntohl(one->ce_mode),\n-\t\t\t\t one->sha1, name, NULL);\n+\tstruct cache_entry *one, *two, *stages[4] = { NULL, };\n+\tconst char *name = ce->name;\n+\tint len = ce_namelen(ce);\n+\n+\tfor (;;) {\n+\t\tint stage = ce_stage(ce);\n+\t\tstages[stage] = ce;\n+\t\tnext_cc(cc);\n+\t\tif (cache_eof(cc))\n+\t\t\tbreak;\n+\t\tce = cc_to_ce(cc);\n+\t\tif (ce_namelen(ce) != len ||\n+\t\t\tmemcmp(name, ce->name, len))\n+\t\t\tbreak;\n+\t}\n+\n+\tone = stages[stage1];\n+\ttwo = stages[stage2];\n+\tif (!one && !two)\n+\t\tgoto out;\n+\tif (!one)\n+\t\tdiff_addremove('+', ntohl(two->ce_mode),\n+\t\t\t\t\ttwo->sha1, name, NULL);\n+\telse if (!two)\n+\t\tdiff_addremove('-', ntohl(one->ce_mode),\n+\t\t\t\t\tone->sha1, name, NULL);\n \t\telse if (memcmp(one->sha1, two->sha1, 20) ||\n \t\t\t (one->ce_mode != two->ce_mode) ||\n-\t\t\t find_copies_harder)\n+\t\t\tfind_copies_harder)\n \t\t\tdiff_change(ntohl(one->ce_mode), ntohl(two->ce_mode),\n-\t\t\t\t one->sha1, two->sha1, name, NULL);\n-\t}\n+\t\t\t\t\tone->sha1, two->sha1, name, NULL);\n+out:\n+\tnext_cc(cc);\n+\treturn 0;\n }\n \n int main(int ac, const char **av)\n {\n-\tint stage1, stage2;\n+\tif (read_cache() < 0)\n+\t\tdie(\"unable to read index file\");\n \n-\tread_cache();\n \twhile (1 < ac && av[1][0] == '-') {\n \t\tconst char *arg = av[1];\n \t\tif (!strcmp(arg, \"-r\"))\n@@ -117,7 +118,7 @@ int main(int ac, const char **av)\n \tav += 3; /* The rest from av[0] are for paths restriction. */\n \tdiff_setup(diff_setup_opt);\n \n-\tdiff_stages(stage1, stage2);\n+\twalk_cache(diff_one);\n \n \tdiffcore_std(av,\n \t\t detect_rename, diff_score_opt,\n"},{"id":"8399","messageId":"20050912145558.28120.91494.stgit@dexter.citi.umich.edu","threadId":"1782","inReplyTo":"20050912145543.28120.7086.stgit@dexter.citi.umich.edu","subject":"[PATCH 07/22] teach fsck-objects.c to use cache iterators","fromName":"Chuck Lever","fromEmail":"cel@netapp.com","sentAt":"2005-09-12T14:55:58Z","receivedAt":"2005-09-12T14:55:58Z","isPatch":true,"sender":{"key":"cel@netapp.com","avatar":null},"body":"Signed-off-by: Chuck Lever \n---\n\n fsck-objects.c | 27 ++++++++++++++++-----------\n 1 files changed, 16 insertions(+), 11 deletions(-)\n\ndiff --git a/fsck-objects.c b/fsck-objects.c\n--- a/fsck-objects.c\n+++ b/fsck-objects.c\n@@ -412,6 +412,20 @@ static int fsck_head_link(void)\n \treturn 0;\n }\n \n+static int mark_one_blob_reachable(struct cache_cursor *cc, struct cache_entry *ce)\n+{\n+\tstruct blob *blob = lookup_blob(ce->sha1);\n+\n+\tif (blob) {\n+\t\tstruct object *obj = &blob->object;\n+\t\tobj->used = 1;\n+\t\tmark_reachable(obj, REACHABLE);\n+\t}\n+\n+\tnext_cc(cc);\n+\treturn 0;\n+}\n+\n int main(int argc, char **argv)\n {\n \tint i, heads;\n@@ -519,17 +533,8 @@ int main(int argc, char **argv)\n \t}\n \n \tif (keep_cache_objects) {\n-\t\tint i;\n-\t\tread_cache();\n-\t\tfor (i = 0; i < active_nr; i++) {\n-\t\t\tstruct blob *blob = lookup_blob(active_cache[i]->sha1);\n-\t\t\tstruct object *obj;\n-\t\t\tif (!blob)\n-\t\t\t\tcontinue;\n-\t\t\tobj = &blob->object;\n-\t\t\tobj->used = 1;\n-\t\t\tmark_reachable(obj, REACHABLE);\n-\t\t}\n+\t\tif (read_cache() > 0)\n+\t\t\twalk_cache(mark_one_blob_reachable);\n \t}\n \n \tcheck_connectivity();\n"},{"id":"8378","messageId":"20050912145600.28120.86261.stgit@dexter.citi.umich.edu","threadId":"1782","inReplyTo":"20050912145543.28120.7086.stgit@dexter.citi.umich.edu","subject":"[PATCH 08/22] teach ls-files.c to use cache iterators","fromName":"Chuck Lever","fromEmail":"cel@netapp.com","sentAt":"2005-09-12T14:56:00Z","receivedAt":"2005-09-12T14:56:00Z","isPatch":true,"sender":{"key":"cel@netapp.com","avatar":null},"body":"Signed-off-by: Chuck Lever \n---\n\n ls-files.c | 58 +++++++++++++++++++++++++++++++++-------------------------\n 1 files changed, 33 insertions(+), 25 deletions(-)\n\ndiff --git a/ls-files.c b/ls-files.c\n--- a/ls-files.c\n+++ b/ls-files.c\n@@ -414,14 +414,38 @@ static void show_ce_entry(const char *ta\n \t\t ce->name + offset, line_terminator); \n }\n \n-static void show_files(void)\n+static int show_one_cached(struct cache_cursor *cc, struct cache_entry *ce)\n {\n-\tint i;\n+\tif (excluded(ce->name) != show_ignored)\n+\t\tgoto out;\n+\tif (show_unmerged && !ce_stage(ce))\n+\t\tgoto out;\n+\tshow_ce_entry(ce_stage(ce) ? tag_unmerged : tag_cached, ce);\n+out:\n+\tnext_cc(cc);\n+\treturn 0;\n+}\n \n+static int show_one_deleted(struct cache_cursor *cc, struct cache_entry *ce)\n+{\n+\tstruct stat st;\n+\n+\tif (excluded(ce->name) != show_ignored)\n+\t\tgoto out;\n+\tif (!lstat(ce->name, &st))\n+\t\tgoto out;\n+\tshow_ce_entry(tag_removed, ce);\n+out:\n+\tnext_cc(cc);\n+\treturn 0;\n+}\n+\n+static void show_files(void)\n+{\n \t/* For cached/deleted files we don't need to even do the readdir */\n \tif (show_others || show_killed) {\n \t\tconst char *path = \".\", *base = \"\";\n-\t\tint baselen = prefix_len;\n+\t\tint i, baselen = prefix_len;\n \n \t\tif (baselen)\n \t\t\tpath = base = prefix;\n@@ -433,27 +457,10 @@ static void show_files(void)\n \t\tif (show_killed)\n \t\t\tshow_killed_files();\n \t}\n-\tif (show_cached | show_stage) {\n-\t\tfor (i = 0; i < active_nr; i++) {\n-\t\t\tstruct cache_entry *ce = active_cache[i];\n-\t\t\tif (excluded(ce->name) != show_ignored)\n-\t\t\t\tcontinue;\n-\t\t\tif (show_unmerged && !ce_stage(ce))\n-\t\t\t\tcontinue;\n-\t\t\tshow_ce_entry(ce_stage(ce) ? tag_unmerged : tag_cached, ce);\n-\t\t}\n-\t}\n-\tif (show_deleted) {\n-\t\tfor (i = 0; i < active_nr; i++) {\n-\t\t\tstruct cache_entry *ce = active_cache[i];\n-\t\t\tstruct stat st;\n-\t\t\tif (excluded(ce->name) != show_ignored)\n-\t\t\t\tcontinue;\n-\t\t\tif (!lstat(ce->name, &st))\n-\t\t\t\tcontinue;\n-\t\t\tshow_ce_entry(tag_removed, ce);\n-\t\t}\n-\t}\n+\tif (show_cached | show_stage)\n+\t\twalk_cache(show_one_cached);\n+\tif (show_deleted)\n+\t\twalk_cache(show_one_deleted);\n }\n \n /*\n@@ -633,7 +640,8 @@ int main(int argc, char **argv)\n \tif (!(show_stage | show_deleted | show_others | show_unmerged | show_killed))\n \t\tshow_cached = 1;\n \n-\tread_cache();\n+\tif (read_cache() < 0)\n+\t\tdie(\"unable to read index file\");\n \tif (prefix)\n \t\tprune_cache();\n \tshow_files();\n"},{"id":"8379","messageId":"20050912145602.28120.31547.stgit@dexter.citi.umich.edu","threadId":"1782","inReplyTo":"20050912145543.28120.7086.stgit@dexter.citi.umich.edu","subject":"[PATCH 09/22] teach read-tree.c to use cache iterators","fromName":"Chuck Lever","fromEmail":"cel@netapp.com","sentAt":"2005-09-12T14:56:03Z","receivedAt":"2005-09-12T14:56:03Z","isPatch":true,"sender":{"key":"cel@netapp.com","avatar":null},"body":"Merging will wait for another patch.\n\nSigned-off-by: Chuck Lever \n---\n\n read-tree.c | 66 +++++++++++++++++++++++++++++++++--------------------------\n 1 files changed, 37 insertions(+), 29 deletions(-)\n\ndiff --git a/read-tree.c b/read-tree.c\n--- a/read-tree.c\n+++ b/read-tree.c\n@@ -233,7 +233,7 @@ static void reject_merge(struct cache_en\n \t ce->name);\n }\n \n-static void check_updates(struct cache_entry **src, int nr)\n+static int check_one_out(struct cache_cursor *cc, struct cache_entry *ce)\n {\n \tstatic struct checkout state = {\n \t\t.base_dir = \"\",\n@@ -242,19 +242,21 @@ static void check_updates(struct cache_e\n \t\t.refresh_cache = 1,\n \t};\n \tunsigned short mask = htons(CE_UPDATE);\n-\twhile (nr--) {\n-\t\tstruct cache_entry *ce = *src++;\n-\t\tif (!ce->ce_mode) {\n-\t\t\tif (update)\n-\t\t\t\tunlink(ce->name);\n-\t\t\tcontinue;\n-\t\t}\n-\t\tif (ce->ce_flags & mask) {\n-\t\t\tce->ce_flags &= ~mask;\n-\t\t\tif (update)\n-\t\t\t\tcheckout_entry(ce, &state);\n-\t\t}\n+\n+\tif (!ce->ce_mode) {\n+\t\tif (update)\n+\t\t\tunlink(ce->name);\n+\t\tgoto out;\n \t}\n+\n+\tif (ce->ce_flags & mask) {\n+\t\tce->ce_flags &= ~mask;\n+\t\tif (update)\n+\t\t\tcheckout_entry(ce, &state);\n+\t}\n+out:\n+\tnext_cc(cc);\n+\treturn 0;\n }\n \n static int unpack_trees(merge_fn_t fn)\n@@ -273,7 +275,7 @@ static int unpack_trees(merge_fn_t fn)\n \tif (unpack_trees_rec(posns, len, \"\", fn, &indpos))\n \t\treturn -1;\n \n-\tcheck_updates(active_cache, active_nr);\n+\twalk_cache(check_one_out);\n \treturn 0;\n }\n \n@@ -553,24 +555,30 @@ static int oneway_merge(struct cache_ent\n \treturn merged_entry(a, NULL);\n }\n \n-static int read_cache_unmerged(void)\n+static int deleted = 0;\n+static struct cache_cursor dst;\n+\n+static int read_one_unmerged(struct cache_cursor *cc, struct cache_entry *ce)\n {\n-\tint i, deleted;\n-\tstruct cache_entry **dst;\n+\tif (ce_stage(ce)) {\n+\t\tdeleted++;\n+\t\tgoto out;\n+\t}\n+\tif (deleted)\n+\t\tset_ce_at_cursor(&dst, ce);\n+\tnext_cc(&dst);\n+out:\n+\tnext_cc(cc);\n+\treturn 0;\n+}\n \n-\tread_cache();\n-\tdst = active_cache;\n-\tdeleted = 0;\n-\tfor (i = 0; i < active_nr; i++) {\n-\t\tstruct cache_entry *ce = active_cache[i];\n-\t\tif (ce_stage(ce)) {\n-\t\t\tdeleted++;\n-\t\t\tcontinue;\n-\t\t}\n-\t\tif (deleted)\n-\t\t\t*dst = ce;\n-\t\tdst++;\n+static int read_cache_unmerged(void)\n+{\n+\tif (read_cache() > 0) {\n+\t\tinit_cc(&dst);\n+\t\twalk_cache(read_one_unmerged);\n \t}\n+\n \tactive_nr -= deleted;\n \treturn deleted;\n }\n"},{"id":"8395","messageId":"20050912145605.28120.174.stgit@dexter.citi.umich.edu","threadId":"1782","inReplyTo":"20050912145543.28120.7086.stgit@dexter.citi.umich.edu","subject":"[PATCH 10/22] teach update-index.c about cache cursors","fromName":"Chuck Lever","fromEmail":"cel@netapp.com","sentAt":"2005-09-12T14:56:05Z","receivedAt":"2005-09-12T14:56:05Z","isPatch":true,"sender":{"key":"cel@netapp.com","avatar":null},"body":"Signed-off-by: Chuck Lever \n---\n\n update-index.c | 62 +++++++++++++++++++++++++-------------------------------\n 1 files changed, 28 insertions(+), 34 deletions(-)\n\ndiff --git a/update-index.c b/update-index.c\n--- a/update-index.c\n+++ b/update-index.c\n@@ -13,7 +13,7 @@\n * files be revision controlled.\n */\n static int allow_add = 0, allow_remove = 0, allow_replace = 0, not_new = 0, quiet = 0, info_only = 0;\n-static int force_remove;\n+static int force_remove, has_errors = 0;\n \n /* Three functions to allow overloaded pointer return; see linux/err.h */\n static inline void *ERR_PTR(long error)\n@@ -190,41 +190,35 @@ static struct cache_entry *refresh_entry\n \treturn updated;\n }\n \n-static int refresh_cache(void)\n+static int refresh_one(struct cache_cursor *cc, struct cache_entry *ce)\n {\n-\tint i;\n-\tint has_errors = 0;\n+\tstruct cache_entry *new;\n \n-\tfor (i = 0; i < active_nr; i++) {\n-\t\tstruct cache_entry *ce, *new;\n-\t\tce = active_cache[i];\n-\t\tif (ce_stage(ce)) {\n-\t\t\tprintf(\"%s: needs merge\\n\", ce->name);\n-\t\t\thas_errors = 1;\n-\t\t\twhile ((i < active_nr) &&\n-\t\t\t ! strcmp(active_cache[i]->name, ce->name))\n-\t\t\t\ti++;\n-\t\t\ti--;\n-\t\t\tcontinue;\n-\t\t}\n+\tif (ce_stage(ce)) {\n+\t\tprintf(\"%s: needs merge\\n\", ce->name);\n+\t\thas_errors = 1;\n+\t\tnext_name(cc, ce);\n+\t\treturn 0;\n+\t}\n \n-\t\tnew = refresh_entry(ce);\n-\t\tif (IS_ERR(new)) {\n-\t\t\tif (not_new && PTR_ERR(new) == -ENOENT)\n-\t\t\t\tcontinue;\n-\t\t\tif (quiet)\n-\t\t\t\tcontinue;\n-\t\t\tprintf(\"%s: needs update\\n\", ce->name);\n-\t\t\thas_errors = 1;\n-\t\t\tcontinue;\n-\t\t}\n-\t\tactive_cache_changed = 1;\n-\t\t/* You can NOT just free active_cache[i] here, since it\n-\t\t * might not be necessarily malloc()ed but can also come\n-\t\t * from mmap(). */\n-\t\tactive_cache[i] = new;\n+\tnew = refresh_entry(ce);\n+\tif (IS_ERR(new)) {\n+\t\tif (not_new && PTR_ERR(new) == -ENOENT)\n+\t\t\treturn 0;\n+\t\tif (quiet)\n+\t\t\treturn 0;\n+\t\tprintf(\"%s: needs update\\n\", ce->name);\n+\t\thas_errors = 1;\n+\t\tnext_cc(cc);\n+\t\treturn 0;\n \t}\n-\treturn has_errors;\n+\n+\t/* You can NOT just free active_cache[i] here, since it\n+\t * might not be necessarily malloc()ed but can also come\n+\t * from mmap(). */\n+\tset_ce_at_cursor(cc, new);\n+\tnext_cc(cc);\n+\treturn 0;\n }\n \n /*\n@@ -323,7 +317,7 @@ static struct cache_file cache_file;\n \n int main(int argc, char **argv)\n {\n-\tint i, newfd, entries, has_errors = 0;\n+\tint i, newfd, entries;\n \tint allow_options = 1;\n \tconst char *prefix = setup_git_directory();\n \n@@ -360,7 +354,7 @@ int main(int argc, char **argv)\n \t\t\t\tcontinue;\n \t\t\t}\n \t\t\tif (!strcmp(path, \"--refresh\")) {\n-\t\t\t\thas_errors |= refresh_cache();\n+\t\t\t\twalk_cache(refresh_one);\n \t\t\t\tcontinue;\n \t\t\t}\n \t\t\tif (!strcmp(path, \"--cacheinfo\")) {\n"},{"id":"8397","messageId":"20050912145607.28120.80487.stgit@dexter.citi.umich.edu","threadId":"1782","inReplyTo":"20050912145543.28120.7086.stgit@dexter.citi.umich.edu","subject":"[PATCH 11/22] teach write-tree.c to use cache iterators","fromName":"Chuck Lever","fromEmail":"cel@netapp.com","sentAt":"2005-09-12T14:56:07Z","receivedAt":"2005-09-12T14:56:07Z","isPatch":true,"sender":{"key":"cel@netapp.com","avatar":null},"body":"Signed-off-by: Chuck Lever \n---\n\n write-tree.c | 110 ++++++++++++++++++++++++++++++++++++----------------------\n 1 files changed, 69 insertions(+), 41 deletions(-)\n\ndiff --git a/write-tree.c b/write-tree.c\n--- a/write-tree.c\n+++ b/write-tree.c\n@@ -5,7 +5,7 @@\n */\n #include \"cache.h\"\n \n-static int missing_ok = 0;\n+static int funny, missing_ok = 0;\n \n static int check_valid_sha1(unsigned char *sha1)\n {\n@@ -18,8 +18,9 @@ static int check_valid_sha1(unsigned cha\n \treturn ret ? 0 : -1;\n }\n \n-static int write_tree(struct cache_entry **cachep, int maxentries, const char *base, int baselen, unsigned char *returnsha1)\n+static int write_tree(struct cache_cursor *cc, int maxentries, const char *base, int baselen, unsigned char *returnsha1)\n {\n+\tstruct cache_cursor next = *cc;\n \tunsigned char subdir_sha1[20];\n \tunsigned long size, offset;\n \tchar *buffer;\n@@ -32,7 +33,7 @@ static int write_tree(struct cache_entry\n \n \tnr = 0;\n \twhile (nr < maxentries) {\n-\t\tstruct cache_entry *ce = cachep[nr];\n+\t\tstruct cache_entry *ce = cc_to_ce(&next);\n \t\tconst char *pathname = ce->name, *filename, *dirname;\n \t\tint pathlen = ce_namelen(ce), entrylen;\n \t\tunsigned char *sha1;\n@@ -51,15 +52,20 @@ static int write_tree(struct cache_entry\n \t\tif (dirname) {\n \t\t\tint subdir_written;\n \n-\t\t\tsubdir_written = write_tree(cachep + nr, maxentries - nr, pathname, dirname-pathname+1, subdir_sha1);\n-\t\t\tnr += subdir_written;\n-\n+\t\t\tsubdir_written = write_tree(&next,\n+\t\t\t\t\t\t maxentries - nr,\n+\t\t\t\t\t\t pathname,\n+\t\t\t\t\t\t dirname - pathname + 1,\n+\t\t\t\t\t\t subdir_sha1);\n+\t\t\t\n \t\t\t/* Now we need to write out the directory entry into this tree.. */\n \t\t\tmode = S_IFDIR;\n \t\t\tpathlen = dirname - pathname;\n \n \t\t\t/* ..but the directory entry doesn't count towards the total count */\n-\t\t\tnr--;\n+\t\t\tnr += subdir_written - 1;\n+\t\t\twhile (--subdir_written)\n+\t\t\t\tnext_cc(&next);\n \t\t\tsha1 = subdir_sha1;\n \t\t}\n \n@@ -76,6 +82,7 @@ static int write_tree(struct cache_entry\n \t\tmemcpy(buffer + offset, sha1, 20);\n \t\toffset += 20;\n \t\tnr++;\n+\t\tnext_cc(&next);\n \t}\n \n \twrite_sha1_file(buffer, offset, \"tree\", returnsha1);\n@@ -83,11 +90,57 @@ static int write_tree(struct cache_entry\n \treturn nr;\n }\n \n+static int verify_merged(struct cache_cursor *cc, struct cache_entry *ce)\n+{\n+\tif (ntohs(ce->ce_flags) & ~CE_NAMEMASK) {\n+\t\tif (10 < ++funny) {\n+\t\t\tfprintf(stderr, \"...\\n\");\n+\t\t\treturn -1;\n+\t\t}\n+\t\tfprintf(stderr, \"%s: unmerged (%s)\\n\", ce->name, sha1_to_hex(ce->sha1));\n+\t}\n+\n+\tnext_cc(cc);\n+\treturn 0;\n+}\n+\n+/*\n+ * path/file always comes after path because of the way\n+ * the cache is sorted. Also path can appear only once,\n+ * which means conflicting one would immediately follow.\n+ */\n+static int verify_path(struct cache_cursor *cc, struct cache_entry *ce)\n+{\n+\tstruct cache_entry *next;\n+\tconst char *next_name, *this_name = ce->name;\n+\tint this_len = strlen(this_name);\n+\n+\t/* don't check the last cache entry */\n+\tnext_cc(cc);\n+\tif (cache_eof(cc))\n+\t\treturn -1;\n+\tnext = cc_to_ce(cc);\n+\tnext_name = next->name;\n+\n+\tif (this_len < strlen(next_name) &&\n+\t strncmp(this_name, next_name, this_len) == 0 &&\n+\t next_name[this_len] == '/') {\n+\t\tif (10 < ++funny) {\n+\t\t\tfprintf(stderr, \"...\\n\");\n+\t\t\treturn -1;\n+\t\t}\n+\t\tfprintf(stderr, \"You have both %s and %s\\n\",\n+\t\t\tthis_name, next_name);\n+\t}\n+\n+\treturn 0;\n+}\n+\n int main(int argc, char **argv)\n {\n-\tint i, funny;\n-\tint entries = read_cache();\n+\tstruct cache_cursor cc;\n \tunsigned char sha1[20];\n+\tint entries;\n \t\n \tif (argc == 2) {\n \t\tif (!strcmp(argv[1], \"--missing-ok\"))\n@@ -99,53 +152,28 @@ int main(int argc, char **argv)\n \tif (argc > 2)\n \t\tdie(\"too many options\");\n \n+\tentries = read_cache();\n \tif (entries < 0)\n \t\tdie(\"git-write-tree: error reading cache\");\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 = active_cache[i];\n-\t\tif (ntohs(ce->ce_flags) & ~CE_NAMEMASK) {\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\", ce->name, sha1_to_hex(ce->sha1));\n-\t\t}\n-\t}\n+\twalk_cache(verify_merged);\n \tif (funny)\n-\t\tdie(\"git-write-tree: not able to write tree\");\n+\t\tdie(\"git-write-tree: verify_merged: not able to write tree\");\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 = active_cache[i]->name;\n-\t\tconst char *next_name = active_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+\twalk_cache(verify_path);\n \tif (funny)\n-\t\tdie(\"git-write-tree: not able to write tree\");\n+\t\tdie(\"git-write-tree: verify_path: not able to write tree\");\n \n \t/* Ok, write it out */\n-\tif (write_tree(active_cache, entries, \"\", 0, sha1) != entries)\n+\tinit_cc(&cc);\n+\tif (write_tree(&cc, entries, \"\", 0, sha1) != entries)\n \t\tdie(\"git-write-tree: internal error\");\n \tprintf(\"%s\\n\", sha1_to_hex(sha1));\n \treturn 0;\n"},{"id":"8390","messageId":"20050912145609.28120.67621.stgit@dexter.citi.umich.edu","threadId":"1782","inReplyTo":"20050912145543.28120.7086.stgit@dexter.citi.umich.edu","subject":"[PATCH 12/22] simplify write_cache() calling sequence","fromName":"Chuck Lever","fromEmail":"cel@netapp.com","sentAt":"2005-09-12T14:56:09Z","receivedAt":"2005-09-12T14:56:09Z","isPatch":true,"sender":{"key":"cel@netapp.com","avatar":null},"body":"Clean-up: Hide some external references to \"active_cache\" and \"active_nr\"\nby simplifying the calling sequence of write_cache().\n\nSigned-off-by: Chuck Lever \n---\n\n apply.c | 3 +--\n cache.h | 2 +-\n checkout-index.c | 3 +--\n read-cache.c | 41 +++++++++++++++++++++++++++--------------\n read-tree.c | 3 +--\n update-index.c | 3 +--\n 6 files changed, 32 insertions(+), 23 deletions(-)\n\ndiff --git a/apply.c b/apply.c\n--- a/apply.c\n+++ b/apply.c\n@@ -1440,8 +1440,7 @@ static int apply_patch(int fd)\n \t\twrite_out_results(list, skipped_patch);\n \n \tif (write_index) {\n-\t\tif (write_cache(newfd, active_cache, active_nr) ||\n-\t\t commit_index_file(&cache_file))\n+\t\tif (write_cache(newfd) || commit_index_file(&cache_file))\n \t\t\tdie(\"Unable to write new cachefile\");\n \t}\n \ndiff --git a/cache.h b/cache.h\n--- a/cache.h\n+++ b/cache.h\n@@ -157,7 +157,7 @@ extern char *prefix_path(const char *pre\n \n /* Initialize and use the cache information */\n extern int read_cache(void);\n-extern int write_cache(int newfd, struct cache_entry **cache, int entries);\n+extern int write_cache(int newfd);\n extern int cache_name_pos(const char *name, int namelen);\n #define ADD_CACHE_OK_TO_ADD 1\t\t/* Ok to add */\n #define ADD_CACHE_OK_TO_REPLACE 2\t/* Ok to replace file/directory */\ndiff --git a/checkout-index.c b/checkout-index.c\n--- a/checkout-index.c\n+++ b/checkout-index.c\n@@ -138,8 +138,7 @@ int main(int argc, char **argv)\n \t}\n \n \tif (0 <= newfd &&\n-\t (write_cache(newfd, active_cache, active_nr) ||\n-\t commit_index_file(&cache_file)))\n+\t (write_cache(newfd) || commit_index_file(&cache_file)))\n \t\tdie(\"Unable to write new cachefile\");\n \treturn 0;\n }\ndiff --git a/read-cache.c b/read-cache.c\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -470,30 +470,43 @@ static int ce_flush(SHA_CTX *context, in\n \treturn 0;\n }\n \n-int write_cache(int newfd, struct cache_entry **cache, int entries)\n+static int fd, removed = 0;\n+static SHA_CTX c;\n+\n+static int count_removed(struct cache_cursor *cc, struct cache_entry *ce)\n+{\n+\tif (ce->ce_mode == 0)\n+\t\tremoved++;\n+\tnext_cc(cc);\n+\treturn 0;\n+}\n+\n+static int write_one_cache_entry(struct cache_cursor *cc, struct cache_entry *ce)\n+{\n+\tif (ce->ce_mode != 0)\n+\t\tif (ce_write(&c, fd, ce, ce_size(ce)) < 0)\n+\t\t\treturn -1;\n+\tnext_cc(cc);\n+\treturn 0;\n+}\n+\n+int write_cache(int newfd)\n {\n-\tSHA_CTX c;\n \tstruct cache_header hdr;\n-\tint i, removed;\n \n-\tfor (i = removed = 0; i < entries; i++)\n-\t\tif (!cache[i]->ce_mode)\n-\t\t\tremoved++;\n+\twalk_cache(count_removed);\n \n \thdr.hdr_signature = htonl(CACHE_SIGNATURE);\n \thdr.hdr_version = htonl(2);\n-\thdr.hdr_entries = htonl(entries - removed);\n+\thdr.hdr_entries = htonl(active_nr - removed);\n \n \tSHA1_Init(&c);\n \tif (ce_write(&c, newfd, &hdr, sizeof(hdr)) < 0)\n \t\treturn -1;\n \n-\tfor (i = 0; i < entries; i++) {\n-\t\tstruct cache_entry *ce = cache[i];\n-\t\tif (!ce->ce_mode)\n-\t\t\tcontinue;\n-\t\tif (ce_write(&c, newfd, ce, ce_size(ce)) < 0)\n-\t\t\treturn -1;\n-\t}\n+\tfd = newfd;\n+\tif (walk_cache(write_one_cache_entry))\n+\t\treturn -1;\n+\n \treturn ce_flush(&c, newfd);\n }\ndiff --git a/read-tree.c b/read-tree.c\n--- a/read-tree.c\n+++ b/read-tree.c\n@@ -670,8 +670,7 @@ int main(int argc, char **argv)\n \t}\n \n \tunpack_trees(fn);\n-\tif (write_cache(newfd, active_cache, active_nr) ||\n-\t commit_index_file(&cache_file))\n+\tif (write_cache(newfd) || commit_index_file(&cache_file))\n \t\tdie(\"unable to write new index file\");\n \treturn 0;\n }\ndiff --git a/update-index.c b/update-index.c\n--- a/update-index.c\n+++ b/update-index.c\n@@ -393,8 +393,7 @@ int main(int argc, char **argv)\n \t\tif (add_file_to_cache(path))\n \t\t\tdie(\"Unable to add %s to database; maybe you want to use --add option?\", path);\n \t}\n-\tif (write_cache(newfd, active_cache, active_nr) ||\n-\t commit_index_file(&cache_file))\n+\tif (write_cache(newfd) || commit_index_file(&cache_file))\n \t\tdie(\"Unable to write new cachefile\");\n \n \treturn has_errors ? 1 : 0;\n"},{"id":"8383","messageId":"20050912145611.28120.45845.stgit@dexter.citi.umich.edu","threadId":"1782","inReplyTo":"20050912145543.28120.7086.stgit@dexter.citi.umich.edu","subject":"[PATCH 13/22] move purge_cache() to read-cache.c","fromName":"Chuck Lever","fromEmail":"cel@netapp.com","sentAt":"2005-09-12T14:56:11Z","receivedAt":"2005-09-12T14:56:11Z","isPatch":true,"sender":{"key":"cel@netapp.com","avatar":null},"body":"Functions that manipulate active_cache and active_nr should be in one place.\n\nSigned-off-by: Chuck Lever \n---\n\n cache.h | 1 +\n ls-files.c | 28 +---------------------------\n read-cache.c | 26 ++++++++++++++++++++++++++\n 3 files changed, 28 insertions(+), 27 deletions(-)\n\ndiff --git a/cache.h b/cache.h\n--- a/cache.h\n+++ b/cache.h\n@@ -165,6 +165,7 @@ extern int cache_name_pos(const char *na\n extern int add_cache_entry(struct cache_entry *ce, int option);\n extern int remove_cache_entry_at(int pos);\n extern int remove_file_from_cache(char *path);\n+extern void prune_cache(const char *prefix, int prefix_len);\n extern int ce_same_name(struct cache_entry *a, struct cache_entry *b);\n extern int ce_match_stat(struct cache_entry *ce, struct stat *st);\n extern int ce_path_match(const struct cache_entry *ce, const char **pathspec);\ndiff --git a/ls-files.c b/ls-files.c\n--- a/ls-files.c\n+++ b/ls-files.c\n@@ -463,32 +463,6 @@ static void show_files(void)\n \t\twalk_cache(show_one_deleted);\n }\n \n-/*\n- * Prune the index to only contain stuff starting with \"prefix\"\n- */\n-static void prune_cache(void)\n-{\n-\tint pos = cache_name_pos(prefix, prefix_len);\n-\tunsigned int first, last;\n-\n-\tif (pos < 0)\n-\t\tpos = -pos-1;\n-\tactive_cache += pos;\n-\tactive_nr -= pos;\n-\tfirst = 0;\n-\tlast = active_nr;\n-\twhile (last > first) {\n-\t\tint next = (last + first) >> 1;\n-\t\tstruct cache_entry *ce = active_cache[next];\n-\t\tif (!strncmp(ce->name, prefix, prefix_len)) {\n-\t\t\tfirst = next+1;\n-\t\t\tcontinue;\n-\t\t}\n-\t\tlast = next;\n-\t}\n-\tactive_nr = last;\n-}\n-\n static void verify_pathspec(void)\n {\n \tconst char **p, *n, *prev;\n@@ -643,7 +617,7 @@ int main(int argc, char **argv)\n \tif (read_cache() < 0)\n \t\tdie(\"unable to read index file\");\n \tif (prefix)\n-\t\tprune_cache();\n+\t\tprune_cache(prefix, prefix_len);\n \tshow_files();\n \treturn 0;\n }\ndiff --git a/read-cache.c b/read-cache.c\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -165,6 +165,32 @@ int remove_file_from_cache(char *path)\n \treturn 0;\n }\n \n+/*\n+ * Prune the index to only contain stuff starting with \"prefix\"\n+ */\n+void prune_cache(const char *prefix, int prefix_len)\n+{\n+\tint pos = cache_name_pos(prefix, prefix_len);\n+\tunsigned int first, last;\n+\n+\tif (pos < 0)\n+\t\tpos = -pos-1;\n+\tactive_cache += pos;\n+\tactive_nr -= pos;\n+\tfirst = 0;\n+\tlast = active_nr;\n+\twhile (last > first) {\n+\t\tint next = (last + first) >> 1;\n+\t\tstruct cache_entry *ce = active_cache[next];\n+\t\tif (!strncmp(ce->name, prefix, prefix_len)) {\n+\t\t\tfirst = next+1;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tlast = next;\n+\t}\n+\tactive_nr = last;\n+}\n+\n int ce_same_name(struct cache_entry *a, struct cache_entry *b)\n {\n \tint len = ce_namelen(a);\n"},{"id":"8381","messageId":"20050912145613.28120.32935.stgit@dexter.citi.umich.edu","threadId":"1782","inReplyTo":"20050912145543.28120.7086.stgit@dexter.citi.umich.edu","subject":"[PATCH 14/22] move read_cache_unmerged into read-cache.c","fromName":"Chuck Lever","fromEmail":"cel@netapp.com","sentAt":"2005-09-12T14:56:14Z","receivedAt":"2005-09-12T14:56:14Z","isPatch":true,"sender":{"key":"cel@netapp.com","avatar":null},"body":"Clean-up: put read_cache_unmerged() right next to read_cache().\nread_cache_unmerged() will likely need to be reconstructed if\nthe active cache data type changes.\n\nSigned-off-by: Chuck Lever \n---\n\n cache.h | 1 +\n read-cache.c | 31 +++++++++++++++++++++++++++++++\n read-tree.c | 28 ----------------------------\n 3 files changed, 32 insertions(+), 28 deletions(-)\n\ndiff --git a/cache.h b/cache.h\n--- a/cache.h\n+++ b/cache.h\n@@ -157,6 +157,7 @@ extern char *prefix_path(const char *pre\n \n /* Initialize and use the cache information */\n extern int read_cache(void);\n+extern int read_cache_unmerged(void);\n extern int write_cache(int newfd);\n extern int cache_name_pos(const char *name, int namelen);\n #define ADD_CACHE_OK_TO_ADD 1\t\t/* Ok to add */\ndiff --git a/read-cache.c b/read-cache.c\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -453,6 +453,37 @@ unmap:\n \treturn error(\"verify header failed\");\n }\n \n+static int deleted = 0;\n+static struct cache_cursor dst;\n+\n+static int read_one_unmerged(struct cache_cursor *cc, struct cache_entry *ce)\n+{\n+\tif (ce_stage(ce)) {\n+\t\tdeleted++;\n+\t\tgoto out;\n+\t}\n+\tif (deleted)\n+\t\tset_ce_at_cursor(&dst, ce);\n+\tnext_cc(&dst);\n+out:\n+\tnext_cc(cc);\n+\treturn 0;\n+}\n+\n+/*\n+ * Read in the cache, then throw away the unmerged entries\n+ */\n+int read_cache_unmerged(void)\n+{\n+\tif (read_cache() > 0) {\n+\t\tinit_cc(&dst);\n+\t\twalk_cache(read_one_unmerged);\n+\t}\n+\n+\tactive_nr -= deleted;\n+\treturn deleted;\n+}\n+\n #define WRITE_BUFFER_SIZE 8192\n static unsigned char write_buffer[WRITE_BUFFER_SIZE];\n static unsigned long write_buffer_len;\ndiff --git a/read-tree.c b/read-tree.c\n--- a/read-tree.c\n+++ b/read-tree.c\n@@ -555,34 +555,6 @@ static int oneway_merge(struct cache_ent\n \treturn merged_entry(a, NULL);\n }\n \n-static int deleted = 0;\n-static struct cache_cursor dst;\n-\n-static int read_one_unmerged(struct cache_cursor *cc, struct cache_entry *ce)\n-{\n-\tif (ce_stage(ce)) {\n-\t\tdeleted++;\n-\t\tgoto out;\n-\t}\n-\tif (deleted)\n-\t\tset_ce_at_cursor(&dst, ce);\n-\tnext_cc(&dst);\n-out:\n-\tnext_cc(cc);\n-\treturn 0;\n-}\n-\n-static int read_cache_unmerged(void)\n-{\n-\tif (read_cache() > 0) {\n-\t\tinit_cc(&dst);\n-\t\twalk_cache(read_one_unmerged);\n-\t}\n-\n-\tactive_nr -= deleted;\n-\treturn deleted;\n-}\n-\n static const char read_tree_usage[] = \"git-read-tree ( | -m [-u] [ []])\";\n \n static struct cache_file cache_file;\n"},{"id":"8382","messageId":"20050912145616.28120.30912.stgit@dexter.citi.umich.edu","threadId":"1782","inReplyTo":"20050912145543.28120.7086.stgit@dexter.citi.umich.edu","subject":"[PATCH 15/22] replace cache_name_pos","fromName":"Chuck Lever","fromEmail":"cel@netapp.com","sentAt":"2005-09-12T14:56:16Z","receivedAt":"2005-09-12T14:56:16Z","isPatch":true,"sender":{"key":"cel@netapp.com","avatar":null},"body":"Clean up: Introduce an interface to return a cache_cursor instead of\nan integer. Note we can also eliminate the need to overload the\nreturn value of cache_name_pos to return a negative \"pos\" value to\nsignal an insertion point rather than a found entry.\n\nSigned-off-by: Chuck Lever \n---\n\n cache.h | 13 +++++++++++++\n read-cache.c | 44 ++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 57 insertions(+), 0 deletions(-)\n\ndiff --git a/cache.h b/cache.h\n--- a/cache.h\n+++ b/cache.h\n@@ -160,6 +160,8 @@ extern int read_cache(void);\n extern int read_cache_unmerged(void);\n extern int write_cache(int newfd);\n extern int cache_name_pos(const char *name, int namelen);\n+extern int cache_find_name(const char *name, int namelen, struct cache_cursor *cc);\n+\n #define ADD_CACHE_OK_TO_ADD 1\t\t/* Ok to add */\n #define ADD_CACHE_OK_TO_REPLACE 2\t/* Ok to replace file/directory */\n #define ADD_CACHE_SKIP_DFCHECK 4\t/* Ok to skip DF conflict checks */\n@@ -350,6 +352,17 @@ static inline int walk_cache(cache_itera\n \treturn 0;\n }\n \n+static inline int cache_find_entry(const char *name, int namelen, struct cache_entry **ce)\n+{\n+\tstruct cache_cursor cc;\n+\tint result;\n+\n+\tresult = cache_find_name(name, namelen, &cc);\n+\tif (ce)\n+\t\t*ce = active_cache[cc.pos];\n+\treturn result;\n+}\n+\n struct checkout {\n \tconst char *base_dir;\n \tint base_dir_len;\ndiff --git a/read-cache.c b/read-cache.c\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -144,6 +144,50 @@ int cache_name_pos(const char *name, int\n \treturn -first-1;\n }\n \n+/*\n+ * Given a name, find the first cache entry that matches. Returning 1\n+ * means the cursor points to the cache entry with a matching name.\n+ * Returning 0 means the name wasn't found, but the cursor points to an\n+ * appropriate insertion point.\n+ */\n+int cache_find_name(const char *name, int namelen, struct cache_cursor *cc)\n+{\n+\tint first, last;\n+\n+\t/*\n+\t * Look for the right name\n+\t */\n+\tcc->pos = first = 0;\n+\tlast = active_nr;\n+\twhile (last > first) {\n+\t\tstruct cache_entry *ce;\n+\t\tint cmp;\n+\t\tcc->pos = (last + first) >> 1;\n+\t\tce = active_cache[cc->pos];\n+\t\tcmp = cache_name_compare(name, namelen, ce->name, ntohs(ce->ce_flags));\n+\t\tif (!cmp) {\n+\t\t\t/* found it */\n+\t\t\treturn 1;\n+\t\t}\n+\t\tif (cmp < 0) {\n+\t\t\t/* next: search [first, cc->pos] */\n+\t\t\tlast = cc->pos;\n+\t\t\tcontinue;\n+\t\t}\n+\t\t/* next: search [cc->pos + 1, last] */\n+\t\tfirst = cc->pos + 1;\n+\t}\n+\n+\t/*\n+\t * Name not found, so return an insertion point.\n+\t *\n+\t * On return, callers insert *before* the insertion point,\n+\t * not after it, to maintain proper list order.\n+\t */\n+\tcc->pos = first;\n+\treturn 0;\n+}\n+\n /* Remove entry, return true if there are more entries to go.. */\n int remove_cache_entry_at(int pos)\n {\n"},{"id":"8384","messageId":"20050912145618.28120.90781.stgit@dexter.citi.umich.edu","threadId":"1782","inReplyTo":"20050912145543.28120.7086.stgit@dexter.citi.umich.edu","subject":"[PATCH 16/22] teach apply.c to use cache_find_name()","fromName":"Chuck Lever","fromEmail":"cel@netapp.com","sentAt":"2005-09-12T14:56:18Z","receivedAt":"2005-09-12T14:56:18Z","isPatch":true,"sender":{"key":"cel@netapp.com","avatar":null},"body":"Signed-off-by: Chuck Lever \n---\n\n apply.c | 8 ++++----\n 1 files changed, 4 insertions(+), 4 deletions(-)\n\ndiff --git a/apply.c b/apply.c\n--- a/apply.c\n+++ b/apply.c\n@@ -1021,10 +1021,10 @@ static int check_patch(struct patch *pat\n \t\tif (lstat(old_name, &st) < 0)\n \t\t\treturn error(\"%s: %s\", old_name, strerror(errno));\n \t\tif (check_index) {\n-\t\t\tint pos = cache_name_pos(old_name, strlen(old_name));\n-\t\t\tif (pos < 0)\n+\t\t\tstruct cache_entry *ce;\n+\t\t\tif (!cache_find_entry(old_name, strlen(old_name), &ce))\n \t\t\t\treturn error(\"%s: does not exist in index\", old_name);\n-\t\t\tchanged = ce_match_stat(active_cache[pos], &st);\n+\t\t\tchanged = ce_match_stat(ce, &st);\n \t\t\tif (changed)\n \t\t\t\treturn error(\"%s: does not match index\", old_name);\n \t\t}\n@@ -1041,7 +1041,7 @@ static int check_patch(struct patch *pat\n \t}\n \n \tif (new_name && (patch->is_new | patch->is_rename | patch->is_copy)) {\n-\t\tif (check_index && cache_name_pos(new_name, strlen(new_name)) >= 0)\n+\t\tif (check_index && cache_find_entry(new_name, strlen(new_name), NULL))\n \t\t\treturn error(\"%s: already exists in index\", new_name);\n \t\tif (!lstat(new_name, &st))\n \t\t\treturn error(\"%s: already exists in working directory\", new_name);\n"},{"id":"8380","messageId":"20050912145620.28120.86534.stgit@dexter.citi.umich.edu","threadId":"1782","inReplyTo":"20050912145543.28120.7086.stgit@dexter.citi.umich.edu","subject":"[PATCH 17/22] teach checkout-index.c to use cache_find_name()","fromName":"Chuck Lever","fromEmail":"cel@netapp.com","sentAt":"2005-09-12T14:56:20Z","receivedAt":"2005-09-12T14:56:20Z","isPatch":true,"sender":{"key":"cel@netapp.com","avatar":null},"body":"Signed-off-by: Chuck Lever \n---\n\n checkout-index.c | 11 +++++------\n 1 files changed, 5 insertions(+), 6 deletions(-)\n\ndiff --git a/checkout-index.c b/checkout-index.c\n--- a/checkout-index.c\n+++ b/checkout-index.c\n@@ -45,20 +45,19 @@ static struct checkout state = {\n \n static int checkout_file(const char *name)\n {\n-\tint pos = cache_name_pos(name, strlen(name));\n-\tif (pos < 0) {\n+\tstruct cache_entry *ce;\n+\n+\tif (!cache_find_entry(name, strlen(name), &ce)) {\n \t\tif (!state.quiet) {\n-\t\t\tpos = -pos - 1;\n \t\t\tfprintf(stderr,\n \t\t\t\t\"git-checkout-index: %s is %s.\\n\",\n \t\t\t\tname,\n-\t\t\t\t(pos < active_nr &&\n-\t\t\t\t !strcmp(active_cache[pos]->name, name)) ?\n+\t\t\t\t!strcmp(ce->name, name) ?\n \t\t\t\t\"unmerged\" : \"not in the cache\");\n \t\t}\n \t\treturn -1;\n \t}\n-\treturn checkout_entry(active_cache[pos], &state);\n+\treturn checkout_entry(ce, &state);\n }\n \n static int checkout_one(struct cache_cursor *cc, struct cache_entry *ce)\n"},{"id":"8386","messageId":"20050912145622.28120.62972.stgit@dexter.citi.umich.edu","threadId":"1782","inReplyTo":"20050912145543.28120.7086.stgit@dexter.citi.umich.edu","subject":"[PATCH 18/22] teach diff.c to use cache_find_name()","fromName":"Chuck Lever","fromEmail":"cel@netapp.com","sentAt":"2005-09-12T14:56:22Z","receivedAt":"2005-09-12T14:56:22Z","isPatch":true,"sender":{"key":"cel@netapp.com","avatar":null},"body":"Signed-off-by: Chuck Lever \n---\n\n diff.c | 6 +-----\n 1 files changed, 1 insertions(+), 5 deletions(-)\n\ndiff --git a/diff.c b/diff.c\n--- a/diff.c\n+++ b/diff.c\n@@ -244,7 +244,6 @@ static int work_tree_matches(const char \n {\n \tstruct cache_entry *ce;\n \tstruct stat st;\n-\tint pos, len;\n \n \t/* We do not read the cache ourselves here, because the\n \t * benchmark with my previous version that always reads cache\n@@ -261,11 +260,8 @@ static int work_tree_matches(const char \n \tif (read_cache_needed())\n \t\treturn 0;\n \n-\tlen = strlen(name);\n-\tpos = cache_name_pos(name, len);\n-\tif (pos < 0)\n+\tif (!cache_find_entry(name, strlen(name), &ce))\n \t\treturn 0;\n-\tce = active_cache[pos];\n \tif ((lstat(name, &st) < 0) ||\n \t !S_ISREG(st.st_mode) || /* careful! */\n \t ce_match_stat(ce, &st) ||\n"},{"id":"8385","messageId":"20050912145624.28120.48523.stgit@dexter.citi.umich.edu","threadId":"1782","inReplyTo":"20050912145543.28120.7086.stgit@dexter.citi.umich.edu","subject":"[PATCH 19/22] teach ls-files.c to use cache_find_name()","fromName":"Chuck Lever","fromEmail":"cel@netapp.com","sentAt":"2005-09-12T14:56:25Z","receivedAt":"2005-09-12T14:56:25Z","isPatch":true,"sender":{"key":"cel@netapp.com","avatar":null},"body":"Signed-off-by: Chuck Lever \n---\n\n ls-files.c | 30 ++++++++++++++----------------\n 1 files changed, 14 insertions(+), 16 deletions(-)\n\ndiff --git a/ls-files.c b/ls-files.c\n--- a/ls-files.c\n+++ b/ls-files.c\n@@ -216,7 +216,7 @@ static void add_name(const char *pathnam\n {\n \tstruct nond_on_fs *ent;\n \n-\tif (cache_name_pos(pathname, len) >= 0)\n+\tif (cache_find_entry(pathname, len, NULL))\n \t\treturn;\n \n \tif (nr_dir == dir_alloc) {\n@@ -349,36 +349,34 @@ static void show_killed_files(void)\n \tfor (i = 0; i < nr_dir; i++) {\n \t\tstruct nond_on_fs *ent = dir[i];\n \t\tchar *cp, *sp;\n-\t\tint pos, len, killed = 0;\n+\t\tint killed = 0;\n \n \t\tfor (cp = ent->name; cp - ent->name < ent->len; cp = sp + 1) {\n \t\t\tsp = strchr(cp, '/');\n \t\t\tif (!sp) {\n+\t\t\t\tstruct cache_cursor cc;\n+\t\t\t\tstruct cache_entry *ce;\n \t\t\t\t/* If ent->name is prefix of an entry in the\n \t\t\t\t * cache, it will be killed.\n \t\t\t\t */\n-\t\t\t\tpos = cache_name_pos(ent->name, ent->len);\n-\t\t\t\tif (0 <= pos)\n+\t\t\t\tif (cache_find_name(ent->name, ent->len, &cc))\n \t\t\t\t\tdie(\"bug in show-killed-files\");\n-\t\t\t\tpos = -pos - 1;\n-\t\t\t\twhile (pos < active_nr &&\n-\t\t\t\t ce_stage(active_cache[pos]))\n-\t\t\t\t\tpos++; /* skip unmerged */\n-\t\t\t\tif (active_nr <= pos)\n+\t\t\t\twhile (!cache_eof(&cc) && ce_stage(cc_to_ce(&cc)))\n+\t\t\t\t\tnext_cc(&cc); /* skip unmerged */\n+\t\t\t\tif (cache_eof(&cc))\n \t\t\t\t\tbreak;\n-\t\t\t\t/* pos points at a name immediately after\n+\t\t\t\t/* cc points at a name immediately after\n \t\t\t\t * ent->name in the cache. Does it expect\n \t\t\t\t * ent->name to be a directory?\n \t\t\t\t */\n-\t\t\t\tlen = ce_namelen(active_cache[pos]);\n-\t\t\t\tif ((ent->len < len) &&\n-\t\t\t\t !strncmp(active_cache[pos]->name,\n-\t\t\t\t\t ent->name, ent->len) &&\n-\t\t\t\t active_cache[pos]->name[ent->len] == '/')\n+\t\t\t\tce = cc_to_ce(&cc);\n+\t\t\t\tif ((ent->len < ce_namelen(ce)) &&\n+\t\t\t\t !strncmp(ce->name, ent->name, ent->len) &&\n+\t\t\t\t ce->name[ent->len] == '/')\n \t\t\t\t\tkilled = 1;\n \t\t\t\tbreak;\n \t\t\t}\n-\t\t\tif (0 <= cache_name_pos(ent->name, sp - ent->name)) {\n+\t\t\tif (cache_find_entry(ent->name, sp - ent->name, NULL)) {\n \t\t\t\t/* If any of the leading directories in\n \t\t\t\t * ent->name is registered in the cache,\n \t\t\t\t * ent->name will be killed.\n"},{"id":"8396","messageId":"20050912145627.28120.80905.stgit@dexter.citi.umich.edu","threadId":"1782","inReplyTo":"20050912145543.28120.7086.stgit@dexter.citi.umich.edu","subject":"[PATCH 20/22] teach merge-index.c to use cache_find_name()","fromName":"Chuck Lever","fromEmail":"cel@netapp.com","sentAt":"2005-09-12T14:56:27Z","receivedAt":"2005-09-12T14:56:27Z","isPatch":true,"sender":{"key":"cel@netapp.com","avatar":null},"body":"Signed-off-by: Chuck Lever \n---\n\n merge-index.c | 44 +++++++++++++++++++++-----------------------\n 1 files changed, 21 insertions(+), 23 deletions(-)\n\ndiff --git a/merge-index.c b/merge-index.c\n--- a/merge-index.c\n+++ b/merge-index.c\n@@ -37,11 +37,11 @@ static void run_program(void)\n \t}\n }\n \n-static int merge_entry(int pos, const char *path)\n+static void merge_entry(struct cache_cursor *cc, const char *path)\n {\n \tint found;\n \t\n-\tif (pos >= active_nr)\n+\tif (cache_eof(cc))\n \t\tdie(\"git-merge-index: %s not in the cache\", path);\n \targuments[0] = pgm;\n \targuments[1] = \"\";\n@@ -55,7 +55,7 @@ static int merge_entry(int pos, const ch\n \tdo {\n \t\tstatic char hexbuf[4][60];\n \t\tstatic char ownbuf[4][60];\n-\t\tstruct cache_entry *ce = active_cache[pos];\n+\t\tstruct cache_entry *ce = cc_to_ce(cc);\n \t\tint stage = ce_stage(ce);\n \n \t\tif (strcmp(ce->name, path))\n@@ -65,34 +65,31 @@ static int merge_entry(int pos, const ch\n \t\tsprintf(ownbuf[stage], \"%o\", ntohl(ce->ce_mode) & (~S_IFMT));\n \t\targuments[stage] = hexbuf[stage];\n \t\targuments[stage + 4] = ownbuf[stage];\n-\t} while (++pos < active_nr);\n+\t\tnext_cc(cc);\n+\t} while (!cache_eof(cc));\n \tif (!found)\n \t\tdie(\"git-merge-index: %s not in the cache\", path);\n \trun_program();\n-\treturn found;\n }\n \n+/*\n+ * If it already exists in the cache as stage0, it's\n+ * already merged and there is nothing to do.\n+ */\n static void merge_file(const char *path)\n {\n-\tint pos = cache_name_pos(path, strlen(path));\n-\n-\t/*\n-\t * If it already exists in the cache as stage0, it's\n-\t * already merged and there is nothing to do.\n-\t */\n-\tif (pos < 0)\n-\t\tmerge_entry(-pos-1, path);\n+\tstruct cache_cursor cc;\n+\tif (!cache_find_name(path, strlen(path), &cc))\n+\t\tmerge_entry(&cc, path);\n }\n \n-static void merge_all(void)\n+static int merge_one(struct cache_cursor *cc, struct cache_entry *ce)\n {\n-\tint i;\n-\tfor (i = 0; i < active_nr; i++) {\n-\t\tstruct cache_entry *ce = active_cache[i];\n-\t\tif (!ce_stage(ce))\n-\t\t\tcontinue;\n-\t\ti += merge_entry(i, ce->name)-1;\n-\t}\n+\tif (ce_stage(ce))\n+\t\tmerge_entry(cc, ce->name);\n+\telse\n+\t\tnext_cc(cc);\n+\treturn 0;\n }\n \n int main(int argc, char **argv)\n@@ -102,7 +99,8 @@ int main(int argc, char **argv)\n \tif (argc < 3)\n \t\tusage(\"git-merge-index [-o] [-q] (-a | *)\");\n \n-\tread_cache();\n+\tif (read_cache() < 0)\n+\t\tdie(\"unable to read index file\");\n \n \ti = 1;\n \tif (!strcmp(argv[i], \"-o\")) {\n@@ -122,7 +120,7 @@ int main(int argc, char **argv)\n \t\t\t\tcontinue;\n \t\t\t}\n \t\t\tif (!strcmp(arg, \"-a\")) {\n-\t\t\t\tmerge_all();\n+\t\t\t\twalk_cache(merge_one);\n \t\t\t\tcontinue;\n \t\t\t}\n \t\t\tdie(\"git-merge-index: unknown option %s\", arg);\n"},{"id":"8377","messageId":"20050912145629.28120.70337.stgit@dexter.citi.umich.edu","threadId":"1782","inReplyTo":"20050912145543.28120.7086.stgit@dexter.citi.umich.edu","subject":"[PATCH 21/22] teach the merge algorithm about cache iterators","fromName":"Chuck Lever","fromEmail":"cel@netapp.com","sentAt":"2005-09-12T14:56:29Z","receivedAt":"2005-09-12T14:56:29Z","isPatch":true,"sender":{"key":"cel@netapp.com","avatar":null},"body":"For now, we simply replace indpos with a cache cursor. Likely more\nchanges will be needed after we successfully replace the cache array\nwith an abstract data type.\n\nSigned-off-by: Chuck Lever \n---\n\n read-tree.c | 23 ++++++++++++++---------\n 1 files changed, 14 insertions(+), 9 deletions(-)\n\ndiff --git a/read-tree.c b/read-tree.c\n--- a/read-tree.c\n+++ b/read-tree.c\n@@ -50,7 +50,8 @@ static int entcmp(char *name1, int dir1,\n }\n \n static int unpack_trees_rec(struct tree_entry_list **posns, int len,\n-\t\t\t const char *base, merge_fn_t fn, int *indpos)\n+\t\t\t const char *base, merge_fn_t fn,\n+\t\t\t struct cache_cursor *cc)\n {\n \tint baselen = strlen(base);\n \tint src_size = len + 1;\n@@ -73,7 +74,7 @@ static int unpack_trees_rec(struct tree_\n \t\tcache_name = NULL;\n \n \t\t/* Check the cache */\n-\t\tif (merge && *indpos < active_nr) {\n+\t\tif (merge && !cache_eof(cc)) {\n \t\t\t/* This is a bit tricky: */\n \t\t\t/* If the index has a subdirectory (with\n \t\t\t * contents) as the first name, it'll get a\n@@ -91,7 +92,7 @@ static int unpack_trees_rec(struct tree_\n \t\t\t * file case.\n \t\t\t */\n \n-\t\t\tcache_name = active_cache[*indpos]->name;\n+\t\t\tcache_name = cc_to_ce(cc)->name;\n \t\t\tif (strlen(cache_name) > baselen &&\n \t\t\t !memcmp(cache_name, base, baselen)) {\n \t\t\t\tcache_name += baselen;\n@@ -133,8 +134,8 @@ static int unpack_trees_rec(struct tree_\n \n \t\tif (cache_name && !strcmp(cache_name, first)) {\n \t\t\tany_files = 1;\n-\t\t\tsrc[0] = active_cache[*indpos];\n-\t\t\tremove_cache_entry_at(*indpos);\n+\t\t\tsrc[0] = cc_to_ce(cc);\n+\t\t\tremove_cache_entry_at(cc->pos);\n \t\t}\n \n \t\tfor (i = 0; i < len; i++) {\n@@ -203,7 +204,8 @@ static int unpack_trees_rec(struct tree_\n #if DBRT_DEBUG > 1\n \t\t\t\tprintf(\"Added %d entries\\n\", ret);\n #endif\n-\t\t\t\t*indpos += ret;\n+\t\t\t\twhile (ret--)\n+\t\t\t\t\tnext_cc(cc);\n \t\t\t} else {\n \t\t\t\tfor (i = 0; i < src_size; i++) {\n \t\t\t\t\tif (src[i]) {\n@@ -219,7 +221,7 @@ static int unpack_trees_rec(struct tree_\n \t\t\tnewbase[baselen + pathlen] = '/';\n \t\t\tnewbase[baselen + pathlen + 1] = '\\0';\n \t\t\tif (unpack_trees_rec(subposns, len, newbase, fn,\n-\t\t\t\t\t indpos))\n+\t\t\t\t\t cc))\n \t\t\t\treturn -1;\n \t\t}\n \t\tfree(subposns);\n@@ -261,18 +263,21 @@ out:\n \n static int unpack_trees(merge_fn_t fn)\n {\n-\tint indpos = 0;\n+\tstruct cache_cursor cc;\n \tunsigned len = object_list_length(trees);\n \tstruct tree_entry_list **posns = \n \t\txmalloc(len * sizeof(struct tree_entry_list *));\n \tint i;\n \tstruct object_list *posn = trees;\n+\n \tmerge_size = len;\n \tfor (i = 0; i < len; i++) {\n \t\tposns[i] = ((struct tree *) posn->item)->entries;\n \t\tposn = posn->next;\n \t}\n-\tif (unpack_trees_rec(posns, len, \"\", fn, &indpos))\n+\n+\tinit_cc(&cc);\n+\tif (unpack_trees_rec(posns, len, \"\", fn, &cc))\n \t\treturn -1;\n \n \twalk_cache(check_one_out);\n"},{"id":"8392","messageId":"20050912145631.28120.70807.stgit@dexter.citi.umich.edu","threadId":"1782","inReplyTo":"20050912145543.28120.7086.stgit@dexter.citi.umich.edu","subject":"[PATCH 22/22] teach read-cache.c to use cache_find_name()","fromName":"Chuck Lever","fromEmail":"cel@netapp.com","sentAt":"2005-09-12T14:56:31Z","receivedAt":"2005-09-12T14:56:31Z","isPatch":true,"sender":{"key":"cel@netapp.com","avatar":null},"body":"Fix up the functions in read-cache.c to use cache cursors and\ncache_find_name(). As a bonus, cache_name_pos() is no longer\nneeded.\n\nWe've now replaced all logic that depends on a negative result\nfrom cache_name_pos to detect cache insertion points.\n\nSigned-off-by: Chuck Lever \n---\n\n cache.h | 3 -\n read-cache.c | 118 ++++++++++++++++++++++++----------------------------------\n read-tree.c | 2 -\n 3 files changed, 51 insertions(+), 72 deletions(-)\n\ndiff --git a/cache.h b/cache.h\n--- a/cache.h\n+++ b/cache.h\n@@ -159,14 +159,13 @@ extern char *prefix_path(const char *pre\n extern int read_cache(void);\n extern int read_cache_unmerged(void);\n extern int write_cache(int newfd);\n-extern int cache_name_pos(const char *name, int namelen);\n extern int cache_find_name(const char *name, int namelen, struct cache_cursor *cc);\n \n #define ADD_CACHE_OK_TO_ADD 1\t\t/* Ok to add */\n #define ADD_CACHE_OK_TO_REPLACE 2\t/* Ok to replace file/directory */\n #define ADD_CACHE_SKIP_DFCHECK 4\t/* Ok to skip DF conflict checks */\n extern int add_cache_entry(struct cache_entry *ce, int option);\n-extern int remove_cache_entry_at(int pos);\n+extern int remove_cache_entry_at(struct cache_cursor *cc);\n extern int remove_file_from_cache(char *path);\n extern void prune_cache(const char *prefix, int prefix_len);\n extern int ce_same_name(struct cache_entry *a, struct cache_entry *b);\ndiff --git a/read-cache.c b/read-cache.c\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -123,27 +123,6 @@ int cache_name_compare(const char *name1\n \treturn 0;\n }\n \n-int cache_name_pos(const char *name, int namelen)\n-{\n-\tint first, last;\n-\n-\tfirst = 0;\n-\tlast = active_nr;\n-\twhile (last > first) {\n-\t\tint next = (last + first) >> 1;\n-\t\tstruct cache_entry *ce = active_cache[next];\n-\t\tint cmp = cache_name_compare(name, namelen, ce->name, ntohs(ce->ce_flags));\n-\t\tif (!cmp)\n-\t\t\treturn next;\n-\t\tif (cmp < 0) {\n-\t\t\tlast = next;\n-\t\t\tcontinue;\n-\t\t}\n-\t\tfirst = next+1;\n-\t}\n-\treturn -first-1;\n-}\n-\n /*\n * Given a name, find the first cache entry that matches. Returning 1\n * means the cursor points to the cache entry with a matching name.\n@@ -189,11 +168,13 @@ int cache_find_name(const char *name, in\n }\n \n /* Remove entry, return true if there are more entries to go.. */\n-int remove_cache_entry_at(int pos)\n+int remove_cache_entry_at(struct cache_cursor *cc)\n {\n+\tint pos = cc->pos;\n+\n \tactive_cache_changed = 1;\n \tactive_nr--;\n-\tif (pos >= active_nr)\n+\tif (cache_eof(cc))\n \t\treturn 0;\n \tmemmove(active_cache + pos, active_cache + pos + 1, (active_nr - pos) * sizeof(struct cache_entry *));\n \treturn 1;\n@@ -201,11 +182,11 @@ int remove_cache_entry_at(int pos)\n \n int remove_file_from_cache(char *path)\n {\n-\tint pos = cache_name_pos(path, strlen(path));\n-\tif (pos < 0)\n-\t\tpos = -pos-1;\n-\twhile (pos < active_nr && !strcmp(active_cache[pos]->name, path))\n-\t\tremove_cache_entry_at(pos);\n+\tstruct cache_cursor cc;\n+\n+\tcache_find_name(path, strlen(path), &cc);\n+\twhile (!cache_eof(&cc) && !strcmp(cc_to_ce(&cc)->name, path))\n+\t\tremove_cache_entry_at(&cc);\n \treturn 0;\n }\n \n@@ -214,13 +195,12 @@ int remove_file_from_cache(char *path)\n */\n void prune_cache(const char *prefix, int prefix_len)\n {\n-\tint pos = cache_name_pos(prefix, prefix_len);\n+\tstruct cache_cursor cc;\n \tunsigned int first, last;\n \n-\tif (pos < 0)\n-\t\tpos = -pos-1;\n-\tactive_cache += pos;\n-\tactive_nr -= pos;\n+\tcache_find_name(prefix, prefix_len, &cc);\n+\tactive_cache += cc.pos;\n+\tactive_nr -= cc.pos;\n \tfirst = 0;\n \tlast = active_nr;\n \twhile (last > first) {\n@@ -237,7 +217,8 @@ void prune_cache(const char *prefix, int\n \n int ce_same_name(struct cache_entry *a, struct cache_entry *b)\n {\n-\tint len = ce_namelen(a);\n+\tint len;\n+\tlen = ce_namelen(a);\n \treturn ce_namelen(b) == len && !memcmp(a->name, b->name, len);\n }\n \n@@ -271,28 +252,30 @@ int ce_path_match(const struct cache_ent\n * Do we have another file that has the beginning components being a\n * proper superset of the name we're trying to add?\n */\n-static int has_file_name(const struct cache_entry *ce, int pos, int ok_to_replace)\n+static int has_file_name(const struct cache_entry *ce, struct cache_cursor *cc, int ok_to_replace)\n {\n \tint retval = 0;\n \tint len = ce_namelen(ce);\n \tint stage = ce_stage(ce);\n \tconst char *name = ce->name;\n \n-\twhile (pos < active_nr) {\n-\t\tstruct cache_entry *p = active_cache[pos++];\n+\twhile (!cache_eof(cc)) {\n+\t\tstruct cache_entry *p = cc_to_ce(cc);\n \n \t\tif (len >= ce_namelen(p))\n \t\t\tbreak;\n \t\tif (memcmp(name, p->name, len))\n \t\t\tbreak;\n \t\tif (ce_stage(p) != stage)\n-\t\t\tcontinue;\n+\t\t\tgoto next;\n \t\tif (p->name[len] != '/')\n-\t\t\tcontinue;\n+\t\t\tgoto next;\n \t\tretval = -1;\n \t\tif (!ok_to_replace)\n \t\t\tbreak;\n-\t\tremove_cache_entry_at(--pos);\n+\t\tremove_cache_entry_at(cc);\n+next:\n+\t\tnext_cc(cc);\n \t}\n \treturn retval;\n }\n@@ -301,8 +284,9 @@ static int has_file_name(const struct ca\n * Do we have another file with a pathname that is a proper\n * subset of the name we're trying to add?\n */\n-static int has_dir_name(const struct cache_entry *ce, int pos, int ok_to_replace)\n+static int has_dir_name(const struct cache_entry *ce, int ok_to_replace)\n {\n+\tstruct cache_cursor cc;\n \tint retval = 0;\n \tint stage = ce_stage(ce);\n \tconst char *name = ce->name;\n@@ -319,12 +303,11 @@ static int has_dir_name(const struct cac\n \t\t}\n \t\tlen = slash - name;\n \n-\t\tpos = cache_name_pos(name, ntohs(create_ce_flags(len, stage)));\n-\t\tif (pos >= 0) {\n+\t\tif (cache_find_name(name, ntohs(create_ce_flags(len, stage)), &cc)) {\n \t\t\tretval = -1;\n \t\t\tif (ok_to_replace)\n \t\t\t\tbreak;\n-\t\t\tremove_cache_entry_at(pos);\n+\t\t\tremove_cache_entry_at(&cc);\n \t\t\tcontinue;\n \t\t}\n \n@@ -333,9 +316,8 @@ static int has_dir_name(const struct cac\n \t\t * already matches the sub-directory, then we know\n \t\t * we're ok, and we can exit.\n \t\t */\n-\t\tpos = -pos-1;\n-\t\twhile (pos < active_nr) {\n-\t\t\tstruct cache_entry *p = active_cache[pos];\n+\t\twhile (!cache_eof(&cc)) {\n+\t\t\tstruct cache_entry *p = cc_to_ce(&cc);\n \t\t\tif ((ce_namelen(p) <= len) ||\n \t\t\t (p->name[len] != '/') ||\n \t\t\t memcmp(p->name, name, len))\n@@ -347,7 +329,7 @@ static int has_dir_name(const struct cac\n \t\t\t\t * level or anything shorter.\n \t\t\t\t */\n \t\t\t\treturn retval;\n-\t\t\tpos++;\n+\t\t\tnext_cc(&cc);\n \t\t}\n \t}\n \treturn retval;\n@@ -362,45 +344,41 @@ static int has_dir_name(const struct cac\n * from the cache so the caller should recompute the insert position.\n * When this happens, we return non-zero.\n */\n-static int check_file_directory_conflict(const struct cache_entry *ce, int pos, int ok_to_replace)\n+static int check_file_directory_conflict(const struct cache_entry *ce, struct cache_cursor *cc, int ok_to_replace)\n {\n+\tstruct cache_cursor cd = *cc;\n \t/*\n \t * We check if the path is a sub-path of a subsequent pathname\n \t * first, since removing those will not change the position\n \t * in the array\n \t */\n-\tint retval = has_file_name(ce, pos, ok_to_replace);\n+\tint retval = has_file_name(ce, &cd, ok_to_replace);\n \t/*\n \t * Then check if the path might have a clashing sub-directory\n \t * before it.\n \t */\n-\treturn retval + has_dir_name(ce, pos, ok_to_replace);\n+\treturn retval + has_dir_name(ce, ok_to_replace);\n }\n \n int add_cache_entry(struct cache_entry *ce, int option)\n {\n-\tint pos;\n+\tstruct cache_cursor cc;\n \tint ok_to_add = option & ADD_CACHE_OK_TO_ADD;\n \tint ok_to_replace = option & ADD_CACHE_OK_TO_REPLACE;\n \tint skip_df_check = option & ADD_CACHE_SKIP_DFCHECK;\n-\tpos = cache_name_pos(ce->name, ntohs(ce->ce_flags));\n \n \t/* existing match? Just replace it */\n-\tif (pos >= 0) {\n-\t\tactive_cache_changed = 1;\n-\t\tactive_cache[pos] = ce;\n-\t\treturn 0;\n-\t}\n-\tpos = -pos-1;\n+\tif (cache_find_name(ce->name, ntohs(ce->ce_flags), &cc))\n+\t\tgoto out;\n \n \t/*\n \t * Inserting a merged entry (\"stage 0\") into the index\n \t * will always replace all non-merged entries..\n \t */\n-\tif (pos < active_nr && ce_stage(ce) == 0) {\n-\t\twhile (ce_same_name(active_cache[pos], ce)) {\n+\tif (!cache_eof(&cc) && ce_stage(ce) == 0) {\n+\t\twhile (ce_same_name(cc_to_ce(&cc), ce)) {\n \t\t\tok_to_add = 1;\n-\t\t\tif (!remove_cache_entry_at(pos))\n+\t\t\tif (!remove_cache_entry_at(&cc))\n \t\t\t\tbreak;\n \t\t}\n \t}\n@@ -408,11 +386,10 @@ int add_cache_entry(struct cache_entry *\n \tif (!ok_to_add)\n \t\treturn -1;\n \n-\tif (!skip_df_check && check_file_directory_conflict(ce, pos, ok_to_replace)) {\n+\tif (!skip_df_check && check_file_directory_conflict(ce, &cc, ok_to_replace)) {\n \t\tif (!ok_to_replace)\n \t\t\treturn -1;\n-\t\tpos = cache_name_pos(ce->name, ntohs(ce->ce_flags));\n-\t\tpos = -pos-1;\n+\t\tcache_find_name(ce->name, ntohs(ce->ce_flags), &cc);\n \t}\n \n \t/* Make sure the array is big enough .. */\n@@ -423,10 +400,13 @@ int add_cache_entry(struct cache_entry *\n \n \t/* Add it in.. */\n \tactive_nr++;\n-\tif (active_nr > pos)\n+\tif (!cache_eof(&cc)) {\n+\t\tint pos = cc.pos;\n \t\tmemmove(active_cache + pos + 1, active_cache + pos, (active_nr - pos - 1) * sizeof(ce));\n-\tactive_cache[pos] = ce;\n-\tactive_cache_changed = 1;\n+\t}\n+\n+out:\n+\tset_ce_at_cursor(&cc, ce);\n \treturn 0;\n }\n \n@@ -456,7 +436,7 @@ int read_cache(void)\n \tstruct cache_header *hdr;\n \n \terrno = EBUSY;\n-\tif (active_cache)\n+\tif (!read_cache_needed())\n \t\treturn error(\"more than one cachefile\");\n \terrno = ENOENT;\n \tfd = open(get_index_file(), O_RDONLY);\ndiff --git a/read-tree.c b/read-tree.c\n--- a/read-tree.c\n+++ b/read-tree.c\n@@ -135,7 +135,7 @@ static int unpack_trees_rec(struct tree_\n \t\tif (cache_name && !strcmp(cache_name, first)) {\n \t\t\tany_files = 1;\n \t\t\tsrc[0] = cc_to_ce(cc);\n-\t\t\tremove_cache_entry_at(cc->pos);\n+\t\t\tremove_cache_entry_at(cc);\n \t\t}\n \n \t\tfor (i = 0; i < len; i++) {\n"},{"id":"8400","messageId":"4325A0D9.2000806@gmail.com","threadId":"1782","inReplyTo":"20050912145543.28120.7086.stgit@dexter.citi.umich.edu","subject":"Re: [PATCH 00/22] cache cursors: an introduction","fromName":"A Large Angry SCM","fromEmail":"gitzilla@gmail.com","sentAt":"2005-09-12T15:38:01Z","receivedAt":"2005-09-12T15:38:01Z","isPatch":true,"sender":{"key":"gitzilla@gmail.com","avatar":"https://gravatar.com/avatar/354625c442439908ff3dd99757dee330e29e9df7847472384faf7a00add247fb?d=mp&s=160"},"body":"Chuck Lever wrote:\n> [ This series is posted for review and comments. ]\n> \n> The following patch series introduces an abstraction called a \"cache\n> cursor\" that will eventually allow us to replace the current\n> active_cache array with something else.\n> \n> A cache cursor represents a position inside the cache. This position\n> has a cache_entry associated with it, of course, but since the cache\n> is ordered, a cache cursor also has the concept of next, previous,\n> and end-of-cache.\n> \n> With a cache cursor we can build a simple iterator mechanism that\n> calls a particular function for every entry in the cache, in order.\n> This allows us to hide further the specifics of the active cache\n> implementation -- the function gets to see the cache cursor and\n> an element, but does not have direct access to the cache and cannot\n> assume it has a particular structure.\n> \n> Currently the cache cursor type is just a structure with an integer\n> in it, so it largely mimics the existing implementation.\n> \n> This patch series is against the \"proposed updates\" branch, as of\n> a couple of days ago. It has been tested via \"make test\" and I'm\n> currently using it for my own work without issue.\n\nI'll let others comment on the need for this type of facility and it's \nproposed implementation.\n\nSince you are proposing an API, some basic documentation about how to \nuse the API would be nice. Comments in cache.h seems the best place, for \nnow.\n\nThe sentence \"This patch series is against the \"proposed updates\" \nbranch, as of a couple of days ago.\" should have also included a commit \nID. That way we would know where/when the patches would apply cleanly \nfor testing and dissection.\n"},{"id":"8402","messageId":"4325AED6.8050401@citi.umich.edu","threadId":"1782","inReplyTo":"4325A0D9.2000806@gmail.com","subject":"Re: [PATCH 00/22] cache cursors: an introduction","fromName":"Chuck Lever","fromEmail":"cel@citi.umich.edu","sentAt":"2005-09-12T16:37:42Z","receivedAt":"2005-09-12T16:37:42Z","isPatch":true,"sender":{"key":"cel@citi.umich.edu","avatar":null},"body":"A Large Angry SCM wrote:\n> Since you are proposing an API, some basic documentation about how to \n> use the API would be nice. Comments in cache.h seems the best place, for \n> now.\n\nactually it might be best to have a list discussion first. if i can \nanswer questions and provide a few explanations here, the list archive \nmight be a reasonable resting place for documentation.\n\nthe API is fairly simple and is documented via the function names. \nthere isn't a whole lot of function-level documentation in the git code \nbase that i have seen, so i erred on the side of less is more.\n\nthe first patch \"introduce-cache-cursors provides most of the interface, \nand the subsequent patches demonstrate how to use it by changing parts \nof the git C code base to use the interface instead.\n\nthe main pieces are:\n\n+ struct cache_cursor\n\nwhich describes a position in the cache.\n\n+ init_cc\n\nwhich sets the given cursor to the top of the cache.\n\n+ cc_to_ce\n\nwhich extracts the cache entry that a cursor refers to.\n\n+ next_cc, prev_cc, cache_eof\n\nwhich allow cursor movement.\n\n+ next_name\n\nwhich skips to the next unique name in the cache.\n\n+ walk_cache\n\nwhich calls a function for each entry in the cache, in order. the given \nfunction is responsible for moving the cursor to the next position \nbefore returning.\n\n+ cache_find_name\n\nwhich returns a cache cursor pointing to the found entry or to the entry \nwhich can be used as an insertion point if nothing matches.\n\n+ cache_find_entry\n\nwhich is a wrapper around cache_find_name that returns an entry instead \nof a position.\n\n> The sentence \"This patch series is against the \"proposed updates\" \n> branch, as of a couple of days ago.\" should have also included a commit \n> ID. That way we would know where/when the patches would apply cleanly \n> for testing and dissection.\n\ni'm a dork.\n\n6ae3d6e6d0f87cfa75b4bf213a485ff687defce8\n\ni will include the base ref in my future postings.\n\n\nbegin:vcard\nfn:Chuck Lever\nn:Lever;Charles\norg:Network Appliance, Incorporated;Linux NFS Client Development\nadr:535 West William Street, Suite 3100;;Center for Information Technology Integration;Ann Arbor;MI;48103-4943;USA\nemail;internet:cel@citi.umich.edu\ntitle:Member of Technical Staff\ntel;work:+1 734 763 4415\ntel;fax:+1 734 763 4434\ntel;home:+1 734 668 1089\nx-mozilla-html:FALSE\nurl:http://www.monkey.org/~cel/\nversion:2.1\nend:vcard\n\n"},{"id":"8413","messageId":"7vaciiawrm.fsf@assigned-by-dhcp.cox.net","threadId":"1782","inReplyTo":"20050912145543.28120.7086.stgit@dexter.citi.umich.edu","subject":"Re: [PATCH 00/22] cache cursors: an introduction","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-12T19:53:01Z","receivedAt":"2005-09-12T19:53:01Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"I've only skimmed the surface of your patchset and cannot\ncomment on the correctness of all the conversion of active_cache\nusers; today is my day-job day not a GIT day.\n\nI have to say you did quite a lot of work, and I am pleasantly\nsurprised to see the massive clean-up this change brings us. It\nseems like this makes the active_cache users a lot easier to\nread.\n\nI have a couple of comments on the API, though.\n\n* Doesn't function to be applied usually want to have its own\n data when passed to walk, maybe something like this?\n\n typedef int (*cache_iterator_fn_t) (struct cache_cursor *cc,\n\t\t\t struct cache_entry *ce, void *udata);\n static inline int walk_cache(cache_iterator_fn_t func, void *udata)\n {\n struct cache_cursor cc;\n\n init_cc(&cc);\n while (!cache_eof(&cc)) {\n int status = func(&cc, cc_to_ce(&cc), udata);\n if (status < 0)\n return status;\n }\n return 0;\n }\n\n This was a question I had when I read [PATCH 01/22] before\n reading the rest of the patches, but the actual conversion\n does not seem to find much need for it. A new global variable\n pathspec is introduced to pass information the API is unable\n to pass to diff_one() in diff-index.c, which may be a sign\n that an extra \"user data\" parameter might help. Your call.\n\n* It may make sense to give another param to describe which\n cache the caller is talking about so that we can later have\n more than one cache at the same time:\n\n struct cache {\n struct cache_entry **cache_array;\n unsigned int nr;\n unsigned int alloc;\n unsigned int cache_changed;\n };\n struct cache active_cache;\n\n and use it like this:\n\n static inline struct cache_entry *cc_to_ce(struct cache_cursor *cc,\n struct cache *cache)\n {\n return cache->cache_array[cc->pos];\n }\n\n We could argue that this should be left for later rounds. On\n the other hand, we will be changing all the cc_* function call\n sites during that round, which is by definition the places you\n are touching in this round anyway. Also I suspect that the\n \"later job\" is made larger if we do something like this during\n this round:\n\n diff --git a/cache.h b/cache.h\n --- a/cache.h\n +++ b/cache.h\n @@ -157,7 +157,7 @@ extern char *prefix_path(const char *pre\n\n /* Initialize and use the cache information */\n extern int read_cache(void);\n -extern int write_cache(int newfd, struct cache_entry **cache, int entries);\n +extern int write_cache(int newfd);\n extern int cache_name_pos(const char *name, int namelen);\n #define ADD_CACHE_OK_TO_ADD 1\t\t/* Ok to add */\n #define ADD_CACHE_OK_TO_REPLACE 2\t/* Ok to replace file/directory */\n\n This function could already act on more than one active_cache,\n although nobody uses it like that.\n"},{"id":"8416","messageId":"Pine.LNX.4.63.0509121614140.23242@iabervon.org","threadId":"1782","inReplyTo":"7vaciiawrm.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 00/22] cache cursors: an introduction","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-09-12T20:22:44Z","receivedAt":"2005-09-12T20:22:44Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Mon, 12 Sep 2005, Junio C Hamano wrote:\n\n> I've only skimmed the surface of your patchset and cannot\n> comment on the correctness of all the conversion of active_cache\n> users; today is my day-job day not a GIT day.\n> \n> I have to say you did quite a lot of work, and I am pleasantly\n> surprised to see the massive clean-up this change brings us. It\n> seems like this makes the active_cache users a lot easier to\n> read.\n> \n> I have a couple of comments on the API, though.\n> \n> * Doesn't function to be applied usually want to have its own\n> data when passed to walk, maybe something like this?\n> \n> This was a question I had when I read [PATCH 01/22] before\n> reading the rest of the patches, but the actual conversion\n> does not seem to find much need for it. A new global variable\n> pathspec is introduced to pass information the API is unable\n> to pass to diff_one() in diff-index.c, which may be a sign\n> that an extra \"user data\" parameter might help. Your call.\n\nI agree that it only works for the current conversion, due to there only \nbeing a limited amount you might try to do in a single git executable \ncurrently. Long-term, that should be fixed.\n\n> * It may make sense to give another param to describe which\n> cache the caller is talking about so that we can later have\n> more than one cache at the same time:\n> \n> We could argue that this should be left for later rounds. On\n> the other hand, we will be changing all the cc_* function call\n> sites during that round, which is by definition the places you\n> are touching in this round anyway. \n\nWouldn't it be better to only take it in cc_init(), and have the cursor \nremember what it's iterating through?\n\nI'm actually particularly interested in having a pair of caches for \nread-tree, because it would actually like to keep the old index separate \nfrom the index it's building.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"8418","messageId":"Pine.LNX.4.63.0509121622520.23242@iabervon.org","threadId":"1782","inReplyTo":"4325AED6.8050401@citi.umich.edu","subject":"Re: [PATCH 00/22] cache cursors: an introduction","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-09-12T20:26:46Z","receivedAt":"2005-09-12T20:26:46Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Mon, 12 Sep 2005, Chuck Lever wrote:\n\n> A Large Angry SCM wrote:\n> > Since you are proposing an API, some basic documentation about how to use\n> > the API would be nice. Comments in cache.h seems the best place, for now.\n> \n> actually it might be best to have a list discussion first. if i can answer\n> questions and provide a few explanations here, the list archive might be a\n> reasonable resting place for documentation.\n> \n> the API is fairly simple and is documented via the function names. there isn't\n> a whole lot of function-level documentation in the git code base that i have\n> seen, so i erred on the side of less is more.\n> \n> the main pieces are:\n> \n> + next_name\n> \n> which skips to the next unique name in the cache.\n\nSomething with \"cc\" in it?\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"8419","messageId":"7vwtlm9ggx.fsf@assigned-by-dhcp.cox.net","threadId":"1782","inReplyTo":"Pine.LNX.4.63.0509121614140.23242@iabervon.org","subject":"Re: [PATCH 00/22] cache cursors: an introduction","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-12T20:30:22Z","receivedAt":"2005-09-12T20:30:22Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Daniel Barkalow writes:\n\n>> * It may make sense to give another param to describe which\n>> cache the caller is talking about so that we can later have\n>> more than one cache at the same time:\n>> \n> Wouldn't it be better to only take it in cc_init(), and have the cursor \n> remember what it's iterating through?\n\nYes.\n\n> I'm actually particularly interested in having a pair of caches for \n> read-tree, because it would actually like to keep the old index separate \n> from the index it's building.\n\nYes.\n"},{"id":"8420","messageId":"Pine.LNX.4.63.0509121633480.23242@iabervon.org","threadId":"1782","inReplyTo":"20050912145629.28120.70337.stgit@dexter.citi.umich.edu","subject":"Re: [PATCH 21/22] teach the merge algorithm about cache iterators","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-09-12T20:43:05Z","receivedAt":"2005-09-12T20:43:05Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Mon, 12 Sep 2005, Chuck Lever wrote:\n\n> For now, we simply replace indpos with a cache cursor. Likely more\n> changes will be needed after we successfully replace the cache array\n> with an abstract data type.\n\nThe right order is probably to add the concept of a cache that isn't the \none that normal functions deal with, have read_cache_unmerged return such \na thing, call cc_init with that, and rip out all of the removal and \nposition adjustment code. Then read_tree won't care at all about the \ninternal structure of the cache type, and it can be replaced without any \nproblem.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"8421","messageId":"7vr7bu9foh.fsf@assigned-by-dhcp.cox.net","threadId":"1782","inReplyTo":"4325AED6.8050401@citi.umich.edu","subject":"Re: [PATCH 00/22] cache cursors: an introduction","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-12T20:47:26Z","receivedAt":"2005-09-12T20:47:26Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Chuck Lever writes:\n\n>> The sentence \"This patch series is against the \"proposed updates\"\n>> branch, as of a couple of days ago.\" should have also included a\n>> commit ID. That way we would know where/when the patches would apply\n>> cleanly for testing and dissection.\n>\n> i'm a dork.\n>\n> 6ae3d6e6d0f87cfa75b4bf213a485ff687defce8\n>\n> i will include the base ref in my future postings.\n\nNo need for any of that. All the necessary bits are already in\nthe \"master\" branch.\n"},{"id":"8450","messageId":"43261675.10905@citi.umich.edu","threadId":"1782","inReplyTo":"7vaciiawrm.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 00/22] cache cursors: an introduction","fromName":"Chuck Lever","fromEmail":"cel@citi.umich.edu","sentAt":"2005-09-12T23:59:49Z","receivedAt":"2005-09-12T23:59:49Z","isPatch":true,"sender":{"key":"cel@citi.umich.edu","avatar":null},"body":"Junio C Hamano wrote:\n> I have a couple of comments on the API, though.\n> \n> * Doesn't function to be applied usually want to have its own\n> data when passed to walk, maybe something like this?\n> \n> typedef int (*cache_iterator_fn_t) (struct cache_cursor *cc,\n> \t\t\t struct cache_entry *ce, void *udata);\n> static inline int walk_cache(cache_iterator_fn_t func, void *udata)\n> {\n> struct cache_cursor cc;\n> \n> init_cc(&cc);\n> while (!cache_eof(&cc)) {\n> int status = func(&cc, cc_to_ce(&cc), udata);\n> if (status < 0)\n> return status;\n> }\n> return 0;\n> }\n> \n> This was a question I had when I read [PATCH 01/22] before\n> reading the rest of the patches, but the actual conversion\n> does not seem to find much need for it. A new global variable\n> pathspec is introduced to pass information the API is unable\n> to pass to diff_one() in diff-index.c, which may be a sign\n> that an extra \"user data\" parameter might help. Your call.\n\nheh. well, i had something like this earlier, but i know linus doesn't \nlike void *, and it was really kind of ugly. and as you observed, it's \nused so rarely. so i just decided to drop it.\n\n> * It may make sense to give another param to describe which\n> cache the caller is talking about so that we can later have\n> more than one cache at the same time:\n> \n> struct cache {\n> struct cache_entry **cache_array;\n> unsigned int nr;\n> unsigned int alloc;\n> unsigned int cache_changed;\n> };\n> struct cache active_cache;\n> \n> and use it like this:\n> \n> static inline struct cache_entry *cc_to_ce(struct cache_cursor *cc,\n> struct cache *cache)\n> {\n> return cache->cache_array[cc->pos];\n> }\n> \n> We could argue that this should be left for later rounds. On\n> the other hand, we will be changing all the cc_* function call\n> sites during that round, which is by definition the places you\n> are touching in this round anyway.\n\nactually this is simple to add now. i'll give it a shot (and fix up \nwrite_cache to use it).\n\nbtw, with daniel's changes i don't see where we're using \nactive_cache_changed any more.\n\n\nbegin:vcard\nfn:Chuck Lever\nn:Lever;Charles\norg:Network Appliance, Incorporated;Linux NFS Client Development\nadr:535 West William Street, Suite 3100;;Center for Information Technology Integration;Ann Arbor;MI;48103-4943;USA\nemail;internet:cel@citi.umich.edu\ntitle:Member of Technical Staff\ntel;work:+1 734 763-4415\ntel;fax:+1 734 763 4434\ntel;home:+1 734 668-1089\nx-mozilla-html:FALSE\nurl:http://www.monkey.org/~cel/\nversion:2.1\nend:vcard\n\n"},{"id":"8451","messageId":"4326170E.5040509@citi.umich.edu","threadId":"1782","inReplyTo":"Pine.LNX.4.63.0509121633480.23242@iabervon.org","subject":"Re: [PATCH 21/22] teach the merge algorithm about cache iterators","fromName":"Chuck Lever","fromEmail":"cel@citi.umich.edu","sentAt":"2005-09-13T00:02:22Z","receivedAt":"2005-09-13T00:02:22Z","isPatch":true,"sender":{"key":"cel@citi.umich.edu","avatar":null},"body":"Daniel Barkalow wrote:\n> On Mon, 12 Sep 2005, Chuck Lever wrote:\n>>For now, we simply replace indpos with a cache cursor. Likely more\n>>changes will be needed after we successfully replace the cache array\n>>with an abstract data type.\n> \n> The right order is probably to add the concept of a cache that isn't the \n> one that normal functions deal with, have read_cache_unmerged return such \n> a thing, call cc_init with that, and rip out all of the removal and \n> position adjustment code. Then read_tree won't care at all about the \n> internal structure of the cache type, and it can be replaced without any \n> problem.\n\nyeah, i've come to the same conclusion, and started screwing with this \nidea today.\n\n\nbegin:vcard\nfn:Chuck Lever\nn:Lever;Charles\norg:Network Appliance, Incorporated;Linux NFS Client Development\nadr:535 West William Street, Suite 3100;;Center for Information Technology Integration;Ann Arbor;MI;48103-4943;USA\nemail;internet:cel@citi.umich.edu\ntitle:Member of Technical Staff\ntel;work:+1 734 763-4415\ntel;fax:+1 734 763 4434\ntel;home:+1 734 668-1089\nx-mozilla-html:FALSE\nurl:http://www.monkey.org/~cel/\nversion:2.1\nend:vcard\n\n"},{"id":"8452","messageId":"7vd5nd6cyn.fsf@assigned-by-dhcp.cox.net","threadId":"1782","inReplyTo":"43261675.10905@citi.umich.edu","subject":"Re: [PATCH 00/22] cache cursors: an introduction","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-13T00:14:24Z","receivedAt":"2005-09-13T00:14:24Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Chuck Lever writes:\n\n> btw, with daniel's changes i don't see where we're using \n> active_cache_changed any more.\n\nThat came from an earlier botched attempt of mine to optimize\nout writing of cache (eh, index file these days it is called but\nback then it was \"cache\") when read-tree ended up not modifying\nthe cache contents (e.g. reading HEAD immediately after checking\nit out). My implementation was quite buggy and Linus fixed it\nin the ee267527aa80807f37caf1d00bcf1b5263945adb commit by adding\nthe variable while disabling the optimization for safety. And\nthe optimization has not been re-enabled ever since. I think\nyou can remove the variable now.\n"},{"id":"8453","messageId":"Pine.LNX.4.58.0509121708430.3266@g5.osdl.org","threadId":"1782","inReplyTo":"43261675.10905@citi.umich.edu","subject":"Re: [PATCH 00/22] cache cursors: an introduction","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-09-13T00:17:32Z","receivedAt":"2005-09-13T00:17:32Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 12 Sep 2005, Chuck Lever wrote:\n> \n> heh. well, i had something like this earlier, but i know linus doesn't \n> like void *, and it was really kind of ugly. and as you observed, it's \n> used so rarely. so i just decided to drop it.\n\nIterators are _much_ nicer if you can use them in-line instead of with a \nfunction pointer. It makes them a hundred times more powerful, and avoids \nall the crap with trying to pass a magic argument around.\n\nThat was why I mentioned the sparse \"ptrlist\" implementation: the data \nstructure itself may not be all that exciting, but the syntax for _using_ \nit is incredibly powerful. Much better than any other list handling \npackage I've ever seen, if I do say so myself.\n\nSo check out\n\n\tkernel.org:/pub/scm/devel/sparse/sparse.git\n\nand look at how easy it is to iterate over a list. The _true_ power is how \nyou can return out of a function in the middle of the iterator, ie\n\n\tint pseudo_in_list(struct pseudo_list *list, pseudo_t pseudo)\n\t{\n\t pseudo_t old;\n\t FOR_EACH_PTR(list,old) {\n\t if (old == pseudo)\n\t return 1;\n\t } END_FOR_EACH_PTR(old);\n\t return 0;\n\t}\n\n(and it's type-safe too!)\n\nNow, nested iterators may sound easy, but they aren't easy if you want to \nactually break out of them in a nested way. Try to do _this_ with a \nfunction pointer interface without going crazy:\n\n\t /* Remove the pseudos from the \"defines\" list that are used internally */\n\t FOR_EACH_PTR(ep->bbs, bb) {\n\t pseudo_t def;\n\t FOR_EACH_PTR(bb->defines, def) {\n\t struct basic_block *child;\n\t FOR_EACH_PTR(bb->children, child) {\n\t if (pseudo_in_list(child->needs, def))\n\t goto is_used;\n\t } END_FOR_EACH_PTR(child);\n\t DELETE_CURRENT_PTR(def);\n\tis_used:\n\t ;\n\t } END_FOR_EACH_PTR(def);\n\t PACK_PTR_LIST(&bb->defines);\n\t } END_FOR_EACH_PTR(bb);\n\nall real examples from real code that implements an almost-real compiler.\n\nVery dense code too, btw. It's incredible how expressive these iterators \nare: I started out with a function pointer interface, and it was painful \nas _hell_ to see what was going on.\n\n\t\tLinus\n"},{"id":"8475","messageId":"43272350.3060801@progeny.com","threadId":"1782","inReplyTo":"4325AED6.8050401@citi.umich.edu","subject":"Re: [PATCH 00/22] cache cursors: an introduction","fromName":"Tim Ottinger","fromEmail":"tottinge@progeny.com","sentAt":"2005-09-13T19:06:56Z","receivedAt":"2005-09-13T19:06:56Z","isPatch":true,"sender":{"key":"tottinge@progeny.com","avatar":null},"body":"I know it's a little picky, but can we be consistently noun-verb-noun \nwith these?\nI'm not meaning to be a jerk (it just happens unbidden).\n\nMy reasons\n1) My editor has word completion, which is handy.\n2) However unimportant, I'm an old OO guy and object_cmd looks like \nobject.command to me.\n3) I'm so stupid I need consistent naming to help me learn the git guts.\n4) I'm generally a butt about naming anyway \n(http://tottinge.blogsome.com/naming-rules/)\n5) I work with a guy who is a stickler for lexicon, and he revived the \npassion for consistency.\n\n> which describes a position in the cache.\n>\n> + init_cc\n\ncc_init?\n\n>\n> + next_cc, prev_cc, cache_eof\n\ncc_next, cc_previous\n\nWhich is that, cc_to_end or cc_at_end?\n\n> + next_name\n\ncc_next_name?\n\n>\n> + walk_cache\n\ncache_walk?\n\nThe rest of those looked great. I only listed the ones I was unsure about.\n\n\n-- \n ><>\n... either 'way ahead of the game, or 'way out in left field.\n"},{"id":"8476","messageId":"7vslw821jl.fsf@assigned-by-dhcp.cox.net","threadId":"1782","inReplyTo":"43272350.3060801@progeny.com","subject":"Re: [PATCH 00/22] cache cursors: an introduction","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-13T19:46:54Z","receivedAt":"2005-09-13T19:46:54Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Tim Ottinger writes:\n\n> 2) However unimportant, I'm an old OO guy and object_cmd looks like \n> object.command to me.\n\nIf you are OO then would not object_method remind you of object->method ??\n\n>> + init_cc\n>> + next_cc, prev_cc\n>\n> cc_init?\n> cc_next, cc_previous\n\nNah, either set is fine as long as it is internally consistent.\nI tend to prefer \"do-this-to-that\" so init_cc and next_cc are\nfine by me (just one person's opinion, not a dictator's ruling).\n"},{"id":"8477","messageId":"4327312D.3000208@progeny.com","threadId":"1782","inReplyTo":"7vslw821jl.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 00/22] cache cursors: an introduction","fromName":"Tim Ottinger","fromEmail":"tottinge@progeny.com","sentAt":"2005-09-13T20:06:05Z","receivedAt":"2005-09-13T20:06:05Z","isPatch":true,"sender":{"key":"tottinge@progeny.com","avatar":null},"body":"Junio C Hamano wrote:\n\n>Tim Ottinger writes:\n>\n> \n>\n>>2) However unimportant, I'm an old OO guy and object_cmd looks like \n>>object.command to me.\n>> \n>>\n>\n>If you are OO then would not object_method remind you of object->method ??\n>\n> \n>\n>>>+ init_cc\n>>>+ next_cc, prev_cc\n>>> \n>>>\n>>cc_init?\n>>cc_next, cc_previous\n>> \n>>\n>\n>Nah, either set is fine as long as it is internally consistent.\n>I tend to prefer \"do-this-to-that\" so init_cc and next_cc are\n>fine by me (just one person's opinion, not a dictator's ruling).\n>\n> \n>\nI guess it depends on whether you're looking at command completion or\nnot. Most the time I have a thing, and want to do something to it. Then\nstarting with cc_ helps, but starting with init_ only tells me what I can\ninit -- more filtering on my part.\n\nOf course, i can just open the darned file and read it. ;-) So it's a \nmatter\nof what you and your tools like best. Starting with the subject does sort\nbetter, though. \n\n\n-- \n ><>\n... either 'way ahead of the game, or 'way out in left field.\n"},{"id":"8506","messageId":"tnxu0gocats.fsf@arm.com","threadId":"1782","inReplyTo":"43272350.3060801@progeny.com","subject":"Re: [PATCH 00/22] cache cursors: an introduction","fromName":"Catalin Marinas","fromEmail":"catalin.marinas@gmail.com","sentAt":"2005-09-14T08:28:31Z","receivedAt":"2005-09-14T08:28:31Z","isPatch":true,"sender":{"key":"catalin.marinas@gmail.com","avatar":null},"body":"Tim Ottinger wrote:\n> 2) However unimportant, I'm an old OO guy and object_cmd looks like\n> object.command to me.\n\nWell, it depends on the language. If you only used LISP/CLOS, it would\nlook more like (cmd object) :-)\n\n-- \nCatalin\n"},{"id":"8521","messageId":"43283888.10909@citi.umich.edu","threadId":"1782","inReplyTo":"tnxu0gocats.fsf@arm.com","subject":"Re: [PATCH 00/22] cache cursors: an introduction","fromName":"Chuck Lever","fromEmail":"cel@citi.umich.edu","sentAt":"2005-09-14T14:49:44Z","receivedAt":"2005-09-14T14:49:44Z","isPatch":true,"sender":{"key":"cel@citi.umich.edu","avatar":null},"body":"Catalin Marinas wrote:\n> Tim Ottinger wrote:\n> \n>>2) However unimportant, I'm an old OO guy and object_cmd looks like\n>>object.command to me.\n> \n> \n> Well, it depends on the language. If you only used LISP/CLOS, it would\n> look more like (cmd object) :-)\n> \n\njust a note on function naming: i followed the pre-existing function \nnaming convention. to wit:\n\nexisting:\n\nread_cache\nwrite_cache\nadd_cache_entry\nremove_cache_entry_at\n\nnew:\n\ninit_cc\nnext_cc\nwalk_cache\n\netc.\n\n\nbegin:vcard\nfn:Chuck Lever\nn:Lever;Charles\norg:Network Appliance, Incorporated;Linux NFS Client Development\nadr:535 West William Street, Suite 3100;;Center for Information Technology Integration;Ann Arbor;MI;48103-4943;USA\nemail;internet:cel@citi.umich.edu\ntitle:Member of Technical Staff\ntel;work:+1 734 763 4415\ntel;fax:+1 734 763 4434\ntel;home:+1 734 668 1089\nx-mozilla-html:FALSE\nurl:http://www.monkey.org/~cel/\nversion:2.1\nend:vcard\n\n"},{"id":"8527","messageId":"43284368.8010004@citi.umich.edu","threadId":"1782","inReplyTo":"Pine.LNX.4.63.0509121633480.23242@iabervon.org","subject":"Re: [PATCH 21/22] teach the merge algorithm about cache iterators","fromName":"Chuck Lever","fromEmail":"cel@citi.umich.edu","sentAt":"2005-09-14T15:36:08Z","receivedAt":"2005-09-14T15:36:08Z","isPatch":true,"sender":{"key":"cel@citi.umich.edu","avatar":null},"body":"Daniel Barkalow wrote:\n> On Mon, 12 Sep 2005, Chuck Lever wrote:\n> \n> \n>>For now, we simply replace indpos with a cache cursor. Likely more\n>>changes will be needed after we successfully replace the cache array\n>>with an abstract data type.\n> \n> \n> The right order is probably to add the concept of a cache that isn't the \n> one that normal functions deal with, have read_cache_unmerged return such \n> a thing, call cc_init with that, and rip out all of the removal and \n> position adjustment code. Then read_tree won't care at all about the \n> internal structure of the cache type, and it can be replaced without any \n> problem.\n\nok, i've done this. read_cache_unmerged now reads into a separate \ncache, and read-tree.c does the merge by moving the appropriate cache \nentries into the active cache.\n\nthe linked list prototype is done, and works correctly. this validates \nthe new cache cursor API. unfortunately because finding a name is now \nO(n), many things are slower than before (but i expected this would be \nthe case for lists).\n\nthe next step is to try out more sophisticated data types. we have \nthree on the table so far:\n\n1. linus' sparse hyperlist implementation. i suspect this will have \nthe same bad performance characteristics as a standard linked list.\n\n2. self-balancing trees. a splay tree is a good example. we can \nreduce the size of the tree by storing all stages of a name in each \nnode. kernel source is about 18K files, which means we can find names \nin about 15 steps, on average.\n\n3. hash table, hashing on ce->name. similar to a Python dictionary. \nwith an 8 kilobucket hash table and a good hash function, we can store \nthe kernel source, finding names in two or three steps on average.\n\nare there others?\n\n\nbegin:vcard\nfn:Chuck Lever\nn:Lever;Charles\norg:Network Appliance, Incorporated;Linux NFS Client Development\nadr:535 West William Street, Suite 3100;;Center for Information Technology Integration;Ann Arbor;MI;48103-4943;USA\nemail;internet:cel@citi.umich.edu\ntitle:Member of Technical Staff\ntel;work:+1 734 763 4415\ntel;fax:+1 734 763 4434\ntel;home:+1 734 668 1089\nx-mozilla-html:FALSE\nurl:http://www.monkey.org/~cel/\nversion:2.1\nend:vcard\n\n"},{"id":"8534","messageId":"Pine.LNX.4.63.0509141214490.23242@iabervon.org","threadId":"1782","inReplyTo":"43284368.8010004@citi.umich.edu","subject":"Re: [PATCH 21/22] teach the merge algorithm about cache iterators","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-09-14T16:41:36Z","receivedAt":"2005-09-14T16:41:36Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Wed, 14 Sep 2005, Chuck Lever wrote:\n\n> Daniel Barkalow wrote:\n> > On Mon, 12 Sep 2005, Chuck Lever wrote:\n> > \n> > \n> > >For now, we simply replace indpos with a cache cursor. Likely more\n> > >changes will be needed after we successfully replace the cache array\n> > >with an abstract data type.\n> > \n> > \n> > The right order is probably to add the concept of a cache that isn't the one\n> > that normal functions deal with, have read_cache_unmerged return such a\n> > thing, call cc_init with that, and rip out all of the removal and position\n> > adjustment code. Then read_tree won't care at all about the internal\n> > structure of the cache type, and it can be replaced without any problem.\n> \n> ok, i've done this. read_cache_unmerged now reads into a separate cache, and\n> read-tree.c does the merge by moving the appropriate cache entries into the\n> active cache.\n> \n> the linked list prototype is done, and works correctly. this validates the\n> new cache cursor API. unfortunately because finding a name is now O(n), many\n> things are slower than before (but i expected this would be the case for\n> lists).\n\nThe really exciting thing to do would be to have different programs use \ndifferent implementations, by way of linker magic.\n\nMy guess for the ideal is to have a linked list with a hashtable for \nfinding entries by looking up names, because we don't look things up by \nindex. This combination gives O(1) in-order iteration, O(1) lookup by \nname, O(1) append, O(n) insert, and O(1) remove. This means that \ngit-update-cache --add would be slow, but everything else would be fast. \n(Except, of course, for the overhead of actually reading and writing the \nindex file, rather than mmaping it.)\n\nAnother thing to try would be the original dynamic table implementation, \nplus a hashtable for name lookups, generated the first time a lookup is \nattempted (since some programs don't do any lookups by name). This has the \nadvantage of skipping the O(n) startup.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"8540","messageId":"7vbr2vlest.fsf@assigned-by-dhcp.cox.net","threadId":"1782","inReplyTo":"Pine.LNX.4.63.0509141214490.23242@iabervon.org","subject":"Re: [PATCH 21/22] teach the merge algorithm about cache iterators","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-14T17:50:10Z","receivedAt":"2005-09-14T17:50:10Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Daniel Barkalow writes:\n\n> Another thing to try would be the original dynamic table implementation, \n> plus a hashtable for name lookups, generated the first time a lookup is \n> attempted (since some programs don't do any lookups by name). This has the \n> advantage of skipping the O(n) startup.\n\nHow about just the original dynamic table implementation with\nthe original binary search name lookups? Am I missing\nsomething?\n"},{"id":"8553","messageId":"43287ECB.8090308@citi.umich.edu","threadId":"1782","inReplyTo":"Pine.LNX.4.63.0509141214490.23242@iabervon.org","subject":"Re: [PATCH 21/22] teach the merge algorithm about cache iterators","fromName":"Chuck Lever","fromEmail":"cel@citi.umich.edu","sentAt":"2005-09-14T19:49:31Z","receivedAt":"2005-09-14T19:49:31Z","isPatch":true,"sender":{"key":"cel@citi.umich.edu","avatar":null},"body":"Daniel Barkalow wrote:\n> The really exciting thing to do would be to have different programs use \n> different implementations, by way of linker magic.\n\nyes, i've been considering that, but i'm not sure it is really worth the \neffort. see below -- the right data structure should be good for just \nabout any git workload.\n\n> My guess for the ideal is to have a linked list with a hashtable for \n> finding entries by looking up names, because we don't look things up by \n> index. This combination gives O(1) in-order iteration, O(1) lookup by \n> name, O(1) append, O(n) insert, and O(1) remove. This means that \n> git-update-cache --add would be slow, but everything else would be fast. \n> (Except, of course, for the overhead of actually reading and writing the \n> index file, rather than mmaping it.)\n\n[ i'm not sure why you think insert would be O(n). ]\n\nkeeping the linked list for O(1) next/prev and delete, and augmenting it \nwith a hash table to allow O(m/n) insert and find would be ideal. with \na fairly large hash table, we do better than a tree for any reasonably \nsized repository i can imagine.\n\nand, i believe simply adding a hash table to my list implementation will \nbe easy, and simpler overall than a tree implementation. famous last words.\n\nmmapping the index file is still OK. i haven't changed the cache_entry \nstructure at all.\n\n\nbegin:vcard\nfn:Chuck Lever\nn:Lever;Charles\norg:Network Appliance, Incorporated;Linux NFS Client Development\nadr:535 West William Street, Suite 3100;;Center for Information Technology Integration;Ann Arbor;MI;48103-4943;USA\nemail;internet:cel@citi.umich.edu\ntitle:Member of Technical Staff\ntel;work:+1 734 763 4415\ntel;fax:+1 734 763 4434\ntel;home:+1 734 668 1089\nx-mozilla-html:FALSE\nurl:http://www.monkey.org/~cel/\nversion:2.1\nend:vcard\n\n"},{"id":"8556","messageId":"Pine.LNX.4.63.0509141622340.23242@iabervon.org","threadId":"1782","inReplyTo":"43287ECB.8090308@citi.umich.edu","subject":"Re: [PATCH 21/22] teach the merge algorithm about cache iterators","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-09-14T20:40:28Z","receivedAt":"2005-09-14T20:40:28Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Wed, 14 Sep 2005, Chuck Lever wrote:\n\n> Daniel Barkalow wrote:\n> > The really exciting thing to do would be to have different programs use\n> > different implementations, by way of linker magic.\n> \n> yes, i've been considering that, but i'm not sure it is really worth the\n> effort. see below -- the right data structure should be good for just about\n> any git workload.\n> \n> > My guess for the ideal is to have a linked list with a hashtable for finding\n> > entries by looking up names, because we don't look things up by index. This\n> > combination gives O(1) in-order iteration, O(1) lookup by name, O(1) append,\n> > O(n) insert, and O(1) remove. This means that git-update-cache --add would\n> > be slow, but everything else would be fast. (Except, of course, for the\n> > overhead of actually reading and writing the index file, rather than mmaping\n> > it.)\n> \n> [ i'm not sure why you think insert would be O(n). ]\n\nYou need to find the correct location to insert in the sorted list, and \nthe hash table won't help you, because it doesn't have the new name. \nRemember that the cursors need to go through the index in order, so the \nlist has to stay sorted.\n\n> keeping the linked list for O(1) next/prev and delete, and augmenting it with\n> a hash table to allow O(m/n) insert and find would be ideal. with a fairly\n> large hash table, we do better than a tree for any reasonably sized repository\n> i can imagine.\n> \n> and, i believe simply adding a hash table to my list implementation will be\n> easy, and simpler overall than a tree implementation. famous last words.\n\nI've written a nice hash table which should work well, if you want to make \nthe coding style suitable.\n\n> mmapping the index file is still OK. i haven't changed the cache_entry\n> structure at all.\n\nOh, right, I forgot that the orgnaizational structure isn't the array of \nstructs, but an array of pointers.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"8567","messageId":"4328A3F9.1010506@citi.umich.edu","threadId":"1782","inReplyTo":"Pine.LNX.4.63.0509141622340.23242@iabervon.org","subject":"Re: [PATCH 21/22] teach the merge algorithm about cache iterators","fromName":"Chuck Lever","fromEmail":"cel@citi.umich.edu","sentAt":"2005-09-14T22:28:09Z","receivedAt":"2005-09-14T22:28:09Z","isPatch":true,"sender":{"key":"cel@citi.umich.edu","avatar":null},"body":"Daniel Barkalow wrote:\n> On Wed, 14 Sep 2005, Chuck Lever wrote:\n>>[ i'm not sure why you think insert would be O(n). ]\n> \n> \n> You need to find the correct location to insert in the sorted list, and \n> the hash table won't help you, because it doesn't have the new name. \n> Remember that the cursors need to go through the index in order, so the \n> list has to stay sorted.\n\noh, i see. the hash table won't help cache_find_name find an insertion \npoint quickly if the name isn't already in the cache.\n\nin fact, this will impact the other places that need an insertion point, \nsuch as ls-files and merge-index, as well as your new merge algorithm \n(which inserts all merged entries into the active cache one at a time \nvia add_cache_entry).\n\nconsidering that add_cache_entry can do a cache lookup several times, i \nthink we need the \"not found, returning insertion point\" case to be fast \ntoo.\n\nback to the drawring board.\n\n\nbegin:vcard\nfn:Chuck Lever\nn:Lever;Charles\norg:Network Appliance, Incorporated;Linux NFS Client Development\nadr:535 West William Street, Suite 3100;;Center for Information Technology Integration;Ann Arbor;MI;48103-4943;USA\nemail;internet:cel@citi.umich.edu\ntitle:Member of Technical Staff\ntel;work:+1 734 763 4415\ntel;fax:+1 734 763 4434\ntel;home:+1 734 668 1089\nx-mozilla-html:FALSE\nurl:http://www.monkey.org/~cel/\nversion:2.1\nend:vcard\n\n"},{"id":"8568","messageId":"Pine.LNX.4.58.0509141549270.26803@g5.osdl.org","threadId":"1782","inReplyTo":"4328A3F9.1010506@citi.umich.edu","subject":"Re: [PATCH 21/22] teach the merge algorithm about cache iterators","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-09-14T22:50:53Z","receivedAt":"2005-09-14T22:50:53Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 14 Sep 2005, Chuck Lever wrote:\n> \n> oh, i see. the hash table won't help cache_find_name find an insertion \n> point quickly if the name isn't already in the cache.\n\nNote that almost all insertion tends to happen linearly.\n\nIn particular, read-tree always inserts things in order.\n\nSo probably _most_ of the file finding could actually use even a stupid \nlinear search, if they just had a place to start from. And 99% of the \ntime, it would be very close to where they wanted to be.\n\nHmm?\n\n\t\tLinus\n"},{"id":"8569","messageId":"Pine.LNX.4.63.0509141901020.23242@iabervon.org","threadId":"1782","inReplyTo":"Pine.LNX.4.58.0509141549270.26803@g5.osdl.org","subject":"Re: [PATCH 21/22] teach the merge algorithm about cache iterators","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-09-14T23:23:21Z","receivedAt":"2005-09-14T23:23:21Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Wed, 14 Sep 2005, Linus Torvalds wrote:\n\n> On Wed, 14 Sep 2005, Chuck Lever wrote:\n> > \n> > oh, i see. the hash table won't help cache_find_name find an insertion \n> > point quickly if the name isn't already in the cache.\n> \n> Note that almost all insertion tends to happen linearly.\n> \n> In particular, read-tree always inserts things in order.\n\nread-tree (with Chuck's latest work) should actually only append entries \nto an initially-empty list, which is even easier. Dunno about the other \nstuff, but I'd guess inserting into a cursor would handle a lot of it.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"8600","messageId":"43297EAC.6020205@citi.umich.edu","threadId":"1782","inReplyTo":"Pine.LNX.4.63.0509141901020.23242@iabervon.org","subject":"Re: [PATCH 21/22] teach the merge algorithm about cache iterators","fromName":"Chuck Lever","fromEmail":"cel@citi.umich.edu","sentAt":"2005-09-15T14:01:16Z","receivedAt":"2005-09-15T14:01:16Z","isPatch":true,"sender":{"key":"cel@citi.umich.edu","avatar":null},"body":"Daniel Barkalow wrote:\n> On Wed, 14 Sep 2005, Linus Torvalds wrote:\n> \n> \n>>On Wed, 14 Sep 2005, Chuck Lever wrote:\n>>\n>>>oh, i see. the hash table won't help cache_find_name find an insertion \n>>>point quickly if the name isn't already in the cache.\n>>\n>>Note that almost all insertion tends to happen linearly.\n>>\n>>In particular, read-tree always inserts things in order.\n> \n> read-tree (with Chuck's latest work) should actually only append entries \n> to an initially-empty list, which is even easier. Dunno about the other \n> stuff, but I'd guess inserting into a cursor would handle a lot of it.\n\ni'm implementing the splay tree now.\n\npart of the insertion process is to splay the insertion point up to the \nroot of the tree. if what you and linus says is true, then the search \nfor the next insertion point will be very fast most of the time.\n\n\nbegin:vcard\nfn:Chuck Lever\nn:Lever;Charles\norg:Network Appliance, Incorporated;Linux NFS Client Development\nadr:535 West William Street, Suite 3100;;Center for Information Technology Integration;Ann Arbor;MI;48103-4943;USA\nemail;internet:cel@citi.umich.edu\ntitle:Member of Technical Staff\ntel;work:+1 734 763-4415\ntel;fax:+1 734 763 4434\ntel;home:+1 734 668-1089\nx-mozilla-html:FALSE\nurl:http://www.monkey.org/~cel/\nversion:2.1\nend:vcard\n\n"}]}