patch, 28 partssort_ref_dir(): do not sort if already sorted

diff --git a/refs.c b/refs.c
index 96466f3..56868a5 100644
--- a/refs.c
+++ b/refs.c
@@ -4,6 +4,108 @@
 #include "tag.h"
 #include "dir.h"
 
+/*
+ * 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;
+}
+
+struct ref_entry;
+
+struct ref_array {
+	int nr, alloc;
+	struct ref_entry **refs;
+};
+
 /* ISSYMREF=0x01, ISPACKED=0x02 and ISBROKEN=0x04 are public interfaces */
 #define REF_KNOWS_PEELED 0x10
 
@@ -15,47 +117,6 @@ struct ref_entry {
 	char name[FLEX_ARRAY];
 };
 
-struct ref_array {
-	int nr, alloc;
-	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;
-
-	if (check_refname_format(line, REFNAME_ALLOW_ONELEVEL))
-		return NULL;
-
-	return line;
-}
-
 static struct ref_entry *create_ref_entry(const char *refname,
 					  const unsigned char *sha1, int flag)
 {
@@ -80,6 +141,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->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;
@@ -87,6 +158,31 @@ static int ref_entry_cmp(const void *a, const void *b)
 	return strcmp(one->name, two->name);
 }
 
+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;
+
+	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
@@ -130,29 +226,137 @@ static void sort_ref_array(struct ref_array *array)
 	array->nr = i + 1;
 }
 
-static struct ref_entry *search_ref_array(struct ref_array *array, const char *refname)
+#define DO_FOR_EACH_INCLUDE_BROKEN 01
+
+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)
 {
-	struct ref_entry *e, **r;
-	int len;
+	if (prefixcmp(entry->name, base))
+		return 0;
 
-	if (refname == 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);
+}
 
-	if (!array->nr)
-		return NULL;
+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;
+	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;
+}
 
-	len = strlen(refname) + 1;
-	e = xmalloc(sizeof(struct ref_entry) + len);
-	memcpy(e->name, refname, len);
+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;
 
-	r = bsearch(&e, array->refs, array->nr, sizeof(*array->refs), ref_entry_cmp);
+	while (1) {
+		struct ref_entry *e1, *e2;
+		int cmp;
+		if (i1 == array1->nr) {
+			return do_for_each_ref_in_array(array2, i2,
+							base, fn, trim, flags, cb_data);
+		}
+		if (i2 == array2->nr) {
+			return do_for_each_ref_in_array(array1, i1,
+							base, fn, trim, flags, cb_data);
+		}
+		e1 = array1->refs[i1];
+		e2 = array2->refs[i2];
+		cmp = strcmp(e1->name, e2->name);
+		if (cmp == 0) {
+			/* Two refs with the same name; ignore the one from array1. */
+			i1++;
+			continue;
+		}
+		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 (retval)
+			return retval;
+	}
+}
 
-	free(e);
+/*
+ * 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)
+{
+	for (; *refname1 && *refname1 == *refname2; refname1++, refname2++)
+		;
+	return (*refname1 == '\0' && *refname2 == '/')
+		|| (*refname1 == '/' && *refname2 == '\0');
+}
 
-	if (r == NULL)
-		return NULL;
+struct name_conflict_cb {
+	const char *refname;
+	const char *oldrefname;
+	const char *conflicting_refname;
+};
 
-	return *r;
+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
+ * operation).
+ */
+static int is_refname_available(const char *refname, const char *oldrefname,
+				struct ref_array *array)
+{
+	struct name_conflict_cb data;
+	data.refname = refname;
+	data.oldrefname = oldrefname;
+	data.conflicting_refname = NULL;
+
+	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;
 }
 
 /*
@@ -169,20 +373,8 @@ static struct ref_cache {
 	char name[FLEX_ARRAY];
 } *ref_cache;
 
-static struct ref_entry *current_ref;
-
 static struct ref_array extra_refs;
 
-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->nr = array->alloc = 0;
-	array->refs = NULL;
-}
-
 static void clear_packed_ref_cache(struct ref_cache *refs)
 {
 	if (refs->did_packed)
@@ -239,6 +431,42 @@ 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;
+
+	if (check_refname_format(line, REFNAME_ALLOW_ONELEVEL))
+		return NULL;
+
+	return line;
+}
+
 static void read_packed_refs(FILE *f, struct ref_array *array)
 {
 	struct ref_entry *last = NULL;
@@ -355,53 +583,19 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,
 				hashclr(sha1);
 				flag = 0;
 				if (resolve_gitlink_ref(refs->name, refname, sha1) < 0) {
-					hashclr(sha1);
-					flag |= REF_ISBROKEN;
-				}
-			} else
-				if (!resolve_ref(refname, sha1, 1, &flag)) {
-					hashclr(sha1);
-					flag |= REF_ISBROKEN;
-				}
-			add_ref(array, create_ref_entry(refname, sha1, flag));
-		}
-		free(refname);
-		closedir(dir);
-	}
-}
-
-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(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);
+					hashclr(sha1);
+					flag |= REF_ISBROKEN;
+				}
+			} else
+				if (!resolve_ref(refname, sha1, 1, &flag)) {
+					hashclr(sha1);
+					flag |= REF_ISBROKEN;
+				}
+			add_ref(array, create_ref_entry(refname, sha1, flag));
+		}
+		free(refname);
+		closedir(dir);
+	}
 }
 
 static struct ref_array *get_loose_refs(struct ref_cache *refs)
@@ -631,27 +825,8 @@ int read_ref(const char *refname, unsigned char *sha1)
 	return -1;
 }
 
-#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)
-{
-	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);
-}
-
 static int filter_refs(const char *refname, const unsigned char *sha, int flags,
-	void *data)
+		       void *data)
 {
 	struct ref_filter *filter = (struct ref_filter *)data;
 	if (fnmatch(filter->pattern, refname, 0))
@@ -700,56 +875,38 @@ fallback:
 	return -1;
 }
 
-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)
+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)
 {
-	int i;
-	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;
-	}
+	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(refname, junk, 0, NULL);
+	if (!resolves_to || strcmp(resolves_to, d->refname))
+		return 0;
+
+	fprintf(d->fp, d->msg_fmt, refname);
 	return 0;
 }
 
-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)
+void warn_dangling_symref(FILE *fp, const char *msg_fmt, const char *refname)
 {
-	int retval;
-	int i1 = 0, i2 = 0;
+	struct warn_if_dangling_data data;
 
-	while (1) {
-		struct ref_entry *e1, *e2;
-		int cmp;
-		if (i1 == array1->nr) {
-			return do_for_each_ref_in_array(array2, i2,
-							base, fn, trim, flags, cb_data);
-		}
-		if (i2 == array2->nr) {
-			return do_for_each_ref_in_array(array1, i1,
-							base, fn, trim, flags, cb_data);
-		}
-		e1 = array1->refs[i1];
-		e2 = array2->refs[i2];
-		cmp = strcmp(e1->name, e2->name);
-		if (cmp == 0) {
-			/* Two refs with the same name; ignore the one from array1. */
-			i1++;
-			continue;
-		}
-		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 (retval)
-			return retval;
-	}
+	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,
@@ -920,101 +1077,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 + (
@@ -1092,65 +1154,6 @@ static int remove_empty_directories(const char *file)
 }
 
 /*
- * 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)
-{
-	for (; *refname1 && *refname1 == *refname2; refname1++, refname2++)
-		;
-	return (*refname1 == '\0' && *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
- * operation).
- */
-static int is_refname_available(const char *refname, const char *oldrefname,
-				struct ref_array *array)
-{
-	struct name_conflict_cb data;
-	data.refname = refname;
-	data.oldrefname = oldrefname;
-	data.conflicting_refname = NULL;
-
-	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;
-}
-
-/*
  * *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.

diff --git a/refs.c b/refs.c
index 56868a5..eff1abe 100644
--- a/refs.c
+++ b/refs.c
@@ -134,6 +134,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)
 {
@@ -145,7 +150,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->nr = array->alloc = 0;
 	array->refs = NULL;
@@ -217,7 +222,7 @@ static void sort_ref_array(struct ref_array *array)
 		struct ref_entry *a = array->refs[i];
 		struct ref_entry *b = array->refs[j];
 		if (is_dup_ref(a, b)) {
-			free(b);
+			free_ref_entry(b);
 			continue;
 		}
 		i++;

diff --git a/refs.c b/refs.c
index eff1abe..61dfb32 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] == '/')) {

diff --git a/refs.c b/refs.c
index 61dfb32..dafb585 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;
 	struct ref_entry **refs;
@@ -111,8 +116,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];
 };
@@ -127,8 +133,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;
@@ -197,7 +203,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);
@@ -244,13 +250,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;
-	return fn(entry->name + trim, entry->sha1, entry->flag, cb_data);
+	return fn(entry->name + trim, entry->u.value.sha1, entry->flag, cb_data);
 }
 
 static int do_for_each_ref_in_array(struct ref_array *array, int offset,
@@ -502,7 +508,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);
 	}
 	sort_ref_array(array);
 }
@@ -632,7 +638,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;
 }
 
@@ -702,7 +708,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;
@@ -848,10 +854,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;
 	}
 
@@ -863,7 +869,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;
 		}
 	}

diff --git a/refs.c b/refs.c
index dafb585..708eebf 100644
--- a/refs.c
+++ b/refs.c
@@ -106,9 +106,9 @@ struct ref_value {
 	unsigned char peeled[20];
 };
 
-struct ref_array {
+struct ref_dir {
 	int nr, alloc;
-	struct ref_entry **refs;
+	struct ref_entry **entries;
 };
 
 /* ISSYMREF=0x01, ISPACKED=0x02 and ISBROKEN=0x04 are public interfaces */
@@ -145,21 +145,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->nr = array->alloc = 0;
-	array->refs = NULL;
+	for (i = 0; i < dir->nr; i++)
+		free_ref_entry(dir->entries[i]);
+	free(dir->entries);
+	dir->nr = dir->alloc = 0;
+	dir->entries = NULL;
 }
 
 static int ref_entry_cmp(const void *a, const void *b)
@@ -169,7 +169,7 @@ static int ref_entry_cmp(const void *a, const void *b)
 	return strcmp(one->name, two->name);
 }
 
-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;
@@ -177,14 +177,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;
 
 	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);
 
@@ -213,28 +213,28 @@ static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2
 	}
 }
 
-static void sort_ref_array(struct ref_array *array)
+static void sort_ref_dir(struct ref_dir *dir)
 {
 	int i = 0, j = 1;
 
 	/* Nothing to sort unless there are at least two entries */
-	if (array->nr < 2)
+	if (dir->nr < 2)
 		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 */
-	for (; j < array->nr; j++) {
-		struct ref_entry *a = array->refs[i];
-		struct ref_entry *b = array->refs[j];
+	/* Remove any duplicates from the ref_dir */
+	for (; j < dir->nr; j++) {
+		struct ref_entry *a = dir->entries[i];
+		struct ref_entry *b = dir->entries[j];
 		if (is_dup_ref(a, b)) {
 			free_ref_entry(b);
 			continue;
 		}
 		i++;
-		array->refs[i] = array->refs[j];
+		dir->entries[i] = dir->entries[j];
 	}
-	array->nr = i + 1;
+	dir->nr = i + 1;
 }
 
 #define DO_FOR_EACH_INCLUDE_BROKEN 01
@@ -259,23 +259,23 @@ static int do_one_ref(const char *base, each_ref_fn fn, int trim,
 	return fn(entry->name + trim, entry->u.value.sha1, entry->flag, cb_data);
 }
 
-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;
-	for (i = offset; i < array->nr; i++) {
-		int retval = do_one_ref(base, fn, trim, flags, cb_data, array->refs[i]);
+	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;
 	}
 	return 0;
 }
 
