[PATCH 00/15] Hierarchical reference cache (once again)

[PATCH 00/15] Hierarchical reference cache (once again)

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

Here is another installment of the "hierarchical refs" saga.  This
patch series (obviously) builds on the changes in master that removed
extra_refs.  This group of patches does some cleanup then makes the
transition to storing reference caches hierarchically.  It also
includes the first benefit of the hierarchical storage scheme, namely
that searching for individual references becomes more efficient
(though as yet all references are read into the cache if any
references are needed, so the benefit is limited).

I will have limited Internet connectivity for the next week, so I
apologize in advance if I don't react quickly to feedback.  But I
wanted to throw at least part of this reworked "ref-api" patch series
back into the ring while the new release cycle is still fresh.

Michael Haggerty (15):
  refs.c: reorder definitions more logically
  refs: manage current_ref within do_one_ref()
  do_for_each_ref_in_array(): new function
  do_for_each_ref_in_arrays(): new function
  repack_without_ref(): reimplement using do_for_each_ref_in_array()
  names_conflict(): new function, extracted from is_refname_available()
  names_conflict(): simplify implementation
  is_refname_available(): reimplement using do_for_each_ref_in_array()
  free_ref_entry(): new function
  check_refname_component(): return 0 for zero-length components
  struct ref_entry: nest the value part in a union
  refs.c: rename ref_array -> ref_dir
  sort_ref_dir(): simplify logic
  refs: store references hierarchically
  do_for_each_ref(): only iterate over the subtree that was requested

 refs.c | 1036 +++++++++++++++++++++++++++++++++++++++++-----------------------
 refs.h |    7 +-
 2 files changed, 670 insertions(+), 373 deletions(-)

-- 
1.7.10

[PATCH 01/15] refs.c: reorder definitions more logically

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

Reorder definitions in file: first check_refname_format() and helper
functions, then the functions for managing the ref_entry and ref_array
data structures, then ref_cache, then the more "business-logicky"
stuff.  No code is changed.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |  509 ++++++++++++++++++++++++++++++++--------------------------------
 1 file changed, 256 insertions(+), 253 deletions(-)

diff --git a/refs.c b/refs.c
index c9f6835..0c9ca4c 100644
--- a/refs.c
+++ b/refs.c
@@ -4,16 +4,102 @@
 #include "tag.h"
 #include "dir.h"
 
-/* ISSYMREF=0x01, ISPACKED=0x02 and ISBROKEN=0x04 are public interfaces */
-#define REF_KNOWS_PEELED 0x10
+/*
+ * Make sure "ref" is something reasonable to have under ".git/refs/";
+ * We do not like it if:
+ *
+ * - any path component of it begins with ".", or
+ * - it has double dots "..", or
+ * - it has ASCII control character, "~", "^", ":" or SP, anywhere, or
+ * - it ends with a "/".
+ * - it ends with ".lock"
+ * - it contains a "\" (backslash)
+ */
 
-struct ref_entry {
-	unsigned char flag; /* ISSYMREF? ISPACKED? */
-	unsigned char sha1[20];
-	unsigned char peeled[20];
-	/* The full name of the reference (e.g., "refs/heads/master"): */
-	char name[FLEX_ARRAY];
-};
+/* Return true iff ch is not allowed in reference names. */
+static inline int bad_ref_char(int ch)
+{
+	if (((unsigned) ch) <= ' ' || ch == 0x7f ||
+	    ch == '~' || ch == '^' || ch == ':' || ch == '\\')
+		return 1;
+	/* 2.13 Pattern Matching Notation */
+	if (ch == '*' || ch == '?' || ch == '[') /* Unsupported */
+		return 1;
+	return 0;
+}
+
+/*
+ * Try to read one refname component from the front of refname.  Return
+ * the length of the component found, or -1 if the component is not
+ * legal.
+ */
+static int check_refname_component(const char *refname, int flags)
+{
+	const char *cp;
+	char last = '\0';
+
+	for (cp = refname; ; cp++) {
+		char ch = *cp;
+		if (ch == '\0' || ch == '/')
+			break;
+		if (bad_ref_char(ch))
+			return -1; /* Illegal character in refname. */
+		if (last == '.' && ch == '.')
+			return -1; /* Refname contains "..". */
+		if (last == '@' && ch == '{')
+			return -1; /* Refname contains "@{". */
+		last = ch;
+	}
+	if (cp == refname)
+		return -1; /* Component has zero length. */
+	if (refname[0] == '.') {
+		if (!(flags & REFNAME_DOT_COMPONENT))
+			return -1; /* Component starts with '.'. */
+		/*
+		 * Even if leading dots are allowed, don't allow "."
+		 * as a component (".." is prevented by a rule above).
+		 */
+		if (refname[1] == '\0')
+			return -1; /* Component equals ".". */
+	}
+	if (cp - refname >= 5 && !memcmp(cp - 5, ".lock", 5))
+		return -1; /* Refname ends with ".lock". */
+	return cp - refname;
+}
+
+int check_refname_format(const char *refname, int flags)
+{
+	int component_len, component_count = 0;
+
+	while (1) {
+		/* We are at the start of a path component. */
+		component_len = check_refname_component(refname, flags);
+		if (component_len < 0) {
+			if ((flags & REFNAME_REFSPEC_PATTERN) &&
+					refname[0] == '*' &&
+					(refname[1] == '\0' || refname[1] == '/')) {
+				/* Accept one wildcard as a full refname component. */
+				flags &= ~REFNAME_REFSPEC_PATTERN;
+				component_len = 1;
+			} else {
+				return -1;
+			}
+		}
+		component_count++;
+		if (refname[component_len] == '\0')
+			break;
+		/* Skip to next component. */
+		refname += component_len + 1;
+	}
+
+	if (refname[component_len - 1] == '.')
+		return -1; /* Refname ends with '.'. */
+	if (!(flags & REFNAME_ALLOW_ONELEVEL) && component_count < 2)
+		return -1; /* Refname has only one component. */
+	return 0;
+}
+
+struct ref_entry;
 
 struct ref_array {
 	int nr, alloc;
@@ -29,38 +115,16 @@ struct ref_array {
 	struct ref_entry **refs;
 };
 
-/*
- * Parse one line from a packed-refs file.  Write the SHA1 to sha1.
- * Return a pointer to the refname within the line (null-terminated),
- * or NULL if there was a problem.
- */
-static const char *parse_ref_line(char *line, unsigned char *sha1)
-{
-	/*
-	 * 42: the answer to everything.
-	 *
-	 * In this case, it happens to be the answer to
-	 *  40 (length of sha1 hex representation)
-	 *  +1 (space in between hex and name)
-	 *  +1 (newline at the end of the line)
-	 */
-	int len = strlen(line) - 42;
-
-	if (len <= 0)
-		return NULL;
-	if (get_sha1_hex(line, sha1) < 0)
-		return NULL;
-	if (!isspace(line[40]))
-		return NULL;
-	line += 41;
-	if (isspace(*line))
-		return NULL;
-	if (line[len] != '\n')
-		return NULL;
-	line[len] = 0;
+/* ISSYMREF=0x01, ISPACKED=0x02 and ISBROKEN=0x04 are public interfaces */
+#define REF_KNOWS_PEELED 0x10
 
-	return line;
-}
+struct ref_entry {
+	unsigned char flag; /* ISSYMREF? ISPACKED? */
+	unsigned char sha1[20];
+	unsigned char peeled[20];
+	/* The full name of the reference (e.g., "refs/heads/master"): */
+	char name[FLEX_ARRAY];
+};
 
 static struct ref_entry *create_ref_entry(const char *refname,
 					  const unsigned char *sha1, int flag,
@@ -88,6 +152,16 @@ static void add_ref(struct ref_array *refs, struct ref_entry *ref)
 	refs->refs[refs->nr++] = ref;
 }
 
+static void clear_ref_array(struct ref_array *array)
+{
+	int i;
+	for (i = 0; i < array->nr; i++)
+		free(array->refs[i]);
+	free(array->refs);
+	array->sorted = array->nr = array->alloc = 0;
+	array->refs = NULL;
+}
+
 static int ref_entry_cmp(const void *a, const void *b)
 {
 	struct ref_entry *one = *(struct ref_entry **)a;
@@ -95,6 +169,33 @@ static int ref_entry_cmp(const void *a, const void *b)
 	return strcmp(one->name, two->name);
 }
 
+static void sort_ref_array(struct ref_array *array);
+
+static struct ref_entry *search_ref_array(struct ref_array *array, const char *refname)
+{
+	struct ref_entry *e, **r;
+	int len;
+
+	if (refname == NULL)
+		return NULL;
+
+	if (!array->nr)
+		return NULL;
+	sort_ref_array(array);
+	len = strlen(refname) + 1;
+	e = xmalloc(sizeof(struct ref_entry) + len);
+	memcpy(e->name, refname, len);
+
+	r = bsearch(&e, array->refs, array->nr, sizeof(*array->refs), ref_entry_cmp);
+
+	free(e);
+
+	if (r == NULL)
+		return NULL;
+
+	return *r;
+}
+
 /*
  * Emit a warning and return true iff ref1 and ref2 have the same name
  * and the same sha1.  Die if they have the same name but different
@@ -142,29 +243,55 @@ static void sort_ref_array(struct ref_array *array)
 	array->sorted = array->nr = i + 1;
 }
 
-static struct ref_entry *search_ref_array(struct ref_array *array, const char *refname)
-{
-	struct ref_entry *e, **r;
-	int len;
-
-	if (refname == NULL)
-		return NULL;
-
-	if (!array->nr)
-		return NULL;
-	sort_ref_array(array);
-	len = strlen(refname) + 1;
-	e = xmalloc(sizeof(struct ref_entry) + len);
-	memcpy(e->name, refname, len);
+#define DO_FOR_EACH_INCLUDE_BROKEN 01
 
-	r = bsearch(&e, array->refs, array->nr, sizeof(*array->refs), ref_entry_cmp);
+static struct ref_entry *current_ref;
 
-	free(e);
+static int do_one_ref(const char *base, each_ref_fn fn, int trim,
+		      int flags, void *cb_data, struct ref_entry *entry)
+{
+	if (prefixcmp(entry->name, base))
+		return 0;
 
-	if (r == NULL)
-		return NULL;
+	if (!(flags & DO_FOR_EACH_INCLUDE_BROKEN)) {
+		if (entry->flag & REF_ISBROKEN)
+			return 0; /* ignore broken refs e.g. dangling symref */
+		if (!has_sha1_file(entry->sha1)) {
+			error("%s does not point to a valid object!", entry->name);
+			return 0;
+		}
+	}
+	current_ref = entry;
+	return fn(entry->name + trim, entry->sha1, entry->flag, cb_data);
+}
 
