{"thread":{"id":"30192","subject":"[PATCH 02/15] refs: manage current_ref within do_one_ref()","startedAt":"2012-04-10T05:30:12Z","lastAt":"2012-04-12T15:36:12Z","messageCount":18,"participants":["mhagger@alum.mit.edu","Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":15},"messages":[{"id":"188839","messageId":"1334035827-20331-1-git-send-email-mhagger@alum.mit.edu","threadId":"30192","inReplyTo":null,"subject":"[PATCH 00/15] Hierarchical reference cache (once again)","fromName":"","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-04-10T05:30:12Z","receivedAt":"2012-04-10T05:30:12Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"From: Michael Haggerty \n\nHere is another installment of the \"hierarchical refs\" saga. This\npatch series (obviously) builds on the changes in master that removed\nextra_refs. This group of patches does some cleanup then makes the\ntransition to storing reference caches hierarchically. It also\nincludes the first benefit of the hierarchical storage scheme, namely\nthat searching for individual references becomes more efficient\n(though as yet all references are read into the cache if any\nreferences are needed, so the benefit is limited).\n\nI will have limited Internet connectivity for the next week, so I\napologize in advance if I don't react quickly to feedback. But I\nwanted to throw at least part of this reworked \"ref-api\" patch series\nback into the ring while the new release cycle is still fresh.\n\nMichael Haggerty (15):\n refs.c: reorder definitions more logically\n refs: manage current_ref within do_one_ref()\n do_for_each_ref_in_array(): new function\n do_for_each_ref_in_arrays(): new function\n repack_without_ref(): reimplement using do_for_each_ref_in_array()\n names_conflict(): new function, extracted from is_refname_available()\n names_conflict(): simplify implementation\n is_refname_available(): reimplement using do_for_each_ref_in_array()\n free_ref_entry(): new function\n check_refname_component(): return 0 for zero-length components\n struct ref_entry: nest the value part in a union\n refs.c: rename ref_array -> ref_dir\n sort_ref_dir(): simplify logic\n refs: store references hierarchically\n do_for_each_ref(): only iterate over the subtree that was requested\n\n refs.c | 1036 +++++++++++++++++++++++++++++++++++++++++-----------------------\n refs.h | 7 +-\n 2 files changed, 670 insertions(+), 373 deletions(-)\n\n-- \n1.7.10\n"},{"id":"188838","messageId":"1334035827-20331-2-git-send-email-mhagger@alum.mit.edu","threadId":"30192","inReplyTo":"1334035827-20331-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 01/15] refs.c: reorder definitions more logically","fromName":"","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-04-10T05:30:13Z","receivedAt":"2012-04-10T05:30:13Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"From: Michael Haggerty \n\nReorder definitions in file: first check_refname_format() and helper\nfunctions, then the functions for managing the ref_entry and ref_array\ndata structures, then ref_cache, then the more \"business-logicky\"\nstuff. No code is changed.\n\nSigned-off-by: Michael Haggerty \n---\n refs.c | 509 ++++++++++++++++++++++++++++++++--------------------------------\n 1 file changed, 256 insertions(+), 253 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex c9f6835..0c9ca4c 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -4,16 +4,102 @@\n #include \"tag.h\"\n #include \"dir.h\"\n \n-/* ISSYMREF=0x01, ISPACKED=0x02 and ISBROKEN=0x04 are public interfaces */\n-#define REF_KNOWS_PEELED 0x10\n+/*\n+ * Make sure \"ref\" is something reasonable to have under \".git/refs/\";\n+ * We do not like it if:\n+ *\n+ * - any path component of it begins with \".\", or\n+ * - it has double dots \"..\", or\n+ * - it has ASCII control character, \"~\", \"^\", \":\" or SP, anywhere, or\n+ * - it ends with a \"/\".\n+ * - it ends with \".lock\"\n+ * - it contains a \"\\\" (backslash)\n+ */\n \n-struct ref_entry {\n-\tunsigned char flag; /* ISSYMREF? ISPACKED? */\n-\tunsigned char sha1[20];\n-\tunsigned char peeled[20];\n-\t/* The full name of the reference (e.g., \"refs/heads/master\"): */\n-\tchar name[FLEX_ARRAY];\n-};\n+/* Return true iff ch is not allowed in reference names. */\n+static inline int bad_ref_char(int ch)\n+{\n+\tif (((unsigned) ch) <= ' ' || ch == 0x7f ||\n+\t ch == '~' || ch == '^' || ch == ':' || ch == '\\\\')\n+\t\treturn 1;\n+\t/* 2.13 Pattern Matching Notation */\n+\tif (ch == '*' || ch == '?' || ch == '[') /* Unsupported */\n+\t\treturn 1;\n+\treturn 0;\n+}\n+\n+/*\n+ * Try to read one refname component from the front of refname. Return\n+ * the length of the component found, or -1 if the component is not\n+ * legal.\n+ */\n+static int check_refname_component(const char *refname, int flags)\n+{\n+\tconst char *cp;\n+\tchar last = '\\0';\n+\n+\tfor (cp = refname; ; cp++) {\n+\t\tchar ch = *cp;\n+\t\tif (ch == '\\0' || ch == '/')\n+\t\t\tbreak;\n+\t\tif (bad_ref_char(ch))\n+\t\t\treturn -1; /* Illegal character in refname. */\n+\t\tif (last == '.' && ch == '.')\n+\t\t\treturn -1; /* Refname contains \"..\". */\n+\t\tif (last == '@' && ch == '{')\n+\t\t\treturn -1; /* Refname contains \"@{\". */\n+\t\tlast = ch;\n+\t}\n+\tif (cp == refname)\n+\t\treturn -1; /* Component has zero length. */\n+\tif (refname[0] == '.') {\n+\t\tif (!(flags & REFNAME_DOT_COMPONENT))\n+\t\t\treturn -1; /* Component starts with '.'. */\n+\t\t/*\n+\t\t * Even if leading dots are allowed, don't allow \".\"\n+\t\t * as a component (\"..\" is prevented by a rule above).\n+\t\t */\n+\t\tif (refname[1] == '\\0')\n+\t\t\treturn -1; /* Component equals \".\". */\n+\t}\n+\tif (cp - refname >= 5 && !memcmp(cp - 5, \".lock\", 5))\n+\t\treturn -1; /* Refname ends with \".lock\". */\n+\treturn cp - refname;\n+}\n+\n+int check_refname_format(const char *refname, int flags)\n+{\n+\tint component_len, component_count = 0;\n+\n+\twhile (1) {\n+\t\t/* We are at the start of a path component. */\n+\t\tcomponent_len = check_refname_component(refname, flags);\n+\t\tif (component_len < 0) {\n+\t\t\tif ((flags & REFNAME_REFSPEC_PATTERN) &&\n+\t\t\t\t\trefname[0] == '*' &&\n+\t\t\t\t\t(refname[1] == '\\0' || refname[1] == '/')) {\n+\t\t\t\t/* Accept one wildcard as a full refname component. */\n+\t\t\t\tflags &= ~REFNAME_REFSPEC_PATTERN;\n+\t\t\t\tcomponent_len = 1;\n+\t\t\t} else {\n+\t\t\t\treturn -1;\n+\t\t\t}\n+\t\t}\n+\t\tcomponent_count++;\n+\t\tif (refname[component_len] == '\\0')\n+\t\t\tbreak;\n+\t\t/* Skip to next component. */\n+\t\trefname += component_len + 1;\n+\t}\n+\n+\tif (refname[component_len - 1] == '.')\n+\t\treturn -1; /* Refname ends with '.'. */\n+\tif (!(flags & REFNAME_ALLOW_ONELEVEL) && component_count < 2)\n+\t\treturn -1; /* Refname has only one component. */\n+\treturn 0;\n+}\n+\n+struct ref_entry;\n \n struct ref_array {\n \tint nr, alloc;\n@@ -29,38 +115,16 @@ struct ref_array {\n \tstruct ref_entry **refs;\n };\n \n-/*\n- * Parse one line from a packed-refs file. Write the SHA1 to sha1.\n- * Return a pointer to the refname within the line (null-terminated),\n- * or NULL if there was a problem.\n- */\n-static const char *parse_ref_line(char *line, unsigned char *sha1)\n-{\n-\t/*\n-\t * 42: the answer to everything.\n-\t *\n-\t * In this case, it happens to be the answer to\n-\t * 40 (length of sha1 hex representation)\n-\t * +1 (space in between hex and name)\n-\t * +1 (newline at the end of the line)\n-\t */\n-\tint len = strlen(line) - 42;\n-\n-\tif (len <= 0)\n-\t\treturn NULL;\n-\tif (get_sha1_hex(line, sha1) < 0)\n-\t\treturn NULL;\n-\tif (!isspace(line[40]))\n-\t\treturn NULL;\n-\tline += 41;\n-\tif (isspace(*line))\n-\t\treturn NULL;\n-\tif (line[len] != '\\n')\n-\t\treturn NULL;\n-\tline[len] = 0;\n+/* ISSYMREF=0x01, ISPACKED=0x02 and ISBROKEN=0x04 are public interfaces */\n+#define REF_KNOWS_PEELED 0x10\n \n-\treturn line;\n-}\n+struct ref_entry {\n+\tunsigned char flag; /* ISSYMREF? ISPACKED? */\n+\tunsigned char sha1[20];\n+\tunsigned char peeled[20];\n+\t/* The full name of the reference (e.g., \"refs/heads/master\"): */\n+\tchar name[FLEX_ARRAY];\n+};\n \n static struct ref_entry *create_ref_entry(const char *refname,\n \t\t\t\t\t const unsigned char *sha1, int flag,\n@@ -88,6 +152,16 @@ static void add_ref(struct ref_array *refs, struct ref_entry *ref)\n \trefs->refs[refs->nr++] = ref;\n }\n \n+static void clear_ref_array(struct ref_array *array)\n+{\n+\tint i;\n+\tfor (i = 0; i < array->nr; i++)\n+\t\tfree(array->refs[i]);\n+\tfree(array->refs);\n+\tarray->sorted = array->nr = array->alloc = 0;\n+\tarray->refs = NULL;\n+}\n+\n static int ref_entry_cmp(const void *a, const void *b)\n {\n \tstruct ref_entry *one = *(struct ref_entry **)a;\n@@ -95,6 +169,33 @@ static int ref_entry_cmp(const void *a, const void *b)\n \treturn strcmp(one->name, two->name);\n }\n \n+static void sort_ref_array(struct ref_array *array);\n+\n+static struct ref_entry *search_ref_array(struct ref_array *array, const char *refname)\n+{\n+\tstruct ref_entry *e, **r;\n+\tint len;\n+\n+\tif (refname == NULL)\n+\t\treturn NULL;\n+\n+\tif (!array->nr)\n+\t\treturn NULL;\n+\tsort_ref_array(array);\n+\tlen = strlen(refname) + 1;\n+\te = xmalloc(sizeof(struct ref_entry) + len);\n+\tmemcpy(e->name, refname, len);\n+\n+\tr = bsearch(&e, array->refs, array->nr, sizeof(*array->refs), ref_entry_cmp);\n+\n+\tfree(e);\n+\n+\tif (r == NULL)\n+\t\treturn NULL;\n+\n+\treturn *r;\n+}\n+\n /*\n * Emit a warning and return true iff ref1 and ref2 have the same name\n * and the same sha1. Die if they have the same name but different\n@@ -142,29 +243,55 @@ static void sort_ref_array(struct ref_array *array)\n \tarray->sorted = array->nr = i + 1;\n }\n \n-static struct ref_entry *search_ref_array(struct ref_array *array, const char *refname)\n-{\n-\tstruct ref_entry *e, **r;\n-\tint len;\n-\n-\tif (refname == NULL)\n-\t\treturn NULL;\n-\n-\tif (!array->nr)\n-\t\treturn NULL;\n-\tsort_ref_array(array);\n-\tlen = strlen(refname) + 1;\n-\te = xmalloc(sizeof(struct ref_entry) + len);\n-\tmemcpy(e->name, refname, len);\n+#define DO_FOR_EACH_INCLUDE_BROKEN 01\n \n-\tr = bsearch(&e, array->refs, array->nr, sizeof(*array->refs), ref_entry_cmp);\n+static struct ref_entry *current_ref;\n \n-\tfree(e);\n+static int do_one_ref(const char *base, each_ref_fn fn, int trim,\n+\t\t int flags, void *cb_data, struct ref_entry *entry)\n+{\n+\tif (prefixcmp(entry->name, base))\n+\t\treturn 0;\n \n-\tif (r == NULL)\n-\t\treturn NULL;\n+\tif (!(flags & DO_FOR_EACH_INCLUDE_BROKEN)) {\n+\t\tif (entry->flag & REF_ISBROKEN)\n+\t\t\treturn 0; /* ignore broken refs e.g. dangling symref */\n+\t\tif (!has_sha1_file(entry->sha1)) {\n+\t\t\terror(\"%s does not point to a valid object!\", entry->name);\n+\t\t\treturn 0;\n+\t\t}\n+\t}\n+\tcurrent_ref = entry;\n+\treturn fn(entry->name + trim, entry->sha1, entry->flag, cb_data);\n+}\n \n-\treturn *r;\n+/*\n+ * Return true iff a reference named refname could be created without\n+ * conflicting with the name of an existing reference. If oldrefname\n+ * is non-NULL, ignore potential conflicts with oldrefname (e.g.,\n+ * because oldrefname is scheduled for deletion in the same\n+ * operation).\n+ */\n+static int is_refname_available(const char *refname, const char *oldrefname,\n+\t\t\t\tstruct ref_array *array)\n+{\n+\tint i, namlen = strlen(refname); /* e.g. 'foo/bar' */\n+\tfor (i = 0; i < array->nr; i++ ) {\n+\t\tstruct ref_entry *entry = array->refs[i];\n+\t\t/* entry->name could be 'foo' or 'foo/bar/baz' */\n+\t\tif (!oldrefname || strcmp(oldrefname, entry->name)) {\n+\t\t\tint len = strlen(entry->name);\n+\t\t\tint cmplen = (namlen < len) ? namlen : len;\n+\t\t\tconst char *lead = (namlen < len) ? entry->name : refname;\n+\t\t\tif (!strncmp(refname, entry->name, cmplen) &&\n+\t\t\t lead[cmplen] == '/') {\n+\t\t\t\terror(\"'%s' exists; cannot create '%s'\",\n+\t\t\t\t entry->name, refname);\n+\t\t\t\treturn 0;\n+\t\t\t}\n+\t\t}\n+\t}\n+\treturn 1;\n }\n \n /*\n@@ -181,18 +308,6 @@ static struct ref_cache {\n \tchar name[FLEX_ARRAY];\n } *ref_cache;\n \n-static struct ref_entry *current_ref;\n-\n-static void clear_ref_array(struct ref_array *array)\n-{\n-\tint i;\n-\tfor (i = 0; i < array->nr; i++)\n-\t\tfree(array->refs[i]);\n-\tfree(array->refs);\n-\tarray->sorted = array->nr = array->alloc = 0;\n-\tarray->refs = NULL;\n-}\n-\n static void clear_packed_ref_cache(struct ref_cache *refs)\n {\n \tif (refs->did_packed)\n@@ -249,6 +364,39 @@ void invalidate_ref_cache(const char *submodule)\n \tclear_loose_ref_cache(refs);\n }\n \n+/*\n+ * Parse one line from a packed-refs file. Write the SHA1 to sha1.\n+ * Return a pointer to the refname within the line (null-terminated),\n+ * or NULL if there was a problem.\n+ */\n+static const char *parse_ref_line(char *line, unsigned char *sha1)\n+{\n+\t/*\n+\t * 42: the answer to everything.\n+\t *\n+\t * In this case, it happens to be the answer to\n+\t * 40 (length of sha1 hex representation)\n+\t * +1 (space in between hex and name)\n+\t * +1 (newline at the end of the line)\n+\t */\n+\tint len = strlen(line) - 42;\n+\n+\tif (len <= 0)\n+\t\treturn NULL;\n+\tif (get_sha1_hex(line, sha1) < 0)\n+\t\treturn NULL;\n+\tif (!isspace(line[40]))\n+\t\treturn NULL;\n+\tline += 41;\n+\tif (isspace(*line))\n+\t\treturn NULL;\n+\tif (line[len] != '\\n')\n+\t\treturn NULL;\n+\tline[len] = 0;\n+\n+\treturn line;\n+}\n+\n static void read_packed_refs(FILE *f, struct ref_array *array)\n {\n \tstruct ref_entry *last = NULL;\n@@ -320,7 +468,6 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,\n \telse\n \t\tpath = git_path(\"%s\", base);\n \n-\n \tdir = opendir(path);\n \n \tif (dir) {\n@@ -374,40 +521,6 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,\n \t}\n }\n \n-struct warn_if_dangling_data {\n-\tFILE *fp;\n-\tconst char *refname;\n-\tconst char *msg_fmt;\n-};\n-\n-static int warn_if_dangling_symref(const char *refname, const unsigned char *sha1,\n-\t\t\t\t int flags, void *cb_data)\n-{\n-\tstruct warn_if_dangling_data *d = cb_data;\n-\tconst char *resolves_to;\n-\tunsigned char junk[20];\n-\n-\tif (!(flags & REF_ISSYMREF))\n-\t\treturn 0;\n-\n-\tresolves_to = resolve_ref_unsafe(refname, junk, 0, NULL);\n-\tif (!resolves_to || strcmp(resolves_to, d->refname))\n-\t\treturn 0;\n-\n-\tfprintf(d->fp, d->msg_fmt, refname);\n-\treturn 0;\n-}\n-\n-void warn_dangling_symref(FILE *fp, const char *msg_fmt, const char *refname)\n-{\n-\tstruct warn_if_dangling_data data;\n-\n-\tdata.fp = fp;\n-\tdata.refname = refname;\n-\tdata.msg_fmt = msg_fmt;\n-\tfor_each_rawref(warn_if_dangling_symref, &data);\n-}\n-\n static struct ref_array *get_loose_refs(struct ref_cache *refs)\n {\n \tif (!refs->did_loose) {\n@@ -645,23 +758,10 @@ int read_ref(const char *refname, unsigned char *sha1)\n \treturn read_ref_full(refname, sha1, 1, NULL);\n }\n \n-#define DO_FOR_EACH_INCLUDE_BROKEN 01\n-static int do_one_ref(const char *base, each_ref_fn fn, int trim,\n-\t\t int flags, void *cb_data, struct ref_entry *entry)\n+int ref_exists(const char *refname)\n {\n-\tif (prefixcmp(entry->name, base))\n-\t\treturn 0;\n-\n-\tif (!(flags & DO_FOR_EACH_INCLUDE_BROKEN)) {\n-\t\tif (entry->flag & REF_ISBROKEN)\n-\t\t\treturn 0; /* ignore broken refs e.g. dangling symref */\n-\t\tif (!has_sha1_file(entry->sha1)) {\n-\t\t\terror(\"%s does not point to a valid object!\", entry->name);\n-\t\t\treturn 0;\n-\t\t}\n-\t}\n-\tcurrent_ref = entry;\n-\treturn fn(entry->name + trim, entry->sha1, entry->flag, cb_data);\n+\tunsigned char sha1[20];\n+\treturn !!resolve_ref_unsafe(refname, sha1, 1, NULL);\n }\n \n static int filter_refs(const char *refname, const unsigned char *sha1, int flags,\n@@ -714,6 +814,40 @@ fallback:\n \treturn -1;\n }\n \n+struct warn_if_dangling_data {\n+\tFILE *fp;\n+\tconst char *refname;\n+\tconst char *msg_fmt;\n+};\n+\n+static int warn_if_dangling_symref(const char *refname, const unsigned char *sha1,\n+\t\t\t\t int flags, void *cb_data)\n+{\n+\tstruct warn_if_dangling_data *d = cb_data;\n+\tconst char *resolves_to;\n+\tunsigned char junk[20];\n+\n+\tif (!(flags & REF_ISSYMREF))\n+\t\treturn 0;\n+\n+\tresolves_to = resolve_ref_unsafe(refname, junk, 0, NULL);\n+\tif (!resolves_to || strcmp(resolves_to, d->refname))\n+\t\treturn 0;\n+\n+\tfprintf(d->fp, d->msg_fmt, refname);\n+\treturn 0;\n+}\n+\n+void warn_dangling_symref(FILE *fp, const char *msg_fmt, const char *refname)\n+{\n+\tstruct warn_if_dangling_data data;\n+\n+\tdata.fp = fp;\n+\tdata.refname = refname;\n+\tdata.msg_fmt = msg_fmt;\n+\tfor_each_rawref(warn_if_dangling_symref, &data);\n+}\n+\n static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn fn,\n \t\t\t int trim, int flags, void *cb_data)\n {\n@@ -757,7 +891,6 @@ end_each:\n \treturn retval;\n }\n \n-\n static int do_head_ref(const char *submodule, each_ref_fn fn, void *cb_data)\n {\n \tunsigned char sha1[20];\n@@ -908,101 +1041,6 @@ int for_each_rawref(each_ref_fn fn, void *cb_data)\n \t\t\t DO_FOR_EACH_INCLUDE_BROKEN, cb_data);\n }\n \n-/*\n- * Make sure \"ref\" is something reasonable to have under \".git/refs/\";\n- * We do not like it if:\n- *\n- * - any path component of it begins with \".\", or\n- * - it has double dots \"..\", or\n- * - it has ASCII control character, \"~\", \"^\", \":\" or SP, anywhere, or\n- * - it ends with a \"/\".\n- * - it ends with \".lock\"\n- * - it contains a \"\\\" (backslash)\n- */\n-\n-/* Return true iff ch is not allowed in reference names. */\n-static inline int bad_ref_char(int ch)\n-{\n-\tif (((unsigned) ch) <= ' ' || ch == 0x7f ||\n-\t ch == '~' || ch == '^' || ch == ':' || ch == '\\\\')\n-\t\treturn 1;\n-\t/* 2.13 Pattern Matching Notation */\n-\tif (ch == '*' || ch == '?' || ch == '[') /* Unsupported */\n-\t\treturn 1;\n-\treturn 0;\n-}\n-\n-/*\n- * Try to read one refname component from the front of refname. Return\n- * the length of the component found, or -1 if the component is not\n- * legal.\n- */\n-static int check_refname_component(const char *refname, int flags)\n-{\n-\tconst char *cp;\n-\tchar last = '\\0';\n-\n-\tfor (cp = refname; ; cp++) {\n-\t\tchar ch = *cp;\n-\t\tif (ch == '\\0' || ch == '/')\n-\t\t\tbreak;\n-\t\tif (bad_ref_char(ch))\n-\t\t\treturn -1; /* Illegal character in refname. */\n-\t\tif (last == '.' && ch == '.')\n-\t\t\treturn -1; /* Refname contains \"..\". */\n-\t\tif (last == '@' && ch == '{')\n-\t\t\treturn -1; /* Refname contains \"@{\". */\n-\t\tlast = ch;\n-\t}\n-\tif (cp == refname)\n-\t\treturn -1; /* Component has zero length. */\n-\tif (refname[0] == '.') {\n-\t\tif (!(flags & REFNAME_DOT_COMPONENT))\n-\t\t\treturn -1; /* Component starts with '.'. */\n-\t\t/*\n-\t\t * Even if leading dots are allowed, don't allow \".\"\n-\t\t * as a component (\"..\" is prevented by a rule above).\n-\t\t */\n-\t\tif (refname[1] == '\\0')\n-\t\t\treturn -1; /* Component equals \".\". */\n-\t}\n-\tif (cp - refname >= 5 && !memcmp(cp - 5, \".lock\", 5))\n-\t\treturn -1; /* Refname ends with \".lock\". */\n-\treturn cp - refname;\n-}\n-\n-int check_refname_format(const char *refname, int flags)\n-{\n-\tint component_len, component_count = 0;\n-\n-\twhile (1) {\n-\t\t/* We are at the start of a path component. */\n-\t\tcomponent_len = check_refname_component(refname, flags);\n-\t\tif (component_len < 0) {\n-\t\t\tif ((flags & REFNAME_REFSPEC_PATTERN) &&\n-\t\t\t\t\trefname[0] == '*' &&\n-\t\t\t\t\t(refname[1] == '\\0' || refname[1] == '/')) {\n-\t\t\t\t/* Accept one wildcard as a full refname component. */\n-\t\t\t\tflags &= ~REFNAME_REFSPEC_PATTERN;\n-\t\t\t\tcomponent_len = 1;\n-\t\t\t} else {\n-\t\t\t\treturn -1;\n-\t\t\t}\n-\t\t}\n-\t\tcomponent_count++;\n-\t\tif (refname[component_len] == '\\0')\n-\t\t\tbreak;\n-\t\t/* Skip to next component. */\n-\t\trefname += component_len + 1;\n-\t}\n-\n-\tif (refname[component_len - 1] == '.')\n-\t\treturn -1; /* Refname ends with '.'. */\n-\tif (!(flags & REFNAME_ALLOW_ONELEVEL) && component_count < 2)\n-\t\treturn -1; /* Refname has only one component. */\n-\treturn 0;\n-}\n-\n const char *prettify_refname(const char *name)\n {\n \treturn name + (\n@@ -1073,35 +1111,6 @@ static int remove_empty_directories(const char *file)\n }\n \n /*\n- * Return true iff a reference named refname could be created without\n- * conflicting with the name of an existing reference. If oldrefname\n- * is non-NULL, ignore potential conflicts with oldrefname (e.g.,\n- * because oldrefname is scheduled for deletion in the same\n- * operation).\n- */\n-static int is_refname_available(const char *refname, const char *oldrefname,\n-\t\t\t\tstruct ref_array *array)\n-{\n-\tint i, namlen = strlen(refname); /* e.g. 'foo/bar' */\n-\tfor (i = 0; i < array->nr; i++ ) {\n-\t\tstruct ref_entry *entry = array->refs[i];\n-\t\t/* entry->name could be 'foo' or 'foo/bar/baz' */\n-\t\tif (!oldrefname || strcmp(oldrefname, entry->name)) {\n-\t\t\tint len = strlen(entry->name);\n-\t\t\tint cmplen = (namlen < len) ? namlen : len;\n-\t\t\tconst char *lead = (namlen < len) ? entry->name : refname;\n-\t\t\tif (!strncmp(refname, entry->name, cmplen) &&\n-\t\t\t lead[cmplen] == '/') {\n-\t\t\t\terror(\"'%s' exists; cannot create '%s'\",\n-\t\t\t\t entry->name, refname);\n-\t\t\t\treturn 0;\n-\t\t\t}\n-\t\t}\n-\t}\n-\treturn 1;\n-}\n-\n-/*\n * *string and *len will only be substituted, and *string returned (for\n * later free()ing) if the string passed in is a magic short-hand form\n * to name a branch.\n@@ -2004,12 +2013,6 @@ int update_ref(const char *action, const char *refname,\n \treturn 0;\n }\n \n-int ref_exists(const char *refname)\n-{\n-\tunsigned char sha1[20];\n-\treturn !!resolve_ref_unsafe(refname, sha1, 1, NULL);\n-}\n-\n struct ref *find_ref_by_name(const struct ref *list, const char *name)\n {\n \tfor ( ; list; list = list->next)\n-- \n1.7.10\n"},{"id":"188837","messageId":"1334035827-20331-3-git-send-email-mhagger@alum.mit.edu","threadId":"30192","inReplyTo":"1334035827-20331-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 02/15] refs: manage current_ref within do_one_ref()","fromName":"","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-04-10T05:30:14Z","receivedAt":"2012-04-10T05:30:14Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"From: Michael Haggerty \n\nSet and clear current_ref within do_one_ref() instead of setting it\nhere and leaving it to somebody else to clear it.\n\nSigned-off-by: Michael Haggerty \n---\n refs.c | 13 +++++++------\n 1 file changed, 7 insertions(+), 6 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex 0c9ca4c..20d5300 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -250,6 +250,7 @@ static struct ref_entry *current_ref;\n static int do_one_ref(const char *base, each_ref_fn fn, int trim,\n \t\t int flags, void *cb_data, struct ref_entry *entry)\n {\n+\tint retval;\n \tif (prefixcmp(entry->name, base))\n \t\treturn 0;\n \n@@ -262,7 +263,9 @@ static int do_one_ref(const char *base, each_ref_fn fn, int trim,\n \t\t}\n \t}\n \tcurrent_ref = entry;\n-\treturn fn(entry->name + trim, entry->sha1, entry->flag, cb_data);\n+\tretval = fn(entry->name + trim, entry->sha1, entry->flag, cb_data);\n+\tcurrent_ref = NULL;\n+\treturn retval;\n }\n \n /*\n@@ -872,7 +875,7 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn\n \t\t}\n \t\tretval = do_one_ref(base, fn, trim, flags, cb_data, entry);\n \t\tif (retval)\n-\t\t\tgoto end_each;\n+\t\t\treturn retval;\n \t}\n \n \tif (l < loose->nr) {\n@@ -883,12 +886,10 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn\n \tfor (; p < packed->nr; p++) {\n \t\tretval = do_one_ref(base, fn, trim, flags, cb_data, packed->refs[p]);\n \t\tif (retval)\n-\t\t\tgoto end_each;\n+\t\t\treturn retval;\n \t}\n \n-end_each:\n-\tcurrent_ref = NULL;\n-\treturn retval;\n+\treturn 0;\n }\n \n static int do_head_ref(const char *submodule, each_ref_fn fn, void *cb_data)\n-- \n1.7.10\n"},{"id":"188842","messageId":"1334035827-20331-4-git-send-email-mhagger@alum.mit.edu","threadId":"30192","inReplyTo":"1334035827-20331-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 03/15] do_for_each_ref_in_array(): new function","fromName":"","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-04-10T05:30:15Z","receivedAt":"2012-04-10T05:30:15Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"From: Michael Haggerty \n\nExtract function do_for_each_ref_in_array() from do_for_each_ref().\nThe new function will be a useful building block for storing refs\nhierarchically.\n\nSigned-off-by: Michael Haggerty \n---\n refs.c | 33 +++++++++++++++++++++++----------\n 1 file changed, 23 insertions(+), 10 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex 20d5300..263bd81 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -269,6 +269,25 @@ static int do_one_ref(const char *base, each_ref_fn fn, int trim,\n }\n \n /*\n+ * Call fn for each reference in array that has index in the range\n+ * offset <= index < array->nr. This function does not sort the\n+ * array; sorting should be done by the caller.\n+ */\n+static int do_for_each_ref_in_array(struct ref_array *array, int offset,\n+\t\t\t\t const char *base,\n+\t\t\t\t each_ref_fn fn, int trim, int flags, void *cb_data)\n+{\n+\tint i;\n+\tassert(array->sorted == array->nr);\n+\tfor (i = offset; i < array->nr; i++) {\n+\t\tint retval = do_one_ref(base, fn, trim, flags, cb_data, array->refs[i]);\n+\t\tif (retval)\n+\t\t\treturn retval;\n+\t}\n+\treturn 0;\n+}\n+\n+/*\n * Return true iff a reference named refname could be created without\n * conflicting with the name of an existing reference. If oldrefname\n * is non-NULL, ignore potential conflicts with oldrefname (e.g.,\n@@ -878,16 +897,10 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn\n \t\t\treturn retval;\n \t}\n \n-\tif (l < loose->nr) {\n-\t\tp = l;\n-\t\tpacked = loose;\n-\t}\n-\n-\tfor (; p < packed->nr; p++) {\n-\t\tretval = do_one_ref(base, fn, trim, flags, cb_data, packed->refs[p]);\n-\t\tif (retval)\n-\t\t\treturn retval;\n-\t}\n+\tif (l < loose->nr)\n+\t\treturn do_for_each_ref_in_array(loose, l, base, fn, trim, flags, cb_data);\n+\tif (p < packed->nr)\n+\t\treturn do_for_each_ref_in_array(packed, p, base, fn, trim, flags, cb_data);\n \n \treturn 0;\n }\n-- \n1.7.10\n"},{"id":"188840","messageId":"1334035827-20331-5-git-send-email-mhagger@alum.mit.edu","threadId":"30192","inReplyTo":"1334035827-20331-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 04/15] do_for_each_ref_in_arrays(): new function","fromName":"","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-04-10T05:30:16Z","receivedAt":"2012-04-10T05:30:16Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"From: Michael Haggerty \n\nExtract function do_for_each_ref_in_arrays() from do_for_each_ref().\nThe new function will be a useful building block for storing refs\nhierarchically.\n\nSigned-off-by: Michael Haggerty \n---\n refs.c | 82 +++++++++++++++++++++++++++++++++++++++++-----------------------\n 1 file changed, 53 insertions(+), 29 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex 263bd81..f9a1b57 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -288,6 +288,52 @@ static int do_for_each_ref_in_array(struct ref_array *array, int offset,\n }\n \n /*\n+ * Call fn for each reference in the union of array1 and array2, in\n+ * order by refname. If an entry appears in both array1 and array2,\n+ * then only process the version that is in array2. The input arrays\n+ * must already be sorted.\n+ */\n+static int do_for_each_ref_in_arrays(struct ref_array *array1,\n+\t\t\t\t struct ref_array *array2,\n+\t\t\t\t const char *base, each_ref_fn fn, int trim,\n+\t\t\t\t int flags, void *cb_data)\n+{\n+\tint retval;\n+\tint i1 = 0, i2 = 0;\n+\n+\tassert(array1->sorted == array1->nr);\n+\tassert(array2->sorted == array2->nr);\n+\twhile (i1 < array1->nr && i2 < array2->nr) {\n+\t\tstruct ref_entry *e1 = array1->refs[i1];\n+\t\tstruct ref_entry *e2 = array2->refs[i2];\n+\t\tint cmp = strcmp(e1->name, e2->name);\n+\t\tif (cmp < 0) {\n+\t\t\tretval = do_one_ref(base, fn, trim, flags, cb_data, e1);\n+\t\t\ti1++;\n+\t\t} else {\n+\t\t\tretval = do_one_ref(base, fn, trim, flags, cb_data, e2);\n+\t\t\ti2++;\n+\t\t\tif (cmp == 0) {\n+\t\t\t\t/*\n+\t\t\t\t * There was a ref in array1 with the\n+\t\t\t\t * same name; ignore it.\n+\t\t\t\t */\n+\t\t\t\ti1++;\n+\t\t\t}\n+\t\t}\n+\t\tif (retval)\n+\t\t\treturn retval;\n+\t}\n+\tif (i1 < array1->nr)\n+\t\treturn do_for_each_ref_in_array(array1, i1,\n+\t\t\t\t\t\tbase, fn, trim, flags, cb_data);\n+\tif (i2 < array2->nr)\n+\t\treturn do_for_each_ref_in_array(array2, i2,\n+\t\t\t\t\t\tbase, fn, trim, flags, cb_data);\n+\treturn 0;\n+}\n+\n+/*\n * Return true iff a reference named refname could be created without\n * conflicting with the name of an existing reference. If oldrefname\n * is non-NULL, ignore potential conflicts with oldrefname (e.g.,\n@@ -873,36 +919,14 @@ void warn_dangling_symref(FILE *fp, const char *msg_fmt, const char *refname)\n static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn fn,\n \t\t\t int trim, int flags, void *cb_data)\n {\n-\tint retval = 0, p = 0, l = 0;\n \tstruct ref_cache *refs = get_ref_cache(submodule);\n-\tstruct ref_array *packed = get_packed_refs(refs);\n-\tstruct ref_array *loose = get_loose_refs(refs);\n-\n-\tsort_ref_array(packed);\n-\tsort_ref_array(loose);\n-\twhile (p < packed->nr && l < loose->nr) {\n-\t\tstruct ref_entry *entry;\n-\t\tint cmp = strcmp(packed->refs[p]->name, loose->refs[l]->name);\n-\t\tif (!cmp) {\n-\t\t\tp++;\n-\t\t\tcontinue;\n-\t\t}\n-\t\tif (cmp > 0) {\n-\t\t\tentry = loose->refs[l++];\n-\t\t} else {\n-\t\t\tentry = packed->refs[p++];\n-\t\t}\n-\t\tretval = do_one_ref(base, fn, trim, flags, cb_data, entry);\n-\t\tif (retval)\n-\t\t\treturn retval;\n-\t}\n-\n-\tif (l < loose->nr)\n-\t\treturn do_for_each_ref_in_array(loose, l, base, fn, trim, flags, cb_data);\n-\tif (p < packed->nr)\n-\t\treturn do_for_each_ref_in_array(packed, p, base, fn, trim, flags, cb_data);\n-\n-\treturn 0;\n+\tstruct ref_array *packed_refs = get_packed_refs(refs);\n+\tstruct ref_array *loose_refs = get_loose_refs(refs);\n+\tsort_ref_array(packed_refs);\n+\tsort_ref_array(loose_refs);\n+\treturn do_for_each_ref_in_arrays(packed_refs,\n+\t\t\t\t\t loose_refs,\n+\t\t\t\t\t base, fn, trim, flags, cb_data);\n }\n \n static int do_head_ref(const char *submodule, each_ref_fn fn, void *cb_data)\n-- \n1.7.10\n"},{"id":"188841","messageId":"1334035827-20331-6-git-send-email-mhagger@alum.mit.edu","threadId":"30192","inReplyTo":"1334035827-20331-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 05/15] repack_without_ref(): reimplement using do_for_each_ref_in_array()","fromName":"","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-04-10T05:30:17Z","receivedAt":"2012-04-10T05:30:17Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"From: Michael Haggerty \n\nIt costs a bit of boilerplate, but it means that the function can be\nignorant of how cached refs are stored.\n\nSigned-off-by: Michael Haggerty \n---\n refs.c | 51 ++++++++++++++++++++++++++++++---------------------\n 1 file changed, 30 insertions(+), 21 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex f9a1b57..78dbda6 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -1333,36 +1333,45 @@ struct ref_lock *lock_any_ref_for_update(const char *refname,\n \treturn lock_ref_sha1_basic(refname, old_sha1, flags, NULL);\n }\n \n+struct repack_without_ref_sb {\n+\tconst char *refname;\n+\tint fd;\n+};\n+\n+static int repack_without_ref_fn(const char *refname, const unsigned char *sha1,\n+\t\t\t\t int flags, void *cb_data)\n+{\n+\tstruct repack_without_ref_sb *data = cb_data;\n+\tchar line[PATH_MAX + 100];\n+\tint len;\n+\n+\tif (!strcmp(data->refname, refname))\n+\t\treturn 0;\n+\tlen = snprintf(line, sizeof(line), \"%s %s\\n\",\n+\t\t sha1_to_hex(sha1), refname);\n+\t/* this should not happen but just being defensive */\n+\tif (len > sizeof(line))\n+\t\tdie(\"too long a refname '%s'\", refname);\n+\twrite_or_die(data->fd, line, len);\n+\treturn 0;\n+}\n+\n static struct lock_file packlock;\n \n static int repack_without_ref(const char *refname)\n {\n-\tstruct ref_array *packed;\n-\tint fd, i;\n-\n-\tpacked = get_packed_refs(get_ref_cache(NULL));\n+\tstruct repack_without_ref_sb data;\n+\tstruct ref_array *packed = get_packed_refs(get_ref_cache(NULL));\n+\tsort_ref_array(packed);\n \tif (search_ref_array(packed, refname) == NULL)\n \t\treturn 0;\n-\tfd = hold_lock_file_for_update(&packlock, git_path(\"packed-refs\"), 0);\n-\tif (fd < 0) {\n+\tdata.refname = refname;\n+\tdata.fd = hold_lock_file_for_update(&packlock, git_path(\"packed-refs\"), 0);\n+\tif (data.fd < 0) {\n \t\tunable_to_lock_error(git_path(\"packed-refs\"), errno);\n \t\treturn error(\"cannot delete '%s' from packed refs\", refname);\n \t}\n-\n-\tfor (i = 0; i < packed->nr; i++) {\n-\t\tchar line[PATH_MAX + 100];\n-\t\tint len;\n-\t\tstruct ref_entry *ref = packed->refs[i];\n-\n-\t\tif (!strcmp(refname, ref->name))\n-\t\t\tcontinue;\n-\t\tlen = snprintf(line, sizeof(line), \"%s %s\\n\",\n-\t\t\t sha1_to_hex(ref->sha1), ref->name);\n-\t\t/* this should not happen but just being defensive */\n-\t\tif (len > sizeof(line))\n-\t\t\tdie(\"too long a refname '%s'\", ref->name);\n-\t\twrite_or_die(fd, line, len);\n-\t}\n+\tdo_for_each_ref_in_array(packed, 0, \"\", repack_without_ref_fn, 0, 0, &data);\n \treturn commit_lock_file(&packlock);\n }\n \n-- \n1.7.10\n"},{"id":"188843","messageId":"1334035827-20331-7-git-send-email-mhagger@alum.mit.edu","threadId":"30192","inReplyTo":"1334035827-20331-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 06/15] names_conflict(): new function, extracted from is_refname_available()","fromName":"","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-04-10T05:30:18Z","receivedAt":"2012-04-10T05:30:18Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"From: Michael Haggerty \n\nThis costs an extra strlen() in the loop, but even that small price\nwill be clawed back in the next patch.\n\nSigned-off-by: Michael Haggerty \n---\n refs.c | 43 +++++++++++++++++++++++++++++++------------\n 1 file changed, 31 insertions(+), 12 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex 78dbda6..cdb66d9 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -334,6 +334,30 @@ static int do_for_each_ref_in_arrays(struct ref_array *array1,\n }\n \n /*\n+ * Return true iff refname1 and refname2 conflict with each other.\n+ * Two reference names conflict if one of them exactly matches the\n+ * leading components of the other; e.g., \"foo/bar\" conflicts with\n+ * both \"foo\" and with \"foo/bar/baz\" but not with \"foo/bar\" or\n+ * \"foo/barbados\".\n+ */\n+static int names_conflict(const char *refname1, const char *refname2)\n+{\n+\tint len1 = strlen(refname1);\n+\tint len2 = strlen(refname2);\n+\tint cmplen;\n+\tconst char *lead;\n+\n+\tif (len1 < len2) {\n+\t\tcmplen = len1;\n+\t\tlead = refname2;\n+\t} else {\n+\t\tcmplen = len2;\n+\t\tlead = refname1;\n+\t}\n+\treturn !strncmp(refname1, refname2, cmplen) && lead[cmplen] == '/';\n+}\n+\n+/*\n * Return true iff a reference named refname could be created without\n * conflicting with the name of an existing reference. If oldrefname\n * is non-NULL, ignore potential conflicts with oldrefname (e.g.,\n@@ -343,20 +367,15 @@ static int do_for_each_ref_in_arrays(struct ref_array *array1,\n static int is_refname_available(const char *refname, const char *oldrefname,\n \t\t\t\tstruct ref_array *array)\n {\n-\tint i, namlen = strlen(refname); /* e.g. 'foo/bar' */\n+\tint i;\n \tfor (i = 0; i < array->nr; i++ ) {\n \t\tstruct ref_entry *entry = array->refs[i];\n-\t\t/* entry->name could be 'foo' or 'foo/bar/baz' */\n-\t\tif (!oldrefname || strcmp(oldrefname, entry->name)) {\n-\t\t\tint len = strlen(entry->name);\n-\t\t\tint cmplen = (namlen < len) ? namlen : len;\n-\t\t\tconst char *lead = (namlen < len) ? entry->name : refname;\n-\t\t\tif (!strncmp(refname, entry->name, cmplen) &&\n-\t\t\t lead[cmplen] == '/') {\n-\t\t\t\terror(\"'%s' exists; cannot create '%s'\",\n-\t\t\t\t entry->name, refname);\n-\t\t\t\treturn 0;\n-\t\t\t}\n+\t\tif (oldrefname && !strcmp(oldrefname, entry->name))\n+\t\t\tcontinue;\n+\t\tif (names_conflict(refname, entry->name)) {\n+\t\t\terror(\"'%s' exists; cannot create '%s'\",\n+\t\t\t entry->name, refname);\n+\t\t\treturn 0;\n \t\t}\n \t}\n \treturn 1;\n-- \n1.7.10\n"},{"id":"188852","messageId":"1334035827-20331-8-git-send-email-mhagger@alum.mit.edu","threadId":"30192","inReplyTo":"1334035827-20331-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 07/15] names_conflict(): simplify implementation","fromName":"","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-04-10T05:30:19Z","receivedAt":"2012-04-10T05:30:19Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"From: Michael Haggerty \n\nSave a bunch of lines of code and a couple of strlen() calls.\n\nSigned-off-by: Michael Haggerty \n---\n refs.c | 17 ++++-------------\n 1 file changed, 4 insertions(+), 13 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex cdb66d9..d4f58b8 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -342,19 +342,10 @@ static int do_for_each_ref_in_arrays(struct ref_array *array1,\n */\n static int names_conflict(const char *refname1, const char *refname2)\n {\n-\tint len1 = strlen(refname1);\n-\tint len2 = strlen(refname2);\n-\tint cmplen;\n-\tconst char *lead;\n-\n-\tif (len1 < len2) {\n-\t\tcmplen = len1;\n-\t\tlead = refname2;\n-\t} else {\n-\t\tcmplen = len2;\n-\t\tlead = refname1;\n-\t}\n-\treturn !strncmp(refname1, refname2, cmplen) && lead[cmplen] == '/';\n+\tfor (; *refname1 && *refname1 == *refname2; refname1++, refname2++)\n+\t\t;\n+\treturn (*refname1 == '\\0' && *refname2 == '/')\n+\t\t|| (*refname1 == '/' && *refname2 == '\\0');\n }\n \n /*\n-- \n1.7.10\n"},{"id":"188848","messageId":"1334035827-20331-9-git-send-email-mhagger@alum.mit.edu","threadId":"30192","inReplyTo":"1334035827-20331-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 08/15] is_refname_available(): reimplement using do_for_each_ref_in_array()","fromName":"","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-04-10T05:30:20Z","receivedAt":"2012-04-10T05:30:20Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"From: Michael Haggerty \n\nThis implementation will survive upcoming changes to the ref_array\ndata structure.\n\nSigned-off-by: Michael Haggerty \n---\n refs.c | 47 ++++++++++++++++++++++++++++++++++-------------\n 1 file changed, 34 insertions(+), 13 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex d4f58b8..4b94b08 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -348,26 +348,47 @@ static int names_conflict(const char *refname1, const char *refname2)\n \t\t|| (*refname1 == '/' && *refname2 == '\\0');\n }\n \n+struct name_conflict_cb {\n+\tconst char *refname;\n+\tconst char *oldrefname;\n+\tconst char *conflicting_refname;\n+};\n+\n+static int name_conflict_fn(const char *existingrefname, const unsigned char *sha1,\n+\t\t\t int flags, void *cb_data)\n+{\n+\tstruct name_conflict_cb *data = (struct name_conflict_cb *)cb_data;\n+\tif (data->oldrefname && !strcmp(data->oldrefname, existingrefname))\n+\t\treturn 0;\n+\tif (names_conflict(data->refname, existingrefname)) {\n+\t\tdata->conflicting_refname = existingrefname;\n+\t\treturn 1;\n+\t}\n+\treturn 0;\n+}\n+\n /*\n * Return true iff a reference named refname could be created without\n- * conflicting with the name of an existing reference. If oldrefname\n- * is non-NULL, ignore potential conflicts with oldrefname (e.g.,\n- * because oldrefname is scheduled for deletion in the same\n+ * conflicting with the name of an existing reference in array. If\n+ * oldrefname is non-NULL, ignore potential conflicts with oldrefname\n+ * (e.g., because oldrefname is scheduled for deletion in the same\n * operation).\n */\n static int is_refname_available(const char *refname, const char *oldrefname,\n \t\t\t\tstruct ref_array *array)\n {\n-\tint i;\n-\tfor (i = 0; i < array->nr; i++ ) {\n-\t\tstruct ref_entry *entry = array->refs[i];\n-\t\tif (oldrefname && !strcmp(oldrefname, entry->name))\n-\t\t\tcontinue;\n-\t\tif (names_conflict(refname, entry->name)) {\n-\t\t\terror(\"'%s' exists; cannot create '%s'\",\n-\t\t\t entry->name, refname);\n-\t\t\treturn 0;\n-\t\t}\n+\tstruct name_conflict_cb data;\n+\tdata.refname = refname;\n+\tdata.oldrefname = oldrefname;\n+\tdata.conflicting_refname = NULL;\n+\n+\tsort_ref_array(array);\n+\tif (do_for_each_ref_in_array(array, 0, \"\", name_conflict_fn,\n+\t\t\t\t 0, DO_FOR_EACH_INCLUDE_BROKEN,\n+\t\t\t\t &data)) {\n+\t\terror(\"'%s' exists; cannot create '%s'\",\n+\t\t data.conflicting_refname, refname);\n+\t\treturn 0;\n \t}\n \treturn 1;\n }\n-- \n1.7.10\n"},{"id":"188851","messageId":"1334035827-20331-10-git-send-email-mhagger@alum.mit.edu","threadId":"30192","inReplyTo":"1334035827-20331-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 09/15] free_ref_entry(): new function","fromName":"","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-04-10T05:30:21Z","receivedAt":"2012-04-10T05:30:21Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"From: Michael Haggerty \n\nAdd a function free_ref_entry(). This function will become nontrivial\nwhen ref_entry (soon) becomes polymorphic.\n\nSigned-off-by: Michael Haggerty \n---\n refs.c | 9 +++++++--\n 1 file changed, 7 insertions(+), 2 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex 4b94b08..8659c3e 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -145,6 +145,11 @@ static struct ref_entry *create_ref_entry(const char *refname,\n \treturn ref;\n }\n \n+static void free_ref_entry(struct ref_entry *entry)\n+{\n+\tfree(entry);\n+}\n+\n /* Add a ref_entry to the end of the ref_array (unsorted). */\n static void add_ref(struct ref_array *refs, struct ref_entry *ref)\n {\n@@ -156,7 +161,7 @@ static void clear_ref_array(struct ref_array *array)\n {\n \tint i;\n \tfor (i = 0; i < array->nr; i++)\n-\t\tfree(array->refs[i]);\n+\t\tfree_ref_entry(array->refs[i]);\n \tfree(array->refs);\n \tarray->sorted = array->nr = array->alloc = 0;\n \tarray->refs = NULL;\n@@ -235,7 +240,7 @@ static void sort_ref_array(struct ref_array *array)\n \ti = 0;\n \tfor (j = 1; j < array->nr; j++) {\n \t\tif (is_dup_ref(array->refs[i], array->refs[j])) {\n-\t\t\tfree(array->refs[j]);\n+\t\t\tfree_ref_entry(array->refs[j]);\n \t\t\tcontinue;\n \t\t}\n \t\tarray->refs[++i] = array->refs[j];\n-- \n1.7.10\n"},{"id":"188846","messageId":"1334035827-20331-11-git-send-email-mhagger@alum.mit.edu","threadId":"30192","inReplyTo":"1334035827-20331-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 10/15] check_refname_component(): return 0 for zero-length components","fromName":"","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-04-10T05:30:22Z","receivedAt":"2012-04-10T05:30:22Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"From: Michael Haggerty \n\nReturn 0 (instead of -1) for zero-length components. Move the\ninterpretation of zero-length components as illegal to\ncheck_refname_format().\n\nThis will make it easier to extend check_refname_format() to also\ncheck whether directory names are valid.\n\nSigned-off-by: Michael Haggerty \n---\n refs.c | 4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex 8659c3e..1f6890b 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -51,7 +51,7 @@ static int check_refname_component(const char *refname, int flags)\n \t\tlast = ch;\n \t}\n \tif (cp == refname)\n-\t\treturn -1; /* Component has zero length. */\n+\t\treturn 0; /* Component has zero length. */\n \tif (refname[0] == '.') {\n \t\tif (!(flags & REFNAME_DOT_COMPONENT))\n \t\t\treturn -1; /* Component starts with '.'. */\n@@ -74,7 +74,7 @@ int check_refname_format(const char *refname, int flags)\n \twhile (1) {\n \t\t/* We are at the start of a path component. */\n \t\tcomponent_len = check_refname_component(refname, flags);\n-\t\tif (component_len < 0) {\n+\t\tif (component_len <= 0) {\n \t\t\tif ((flags & REFNAME_REFSPEC_PATTERN) &&\n \t\t\t\t\trefname[0] == '*' &&\n \t\t\t\t\t(refname[1] == '\\0' || refname[1] == '/')) {\n-- \n1.7.10\n"},{"id":"188844","messageId":"1334035827-20331-12-git-send-email-mhagger@alum.mit.edu","threadId":"30192","inReplyTo":"1334035827-20331-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 11/15] struct ref_entry: nest the value part in a union","fromName":"","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-04-10T05:30:23Z","receivedAt":"2012-04-10T05:30:23Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"From: Michael Haggerty \n\nThis change is obviously silly by itself, but it is a step towards\nadding a second member to the union.\n\nSigned-off-by: Michael Haggerty \n---\n refs.c | 32 +++++++++++++++++++-------------\n 1 file changed, 19 insertions(+), 13 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex 1f6890b..416c97f 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -101,6 +101,11 @@ int check_refname_format(const char *refname, int flags)\n \n struct ref_entry;\n \n+struct ref_value {\n+\tunsigned char sha1[20];\n+\tunsigned char peeled[20];\n+};\n+\n struct ref_array {\n \tint nr, alloc;\n \n@@ -120,8 +125,9 @@ struct ref_array {\n \n struct ref_entry {\n \tunsigned char flag; /* ISSYMREF? ISPACKED? */\n-\tunsigned char sha1[20];\n-\tunsigned char peeled[20];\n+\tunion {\n+\t\tstruct ref_value value;\n+\t} u;\n \t/* The full name of the reference (e.g., \"refs/heads/master\"): */\n \tchar name[FLEX_ARRAY];\n };\n@@ -138,8 +144,8 @@ static struct ref_entry *create_ref_entry(const char *refname,\n \t\tdie(\"Reference has invalid format: '%s'\", refname);\n \tlen = strlen(refname) + 1;\n \tref = xmalloc(sizeof(struct ref_entry) + len);\n-\thashcpy(ref->sha1, sha1);\n-\thashclr(ref->peeled);\n+\thashcpy(ref->u.value.sha1, sha1);\n+\thashclr(ref->u.value.peeled);\n \tmemcpy(ref->name, refname, len);\n \tref->flag = flag;\n \treturn ref;\n@@ -210,7 +216,7 @@ static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2\n {\n \tif (!strcmp(ref1->name, ref2->name)) {\n \t\t/* Duplicate name; make sure that the SHA1s match: */\n-\t\tif (hashcmp(ref1->sha1, ref2->sha1))\n+\t\tif (hashcmp(ref1->u.value.sha1, ref2->u.value.sha1))\n \t\t\tdie(\"Duplicated ref, and SHA1s don't match: %s\",\n \t\t\t ref1->name);\n \t\twarning(\"Duplicated ref: %s\", ref1->name);\n@@ -262,13 +268,13 @@ static int do_one_ref(const char *base, each_ref_fn fn, int trim,\n \tif (!(flags & DO_FOR_EACH_INCLUDE_BROKEN)) {\n \t\tif (entry->flag & REF_ISBROKEN)\n \t\t\treturn 0; /* ignore broken refs e.g. dangling symref */\n-\t\tif (!has_sha1_file(entry->sha1)) {\n+\t\tif (!has_sha1_file(entry->u.value.sha1)) {\n \t\t\terror(\"%s does not point to a valid object!\", entry->name);\n \t\t\treturn 0;\n \t\t}\n \t}\n \tcurrent_ref = entry;\n-\tretval = fn(entry->name + trim, entry->sha1, entry->flag, cb_data);\n+\tretval = fn(entry->name + trim, entry->u.value.sha1, entry->flag, cb_data);\n \tcurrent_ref = NULL;\n \treturn retval;\n }\n@@ -531,7 +537,7 @@ static void read_packed_refs(FILE *f, struct ref_array *array)\n \t\t strlen(refline) == 42 &&\n \t\t refline[41] == '\\n' &&\n \t\t !get_sha1_hex(refline + 1, sha1))\n-\t\t\thashcpy(last->peeled, sha1);\n+\t\t\thashcpy(last->u.value.peeled, sha1);\n \t}\n }\n \n@@ -653,7 +659,7 @@ static int resolve_gitlink_packed_ref(struct ref_cache *refs,\n \tif (ref == NULL)\n \t\treturn -1;\n \n-\tmemcpy(sha1, ref->sha1, 20);\n+\tmemcpy(sha1, ref->u.value.sha1, 20);\n \treturn 0;\n }\n \n@@ -723,7 +729,7 @@ static int get_packed_ref(const char *refname, unsigned char *sha1)\n \tstruct ref_array *packed = get_packed_refs(get_ref_cache(NULL));\n \tstruct ref_entry *entry = search_ref_array(packed, refname);\n \tif (entry) {\n-\t\thashcpy(sha1, entry->sha1);\n+\t\thashcpy(sha1, entry->u.value.sha1);\n \t\treturn 0;\n \t}\n \treturn -1;\n@@ -886,10 +892,10 @@ int peel_ref(const char *refname, unsigned char *sha1)\n \tif (current_ref && (current_ref->name == refname\n \t\t|| !strcmp(current_ref->name, refname))) {\n \t\tif (current_ref->flag & REF_KNOWS_PEELED) {\n-\t\t\thashcpy(sha1, current_ref->peeled);\n+\t\t\thashcpy(sha1, current_ref->u.value.peeled);\n \t\t\treturn 0;\n \t\t}\n-\t\thashcpy(base, current_ref->sha1);\n+\t\thashcpy(base, current_ref->u.value.sha1);\n \t\tgoto fallback;\n \t}\n \n@@ -901,7 +907,7 @@ int peel_ref(const char *refname, unsigned char *sha1)\n \t\tstruct ref_entry *r = search_ref_array(array, refname);\n \n \t\tif (r != NULL && r->flag & REF_KNOWS_PEELED) {\n-\t\t\thashcpy(sha1, r->peeled);\n+\t\t\thashcpy(sha1, r->u.value.peeled);\n \t\t\treturn 0;\n \t\t}\n \t}\n-- \n1.7.10\n"},{"id":"188847","messageId":"1334035827-20331-13-git-send-email-mhagger@alum.mit.edu","threadId":"30192","inReplyTo":"1334035827-20331-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 12/15] refs.c: rename ref_array -> ref_dir","fromName":"","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-04-10T05:30:24Z","receivedAt":"2012-04-10T05:30:24Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"From: Michael Haggerty \n\nThis purely textual change is in preparation for storing references\nhierarchically, when the old ref_array structure will represent one\n\"directory\" of references. Rename functions that deal with this\nstructure analogously, and also rename the structure's \"refs\" member\nto \"entries\".\n\nSigned-off-by: Michael Haggerty \n---\n refs.c | 195 ++++++++++++++++++++++++++++++++--------------------------------\n 1 file changed, 97 insertions(+), 98 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex 416c97f..4e0cfb2 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -106,7 +106,7 @@ struct ref_value {\n \tunsigned char peeled[20];\n };\n \n-struct ref_array {\n+struct ref_dir {\n \tint nr, alloc;\n \n \t/*\n@@ -117,7 +117,7 @@ struct ref_array {\n \t */\n \tint sorted;\n \n-\tstruct ref_entry **refs;\n+\tstruct ref_entry **entries;\n };\n \n /* ISSYMREF=0x01, ISPACKED=0x02 and ISBROKEN=0x04 are public interfaces */\n@@ -156,21 +156,21 @@ static void free_ref_entry(struct ref_entry *entry)\n \tfree(entry);\n }\n \n-/* Add a ref_entry to the end of the ref_array (unsorted). */\n-static void add_ref(struct ref_array *refs, struct ref_entry *ref)\n+/* Add a ref_entry to the end of the ref_dir (unsorted). */\n+static void add_ref(struct ref_dir *refs, struct ref_entry *ref)\n {\n-\tALLOC_GROW(refs->refs, refs->nr + 1, refs->alloc);\n-\trefs->refs[refs->nr++] = ref;\n+\tALLOC_GROW(refs->entries, refs->nr + 1, refs->alloc);\n+\trefs->entries[refs->nr++] = ref;\n }\n \n-static void clear_ref_array(struct ref_array *array)\n+static void clear_ref_dir(struct ref_dir *dir)\n {\n \tint i;\n-\tfor (i = 0; i < array->nr; i++)\n-\t\tfree_ref_entry(array->refs[i]);\n-\tfree(array->refs);\n-\tarray->sorted = array->nr = array->alloc = 0;\n-\tarray->refs = NULL;\n+\tfor (i = 0; i < dir->nr; i++)\n+\t\tfree_ref_entry(dir->entries[i]);\n+\tfree(dir->entries);\n+\tdir->sorted = dir->nr = dir->alloc = 0;\n+\tdir->entries = NULL;\n }\n \n static int ref_entry_cmp(const void *a, const void *b)\n@@ -180,9 +180,9 @@ static int ref_entry_cmp(const void *a, const void *b)\n \treturn strcmp(one->name, two->name);\n }\n \n-static void sort_ref_array(struct ref_array *array);\n+static void sort_ref_dir(struct ref_dir *dir);\n \n-static struct ref_entry *search_ref_array(struct ref_array *array, const char *refname)\n+static struct ref_entry *search_ref_dir(struct ref_dir *dir, const char *refname)\n {\n \tstruct ref_entry *e, **r;\n \tint len;\n@@ -190,14 +190,14 @@ static struct ref_entry *search_ref_array(struct ref_array *array, const char *r\n \tif (refname == NULL)\n \t\treturn NULL;\n \n-\tif (!array->nr)\n+\tif (!dir->nr)\n \t\treturn NULL;\n-\tsort_ref_array(array);\n+\tsort_ref_dir(dir);\n \tlen = strlen(refname) + 1;\n \te = xmalloc(sizeof(struct ref_entry) + len);\n \tmemcpy(e->name, refname, len);\n \n-\tr = bsearch(&e, array->refs, array->nr, sizeof(*array->refs), ref_entry_cmp);\n+\tr = bsearch(&e, dir->entries, dir->nr, sizeof(*dir->entries), ref_entry_cmp);\n \n \tfree(e);\n \n@@ -227,9 +227,9 @@ static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2\n }\n \n /*\n- * Sort the entries in array (if they are not already sorted).\n+ * Sort the entries in dir (if they are not already sorted).\n */\n-static void sort_ref_array(struct ref_array *array)\n+static void sort_ref_dir(struct ref_dir *dir)\n {\n \tint i, j;\n \n@@ -237,21 +237,21 @@ static void sort_ref_array(struct ref_array *array)\n \t * This check also prevents passing a zero-length array to qsort(),\n \t * which is a problem on some platforms.\n \t */\n-\tif (array->sorted == array->nr)\n+\tif (dir->sorted == dir->nr)\n \t\treturn;\n \n-\tqsort(array->refs, array->nr, sizeof(*array->refs), ref_entry_cmp);\n+\tqsort(dir->entries, dir->nr, sizeof(*dir->entries), ref_entry_cmp);\n \n-\t/* Remove any duplicates from the ref_array */\n+\t/* Remove any duplicates from the ref_dir */\n \ti = 0;\n-\tfor (j = 1; j < array->nr; j++) {\n-\t\tif (is_dup_ref(array->refs[i], array->refs[j])) {\n-\t\t\tfree_ref_entry(array->refs[j]);\n+\tfor (j = 1; j < dir->nr; j++) {\n+\t\tif (is_dup_ref(dir->entries[i], dir->entries[j])) {\n+\t\t\tfree_ref_entry(dir->entries[j]);\n \t\t\tcontinue;\n \t\t}\n-\t\tarray->refs[++i] = array->refs[j];\n+\t\tdir->entries[++i] = dir->entries[j];\n \t}\n-\tarray->sorted = array->nr = i + 1;\n+\tdir->sorted = dir->nr = i + 1;\n }\n \n #define DO_FOR_EACH_INCLUDE_BROKEN 01\n@@ -280,18 +280,18 @@ static int do_one_ref(const char *base, each_ref_fn fn, int trim,\n }\n \n /*\n- * Call fn for each reference in array that has index in the range\n- * offset <= index < array->nr. This function does not sort the\n- * array; sorting should be done by the caller.\n+ * Call fn for each reference in dir that has index in the range\n+ * offset <= index < dir->nr. This function does not sort the dir;\n+ * sorting should be done by the caller.\n */\n-static int do_for_each_ref_in_array(struct ref_array *array, int offset,\n-\t\t\t\t const char *base,\n-\t\t\t\t each_ref_fn fn, int trim, int flags, void *cb_data)\n+static int do_for_each_ref_in_dir(struct ref_dir *dir, int offset,\n+\t\t\t\t const char *base,\n+\t\t\t\t each_ref_fn fn, int trim, int flags, void *cb_data)\n {\n \tint i;\n-\tassert(array->sorted == array->nr);\n-\tfor (i = offset; i < array->nr; i++) {\n-\t\tint retval = do_one_ref(base, fn, trim, flags, cb_data, array->refs[i]);\n+\tassert(dir->sorted == dir->nr);\n+\tfor (i = offset; i < dir->nr; i++) {\n+\t\tint retval = do_one_ref(base, fn, trim, flags, cb_data, dir->entries[i]);\n \t\tif (retval)\n \t\t\treturn retval;\n \t}\n@@ -299,24 +299,24 @@ static int do_for_each_ref_in_array(struct ref_array *array, int offset,\n }\n \n /*\n- * Call fn for each reference in the union of array1 and array2, in\n- * order by refname. If an entry appears in both array1 and array2,\n- * then only process the version that is in array2. The input arrays\n- * must already be sorted.\n+ * Call fn for each reference in the union of dir1 and dir2, in order\n+ * by refname. If an entry appears in both dir1 and dir2, then only\n+ * process the version that is in dir2. The input dirs must already\n+ * be sorted.\n */\n-static int do_for_each_ref_in_arrays(struct ref_array *array1,\n-\t\t\t\t struct ref_array *array2,\n-\t\t\t\t const char *base, each_ref_fn fn, int trim,\n-\t\t\t\t int flags, void *cb_data)\n+static int do_for_each_ref_in_dirs(struct ref_dir *dir1,\n+\t\t\t\t struct ref_dir *dir2,\n+\t\t\t\t const char *base, each_ref_fn fn, int trim,\n+\t\t\t\t int flags, void *cb_data)\n {\n \tint retval;\n \tint i1 = 0, i2 = 0;\n \n-\tassert(array1->sorted == array1->nr);\n-\tassert(array2->sorted == array2->nr);\n-\twhile (i1 < array1->nr && i2 < array2->nr) {\n-\t\tstruct ref_entry *e1 = array1->refs[i1];\n-\t\tstruct ref_entry *e2 = array2->refs[i2];\n+\tassert(dir1->sorted == dir1->nr);\n+\tassert(dir2->sorted == dir2->nr);\n+\twhile (i1 < dir1->nr && i2 < dir2->nr) {\n+\t\tstruct ref_entry *e1 = dir1->entries[i1];\n+\t\tstruct ref_entry *e2 = dir2->entries[i2];\n \t\tint cmp = strcmp(e1->name, e2->name);\n \t\tif (cmp < 0) {\n \t\t\tretval = do_one_ref(base, fn, trim, flags, cb_data, e1);\n@@ -335,12 +335,12 @@ static int do_for_each_ref_in_arrays(struct ref_array *array1,\n \t\tif (retval)\n \t\t\treturn retval;\n \t}\n-\tif (i1 < array1->nr)\n-\t\treturn do_for_each_ref_in_array(array1, i1,\n-\t\t\t\t\t\tbase, fn, trim, flags, cb_data);\n-\tif (i2 < array2->nr)\n-\t\treturn do_for_each_ref_in_array(array2, i2,\n-\t\t\t\t\t\tbase, fn, trim, flags, cb_data);\n+\tif (i1 < dir1->nr)\n+\t\treturn do_for_each_ref_in_dir(dir1, i1,\n+\t\t\t\t\t base, fn, trim, flags, cb_data);\n+\tif (i2 < dir2->nr)\n+\t\treturn do_for_each_ref_in_dir(dir2, i2,\n+\t\t\t\t\t base, fn, trim, flags, cb_data);\n \treturn 0;\n }\n \n@@ -386,17 +386,17 @@ static int name_conflict_fn(const char *existingrefname, const unsigned char *sh\n * operation).\n */\n static int is_refname_available(const char *refname, const char *oldrefname,\n-\t\t\t\tstruct ref_array *array)\n+\t\t\t\tstruct ref_dir *dir)\n {\n \tstruct name_conflict_cb data;\n \tdata.refname = refname;\n \tdata.oldrefname = oldrefname;\n \tdata.conflicting_refname = NULL;\n \n-\tsort_ref_array(array);\n-\tif (do_for_each_ref_in_array(array, 0, \"\", name_conflict_fn,\n-\t\t\t\t 0, DO_FOR_EACH_INCLUDE_BROKEN,\n-\t\t\t\t &data)) {\n+\tsort_ref_dir(dir);\n+\tif (do_for_each_ref_in_dir(dir, 0, \"\", name_conflict_fn,\n+\t\t\t\t 0, DO_FOR_EACH_INCLUDE_BROKEN,\n+\t\t\t\t &data)) {\n \t\terror(\"'%s' exists; cannot create '%s'\",\n \t\t data.conflicting_refname, refname);\n \t\treturn 0;\n@@ -412,8 +412,8 @@ static struct ref_cache {\n \tstruct ref_cache *next;\n \tchar did_loose;\n \tchar did_packed;\n-\tstruct ref_array loose;\n-\tstruct ref_array packed;\n+\tstruct ref_dir loose;\n+\tstruct ref_dir packed;\n \t/* The submodule name, or \"\" for the main repo. */\n \tchar name[FLEX_ARRAY];\n } *ref_cache;\n@@ -421,14 +421,14 @@ static struct ref_cache {\n static void clear_packed_ref_cache(struct ref_cache *refs)\n {\n \tif (refs->did_packed)\n-\t\tclear_ref_array(&refs->packed);\n+\t\tclear_ref_dir(&refs->packed);\n \trefs->did_packed = 0;\n }\n \n static void clear_loose_ref_cache(struct ref_cache *refs)\n {\n \tif (refs->did_loose)\n-\t\tclear_ref_array(&refs->loose);\n+\t\tclear_ref_dir(&refs->loose);\n \trefs->did_loose = 0;\n }\n \n@@ -507,7 +507,7 @@ static const char *parse_ref_line(char *line, unsigned char *sha1)\n \treturn line;\n }\n \n-static void read_packed_refs(FILE *f, struct ref_array *array)\n+static void read_packed_refs(FILE *f, struct ref_dir *dir)\n {\n \tstruct ref_entry *last = NULL;\n \tchar refline[PATH_MAX];\n@@ -529,7 +529,7 @@ static void read_packed_refs(FILE *f, struct ref_array *array)\n \t\trefname = parse_ref_line(refline, sha1);\n \t\tif (refname) {\n \t\t\tlast = create_ref_entry(refname, sha1, flag, 1);\n-\t\t\tadd_ref(array, last);\n+\t\t\tadd_ref(dir, last);\n \t\t\tcontinue;\n \t\t}\n \t\tif (last &&\n@@ -541,7 +541,7 @@ static void read_packed_refs(FILE *f, struct ref_array *array)\n \t}\n }\n \n-static struct ref_array *get_packed_refs(struct ref_cache *refs)\n+static struct ref_dir *get_packed_refs(struct ref_cache *refs)\n {\n \tif (!refs->did_packed) {\n \t\tconst char *packed_refs_file;\n@@ -568,9 +568,9 @@ void add_packed_ref(const char *refname, const unsigned char *sha1)\n }\n \n static void get_ref_dir(struct ref_cache *refs, const char *base,\n-\t\t\tstruct ref_array *array)\n+\t\t\tstruct ref_dir *dir)\n {\n-\tDIR *dir;\n+\tDIR *d;\n \tconst char *path;\n \n \tif (*refs->name)\n@@ -578,9 +578,8 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,\n \telse\n \t\tpath = git_path(\"%s\", base);\n \n-\tdir = opendir(path);\n-\n-\tif (dir) {\n+\td = opendir(path);\n+\tif (d) {\n \t\tstruct dirent *de;\n \t\tint baselen = strlen(base);\n \t\tchar *refname = xmalloc(baselen + 257);\n@@ -589,7 +588,7 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,\n \t\tif (baselen && base[baselen-1] != '/')\n \t\t\trefname[baselen++] = '/';\n \n-\t\twhile ((de = readdir(dir)) != NULL) {\n+\t\twhile ((de = readdir(d)) != NULL) {\n \t\t\tunsigned char sha1[20];\n \t\t\tstruct stat st;\n \t\t\tint flag;\n@@ -610,7 +609,7 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,\n \t\t\tif (stat(refdir, &st) < 0)\n \t\t\t\tcontinue;\n \t\t\tif (S_ISDIR(st.st_mode)) {\n-\t\t\t\tget_ref_dir(refs, refname, array);\n+\t\t\t\tget_ref_dir(refs, refname, dir);\n \t\t\t\tcontinue;\n \t\t\t}\n \t\t\tif (*refs->name) {\n@@ -624,14 +623,14 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,\n \t\t\t\thashclr(sha1);\n \t\t\t\tflag |= REF_ISBROKEN;\n \t\t\t}\n-\t\t\tadd_ref(array, create_ref_entry(refname, sha1, flag, 1));\n+\t\t\tadd_ref(dir, create_ref_entry(refname, sha1, flag, 1));\n \t\t}\n \t\tfree(refname);\n-\t\tclosedir(dir);\n+\t\tclosedir(d);\n \t}\n }\n \n-static struct ref_array *get_loose_refs(struct ref_cache *refs)\n+static struct ref_dir *get_loose_refs(struct ref_cache *refs)\n {\n \tif (!refs->did_loose) {\n \t\tget_ref_dir(refs, \"refs\", &refs->loose);\n@@ -653,9 +652,9 @@ static int resolve_gitlink_packed_ref(struct ref_cache *refs,\n \t\t\t\t const char *refname, unsigned char *sha1)\n {\n \tstruct ref_entry *ref;\n-\tstruct ref_array *array = get_packed_refs(refs);\n+\tstruct ref_dir *dir = get_packed_refs(refs);\n \n-\tref = search_ref_array(array, refname);\n+\tref = search_ref_dir(dir, refname);\n \tif (ref == NULL)\n \t\treturn -1;\n \n@@ -726,8 +725,8 @@ int resolve_gitlink_ref(const char *path, const char *refname, unsigned char *sh\n */\n static int get_packed_ref(const char *refname, unsigned char *sha1)\n {\n-\tstruct ref_array *packed = get_packed_refs(get_ref_cache(NULL));\n-\tstruct ref_entry *entry = search_ref_array(packed, refname);\n+\tstruct ref_dir *packed = get_packed_refs(get_ref_cache(NULL));\n+\tstruct ref_entry *entry = search_ref_dir(packed, refname);\n \tif (entry) {\n \t\thashcpy(sha1, entry->u.value.sha1);\n \t\treturn 0;\n@@ -903,8 +902,8 @@ int peel_ref(const char *refname, unsigned char *sha1)\n \t\treturn -1;\n \n \tif ((flag & REF_ISPACKED)) {\n-\t\tstruct ref_array *array = get_packed_refs(get_ref_cache(NULL));\n-\t\tstruct ref_entry *r = search_ref_array(array, refname);\n+\t\tstruct ref_dir *dir = get_packed_refs(get_ref_cache(NULL));\n+\t\tstruct ref_entry *r = search_ref_dir(dir, refname);\n \n \t\tif (r != NULL && r->flag & REF_KNOWS_PEELED) {\n \t\t\thashcpy(sha1, r->u.value.peeled);\n@@ -962,13 +961,13 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn\n \t\t\t int trim, int flags, void *cb_data)\n {\n \tstruct ref_cache *refs = get_ref_cache(submodule);\n-\tstruct ref_array *packed_refs = get_packed_refs(refs);\n-\tstruct ref_array *loose_refs = get_loose_refs(refs);\n-\tsort_ref_array(packed_refs);\n-\tsort_ref_array(loose_refs);\n-\treturn do_for_each_ref_in_arrays(packed_refs,\n-\t\t\t\t\t loose_refs,\n-\t\t\t\t\t base, fn, trim, flags, cb_data);\n+\tstruct ref_dir *packed_refs = get_packed_refs(refs);\n+\tstruct ref_dir *loose_refs = get_loose_refs(refs);\n+\tsort_ref_dir(packed_refs);\n+\tsort_ref_dir(loose_refs);\n+\treturn do_for_each_ref_in_dirs(packed_refs,\n+\t\t\t\t loose_refs,\n+\t\t\t\t base, fn, trim, flags, cb_data);\n }\n \n static int do_head_ref(const char *submodule, each_ref_fn fn, void *cb_data)\n@@ -1403,9 +1402,9 @@ static struct lock_file packlock;\n static int repack_without_ref(const char *refname)\n {\n \tstruct repack_without_ref_sb data;\n-\tstruct ref_array *packed = get_packed_refs(get_ref_cache(NULL));\n-\tsort_ref_array(packed);\n-\tif (search_ref_array(packed, refname) == NULL)\n+\tstruct ref_dir *packed = get_packed_refs(get_ref_cache(NULL));\n+\tsort_ref_dir(packed);\n+\tif (search_ref_dir(packed, refname) == NULL)\n \t\treturn 0;\n \tdata.refname = refname;\n \tdata.fd = hold_lock_file_for_update(&packlock, git_path(\"packed-refs\"), 0);\n@@ -1413,7 +1412,7 @@ static int repack_without_ref(const char *refname)\n \t\tunable_to_lock_error(git_path(\"packed-refs\"), errno);\n \t\treturn error(\"cannot delete '%s' from packed refs\", refname);\n \t}\n-\tdo_for_each_ref_in_array(packed, 0, \"\", repack_without_ref_fn, 0, 0, &data);\n+\tdo_for_each_ref_in_dir(packed, 0, \"\", repack_without_ref_fn, 0, 0, &data);\n \treturn commit_lock_file(&packlock);\n }\n \n@@ -2024,10 +2023,10 @@ int for_each_reflog_ent(const char *refname, each_reflog_ent_fn fn, void *cb_dat\n \n static int do_for_each_reflog(const char *base, each_ref_fn fn, void *cb_data)\n {\n-\tDIR *dir = opendir(git_path(\"logs/%s\", base));\n+\tDIR *d = opendir(git_path(\"logs/%s\", base));\n \tint retval = 0;\n \n-\tif (dir) {\n+\tif (d) {\n \t\tstruct dirent *de;\n \t\tint baselen = strlen(base);\n \t\tchar *log = xmalloc(baselen + 257);\n@@ -2036,7 +2035,7 @@ static int do_for_each_reflog(const char *base, each_ref_fn fn, void *cb_data)\n \t\tif (baselen && base[baselen-1] != '/')\n \t\t\tlog[baselen++] = '/';\n \n-\t\twhile ((de = readdir(dir)) != NULL) {\n+\t\twhile ((de = readdir(d)) != NULL) {\n \t\t\tstruct stat st;\n \t\t\tint namelen;\n \n@@ -2063,7 +2062,7 @@ static int do_for_each_reflog(const char *base, each_ref_fn fn, void *cb_data)\n \t\t\t\tbreak;\n \t\t}\n \t\tfree(log);\n-\t\tclosedir(dir);\n+\t\tclosedir(d);\n \t}\n \telse if (*base)\n \t\treturn errno;\n-- \n1.7.10\n"},{"id":"188850","messageId":"1334035827-20331-14-git-send-email-mhagger@alum.mit.edu","threadId":"30192","inReplyTo":"1334035827-20331-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 13/15] sort_ref_dir(): simplify logic","fromName":"","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-04-10T05:30:25Z","receivedAt":"2012-04-10T05:30:25Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"From: Michael Haggerty \n\nUse the more usual indexing idiom for clarity.\n\nSigned-off-by: Michael Haggerty \n---\n refs.c | 20 +++++++++++---------\n 1 file changed, 11 insertions(+), 9 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex 4e0cfb2..a3b8428 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -227,11 +227,13 @@ static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2\n }\n \n /*\n- * Sort the entries in dir (if they are not already sorted).\n+ * Sort the entries in dir (if they are not already sorted)\n+ * and remove any duplicate entries.\n */\n static void sort_ref_dir(struct ref_dir *dir)\n {\n \tint i, j;\n+\tstruct ref_entry *last = NULL;\n \n \t/*\n \t * This check also prevents passing a zero-length array to qsort(),\n@@ -242,16 +244,16 @@ static void sort_ref_dir(struct ref_dir *dir)\n \n \tqsort(dir->entries, dir->nr, sizeof(*dir->entries), ref_entry_cmp);\n \n-\t/* Remove any duplicates from the ref_dir */\n-\ti = 0;\n-\tfor (j = 1; j < dir->nr; j++) {\n-\t\tif (is_dup_ref(dir->entries[i], dir->entries[j])) {\n-\t\t\tfree_ref_entry(dir->entries[j]);\n-\t\t\tcontinue;\n+\t/* Remove any duplicates: */\n+\tfor (i = 0, j = 0; j < dir->nr; j++) {\n+\t\tstruct ref_entry *entry = dir->entries[j];\n+\t\tif (last && is_dup_ref(last, entry)) {\n+\t\t\tfree_ref_entry(entry);\n+\t\t} else {\n+\t\t\tlast = dir->entries[i++] = entry;\n \t\t}\n-\t\tdir->entries[++i] = dir->entries[j];\n \t}\n-\tdir->sorted = dir->nr = i + 1;\n+\tdir->sorted = dir->nr = i;\n }\n \n #define DO_FOR_EACH_INCLUDE_BROKEN 01\n-- \n1.7.10\n"},{"id":"188849","messageId":"1334035827-20331-15-git-send-email-mhagger@alum.mit.edu","threadId":"30192","inReplyTo":"1334035827-20331-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 14/15] refs: store references hierarchically","fromName":"","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-04-10T05:30:26Z","receivedAt":"2012-04-10T05:30:26Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"From: Michael Haggerty \n\nStore references hierarchically in a tree that matches the\npseudo-directory structure of the reference names. Add a new kind of\nref_entry (with flag REF_DIR) to represent a whole subdirectory of\nreferences. Sort ref_dirs one subdirectory at a time.\n\nNOTE: the dirs can now be sorted as a side-effect of other function\ncalls. Therefore, it would be problematic to do something from a\neach_ref_fn callback that could provoke the sorting of a directory\nthat is currently being iterated over (i.e., the directory containing\nthe entry that is being processed or any of its parents).\n\nThis is a bit far-fetched, because a directory is always sorted just\nbefore being iterated over. Therefore, read-only accesses cannot\ntrigger the sorting of a directory whose iteration has already\nstarted. But if a callback function would add a reference to a parent\ndirectory of the reference in the iteration, then try to resolve a\nreference under that directory, a re-sort could be triggered and cause\nthe iteration to work incorrectly.\n\nNevertheless...add a comment in refs.h warning against modifications\nduring iteration.\n\nSigned-off-by: Michael Haggerty \n---\n refs.c | 274 +++++++++++++++++++++++++++++++++++++++++++++++++++++-----------\n refs.h | 7 +-\n 2 files changed, 232 insertions(+), 49 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex a3b8428..cdfb53d 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -120,15 +120,54 @@ struct ref_dir {\n \tstruct ref_entry **entries;\n };\n \n-/* ISSYMREF=0x01, ISPACKED=0x02 and ISBROKEN=0x04 are public interfaces */\n-#define REF_KNOWS_PEELED 0x10\n+/* ISSYMREF=0x01, ISPACKED=0x02, and ISBROKEN=0x04 are public interfaces */\n+#define REF_KNOWS_PEELED 0x08\n+#define REF_DIR 0x10\n \n+/*\n+ * A ref_entry represents either a reference or a \"subdirectory\" of\n+ * references. Each directory in the reference namespace is\n+ * represented by a ref_entry with (flags & REF_DIR) set and\n+ * containing a subdir member that holds the entries in that\n+ * directory. References are represented by a ref_entry with (flags &\n+ * REF_DIR) unset and a value member that describes the reference's\n+ * value. The flag member is at the ref_entry level, but it is also\n+ * needed to interpret the contents of the value field (in other\n+ * words, a ref_value object is not very much use without the\n+ * enclosing ref_entry).\n+ *\n+ * Reference names cannot end with slash and directories' names are\n+ * always stored with a trailing slash (except for the top-level\n+ * directory, which is always denoted by \"\"). This has two nice\n+ * consequences: (1) when the entries in each subdir are sorted\n+ * lexicographically by name (as they usually are), the references in\n+ * a whole tree can be generated in lexicographic order by traversing\n+ * the tree in left-to-right, depth-first order; (2) the names of\n+ * references and subdirectories cannot conflict, and therefore the\n+ * presence of an empty subdirectory does not block the creation of a\n+ * similarly-named reference. (The fact that reference names with the\n+ * same leading components can conflict *with each other* is a\n+ * separate issue that is regulated by is_refname_available().)\n+ *\n+ * Please note that the name field contains the fully-qualified\n+ * reference (or subdirectory) name. Space could be saved by only\n+ * storing the relative names. But that would require the full names\n+ * to be generated on the fly when iterating in do_for_each_ref(), and\n+ * would break callback functions, who have always been able to assume\n+ * that the name strings that they are passed will not be freed during\n+ * the iteration.\n+ */\n struct ref_entry {\n \tunsigned char flag; /* ISSYMREF? ISPACKED? */\n \tunion {\n-\t\tstruct ref_value value;\n+\t\tstruct ref_value value; /* if not (flags&REF_DIR) */\n+\t\tstruct ref_dir subdir; /* if (flags&REF_DIR) */\n \t} u;\n-\t/* The full name of the reference (e.g., \"refs/heads/master\"): */\n+\t/*\n+\t * The full name of the reference (e.g., \"refs/heads/master\")\n+\t * or the full name of the directory with a trailing slash\n+\t * (e.g., \"refs/heads/\"):\n+\t */\n \tchar name[FLEX_ARRAY];\n };\n \n@@ -151,18 +190,29 @@ static struct ref_entry *create_ref_entry(const char *refname,\n \treturn ref;\n }\n \n+static void clear_ref_dir(struct ref_dir *dir);\n+\n static void free_ref_entry(struct ref_entry *entry)\n {\n+\tif (entry->flag & REF_DIR)\n+\t\tclear_ref_dir(&entry->u.subdir);\n \tfree(entry);\n }\n \n-/* Add a ref_entry to the end of the ref_dir (unsorted). */\n-static void add_ref(struct ref_dir *refs, struct ref_entry *ref)\n+/*\n+ * Add a ref_entry to the end of dir (unsorted). Entry is always\n+ * stored directly in dir; no recursion into subdirectories is\n+ * done.\n+ */\n+static void add_entry_to_dir(struct ref_dir *dir, struct ref_entry *entry)\n {\n-\tALLOC_GROW(refs->entries, refs->nr + 1, refs->alloc);\n-\trefs->entries[refs->nr++] = ref;\n+\tALLOC_GROW(dir->entries, dir->nr + 1, dir->alloc);\n+\tdir->entries[dir->nr++] = entry;\n }\n \n+/*\n+ * Clear and free all entries in dir, recursively.\n+ */\n static void clear_ref_dir(struct ref_dir *dir)\n {\n \tint i;\n@@ -173,6 +223,21 @@ static void clear_ref_dir(struct ref_dir *dir)\n \tdir->entries = NULL;\n }\n \n+/*\n+ * Create a struct ref_entry object for the specified dirname.\n+ * dirname is the name of the directory with a trailing slash (e.g.,\n+ * \"refs/heads/\") or \"\" for the top-level directory.\n+ */\n+static struct ref_entry *create_dir_entry(const char *dirname)\n+{\n+\tstruct ref_entry *direntry;\n+\tint len = strlen(dirname);\n+\tdirentry = xcalloc(1, sizeof(struct ref_entry) + len + 1);\n+\tmemcpy(direntry->name, dirname, len + 1);\n+\tdirentry->flag = REF_DIR;\n+\treturn direntry;\n+}\n+\n static int ref_entry_cmp(const void *a, const void *b)\n {\n \tstruct ref_entry *one = *(struct ref_entry **)a;\n@@ -182,17 +247,21 @@ static int ref_entry_cmp(const void *a, const void *b)\n \n static void sort_ref_dir(struct ref_dir *dir);\n \n+/*\n+ * Return the entry with the given refname from the ref_dir\n+ * (non-recursively), sorting dir if necessary. Return NULL if no\n+ * such entry is found.\n+ */\n static struct ref_entry *search_ref_dir(struct ref_dir *dir, const char *refname)\n {\n \tstruct ref_entry *e, **r;\n \tint len;\n \n-\tif (refname == NULL)\n+\tif (refname == NULL || !dir->nr)\n \t\treturn NULL;\n \n-\tif (!dir->nr)\n-\t\treturn NULL;\n \tsort_ref_dir(dir);\n+\n \tlen = strlen(refname) + 1;\n \te = xmalloc(sizeof(struct ref_entry) + len);\n \tmemcpy(e->name, refname, len);\n@@ -208,27 +277,96 @@ static struct ref_entry *search_ref_dir(struct ref_dir *dir, const char *refname\n }\n \n /*\n+ * If refname is a reference name, find the ref_dir within the dir\n+ * tree that should hold refname. If refname is a directory name\n+ * (i.e., ends in '/'), then return that ref_dir itself. dir must\n+ * represent the top-level directory. Sort ref_dirs and recurse into\n+ * subdirectories as necessary. If mkdir is set, then create any\n+ * missing directories; otherwise, return NULL if the desired\n+ * directory cannot be found.\n+ */\n+static struct ref_dir *find_containing_dir(struct ref_dir *dir,\n+\t\t\t\t\t const char *refname, int mkdir)\n+{\n+\tchar *refname_copy = xstrdup(refname);\n+\tchar *slash;\n+\tstruct ref_entry *entry;\n+\tfor (slash = strchr(refname_copy, '/'); slash; slash = strchr(slash + 1, '/')) {\n+\t\tchar tmp = slash[1];\n+\t\tslash[1] = '\\0';\n+\t\tentry = search_ref_dir(dir, refname_copy);\n+\t\tif (!entry) {\n+\t\t\tif (!mkdir) {\n+\t\t\t\tdir = NULL;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tentry = create_dir_entry(refname_copy);\n+\t\t\tadd_entry_to_dir(dir, entry);\n+\t\t}\n+\t\tslash[1] = tmp;\n+\t\tassert(entry->flag & REF_DIR);\n+\t\tdir = &entry->u.subdir;\n+\t}\n+\n+\tfree(refname_copy);\n+\treturn dir;\n+}\n+\n+/*\n+ * Find the value entry with the given name in dir, sorting ref_dirs\n+ * and recursing into subdirectories as necessary. If the name is not\n+ * found or it corresponds to a directory entry, return NULL.\n+ */\n+static struct ref_entry *find_ref(struct ref_dir *dir, const char *refname)\n+{\n+\tstruct ref_entry *entry;\n+\tdir = find_containing_dir(dir, refname, 0);\n+\tif (!dir)\n+\t\treturn NULL;\n+\tentry = search_ref_dir(dir, refname);\n+\treturn (entry && !(entry->flag & REF_DIR)) ? entry : NULL;\n+}\n+\n+/*\n+ * Add a ref_entry to the ref_dir (unsorted), recursing into\n+ * subdirectories as necessary. dir must represent the top-level\n+ * directory. Return 0 on success.\n+ */\n+static int add_ref(struct ref_dir *dir, struct ref_entry *ref)\n+{\n+\tdir = find_containing_dir(dir, ref->name, 1);\n+\tif (!dir)\n+\t\treturn -1;\n+\tadd_entry_to_dir(dir, ref);\n+\treturn 0;\n+}\n+\n+/*\n * Emit a warning and return true iff ref1 and ref2 have the same name\n * and the same sha1. Die if they have the same name but different\n * sha1s.\n */\n static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2)\n {\n-\tif (!strcmp(ref1->name, ref2->name)) {\n-\t\t/* Duplicate name; make sure that the SHA1s match: */\n-\t\tif (hashcmp(ref1->u.value.sha1, ref2->u.value.sha1))\n-\t\t\tdie(\"Duplicated ref, and SHA1s don't match: %s\",\n-\t\t\t ref1->name);\n-\t\twarning(\"Duplicated ref: %s\", ref1->name);\n-\t\treturn 1;\n-\t} else {\n+\tif (strcmp(ref1->name, ref2->name))\n \t\treturn 0;\n-\t}\n+\n+\t/* Duplicate name; make sure that they don't conflict: */\n+\n+\tif ((ref1->flag & REF_DIR) || (ref2->flag & REF_DIR))\n+\t\t/* This is impossible by construction */\n+\t\tdie(\"Reference directory conflict: %s\", ref1->name);\n+\n+\tif (hashcmp(ref1->u.value.sha1, ref2->u.value.sha1))\n+\t\tdie(\"Duplicated ref, and SHA1s don't match: %s\", ref1->name);\n+\n+\twarning(\"Duplicated ref: %s\", ref1->name);\n+\treturn 1;\n }\n \n /*\n- * Sort the entries in dir (if they are not already sorted)\n- * and remove any duplicate entries.\n+ * Sort the entries in dir non-recursively (if they are not already\n+ * sorted) and remove any duplicate entries.\n */\n static void sort_ref_dir(struct ref_dir *dir)\n {\n@@ -283,8 +421,9 @@ static int do_one_ref(const char *base, each_ref_fn fn, int trim,\n \n /*\n * Call fn for each reference in dir that has index in the range\n- * offset <= index < dir->nr. This function does not sort the dir;\n- * sorting should be done by the caller.\n+ * offset <= index < dir->nr. Recurse into subdirectories that are in\n+ * that index range, sorting them before iterating. This function\n+ * does not sort dir itself; it should be sorted beforehand.\n */\n static int do_for_each_ref_in_dir(struct ref_dir *dir, int offset,\n \t\t\t\t const char *base,\n@@ -293,7 +432,15 @@ static int do_for_each_ref_in_dir(struct ref_dir *dir, int offset,\n \tint i;\n \tassert(dir->sorted == dir->nr);\n \tfor (i = offset; i < dir->nr; i++) {\n-\t\tint retval = do_one_ref(base, fn, trim, flags, cb_data, dir->entries[i]);\n+\t\tstruct ref_entry *entry = dir->entries[i];\n+\t\tint retval;\n+\t\tif (entry->flag & REF_DIR) {\n+\t\t\tsort_ref_dir(&entry->u.subdir);\n+\t\t\tretval = do_for_each_ref_in_dir(&entry->u.subdir, 0,\n+\t\t\t\t\t\t\tbase, fn, trim, flags, cb_data);\n+\t\t} else {\n+\t\t\tretval = do_one_ref(base, fn, trim, flags, cb_data, entry);\n+\t\t}\n \t\tif (retval)\n \t\t\treturn retval;\n \t}\n@@ -302,9 +449,10 @@ static int do_for_each_ref_in_dir(struct ref_dir *dir, int offset,\n \n /*\n * Call fn for each reference in the union of dir1 and dir2, in order\n- * by refname. If an entry appears in both dir1 and dir2, then only\n- * process the version that is in dir2. The input dirs must already\n- * be sorted.\n+ * by refname. Recurse into subdirectories. If a value entry appears\n+ * in both dir1 and dir2, then only process the version that is in\n+ * dir2. The input dirs must already be sorted, but subdirs will be\n+ * sorted as needed.\n */\n static int do_for_each_ref_in_dirs(struct ref_dir *dir1,\n \t\t\t\t struct ref_dir *dir2,\n@@ -316,22 +464,55 @@ static int do_for_each_ref_in_dirs(struct ref_dir *dir1,\n \n \tassert(dir1->sorted == dir1->nr);\n \tassert(dir2->sorted == dir2->nr);\n-\twhile (i1 < dir1->nr && i2 < dir2->nr) {\n-\t\tstruct ref_entry *e1 = dir1->entries[i1];\n-\t\tstruct ref_entry *e2 = dir2->entries[i2];\n-\t\tint cmp = strcmp(e1->name, e2->name);\n-\t\tif (cmp < 0) {\n-\t\t\tretval = do_one_ref(base, fn, trim, flags, cb_data, e1);\n-\t\t\ti1++;\n+\twhile (1) {\n+\t\tstruct ref_entry *e1, *e2;\n+\t\tint cmp;\n+\t\tif (i1 == dir1->nr) {\n+\t\t\treturn do_for_each_ref_in_dir(dir2, i2,\n+\t\t\t\t\t\t base, fn, trim, flags, cb_data);\n+\t\t}\n+\t\tif (i2 == dir2->nr) {\n+\t\t\treturn do_for_each_ref_in_dir(dir1, i1,\n+\t\t\t\t\t\t base, fn, trim, flags, cb_data);\n+\t\t}\n+\t\te1 = dir1->entries[i1];\n+\t\te2 = dir2->entries[i2];\n+\t\tcmp = strcmp(e1->name, e2->name);\n+\t\tif (cmp == 0) {\n+\t\t\tif ((e1->flag & REF_DIR) && (e2->flag & REF_DIR)) {\n+\t\t\t\t/* Both are directories; descend them in parallel. */\n+\t\t\t\tsort_ref_dir(&e1->u.subdir);\n+\t\t\t\tsort_ref_dir(&e2->u.subdir);\n+\t\t\t\tretval = do_for_each_ref_in_dirs(\n+\t\t\t\t\t\t&e1->u.subdir, &e2->u.subdir,\n+\t\t\t\t\t\tbase, fn, trim, flags, cb_data);\n+\t\t\t\ti1++;\n+\t\t\t\ti2++;\n+\t\t\t} else if (!(e1->flag & REF_DIR) && !(e2->flag & REF_DIR)) {\n+\t\t\t\t/* Both are references; ignore the one from dir1. */\n+\t\t\t\tretval = do_one_ref(base, fn, trim, flags, cb_data, e2);\n+\t\t\t\ti1++;\n+\t\t\t\ti2++;\n+\t\t\t} else {\n+\t\t\t\tdie(\"conflict between reference and directory: %s\",\n+\t\t\t\t e1->name);\n+\t\t\t}\n \t\t} else {\n-\t\t\tretval = do_one_ref(base, fn, trim, flags, cb_data, e2);\n-\t\t\ti2++;\n-\t\t\tif (cmp == 0) {\n-\t\t\t\t/*\n-\t\t\t\t * There was a ref in array1 with the\n-\t\t\t\t * same name; ignore it.\n-\t\t\t\t */\n+\t\t\tstruct ref_entry *e;\n+\t\t\tif (cmp < 0) {\n+\t\t\t\te = e1;\n \t\t\t\ti1++;\n+\t\t\t} else {\n+\t\t\t\te = e2;\n+\t\t\t\ti2++;\n+\t\t\t}\n+\t\t\tif (e->flag & REF_DIR) {\n+\t\t\t\tsort_ref_dir(&e->u.subdir);\n+\t\t\t\tretval = do_for_each_ref_in_dir(\n+\t\t\t\t\t\t&e->u.subdir, 0,\n+\t\t\t\t\t\tbase, fn, trim, flags, cb_data);\n+\t\t\t} else {\n+\t\t\t\tretval = do_one_ref(base, fn, trim, flags, cb_data, e);\n \t\t\t}\n \t\t}\n \t\tif (retval)\n@@ -656,7 +837,7 @@ static int resolve_gitlink_packed_ref(struct ref_cache *refs,\n \tstruct ref_entry *ref;\n \tstruct ref_dir *dir = get_packed_refs(refs);\n \n-\tref = search_ref_dir(dir, refname);\n+\tref = find_ref(dir, refname);\n \tif (ref == NULL)\n \t\treturn -1;\n \n@@ -728,7 +909,7 @@ int resolve_gitlink_ref(const char *path, const char *refname, unsigned char *sh\n static int get_packed_ref(const char *refname, unsigned char *sha1)\n {\n \tstruct ref_dir *packed = get_packed_refs(get_ref_cache(NULL));\n-\tstruct ref_entry *entry = search_ref_dir(packed, refname);\n+\tstruct ref_entry *entry = find_ref(packed, refname);\n \tif (entry) {\n \t\thashcpy(sha1, entry->u.value.sha1);\n \t\treturn 0;\n@@ -905,7 +1086,7 @@ int peel_ref(const char *refname, unsigned char *sha1)\n \n \tif ((flag & REF_ISPACKED)) {\n \t\tstruct ref_dir *dir = get_packed_refs(get_ref_cache(NULL));\n-\t\tstruct ref_entry *r = search_ref_dir(dir, refname);\n+\t\tstruct ref_entry *r = find_ref(dir, refname);\n \n \t\tif (r != NULL && r->flag & REF_KNOWS_PEELED) {\n \t\t\thashcpy(sha1, r->u.value.peeled);\n@@ -1405,8 +1586,7 @@ static int repack_without_ref(const char *refname)\n {\n \tstruct repack_without_ref_sb data;\n \tstruct ref_dir *packed = get_packed_refs(get_ref_cache(NULL));\n-\tsort_ref_dir(packed);\n-\tif (search_ref_dir(packed, refname) == NULL)\n+\tif (find_ref(packed, refname) == NULL)\n \t\treturn 0;\n \tdata.refname = refname;\n \tdata.fd = hold_lock_file_for_update(&packlock, git_path(\"packed-refs\"), 0);\ndiff --git a/refs.h b/refs.h\nindex 33202b0..d6c2fe2 100644\n--- a/refs.h\n+++ b/refs.h\n@@ -15,8 +15,11 @@ struct ref_lock {\n #define REF_ISBROKEN 0x04\n \n /*\n- * Calls the specified function for each ref file until it returns nonzero,\n- * and returns the value\n+ * Calls the specified function for each ref file until it returns\n+ * nonzero, and returns the value. Please note that it is not safe to\n+ * modify references while an iteration is in progress, unless the\n+ * same callback function invocation that modifies the reference also\n+ * returns a nonzero value to immediately stop the iteration.\n */\n typedef int each_ref_fn(const char *refname, const unsigned char *sha1, int flags, void *cb_data);\n extern int head_ref(each_ref_fn, void *);\n-- \n1.7.10\n"},{"id":"188845","messageId":"1334035827-20331-16-git-send-email-mhagger@alum.mit.edu","threadId":"30192","inReplyTo":"1334035827-20331-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 15/15] do_for_each_ref(): only iterate over the subtree that was requested","fromName":"","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-04-10T05:30:27Z","receivedAt":"2012-04-10T05:30:27Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"From: Michael Haggerty \n\nIf the base argument has a \"/\" chararacter, then only iterate over the\nreference subdir whose name is the part up to the last \"/\".\n\nSigned-off-by: Michael Haggerty \n---\n refs.c | 35 ++++++++++++++++++++++++++++-------\n 1 file changed, 28 insertions(+), 7 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex cdfb53d..f97a256 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -1144,13 +1144,34 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn\n \t\t\t int trim, int flags, void *cb_data)\n {\n \tstruct ref_cache *refs = get_ref_cache(submodule);\n-\tstruct ref_dir *packed_refs = get_packed_refs(refs);\n-\tstruct ref_dir *loose_refs = get_loose_refs(refs);\n-\tsort_ref_dir(packed_refs);\n-\tsort_ref_dir(loose_refs);\n-\treturn do_for_each_ref_in_dirs(packed_refs,\n-\t\t\t\t loose_refs,\n-\t\t\t\t base, fn, trim, flags, cb_data);\n+\tstruct ref_dir *packed_dir = get_packed_refs(refs);\n+\tstruct ref_dir *loose_dir = get_loose_refs(refs);\n+\tint retval = 0;\n+\n+\tif (base && *base) {\n+\t\tpacked_dir = find_containing_dir(packed_dir, base, 0);\n+\t\tloose_dir = find_containing_dir(loose_dir, base, 0);\n+\t}\n+\n+\tif (packed_dir && loose_dir) {\n+\t\tsort_ref_dir(packed_dir);\n+\t\tsort_ref_dir(loose_dir);\n+\t\tretval = do_for_each_ref_in_dirs(\n+\t\t\t\tpacked_dir, loose_dir,\n+\t\t\t\tbase, fn, trim, flags, cb_data);\n+\t} else if (packed_dir) {\n+\t\tsort_ref_dir(packed_dir);\n+\t\tretval = do_for_each_ref_in_dir(\n+\t\t\t\tpacked_dir, 0,\n+\t\t\t\tbase, fn, trim, flags, cb_data);\n+\t} else if (loose_dir) {\n+\t\tsort_ref_dir(loose_dir);\n+\t\tretval = do_for_each_ref_in_dir(\n+\t\t\t\tloose_dir, 0,\n+\t\t\t\tbase, fn, trim, flags, cb_data);\n+\t}\n+\n+\treturn retval;\n }\n \n static int do_head_ref(const char *submodule, each_ref_fn fn, void *cb_data)\n-- \n1.7.10\n"},{"id":"189080","messageId":"20120412064459.GD27369@sigill.intra.peff.net","threadId":"30192","inReplyTo":"1334035827-20331-1-git-send-email-mhagger@alum.mit.edu","subject":"Re: [PATCH 00/15] Hierarchical reference cache (once again)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-04-12T06:44:59Z","receivedAt":"2012-04-12T06:44:59Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Apr 10, 2012 at 07:30:12AM +0200, mhagger@alum.mit.edu wrote:\n\n> Michael Haggerty (15):\n> refs.c: reorder definitions more logically\n> refs: manage current_ref within do_one_ref()\n> do_for_each_ref_in_array(): new function\n> do_for_each_ref_in_arrays(): new function\n> repack_without_ref(): reimplement using do_for_each_ref_in_array()\n> names_conflict(): new function, extracted from is_refname_available()\n> names_conflict(): simplify implementation\n> is_refname_available(): reimplement using do_for_each_ref_in_array()\n> free_ref_entry(): new function\n> check_refname_component(): return 0 for zero-length components\n> struct ref_entry: nest the value part in a union\n> refs.c: rename ref_array -> ref_dir\n> sort_ref_dir(): simplify logic\n> refs: store references hierarchically\n> do_for_each_ref(): only iterate over the subtree that was requested\n\nI read through the whole series and didn't find anything noticeably\nwrong. Overall, it was quite readable for such a large series. Thanks\nfor breaking it up as you did.\n\n-Peff\n"},{"id":"189110","messageId":"7v4nspgdxv.fsf@alter.siamese.dyndns.org","threadId":"30192","inReplyTo":"20120412064459.GD27369@sigill.intra.peff.net","subject":"Re: [PATCH 00/15] Hierarchical reference cache (once again)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-04-12T15:36:12Z","receivedAt":"2012-04-12T15:36:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Tue, Apr 10, 2012 at 07:30:12AM +0200, mhagger@alum.mit.edu wrote:\n>\n>> Michael Haggerty (15):\n>> refs.c: reorder definitions more logically\n>> ...\n>\n> I read through the whole series and didn't find anything noticeably\n> wrong. Overall, it was quite readable for such a large series. Thanks\n> for breaking it up as you did.\n\nI hate myself doing this, but...\n\n\t me too! \n\nThe series looked very readable, unlike the previous huge rounds.\n\nThanks.\n"}]}