-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;
@@ -283,19 +283,19 @@ static int do_for_each_ref_in_arrays(struct ref_array *array1,
 	while (1) {
 		struct ref_entry *e1, *e2;
 		int cmp;
-		if (i1 == array1->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(dir2, i2,
+						      base, fn, trim, flags, cb_data);
 		}
-		if (i2 == array2->nr) {
-			return do_for_each_ref_in_array(array1, i1,
-							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 = array1->refs[i1];
-		e2 = array2->refs[i2];
+		e1 = dir1->entries[i1];
+		e2 = dir2->entries[i2];
 		cmp = strcmp(e1->name, e2->name);
 		if (cmp == 0) {
-			/* Two refs with the same name; ignore the one from array1. */
+			/* Two refs with the same name; ignore the one from dir1. */
 			i1++;
 			continue;
 		}
@@ -353,16 +353,16 @@ 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;
 
-	if (do_for_each_ref_in_array(array, 0, "", name_conflict_fn,
-				     0, DO_FOR_EACH_INCLUDE_BROKEN,
-				     &data)) {
+	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;
@@ -378,25 +378,25 @@ 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;
 
-static struct ref_array extra_refs;
+static struct ref_dir extra_refs;
 
 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;
 }
 
@@ -478,7 +478,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];
@@ -500,7 +500,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);
-			add_ref(array, last);
+			add_ref(dir, last);
 			continue;
 		}
 		if (last &&
@@ -510,7 +510,7 @@ static void read_packed_refs(FILE *f, struct ref_array *array)
 		    !get_sha1_hex(refline + 1, sha1))
 			hashcpy(last->u.value.peeled, sha1);
 	}
-	sort_ref_array(array);
+	sort_ref_dir(dir);
 }
 
 void add_extra_ref(const char *refname, const unsigned char *sha1, int flag)
@@ -520,10 +520,10 @@ void add_extra_ref(const char *refname, const unsigned char *sha1, int flag)
 
 void clear_extra_refs(void)
 {
-	clear_ref_array(&extra_refs);
+	clear_ref_dir(&extra_refs);
 }
 
-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;
@@ -544,9 +544,9 @@ static struct ref_array *get_packed_refs(struct ref_cache *refs)
 }
 
 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)
@@ -555,9 +555,9 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,
 		path = git_path("%s", base);
 
 
-	dir = opendir(path);
+	d = opendir(path);
 
-	if (dir) {
+	if (d) {
 		struct dirent *de;
 		int baselen = strlen(base);
 		char *refname = xmalloc(baselen + 257);
@@ -566,7 +566,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;
@@ -587,7 +587,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) {
@@ -602,18 +602,18 @@ 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));
+			add_ref(dir, create_ref_entry(refname, sha1, flag));
 		}
 		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);
-		sort_ref_array(&refs->loose);
+		sort_ref_dir(&refs->loose);
 		refs->did_loose = 1;
 	}
 	return &refs->loose;
@@ -632,9 +632,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;
 
@@ -705,8 +705,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;
@@ -865,8 +865,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);
@@ -926,12 +926,12 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn
 	int retval = 0;
 	struct ref_cache *refs = get_ref_cache(submodule);
 
-	retval = do_for_each_ref_in_array(&extra_refs, 0,
-					  base, fn, trim, flags, cb_data);
+	retval = do_for_each_ref_in_dir(&extra_refs, 0,
+					base, fn, trim, flags, cb_data);
 	if (!retval)
-		retval = do_for_each_ref_in_arrays(get_packed_refs(refs),
-						   get_loose_refs(refs),
-						   base, fn, trim, flags, cb_data);
+		retval = do_for_each_ref_in_dirs(get_packed_refs(refs),
+						 get_loose_refs(refs),
+						 base, fn, trim, flags, cb_data);
 
 	current_ref = NULL;
 	return retval;
@@ -1377,10 +1377,10 @@ static struct lock_file packlock;
 static int repack_without_ref(const char *refname)
 {
 	struct repack_without_ref_sb data;
-	struct ref_array *packed;
+	struct ref_dir *packed;
 
 	packed = get_packed_refs(get_ref_cache(NULL));
-	if (search_ref_array(packed, refname) == NULL)
+	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);
@@ -1388,7 +1388,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);
 }
 
@@ -1998,10 +1998,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);
@@ -2010,7 +2010,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;
 
@@ -2037,7 +2037,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;

diff --git a/refs.c b/refs.c
index 708eebf..6b4d5d5 100644
--- a/refs.c
+++ b/refs.c
@@ -67,6 +67,23 @@ static int check_refname_component(const char *refname, int flags)
 	return cp - refname;
 }
 
+/*
+ * Non-public option to check_refname_format(), for asking it to check
+ * that refname is a valid reference "directory" name.
+ */
+#define REFNAME_DIR 0x08
+
+/*
+ * See refs.h for a description of the public interface of this
+ * function.  In addition, there is a private interface that can be
+ * accessed by setting the REFNAME_DIR bit.  If REFNAME_DIR is set,
+ * then refname must be a valid reference "directory" name.  This
+ * means that it must include at least one valid component (which *is*
+ * allowed to end with '.') followed by a trailing '/'.  If
+ * REFNAME_DIR and REFNAME_ALLOW_ONELEVEL are both passed, then
+ * additionally the empty string (no trailing slash allowed) is
+ * allowed.
+ */
 int check_refname_format(const char *refname, int flags)
 {
 	int component_len, component_count = 0;
@@ -74,7 +91,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] == '/')) {
@@ -86,16 +103,36 @@ int check_refname_format(const char *refname, int flags)
 			}
 		}
 		component_count++;