-	return *r;
+/*
+ * Return true iff a reference named refname could be created without
+ * conflicting with the name of an existing reference.  If oldrefname
+ * is non-NULL, ignore potential conflicts with oldrefname (e.g.,
+ * because oldrefname is scheduled for deletion in the same
+ * operation).
+ */
+static int is_refname_available(const char *refname, const char *oldrefname,
+				struct ref_array *array)
+{
+	int i, namlen = strlen(refname); /* e.g. 'foo/bar' */
+	for (i = 0; i < array->nr; i++ ) {
+		struct ref_entry *entry = array->refs[i];
+		/* entry->name could be 'foo' or 'foo/bar/baz' */
+		if (!oldrefname || strcmp(oldrefname, entry->name)) {
+			int len = strlen(entry->name);
+			int cmplen = (namlen < len) ? namlen : len;
+			const char *lead = (namlen < len) ? entry->name : refname;
+			if (!strncmp(refname, entry->name, cmplen) &&
+			    lead[cmplen] == '/') {
+				error("'%s' exists; cannot create '%s'",
+				      entry->name, refname);
+				return 0;
+			}
+		}
+	}
+	return 1;
 }
 
 /*
@@ -181,18 +308,6 @@ static struct ref_cache {
 	char name[FLEX_ARRAY];
 } *ref_cache;
 
-static struct ref_entry *current_ref;
-
-static void clear_ref_array(struct ref_array *array)
-{
-	int i;
-	for (i = 0; i < array->nr; i++)
-		free(array->refs[i]);
-	free(array->refs);
-	array->sorted = array->nr = array->alloc = 0;
-	array->refs = NULL;
-}
-
 static void clear_packed_ref_cache(struct ref_cache *refs)
 {
 	if (refs->did_packed)
@@ -249,6 +364,39 @@ void invalidate_ref_cache(const char *submodule)
 	clear_loose_ref_cache(refs);
 }
 
+/*
+ * Parse one line from a packed-refs file.  Write the SHA1 to sha1.
+ * Return a pointer to the refname within the line (null-terminated),
+ * or NULL if there was a problem.
+ */
+static const char *parse_ref_line(char *line, unsigned char *sha1)
+{
+	/*
+	 * 42: the answer to everything.
+	 *
+	 * In this case, it happens to be the answer to
+	 *  40 (length of sha1 hex representation)
+	 *  +1 (space in between hex and name)
+	 *  +1 (newline at the end of the line)
+	 */
+	int len = strlen(line) - 42;
+
+	if (len <= 0)
+		return NULL;
+	if (get_sha1_hex(line, sha1) < 0)
+		return NULL;
+	if (!isspace(line[40]))
+		return NULL;
+	line += 41;
+	if (isspace(*line))
+		return NULL;
+	if (line[len] != '\n')
+		return NULL;
+	line[len] = 0;
+
+	return line;
+}
+
 static void read_packed_refs(FILE *f, struct ref_array *array)
 {
 	struct ref_entry *last = NULL;
@@ -320,7 +468,6 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,
 	else
 		path = git_path("%s", base);
 
-
 	dir = opendir(path);
 
 	if (dir) {
@@ -374,40 +521,6 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,
 	}
 }
 
-struct warn_if_dangling_data {
-	FILE *fp;
-	const char *refname;
-	const char *msg_fmt;
-};
-
-static int warn_if_dangling_symref(const char *refname, const unsigned char *sha1,
-				   int flags, void *cb_data)
-{
-	struct warn_if_dangling_data *d = cb_data;
-	const char *resolves_to;
-	unsigned char junk[20];
-
-	if (!(flags & REF_ISSYMREF))
-		return 0;
-
-	resolves_to = resolve_ref_unsafe(refname, junk, 0, NULL);
-	if (!resolves_to || strcmp(resolves_to, d->refname))
-		return 0;
-
-	fprintf(d->fp, d->msg_fmt, refname);
-	return 0;
-}
-
-void warn_dangling_symref(FILE *fp, const char *msg_fmt, const char *refname)
-{
-	struct warn_if_dangling_data data;
-
-	data.fp = fp;
-	data.refname = refname;
-	data.msg_fmt = msg_fmt;
-	for_each_rawref(warn_if_dangling_symref, &data);
-}
-
 static struct ref_array *get_loose_refs(struct ref_cache *refs)
 {
 	if (!refs->did_loose) {
@@ -645,23 +758,10 @@ int read_ref(const char *refname, unsigned char *sha1)
 	return read_ref_full(refname, sha1, 1, NULL);
 }
 
-#define DO_FOR_EACH_INCLUDE_BROKEN 01
-static int do_one_ref(const char *base, each_ref_fn fn, int trim,
-		      int flags, void *cb_data, struct ref_entry *entry)
+int ref_exists(const char *refname)
 {
-	if (prefixcmp(entry->name, base))
-		return 0;
-
-	if (!(flags & DO_FOR_EACH_INCLUDE_BROKEN)) {
-		if (entry->flag & REF_ISBROKEN)
-			return 0; /* ignore broken refs e.g. dangling symref */
-		if (!has_sha1_file(entry->sha1)) {
-			error("%s does not point to a valid object!", entry->name);
-			return 0;
-		}
-	}
-	current_ref = entry;
-	return fn(entry->name + trim, entry->sha1, entry->flag, cb_data);
+	unsigned char sha1[20];
+	return !!resolve_ref_unsafe(refname, sha1, 1, NULL);
 }
 
 static int filter_refs(const char *refname, const unsigned char *sha1, int flags,
@@ -714,6 +814,40 @@ fallback:
 	return -1;
 }
 
+struct warn_if_dangling_data {
+	FILE *fp;
+	const char *refname;
+	const char *msg_fmt;
+};
+
+static int warn_if_dangling_symref(const char *refname, const unsigned char *sha1,
+				   int flags, void *cb_data)
+{
+	struct warn_if_dangling_data *d = cb_data;
+	const char *resolves_to;
+	unsigned char junk[20];
+
+	if (!(flags & REF_ISSYMREF))
+		return 0;
+
+	resolves_to = resolve_ref_unsafe(refname, junk, 0, NULL);
+	if (!resolves_to || strcmp(resolves_to, d->refname))
+		return 0;
+
+	fprintf(d->fp, d->msg_fmt, refname);
+	return 0;
+}
+
+void warn_dangling_symref(FILE *fp, const char *msg_fmt, const char *refname)
+{
+	struct warn_if_dangling_data data;
+
+	data.fp = fp;
+	data.refname = refname;
+	data.msg_fmt = msg_fmt;
+	for_each_rawref(warn_if_dangling_symref, &data);
+}
+
 static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn fn,
 			   int trim, int flags, void *cb_data)
 {
@@ -757,7 +891,6 @@ end_each:
 	return retval;
 }
 
-
 static int do_head_ref(const char *submodule, each_ref_fn fn, void *cb_data)
 {
 	unsigned char sha1[20];
@@ -908,101 +1041,6 @@ int for_each_rawref(each_ref_fn fn, void *cb_data)
 			       DO_FOR_EACH_INCLUDE_BROKEN, cb_data);
 }
 
-/*
- * Make sure "ref" is something reasonable to have under ".git/refs/";
- * We do not like it if:
- *
- * - any path component of it begins with ".", or
- * - it has double dots "..", or
- * - it has ASCII control character, "~", "^", ":" or SP, anywhere, or
- * - it ends with a "/".
- * - it ends with ".lock"
- * - it contains a "\" (backslash)
- */
-
-/* Return true iff ch is not allowed in reference names. */
-static inline int bad_ref_char(int ch)
-{
-	if (((unsigned) ch) <= ' ' || ch == 0x7f ||
-	    ch == '~' || ch == '^' || ch == ':' || ch == '\\')
-		return 1;
-	/* 2.13 Pattern Matching Notation */
-	if (ch == '*' || ch == '?' || ch == '[') /* Unsupported */
-		return 1;
-	return 0;
-}
-
-/*
- * Try to read one refname component from the front of refname.  Return
- * the length of the component found, or -1 if the component is not
- * legal.
- */
-static int check_refname_component(const char *refname, int flags)
-{
-	const char *cp;
-	char last = '\0';
-
-	for (cp = refname; ; cp++) {
-		char ch = *cp;
-		if (ch == '\0' || ch == '/')
-			break;
-		if (bad_ref_char(ch))
-			return -1; /* Illegal character in refname. */
-		if (last == '.' && ch == '.')
-			return -1; /* Refname contains "..". */
-		if (last == '@' && ch == '{')
-			return -1; /* Refname contains "@{". */
-		last = ch;
-	}
-	if (cp == refname)
-		return -1; /* Component has zero length. */
-	if (refname[0] == '.') {
-		if (!(flags & REFNAME_DOT_COMPONENT))
-			return -1; /* Component starts with '.'. */
-		/*
-		 * Even if leading dots are allowed, don't allow "."
-		 * as a component (".." is prevented by a rule above).
-		 */
-		if (refname[1] == '\0')
-			return -1; /* Component equals ".". */
-	}
-	if (cp - refname >= 5 && !memcmp(cp - 5, ".lock", 5))
-		return -1; /* Refname ends with ".lock". */
-	return cp - refname;
-}
-
-int check_refname_format(const char *refname, int flags)
-{
-	int component_len, component_count = 0;
-
-	while (1) {
-		/* We are at the start of a path component. */
-		component_len = check_refname_component(refname, flags);
-		if (component_len < 0) {
-			if ((flags & REFNAME_REFSPEC_PATTERN) &&
-					refname[0] == '*' &&
-					(refname[1] == '\0' || refname[1] == '/')) {
-				/* Accept one wildcard as a full refname component. */
-				flags &= ~REFNAME_REFSPEC_PATTERN;
-				component_len = 1;
-			} else {
-				return -1;
-			}
-		}
-		component_count++;
-		if (refname[component_len] == '\0')
-			break;
-		/* Skip to next component. */
-		refname += component_len + 1;
-	}
-
-	if (refname[component_len - 1] == '.')
-		return -1; /* Refname ends with '.'. */
-	if (!(flags & REFNAME_ALLOW_ONELEVEL) && component_count < 2)
-		return -1; /* Refname has only one component. */
-	return 0;
-}
-
 const char *prettify_refname(const char *name)
 {
 	return name + (
@@ -1073,35 +1111,6 @@ static int remove_empty_directories(const char *file)
 }
 
 /*
- * Return true iff a reference named refname could be created without
- * conflicting with the name of an existing reference.  If oldrefname
- * is non-NULL, ignore potential conflicts with oldrefname (e.g.,
- * because oldrefname is scheduled for deletion in the same
- * operation).
- */
-static int is_refname_available(const char *refname, const char *oldrefname,
-				struct ref_array *array)
-{
-	int i, namlen = strlen(refname); /* e.g. 'foo/bar' */
-	for (i = 0; i < array->nr; i++ ) {
-		struct ref_entry *entry = array->refs[i];
-		/* entry->name could be 'foo' or 'foo/bar/baz' */
-		if (!oldrefname || strcmp(oldrefname, entry->name)) {
-			int len = strlen(entry->name);
-			int cmplen = (namlen < len) ? namlen : len;
-			const char *lead = (namlen < len) ? entry->name : refname;
-			if (!strncmp(refname, entry->name, cmplen) &&
-			    lead[cmplen] == '/') {
-				error("'%s' exists; cannot create '%s'",
-				      entry->name, refname);
-				return 0;
-			}
-		}
-	}
-	return 1;
-}
-
-/*
  * *string and *len will only be substituted, and *string returned (for
  * later free()ing) if the string passed in is a magic short-hand form
  * to name a branch.
@@ -2004,12 +2013,6 @@ int update_ref(const char *action, const char *refname,
 	return 0;
 }
 
-int ref_exists(const char *refname)
-{
-	unsigned char sha1[20];
-	return !!resolve_ref_unsafe(refname, sha1, 1, NULL);
-}
-
 struct ref *find_ref_by_name(const struct ref *list, const char *name)
 {
 	for ( ; list; list = list->next)
-- 
1.7.10

[PATCH 02/15] refs: manage current_ref within do_one_ref()

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

Set and clear current_ref within do_one_ref() instead of setting it
here and leaving it to somebody else to clear it.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |   13 +++++++------
 1 file changed, 7 insertions(+), 6 deletions(-)

diff --git a/refs.c b/refs.c
index 0c9ca4c..20d5300 100644
--- a/refs.c
+++ b/refs.c
@@ -250,6 +250,7 @@ static struct ref_entry *current_ref;
 static int do_one_ref(const char *base, each_ref_fn fn, int trim,
 		      int flags, void *cb_data, struct ref_entry *entry)
 {
+	int retval;
 	if (prefixcmp(entry->name, base))
 		return 0;
 
@@ -262,7 +263,9 @@ static int do_one_ref(const char *base, each_ref_fn fn, int trim,
 		}
 	}
 	current_ref = entry;
-	return fn(entry->name + trim, entry->sha1, entry->flag, cb_data);
+	retval = fn(entry->name + trim, entry->sha1, entry->flag, cb_data);
+	current_ref = NULL;
+	return retval;
 }
 
 /*
@@ -872,7 +875,7 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn
 		}
 		retval = do_one_ref(base, fn, trim, flags, cb_data, entry);
 		if (retval)
-			goto end_each;
+			return retval;
 	}
 
 	if (l < loose->nr) {
@@ -883,12 +886,10 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn
 	for (; p < packed->nr; p++) {
 		retval = do_one_ref(base, fn, trim, flags, cb_data, packed->refs[p]);
 		if (retval)
-			goto end_each;
+			return retval;
 	}
 
-end_each:
-	current_ref = NULL;
-	return retval;
+	return 0;
 }
 
 static int do_head_ref(const char *submodule, each_ref_fn fn, void *cb_data)
-- 
1.7.10

[PATCH 03/15] do_for_each_ref_in_array(): new function

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

Extract function do_for_each_ref_in_array() from do_for_each_ref().
The new function will be a useful building block for storing refs
hierarchically.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |   33 +++++++++++++++++++++++----------
 1 file changed, 23 insertions(+), 10 deletions(-)

diff --git a/refs.c b/refs.c
index 20d5300..263bd81 100644
--- a/refs.c
+++ b/refs.c
@@ -269,6 +269,25 @@ static int do_one_ref(const char *base, each_ref_fn fn, int trim,
 }
 
 /*
+ * Call fn for each reference in array that has index in the range
+ * offset <= index < array->nr.  This function does not sort the
+ * array; sorting should be done by the caller.
+ */
+static int do_for_each_ref_in_array(struct ref_array *array, int offset,
+				    const char *base,
+				    each_ref_fn fn, int trim, int flags, void *cb_data)
+{
+	int i;
+	assert(array->sorted == array->nr);
+	for (i = offset; i < array->nr; i++) {
+		int retval = do_one_ref(base, fn, trim, flags, cb_data, array->refs[i]);
+		if (retval)
+			return retval;
+	}
+	return 0;
+}
+
+/*
  * Return true iff a reference named refname could be created without
  * conflicting with the name of an existing reference.  If oldrefname
  * is non-NULL, ignore potential conflicts with oldrefname (e.g.,
@@ -878,16 +897,10 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn
 			return retval;
 	}
 
-	if (l < loose->nr) {
-		p = l;
-		packed = loose;
-	}
-
-	for (; p < packed->nr; p++) {
-		retval = do_one_ref(base, fn, trim, flags, cb_data, packed->refs[p]);
-		if (retval)
-			return retval;
-	}
+	if (l < loose->nr)
+		return do_for_each_ref_in_array(loose, l, base, fn, trim, flags, cb_data);
+	if (p < packed->nr)
+		return do_for_each_ref_in_array(packed, p, base, fn, trim, flags, cb_data);
 
 	return 0;
 }
-- 
1.7.10

[PATCH 04/15] do_for_each_ref_in_arrays(): new function

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

Extract function do_for_each_ref_in_arrays() from do_for_each_ref().
The new function will be a useful building block for storing refs
hierarchically.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |   82 +++++++++++++++++++++++++++++++++++++++++-----------------------
 1 file changed, 53 insertions(+), 29 deletions(-)

diff --git a/refs.c b/refs.c
index 263bd81..f9a1b57 100644
--- a/refs.c
+++ b/refs.c
@@ -288,6 +288,52 @@ static int do_for_each_ref_in_array(struct ref_array *array, int offset,
 }
 
 /*
+ * Call fn for each reference in the union of array1 and array2, in
+ * order by refname.  If an entry appears in both array1 and array2,
+ * then only process the version that is in array2.  The input arrays
+ * must already be sorted.
+ */
+static int do_for_each_ref_in_arrays(struct ref_array *array1,
+				     struct ref_array *array2,
+				     const char *base, each_ref_fn fn, int trim,
+				     int flags, void *cb_data)
+{
+	int retval;
+	int i1 = 0, i2 = 0;
+
+	assert(array1->sorted == array1->nr);
+	assert(array2->sorted == array2->nr);
+	while (i1 < array1->nr && i2 < array2->nr) {
+		struct ref_entry *e1 = array1->refs[i1];
+		struct ref_entry *e2 = array2->refs[i2];
+		int cmp = strcmp(e1->name, e2->name);
+		if (cmp < 0) {
+			retval = do_one_ref(base, fn, trim, flags, cb_data, e1);
+			i1++;
+		} else {
+			retval = do_one_ref(base, fn, trim, flags, cb_data, e2);
+			i2++;
+			if (cmp == 0) {
+				/*
+				 * There was a ref in array1 with the
+				 * same name; ignore it.
+				 */
+				i1++;
+			}
+		}
+		if (retval)
+			return retval;
+	}
+	if (i1 < array1->nr)
+		return do_for_each_ref_in_array(array1, i1,
+						base, fn, trim, flags, cb_data);
+	if (i2 < array2->nr)
+		return do_for_each_ref_in_array(array2, i2,
+						base, fn, trim, flags, cb_data);
+	return 0;
+}
+
+/*
  * Return true iff a reference named refname could be created without
  * conflicting with the name of an existing reference.  If oldrefname
  * is non-NULL, ignore potential conflicts with oldrefname (e.g.,
@@ -873,36 +919,14 @@ void warn_dangling_symref(FILE *fp, const char *msg_fmt, const char *refname)
 static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn fn,
 			   int trim, int flags, void *cb_data)
 {
-	int retval = 0, p = 0, l = 0;
 	struct ref_cache *refs = get_ref_cache(submodule);
-	struct ref_array *packed = get_packed_refs(refs);
-	struct ref_array *loose = get_loose_refs(refs);
-
-	sort_ref_array(packed);
-	sort_ref_array(loose);
-	while (p < packed->nr && l < loose->nr) {
-		struct ref_entry *entry;
-		int cmp = strcmp(packed->refs[p]->name, loose->refs[l]->name);
-		if (!cmp) {
-			p++;
-			continue;
-		}
-		if (cmp > 0) {
-			entry = loose->refs[l++];
-		} else {
-			entry = packed->refs[p++];
-		}
-		retval = do_one_ref(base, fn, trim, flags, cb_data, entry);
-		if (retval)
-			return retval;
-	}
-
-	if (l < loose->nr)
-		return do_for_each_ref_in_array(loose, l, base, fn, trim, flags, cb_data);
-	if (p < packed->nr)
-		return do_for_each_ref_in_array(packed, p, base, fn, trim, flags, cb_data);
-
-	return 0;
+	struct ref_array *packed_refs = get_packed_refs(refs);
+	struct ref_array *loose_refs = get_loose_refs(refs);
+	sort_ref_array(packed_refs);
+	sort_ref_array(loose_refs);
+	return do_for_each_ref_in_arrays(packed_refs,
+					 loose_refs,
+					 base, fn, trim, flags, cb_data);
 }
 
 static int do_head_ref(const char *submodule, each_ref_fn fn, void *cb_data)
-- 
1.7.10

[PATCH 05/15] repack_without_ref(): reimplement using do_for_each_ref_in_array()

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

It costs a bit of boilerplate, but it means that the function can be
ignorant of how cached refs are stored.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |   51 ++++++++++++++++++++++++++++++---------------------
 1 file changed, 30 insertions(+), 21 deletions(-)

diff --git a/refs.c b/refs.c
index f9a1b57..78dbda6 100644
--- a/refs.c
+++ b/refs.c
@@ -1333,36 +1333,45 @@ struct ref_lock *lock_any_ref_for_update(const char *refname,
 	return lock_ref_sha1_basic(refname, old_sha1, flags, NULL);
 }
 
+struct repack_without_ref_sb {
+	const char *refname;
+	int fd;
+};
+
+static int repack_without_ref_fn(const char *refname, const unsigned char *sha1,
+				 int flags, void *cb_data)
+{
+	struct repack_without_ref_sb *data = cb_data;
+	char line[PATH_MAX + 100];
+	int len;
+
+	if (!strcmp(data->refname, refname))
+		return 0;
+	len = snprintf(line, sizeof(line), "%s %s\n",
+		       sha1_to_hex(sha1), refname);
+	/* this should not happen but just being defensive */
+	if (len > sizeof(line))
+		die("too long a refname '%s'", refname);
+	write_or_die(data->fd, line, len);
+	return 0;
+}
+
 static struct lock_file packlock;
 
 static int repack_without_ref(const char *refname)
 {
-	struct ref_array *packed;
-	int fd, i;
-
-	packed = get_packed_refs(get_ref_cache(NULL));
+	struct repack_without_ref_sb data;
+	struct ref_array *packed = get_packed_refs(get_ref_cache(NULL));
+	sort_ref_array(packed);
 	if (search_ref_array(packed, refname) == NULL)
 		return 0;
-	fd = hold_lock_file_for_update(&packlock, git_path("packed-refs"), 0);
-	if (fd < 0) {
+	data.refname = refname;
+	data.fd = hold_lock_file_for_update(&packlock, git_path("packed-refs"), 0);
+	if (data.fd < 0) {
 		unable_to_lock_error(git_path("packed-refs"), errno);
 		return error("cannot delete '%s' from packed refs", refname);
 	}
-
-	for (i = 0; i < packed->nr; i++) {
-		char line[PATH_MAX + 100];
-		int len;
-		struct ref_entry *ref = packed->refs[i];
-
-		if (!strcmp(refname, ref->name))
-			continue;
-		len = snprintf(line, sizeof(line), "%s %s\n",
-			       sha1_to_hex(ref->sha1), ref->name);
-		/* this should not happen but just being defensive */
-		if (len > sizeof(line))
-			die("too long a refname '%s'", ref->name);
-		write_or_die(fd, line, len);
-	}
+	do_for_each_ref_in_array(packed, 0, "", repack_without_ref_fn, 0, 0, &data);
 	return commit_lock_file(&packlock);
 }
 
-- 
1.7.10

[PATCH 06/15] names_conflict(): new function, extracted from is_refname_available()

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

This costs an extra strlen() in the loop, but even that small price
will be clawed back in the next patch.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |   43 +++++++++++++++++++++++++++++++------------
 1 file changed, 31 insertions(+), 12 deletions(-)

diff --git a/refs.c b/refs.c
index 78dbda6..cdb66d9 100644
--- a/refs.c
+++ b/refs.c
@@ -334,6 +334,30 @@ static int do_for_each_ref_in_arrays(struct ref_array *array1,
 }
 
 /*
+ * Return true iff refname1 and refname2 conflict with each other.
+ * Two reference names conflict if one of them exactly matches the
+ * leading components of the other; e.g., "foo/bar" conflicts with
+ * both "foo" and with "foo/bar/baz" but not with "foo/bar" or
+ * "foo/barbados".
+ */
+static int names_conflict(const char *refname1, const char *refname2)
+{
+	int len1 = strlen(refname1);
+	int len2 = strlen(refname2);
+	int cmplen;
+	const char *lead;
+
+	if (len1 < len2) {
+		cmplen = len1;
+		lead = refname2;
+	} else {
+		cmplen = len2;
+		lead = refname1;
+	}
+	return !strncmp(refname1, refname2, cmplen) && lead[cmplen] == '/';
+}
+
+/*
  * Return true iff a reference named refname could be created without
  * conflicting with the name of an existing reference.  If oldrefname
  * is non-NULL, ignore potential conflicts with oldrefname (e.g.,
@@ -343,20 +367,15 @@ static int do_for_each_ref_in_arrays(struct ref_array *array1,
 static int is_refname_available(const char *refname, const char *oldrefname,
 				struct ref_array *array)
 {
-	int i, namlen = strlen(refname); /* e.g. 'foo/bar' */
+	int i;
 	for (i = 0; i < array->nr; i++ ) {
 		struct ref_entry *entry = array->refs[i];
-		/* entry->name could be 'foo' or 'foo/bar/baz' */
-		if (!oldrefname || strcmp(oldrefname, entry->name)) {
-			int len = strlen(entry->name);
-			int cmplen = (namlen < len) ? namlen : len;
-			const char *lead = (namlen < len) ? entry->name : refname;
-			if (!strncmp(refname, entry->name, cmplen) &&
-			    lead[cmplen] == '/') {
-				error("'%s' exists; cannot create '%s'",
-				      entry->name, refname);
-				return 0;
-			}
+		if (oldrefname && !strcmp(oldrefname, entry->name))
+			continue;
+		if (names_conflict(refname, entry->name)) {
+			error("'%s' exists; cannot create '%s'",
+			      entry->name, refname);
+			return 0;
 		}
 	}
 	return 1;
-- 
1.7.10

[PATCH 07/15] names_conflict(): simplify implementation

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

Save a bunch of lines of code and a couple of strlen() calls.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |   17 ++++-------------
 1 file changed, 4 insertions(+), 13 deletions(-)

diff --git a/refs.c b/refs.c
index cdb66d9..d4f58b8 100644
--- a/refs.c
+++ b/refs.c
@@ -342,19 +342,10 @@ static int do_for_each_ref_in_arrays(struct ref_array *array1,
  */
 static int names_conflict(const char *refname1, const char *refname2)
 {
-	int len1 = strlen(refname1);
-	int len2 = strlen(refname2);
-	int cmplen;
-	const char *lead;
-
-	if (len1 < len2) {
-		cmplen = len1;
-		lead = refname2;
-	} else {
-		cmplen = len2;
-		lead = refname1;
-	}
-	return !strncmp(refname1, refname2, cmplen) && lead[cmplen] == '/';
+	for (; *refname1 && *refname1 == *refname2; refname1++, refname2++)
+		;
+	return (*refname1 == '\0' && *refname2 == '/')
+		|| (*refname1 == '/' && *refname2 == '\0');
 }
 
 /*
-- 
1.7.10

[PATCH 08/15] is_refname_available(): reimplement using do_for_each_ref_in_array()

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

This implementation will survive upcoming changes to the ref_array
data structure.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |   47 ++++++++++++++++++++++++++++++++++-------------
 1 file changed, 34 insertions(+), 13 deletions(-)

diff --git a/refs.c b/refs.c
index d4f58b8..4b94b08 100644
--- a/refs.c
+++ b/refs.c
@@ -348,26 +348,47 @@ static int names_conflict(const char *refname1, const char *refname2)
 		|| (*refname1 == '/' && *refname2 == '\0');
 }
 
+struct name_conflict_cb {
+	const char *refname;
+	const char *oldrefname;
+	const char *conflicting_refname;
+};
+
+static int name_conflict_fn(const char *existingrefname, const unsigned char *sha1,
+			    int flags, void *cb_data)
+{
+	struct name_conflict_cb *data = (struct name_conflict_cb *)cb_data;
+	if (data->oldrefname && !strcmp(data->oldrefname, existingrefname))
+		return 0;
+	if (names_conflict(data->refname, existingrefname)) {
+		data->conflicting_refname = existingrefname;
+		return 1;
+	}
+	return 0;
+}
+
 /*
  * Return true iff a reference named refname could be created without
- * conflicting with the name of an existing reference.  If oldrefname
- * is non-NULL, ignore potential conflicts with oldrefname (e.g.,
- * because oldrefname is scheduled for deletion in the same
+ * conflicting with the name of an existing reference in array.  If
+ * oldrefname is non-NULL, ignore potential conflicts with oldrefname
+ * (e.g., because oldrefname is scheduled for deletion in the same
  * operation).
  */
 static int is_refname_available(const char *refname, const char *oldrefname,
 				struct ref_array *array)
 {
-	int i;
-	for (i = 0; i < array->nr; i++ ) {
-		struct ref_entry *entry = array->refs[i];
-		if (oldrefname && !strcmp(oldrefname, entry->name))
-			continue;
-		if (names_conflict(refname, entry->name)) {
-			error("'%s' exists; cannot create '%s'",
-			      entry->name, refname);
-			return 0;
-		}
+	struct name_conflict_cb data;
+	data.refname = refname;
+	data.oldrefname = oldrefname;
+	data.conflicting_refname = NULL;
+
+	sort_ref_array(array);
+	if (do_for_each_ref_in_array(array, 0, "", name_conflict_fn,
+				     0, DO_FOR_EACH_INCLUDE_BROKEN,
+				     &data)) {
+		error("'%s' exists; cannot create '%s'",
+		      data.conflicting_refname, refname);
+		return 0;
 	}
 	return 1;
 }
-- 
1.7.10

[PATCH 09/15] free_ref_entry(): new function

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

Add a function free_ref_entry().  This function will become nontrivial
when ref_entry (soon) becomes polymorphic.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |    9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)

diff --git a/refs.c b/refs.c
index 4b94b08..8659c3e 100644
--- a/refs.c
+++ b/refs.c
@@ -145,6 +145,11 @@ static struct ref_entry *create_ref_entry(const char *refname,
 	return ref;
 }
 
+static void free_ref_entry(struct ref_entry *entry)
+{
+	free(entry);
+}
+
 /* Add a ref_entry to the end of the ref_array (unsorted). */
 static void add_ref(struct ref_array *refs, struct ref_entry *ref)
 {
@@ -156,7 +161,7 @@ static void clear_ref_array(struct ref_array *array)
 {
 	int i;
 	for (i = 0; i < array->nr; i++)
-		free(array->refs[i]);
+		free_ref_entry(array->refs[i]);
 	free(array->refs);
 	array->sorted = array->nr = array->alloc = 0;
 	array->refs = NULL;
@@ -235,7 +240,7 @@ static void sort_ref_array(struct ref_array *array)
 	i = 0;
 	for (j = 1; j < array->nr; j++) {
 		if (is_dup_ref(array->refs[i], array->refs[j])) {
-			free(array->refs[j]);
+			free_ref_entry(array->refs[j]);
 			continue;
 		}
 		array->refs[++i] = array->refs[j];
-- 
1.7.10

[PATCH 10/15] check_refname_component(): return 0 for zero-length components

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

Return 0 (instead of -1) for zero-length components.  Move the
interpretation of zero-length components as illegal to
check_refname_format().

This will make it easier to extend check_refname_format() to also
check whether directory names are valid.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |    4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/refs.c b/refs.c
index 8659c3e..1f6890b 100644
--- a/refs.c
+++ b/refs.c
@@ -51,7 +51,7 @@ static int check_refname_component(const char *refname, int flags)
 		last = ch;
 	}
 	if (cp == refname)
-		return -1; /* Component has zero length. */
+		return 0; /* Component has zero length. */
 	if (refname[0] == '.') {
 		if (!(flags & REFNAME_DOT_COMPONENT))
 			return -1; /* Component starts with '.'. */
@@ -74,7 +74,7 @@ int check_refname_format(const char *refname, int flags)
 	while (1) {
 		/* We are at the start of a path component. */
 		component_len = check_refname_component(refname, flags);
-		if (component_len < 0) {
+		if (component_len <= 0) {
 			if ((flags & REFNAME_REFSPEC_PATTERN) &&
 					refname[0] == '*' &&
 					(refname[1] == '\0' || refname[1] == '/')) {
-- 
1.7.10

[PATCH 11/15] struct ref_entry: nest the value part in a union

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

This change is obviously silly by itself, but it is a step towards
adding a second member to the union.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |   32 +++++++++++++++++++-------------
 1 file changed, 19 insertions(+), 13 deletions(-)

diff --git a/refs.c b/refs.c
index 1f6890b..416c97f 100644
--- a/refs.c
+++ b/refs.c
@@ -101,6 +101,11 @@ int check_refname_format(const char *refname, int flags)
 
 struct ref_entry;
 
+struct ref_value {
+	unsigned char sha1[20];
+	unsigned char peeled[20];
+};
+
 struct ref_array {
 	int nr, alloc;
 
@@ -120,8 +125,9 @@ struct ref_array {
 
 struct ref_entry {
 	unsigned char flag; /* ISSYMREF? ISPACKED? */
-	unsigned char sha1[20];
-	unsigned char peeled[20];
+	union {
+		struct ref_value value;
+	} u;
 	/* The full name of the reference (e.g., "refs/heads/master"): */
 	char name[FLEX_ARRAY];
 };
@@ -138,8 +144,8 @@ static struct ref_entry *create_ref_entry(const char *refname,
 		die("Reference has invalid format: '%s'", refname);
 	len = strlen(refname) + 1;
 	ref = xmalloc(sizeof(struct ref_entry) + len);
-	hashcpy(ref->sha1, sha1);
-	hashclr(ref->peeled);
+	hashcpy(ref->u.value.sha1, sha1);
+	hashclr(ref->u.value.peeled);
 	memcpy(ref->name, refname, len);
 	ref->flag = flag;
 	return ref;
@@ -210,7 +216,7 @@ static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2
 {
 	if (!strcmp(ref1->name, ref2->name)) {
 		/* Duplicate name; make sure that the SHA1s match: */
-		if (hashcmp(ref1->sha1, ref2->sha1))
+		if (hashcmp(ref1->u.value.sha1, ref2->u.value.sha1))
 			die("Duplicated ref, and SHA1s don't match: %s",
 			    ref1->name);
 		warning("Duplicated ref: %s", ref1->name);
@@ -262,13 +268,13 @@ static int do_one_ref(const char *base, each_ref_fn fn, int trim,
 	if (!(flags & DO_FOR_EACH_INCLUDE_BROKEN)) {
 		if (entry->flag & REF_ISBROKEN)
 			return 0; /* ignore broken refs e.g. dangling symref */
-		if (!has_sha1_file(entry->sha1)) {
+		if (!has_sha1_file(entry->u.value.sha1)) {
 			error("%s does not point to a valid object!", entry->name);
 			return 0;
 		}
 	}
 	current_ref = entry;
-	retval = fn(entry->name + trim, entry->sha1, entry->flag, cb_data);
+	retval = fn(entry->name + trim, entry->u.value.sha1, entry->flag, cb_data);
 	current_ref = NULL;
 	return retval;
 }
@@ -531,7 +537,7 @@ static void read_packed_refs(FILE *f, struct ref_array *array)
 		    strlen(refline) == 42 &&
 		    refline[41] == '\n' &&
 		    !get_sha1_hex(refline + 1, sha1))
-			hashcpy(last->peeled, sha1);
+			hashcpy(last->u.value.peeled, sha1);
 	}
 }
 
@@ -653,7 +659,7 @@ static int resolve_gitlink_packed_ref(struct ref_cache *refs,
 	if (ref == NULL)
 		return -1;
 
-	memcpy(sha1, ref->sha1, 20);
+	memcpy(sha1, ref->u.value.sha1, 20);
 	return 0;
 }
 
@@ -723,7 +729,7 @@ static int get_packed_ref(const char *refname, unsigned char *sha1)
 	struct ref_array *packed = get_packed_refs(get_ref_cache(NULL));
 	struct ref_entry *entry = search_ref_array(packed, refname);
 	if (entry) {
-		hashcpy(sha1, entry->sha1);
+		hashcpy(sha1, entry->u.value.sha1);
 		return 0;
 	}
 	return -1;
@@ -886,10 +892,10 @@ int peel_ref(const char *refname, unsigned char *sha1)
 	if (current_ref && (current_ref->name == refname
 		|| !strcmp(current_ref->name, refname))) {
 		if (current_ref->flag & REF_KNOWS_PEELED) {
-			hashcpy(sha1, current_ref->peeled);
+			hashcpy(sha1, current_ref->u.value.peeled);
 			return 0;
 		}
-		hashcpy(base, current_ref->sha1);
+		hashcpy(base, current_ref->u.value.sha1);
 		goto fallback;
 	}
 
@@ -901,7 +907,7 @@ int peel_ref(const char *refname, unsigned char *sha1)
 		struct ref_entry *r = search_ref_array(array, refname);
 
 		if (r != NULL && r->flag & REF_KNOWS_PEELED) {
-			hashcpy(sha1, r->peeled);
+			hashcpy(sha1, r->u.value.peeled);
 			return 0;
 		}
 	}
-- 
1.7.10

[PATCH 12/15] refs.c: rename ref_array -> ref_dir

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

This purely textual change is in preparation for storing references
hierarchically, when the old ref_array structure will represent one
"directory" of references.  Rename functions that deal with this
structure analogously, and also rename the structure's "refs" member
to "entries".

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |  195 ++++++++++++++++++++++++++++++++--------------------------------
 1 file changed, 97 insertions(+), 98 deletions(-)

diff --git a/refs.c b/refs.c
index 416c97f..4e0cfb2 100644
--- a/refs.c
+++ b/refs.c
@@ -106,7 +106,7 @@ struct ref_value {
 	unsigned char peeled[20];
 };
 
-struct ref_array {
+struct ref_dir {
 	int nr, alloc;
 
 	/*
@@ -117,7 +117,7 @@ struct ref_array {
 	 */
 	int sorted;
 
-	struct ref_entry **refs;
+	struct ref_entry **entries;
 };
 
 /* ISSYMREF=0x01, ISPACKED=0x02 and ISBROKEN=0x04 are public interfaces */
@@ -156,21 +156,21 @@ static void free_ref_entry(struct ref_entry *entry)
 	free(entry);
 }
 
-/* Add a ref_entry to the end of the ref_array (unsorted). */
-static void add_ref(struct ref_array *refs, struct ref_entry *ref)
+/* Add a ref_entry to the end of the ref_dir (unsorted). */
+static void add_ref(struct ref_dir *refs, struct ref_entry *ref)
 {
-	ALLOC_GROW(refs->refs, refs->nr + 1, refs->alloc);
-	refs->refs[refs->nr++] = ref;
+	ALLOC_GROW(refs->entries, refs->nr + 1, refs->alloc);
+	refs->entries[refs->nr++] = ref;
 }
 
-static void clear_ref_array(struct ref_array *array)
+static void clear_ref_dir(struct ref_dir *dir)
 {
 	int i;
-	for (i = 0; i < array->nr; i++)
-		free_ref_entry(array->refs[i]);
-	free(array->refs);
-	array->sorted = array->nr = array->alloc = 0;
-	array->refs = NULL;
+	for (i = 0; i < dir->nr; i++)
+		free_ref_entry(dir->entries[i]);
+	free(dir->entries);
+	dir->sorted = dir->nr = dir->alloc = 0;
+	dir->entries = NULL;
 }
 
 static int ref_entry_cmp(const void *a, const void *b)
@@ -180,9 +180,9 @@ static int ref_entry_cmp(const void *a, const void *b)
 	return strcmp(one->name, two->name);
 }
 
-static void sort_ref_array(struct ref_array *array);
+static void sort_ref_dir(struct ref_dir *dir);
 
-static struct ref_entry *search_ref_array(struct ref_array *array, const char *refname)
+static struct ref_entry *search_ref_dir(struct ref_dir *dir, const char *refname)
 {
 	struct ref_entry *e, **r;
 	int len;
@@ -190,14 +190,14 @@ static struct ref_entry *search_ref_array(struct ref_array *array, const char *r
 	if (refname == NULL)
 		return NULL;
 
-	if (!array->nr)
+	if (!dir->nr)
 		return NULL;
-	sort_ref_array(array);
+	sort_ref_dir(dir);
 	len = strlen(refname) + 1;
 	e = xmalloc(sizeof(struct ref_entry) + len);
 	memcpy(e->name, refname, len);
 
-	r = bsearch(&e, array->refs, array->nr, sizeof(*array->refs), ref_entry_cmp);
+	r = bsearch(&e, dir->entries, dir->nr, sizeof(*dir->entries), ref_entry_cmp);
 
 	free(e);
 
@@ -227,9 +227,9 @@ static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2
 }
 
 /*
- * Sort the entries in array (if they are not already sorted).
+ * Sort the entries in dir (if they are not already sorted).
  */
-static void sort_ref_array(struct ref_array *array)
+static void sort_ref_dir(struct ref_dir *dir)
 {
 	int i, j;
 
@@ -237,21 +237,21 @@ static void sort_ref_array(struct ref_array *array)
 	 * This check also prevents passing a zero-length array to qsort(),
 	 * which is a problem on some platforms.
 	 */
-	if (array->sorted == array->nr)
+	if (dir->sorted == dir->nr)
 		return;
 
-	qsort(array->refs, array->nr, sizeof(*array->refs), ref_entry_cmp);
+	qsort(dir->entries, dir->nr, sizeof(*dir->entries), ref_entry_cmp);
 
-	/* Remove any duplicates from the ref_array */
+	/* Remove any duplicates from the ref_dir */
 	i = 0;
-	for (j = 1; j < array->nr; j++) {
-		if (is_dup_ref(array->refs[i], array->refs[j])) {
-			free_ref_entry(array->refs[j]);
+	for (j = 1; j < dir->nr; j++) {
+		if (is_dup_ref(dir->entries[i], dir->entries[j])) {
+			free_ref_entry(dir->entries[j]);
 			continue;
 		}
-		array->refs[++i] = array->refs[j];
+		dir->entries[++i] = dir->entries[j];
 	}
-	array->sorted = array->nr = i + 1;
+	dir->sorted = dir->nr = i + 1;
 }
 
 #define DO_FOR_EACH_INCLUDE_BROKEN 01
@@ -280,18 +280,18 @@ static int do_one_ref(const char *base, each_ref_fn fn, int trim,
 }
 
 /*
- * Call fn for each reference in array that has index in the range
- * offset <= index < array->nr.  This function does not sort the
- * array; sorting should be done by the caller.
+ * Call fn for each reference in dir that has index in the range
+ * offset <= index < dir->nr.  This function does not sort the dir;
+ * sorting should be done by the caller.
  */
-static int do_for_each_ref_in_array(struct ref_array *array, int offset,
-				    const char *base,
-				    each_ref_fn fn, int trim, int flags, void *cb_data)
+static int do_for_each_ref_in_dir(struct ref_dir *dir, int offset,
+				  const char *base,
+				  each_ref_fn fn, int trim, int flags, void *cb_data)
 {
 	int i;
-	assert(array->sorted == array->nr);
-	for (i = offset; i < array->nr; i++) {
-		int retval = do_one_ref(base, fn, trim, flags, cb_data, array->refs[i]);
+	assert(dir->sorted == dir->nr);
+	for (i = offset; i < dir->nr; i++) {
+		int retval = do_one_ref(base, fn, trim, flags, cb_data, dir->entries[i]);
 		if (retval)
 			return retval;
 	}
@@ -299,24 +299,24 @@ static int do_for_each_ref_in_array(struct ref_array *array, int offset,
 }
 
 /*
- * Call fn for each reference in the union of array1 and array2, in
- * order by refname.  If an entry appears in both array1 and array2,
- * then only process the version that is in array2.  The input arrays
- * must already be sorted.
+ * Call fn for each reference in the union of dir1 and dir2, in order
+ * by refname.  If an entry appears in both dir1 and dir2, then only
+ * process the version that is in dir2.  The input dirs must already
+ * be sorted.
  */
-static int do_for_each_ref_in_arrays(struct ref_array *array1,
-				     struct ref_array *array2,
-				     const char *base, each_ref_fn fn, int trim,
-				     int flags, void *cb_data)
+static int do_for_each_ref_in_dirs(struct ref_dir *dir1,
+				   struct ref_dir *dir2,
+				   const char *base, each_ref_fn fn, int trim,
+				   int flags, void *cb_data)
 {
 	int retval;
 	int i1 = 0, i2 = 0;
 
-	assert(array1->sorted == array1->nr);
-	assert(array2->sorted == array2->nr);
-	while (i1 < array1->nr && i2 < array2->nr) {
-		struct ref_entry *e1 = array1->refs[i1];
-		struct ref_entry *e2 = array2->refs[i2];
+	assert(dir1->sorted == dir1->nr);
+	assert(dir2->sorted == dir2->nr);
+	while (i1 < dir1->nr && i2 < dir2->nr) {
+		struct ref_entry *e1 = dir1->entries[i1];
+		struct ref_entry *e2 = dir2->entries[i2];
 		int cmp = strcmp(e1->name, e2->name);
 		if (cmp < 0) {
 			retval = do_one_ref(base, fn, trim, flags, cb_data, e1);
@@ -335,12 +335,12 @@ static int do_for_each_ref_in_arrays(struct ref_array *array1,
 		if (retval)
 			return retval;
 	}
-	if (i1 < array1->nr)
-		return do_for_each_ref_in_array(array1, i1,
-						base, fn, trim, flags, cb_data);
-	if (i2 < array2->nr)
-		return do_for_each_ref_in_array(array2, i2,
-						base, fn, trim, flags, cb_data);
+	if (i1 < dir1->nr)
+		return do_for_each_ref_in_dir(dir1, i1,
+					      base, fn, trim, flags, cb_data);
+	if (i2 < dir2->nr)
+		return do_for_each_ref_in_dir(dir2, i2,
+					      base, fn, trim, flags, cb_data);
 	return 0;
 }
 
@@ -386,17 +386,17 @@ static int name_conflict_fn(const char *existingrefname, const unsigned char *sh
  * operation).
  */
 static int is_refname_available(const char *refname, const char *oldrefname,
-				struct ref_array *array)
+				struct ref_dir *dir)
 {
 	struct name_conflict_cb data;
 	data.refname = refname;
 	data.oldrefname = oldrefname;
 	data.conflicting_refname = NULL;
 
-	sort_ref_array(array);
-	if (do_for_each_ref_in_array(array, 0, "", name_conflict_fn,
-				     0, DO_FOR_EACH_INCLUDE_BROKEN,
-				     &data)) {
+	sort_ref_dir(dir);
+	if (do_for_each_ref_in_dir(dir, 0, "", name_conflict_fn,
+				   0, DO_FOR_EACH_INCLUDE_BROKEN,
+				   &data)) {
 		error("'%s' exists; cannot create '%s'",
 		      data.conflicting_refname, refname);
 		return 0;
@@ -412,8 +412,8 @@ static struct ref_cache {
 	struct ref_cache *next;
 	char did_loose;
 	char did_packed;
-	struct ref_array loose;
-	struct ref_array packed;
+	struct ref_dir loose;
+	struct ref_dir packed;
 	/* The submodule name, or "" for the main repo. */
 	char name[FLEX_ARRAY];
 } *ref_cache;
@@ -421,14 +421,14 @@ static struct ref_cache {
 static void clear_packed_ref_cache(struct ref_cache *refs)
 {
 	if (refs->did_packed)
-		clear_ref_array(&refs->packed);
+		clear_ref_dir(&refs->packed);
 	refs->did_packed = 0;
 }
 
 static void clear_loose_ref_cache(struct ref_cache *refs)
 {
 	if (refs->did_loose)
-		clear_ref_array(&refs->loose);
+		clear_ref_dir(&refs->loose);
 	refs->did_loose = 0;
 }
 
@@ -507,7 +507,7 @@ static const char *parse_ref_line(char *line, unsigned char *sha1)
 	return line;
 }
 
-static void read_packed_refs(FILE *f, struct ref_array *array)
+static void read_packed_refs(FILE *f, struct ref_dir *dir)
 {
 	struct ref_entry *last = NULL;
 	char refline[PATH_MAX];
@@ -529,7 +529,7 @@ static void read_packed_refs(FILE *f, struct ref_array *array)
 		refname = parse_ref_line(refline, sha1);
 		if (refname) {
 			last = create_ref_entry(refname, sha1, flag, 1);
-			add_ref(array, last);
+			add_ref(dir, last);
 			continue;
 		}
 		if (last &&
@@ -541,7 +541,7 @@ static void read_packed_refs(FILE *f, struct ref_array *array)
 	}
 }
 
-static struct ref_array *get_packed_refs(struct ref_cache *refs)
+static struct ref_dir *get_packed_refs(struct ref_cache *refs)
 {
 	if (!refs->did_packed) {
 		const char *packed_refs_file;
@@ -568,9 +568,9 @@ void add_packed_ref(const char *refname, const unsigned char *sha1)
 }
 
 static void get_ref_dir(struct ref_cache *refs, const char *base,
-			struct ref_array *array)
+			struct ref_dir *dir)
 {
-	DIR *dir;
+	DIR *d;
 	const char *path;
 
 	if (*refs->name)
@@ -578,9 +578,8 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,
 	else
 		path = git_path("%s", base);
 
-	dir = opendir(path);
-
-	if (dir) {
+	d = opendir(path);
+	if (d) {
 		struct dirent *de;
 		int baselen = strlen(base);
 		char *refname = xmalloc(baselen + 257);
@@ -589,7 +588,7 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,
 		if (baselen && base[baselen-1] != '/')
 			refname[baselen++] = '/';
 
-		while ((de = readdir(dir)) != NULL) {
+		while ((de = readdir(d)) != NULL) {
 			unsigned char sha1[20];
 			struct stat st;
 			int flag;
@@ -610,7 +609,7 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,
 			if (stat(refdir, &st) < 0)
 				continue;
 			if (S_ISDIR(st.st_mode)) {
-				get_ref_dir(refs, refname, array);
+				get_ref_dir(refs, refname, dir);
 				continue;
 			}
 			if (*refs->name) {
@@ -624,14 +623,14 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,
 				hashclr(sha1);
 				flag |= REF_ISBROKEN;
 			}
-			add_ref(array, create_ref_entry(refname, sha1, flag, 1));
+			add_ref(dir, create_ref_entry(refname, sha1, flag, 1));
 		}
 		free(refname);
-		closedir(dir);
+		closedir(d);
 	}
 }
 
-static struct ref_array *get_loose_refs(struct ref_cache *refs)
+static struct ref_dir *get_loose_refs(struct ref_cache *refs)
 {
 	if (!refs->did_loose) {
 		get_ref_dir(refs, "refs", &refs->loose);
@@ -653,9 +652,9 @@ static int resolve_gitlink_packed_ref(struct ref_cache *refs,
 				      const char *refname, unsigned char *sha1)
 {
 	struct ref_entry *ref;
-	struct ref_array *array = get_packed_refs(refs);
+	struct ref_dir *dir = get_packed_refs(refs);
 
-	ref = search_ref_array(array, refname);
+	ref = search_ref_dir(dir, refname);
 	if (ref == NULL)
 		return -1;
 
@@ -726,8 +725,8 @@ int resolve_gitlink_ref(const char *path, const char *refname, unsigned char *sh
  */
 static int get_packed_ref(const char *refname, unsigned char *sha1)
 {
-	struct ref_array *packed = get_packed_refs(get_ref_cache(NULL));
-	struct ref_entry *entry = search_ref_array(packed, refname);
+	struct ref_dir *packed = get_packed_refs(get_ref_cache(NULL));
+	struct ref_entry *entry = search_ref_dir(packed, refname);
 	if (entry) {
 		hashcpy(sha1, entry->u.value.sha1);
 		return 0;
@@ -903,8 +902,8 @@ int peel_ref(const char *refname, unsigned char *sha1)
 		return -1;
 
 	if ((flag & REF_ISPACKED)) {
-		struct ref_array *array = get_packed_refs(get_ref_cache(NULL));
-		struct ref_entry *r = search_ref_array(array, refname);
+		struct ref_dir *dir = get_packed_refs(get_ref_cache(NULL));
+		struct ref_entry *r = search_ref_dir(dir, refname);
 
 		if (r != NULL && r->flag & REF_KNOWS_PEELED) {
 			hashcpy(sha1, r->u.value.peeled);
@@ -962,13 +961,13 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn
 			   int trim, int flags, void *cb_data)
 {
 	struct ref_cache *refs = get_ref_cache(submodule);
-	struct ref_array *packed_refs = get_packed_refs(refs);
-	struct ref_array *loose_refs = get_loose_refs(refs);
-	sort_ref_array(packed_refs);
-	sort_ref_array(loose_refs);
-	return do_for_each_ref_in_arrays(packed_refs,
-					 loose_refs,
-					 base, fn, trim, flags, cb_data);
+	struct ref_dir *packed_refs = get_packed_refs(refs);
+	struct ref_dir *loose_refs = get_loose_refs(refs);
+	sort_ref_dir(packed_refs);
+	sort_ref_dir(loose_refs);
+	return do_for_each_ref_in_dirs(packed_refs,
+				       loose_refs,
+				       base, fn, trim, flags, cb_data);
 }
 
 static int do_head_ref(const char *submodule, each_ref_fn fn, void *cb_data)
@@ -1403,9 +1402,9 @@ static struct lock_file packlock;
 static int repack_without_ref(const char *refname)
 {
 	struct repack_without_ref_sb data;
-	struct ref_array *packed = get_packed_refs(get_ref_cache(NULL));
-	sort_ref_array(packed);
-	if (search_ref_array(packed, refname) == NULL)
+	struct ref_dir *packed = get_packed_refs(get_ref_cache(NULL));
+	sort_ref_dir(packed);
+	if (search_ref_dir(packed, refname) == NULL)
 		return 0;
 	data.refname = refname;
 	data.fd = hold_lock_file_for_update(&packlock, git_path("packed-refs"), 0);
@@ -1413,7 +1412,7 @@ static int repack_without_ref(const char *refname)
 		unable_to_lock_error(git_path("packed-refs"), errno);
 		return error("cannot delete '%s' from packed refs", refname);
 	}
-	do_for_each_ref_in_array(packed, 0, "", repack_without_ref_fn, 0, 0, &data);
+	do_for_each_ref_in_dir(packed, 0, "", repack_without_ref_fn, 0, 0, &data);
 	return commit_lock_file(&packlock);
 }
 
@@ -2024,10 +2023,10 @@ int for_each_reflog_ent(const char *refname, each_reflog_ent_fn fn, void *cb_dat
 
 static int do_for_each_reflog(const char *base, each_ref_fn fn, void *cb_data)
 {
-	DIR *dir = opendir(git_path("logs/%s", base));
+	DIR *d = opendir(git_path("logs/%s", base));
 	int retval = 0;
 
-	if (dir) {
+	if (d) {
 		struct dirent *de;
 		int baselen = strlen(base);
 		char *log = xmalloc(baselen + 257);
@@ -2036,7 +2035,7 @@ static int do_for_each_reflog(const char *base, each_ref_fn fn, void *cb_data)
 		if (baselen && base[baselen-1] != '/')
 			log[baselen++] = '/';
 
-		while ((de = readdir(dir)) != NULL) {
+		while ((de = readdir(d)) != NULL) {
 			struct stat st;
 			int namelen;
 
@@ -2063,7 +2062,7 @@ static int do_for_each_reflog(const char *base, each_ref_fn fn, void *cb_data)
 				break;
 		}
 		free(log);
-		closedir(dir);
+		closedir(d);
 	}
 	else if (*base)
 		return errno;
-- 
1.7.10

[PATCH 13/15] sort_ref_dir(): simplify logic

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

Use the more usual indexing idiom for clarity.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |   20 +++++++++++---------
 1 file changed, 11 insertions(+), 9 deletions(-)

diff --git a/refs.c b/refs.c
index 4e0cfb2..a3b8428 100644
--- a/refs.c
+++ b/refs.c
@@ -227,11 +227,13 @@ static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2
 }
 
 /*
- * Sort the entries in dir (if they are not already sorted).
+ * Sort the entries in dir (if they are not already sorted)
+ * and remove any duplicate entries.
  */
 static void sort_ref_dir(struct ref_dir *dir)
 {
 	int i, j;
+	struct ref_entry *last = NULL;
 
 	/*
 	 * This check also prevents passing a zero-length array to qsort(),
@@ -242,16 +244,16 @@ static void sort_ref_dir(struct ref_dir *dir)
 
 	qsort(dir->entries, dir->nr, sizeof(*dir->entries), ref_entry_cmp);
 
-	/* Remove any duplicates from the ref_dir */
-	i = 0;
-	for (j = 1; j < dir->nr; j++) {
-		if (is_dup_ref(dir->entries[i], dir->entries[j])) {
-			free_ref_entry(dir->entries[j]);
-			continue;
+	/* Remove any duplicates: */
+	for (i = 0, j = 0; j < dir->nr; j++) {
+		struct ref_entry *entry = dir->entries[j];
+		if (last && is_dup_ref(last, entry)) {
+			free_ref_entry(entry);
+		} else {
+			last = dir->entries[i++] = entry;
 		}
-		dir->entries[++i] = dir->entries[j];
 	}
-	dir->sorted = dir->nr = i + 1;
+	dir->sorted = dir->nr = i;
 }
 
 #define DO_FOR_EACH_INCLUDE_BROKEN 01
-- 
1.7.10

[PATCH 14/15] refs: store references hierarchically

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

Store references hierarchically in a tree that matches the
pseudo-directory structure of the reference names.  Add a new kind of
ref_entry (with flag REF_DIR) to represent a whole subdirectory of
references.  Sort ref_dirs one subdirectory at a time.

NOTE: the dirs can now be sorted as a side-effect of other function
calls.  Therefore, it would be problematic to do something from a
each_ref_fn callback that could provoke the sorting of a directory
that is currently being iterated over (i.e., the directory containing
the entry that is being processed or any of its parents).

This is a bit far-fetched, because a directory is always sorted just
before being iterated over.  Therefore, read-only accesses cannot
trigger the sorting of a directory whose iteration has already
started.  But if a callback function would add a reference to a parent
directory of the reference in the iteration, then try to resolve a
reference under that directory, a re-sort could be triggered and cause
the iteration to work incorrectly.

Nevertheless...add a comment in refs.h warning against modifications
during iteration.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |  274 +++++++++++++++++++++++++++++++++++++++++++++++++++++-----------
 refs.h |    7 +-
 2 files changed, 232 insertions(+), 49 deletions(-)

diff --git a/refs.c b/refs.c
index a3b8428..cdfb53d 100644
--- a/refs.c
+++ b/refs.c
@@ -120,15 +120,54 @@ struct ref_dir {
 	struct ref_entry **entries;
 };
 
-/* ISSYMREF=0x01, ISPACKED=0x02 and ISBROKEN=0x04 are public interfaces */
-#define REF_KNOWS_PEELED 0x10
+/* ISSYMREF=0x01, ISPACKED=0x02, and ISBROKEN=0x04 are public interfaces */
+#define REF_KNOWS_PEELED 0x08
+#define REF_DIR 0x10
 
+/*
+ * A ref_entry represents either a reference or a "subdirectory" of
+ * references.  Each directory in the reference namespace is
+ * represented by a ref_entry with (flags & REF_DIR) set and
+ * containing a subdir member that holds the entries in that
+ * directory.  References are represented by a ref_entry with (flags &
+ * REF_DIR) unset and a value member that describes the reference's
+ * value.  The flag member is at the ref_entry level, but it is also
+ * needed to interpret the contents of the value field (in other
+ * words, a ref_value object is not very much use without the
+ * enclosing ref_entry).
+ *
+ * Reference names cannot end with slash and directories' names are
+ * always stored with a trailing slash (except for the top-level
+ * directory, which is always denoted by "").  This has two nice
+ * consequences: (1) when the entries in each subdir are sorted
+ * lexicographically by name (as they usually are), the references in
+ * a whole tree can be generated in lexicographic order by traversing
+ * the tree in left-to-right, depth-first order; (2) the names of
+ * references and subdirectories cannot conflict, and therefore the
+ * presence of an empty subdirectory does not block the creation of a
+ * similarly-named reference.  (The fact that reference names with the
+ * same leading components can conflict *with each other* is a
+ * separate issue that is regulated by is_refname_available().)
+ *
+ * Please note that the name field contains the fully-qualified
+ * reference (or subdirectory) name.  Space could be saved by only
+ * storing the relative names.  But that would require the full names
+ * to be generated on the fly when iterating in do_for_each_ref(), and
+ * would break callback functions, who have always been able to assume
+ * that the name strings that they are passed will not be freed during
+ * the iteration.
+ */
 struct ref_entry {
 	unsigned char flag; /* ISSYMREF? ISPACKED? */
 	union {
-		struct ref_value value;
+		struct ref_value value; /* if not (flags&REF_DIR) */
+		struct ref_dir subdir; /* if (flags&REF_DIR) */
 	} u;
-	/* The full name of the reference (e.g., "refs/heads/master"): */
+	/*
+	 * The full name of the reference (e.g., "refs/heads/master")
+	 * or the full name of the directory with a trailing slash
+	 * (e.g., "refs/heads/"):
+	 */
 	char name[FLEX_ARRAY];
 };
 
@@ -151,18 +190,29 @@ static struct ref_entry *create_ref_entry(const char *refname,
 	return ref;
 }
 
+static void clear_ref_dir(struct ref_dir *dir);
+
 static void free_ref_entry(struct ref_entry *entry)
 {
+	if (entry->flag & REF_DIR)
+		clear_ref_dir(&entry->u.subdir);
 	free(entry);
 }
 
-/* Add a ref_entry to the end of the ref_dir (unsorted). */
-static void add_ref(struct ref_dir *refs, struct ref_entry *ref)
+/*
+ * Add a ref_entry to the end of dir (unsorted).  Entry is always
+ * stored directly in dir; no recursion into subdirectories is
+ * done.
+ */
+static void add_entry_to_dir(struct ref_dir *dir, struct ref_entry *entry)
 {
-	ALLOC_GROW(refs->entries, refs->nr + 1, refs->alloc);
-	refs->entries[refs->nr++] = ref;
+	ALLOC_GROW(dir->entries, dir->nr + 1, dir->alloc);
+	dir->entries[dir->nr++] = entry;
 }
 
+/*
+ * Clear and free all entries in dir, recursively.
+ */
 static void clear_ref_dir(struct ref_dir *dir)
 {
 	int i;
@@ -173,6 +223,21 @@ static void clear_ref_dir(struct ref_dir *dir)
 	dir->entries = NULL;
 }
 
+/*
+ * Create a struct ref_entry object for the specified dirname.
+ * dirname is the name of the directory with a trailing slash (e.g.,
+ * "refs/heads/") or "" for the top-level directory.
+ */
+static struct ref_entry *create_dir_entry(const char *dirname)
+{
+	struct ref_entry *direntry;
+	int len = strlen(dirname);
+	direntry = xcalloc(1, sizeof(struct ref_entry) + len + 1);
+	memcpy(direntry->name, dirname, len + 1);
+	direntry->flag = REF_DIR;
+	return direntry;
+}
+
 static int ref_entry_cmp(const void *a, const void *b)
 {
 	struct ref_entry *one = *(struct ref_entry **)a;
@@ -182,17 +247,21 @@ static int ref_entry_cmp(const void *a, const void *b)
 
 static void sort_ref_dir(struct ref_dir *dir);
 
+/*
+ * Return the entry with the given refname from the ref_dir
+ * (non-recursively), sorting dir if necessary.  Return NULL if no
+ * such entry is found.
+ */
 static struct ref_entry *search_ref_dir(struct ref_dir *dir, const char *refname)
 {
 	struct ref_entry *e, **r;
 	int len;
 
-	if (refname == NULL)
+	if (refname == NULL || !dir->nr)
 		return NULL;
 
-	if (!dir->nr)
-		return NULL;
 	sort_ref_dir(dir);
+
 	len = strlen(refname) + 1;
 	e = xmalloc(sizeof(struct ref_entry) + len);
 	memcpy(e->name, refname, len);
@@ -208,27 +277,96 @@ static struct ref_entry *search_ref_dir(struct ref_dir *dir, const char *refname
 }
 
 /*
+ * If refname is a reference name, find the ref_dir within the dir
+ * tree that should hold refname.  If refname is a directory name
+ * (i.e., ends in '/'), then return that ref_dir itself.  dir must
+ * represent the top-level directory.  Sort ref_dirs and recurse into
+ * subdirectories as necessary.  If mkdir is set, then create any
+ * missing directories; otherwise, return NULL if the desired
+ * directory cannot be found.
+ */
+static struct ref_dir *find_containing_dir(struct ref_dir *dir,
+					   const char *refname, int mkdir)
+{
+	char *refname_copy = xstrdup(refname);
+	char *slash;
+	struct ref_entry *entry;
+	for (slash = strchr(refname_copy, '/'); slash; slash = strchr(slash + 1, '/')) {
+		char tmp = slash[1];
+		slash[1] = '\0';
+		entry = search_ref_dir(dir, refname_copy);
+		if (!entry) {
+			if (!mkdir) {
+				dir = NULL;
+				break;
+			}
+			entry = create_dir_entry(refname_copy);
+			add_entry_to_dir(dir, entry);
+		}
+		slash[1] = tmp;
+		assert(entry->flag & REF_DIR);
+		dir = &entry->u.subdir;
+	}
+
+	free(refname_copy);
+	return dir;
+}
+
+/*
+ * Find the value entry with the given name in dir, sorting ref_dirs
+ * and recursing into subdirectories as necessary.  If the name is not
+ * found or it corresponds to a directory entry, return NULL.
+ */
+static struct ref_entry *find_ref(struct ref_dir *dir, const char *refname)
+{
+	struct ref_entry *entry;
+	dir = find_containing_dir(dir, refname, 0);
+	if (!dir)
+		return NULL;
+	entry = search_ref_dir(dir, refname);
+	return (entry && !(entry->flag & REF_DIR)) ? entry : NULL;
+}
+
+/*
+ * Add a ref_entry to the ref_dir (unsorted), recursing into
+ * subdirectories as necessary.  dir must represent the top-level
+ * directory.  Return 0 on success.
+ */
+static int add_ref(struct ref_dir *dir, struct ref_entry *ref)
+{
+	dir = find_containing_dir(dir, ref->name, 1);
+	if (!dir)
+		return -1;
+	add_entry_to_dir(dir, ref);
+	return 0;
+}
+
+/*
  * Emit a warning and return true iff ref1 and ref2 have the same name
  * and the same sha1.  Die if they have the same name but different
  * sha1s.
  */
 static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2)
 {
-	if (!strcmp(ref1->name, ref2->name)) {
-		/* Duplicate name; make sure that the SHA1s match: */
-		if (hashcmp(ref1->u.value.sha1, ref2->u.value.sha1))
-			die("Duplicated ref, and SHA1s don't match: %s",
-			    ref1->name);
-		warning("Duplicated ref: %s", ref1->name);
-		return 1;
-	} else {
+	if (strcmp(ref1->name, ref2->name))
 		return 0;
-	}
+
+	/* Duplicate name; make sure that they don't conflict: */
+
+	if ((ref1->flag & REF_DIR) || (ref2->flag & REF_DIR))
+		/* This is impossible by construction */
+		die("Reference directory conflict: %s", ref1->name);
+
+	if (hashcmp(ref1->u.value.sha1, ref2->u.value.sha1))
+		die("Duplicated ref, and SHA1s don't match: %s", ref1->name);
+
+	warning("Duplicated ref: %s", ref1->name);
+	return 1;
 }
 
 /*
- * Sort the entries in dir (if they are not already sorted)
- * and remove any duplicate entries.
+ * Sort the entries in dir non-recursively (if they are not already
+ * sorted) and remove any duplicate entries.
  */
 static void sort_ref_dir(struct ref_dir *dir)
 {
@@ -283,8 +421,9 @@ static int do_one_ref(const char *base, each_ref_fn fn, int trim,
 
 /*
  * Call fn for each reference in dir that has index in the range
- * offset <= index < dir->nr.  This function does not sort the dir;
- * sorting should be done by the caller.
+ * offset <= index < dir->nr.  Recurse into subdirectories that are in
+ * that index range, sorting them before iterating.  This function
+ * does not sort dir itself; it should be sorted beforehand.
  */
 static int do_for_each_ref_in_dir(struct ref_dir *dir, int offset,
 				  const char *base,
@@ -293,7 +432,15 @@ static int do_for_each_ref_in_dir(struct ref_dir *dir, int offset,
 	int i;
 	assert(dir->sorted == dir->nr);
 	for (i = offset; i < dir->nr; i++) {
-		int retval = do_one_ref(base, fn, trim, flags, cb_data, dir->entries[i]);
+		struct ref_entry *entry = dir->entries[i];
+		int retval;
+		if (entry->flag & REF_DIR) {
+			sort_ref_dir(&entry->u.subdir);
+			retval = do_for_each_ref_in_dir(&entry->u.subdir, 0,
+							base, fn, trim, flags, cb_data);
+		} else {
+			retval = do_one_ref(base, fn, trim, flags, cb_data, entry);
+		}
 		if (retval)
 			return retval;
 	}
@@ -302,9 +449,10 @@ static int do_for_each_ref_in_dir(struct ref_dir *dir, int offset,
 
 /*
  * Call fn for each reference in the union of dir1 and dir2, in order
- * by refname.  If an entry appears in both dir1 and dir2, then only
- * process the version that is in dir2.  The input dirs must already
- * be sorted.
+ * by refname.  Recurse into subdirectories.  If a value entry appears
+ * in both dir1 and dir2, then only process the version that is in
+ * dir2.  The input dirs must already be sorted, but subdirs will be
+ * sorted as needed.
  */
 static int do_for_each_ref_in_dirs(struct ref_dir *dir1,
 				   struct ref_dir *dir2,
@@ -316,22 +464,55 @@ static int do_for_each_ref_in_dirs(struct ref_dir *dir1,
 
 	assert(dir1->sorted == dir1->nr);
 	assert(dir2->sorted == dir2->nr);
-	while (i1 < dir1->nr && i2 < dir2->nr) {
-		struct ref_entry *e1 = dir1->entries[i1];
-		struct ref_entry *e2 = dir2->entries[i2];
-		int cmp = strcmp(e1->name, e2->name);
-		if (cmp < 0) {
-			retval = do_one_ref(base, fn, trim, flags, cb_data, e1);
-			i1++;
+	while (1) {
+		struct ref_entry *e1, *e2;
+		int cmp;
+		if (i1 == dir1->nr) {
+			return do_for_each_ref_in_dir(dir2, i2,
+						      base, fn, trim, flags, cb_data);
+		}
+		if (i2 == dir2->nr) {
+			return do_for_each_ref_in_dir(dir1, i1,
+						      base, fn, trim, flags, cb_data);
+		}
+		e1 = dir1->entries[i1];
+		e2 = dir2->entries[i2];
+		cmp = strcmp(e1->name, e2->name);
+		if (cmp == 0) {
+			if ((e1->flag & REF_DIR) && (e2->flag & REF_DIR)) {
+				/* Both are directories; descend them in parallel. */
+				sort_ref_dir(&e1->u.subdir);
+				sort_ref_dir(&e2->u.subdir);
+				retval = do_for_each_ref_in_dirs(
+						&e1->u.subdir, &e2->u.subdir,
+						base, fn, trim, flags, cb_data);
+				i1++;
+				i2++;
+			} else if (!(e1->flag & REF_DIR) && !(e2->flag & REF_DIR)) {
+				/* Both are references; ignore the one from dir1. */
+				retval = do_one_ref(base, fn, trim, flags, cb_data, e2);
+				i1++;
+				i2++;
+			} else {
+				die("conflict between reference and directory: %s",
+				    e1->name);
+			}
 		} else {
-			retval = do_one_ref(base, fn, trim, flags, cb_data, e2);
-			i2++;
-			if (cmp == 0) {
-				/*
-				 * There was a ref in array1 with the
-				 * same name; ignore it.
-				 */
+			struct ref_entry *e;
+			if (cmp < 0) {
+				e = e1;
 				i1++;
+			} else {
+				e = e2;
+				i2++;
+			}
+			if (e->flag & REF_DIR) {
+				sort_ref_dir(&e->u.subdir);
+				retval = do_for_each_ref_in_dir(
+						&e->u.subdir, 0,
+						base, fn, trim, flags, cb_data);
+			} else {
+				retval = do_one_ref(base, fn, trim, flags, cb_data, e);
 			}
 		}
 		if (retval)
@@ -656,7 +837,7 @@ static int resolve_gitlink_packed_ref(struct ref_cache *refs,
 	struct ref_entry *ref;
 	struct ref_dir *dir = get_packed_refs(refs);
 
-	ref = search_ref_dir(dir, refname);
+	ref = find_ref(dir, refname);
 	if (ref == NULL)
 		return -1;
 
@@ -728,7 +909,7 @@ int resolve_gitlink_ref(const char *path, const char *refname, unsigned char *sh
 static int get_packed_ref(const char *refname, unsigned char *sha1)
 {
 	struct ref_dir *packed = get_packed_refs(get_ref_cache(NULL));
-	struct ref_entry *entry = search_ref_dir(packed, refname);
+	struct ref_entry *entry = find_ref(packed, refname);
 	if (entry) {
 		hashcpy(sha1, entry->u.value.sha1);
 		return 0;
@@ -905,7 +1086,7 @@ int peel_ref(const char *refname, unsigned char *sha1)
 
 	if ((flag & REF_ISPACKED)) {
 		struct ref_dir *dir = get_packed_refs(get_ref_cache(NULL));
-		struct ref_entry *r = search_ref_dir(dir, refname);
+		struct ref_entry *r = find_ref(dir, refname);
 
 		if (r != NULL && r->flag & REF_KNOWS_PEELED) {
 			hashcpy(sha1, r->u.value.peeled);
@@ -1405,8 +1586,7 @@ static int repack_without_ref(const char *refname)
 {
 	struct repack_without_ref_sb data;
 	struct ref_dir *packed = get_packed_refs(get_ref_cache(NULL));
-	sort_ref_dir(packed);
-	if (search_ref_dir(packed, refname) == NULL)
+	if (find_ref(packed, refname) == NULL)
 		return 0;
 	data.refname = refname;
 	data.fd = hold_lock_file_for_update(&packlock, git_path("packed-refs"), 0);
diff --git a/refs.h b/refs.h
index 33202b0..d6c2fe2 100644
--- a/refs.h
+++ b/refs.h
@@ -15,8 +15,11 @@ struct ref_lock {
 #define REF_ISBROKEN 0x04
 
 /*
- * Calls the specified function for each ref file until it returns nonzero,
- * and returns the value
+ * Calls the specified function for each ref file until it returns
+ * nonzero, and returns the value.  Please note that it is not safe to
+ * modify references while an iteration is in progress, unless the
+ * same callback function invocation that modifies the reference also
+ * returns a nonzero value to immediately stop the iteration.
  */
 typedef int each_ref_fn(const char *refname, const unsigned char *sha1, int flags, void *cb_data);
 extern int head_ref(each_ref_fn, void *);
-- 
1.7.10

[PATCH 15/15] do_for_each_ref(): only iterate over the subtree that was requested

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

If the base argument has a "/" chararacter, then only iterate over the
reference subdir whose name is the part up to the last "/".

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |   35 ++++++++++++++++++++++++++++-------
 1 file changed, 28 insertions(+), 7 deletions(-)

diff --git a/refs.c b/refs.c
index cdfb53d..f97a256 100644
--- a/refs.c
+++ b/refs.c
@@ -1144,13 +1144,34 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn
 			   int trim, int flags, void *cb_data)
 {
 	struct ref_cache *refs = get_ref_cache(submodule);
-	struct ref_dir *packed_refs = get_packed_refs(refs);
-	struct ref_dir *loose_refs = get_loose_refs(refs);
-	sort_ref_dir(packed_refs);
-	sort_ref_dir(loose_refs);
-	return do_for_each_ref_in_dirs(packed_refs,
-				       loose_refs,
-				       base, fn, trim, flags, cb_data);
+	struct ref_dir *packed_dir = get_packed_refs(refs);
+	struct ref_dir *loose_dir = get_loose_refs(refs);
+	int retval = 0;
+
+	if (base && *base) {
+		packed_dir = find_containing_dir(packed_dir, base, 0);
+		loose_dir = find_containing_dir(loose_dir, base, 0);
+	}
+
+	if (packed_dir && loose_dir) {
+		sort_ref_dir(packed_dir);
+		sort_ref_dir(loose_dir);
+		retval = do_for_each_ref_in_dirs(
+				packed_dir, loose_dir,
+				base, fn, trim, flags, cb_data);
+	} else if (packed_dir) {
+		sort_ref_dir(packed_dir);
+		retval = do_for_each_ref_in_dir(
+				packed_dir, 0,
+				base, fn, trim, flags, cb_data);
+	} else if (loose_dir) {
+		sort_ref_dir(loose_dir);
+		retval = do_for_each_ref_in_dir(
+				loose_dir, 0,
+				base, fn, trim, flags, cb_data);
+	}
+
+	return retval;
 }
 
 static int do_head_ref(const char *submodule, each_ref_fn fn, void *cb_data)
-- 
1.7.10

Re: [PATCH 00/15] Hierarchical reference cache (once again)

[Jeff King]

On Tue, Apr 10, 2012 at 07:30:12AM +0200, mhagger@alum.mit.edu wrote:

> Michael Haggerty (15):
>   refs.c: reorder definitions more logically
>   refs: manage current_ref within do_one_ref()
>   do_for_each_ref_in_array(): new function
>   do_for_each_ref_in_arrays(): new function
>   repack_without_ref(): reimplement using do_for_each_ref_in_array()
>   names_conflict(): new function, extracted from is_refname_available()
>   names_conflict(): simplify implementation
>   is_refname_available(): reimplement using do_for_each_ref_in_array()
>   free_ref_entry(): new function
>   check_refname_component(): return 0 for zero-length components
>   struct ref_entry: nest the value part in a union
>   refs.c: rename ref_array -> ref_dir
>   sort_ref_dir(): simplify logic
>   refs: store references hierarchically
>   do_for_each_ref(): only iterate over the subtree that was requested

I read through the whole series and didn't find anything noticeably
wrong.  Overall, it was quite readable for such a large series. Thanks
for breaking it up as you did.

-Peff

Re: [PATCH 00/15] Hierarchical reference cache (once again)

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> On Tue, Apr 10, 2012 at 07:30:12AM +0200, mhagger@alum.mit.edu wrote:
>
>> Michael Haggerty (15):
>>   refs.c: reorder definitions more logically
>> ...
>
> I read through the whole series and didn't find anything noticeably
> wrong.  Overall, it was quite readable for such a large series. Thanks
> for breaking it up as you did.

I hate myself doing this, but...

	<aol> me too! </aol>

The series looked very readable, unlike the previous huge rounds.

Thanks.