-		if (refname[component_len] == '\0')
+		if (refname[component_len] == '\0') {
+			if (flags & REFNAME_DIR) {
+				/*
+				 * The last component of a REFNAME_DIR
+				 * *must* be the empty string.
+				 */
+				if (component_len != 0)
+					return -1;
+			} else {
+				/*
+				 * The last component of a
+				 * non-REFNAME_DIR *must not* be the
+				 * empty string.
+				 */
+				if (component_len == 0)
+					return -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. */
+
 			break;
+		}
+		if (component_len == 0)
+			return -1; /* Double '/' */
 		/* 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;
 }
 
@@ -111,15 +148,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];
 };
 
@@ -140,18 +216,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;
@@ -162,6 +249,28 @@ 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/").
+ */
+static struct ref_entry *create_dir_entry(const char *dirname)
+{
+	struct ref_entry *direntry;
+	if (*dirname) {
+		int len = strlen(dirname);
+		direntry = xcalloc(1, sizeof(struct ref_entry) + len + 1);
+		memcpy(direntry->name, dirname, len + 1);
+		if (check_refname_format(direntry->name, REFNAME_DIR|REFNAME_ALLOW_ONELEVEL))
+			die("reference directory has invalid format: '%s'", direntry->name);
+	} else {
+		direntry = xcalloc(1, sizeof(struct ref_entry) + 1);
+		direntry->name[0] = '\0';
+	}
+	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;
@@ -169,16 +278,26 @@ static int ref_entry_cmp(const void *a, const void *b)
 	return strcmp(one->name, two->name);
 }
 
+static void sort_ref_dir(struct ref_dir *dir);
+
+/*
+ * Return the entry with the given refname from the ref_dir
+ * (non-recursively).  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;
+	/*
+	 * We need dir to be sorted so that binary search works.
+	 * FIXME: Sorting the array each time is terribly inefficient,
+	 * and has to be changed.
+	 */
+	sort_ref_dir(dir);
 
 	len = strlen(refname) + 1;
 	e = xmalloc(sizeof(struct ref_entry) + len);
@@ -195,46 +314,116 @@ 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.  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, 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;
 }
 
 static void sort_ref_dir(struct ref_dir *dir)
 {
-	int i = 0, j = 1;
+	int i, j;
+	struct ref_entry *last = NULL;
 
-	/* Nothing to sort unless there are at least two entries */
-	if (dir->nr < 2)
+	if (!dir->nr)
 		return;
 
 	qsort(dir->entries, dir->nr, sizeof(*dir->entries), ref_entry_cmp);
 
-	/* Remove any duplicates from the ref_dir */
-	for (; j < dir->nr; j++) {
-		struct ref_entry *a = dir->entries[i];
-		struct ref_entry *b = dir->entries[j];
-		if (is_dup_ref(a, b)) {
-			free_ref_entry(b);
-			continue;
+	/* Remove any duplicates and sort subdirectories: */
+	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 if (entry->flag & REF_DIR) {
+			sort_ref_dir(&entry->u.subdir);
+			dir->entries[i++] = entry;
+			last = NULL;
+		} else {
+			last = dir->entries[i++] = entry;
 		}
-		i++;
-		dir->entries[i] = dir->entries[j];
 	}
-	dir->nr = i + 1;
+	dir->nr = i;
 }
 
 #define DO_FOR_EACH_INCLUDE_BROKEN 01
@@ -265,7 +454,14 @@ static int do_for_each_ref_in_dir(struct ref_dir *dir, int offset,
 {
 	int i;
 	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) {
+			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;
 	}
@@ -281,7 +477,7 @@ static int do_for_each_ref_in_dirs(struct ref_dir *dir1,
 	int i1 = 0, i2 = 0;
 
 	while (1) {
-		struct ref_entry *e1, *e2;
+		struct ref_entry *e1, *e2, *entry;
 		int cmp;
 		if (i1 == dir1->nr) {
 			return do_for_each_ref_in_dir(dir2, i2,
@@ -295,16 +491,37 @@ static int do_for_each_ref_in_dirs(struct ref_dir *dir1,
 		e2 = dir2->entries[i2];
 		cmp = strcmp(e1->name, e2->name);
 		if (cmp == 0) {
-			/* Two refs with the same name; ignore the one from dir1. */
-			i1++;
-			continue;
-		}
-		if (cmp < 0) {
-			retval = do_one_ref(base, fn, trim, flags, cb_data, e1);
-			i1++;
+			if ((e1->flag & REF_DIR) && (e2->flag & REF_DIR)) {
+				/* Both are directories; descend them in parallel. */
+				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) {
+				entry = e1;
+				i1++;
+			} else {
+				entry = e2;
+				i2++;
+			}
+			if (entry->flag & REF_DIR) {
+				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;
@@ -634,7 +851,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;
 
@@ -706,7 +923,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;
@@ -866,7 +1083,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);
@@ -1380,7 +1597,7 @@ static int repack_without_ref(const char *refname)
 	struct ref_dir *packed;
 
 	packed = get_packed_refs(get_ref_cache(NULL));
-	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.c b/refs.c
index 6b4d5d5..8733a08 100644
--- a/refs.c
+++ b/refs.c
@@ -145,6 +145,10 @@ struct ref_value {
 
 struct ref_dir {
 	int nr, alloc;
+
+	/* How many of the entries in this directory are sorted? */
+	int sorted;
+
 	struct ref_entry **entries;
 };
 
@@ -245,7 +249,7 @@ static void clear_ref_dir(struct ref_dir *dir)
 	for (i = 0; i < dir->nr; i++)
 		free_ref_entry(dir->entries[i]);
 	free(dir->entries);
-	dir->nr = dir->alloc = 0;
+	dir->sorted = dir->nr = dir->alloc = 0;
 	dir->entries = NULL;
 }
 
@@ -294,8 +298,9 @@ static struct ref_entry *search_ref_dir(struct ref_dir *dir, const char *refname
 
 	/*
 	 * We need dir to be sorted so that binary search works.
-	 * FIXME: Sorting the array each time is terribly inefficient,
-	 * and has to be changed.
+	 * Calling sort_ref_dir() here is not quite as terribly
+	 * inefficient as it looks, because directories that are
+	 * already sorted are not re-sorted.
 	 */
 	sort_ref_dir(dir);
 
@@ -400,13 +405,27 @@ static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2
 	return 1;
 }
 
+/*
+ * Sort the entries in dir and its subdirectories (if they are not
+ * already sorted).
+ */
 static void sort_ref_dir(struct ref_dir *dir)
 {
 	int i, j;
 	struct ref_entry *last = NULL;
 
-	if (!dir->nr)
+	if (dir->sorted == dir->nr) {
+		/*
+		 * This directory is already sorted and de-duped, but
+		 * we still have to sort subdirectories.
+		 */
+		for (i = 0; i < dir->nr; i++) {
+			struct ref_entry *entry = dir->entries[i];
+			if (entry->flag & REF_DIR)
+				sort_ref_dir(&entry->u.subdir);
+		}
 		return;
+	}
 
 	qsort(dir->entries, dir->nr, sizeof(*dir->entries), ref_entry_cmp);
 
@@ -423,7 +442,7 @@ static void sort_ref_dir(struct ref_dir *dir)
 			last = dir->entries[i++] = entry;
 		}
 	}
-	dir->nr = i;
+	dir->sorted = dir->nr = i;
 }
 
 #define DO_FOR_EACH_INCLUDE_BROKEN 01

refs.c, refs.h

diff --git a/refs.c b/refs.c
index 8733a08..733d7a8 100644
--- a/refs.c
+++ b/refs.c
@@ -298,9 +298,14 @@ static struct ref_entry *search_ref_dir(struct ref_dir *dir, const char *refname
 
 	/*
 	 * We need dir to be sorted so that binary search works.
-	 * Calling sort_ref_dir() here is not quite as terribly
-	 * inefficient as it looks, because directories that are
-	 * already sorted are not re-sorted.
+	 * Calling sort_ref_dir() here is not as terribly inefficient
+	 * as it looks.  (1) If the directory is already sorted, it is
+	 * not re-sorted. (2) When adding a reference,
+	 * search_ref_dir() is only called to find the containing
+	 * subdirectories; there is no search of the directory to
+	 * which the reference will be stored.  Thus adding a bunch of
+	 * references one after the other to a single subdirectory
+	 * doesn't require *any* intermediate sorting.
 	 */
 	sort_ref_dir(dir);
 
@@ -406,26 +411,16 @@ static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2
 }
 
 /*
- * Sort the entries in dir and its subdirectories (if they are not
- * already sorted).
+ * Sort the entries in dir (if they are not already sorted).  Sort
+ * only dir itself, not its subdirectories.
  */
 static void sort_ref_dir(struct ref_dir *dir)
 {
 	int i, j;
 	struct ref_entry *last = NULL;
 
-	if (dir->sorted == dir->nr) {
-		/*
-		 * This directory is already sorted and de-duped, but
-		 * we still have to sort subdirectories.
-		 */
-		for (i = 0; i < dir->nr; i++) {
-			struct ref_entry *entry = dir->entries[i];
-			if (entry->flag & REF_DIR)
-				sort_ref_dir(&entry->u.subdir);
-		}
-		return;
-	}
+	if (dir->sorted == dir->nr)
+		return; /* This directory is already sorted and de-duped */
 
 	qsort(dir->entries, dir->nr, sizeof(*dir->entries), ref_entry_cmp);
 
@@ -435,7 +430,6 @@ static void sort_ref_dir(struct ref_dir *dir)
 		if (last && is_dup_ref(last, entry)) {
 			free_ref_entry(entry);
 		} else if (entry->flag & REF_DIR) {
-			sort_ref_dir(&entry->u.subdir);
 			dir->entries[i++] = entry;
 			last = NULL;
 		} else {
@@ -472,6 +466,7 @@ static int do_for_each_ref_in_dir(struct ref_dir *dir, int offset,
 				  each_ref_fn fn, int trim, int flags, void *cb_data)
 {
 	int i;
+	sort_ref_dir(dir);
 	for (i = offset; i < dir->nr; i++) {
 		struct ref_entry *entry = dir->entries[i];
 		int retval;
@@ -495,6 +490,8 @@ static int do_for_each_ref_in_dirs(struct ref_dir *dir1,
 	int retval;
 	int i1 = 0, i2 = 0;
 
+	sort_ref_dir(dir1);
+	sort_ref_dir(dir2);
 	while (1) {
 		struct ref_entry *e1, *e2, *entry;
 		int cmp;
@@ -746,7 +743,6 @@ static void read_packed_refs(FILE *f, struct ref_dir *dir)
 		    !get_sha1_hex(refline + 1, sha1))
 			hashcpy(last->u.value.peeled, sha1);
 	}
-	sort_ref_dir(dir);
 }
 
 void add_extra_ref(const char *refname, const unsigned char *sha1, int flag)
@@ -849,7 +845,6 @@ static struct ref_dir *get_loose_refs(struct ref_cache *refs)
 {
 	if (!refs->did_loose) {
 		get_ref_dir(refs, "refs", &refs->loose);
-		sort_ref_dir(&refs->loose);
 		refs->did_loose = 1;
 	}
 	return &refs->loose;
diff --git a/refs.h b/refs.h
index d498291..5bb4678 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 *);

diff --git a/refs.c b/refs.c
index 733d7a8..515b44c 100644
--- a/refs.c
+++ b/refs.c
@@ -1156,13 +1156,34 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn
 {
 	int retval = 0;
 	struct ref_cache *refs = get_ref_cache(submodule);
+	struct ref_dir *extra_dir = &extra_refs;
+	struct ref_dir *packed_dir = get_packed_refs(refs);
+	struct ref_dir *loose_dir = get_loose_refs(refs);
 
-	retval = do_for_each_ref_in_dir(&extra_refs, 0,
+	if (base && *base) {
+		extra_dir = find_containing_dir(extra_dir, base, 0);
+		packed_dir = find_containing_dir(packed_dir, base, 0);
+		loose_dir = find_containing_dir(loose_dir, base, 0);
+	}
+
+	if (extra_dir)
+		retval = do_for_each_ref_in_dir(
+				extra_dir, 0,
+				base, fn, trim, flags, cb_data);
+	if (!retval) {
+		if (packed_dir && loose_dir)
+			retval = do_for_each_ref_in_dirs(
+					packed_dir, loose_dir,
+					base, fn, trim, flags, cb_data);
+		else if (packed_dir)
+			retval = do_for_each_ref_in_dir(
+					packed_dir, 0,
 					base, fn, trim, flags, cb_data);
-	if (!retval)
-		retval = do_for_each_ref_in_dirs(get_packed_refs(refs),
-						 get_loose_refs(refs),
-						 base, fn, trim, flags, cb_data);
+		else if (loose_dir)
+			retval = do_for_each_ref_in_dir(
+					loose_dir, 0,
+					base, fn, trim, flags, cb_data);
+	}
 
 	current_ref = NULL;
 	return retval;

diff --git a/refs.c b/refs.c
index 515b44c..bdd90c5 100644
--- a/refs.c
+++ b/refs.c
@@ -775,29 +775,36 @@ static struct ref_dir *get_packed_refs(struct ref_cache *refs)
 	return &refs->packed;
 }
 
-static void get_ref_dir(struct ref_cache *refs, const char *base,
-			struct ref_dir *dir)
+/*
+ * dirname must match the name associated with dir; in particular, it
+ * must end with '/'.
+ */
+static void get_ref_dir(struct ref_cache *refs, const char *dirname)
 {
 	DIR *d;
-	const char *path;
+	char *path;
+	int dirnamelen = strlen(dirname);
+	int pathlen;
+	struct ref_dir *dir;
+
+	assert(dirnamelen && dirname[dirnamelen - 1] == '/');
+
+	dir = find_containing_dir(&refs->loose, dirname, 1);
 
 	if (*refs->name)
-		path = git_path_submodule(refs->name, "%s", base);
+		path = git_path_submodule(refs->name, "%s", dirname);
 	else
-		path = git_path("%s", base);
-
+		path = git_path("%s", dirname);
+	pathlen = strlen(path);
+	assert(pathlen && path[pathlen - 1] == '/');
+	path[pathlen - 1] = '\0';
 
 	d = opendir(path);
 
 	if (d) {
 		struct dirent *de;
-		int baselen = strlen(base);
-		char *refname = xmalloc(baselen + 257);
-
-		memcpy(refname, base, baselen);
-		if (baselen && base[baselen-1] != '/')
-			refname[baselen++] = '/';
-
+		char *refname = xmalloc(dirnamelen + 257);
+		memcpy(refname, dirname, dirnamelen);
 		while ((de = readdir(d)) != NULL) {
 			unsigned char sha1[20];
 			struct stat st;
@@ -812,14 +819,16 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,
 				continue;
 			if (has_extension(de->d_name, ".lock"))
 				continue;
-			memcpy(refname + baselen, de->d_name, namelen+1);
+			memcpy(refname + dirnamelen, de->d_name, namelen+1);
 			refdir = *refs->name
 				? git_path_submodule(refs->name, "%s", refname)
 				: git_path("%s", refname);
 			if (stat(refdir, &st) < 0)
 				continue;
 			if (S_ISDIR(st.st_mode)) {
-				get_ref_dir(refs, refname, dir);
+				refname[dirnamelen + namelen] = '/';
+				refname[dirnamelen + namelen + 1] = '\0';
+				get_ref_dir(refs, refname);
 				continue;
 			}
 			if (*refs->name) {
@@ -834,7 +843,7 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,
 					hashclr(sha1);
 					flag |= REF_ISBROKEN;
 				}
-			add_ref(dir, create_ref_entry(refname, sha1, flag));
+			add_entry_to_dir(dir, create_ref_entry(refname, sha1, flag));
 		}
 		free(refname);
 		closedir(d);
@@ -844,7 +853,7 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,
 static struct ref_dir *get_loose_refs(struct ref_cache *refs)
 {
 	if (!refs->did_loose) {
-		get_ref_dir(refs, "refs", &refs->loose);
+		get_ref_dir(refs, "refs/");
 		refs->did_loose = 1;
 	}
 	return &refs->loose;

diff --git a/refs.c b/refs.c
index bdd90c5..673fa04 100644
--- a/refs.c
+++ b/refs.c
@@ -256,7 +256,7 @@ static void clear_ref_dir(struct ref_dir *dir)
 /*
  * 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/").
+ * "refs/heads/") or "" for the top-level directory.
  */
 static struct ref_entry *create_dir_entry(const char *dirname)
 {
@@ -609,28 +609,28 @@ static int is_refname_available(const char *refname, const char *oldrefname,
  */
 static struct ref_cache {
 	struct ref_cache *next;
-	char did_loose;
-	char did_packed;
-	struct ref_dir loose;
-	struct ref_dir packed;
+	struct ref_entry *loose;
+	struct ref_entry *packed;
 	/* The submodule name, or "" for the main repo. */
 	char name[FLEX_ARRAY];
 } *ref_cache;
 
-static struct ref_dir extra_refs;
+static struct ref_entry *extra_refs;
 
 static void clear_packed_ref_cache(struct ref_cache *refs)
 {
-	if (refs->did_packed)
-		clear_ref_dir(&refs->packed);
-	refs->did_packed = 0;
+	if (refs->packed) {
+		free_ref_entry(refs->packed);
+		refs->packed = NULL;
+	}
 }
 
 static void clear_loose_ref_cache(struct ref_cache *refs)
 {
-	if (refs->did_loose)
-		clear_ref_dir(&refs->loose);
-	refs->did_loose = 0;
+	if (refs->loose) {
+		free_ref_entry(refs->loose);
+		refs->loose = NULL;
+	}
 }
 
 static struct ref_cache *create_ref_cache(const char *submodule)
@@ -747,32 +747,37 @@ static void read_packed_refs(FILE *f, struct ref_dir *dir)
 
 void add_extra_ref(const char *refname, const unsigned char *sha1, int flag)
 {
-	add_ref(&extra_refs, create_ref_entry(refname, sha1, flag));
+	if (!extra_refs)
+		extra_refs = create_dir_entry("");
+	add_ref(&extra_refs->u.subdir, create_ref_entry(refname, sha1, flag));
 }
 
 void clear_extra_refs(void)
 {
-	clear_ref_dir(&extra_refs);
+	if (extra_refs) {
+		free_ref_entry(extra_refs);
+		extra_refs = NULL;
+	}
 }
 
 static struct ref_dir *get_packed_refs(struct ref_cache *refs)
 {
-	if (!refs->did_packed) {
+	if (!refs->packed) {
 		const char *packed_refs_file;
 		FILE *f;
 
+		refs->packed = create_dir_entry("");
 		if (*refs->name)
 			packed_refs_file = git_path_submodule(refs->name, "packed-refs");
 		else
 			packed_refs_file = git_path("packed-refs");
 		f = fopen(packed_refs_file, "r");
 		if (f) {
-			read_packed_refs(f, &refs->packed);
+			read_packed_refs(f, &refs->packed->u.subdir);
 			fclose(f);
 		}
-		refs->did_packed = 1;
 	}
-	return &refs->packed;
+	return &refs->packed->u.subdir;
 }
 
 /*
@@ -789,7 +794,7 @@ static void get_ref_dir(struct ref_cache *refs, const char *dirname)
 
 	assert(dirnamelen && dirname[dirnamelen - 1] == '/');
 
-	dir = find_containing_dir(&refs->loose, dirname, 1);
+	dir = find_containing_dir(&refs->loose->u.subdir, dirname, 1);
 
 	if (*refs->name)
 		path = git_path_submodule(refs->name, "%s", dirname);
@@ -852,11 +857,11 @@ static void get_ref_dir(struct ref_cache *refs, const char *dirname)
 
 static struct ref_dir *get_loose_refs(struct ref_cache *refs)
 {
-	if (!refs->did_loose) {
+	if (!refs->loose) {
+		refs->loose = create_dir_entry("");
 		get_ref_dir(refs, "refs/");
-		refs->did_loose = 1;
 	}
-	return &refs->loose;
+	return &refs->loose->u.subdir;
 }
 
 /* We allow "recursive" symbolic refs. Only within reason, though */
@@ -1165,12 +1170,13 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn
 {
 	int retval = 0;
 	struct ref_cache *refs = get_ref_cache(submodule);
-	struct ref_dir *extra_dir = &extra_refs;
+	struct ref_dir *extra_dir = extra_refs ? &extra_refs->u.subdir : NULL;
 	struct ref_dir *packed_dir = get_packed_refs(refs);
 	struct ref_dir *loose_dir = get_loose_refs(refs);
 
 	if (base && *base) {
-		extra_dir = find_containing_dir(extra_dir, base, 0);
+		if (extra_dir)
+			extra_dir = find_containing_dir(extra_dir, base, 0);
 		packed_dir = find_containing_dir(packed_dir, base, 0);
 		loose_dir = find_containing_dir(loose_dir, base, 0);
 	}

diff --git a/refs.c b/refs.c
index 673fa04..425fdaa 100644
--- a/refs.c
+++ b/refs.c
@@ -760,7 +760,7 @@ void clear_extra_refs(void)
 	}
 }
 
-static struct ref_dir *get_packed_refs(struct ref_cache *refs)
+static struct ref_entry *get_packed_refs(struct ref_cache *refs)
 {
 	if (!refs->packed) {
 		const char *packed_refs_file;
@@ -777,7 +777,7 @@ static struct ref_dir *get_packed_refs(struct ref_cache *refs)
 			fclose(f);
 		}
 	}
-	return &refs->packed->u.subdir;
+	return refs->packed;
 }
 
 /*
@@ -877,9 +877,9 @@ static int resolve_gitlink_packed_ref(struct ref_cache *refs,
 				      const char *refname, unsigned char *sha1)
 {
 	struct ref_entry *ref;
-	struct ref_dir *dir = get_packed_refs(refs);
+	struct ref_entry *direntry = get_packed_refs(refs);
 
-	ref = find_ref(dir, refname);
+	ref = find_ref(&direntry->u.subdir, refname);
 	if (ref == NULL)
 		return -1;
 
@@ -950,8 +950,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_dir *packed = get_packed_refs(get_ref_cache(NULL));
-	struct ref_entry *entry = find_ref(packed, refname);
+	struct ref_entry *packed = get_packed_refs(get_ref_cache(NULL));
+	struct ref_entry *entry = find_ref(&packed->u.subdir, refname);
 	if (entry) {
 		hashcpy(sha1, entry->u.value.sha1);
 		return 0;
@@ -1110,8 +1110,8 @@ int peel_ref(const char *refname, unsigned char *sha1)
 		return -1;
 
 	if ((flag & REF_ISPACKED)) {
-		struct ref_dir *dir = get_packed_refs(get_ref_cache(NULL));
-		struct ref_entry *r = find_ref(dir, refname);
+		struct ref_entry *direntry = get_packed_refs(get_ref_cache(NULL));
+		struct ref_entry *r = find_ref(&direntry->u.subdir, refname);
 
 		if (r != NULL && r->flag & REF_KNOWS_PEELED) {
 			hashcpy(sha1, r->u.value.peeled);
@@ -1171,7 +1171,8 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn
 	int retval = 0;
 	struct ref_cache *refs = get_ref_cache(submodule);
 	struct ref_dir *extra_dir = extra_refs ? &extra_refs->u.subdir : NULL;
-	struct ref_dir *packed_dir = get_packed_refs(refs);
+	struct ref_entry *packed_direntry = get_packed_refs(refs);
+	struct ref_dir *packed_dir = &packed_direntry->u.subdir;
 	struct ref_dir *loose_dir = get_loose_refs(refs);
 
 	if (base && *base) {
@@ -1564,7 +1565,8 @@ static struct ref_lock *lock_ref_sha1_basic(const char *refname,
 	 * name is a proper prefix of our refname.
 	 */
 	if (missing &&
-	     !is_refname_available(refname, NULL, get_packed_refs(get_ref_cache(NULL)))) {
+	     !is_refname_available(refname, NULL,
+				   &get_packed_refs(get_ref_cache(NULL))->u.subdir)) {
 		last_errno = ENOTDIR;
 		goto error_return;
 	}
@@ -1644,10 +1646,8 @@ static struct lock_file packlock;
 static int repack_without_ref(const char *refname)
 {
 	struct repack_without_ref_sb data;
-	struct ref_dir *packed;
-
-	packed = get_packed_refs(get_ref_cache(NULL));
-	if (find_ref(packed, refname) == NULL)
+	struct ref_entry *packed = get_packed_refs(get_ref_cache(NULL));
+	if (find_ref(&packed->u.subdir, refname) == NULL)
 		return 0;
 	data.refname = refname;
 	data.fd = hold_lock_file_for_update(&packlock, git_path("packed-refs"), 0);
@@ -1655,7 +1655,8 @@ 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_dir(packed, 0, "", repack_without_ref_fn, 0, 0, &data);
+	do_for_each_ref_in_dir(&packed->u.subdir, 0,
+			       "", repack_without_ref_fn, 0, 0, &data);
 	return commit_lock_file(&packlock);
 }
 
@@ -1726,7 +1727,7 @@ int rename_ref(const char *oldrefname, const char *newrefname, const char *logms
 	if (!symref)
 		return error("refname %s not found", oldrefname);
 
-	if (!is_refname_available(newrefname, oldrefname, get_packed_refs(refs)))
+	if (!is_refname_available(newrefname, oldrefname, &get_packed_refs(refs)->u.subdir))
 		return 1;
 
 	if (!is_refname_available(newrefname, oldrefname, get_loose_refs(refs)))

diff --git a/refs.c b/refs.c
index 425fdaa..d6d5d0e 100644
--- a/refs.c
+++ b/refs.c
@@ -855,13 +855,13 @@ static void get_ref_dir(struct ref_cache *refs, const char *dirname)
 	}
 }
 
-static struct ref_dir *get_loose_refs(struct ref_cache *refs)
+static struct ref_entry *get_loose_refs(struct ref_cache *refs)
 {
 	if (!refs->loose) {
 		refs->loose = create_dir_entry("");
 		get_ref_dir(refs, "refs/");
 	}
-	return &refs->loose->u.subdir;
+	return refs->loose;
 }
 
 /* We allow "recursive" symbolic refs. Only within reason, though */
@@ -1173,7 +1173,8 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn
 	struct ref_dir *extra_dir = extra_refs ? &extra_refs->u.subdir : NULL;
 	struct ref_entry *packed_direntry = get_packed_refs(refs);
 	struct ref_dir *packed_dir = &packed_direntry->u.subdir;
-	struct ref_dir *loose_dir = get_loose_refs(refs);
+	struct ref_entry *loose_direntry = get_loose_refs(refs);
+	struct ref_dir *loose_dir = &loose_direntry->u.subdir;
 
 	if (base && *base) {
 		if (extra_dir)
@@ -1730,7 +1731,7 @@ int rename_ref(const char *oldrefname, const char *newrefname, const char *logms
 	if (!is_refname_available(newrefname, oldrefname, &get_packed_refs(refs)->u.subdir))
 		return 1;
 
-	if (!is_refname_available(newrefname, oldrefname, get_loose_refs(refs)))
+	if (!is_refname_available(newrefname, oldrefname, &get_loose_refs(refs)->u.subdir))
 		return 1;
 
 	if (log && rename(git_path("logs/%s", oldrefname), git_path(TMP_RENAMED_LOG)))

diff --git a/refs.c b/refs.c
index d6d5d0e..6bda033 100644
--- a/refs.c
+++ b/refs.c
@@ -586,14 +586,16 @@ 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_dir *dir)
+				struct ref_entry *direntry)
 {
 	struct name_conflict_cb data;
 	data.refname = refname;
 	data.oldrefname = oldrefname;
 	data.conflicting_refname = NULL;
 
-	if (do_for_each_ref_in_dir(dir, 0, "", name_conflict_fn,
+	assert(direntry->flag & REF_DIR);
+
+	if (do_for_each_ref_in_dir(&direntry->u.subdir, 0, "", name_conflict_fn,
 				   0, DO_FOR_EACH_INCLUDE_BROKEN,
 				   &data)) {
 		error("'%s' exists; cannot create '%s'",
@@ -1567,7 +1569,7 @@ static struct ref_lock *lock_ref_sha1_basic(const char *refname,
 	 */
 	if (missing &&
 	     !is_refname_available(refname, NULL,
-				   &get_packed_refs(get_ref_cache(NULL))->u.subdir)) {
+				   get_packed_refs(get_ref_cache(NULL)))) {
 		last_errno = ENOTDIR;
 		goto error_return;
 	}
@@ -1728,10 +1730,10 @@ int rename_ref(const char *oldrefname, const char *newrefname, const char *logms
 	if (!symref)
 		return error("refname %s not found", oldrefname);
 
-	if (!is_refname_available(newrefname, oldrefname, &get_packed_refs(refs)->u.subdir))
+	if (!is_refname_available(newrefname, oldrefname, get_packed_refs(refs)))
 		return 1;
 
-	if (!is_refname_available(newrefname, oldrefname, &get_loose_refs(refs)->u.subdir))
+	if (!is_refname_available(newrefname, oldrefname, get_loose_refs(refs)))
 		return 1;
 
 	if (log && rename(git_path("logs/%s", oldrefname), git_path(TMP_RENAMED_LOG)))

diff --git a/refs.c b/refs.c
index 6bda033..e7d4482 100644
--- a/refs.c
+++ b/refs.c
@@ -363,10 +363,12 @@ static struct ref_dir *find_containing_dir(struct ref_dir *dir,
  * 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)
+static struct ref_entry *find_ref(struct ref_entry *direntry, const char *refname)
 {
 	struct ref_entry *entry;
-	dir = find_containing_dir(dir, refname, 0);
+	struct ref_dir *dir;
+	assert(direntry->flag & REF_DIR);
+	dir = find_containing_dir(&direntry->u.subdir, refname, 0);
 	if (!dir)
 		return NULL;
 	entry = search_ref_dir(dir, refname);
@@ -881,7 +883,7 @@ static int resolve_gitlink_packed_ref(struct ref_cache *refs,
 	struct ref_entry *ref;
 	struct ref_entry *direntry = get_packed_refs(refs);
 
-	ref = find_ref(&direntry->u.subdir, refname);
+	ref = find_ref(direntry, refname);
 	if (ref == NULL)
 		return -1;
 
@@ -953,7 +955,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_entry *packed = get_packed_refs(get_ref_cache(NULL));
-	struct ref_entry *entry = find_ref(&packed->u.subdir, refname);
+	struct ref_entry *entry = find_ref(packed, refname);
 	if (entry) {
 		hashcpy(sha1, entry->u.value.sha1);
 		return 0;
@@ -1113,7 +1115,7 @@ int peel_ref(const char *refname, unsigned char *sha1)
 
 	if ((flag & REF_ISPACKED)) {
 		struct ref_entry *direntry = get_packed_refs(get_ref_cache(NULL));
-		struct ref_entry *r = find_ref(&direntry->u.subdir, refname);
+		struct ref_entry *r = find_ref(direntry, refname);
 
 		if (r != NULL && r->flag & REF_KNOWS_PEELED) {
 			hashcpy(sha1, r->u.value.peeled);
@@ -1650,7 +1652,7 @@ static int repack_without_ref(const char *refname)
 {
 	struct repack_without_ref_sb data;
 	struct ref_entry *packed = get_packed_refs(get_ref_cache(NULL));
-	if (find_ref(&packed->u.subdir, 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.c b/refs.c
index e7d4482..f402d39 100644
--- a/refs.c
+++ b/refs.c
@@ -715,12 +715,13 @@ static const char *parse_ref_line(char *line, unsigned char *sha1)
 	return line;
 }
 
-static void read_packed_refs(FILE *f, struct ref_dir *dir)
+static void read_packed_refs(FILE *f, struct ref_entry *direntry)
 {
 	struct ref_entry *last = NULL;
 	char refline[PATH_MAX];
 	int flag = REF_ISPACKED;
 
+	assert(direntry->flag & REF_DIR);
 	while (fgets(refline, sizeof(refline), f)) {
 		unsigned char sha1[20];
 		const char *refname;
@@ -737,7 +738,7 @@ static void read_packed_refs(FILE *f, struct ref_dir *dir)
 		refname = parse_ref_line(refline, sha1);
 		if (refname) {
 			last = create_ref_entry(refname, sha1, flag);
-			add_ref(dir, last);
+			add_ref(&direntry->u.subdir, last);
 			continue;
 		}
 		if (last &&
@@ -777,7 +778,7 @@ static struct ref_entry *get_packed_refs(struct ref_cache *refs)
 			packed_refs_file = git_path("packed-refs");
 		f = fopen(packed_refs_file, "r");
 		if (f) {
-			read_packed_refs(f, &refs->packed->u.subdir);
+			read_packed_refs(f, refs->packed);
 			fclose(f);
 		}
 	}

diff --git a/refs.c b/refs.c
index f402d39..f5aaafe 100644
--- a/refs.c
+++ b/refs.c
@@ -380,9 +380,11 @@ static struct ref_entry *find_ref(struct ref_entry *direntry, const char *refnam
  * 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)
+static int add_ref(struct ref_entry *direntry, struct ref_entry *ref)
 {
-	dir = find_containing_dir(dir, ref->name, 1);
+	struct ref_dir *dir;
+	assert(direntry->flag & REF_DIR);
+	dir = find_containing_dir(&direntry->u.subdir, ref->name, 1);
 	if (!dir)
 		return -1;
 	add_entry_to_dir(dir, ref);
@@ -738,7 +740,7 @@ static void read_packed_refs(FILE *f, struct ref_entry *direntry)
 		refname = parse_ref_line(refline, sha1);
 		if (refname) {
 			last = create_ref_entry(refname, sha1, flag);
-			add_ref(&direntry->u.subdir, last);
+			add_ref(direntry, last);
 			continue;
 		}
 		if (last &&
@@ -754,7 +756,7 @@ void add_extra_ref(const char *refname, const unsigned char *sha1, int flag)
 {
 	if (!extra_refs)
 		extra_refs = create_dir_entry("");
-	add_ref(&extra_refs->u.subdir, create_ref_entry(refname, sha1, flag));
+	add_ref(extra_refs, create_ref_entry(refname, sha1, flag));
 }
 
 void clear_extra_refs(void)

diff --git a/refs.c b/refs.c
index f5aaafe..35b3ff2 100644
--- a/refs.c
+++ b/refs.c
@@ -324,38 +324,40 @@ 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
+ * If refname is a reference name, find the ref_entry 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.  Recurse into subdirectories as
- * necessary.  If mkdir is set, then create any missing directories;
- * otherwise, return NULL if the desired directory cannot be found.
+ * (i.e., "" or ends in '/'), then return that ref_entry itself.  dir
+ * must represent the top-level directory.  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)
+static struct ref_entry *find_containing_direntry(struct ref_entry *direntry,
+						  const char *refname, int mkdir)
 {
 	char *refname_copy = xstrdup(refname);
 	char *slash;
-	struct ref_entry *entry;
+	assert(direntry->flag & REF_DIR);
 	for (slash = strchr(refname_copy, '/'); slash; slash = strchr(slash + 1, '/')) {
 		char tmp = slash[1];
+		struct ref_entry *entry;
 		slash[1] = '\0';
-		entry = search_ref_dir(dir, refname_copy);
+		entry = search_ref_dir(&direntry->u.subdir, refname_copy);
 		if (!entry) {
 			if (!mkdir) {
-				dir = NULL;
+				direntry = NULL;
 				break;
 			}
 			entry = create_dir_entry(refname_copy);
-			add_entry_to_dir(dir, entry);
+			add_entry_to_dir(&direntry->u.subdir, entry);
 		}
 		slash[1] = tmp;
 		assert(entry->flag & REF_DIR);
-		dir = &entry->u.subdir;
+		direntry = entry;
 	}
 
 	free(refname_copy);
-	return dir;
+	return direntry;
 }
 
 /*
@@ -366,12 +368,11 @@ static struct ref_dir *find_containing_dir(struct ref_dir *dir,
 static struct ref_entry *find_ref(struct ref_entry *direntry, const char *refname)
 {
 	struct ref_entry *entry;
-	struct ref_dir *dir;
 	assert(direntry->flag & REF_DIR);
-	dir = find_containing_dir(&direntry->u.subdir, refname, 0);
-	if (!dir)
+	direntry = find_containing_direntry(direntry, refname, 0);
+	if (!direntry)
 		return NULL;
-	entry = search_ref_dir(dir, refname);
+	entry = search_ref_dir(&direntry->u.subdir, refname);
 	return (entry && !(entry->flag & REF_DIR)) ? entry : NULL;
 }
 
@@ -382,12 +383,11 @@ static struct ref_entry *find_ref(struct ref_entry *direntry, const char *refnam
  */
 static int add_ref(struct ref_entry *direntry, struct ref_entry *ref)
 {
-	struct ref_dir *dir;
 	assert(direntry->flag & REF_DIR);
-	dir = find_containing_dir(&direntry->u.subdir, ref->name, 1);
-	if (!dir)
+	direntry = find_containing_direntry(direntry, ref->name, 1);
+	if (!direntry)
 		return -1;
-	add_entry_to_dir(dir, ref);
+	add_entry_to_dir(&direntry->u.subdir, ref);
 	return 0;
 }
 
@@ -797,11 +797,11 @@ static void get_ref_dir(struct ref_cache *refs, const char *dirname)
 	char *path;
 	int dirnamelen = strlen(dirname);
 	int pathlen;
-	struct ref_dir *dir;
+	struct ref_entry *direntry;
 
 	assert(dirnamelen && dirname[dirnamelen - 1] == '/');
 
-	dir = find_containing_dir(&refs->loose->u.subdir, dirname, 1);
+	direntry = find_containing_direntry(refs->loose, dirname, 1);
 
 	if (*refs->name)
 		path = git_path_submodule(refs->name, "%s", dirname);
@@ -855,7 +855,8 @@ static void get_ref_dir(struct ref_cache *refs, const char *dirname)
 					hashclr(sha1);
 					flag |= REF_ISBROKEN;
 				}
-			add_entry_to_dir(dir, create_ref_entry(refname, sha1, flag));
+			add_entry_to_dir(&direntry->u.subdir,
+					 create_ref_entry(refname, sha1, flag));
 		}
 		free(refname);
 		closedir(d);
@@ -1177,35 +1178,34 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn
 {
 	int retval = 0;
 	struct ref_cache *refs = get_ref_cache(submodule);
-	struct ref_dir *extra_dir = extra_refs ? &extra_refs->u.subdir : NULL;
+	struct ref_entry *extra_direntry = extra_refs;
 	struct ref_entry *packed_direntry = get_packed_refs(refs);
-	struct ref_dir *packed_dir = &packed_direntry->u.subdir;
 	struct ref_entry *loose_direntry = get_loose_refs(refs);
-	struct ref_dir *loose_dir = &loose_direntry->u.subdir;
 
 	if (base && *base) {
-		if (extra_dir)
-			extra_dir = find_containing_dir(extra_dir, base, 0);
-		packed_dir = find_containing_dir(packed_dir, base, 0);
-		loose_dir = find_containing_dir(loose_dir, base, 0);
+		if (extra_direntry)
+			extra_direntry = find_containing_direntry(extra_direntry, base, 0);
+		packed_direntry = find_containing_direntry(packed_direntry, base, 0);
+		loose_direntry = find_containing_direntry(loose_direntry, base, 0);
 	}
 
-	if (extra_dir)
+	if (extra_direntry)
 		retval = do_for_each_ref_in_dir(
-				extra_dir, 0,
+				&extra_direntry->u.subdir, 0,
 				base, fn, trim, flags, cb_data);
 	if (!retval) {
-		if (packed_dir && loose_dir)
+		if (packed_direntry && loose_direntry)
 			retval = do_for_each_ref_in_dirs(
-					packed_dir, loose_dir,
+					&packed_direntry->u.subdir,
+					&loose_direntry->u.subdir,
 					base, fn, trim, flags, cb_data);
-		else if (packed_dir)
+		else if (packed_direntry)
 			retval = do_for_each_ref_in_dir(
-					packed_dir, 0,
+					&packed_direntry->u.subdir, 0,
 					base, fn, trim, flags, cb_data);
-		else if (loose_dir)
+		else if (loose_direntry)
 			retval = do_for_each_ref_in_dir(
-					loose_dir, 0,
+					&loose_direntry->u.subdir, 0,
 					base, fn, trim, flags, cb_data);
 	}
 

diff --git a/refs.c b/refs.c
index 35b3ff2..e91cc15 100644
--- a/refs.c
+++ b/refs.c
@@ -288,11 +288,14 @@ static void sort_ref_dir(struct ref_dir *dir);
  * Return the entry with the given refname from the ref_dir
  * (non-recursively).  Return NULL if no such entry is found.
  */
-static struct ref_entry *search_ref_dir(struct ref_dir *dir, const char *refname)
+static struct ref_entry *search_ref_dir(struct ref_entry *direntry, const char *refname)
 {
 	struct ref_entry *e, **r;
 	int len;
+	struct ref_dir *dir;
 
+	assert(direntry->flag & REF_DIR);
+	dir = &direntry->u.subdir;
 	if (refname == NULL || !dir->nr)
 		return NULL;
 
@@ -342,7 +345,7 @@ static struct ref_entry *find_containing_direntry(struct ref_entry *direntry,
 		char tmp = slash[1];
 		struct ref_entry *entry;
 		slash[1] = '\0';
-		entry = search_ref_dir(&direntry->u.subdir, refname_copy);
+		entry = search_ref_dir(direntry, refname_copy);
 		if (!entry) {
 			if (!mkdir) {
 				direntry = NULL;
@@ -372,7 +375,7 @@ static struct ref_entry *find_ref(struct ref_entry *direntry, const char *refnam
 	direntry = find_containing_direntry(direntry, refname, 0);
 	if (!direntry)
 		return NULL;
-	entry = search_ref_dir(&direntry->u.subdir, refname);
+	entry = search_ref_dir(direntry, refname);
 	return (entry && !(entry->flag & REF_DIR)) ? entry : NULL;
 }
 

diff --git a/refs.c b/refs.c
index e91cc15..3567d56 100644
--- a/refs.c
+++ b/refs.c
@@ -234,8 +234,11 @@ static void free_ref_entry(struct ref_entry *entry)
  * stored directly in dir; no recursion into subdirectories is
  * done.
  */
-static void add_entry_to_dir(struct ref_dir *dir, struct ref_entry *entry)
+static void add_entry(struct ref_entry *direntry, struct ref_entry *entry)
 {
+	struct ref_dir *dir;
+	assert(direntry->flag & REF_DIR);
+	dir = &direntry->u.subdir;
 	ALLOC_GROW(dir->entries, dir->nr + 1, dir->alloc);
 	dir->entries[dir->nr++] = entry;
 }
@@ -352,7 +355,7 @@ static struct ref_entry *find_containing_direntry(struct ref_entry *direntry,
 				break;
 			}
 			entry = create_dir_entry(refname_copy);
-			add_entry_to_dir(&direntry->u.subdir, entry);
+			add_entry(direntry, entry);
 		}
 		slash[1] = tmp;
 		assert(entry->flag & REF_DIR);
@@ -390,7 +393,7 @@ static int add_ref(struct ref_entry *direntry, struct ref_entry *ref)
 	direntry = find_containing_direntry(direntry, ref->name, 1);
 	if (!direntry)
 		return -1;
-	add_entry_to_dir(&direntry->u.subdir, ref);
+	add_entry(direntry, ref);
 	return 0;
 }
 
@@ -858,8 +861,7 @@ static void get_ref_dir(struct ref_cache *refs, const char *dirname)
 					hashclr(sha1);
 					flag |= REF_ISBROKEN;
 				}
-			add_entry_to_dir(&direntry->u.subdir,
-					 create_ref_entry(refname, sha1, flag));
+			add_entry(direntry, create_ref_entry(refname, sha1, flag));
 		}
 		free(refname);
 		closedir(d);

diff --git a/refs.c b/refs.c
index 3567d56..c3ee93d 100644
--- a/refs.c
+++ b/refs.c
@@ -471,17 +471,20 @@ static int do_one_ref(const char *base, each_ref_fn fn, int trim,
 	return fn(entry->name + trim, entry->u.value.sha1, entry->flag, cb_data);
 }
 
-static int do_for_each_ref_in_dir(struct ref_dir *dir, int offset,
+static int do_for_each_ref_in_dir(struct ref_entry *direntry, int offset,
 				  const char *base,
 				  each_ref_fn fn, int trim, int flags, void *cb_data)
 {
 	int i;
+	struct ref_dir *dir;
+	assert(direntry->flag & REF_DIR);
+	dir = &direntry->u.subdir;
 	sort_ref_dir(dir);
 	for (i = offset; i < dir->nr; i++) {
 		struct ref_entry *entry = dir->entries[i];
 		int retval;
 		if (entry->flag & REF_DIR) {
-			retval = do_for_each_ref_in_dir(&entry->u.subdir, 0,
+			retval = do_for_each_ref_in_dir(entry, 0,
 							base, fn, trim, flags, cb_data);
 		} else {
 			retval = do_one_ref(base, fn, trim, flags, cb_data, entry);
@@ -492,25 +495,30 @@ static int do_for_each_ref_in_dir(struct ref_dir *dir, int offset,
 	return 0;
 }
 
-static int do_for_each_ref_in_dirs(struct ref_dir *dir1,
-				   struct ref_dir *dir2,
+static int do_for_each_ref_in_dirs(struct ref_entry *direntry1,
+				   struct ref_entry *direntry2,
 				   const char *base, each_ref_fn fn, int trim,
 				   int flags, void *cb_data)
 {
 	int retval;
 	int i1 = 0, i2 = 0;
+	struct ref_dir *dir1, *dir2;
 
+	assert(direntry1->flag & REF_DIR);
+	assert(direntry2->flag & REF_DIR);
+	dir1 = &direntry1->u.subdir;
+	dir2 = &direntry2->u.subdir;
 	sort_ref_dir(dir1);
 	sort_ref_dir(dir2);
 	while (1) {
 		struct ref_entry *e1, *e2, *entry;
 		int cmp;
 		if (i1 == dir1->nr) {
-			return do_for_each_ref_in_dir(dir2, i2,
+			return do_for_each_ref_in_dir(direntry2, i2,
 						      base, fn, trim, flags, cb_data);
 		}
 		if (i2 == dir2->nr) {
-			return do_for_each_ref_in_dir(dir1, i1,
+			return do_for_each_ref_in_dir(direntry1, i1,
 						      base, fn, trim, flags, cb_data);
 		}
 		e1 = dir1->entries[i1];
@@ -520,7 +528,7 @@ static int do_for_each_ref_in_dirs(struct ref_dir *dir1,
 			if ((e1->flag & REF_DIR) && (e2->flag & REF_DIR)) {
 				/* Both are directories; descend them in parallel. */
 				retval = do_for_each_ref_in_dirs(
-						&e1->u.subdir, &e2->u.subdir,
+						e1, e2,
 						base, fn, trim, flags, cb_data);
 				i1++;
 				i2++;
@@ -543,7 +551,7 @@ static int do_for_each_ref_in_dirs(struct ref_dir *dir1,
 			}
 			if (entry->flag & REF_DIR) {
 				retval = do_for_each_ref_in_dir(
-						&entry->u.subdir, 0,
+						entry, 0,
 						base, fn, trim, flags, cb_data);
 			} else {
 				retval = do_one_ref(base, fn, trim, flags, cb_data, entry);
@@ -605,7 +613,7 @@ static int is_refname_available(const char *refname, const char *oldrefname,
 
 	assert(direntry->flag & REF_DIR);
 
-	if (do_for_each_ref_in_dir(&direntry->u.subdir, 0, "", name_conflict_fn,
+	if (do_for_each_ref_in_dir(direntry, 0, "", name_conflict_fn,
 				   0, DO_FOR_EACH_INCLUDE_BROKEN,
 				   &data)) {
 		error("'%s' exists; cannot create '%s'",
@@ -1196,21 +1204,20 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn
 
 	if (extra_direntry)
 		retval = do_for_each_ref_in_dir(
-				&extra_direntry->u.subdir, 0,
+				extra_direntry, 0,
 				base, fn, trim, flags, cb_data);
 	if (!retval) {
 		if (packed_direntry && loose_direntry)
 			retval = do_for_each_ref_in_dirs(
-					&packed_direntry->u.subdir,
-					&loose_direntry->u.subdir,
+					packed_direntry, loose_direntry,
 					base, fn, trim, flags, cb_data);
 		else if (packed_direntry)
 			retval = do_for_each_ref_in_dir(
-					&packed_direntry->u.subdir, 0,
+					packed_direntry, 0,
 					base, fn, trim, flags, cb_data);
 		else if (loose_direntry)
 			retval = do_for_each_ref_in_dir(
-					&loose_direntry->u.subdir, 0,
+					loose_direntry, 0,
 					base, fn, trim, flags, cb_data);
 	}
 
@@ -1668,8 +1675,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_dir(&packed->u.subdir, 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);
 }
 

diff --git a/refs.c b/refs.c
index c3ee93d..98c8569 100644
--- a/refs.c
+++ b/refs.c
@@ -285,7 +285,7 @@ static int ref_entry_cmp(const void *a, const void *b)
 	return strcmp(one->name, two->name);
 }
 
-static void sort_ref_dir(struct ref_dir *dir);
+static void sort_ref_dir(struct ref_entry *direntry);
 
 /*
  * Return the entry with the given refname from the ref_dir
@@ -313,7 +313,7 @@ static struct ref_entry *search_ref_dir(struct ref_entry *direntry, const char *
 	 * references one after the other to a single subdirectory
 	 * doesn't require *any* intermediate sorting.
 	 */
-	sort_ref_dir(dir);
+	sort_ref_dir(direntry);
 
 	len = strlen(refname) + 1;
 	e = xmalloc(sizeof(struct ref_entry) + len);
@@ -424,11 +424,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
  * only dir itself, not its subdirectories.
  */
-static void sort_ref_dir(struct ref_dir *dir)
+static void sort_ref_dir(struct ref_entry *direntry)
 {
 	int i, j;
 	struct ref_entry *last = NULL;
-
+	struct ref_dir *dir;
+	assert(direntry->flag & REF_DIR);
+	dir = &direntry->u.subdir;
 	if (dir->sorted == dir->nr)
 		return; /* This directory is already sorted and de-duped */
 
@@ -479,7 +481,7 @@ static int do_for_each_ref_in_dir(struct ref_entry *direntry, int offset,
 	struct ref_dir *dir;
 	assert(direntry->flag & REF_DIR);
 	dir = &direntry->u.subdir;
-	sort_ref_dir(dir);
+	sort_ref_dir(direntry);
 	for (i = offset; i < dir->nr; i++) {
 		struct ref_entry *entry = dir->entries[i];
 		int retval;
@@ -508,8 +510,8 @@ static int do_for_each_ref_in_dirs(struct ref_entry *direntry1,
 	assert(direntry2->flag & REF_DIR);
 	dir1 = &direntry1->u.subdir;
 	dir2 = &direntry2->u.subdir;
-	sort_ref_dir(dir1);
-	sort_ref_dir(dir2);
+	sort_ref_dir(direntry1);
+	sort_ref_dir(direntry2);
 	while (1) {
 		struct ref_entry *e1, *e2, *entry;
 		int cmp;

diff --git a/refs.c b/refs.c
index 98c8569..6b2b2f6 100644
--- a/refs.c
+++ b/refs.c
@@ -143,6 +143,8 @@ struct ref_value {
 	unsigned char peeled[20];
 };
 
+struct ref_cache;
+
 struct ref_dir {
 	int nr, alloc;
 
@@ -150,6 +152,12 @@ struct ref_dir {
 	int sorted;
 
 	struct ref_entry **entries;
+
+	/*
+	 * A pointer to the ref_cache that contains this ref_dir, or
+	 * NULL if this ref_dir is used for extra_refs.
+	 */
+	struct ref_cache *ref_cache;
 };
 
 /* ISSYMREF=0x01, ISPACKED=0x02, and ISBROKEN=0x04 are public interfaces */
@@ -261,7 +269,8 @@ static void clear_ref_dir(struct ref_dir *dir)
  * 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)
+static struct ref_entry *create_dir_entry(struct ref_cache *ref_cache,
+					  const char *dirname)
 {
 	struct ref_entry *direntry;
 	if (*dirname) {
@@ -275,6 +284,7 @@ static struct ref_entry *create_dir_entry(const char *dirname)
 		direntry->name[0] = '\0';
 	}
 	direntry->flag = REF_DIR;
+	direntry->u.subdir.ref_cache = ref_cache;
 	return direntry;
 }
 
@@ -354,7 +364,8 @@ static struct ref_entry *find_containing_direntry(struct ref_entry *direntry,
 				direntry = NULL;
 				break;
 			}
-			entry = create_dir_entry(refname_copy);
+			entry = create_dir_entry(direntry->u.subdir.ref_cache,
+						 refname_copy);
 			add_entry(direntry, entry);
 		}
 		slash[1] = tmp;
@@ -771,7 +782,7 @@ static void read_packed_refs(FILE *f, struct ref_entry *direntry)
 void add_extra_ref(const char *refname, const unsigned char *sha1, int flag)
 {
 	if (!extra_refs)
-		extra_refs = create_dir_entry("");
+		extra_refs = create_dir_entry(NULL, "");
 	add_ref(extra_refs, create_ref_entry(refname, sha1, flag));
 }
 
@@ -789,7 +800,7 @@ static struct ref_entry *get_packed_refs(struct ref_cache *refs)
 		const char *packed_refs_file;
 		FILE *f;
 
-		refs->packed = create_dir_entry("");
+		refs->packed = create_dir_entry(refs, "");
 		if (*refs->name)
 			packed_refs_file = git_path_submodule(refs->name, "packed-refs");
 		else
@@ -881,7 +892,7 @@ static void get_ref_dir(struct ref_cache *refs, const char *dirname)
 static struct ref_entry *get_loose_refs(struct ref_cache *refs)
 {
 	if (!refs->loose) {
-		refs->loose = create_dir_entry("");
+		refs->loose = create_dir_entry(refs, "");
 		get_ref_dir(refs, "refs/");
 	}
 	return refs->loose;

diff --git a/refs.c b/refs.c
index 6b2b2f6..f3910de 100644
--- a/refs.c
+++ b/refs.c
@@ -815,21 +815,20 @@ static struct ref_entry *get_packed_refs(struct ref_cache *refs)
 }
 
 /*
- * dirname must match the name associated with dir; in particular, it
- * must end with '/'.
+ * Fill direntry with loose references read from the filesystem.
  */
-static void get_ref_dir(struct ref_cache *refs, const char *dirname)
+static void read_loose_refs(struct ref_entry *direntry)
 {
 	DIR *d;
 	char *path;
+	char *dirname = direntry->name;
 	int dirnamelen = strlen(dirname);
 	int pathlen;
-	struct ref_entry *direntry;
-
-	assert(dirnamelen && dirname[dirnamelen - 1] == '/');
-
-	direntry = find_containing_direntry(refs->loose, dirname, 1);
+	struct ref_cache *refs;
 
+	assert(direntry->flag & REF_DIR);
+	assert(dirnamelen && direntry->name[dirnamelen - 1] == '/');
+	refs = direntry->u.subdir.ref_cache;
 	if (*refs->name)
 		path = git_path_submodule(refs->name, "%s", dirname);
 	else
@@ -867,7 +866,9 @@ static void get_ref_dir(struct ref_cache *refs, const char *dirname)
 			if (S_ISDIR(st.st_mode)) {
 				refname[dirnamelen + namelen] = '/';
 				refname[dirnamelen + namelen + 1] = '\0';
-				get_ref_dir(refs, refname);
+				read_loose_refs(find_containing_direntry(
+								refs->loose,
+								refname, 1));
 				continue;
 			}
 			if (*refs->name) {
@@ -893,7 +894,7 @@ static struct ref_entry *get_loose_refs(struct ref_cache *refs)
 {
 	if (!refs->loose) {
 		refs->loose = create_dir_entry(refs, "");
-		get_ref_dir(refs, "refs/");
+		read_loose_refs(find_containing_direntry(refs->loose, "refs/", 1));
 	}
 	return refs->loose;
 }

diff --git a/refs.c b/refs.c
index f3910de..88ef9dd 100644
--- a/refs.c
+++ b/refs.c
@@ -138,6 +138,12 @@ int check_refname_format(const char *refname, int flags)
 
 struct ref_entry;
 
+/*
+ * Information used (along with the information in ref_entry) to
+ * describe a single cached reference.  This data structure only
+ * occurs embedded in a union in struct ref_entry, and only when
+ * (ref_entry->flag & REF_DIR) is zero.
+ */
 struct ref_value {
 	unsigned char sha1[20];
 	unsigned char peeled[20];
@@ -145,6 +151,34 @@ struct ref_value {
 
 struct ref_cache;
 
+/*
+ * Information used (along with the information in ref_entry) to
+ * describe a level in the hierarchy of references.  This data
+ * structure only occurs embedded in a union in struct ref_entry, and
+ * only when (ref_entry.flag & REF_DIR) is nonzero.  In that case,
+ * (ref_entry.flag & REF_DIR) can take the following values:
+ *
+ *     REF_DIR_COMPLETE -- a directory of loose or packed references,
+ *         already read.
+ *
+ *     REF_DIR_INCOMPLETE -- a directory of loose references that
+ *         hasn't been read yet (nor has any of its subdirectories).
+ *
+ * Entries within a directory are stored within a growable array of
+ * pointers to ref_entries (entries, nr, alloc).  Entries 0 <= i <
+ * sorted are sorted by their component name in strcmp() order and the
+ * remaining entries are unsorted.
+ *
+ * Loose references are read lazily, one directory at a time.  When a
+ * directory of loose references is read, then all of the references
+ * in that directory are stored, and REF_DIR_INCOMPLETE stubs are
+ * created for any subdirectories, but the subdirectories themselves
+ * are not read.  The reading is triggered either by search_ref_dir()
+ * (called when single references are added or interrogated), by
+ * sort_ref_dir(), or by iteration over a subdirectory of references
+ * using one of the for_each_ref*() functions (which calls
+ * sort_ref_dir() for each subdirectory).
+ */
 struct ref_dir {
 	int nr, alloc;
 
@@ -162,19 +196,33 @@ struct ref_dir {
 
 /* ISSYMREF=0x01, ISPACKED=0x02, and ISBROKEN=0x04 are public interfaces */
 #define REF_KNOWS_PEELED 0x08
-#define REF_DIR 0x10
+
+/* If any of these bits are set, the entry represents a directory: */
+#define REF_DIR 0x30
+
+/* A directory that has already been fully read. */
+#define REF_DIR_COMPLETE 0x10
+
+/* A directory of loose references that has not yet been fully read. */
+#define REF_DIR_INCOMPLETE 0x20
 
 /*
  * 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).
+ * 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 that have been read so
+ * far.  If (flags & REF_DIR) == REF_DIR_INCOMPLETE, then the
+ * directory and its subdirectories haven't been read yet.
+ * REF_DIR_INCOMPLETE is only used for loose references.
+ *
+ * References are represented by a ref_entry with (flags & REF_DIR) ==
+ * 0 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
@@ -264,13 +312,15 @@ static void clear_ref_dir(struct ref_dir *dir)
 	dir->entries = NULL;
 }
 
+static void read_loose_refs(struct ref_entry *direntry);
+
 /*
  * 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(struct ref_cache *ref_cache,
-					  const char *dirname)
+					  const char *dirname, int flag)
 {
 	struct ref_entry *direntry;
 	if (*dirname) {
@@ -283,7 +333,7 @@ static struct ref_entry *create_dir_entry(struct ref_cache *ref_cache,
 		direntry = xcalloc(1, sizeof(struct ref_entry) + 1);
 		direntry->name[0] = '\0';
 	}
-	direntry->flag = REF_DIR;
+	direntry->flag = flag;
 	direntry->u.subdir.ref_cache = ref_cache;
 	return direntry;
 }
@@ -308,6 +358,7 @@ static struct ref_entry *search_ref_dir(struct ref_entry *direntry, const char *
 	struct ref_dir *dir;
 
 	assert(direntry->flag & REF_DIR);
+	read_loose_refs(direntry);
 	dir = &direntry->u.subdir;
 	if (refname == NULL || !dir->nr)
 		return NULL;
@@ -364,8 +415,14 @@ static struct ref_entry *find_containing_direntry(struct ref_entry *direntry,
 				direntry = NULL;
 				break;
 			}
+			/*
+			 * If search_ref_dir() above didn't make the
+			 * entry spring into existence, then this must
+			 * not be an unread loose reference tree, so
+			 * the correct flag is REF_DIR_COMPLETE.
+			 */
 			entry = create_dir_entry(direntry->u.subdir.ref_cache,
-						 refname_copy);
+						 refname_copy, REF_DIR_COMPLETE);
 			add_entry(direntry, entry);
 		}
 		slash[1] = tmp;
@@ -441,6 +498,7 @@ static void sort_ref_dir(struct ref_entry *direntry)
 	struct ref_entry *last = NULL;
 	struct ref_dir *dir;
 	assert(direntry->flag & REF_DIR);
+	read_loose_refs(direntry);
 	dir = &direntry->u.subdir;
 	if (dir->sorted == dir->nr)
 		return; /* This directory is already sorted and de-duped */
@@ -491,8 +549,8 @@ static int do_for_each_ref_in_dir(struct ref_entry *direntry, int offset,
 	int i;
 	struct ref_dir *dir;
 	assert(direntry->flag & REF_DIR);
-	dir = &direntry->u.subdir;
 	sort_ref_dir(direntry);
+	dir = &direntry->u.subdir;
 	for (i = offset; i < dir->nr; i++) {
 		struct ref_entry *entry = dir->entries[i];
 		int retval;
@@ -519,10 +577,10 @@ static int do_for_each_ref_in_dirs(struct ref_entry *direntry1,
 
 	assert(direntry1->flag & REF_DIR);
 	assert(direntry2->flag & REF_DIR);
-	dir1 = &direntry1->u.subdir;
-	dir2 = &direntry2->u.subdir;
 	sort_ref_dir(direntry1);
 	sort_ref_dir(direntry2);
+	dir1 = &direntry1->u.subdir;
+	dir2 = &direntry2->u.subdir;
 	while (1) {
 		struct ref_entry *e1, *e2, *entry;
 		int cmp;
@@ -782,7 +840,7 @@ static void read_packed_refs(FILE *f, struct ref_entry *direntry)
 void add_extra_ref(const char *refname, const unsigned char *sha1, int flag)
 {
 	if (!extra_refs)
-		extra_refs = create_dir_entry(NULL, "");
+		extra_refs = create_dir_entry(NULL, "", REF_DIR_COMPLETE);
 	add_ref(extra_refs, create_ref_entry(refname, sha1, flag));
 }
 
@@ -800,7 +858,7 @@ static struct ref_entry *get_packed_refs(struct ref_cache *refs)
 		const char *packed_refs_file;
 		FILE *f;
 
-		refs->packed = create_dir_entry(refs, "");
+		refs->packed = create_dir_entry(refs, "", REF_DIR_COMPLETE);
 		if (*refs->name)
 			packed_refs_file = git_path_submodule(refs->name, "packed-refs");
 		else
@@ -822,11 +880,14 @@ static void read_loose_refs(struct ref_entry *direntry)
 	DIR *d;
 	char *path;
 	char *dirname = direntry->name;
-	int dirnamelen = strlen(dirname);
+	int dirnamelen;
 	int pathlen;
 	struct ref_cache *refs;
 
 	assert(direntry->flag & REF_DIR);
+	if ((direntry->flag & REF_DIR) != REF_DIR_INCOMPLETE)
+		return;
+	dirnamelen = strlen(dirname);
 	assert(dirnamelen && direntry->name[dirnamelen - 1] == '/');
 	refs = direntry->u.subdir.ref_cache;
 	if (*refs->name)
@@ -864,11 +925,12 @@ static void read_loose_refs(struct ref_entry *direntry)
 			if (stat(refdir, &st) < 0)
 				continue;
 			if (S_ISDIR(st.st_mode)) {
+				struct ref_entry *subdirentry;
 				refname[dirnamelen + namelen] = '/';
 				refname[dirnamelen + namelen + 1] = '\0';
-				read_loose_refs(find_containing_direntry(
-								refs->loose,
-								refname, 1));
+				subdirentry = create_dir_entry(direntry->u.subdir.ref_cache,
+							       refname, REF_DIR_INCOMPLETE);
+				add_entry(direntry, subdirentry);
 				continue;
 			}
 			if (*refs->name) {
@@ -888,13 +950,15 @@ static void read_loose_refs(struct ref_entry *direntry)
 		free(refname);
 		closedir(d);
 	}
+	direntry->flag = REF_DIR_COMPLETE;
 }
 
 static struct ref_entry *get_loose_refs(struct ref_cache *refs)
 {
 	if (!refs->loose) {
-		refs->loose = create_dir_entry(refs, "");
-		read_loose_refs(find_containing_direntry(refs->loose, "refs/", 1));
+		refs->loose = create_dir_entry(refs, "", REF_DIR_COMPLETE);
+		add_entry(refs->loose,
+			  create_dir_entry(refs, "refs/", REF_DIR_INCOMPLETE));
 	}
 	return refs->loose;
 }

diff --git a/refs.c b/refs.c
index 88ef9dd..6a7f9c3 100644
--- a/refs.c
+++ b/refs.c
@@ -658,7 +658,7 @@ static int name_conflict_fn(const char *existingrefname, const unsigned char *sh
 			    int flags, void *cb_data)
 {
 	struct name_conflict_cb *data = (struct name_conflict_cb *)cb_data;
-	if (data->oldrefname && !strcmp(data->oldrefname, existingrefname))
+	if (!strcmp(data->oldrefname, existingrefname))
 		return 0;
 	if (names_conflict(data->refname, existingrefname)) {
 		data->conflicting_refname = existingrefname;
@@ -669,22 +669,48 @@ static int name_conflict_fn(const char *existingrefname, const unsigned char *sh
 
 /*
  * 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 direntry.  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_entry *direntry)
 {
+	int prefixlen = strlen(refname);
+	char *prefix;
+	char *slash;
 	struct name_conflict_cb data;
+
+	assert(direntry->flag & REF_DIR);
+
+	if (!oldrefname)
+		oldrefname = ""; /* invalid; cannot match any existing refname */
+
+	/* Check whether a prefix of refname is an existing reference: */
+	prefix = xmalloc(prefixlen + 2);
+	memcpy(prefix, refname, prefixlen + 1);
+	for (slash = strchr(prefix, '/'); slash; slash = strchr(slash + 1, '/')) {
+		*slash = '\0';
+		if (strcmp(oldrefname, prefix)) {
+			struct ref_entry *entry = find_ref(direntry, prefix);
+			if (entry) {
+				error("'%s' exists; cannot create '%s'", prefix, refname);
+				free(prefix);
+				return 0;
+			}
+		}
+		*slash = '/';
+	}
+
+	/* Check whether refname is a proper prefix of an existing reference: */
+	prefix[prefixlen++] = '/';
+	prefix[prefixlen] = '\0';
 	data.refname = refname;
 	data.oldrefname = oldrefname;
 	data.conflicting_refname = NULL;
 
-	assert(direntry->flag & REF_DIR);
-
-	if (do_for_each_ref_in_dir(direntry, 0, "", name_conflict_fn,
+	if (do_for_each_ref_in_dir(direntry, 0, prefix, name_conflict_fn,
 				   0, DO_FOR_EACH_INCLUDE_BROKEN,
 				   &data)) {
 		error("'%s' exists; cannot create '%s'",

diff --git a/refs.c b/refs.c
index 6a7f9c3..b185c32 100644
--- a/refs.c
+++ b/refs.c
@@ -633,23 +633,7 @@ static int do_for_each_ref_in_dirs(struct ref_entry *direntry1,
 	}
 }
 
-/*
- * 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)
-{
-	for (; *refname1 && *refname1 == *refname2; refname1++, refname2++)
-		;
-	return (*refname1 == '\0' && *refname2 == '/')
-		|| (*refname1 == '/' && *refname2 == '\0');
-}
-
 struct name_conflict_cb {
-	const char *refname;
 	const char *oldrefname;
 	const char *conflicting_refname;
 };
@@ -660,11 +644,13 @@ static int name_conflict_fn(const char *existingrefname, const unsigned char *sh
 	struct name_conflict_cb *data = (struct name_conflict_cb *)cb_data;
 	if (!strcmp(data->oldrefname, existingrefname))
 		return 0;
-	if (names_conflict(data->refname, existingrefname)) {
-		data->conflicting_refname = existingrefname;
-		return 1;
-	}
-	return 0;
+
+	/*
+	 * Since we are only iterating over the subtree that has the
+	 * new refname as prefix, *any* reference found is a conflict.
+	 */
+	data->conflicting_refname = existingrefname;
+	return 1;
 }
 
 /*
@@ -673,6 +659,11 @@ static int name_conflict_fn(const char *existingrefname, const unsigned char *sh
  * oldrefname is non-NULL, ignore potential conflicts with oldrefname
  * (e.g., because oldrefname is scheduled for deletion in the same
  * operation).
+ *
+ * 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 is_refname_available(const char *refname, const char *oldrefname,
 				struct ref_entry *direntry)
@@ -706,11 +697,14 @@ static int is_refname_available(const char *refname, const char *oldrefname,
 	/* Check whether refname is a proper prefix of an existing reference: */
 	prefix[prefixlen++] = '/';
 	prefix[prefixlen] = '\0';
-	data.refname = refname;
 	data.oldrefname = oldrefname;
 	data.conflicting_refname = NULL;
 
-	if (do_for_each_ref_in_dir(direntry, 0, prefix, name_conflict_fn,
+	direntry = find_containing_direntry(direntry, prefix, 0);
+	if (!direntry)
+		return 1;
+
+	if (do_for_each_ref_in_dir(direntry, 0, "", name_conflict_fn,
 				   0, DO_FOR_EACH_INCLUDE_BROKEN,
 				   &data)) {
 		error("'%s' exists; cannot create '%s'",

diff --git a/refs.c b/refs.c
index 6a7f9c3..6a19d19 100644
--- a/refs.c
+++ b/refs.c
@@ -831,6 +831,7 @@ static const char *parse_ref_line(char *line, unsigned char *sha1)
 static void read_packed_refs(FILE *f, struct ref_entry *direntry)
 {
 	struct ref_entry *last = NULL;
+	struct ref_entry *current_direntry = NULL;
 	char refline[PATH_MAX];
 	int flag = REF_ISPACKED;
 
@@ -850,8 +851,21 @@ static void read_packed_refs(FILE *f, struct ref_entry *direntry)
 
 		refname = parse_ref_line(refline, sha1);
 		if (refname) {
+			if (current_direntry) {
+				char *slash = strrchr(refname, '/');
+				if (!slash
+				    || strncmp(current_direntry->name, refname,
+					       slash - refname + 1)
+				    || current_direntry->name[slash - refname + 1] != '\0')
+					/* The new refname does not go in current_direntry */
+					current_direntry = NULL;
+			}
+			if (!current_direntry)
+				current_direntry = find_containing_direntry(
+						direntry, refname, 1);
+
 			last = create_ref_entry(refname, sha1, flag);
-			add_ref(direntry, last);
+			add_entry(current_direntry, last);
 			continue;
 		}
 		if (last &&

diff --git a/refs.c b/refs.c
index 6a19d19..bbf9e3e 100644
--- a/refs.c
+++ b/refs.c
@@ -1784,7 +1784,9 @@ static struct lock_file packlock;
 static int repack_without_ref(const char *refname)
 {
 	struct repack_without_ref_sb data;
-	struct ref_entry *packed = get_packed_refs(get_ref_cache(NULL));
+	struct ref_cache *refs = get_ref_cache(NULL);
+	struct ref_entry *packed = get_packed_refs(refs);
+
 	if (find_ref(packed, refname) == NULL)
 		return 0;
 	data.refname = refname;
@@ -1794,6 +1796,7 @@ static int repack_without_ref(const char *refname)
 		return error("cannot delete '%s' from packed refs", refname);
 	}
 	do_for_each_ref_in_dir(packed, 0, "", repack_without_ref_fn, 0, 0, &data);
+	clear_packed_ref_cache(refs);
 	return commit_lock_file(&packlock);
 }
 
@@ -1822,6 +1825,7 @@ int delete_ref(const char *refname, const unsigned char *sha1, int delopt)
 
 		if (!(delopt & REF_NODEREF))
 			lock->lk->filename[i] = '.';
+		clear_loose_ref_cache(get_ref_cache(NULL));
 	}
 	/* removing the loose one could have resurrected an earlier
 	 * packed one.  Also, if it was not loose we need to repack
@@ -1830,7 +1834,6 @@ int delete_ref(const char *refname, const unsigned char *sha1, int delopt)
 	ret |= repack_without_ref(refname);
 
 	unlink_or_warn(git_path("logs/%s", lock->ref_name));
-	invalidate_ref_cache(NULL);
 	unlock_ref(lock);
 	return ret;
 }