[PATCH 00/30] Read loose references lazily

[PATCH 00/30] Read loose references lazily

[mhagger]

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

This is the next installment of the ref-api saga.  The main result of
this patch series is to teach git to read loose references one
directory at a time, only when they are needed.

The first nine commits are not very interesting; they convert
get_ref_dir() and do_for_each_reflog() to use strbufs and to tighten
up their specifications.  The search_for_subdir() function extracted
in patch 5 will be useful later.  Patch 6 slightly reduces the amount
of work needed to read loose refs from disk, and also changes the
function's API in a way that will be needed later when directories are
read one at a time.

Patches 10 - 25 mostly switch a lot of code from using ref_dir
pointers to using ref_entry pointers as arguments and return values.
This is important, because we want to be able to read directories of
loose references on demand; this means that functions deep in the refs
code need access to the name of directories of references.  Since the
name field is part of ref_entry but not ref_dir, this change has to
percolate through many functions.  The three key patches are patch 18,
which removes the "dirname" argument to get_ref_dir(), and patches 21
and 25, which change search_ref_dir() and sort_ref_dir() to take
ref_entries as argument.  Together, these patches allow
search_ref_dir() and sort_ref_dir() to call get_ref_dir() to fill
directory entries on demand.

Patch 26-28 makes it possible to get from a ref_entry to the ref_cache
of which it is part, and teach get_ref_dir() (renamed to
read_loose_refs()) to use this mechanism to access the name of the
ref_cache that it is to read.

Finally, patches 29 and 30 teach the code to read loose references
lazily.  This is done by adding a distinction between REF_DIR_COMPLETE
and REF_DIR_INCOMPLETE; the latter is used to stub out directories of
loose references that haven't been read yet.  The loose references are
read transparently into a REF_DIR_INCOMPLETE only when they are
needed, at which time the directory entry is transformed into
REF_DIR_COMPLETE.

This patch series has to be applied on top of mh/ref-api (or next).
It passes all tests.  It also includes quite a few assert()s to
verify and document function preconditions.  The asserts should all be
pretty cheap, but if leaving them in is a problem please let me know.

It seems pretty overwhelming, but the changes are implemented in baby
steps and most of the patches are quite simple.

Michael Haggerty (30):
  get_ref_dir(): return early if directory cannot be read
  get_ref_dir(): use a strbuf to hold refname
  get_ref_dir(): rename "base" parameter to "dirname"
  get_ref_dir(): require that the dirname argument ends in '/'
  refs.c: extract function search_for_subdir()
  get_ref_dir(): take the containing directory as argument
  do_for_each_reflog(): return early on error
  do_for_each_reflog(): use a strbuf to hold logfile name
  do_for_each_reflog(): reuse strbuf across recursive function calls
  refs: wrap top-level ref_dirs in ref_entries
  get_packed_refs(): return (ref_entry *) instead of (ref_dir *)
  get_loose_refs(): return (ref_entry *) instead of (ref_dir *)
  is_refname_available(): take (ref_entry *) instead of (ref_dir *)
  find_ref(): take (ref_entry *) instead of (ref_dir *)
  read_packed_refs(): take (ref_entry *) instead of (ref_dir *)
  add_ref(): take (ref_entry *) instead of (ref_dir *)
  find_containing_direntry(): use (ref_entry *) instead of (ref_dir *)
  get_ref_dir(): take (ref_entry *) instead of (ref_dir *)
  get_ref_dir(): remove dirname argument
  search_for_subdir(): take (ref_entry *) instead of (ref_dir *)
  search_ref_dir(): take (ref_entry *) instead of (ref_dir *)
  add_entry(): take (ref_entry *) instead of (ref_dir *)
  do_for_each_ref_in_dirs(): take (ref_entry *) instead of (ref_dir *)
  do_for_each_ref_in_dir(): take (ref_entry *) instead of (ref_dir *)
  sort_ref_dir(): take (ref_entry *) instead of (ref_dir *)
  struct ref_dir: store a reference to the enclosing ref_cache
  read_loose_refs(): rename function from get_ref_dir()
  read_loose_refs(): access ref_cache via the ref_dir field
  create_dir_entry(): allow the flag value to be passed as an argument
  refs: read loose references lazily

 refs.c |  550 +++++++++++++++++++++++++++++++++++++++-------------------------
 1 file changed, 332 insertions(+), 218 deletions(-)

-- 
1.7.10

[PATCH 01/30] get_ref_dir(): return early if directory cannot be read

[mhagger]

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


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

diff --git a/refs.c b/refs.c
index 09322fe..d539241 100644
--- a/refs.c
+++ b/refs.c
@@ -754,6 +754,9 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,
 {
 	DIR *d;
 	const char *path;
+	struct dirent *de;
+	int baselen;
+	char *refname;
 
 	if (*refs->name)
 		path = git_path_submodule(refs->name, "%s", base);
@@ -761,55 +764,55 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,
 		path = git_path("%s", base);
 
 	d = opendir(path);
-	if (d) {
-		struct dirent *de;
-		int baselen = strlen(base);
-		char *refname = xmalloc(baselen + 257);
+	if (!d)
+		return;
 
-		memcpy(refname, base, baselen);
-		if (baselen && base[baselen-1] != '/')
-			refname[baselen++] = '/';
+	baselen = strlen(base);
+	refname = xmalloc(baselen + 257);
 
-		while ((de = readdir(d)) != NULL) {
-			unsigned char sha1[20];
-			struct stat st;
-			int flag;
-			int namelen;
-			const char *refdir;
+	memcpy(refname, base, baselen);
+	if (baselen && base[baselen-1] != '/')
+		refname[baselen++] = '/';
 
-			if (de->d_name[0] == '.')
-				continue;
-			namelen = strlen(de->d_name);
-			if (namelen > 255)
-				continue;
-			if (has_extension(de->d_name, ".lock"))
-				continue;
-			memcpy(refname + baselen, 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);
-				continue;
-			}
-			if (*refs->name) {
-				hashclr(sha1);
-				flag = 0;
-				if (resolve_gitlink_ref(refs->name, refname, sha1) < 0) {
-					hashclr(sha1);
-					flag |= REF_ISBROKEN;
-				}
-			} else if (read_ref_full(refname, sha1, 1, &flag)) {
+	while ((de = readdir(d)) != NULL) {
+		unsigned char sha1[20];
+		struct stat st;
+		int flag;
+		int namelen;
+		const char *refdir;
+
+		if (de->d_name[0] == '.')
+			continue;
+		namelen = strlen(de->d_name);
+		if (namelen > 255)
+			continue;
+		if (has_extension(de->d_name, ".lock"))
+			continue;
+		memcpy(refname + baselen, 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);
+			continue;
+		}
+		if (*refs->name) {
+			hashclr(sha1);
+			flag = 0;
+			if (resolve_gitlink_ref(refs->name, refname, sha1) < 0) {
 				hashclr(sha1);
 				flag |= REF_ISBROKEN;
 			}
-			add_ref(dir, create_ref_entry(refname, sha1, flag, 1));
+		} else if (read_ref_full(refname, sha1, 1, &flag)) {
+			hashclr(sha1);
+			flag |= REF_ISBROKEN;
 		}
-		free(refname);
-		closedir(d);
+		add_ref(dir, create_ref_entry(refname, sha1, flag, 1));
 	}
+	free(refname);
+	closedir(d);
 }
 
 static struct ref_dir *get_loose_refs(struct ref_cache *refs)
-- 
1.7.10

[PATCH 02/30] get_ref_dir(): use a strbuf to hold refname

[mhagger]

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

This simplifies the bookkeeping and allows an (artificial) restriction
on refname component length to be removed.

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

diff --git a/refs.c b/refs.c
index d539241..df98622 100644
--- a/refs.c
+++ b/refs.c
@@ -756,7 +756,7 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,
 	const char *path;
 	struct dirent *de;
 	int baselen;
-	char *refname;
+	struct strbuf refname;
 
 	if (*refs->name)
 		path = git_path_submodule(refs->name, "%s", base);
@@ -768,50 +768,48 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,
 		return;
 
 	baselen = strlen(base);
-	refname = xmalloc(baselen + 257);
-
-	memcpy(refname, base, baselen);
-	if (baselen && base[baselen-1] != '/')
-		refname[baselen++] = '/';
+	strbuf_init(&refname, baselen + 257);
+	strbuf_add(&refname, base, baselen);
+	if (baselen && base[baselen-1] != '/') {
+		strbuf_addch(&refname, '/');
+		baselen++;
+	}
 
 	while ((de = readdir(d)) != NULL) {
 		unsigned char sha1[20];
 		struct stat st;
 		int flag;
-		int namelen;
 		const char *refdir;
 
 		if (de->d_name[0] == '.')
 			continue;
-		namelen = strlen(de->d_name);
-		if (namelen > 255)
-			continue;
 		if (has_extension(de->d_name, ".lock"))
 			continue;
-		memcpy(refname + baselen, de->d_name, namelen+1);
+		strbuf_addstr(&refname, de->d_name);
 		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);
-			continue;
-		}
-		if (*refs->name) {
-			hashclr(sha1);
-			flag = 0;
-			if (resolve_gitlink_ref(refs->name, refname, sha1) < 0) {
+			? git_path_submodule(refs->name, "%s", refname.buf)
+			: git_path("%s", refname.buf);
+		if (stat(refdir, &st) < 0) {
+			/* Silently ignore. */
+		} else if (S_ISDIR(st.st_mode)) {
+			get_ref_dir(refs, refname.buf, dir);
+		} else {
+			if (*refs->name) {
+				hashclr(sha1);
+				flag = 0;
+				if (resolve_gitlink_ref(refs->name, refname.buf, sha1) < 0) {
+					hashclr(sha1);
+					flag |= REF_ISBROKEN;
+				}
+			} else if (read_ref_full(refname.buf, sha1, 1, &flag)) {
 				hashclr(sha1);
 				flag |= REF_ISBROKEN;
 			}
-		} else if (read_ref_full(refname, sha1, 1, &flag)) {
-			hashclr(sha1);
-			flag |= REF_ISBROKEN;
+			add_ref(dir, create_ref_entry(refname.buf, sha1, flag, 1));
 		}
-		add_ref(dir, create_ref_entry(refname, sha1, flag, 1));
+		strbuf_setlen(&refname, baselen);
 	}
-	free(refname);
+	strbuf_release(&refname);
 	closedir(d);
 }
 
-- 
1.7.10

[PATCH 03/30] get_ref_dir(): rename "base" parameter to "dirname"

[mhagger]

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


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

diff --git a/refs.c b/refs.c
index df98622..dc2b4df 100644
--- a/refs.c
+++ b/refs.c
@@ -749,30 +749,30 @@ void add_packed_ref(const char *refname, const unsigned char *sha1)
 			create_ref_entry(refname, sha1, REF_ISPACKED, 1));
 }
 
-static void get_ref_dir(struct ref_cache *refs, const char *base,
+static void get_ref_dir(struct ref_cache *refs, const char *dirname,
 			struct ref_dir *dir)
 {
 	DIR *d;
 	const char *path;
 	struct dirent *de;
-	int baselen;
+	int dirnamelen;
 	struct strbuf refname;
 
 	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);
 
 	d = opendir(path);
 	if (!d)
 		return;
 
-	baselen = strlen(base);
-	strbuf_init(&refname, baselen + 257);
-	strbuf_add(&refname, base, baselen);
-	if (baselen && base[baselen-1] != '/') {
+	dirnamelen = strlen(dirname);
+	strbuf_init(&refname, dirnamelen + 257);
+	strbuf_add(&refname, dirname, dirnamelen);
+	if (dirnamelen && dirname[dirnamelen-1] != '/') {
 		strbuf_addch(&refname, '/');
-		baselen++;
+		dirnamelen++;
 	}
 
 	while ((de = readdir(d)) != NULL) {
@@ -807,7 +807,7 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,
 			}
 			add_ref(dir, create_ref_entry(refname.buf, sha1, flag, 1));
 		}
-		strbuf_setlen(&refname, baselen);
+		strbuf_setlen(&refname, dirnamelen);
 	}
 	strbuf_release(&refname);
 	closedir(d);
-- 
1.7.10

[PATCH 04/30] get_ref_dir(): require that the dirname argument ends in '/'

[mhagger]

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

This removes some conditional code and makes it consistent with the
way that direntry names are stored.  Please note that this function is
never used on the top-level .git directory; it is always called for
directories at level .git/refs or deeper.

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

diff --git a/refs.c b/refs.c
index dc2b4df..01fcdc7 100644
--- a/refs.c
+++ b/refs.c
@@ -749,13 +749,17 @@ void add_packed_ref(const char *refname, const unsigned char *sha1)
 			create_ref_entry(refname, sha1, REF_ISPACKED, 1));
 }
 
+/*
+ * Read the loose references for refs from the namespace dirname.
+ * dirname must end with '/'.
+ */
 static void get_ref_dir(struct ref_cache *refs, const char *dirname,
 			struct ref_dir *dir)
 {
 	DIR *d;
 	const char *path;
 	struct dirent *de;
-	int dirnamelen;
+	int dirnamelen = strlen(dirname);
 	struct strbuf refname;
 
 	if (*refs->name)
@@ -767,13 +771,8 @@ static void get_ref_dir(struct ref_cache *refs, const char *dirname,
 	if (!d)
 		return;
 
-	dirnamelen = strlen(dirname);
 	strbuf_init(&refname, dirnamelen + 257);
 	strbuf_add(&refname, dirname, dirnamelen);
-	if (dirnamelen && dirname[dirnamelen-1] != '/') {
-		strbuf_addch(&refname, '/');
-		dirnamelen++;
-	}
 
 	while ((de = readdir(d)) != NULL) {
 		unsigned char sha1[20];
@@ -792,6 +791,7 @@ static void get_ref_dir(struct ref_cache *refs, const char *dirname,
 		if (stat(refdir, &st) < 0) {
 			/* Silently ignore. */
 		} else if (S_ISDIR(st.st_mode)) {
+			strbuf_addch(&refname, '/');
 			get_ref_dir(refs, refname.buf, dir);
 		} else {
 			if (*refs->name) {
@@ -816,7 +816,7 @@ 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) {
-		get_ref_dir(refs, "refs", &refs->loose);
+		get_ref_dir(refs, "refs/", &refs->loose);
 		refs->did_loose = 1;
 	}
 	return &refs->loose;
-- 
1.7.10

[PATCH 05/30] refs.c: extract function search_for_subdir()

[mhagger]

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


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

diff --git a/refs.c b/refs.c
index 01fcdc7..5e51c10 100644
--- a/refs.c
+++ b/refs.c
@@ -277,6 +277,27 @@ static struct ref_entry *search_ref_dir(struct ref_dir *dir, const char *refname
 }
 
 /*
+ * Search for a directory entry directly within dir (without
+ * recursing).  Sort dir if necessary.  subdirname must be a directory
+ * name (i.e., end in '/').  If mkdir is set, then create the
+ * directory if it is missing; otherwise, return NULL if the desired
+ * directory cannot be found.
+ */
+static struct ref_entry *search_for_subdir(struct ref_dir *dir,
+					   const char *subdirname, int mkdir)
+{
+	struct ref_entry *entry = search_ref_dir(dir, subdirname);
+	if (!entry) {
+		if (!mkdir)
+			return NULL;
+		entry = create_dir_entry(subdirname);
+		add_entry_to_dir(dir, entry);
+	}
+	assert(entry->flag & REF_DIR);
+	return entry;
+}
+
+/*
  * 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
@@ -294,17 +315,10 @@ static struct ref_dir *find_containing_dir(struct ref_dir *dir,
 	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);
-		}
+		entry = search_for_subdir(dir, refname_copy, mkdir);
 		slash[1] = tmp;
-		assert(entry->flag & REF_DIR);
+		if (!entry)
+			break;
 		dir = &entry->u.subdir;
 	}
 
-- 
1.7.10

[PATCH 06/30] get_ref_dir(): take the containing directory as argument

[mhagger]

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

Previously, the "dir" argument to get_ref_dir() was a pointer to the
top-level ref_dir.  Change the function to expect a pointer to the
ref_dir corresponding to dirname.  This allows entries to be added
directly to dir, without having to recurse through the reference trie
each time (i.e., we can use add_entry_to_dir() instead of add_ref()).

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

diff --git a/refs.c b/refs.c
index 5e51c10..8670c2e 100644
--- a/refs.c
+++ b/refs.c
@@ -765,7 +765,8 @@ void add_packed_ref(const char *refname, const unsigned char *sha1)
 
 /*
  * Read the loose references for refs from the namespace dirname.
- * dirname must end with '/'.
+ * dirname must end with '/'.  dir must be the directory entry
+ * corresponding to dirname.
  */
 static void get_ref_dir(struct ref_cache *refs, const char *dirname,
 			struct ref_dir *dir)
@@ -806,7 +807,8 @@ static void get_ref_dir(struct ref_cache *refs, const char *dirname,
 			/* Silently ignore. */
 		} else if (S_ISDIR(st.st_mode)) {
 			strbuf_addch(&refname, '/');
-			get_ref_dir(refs, refname.buf, dir);
+			get_ref_dir(refs, refname.buf,
+				    &search_for_subdir(dir, refname.buf, 1)->u.subdir);
 		} else {
 			if (*refs->name) {
 				hashclr(sha1);
@@ -819,7 +821,8 @@ static void get_ref_dir(struct ref_cache *refs, const char *dirname,
 				hashclr(sha1);
 				flag |= REF_ISBROKEN;
 			}
-			add_ref(dir, create_ref_entry(refname.buf, sha1, flag, 1));
+			add_entry_to_dir(dir,
+					 create_ref_entry(refname.buf, sha1, flag, 1));
 		}
 		strbuf_setlen(&refname, dirnamelen);
 	}
@@ -830,7 +833,8 @@ 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) {
-		get_ref_dir(refs, "refs/", &refs->loose);
+		get_ref_dir(refs, "refs/",
+			    &search_for_subdir(&refs->loose, "refs/", 1)->u.subdir);
 		refs->did_loose = 1;
 	}
 	return &refs->loose;
-- 
1.7.10

[PATCH 07/30] do_for_each_reflog(): return early on error

[mhagger]

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


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

diff --git a/refs.c b/refs.c
index 8670c2e..1d25151 100644
--- a/refs.c
+++ b/refs.c
@@ -2246,47 +2246,47 @@ static int do_for_each_reflog(const char *base, each_ref_fn fn, void *cb_data)
 {
 	DIR *d = opendir(git_path("logs/%s", base));
 	int retval = 0;
+	struct dirent *de;
+	int baselen;
+	char *log;
 
-	if (d) {
-		struct dirent *de;
-		int baselen = strlen(base);
-		char *log = xmalloc(baselen + 257);
+	if (!d)
+		return *base ? errno : 0;
 
-		memcpy(log, base, baselen);
-		if (baselen && base[baselen-1] != '/')
-			log[baselen++] = '/';
+	baselen = strlen(base);
+	log = xmalloc(baselen + 257);
+	memcpy(log, base, baselen);
+	if (baselen && base[baselen-1] != '/')
+		log[baselen++] = '/';
 
-		while ((de = readdir(d)) != NULL) {
-			struct stat st;
-			int namelen;
+	while ((de = readdir(d)) != NULL) {
+		struct stat st;
+		int namelen;
 
-			if (de->d_name[0] == '.')
-				continue;
-			namelen = strlen(de->d_name);
-			if (namelen > 255)
-				continue;
-			if (has_extension(de->d_name, ".lock"))
-				continue;
-			memcpy(log + baselen, de->d_name, namelen+1);
-			if (stat(git_path("logs/%s", log), &st) < 0)
-				continue;
-			if (S_ISDIR(st.st_mode)) {
-				retval = do_for_each_reflog(log, fn, cb_data);
-			} else {
-				unsigned char sha1[20];
-				if (read_ref_full(log, sha1, 0, NULL))
-					retval = error("bad ref for %s", log);
-				else
-					retval = fn(log, sha1, 0, cb_data);
-			}
-			if (retval)
-				break;
+		if (de->d_name[0] == '.')
+			continue;
+		namelen = strlen(de->d_name);
+		if (namelen > 255)
+			continue;
+		if (has_extension(de->d_name, ".lock"))
+			continue;
+		memcpy(log + baselen, de->d_name, namelen+1);
+		if (stat(git_path("logs/%s", log), &st) < 0)
+			continue;
+		if (S_ISDIR(st.st_mode)) {
+			retval = do_for_each_reflog(log, fn, cb_data);
+		} else {
+			unsigned char sha1[20];
+			if (read_ref_full(log, sha1, 0, NULL))
+				retval = error("bad ref for %s", log);
+			else
+				retval = fn(log, sha1, 0, cb_data);
 		}
-		free(log);
-		closedir(d);
+		if (retval)
+			break;
 	}
-	else if (*base)
-		return errno;
+	free(log);
+	closedir(d);
 	return retval;
 }
 
-- 
1.7.10

[PATCH 08/30] do_for_each_reflog(): use a strbuf to hold logfile name

[mhagger]

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

This simplifies the bookkeeping and allows an (artificial) restriction
on refname component length to be removed.

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

diff --git a/refs.c b/refs.c
index 1d25151..f43c255 100644
--- a/refs.c
+++ b/refs.c
@@ -2248,44 +2248,45 @@ static int do_for_each_reflog(const char *base, each_ref_fn fn, void *cb_data)
 	int retval = 0;
 	struct dirent *de;
 	int baselen;
-	char *log;
+	struct strbuf log;
 
 	if (!d)
 		return *base ? errno : 0;
 
 	baselen = strlen(base);
-	log = xmalloc(baselen + 257);
-	memcpy(log, base, baselen);
-	if (baselen && base[baselen-1] != '/')
-		log[baselen++] = '/';
+	strbuf_init(&log, baselen + 257);
+	strbuf_add(&log, base, baselen);
+	if (log.len && log.buf[log.len-1] != '/') {
+		strbuf_addch(&log, '/');
+		baselen++;
+	}
 
 	while ((de = readdir(d)) != NULL) {
 		struct stat st;
-		int namelen;
 
 		if (de->d_name[0] == '.')
 			continue;
-		namelen = strlen(de->d_name);
-		if (namelen > 255)
-			continue;
 		if (has_extension(de->d_name, ".lock"))
 			continue;
-		memcpy(log + baselen, de->d_name, namelen+1);
-		if (stat(git_path("logs/%s", log), &st) < 0)
-			continue;
-		if (S_ISDIR(st.st_mode)) {
-			retval = do_for_each_reflog(log, fn, cb_data);
+		strbuf_addstr(&log, de->d_name);
+		if (stat(git_path("logs/%s", log.buf), &st) < 0) {
+			/* Silently ignore. */
 		} else {
-			unsigned char sha1[20];
-			if (read_ref_full(log, sha1, 0, NULL))
-				retval = error("bad ref for %s", log);
-			else
-				retval = fn(log, sha1, 0, cb_data);
+			if (S_ISDIR(st.st_mode)) {
+				retval = do_for_each_reflog(log.buf, fn, cb_data);
+			} else {
+				unsigned char sha1[20];
+				if (read_ref_full(log.buf, sha1, 0, NULL))
+					retval = error("bad ref for %s", log.buf);
+				else
+					retval = fn(log.buf, sha1, 0, cb_data);
+			}
+			if (retval)
+				break;
 		}
-		if (retval)
-			break;
+		strbuf_setlen(&log, baselen);
 	}
-	free(log);
+	strbuf_release(&log);
 	closedir(d);
 	return retval;
 }
-- 
1.7.10

[PATCH 09/30] do_for_each_reflog(): reuse strbuf across recursive function calls

[mhagger]

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

This saves some memory allocations.  Also require that the name
argument end in slash, which removes some extra bookkeeping.

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

diff --git a/refs.c b/refs.c
index f43c255..989c10d 100644
--- a/refs.c
+++ b/refs.c
@@ -2242,24 +2242,20 @@ int for_each_reflog_ent(const char *refname, each_reflog_ent_fn fn, void *cb_dat
 	return for_each_recent_reflog_ent(refname, fn, 0, cb_data);
 }
 
-static int do_for_each_reflog(const char *base, each_ref_fn fn, void *cb_data)
+/*
+ * Call fn for each reflog in the namespace indicated by name.  name
+ * must be empty or end with '/'.  Name will be used as a scratch
+ * space, but its contents will be restored before return.
+ */
+static int do_for_each_reflog(struct strbuf *name, each_ref_fn fn, void *cb_data)
 {
-	DIR *d = opendir(git_path("logs/%s", base));
+	DIR *d = opendir(git_path("logs/%s", name->buf));
 	int retval = 0;
 	struct dirent *de;
-	int baselen;
-	struct strbuf log;
+	int oldlen = name->len;
 
 	if (!d)
-		return *base ? errno : 0;
-
-	baselen = strlen(base);
-	strbuf_init(&log, baselen + 257);
-	strbuf_add(&log, base, baselen);
-	if (log.len && log.buf[log.len-1] != '/') {
-		strbuf_addch(&log, '/');
-		baselen++;
-	}
+		return name->len ? errno : 0;
 
 	while ((de = readdir(d)) != NULL) {
 		struct stat st;
@@ -2268,32 +2264,37 @@ static int do_for_each_reflog(const char *base, each_ref_fn fn, void *cb_data)
 			continue;
 		if (has_extension(de->d_name, ".lock"))
 			continue;
-		strbuf_addstr(&log, de->d_name);
-		if (stat(git_path("logs/%s", log.buf), &st) < 0) {
+		strbuf_addstr(name, de->d_name);
+		if (stat(git_path("logs/%s", name->buf), &st) < 0) {
 			/* Silently ignore. */
 		} else {
 			if (S_ISDIR(st.st_mode)) {
-				retval = do_for_each_reflog(log.buf, fn, cb_data);
+				strbuf_addch(name, '/');
+				retval = do_for_each_reflog(name, fn, cb_data);
 			} else {
 				unsigned char sha1[20];
-				if (read_ref_full(log.buf, sha1, 0, NULL))
-					retval = error("bad ref for %s", log.buf);
+				if (read_ref_full(name->buf, sha1, 0, NULL))
+					retval = error("bad ref for %s", name->buf);
 				else
-					retval = fn(log.buf, sha1, 0, cb_data);
+					retval = fn(name->buf, sha1, 0, cb_data);
 			}
 			if (retval)
 				break;
 		}
-		strbuf_setlen(&log, baselen);
+		strbuf_setlen(name, oldlen);
 	}
-	strbuf_release(&log);
 	closedir(d);
 	return retval;
 }
 
 int for_each_reflog(each_ref_fn fn, void *cb_data)
 {
-	return do_for_each_reflog("", fn, cb_data);
+	int retval;
+	struct strbuf name;
+	strbuf_init(&name, PATH_MAX);
+	retval = do_for_each_reflog(&name, fn, cb_data);
+	strbuf_release(&name);
+	return retval;
 }
 
 int update_ref(const char *action, const char *refname,
-- 
1.7.10

[PATCH 10/30] refs: wrap top-level ref_dirs in ref_entries

[mhagger]

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

Wrap the top-level ref_dirs in REF_DIR style ref_entries so that we
have the flag and name available when dealing with them.  This
affects:

* cache_ref::loose
* cache_ref::packed
* extra_refs

The next several commits will expand the use of ref_entry as opposed
to ref_dir, culminating in the ability of a ref_entry representing a
directory of loose references to load itself only when used.

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

diff --git a/refs.c b/refs.c
index 989c10d..4c92dc9 100644
--- a/refs.c
+++ b/refs.c
@@ -606,26 +606,26 @@ 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 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)
@@ -739,22 +739,22 @@ static void read_packed_refs(FILE *f, struct ref_dir *dir)
 
 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;
 }
 
 void add_packed_ref(const char *refname, const unsigned char *sha1)
@@ -832,12 +832,13 @@ 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/",
-			    &search_for_subdir(&refs->loose, "refs/", 1)->u.subdir);
-		refs->did_loose = 1;
+			    &search_for_subdir(&refs->loose->u.subdir,
+					       "refs/", 1)->u.subdir);
 	}
-	return &refs->loose;
+	return &refs->loose->u.subdir;
 }
 
 /* We allow "recursive" symbolic refs. Only within reason, though */
-- 
1.7.10

Re: [PATCH 10/30] refs: wrap top-level ref_dirs in ref_entries

[Michael Haggerty]

On 04/25/2012 12:45 AM, mhagger@alum.mit.edu wrote:
> From: Michael Haggerty<mhagger@alum.mit.edu>
>
> Wrap the top-level ref_dirs in REF_DIR style ref_entries so that we
> have the flag and name available when dealing with them.  This
> affects:
>
> * cache_ref::loose
> * cache_ref::packed
> * extra_refs
>
> The next several commits will expand the use of ref_entry as opposed
> to ref_dir, culminating in the ability of a ref_entry representing a
> directory of loose references to load itself only when used.

The mention of "extra_refs" here is of course obsolete and should be 
deleted.

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/

[PATCH 11/30] get_packed_refs(): return (ref_entry *) instead of (ref_dir *)

[mhagger]

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

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

diff --git a/refs.c b/refs.c
index 4c92dc9..24930ab 100644
--- a/refs.c
+++ b/refs.c
@@ -737,7 +737,7 @@ static void read_packed_refs(FILE *f, struct ref_dir *dir)
 	}
 }
 
-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;
@@ -754,13 +754,13 @@ static struct ref_dir *get_packed_refs(struct ref_cache *refs)
 			fclose(f);
 		}
 	}
-	return &refs->packed->u.subdir;
+	return refs->packed;
 }
 
 void add_packed_ref(const char *refname, const unsigned char *sha1)
 {
-	add_ref(get_packed_refs(get_ref_cache(NULL)),
-			create_ref_entry(refname, sha1, REF_ISPACKED, 1));
+	add_ref(&get_packed_refs(get_ref_cache(NULL))->u.subdir,
+		create_ref_entry(refname, sha1, REF_ISPACKED, 1));
 }
 
 /*
@@ -854,9 +854,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;
 
@@ -927,8 +927,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;
@@ -1104,8 +1104,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);
@@ -1163,7 +1163,8 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn
 			   int trim, int flags, void *cb_data)
 {
 	struct ref_cache *refs = get_ref_cache(submodule);
-	struct ref_dir *packed_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);
 	int retval = 0;
 
@@ -1545,7 +1546,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;
 	}
@@ -1625,8 +1627,8 @@ static struct lock_file packlock;
 static int repack_without_ref(const char *refname)
 {
 	struct repack_without_ref_sb data;
-	struct ref_dir *packed = get_packed_refs(get_ref_cache(NULL));
-	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);
@@ -1634,7 +1636,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);
 }
 
@@ -1705,7 +1708,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)))
-- 
1.7.10

[PATCH 12/30] get_loose_refs(): return (ref_entry *) instead of (ref_dir *)

[mhagger]

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

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

diff --git a/refs.c b/refs.c
index 24930ab..0259ad1 100644
--- a/refs.c
+++ b/refs.c
@@ -830,7 +830,7 @@ static void get_ref_dir(struct ref_cache *refs, const char *dirname,
 	closedir(d);
 }
 
-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("");
@@ -838,7 +838,7 @@ static struct ref_dir *get_loose_refs(struct ref_cache *refs)
 			    &search_for_subdir(&refs->loose->u.subdir,
 					       "refs/", 1)->u.subdir);
 	}
-	return &refs->loose->u.subdir;
+	return refs->loose;
 }
 
 /* We allow "recursive" symbolic refs. Only within reason, though */
@@ -1165,7 +1165,8 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn
 	struct ref_cache *refs = get_ref_cache(submodule);
 	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;
 	int retval = 0;
 
 	if (base && *base) {
@@ -1711,7 +1712,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)))
-- 
1.7.10

[PATCH 13/30] is_refname_available(): take (ref_entry *) instead of (ref_dir *)

[mhagger]

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

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

diff --git a/refs.c b/refs.c
index 0259ad1..044dee9 100644
--- a/refs.c
+++ b/refs.c
@@ -576,21 +576,23 @@ 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 in array.  If
+ * 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_dir *dir)
+				struct ref_entry *direntry)
 {
 	struct name_conflict_cb data;
 	data.refname = refname;
 	data.oldrefname = oldrefname;
 	data.conflicting_refname = NULL;
 
-	sort_ref_dir(dir);
-	if (do_for_each_ref_in_dir(dir, 0, "", name_conflict_fn,
+	assert(direntry->flag & REF_DIR);
+	sort_ref_dir(&direntry->u.subdir);
+
+	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'",
@@ -1548,7 +1550,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;
 	}
@@ -1709,10 +1711,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)))
-- 
1.7.10

[PATCH 14/30] find_ref(): take (ref_entry *) instead of (ref_dir *)

[mhagger]

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

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

diff --git a/refs.c b/refs.c
index 044dee9..c40cbd6 100644
--- a/refs.c
+++ b/refs.c
@@ -327,14 +327,17 @@ static struct ref_dir *find_containing_dir(struct ref_dir *dir,
 }
 
 /*
- * Find the value entry with the given name in dir, sorting ref_dirs
- * and recursing into subdirectories as necessary.  If the name is not
- * found or it corresponds to a directory entry, return NULL.
+ * Find the value entry with the given name in direntry, sorting
+ * reference directories and recursing into subdirectories as
+ * necessary.  If the name is not found or it corresponds to a
+ * directory entry, return NULL.
  */
-static struct ref_entry *find_ref(struct ref_dir *dir, const char *refname)
+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);
@@ -858,7 +861,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;
 
@@ -930,7 +933,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;
@@ -1107,7 +1110,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);
@@ -1631,7 +1634,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);
-- 
1.7.10

[PATCH 15/30] read_packed_refs(): take (ref_entry *) instead of (ref_dir *)

[mhagger]

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

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

diff --git a/refs.c b/refs.c
index c40cbd6..694d802 100644
--- a/refs.c
+++ b/refs.c
@@ -708,12 +708,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;
@@ -730,7 +731,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, 1);
-			add_ref(dir, last);
+			add_ref(&direntry->u.subdir, last);
 			continue;
 		}
 		if (last &&
@@ -755,7 +756,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);
 		}
 	}
-- 
1.7.10

[PATCH 16/30] add_ref(): take (ref_entry *) instead of (ref_dir *)

[mhagger]

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

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

diff --git a/refs.c b/refs.c
index 694d802..6077cfb 100644
--- a/refs.c
+++ b/refs.c
@@ -345,13 +345,15 @@ static struct ref_entry *find_ref(struct ref_entry *direntry, const char *refnam
 }
 
 /*
- * 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.
+ * Add ref to the direntry (unsorted), recursing into subdirectories
+ * as necessary.  direntry 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);
@@ -731,7 +733,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, 1);
-			add_ref(&direntry->u.subdir, last);
+			add_ref(direntry, last);
 			continue;
 		}
 		if (last &&
@@ -765,7 +767,7 @@ static struct ref_entry *get_packed_refs(struct ref_cache *refs)
 
 void add_packed_ref(const char *refname, const unsigned char *sha1)
 {
-	add_ref(&get_packed_refs(get_ref_cache(NULL))->u.subdir,
+	add_ref(get_packed_refs(get_ref_cache(NULL)),
 		create_ref_entry(refname, sha1, REF_ISPACKED, 1));
 }
 
-- 
1.7.10

[PATCH 17/30] find_containing_direntry(): use (ref_entry *) instead of (ref_dir *)

[mhagger]

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

Change type of both argument and return value, and rename function
from find_containing_dir() to find_containing_direntry().

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

diff --git a/refs.c b/refs.c
index 6077cfb..140fbe2 100644
--- a/refs.c
+++ b/refs.c
@@ -298,32 +298,30 @@ static struct ref_entry *search_for_subdir(struct ref_dir *dir,
 }
 
 /*
- * If refname is a reference name, find the ref_dir within the dir
- * tree that should hold refname.  If refname is a directory name
- * (i.e., ends in '/'), then return that ref_dir itself.  dir must
- * represent the top-level directory.  Sort ref_dirs and recurse into
- * subdirectories as necessary.  If mkdir is set, then create any
- * missing directories; otherwise, return NULL if the desired
- * directory cannot be found.
+ * If refname is a reference name, find the directory entry within the
+ * direntry tree that should hold refname.  If refname is a directory
+ * name (i.e., ends in '/'), then return that directory entry itself.
+ * direntry must represent the top-level directory.  Sort directories
+ * and recurse into subdirectories as necessary.  If mkdir is set,
+ * then create any missing directories; otherwise, return NULL if the
+ * desired directory cannot be found.
  */
-static struct ref_dir *find_containing_dir(struct ref_dir *dir,
-					   const char *refname, int mkdir)
+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;
 	for (slash = strchr(refname_copy, '/'); slash; slash = strchr(slash + 1, '/')) {
 		char tmp = slash[1];
 		slash[1] = '\0';
-		entry = search_for_subdir(dir, refname_copy, mkdir);
+		direntry = search_for_subdir(&direntry->u.subdir, refname_copy, mkdir);
 		slash[1] = tmp;
-		if (!entry)
+		if (!direntry)
 			break;
-		dir = &entry->u.subdir;
 	}
 
 	free(refname_copy);
-	return dir;
+	return direntry;
 }
 
 /*
@@ -335,12 +333,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;
 }
 
@@ -351,12 +348,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;
 }
 
@@ -1172,31 +1168,30 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn
 {
 	struct ref_cache *refs = get_ref_cache(submodule);
 	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;
 	int retval = 0;
 
 	if (base && *base) {
-		packed_dir = find_containing_dir(packed_dir, base, 0);
-		loose_dir = find_containing_dir(loose_dir, base, 0);
+		packed_direntry = find_containing_direntry(packed_direntry, base, 0);
+		loose_direntry = find_containing_direntry(loose_direntry, base, 0);
 	}
 
-	if (packed_dir && loose_dir) {
-		sort_ref_dir(packed_dir);
-		sort_ref_dir(loose_dir);
+	if (packed_direntry && loose_direntry) {
+		sort_ref_dir(&packed_direntry->u.subdir);
+		sort_ref_dir(&loose_direntry->u.subdir);
 		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) {
-		sort_ref_dir(packed_dir);
+	} else if (packed_direntry) {
+		sort_ref_dir(&packed_direntry->u.subdir);
 		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) {
-		sort_ref_dir(loose_dir);
+	} else if (loose_direntry) {
+		sort_ref_dir(&loose_direntry->u.subdir);
 		retval = do_for_each_ref_in_dir(
-				loose_dir, 0,
+				&loose_direntry->u.subdir, 0,
 				base, fn, trim, flags, cb_data);
 	}
 
-- 
1.7.10

[PATCH 18/30] get_ref_dir(): take (ref_entry *) instead of (ref_dir *)

[mhagger]

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


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

diff --git a/refs.c b/refs.c
index 140fbe2..2057380 100644
--- a/refs.c
+++ b/refs.c
@@ -769,11 +769,11 @@ void add_packed_ref(const char *refname, const unsigned char *sha1)
 
 /*
  * Read the loose references for refs from the namespace dirname.
- * dirname must end with '/'.  dir must be the directory entry
+ * dirname must end with '/'.  direntry must be the directory entry
  * corresponding to dirname.
  */
 static void get_ref_dir(struct ref_cache *refs, const char *dirname,
-			struct ref_dir *dir)
+			struct ref_entry *direntry)
 {
 	DIR *d;
 	const char *path;
@@ -781,6 +781,8 @@ static void get_ref_dir(struct ref_cache *refs, const char *dirname,
 	int dirnamelen = strlen(dirname);
 	struct strbuf refname;
 
+	assert(direntry->flag & REF_DIR);
+
 	if (*refs->name)
 		path = git_path_submodule(refs->name, "%s", dirname);
 	else
@@ -812,7 +814,8 @@ static void get_ref_dir(struct ref_cache *refs, const char *dirname,
 		} else if (S_ISDIR(st.st_mode)) {
 			strbuf_addch(&refname, '/');
 			get_ref_dir(refs, refname.buf,
-				    &search_for_subdir(dir, refname.buf, 1)->u.subdir);
+				    search_for_subdir(&direntry->u.subdir,
+						      refname.buf, 1));
 		} else {
 			if (*refs->name) {
 				hashclr(sha1);
@@ -825,7 +828,7 @@ static void get_ref_dir(struct ref_cache *refs, const char *dirname,
 				hashclr(sha1);
 				flag |= REF_ISBROKEN;
 			}
-			add_entry_to_dir(dir,
+			add_entry_to_dir(&direntry->u.subdir,
 					 create_ref_entry(refname.buf, sha1, flag, 1));
 		}
 		strbuf_setlen(&refname, dirnamelen);
@@ -839,8 +842,8 @@ static struct ref_entry *get_loose_refs(struct ref_cache *refs)
 	if (!refs->loose) {
 		refs->loose = create_dir_entry("");
 		get_ref_dir(refs, "refs/",
-			    &search_for_subdir(&refs->loose->u.subdir,
-					       "refs/", 1)->u.subdir);
+			    search_for_subdir(&refs->loose->u.subdir,
+					      "refs/", 1));
 	}
 	return refs->loose;
 }
-- 
1.7.10

[PATCH 19/30] get_ref_dir(): remove dirname argument

[mhagger]

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

The dirname can be determined from the direntry argument.

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

diff --git a/refs.c b/refs.c
index 2057380..bc4a69b 100644
--- a/refs.c
+++ b/refs.c
@@ -768,16 +768,14 @@ void add_packed_ref(const char *refname, const unsigned char *sha1)
 }
 
 /*
- * Read the loose references for refs from the namespace dirname.
- * dirname must end with '/'.  direntry must be the directory entry
- * corresponding to dirname.
+ * Read the loose references for direntry in refs.
  */
-static void get_ref_dir(struct ref_cache *refs, const char *dirname,
-			struct ref_entry *direntry)
+static void get_ref_dir(struct ref_cache *refs, struct ref_entry *direntry)
 {
 	DIR *d;
 	const char *path;
 	struct dirent *de;
+	const char *dirname = direntry->name;
 	int dirnamelen = strlen(dirname);
 	struct strbuf refname;
 
@@ -813,7 +811,7 @@ static void get_ref_dir(struct ref_cache *refs, const char *dirname,
 			/* Silently ignore. */
 		} else if (S_ISDIR(st.st_mode)) {
 			strbuf_addch(&refname, '/');
-			get_ref_dir(refs, refname.buf,
+			get_ref_dir(refs,
 				    search_for_subdir(&direntry->u.subdir,
 						      refname.buf, 1));
 		} else {
@@ -841,7 +839,7 @@ static struct ref_entry *get_loose_refs(struct ref_cache *refs)
 {
 	if (!refs->loose) {
 		refs->loose = create_dir_entry("");
-		get_ref_dir(refs, "refs/",
+		get_ref_dir(refs,
 			    search_for_subdir(&refs->loose->u.subdir,
 					      "refs/", 1));
 	}
-- 
1.7.10

[PATCH 20/30] search_for_subdir(): take (ref_entry *) instead of (ref_dir *)

[mhagger]

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


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

diff --git a/refs.c b/refs.c
index bc4a69b..4bea486 100644
--- a/refs.c
+++ b/refs.c
@@ -277,21 +277,22 @@ static struct ref_entry *search_ref_dir(struct ref_dir *dir, const char *refname
 }
 
 /*
- * Search for a directory entry directly within dir (without
- * recursing).  Sort dir if necessary.  subdirname must be a directory
- * name (i.e., end in '/').  If mkdir is set, then create the
- * directory if it is missing; otherwise, return NULL if the desired
- * directory cannot be found.
+ * Search for a directory entry directly within direntry (without
+ * recursing).  Sort direntry if necessary.  subdirname must be a
+ * directory name (i.e., end in '/').  If mkdir is set, then create
+ * the directory if it is missing; otherwise, return NULL if the
+ * desired directory cannot be found.
  */
-static struct ref_entry *search_for_subdir(struct ref_dir *dir,
+static struct ref_entry *search_for_subdir(struct ref_entry *direntry,
 					   const char *subdirname, int mkdir)
 {
-	struct ref_entry *entry = search_ref_dir(dir, subdirname);
+	struct ref_entry *entry = search_ref_dir(&direntry->u.subdir,
+						 subdirname);
 	if (!entry) {
 		if (!mkdir)
 			return NULL;
 		entry = create_dir_entry(subdirname);
-		add_entry_to_dir(dir, entry);
+		add_entry_to_dir(&direntry->u.subdir, entry);
 	}
 	assert(entry->flag & REF_DIR);
 	return entry;
@@ -314,7 +315,7 @@ static struct ref_entry *find_containing_direntry(struct ref_entry *direntry,
 	for (slash = strchr(refname_copy, '/'); slash; slash = strchr(slash + 1, '/')) {
 		char tmp = slash[1];
 		slash[1] = '\0';
-		direntry = search_for_subdir(&direntry->u.subdir, refname_copy, mkdir);
+		direntry = search_for_subdir(direntry, refname_copy, mkdir);
 		slash[1] = tmp;
 		if (!direntry)
 			break;
@@ -812,7 +813,7 @@ static void get_ref_dir(struct ref_cache *refs, struct ref_entry *direntry)
 		} else if (S_ISDIR(st.st_mode)) {
 			strbuf_addch(&refname, '/');
 			get_ref_dir(refs,
-				    search_for_subdir(&direntry->u.subdir,
+				    search_for_subdir(direntry,
 						      refname.buf, 1));
 		} else {
 			if (*refs->name) {
@@ -840,8 +841,7 @@ static struct ref_entry *get_loose_refs(struct ref_cache *refs)
 	if (!refs->loose) {
 		refs->loose = create_dir_entry("");
 		get_ref_dir(refs,
-			    search_for_subdir(&refs->loose->u.subdir,
-					      "refs/", 1));
+			    search_for_subdir(refs->loose, "refs/", 1));
 	}
 	return refs->loose;
 }
-- 
1.7.10

[PATCH 21/30] search_ref_dir(): take (ref_entry *) instead of (ref_dir *)

[mhagger]

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


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

diff --git a/refs.c b/refs.c
index 4bea486..07856fb 100644
--- a/refs.c
+++ b/refs.c
@@ -248,15 +248,19 @@ static int ref_entry_cmp(const void *a, const void *b)
 static void sort_ref_dir(struct ref_dir *dir);
 
 /*
- * Return the entry with the given refname from the ref_dir
- * (non-recursively), sorting dir if necessary.  Return NULL if no
- * such entry is found.
+ * Return the entry with the given refname from direntry
+ * (non-recursively), sorting direntry if necessary.  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;
 
@@ -286,8 +290,7 @@ static struct ref_entry *search_ref_dir(struct ref_dir *dir, const char *refname
 static struct ref_entry *search_for_subdir(struct ref_entry *direntry,
 					   const char *subdirname, int mkdir)
 {
-	struct ref_entry *entry = search_ref_dir(&direntry->u.subdir,
-						 subdirname);
+	struct ref_entry *entry = search_ref_dir(direntry, subdirname);
 	if (!entry) {
 		if (!mkdir)
 			return NULL;
@@ -338,7 +341,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;
 }
 
-- 
1.7.10

[PATCH 22/30] add_entry(): take (ref_entry *) instead of (ref_dir *)

[mhagger]

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

And rename function add_entry_to_dir() -> add_entry().

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

diff --git a/refs.c b/refs.c
index 07856fb..a794d3a 100644
--- a/refs.c
+++ b/refs.c
@@ -200,12 +200,14 @@ static void free_ref_entry(struct ref_entry *entry)
 }
 
 /*
- * Add a ref_entry to the end of dir (unsorted).  Entry is always
- * stored directly in dir; no recursion into subdirectories is
- * done.
+ * Add entry to the end of direntry, unsorted.  entry is always stored
+ * directly in direntry; 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;
 }
@@ -295,7 +297,7 @@ static struct ref_entry *search_for_subdir(struct ref_entry *direntry,
 		if (!mkdir)
 			return NULL;
 		entry = create_dir_entry(subdirname);
-		add_entry_to_dir(&direntry->u.subdir, entry);
+		add_entry(direntry, entry);
 	}
 	assert(entry->flag & REF_DIR);
 	return entry;
@@ -356,7 +358,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;
 }
 
@@ -830,8 +832,8 @@ static void get_ref_dir(struct ref_cache *refs, struct ref_entry *direntry)
 				hashclr(sha1);
 				flag |= REF_ISBROKEN;
 			}
-			add_entry_to_dir(&direntry->u.subdir,
-					 create_ref_entry(refname.buf, sha1, flag, 1));
+			add_entry(direntry,
+				  create_ref_entry(refname.buf, sha1, flag, 1));
 		}
 		strbuf_setlen(&refname, dirnamelen);
 	}
-- 
1.7.10

[PATCH 23/30] do_for_each_ref_in_dirs(): take (ref_entry *) instead of (ref_dir *)

[mhagger]

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


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

diff --git a/refs.c b/refs.c
index a794d3a..4448b14 100644
--- a/refs.c
+++ b/refs.c
@@ -468,35 +468,38 @@ static int do_for_each_ref_in_dir(struct ref_dir *dir, int offset,
 }
 
 /*
- * Call fn for each reference in the union of dir1 and dir2, in order
- * by refname.  Recurse into subdirectories.  If a value entry appears
- * in both dir1 and dir2, then only process the version that is in
- * dir2.  The input dirs must already be sorted, but subdirs will be
- * sorted as needed.
+ * Call fn for each reference in the union of direntry1 and direntry2,
+ * in order by refname.  Recurse into subdirectories.  If a value
+ * entry appears in both direntry1 and direntry2, then only process
+ * the version that is in direntry2.  The input direntries must
+ * already be sorted, but subdirs will be sorted as needed.
  */
-static int do_for_each_ref_in_dirs(struct ref_dir *dir1,
-				   struct ref_dir *dir2,
+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;
 
-	assert(dir1->sorted == dir1->nr);
-	assert(dir2->sorted == dir2->nr);
+	assert(direntry1->flag & REF_DIR);
+	assert(direntry2->flag & REF_DIR);
+	assert(direntry1->u.subdir.sorted == direntry1->u.subdir.nr);
+	assert(direntry2->u.subdir.sorted == direntry2->u.subdir.nr);
+
 	while (1) {
 		struct ref_entry *e1, *e2;
 		int cmp;
-		if (i1 == dir1->nr) {
-			return do_for_each_ref_in_dir(dir2, i2,
+		if (i1 == direntry1->u.subdir.nr) {
+			return do_for_each_ref_in_dir(&direntry2->u.subdir, i2,
 						      base, fn, trim, flags, cb_data);
 		}
-		if (i2 == dir2->nr) {
-			return do_for_each_ref_in_dir(dir1, i1,
+		if (i2 == direntry2->u.subdir.nr) {
+			return do_for_each_ref_in_dir(&direntry1->u.subdir, i1,
 						      base, fn, trim, flags, cb_data);
 		}
-		e1 = dir1->entries[i1];
-		e2 = dir2->entries[i2];
+		e1 = direntry1->u.subdir.entries[i1];
+		e2 = direntry2->u.subdir.entries[i2];
 		cmp = strcmp(e1->name, e2->name);
 		if (cmp == 0) {
 			if ((e1->flag & REF_DIR) && (e2->flag & REF_DIR)) {
@@ -504,12 +507,12 @@ static int do_for_each_ref_in_dirs(struct ref_dir *dir1,
 				sort_ref_dir(&e1->u.subdir);
 				sort_ref_dir(&e2->u.subdir);
 				retval = do_for_each_ref_in_dirs(
-						&e1->u.subdir, &e2->u.subdir,
+						e1, e2,
 						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. */
+				/* Both are references; ignore the one from direntry1. */
 				retval = do_one_ref(base, fn, trim, flags, cb_data, e2);
 				i1++;
 				i2++;
@@ -538,11 +541,11 @@ static int do_for_each_ref_in_dirs(struct ref_dir *dir1,
 		if (retval)
 			return retval;
 	}
-	if (i1 < dir1->nr)
-		return do_for_each_ref_in_dir(dir1, i1,
+	if (i1 < direntry1->u.subdir.nr)
+		return do_for_each_ref_in_dir(&direntry1->u.subdir, i1,
 					      base, fn, trim, flags, cb_data);
-	if (i2 < dir2->nr)
-		return do_for_each_ref_in_dir(dir2, i2,
+	if (i2 < direntry2->u.subdir.nr)
+		return do_for_each_ref_in_dir(&direntry2->u.subdir, i2,
 					      base, fn, trim, flags, cb_data);
 	return 0;
 }
@@ -1186,8 +1189,7 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn
 		sort_ref_dir(&packed_direntry->u.subdir);
 		sort_ref_dir(&loose_direntry->u.subdir);
 		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) {
 		sort_ref_dir(&packed_direntry->u.subdir);
-- 
1.7.10

[PATCH 24/30] do_for_each_ref_in_dir(): take (ref_entry *) instead of (ref_dir *)

[mhagger]

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


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

diff --git a/refs.c b/refs.c
index 4448b14..722545f 100644
--- a/refs.c
+++ b/refs.c
@@ -440,23 +440,24 @@ static int do_one_ref(const char *base, each_ref_fn fn, int trim,
 }
 
 /*
- * Call fn for each reference in dir that has index in the range
+ * Call fn for each reference in direntry that has index in the range
  * offset <= index < dir->nr.  Recurse into subdirectories that are in
  * that index range, sorting them before iterating.  This function
- * does not sort dir itself; it should be sorted beforehand.
+ * does not sort direntry itself; it should be sorted beforehand.
  */
-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;
-	assert(dir->sorted == dir->nr);
-	for (i = offset; i < dir->nr; i++) {
-		struct ref_entry *entry = dir->entries[i];
+	assert(direntry->flag & REF_DIR);
+	assert(direntry->u.subdir.sorted == direntry->u.subdir.nr);
+	for (i = offset; i < direntry->u.subdir.nr; i++) {
+		struct ref_entry *entry = direntry->u.subdir.entries[i];
 		int retval;
 		if (entry->flag & REF_DIR) {
 			sort_ref_dir(&entry->u.subdir);
-			retval = do_for_each_ref_in_dir(&entry->u.subdir, 0,
+			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);
@@ -491,11 +492,11 @@ static int do_for_each_ref_in_dirs(struct ref_entry *direntry1,
 		struct ref_entry *e1, *e2;
 		int cmp;
 		if (i1 == direntry1->u.subdir.nr) {
-			return do_for_each_ref_in_dir(&direntry2->u.subdir, i2,
+			return do_for_each_ref_in_dir(direntry2, i2,
 						      base, fn, trim, flags, cb_data);
 		}
 		if (i2 == direntry2->u.subdir.nr) {
-			return do_for_each_ref_in_dir(&direntry1->u.subdir, i1,
+			return do_for_each_ref_in_dir(direntry1, i1,
 						      base, fn, trim, flags, cb_data);
 		}
 		e1 = direntry1->u.subdir.entries[i1];
@@ -532,7 +533,7 @@ static int do_for_each_ref_in_dirs(struct ref_entry *direntry1,
 			if (e->flag & REF_DIR) {
 				sort_ref_dir(&e->u.subdir);
 				retval = do_for_each_ref_in_dir(
-						&e->u.subdir, 0,
+						e, 0,
 						base, fn, trim, flags, cb_data);
 			} else {
 				retval = do_one_ref(base, fn, trim, flags, cb_data, e);
@@ -542,10 +543,10 @@ static int do_for_each_ref_in_dirs(struct ref_entry *direntry1,
 			return retval;
 	}
 	if (i1 < direntry1->u.subdir.nr)
-		return do_for_each_ref_in_dir(&direntry1->u.subdir, i1,
+		return do_for_each_ref_in_dir(direntry1, i1,
 					      base, fn, trim, flags, cb_data);
 	if (i2 < direntry2->u.subdir.nr)
-		return do_for_each_ref_in_dir(&direntry2->u.subdir, i2,
+		return do_for_each_ref_in_dir(direntry2, i2,
 					      base, fn, trim, flags, cb_data);
 	return 0;
 }
@@ -602,7 +603,7 @@ static int is_refname_available(const char *refname, const char *oldrefname,
 	assert(direntry->flag & REF_DIR);
 	sort_ref_dir(&direntry->u.subdir);
 
-	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'",
@@ -1194,12 +1195,12 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn
 	} else if (packed_direntry) {
 		sort_ref_dir(&packed_direntry->u.subdir);
 		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) {
 		sort_ref_dir(&loose_direntry->u.subdir);
 		retval = do_for_each_ref_in_dir(
-				&loose_direntry->u.subdir, 0,
+				loose_direntry, 0,
 				base, fn, trim, flags, cb_data);
 	}
 
@@ -1648,7 +1649,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,
+	do_for_each_ref_in_dir(packed, 0,
 			       "", repack_without_ref_fn, 0, 0, &data);
 	return commit_lock_file(&packlock);
 }
-- 
1.7.10

[PATCH 25/30] sort_ref_dir(): take (ref_entry *) instead of (ref_dir *)

[mhagger]

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


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

diff --git a/refs.c b/refs.c
index 722545f..90bdd7c 100644
--- a/refs.c
+++ b/refs.c
@@ -247,7 +247,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 direntry
@@ -266,7 +266,7 @@ static struct ref_entry *search_ref_dir(struct ref_entry *direntry,
 	if (refname == NULL || !dir->nr)
 		return NULL;
 
-	sort_ref_dir(dir);
+	sort_ref_dir(direntry);
 
 	len = strlen(refname) + 1;
 	e = xmalloc(sizeof(struct ref_entry) + len);
@@ -386,14 +386,17 @@ static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2
 }
 
 /*
- * Sort the entries in dir non-recursively (if they are not already
- * sorted) and remove any duplicate entries.
+ * Sort the entries in direntry non-recursively (if they are not
+ * already sorted) and remove any duplicate entries.
  */
-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;
 	/*
 	 * This check also prevents passing a zero-length array to qsort(),
 	 * which is a problem on some platforms.
@@ -456,7 +459,7 @@ static int do_for_each_ref_in_dir(struct ref_entry *direntry, int offset,
 		struct ref_entry *entry = direntry->u.subdir.entries[i];
 		int retval;
 		if (entry->flag & REF_DIR) {
-			sort_ref_dir(&entry->u.subdir);
+			sort_ref_dir(entry);
 			retval = do_for_each_ref_in_dir(entry, 0,
 							base, fn, trim, flags, cb_data);
 		} else {
@@ -505,8 +508,8 @@ static int do_for_each_ref_in_dirs(struct ref_entry *direntry1,
 		if (cmp == 0) {
 			if ((e1->flag & REF_DIR) && (e2->flag & REF_DIR)) {
 				/* Both are directories; descend them in parallel. */
-				sort_ref_dir(&e1->u.subdir);
-				sort_ref_dir(&e2->u.subdir);
+				sort_ref_dir(e1);
+				sort_ref_dir(e2);
 				retval = do_for_each_ref_in_dirs(
 						e1, e2,
 						base, fn, trim, flags, cb_data);
@@ -531,7 +534,7 @@ static int do_for_each_ref_in_dirs(struct ref_entry *direntry1,
 				i2++;
 			}
 			if (e->flag & REF_DIR) {
-				sort_ref_dir(&e->u.subdir);
+				sort_ref_dir(e);
 				retval = do_for_each_ref_in_dir(
 						e, 0,
 						base, fn, trim, flags, cb_data);
@@ -601,7 +604,7 @@ static int is_refname_available(const char *refname, const char *oldrefname,
 	data.conflicting_refname = NULL;
 
 	assert(direntry->flag & REF_DIR);
-	sort_ref_dir(&direntry->u.subdir);
+	sort_ref_dir(direntry);
 
 	if (do_for_each_ref_in_dir(direntry, 0, "", name_conflict_fn,
 				   0, DO_FOR_EACH_INCLUDE_BROKEN,
@@ -1187,18 +1190,18 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn
 	}
 
 	if (packed_direntry && loose_direntry) {
-		sort_ref_dir(&packed_direntry->u.subdir);
-		sort_ref_dir(&loose_direntry->u.subdir);
+		sort_ref_dir(packed_direntry);
+		sort_ref_dir(loose_direntry);
 		retval = do_for_each_ref_in_dirs(
 				packed_direntry, loose_direntry,
 				base, fn, trim, flags, cb_data);
 	} else if (packed_direntry) {
-		sort_ref_dir(&packed_direntry->u.subdir);
+		sort_ref_dir(packed_direntry);
 		retval = do_for_each_ref_in_dir(
 				packed_direntry, 0,
 				base, fn, trim, flags, cb_data);
 	} else if (loose_direntry) {
-		sort_ref_dir(&loose_direntry->u.subdir);
+		sort_ref_dir(loose_direntry);
 		retval = do_for_each_ref_in_dir(
 				loose_direntry, 0,
 				base, fn, trim, flags, cb_data);
-- 
1.7.10

[PATCH 26/30] struct ref_dir: store a reference to the enclosing ref_cache

[mhagger]

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

This means that it contains enough information to serve as the sole
argument to get_ref_dir(), which will be changed in a moment.

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

diff --git a/refs.c b/refs.c
index 90bdd7c..11ebc02 100644
--- a/refs.c
+++ b/refs.c
@@ -106,6 +106,8 @@ struct ref_value {
 	unsigned char peeled[20];
 };
 
+struct ref_cache;
+
 struct ref_dir {
 	int nr, alloc;
 
@@ -118,6 +120,9 @@ struct ref_dir {
 	int sorted;
 
 	struct ref_entry **entries;
+
+	/* A pointer to the ref_cache that contains this ref_dir. */
+	struct ref_cache *ref_cache;
 };
 
 /* ISSYMREF=0x01, ISPACKED=0x02, and ISBROKEN=0x04 are public interfaces */
@@ -230,13 +235,15 @@ 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;
 	int len = strlen(dirname);
 	direntry = xcalloc(1, sizeof(struct ref_entry) + len + 1);
 	memcpy(direntry->name, dirname, len + 1);
 	direntry->flag = REF_DIR;
+	direntry->u.subdir.ref_cache = ref_cache;
 	return direntry;
 }
 
@@ -296,7 +303,8 @@ static struct ref_entry *search_for_subdir(struct ref_entry *direntry,
 	if (!entry) {
 		if (!mkdir)
 			return NULL;
-		entry = create_dir_entry(subdirname);
+		entry = create_dir_entry(direntry->u.subdir.ref_cache,
+					 subdirname);
 		add_entry(direntry, entry);
 	}
 	assert(entry->flag & REF_DIR);
@@ -760,7 +768,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
@@ -851,7 +859,7 @@ static void get_ref_dir(struct ref_cache *refs, struct ref_entry *direntry)
 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,
 			    search_for_subdir(refs->loose, "refs/", 1));
 	}
-- 
1.7.10

[PATCH 27/30] read_loose_refs(): rename function from get_ref_dir()

[mhagger]

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


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

diff --git a/refs.c b/refs.c
index 11ebc02..0f5aab2 100644
--- a/refs.c
+++ b/refs.c
@@ -791,7 +791,7 @@ void add_packed_ref(const char *refname, const unsigned char *sha1)
 /*
  * Read the loose references for direntry in refs.
  */
-static void get_ref_dir(struct ref_cache *refs, struct ref_entry *direntry)
+static void read_loose_refs(struct ref_cache *refs, struct ref_entry *direntry)
 {
 	DIR *d;
 	const char *path;
@@ -832,9 +832,9 @@ static void get_ref_dir(struct ref_cache *refs, struct ref_entry *direntry)
 			/* Silently ignore. */
 		} else if (S_ISDIR(st.st_mode)) {
 			strbuf_addch(&refname, '/');
-			get_ref_dir(refs,
-				    search_for_subdir(direntry,
-						      refname.buf, 1));
+			read_loose_refs(refs,
+					search_for_subdir(direntry,
+							  refname.buf, 1));
 		} else {
 			if (*refs->name) {
 				hashclr(sha1);
@@ -860,8 +860,8 @@ static struct ref_entry *get_loose_refs(struct ref_cache *refs)
 {
 	if (!refs->loose) {
 		refs->loose = create_dir_entry(refs, "");
-		get_ref_dir(refs,
-			    search_for_subdir(refs->loose, "refs/", 1));
+		read_loose_refs(refs,
+				search_for_subdir(refs->loose, "refs/", 1));
 	}
 	return refs->loose;
 }
-- 
1.7.10

[PATCH 28/30] read_loose_refs(): access ref_cache via the ref_dir field

[mhagger]

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

This means that all we need to read loose references is the ref_entry
that will receive them.

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

diff --git a/refs.c b/refs.c
index 0f5aab2..4eca965 100644
--- a/refs.c
+++ b/refs.c
@@ -791,7 +791,7 @@ void add_packed_ref(const char *refname, const unsigned char *sha1)
 /*
  * Read the loose references for direntry in refs.
  */
-static void read_loose_refs(struct ref_cache *refs, struct ref_entry *direntry)
+static void read_loose_refs(struct ref_entry *direntry)
 {
 	DIR *d;
 	const char *path;
@@ -799,9 +799,11 @@ static void read_loose_refs(struct ref_cache *refs, struct ref_entry *direntry)
 	const char *dirname = direntry->name;
 	int dirnamelen = strlen(dirname);
 	struct strbuf refname;
+	struct ref_cache *refs;
 
 	assert(direntry->flag & REF_DIR);
 
+	refs = direntry->u.subdir.ref_cache;
 	if (*refs->name)
 		path = git_path_submodule(refs->name, "%s", dirname);
 	else
@@ -832,8 +834,7 @@ static void read_loose_refs(struct ref_cache *refs, struct ref_entry *direntry)
 			/* Silently ignore. */
 		} else if (S_ISDIR(st.st_mode)) {
 			strbuf_addch(&refname, '/');
-			read_loose_refs(refs,
-					search_for_subdir(direntry,
+			read_loose_refs(search_for_subdir(direntry,
 							  refname.buf, 1));
 		} else {
 			if (*refs->name) {
@@ -860,8 +861,7 @@ static struct ref_entry *get_loose_refs(struct ref_cache *refs)
 {
 	if (!refs->loose) {
 		refs->loose = create_dir_entry(refs, "");
-		read_loose_refs(refs,
-				search_for_subdir(refs->loose, "refs/", 1));
+		read_loose_refs(search_for_subdir(refs->loose, "refs/", 1));
 	}
 	return refs->loose;
 }
-- 
1.7.10

[PATCH 29/30] create_dir_entry(): allow the flag value to be passed as an argument

[mhagger]

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

In a moment we will support multiple flag values for directory entries.

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

diff --git a/refs.c b/refs.c
index 4eca965..869c9a7 100644
--- a/refs.c
+++ b/refs.c
@@ -231,18 +231,18 @@ static void clear_ref_dir(struct ref_dir *dir)
 }
 
 /*
- * Create a struct ref_entry object for the specified dirname.
+ * Create a struct ref_entry object for the specified dirname and flag.
  * 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;
 	int len = strlen(dirname);
 	direntry = xcalloc(1, sizeof(struct ref_entry) + len + 1);
 	memcpy(direntry->name, dirname, len + 1);
-	direntry->flag = REF_DIR;
+	direntry->flag = flag;
 	direntry->u.subdir.ref_cache = ref_cache;
 	return direntry;
 }
@@ -304,7 +304,7 @@ static struct ref_entry *search_for_subdir(struct ref_entry *direntry,
 		if (!mkdir)
 			return NULL;
 		entry = create_dir_entry(direntry->u.subdir.ref_cache,
-					 subdirname);
+					 subdirname, REF_DIR);
 		add_entry(direntry, entry);
 	}
 	assert(entry->flag & REF_DIR);
@@ -768,7 +768,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);
 		if (*refs->name)
 			packed_refs_file = git_path_submodule(refs->name, "packed-refs");
 		else
@@ -860,7 +860,7 @@ static void read_loose_refs(struct ref_entry *direntry)
 static struct ref_entry *get_loose_refs(struct ref_cache *refs)
 {
 	if (!refs->loose) {
-		refs->loose = create_dir_entry(refs, "");
+		refs->loose = create_dir_entry(refs, "", REF_DIR);
 		read_loose_refs(search_for_subdir(refs->loose, "refs/", 1));
 	}
 	return refs->loose;
-- 
1.7.10

Re: [PATCH 29/30] create_dir_entry(): allow the flag value to be passed as an argument

[Junio C Hamano]

mhagger@alum.mit.edu writes:

> diff --git a/refs.c b/refs.c
> index 4eca965..869c9a7 100644
> --- a/refs.c
> +++ b/refs.c
> @@ -231,18 +231,18 @@ static void clear_ref_dir(struct ref_dir *dir)
>  }
>  
>  /*
> + * Create a struct ref_entry object for the specified dirname and flag.
>   * 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;
>  	int len = strlen(dirname);
>  	direntry = xcalloc(1, sizeof(struct ref_entry) + len + 1);
>  	memcpy(direntry->name, dirname, len + 1);
> -	direntry->flag = REF_DIR;
> +	direntry->flag = flag;
>  	direntry->u.subdir.ref_cache = ref_cache;

As the returned structure will always represent a subdirectory and not a
leaf node, i.e. you use u.subdir, I do not think it makes any sense to
make it responsibility for the caller of this function to include
REF_DIR in the value of the flag.

Also shouldn't flag be of type "unsigned", not "int"?

Re: [PATCH 29/30] create_dir_entry(): allow the flag value to be passed as an argument

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> mhagger@alum.mit.edu writes:
>
>> diff --git a/refs.c b/refs.c
>> index 4eca965..869c9a7 100644
>> --- a/refs.c
>> +++ b/refs.c
>> @@ -231,18 +231,18 @@ static void clear_ref_dir(struct ref_dir *dir)
>>  }
>>  
>>  /*
>> + * Create a struct ref_entry object for the specified dirname and flag.
>>   * 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;
>>  	int len = strlen(dirname);
>>  	direntry = xcalloc(1, sizeof(struct ref_entry) + len + 1);
>>  	memcpy(direntry->name, dirname, len + 1);
>> -	direntry->flag = REF_DIR;
>> +	direntry->flag = flag;
>>  	direntry->u.subdir.ref_cache = ref_cache;
>
> As the returned structure will always represent a subdirectory and not a
> leaf node, i.e. you use u.subdir, I do not think it makes any sense to
> make it responsibility for the caller of this function to include
> REF_DIR in the value of the flag.

Forseeing a response "But but but REF_DIR will become OR of two
variants", my complaint is still valid ;-) and it is the bit assignment
you did in the final patch that is wrong.  If you make REF_DIR (or not)
to differenticate between ref_dir vs ref_value, and use another bit
REF_INCOMPLETE to remember that you still need to find out the actual
value of it, the the above can still be

	create_dir_entry(struct ref_cache *ref_cache, const char *dirname, int lazy)
	{
		...
		direntry->flag = REF_DIR | (lazy ? REF_INCOMPLETE : 0);
                ...
	}

I am OK with the following as well:

	create_dir_entry(struct ref_cache *ref_cache,
        		const char *dirname, unsigned extra)
	{
		...
		direntry->flag = REF_DIR | extra;
	}

The suggested bit assignment would also allow you to create ref_value
leaf nodes, whose presence you know about (by iterating over readdir()
results) but not their values yet (because you haven't opened and read
them), by marking them with REF_INCOMPLETE to be extra lazy in the
future, if necessary.  I do not know if that much laziness buys us a
lot, though ;-).

Re: [PATCH 29/30] create_dir_entry(): allow the flag value to be passed as an argument

[Michael Haggerty]

On 04/25/2012 08:52 PM, Junio C Hamano wrote:
> Junio C Hamano<gitster@pobox.com>  writes:
>
>> mhagger@alum.mit.edu writes:
>>
>>> diff --git a/refs.c b/refs.c
>>> index 4eca965..869c9a7 100644
>>> --- a/refs.c
>>> +++ b/refs.c
>>> @@ -231,18 +231,18 @@ static void clear_ref_dir(struct ref_dir *dir)
>>>   }
>>>
>>>   /*
>>> + * Create a struct ref_entry object for the specified dirname and flag.
>>>    * 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;
>>>   	int len = strlen(dirname);
>>>   	direntry = xcalloc(1, sizeof(struct ref_entry) + len + 1);
>>>   	memcpy(direntry->name, dirname, len + 1);
>>> -	direntry->flag = REF_DIR;
>>> +	direntry->flag = flag;
>>>   	direntry->u.subdir.ref_cache = ref_cache;
>>
>> As the returned structure will always represent a subdirectory and not a
>> leaf node, i.e. you use u.subdir, I do not think it makes any sense to
>> make it responsibility for the caller of this function to include
>> REF_DIR in the value of the flag.
>
> Forseeing a response "But but but REF_DIR will become OR of two
> variants", my complaint is still valid ;-) and it is the bit assignment
> you did in the final patch that is wrong.  If you make REF_DIR (or not)
> to differenticate between ref_dir vs ref_value, and use another bit
> REF_INCOMPLETE to remember that you still need to find out the actual
> value of it, the the above can still be

In an earlier design, there were three types of REF_DIR: packed, 
loose(read), and loose(unread), which could all be packed (along with 
dir/non-dir) into two bits.  The current bit assignment was left over 
from that design, plus a latent expectation that it would sometime be 
necessary to distinguish between packed and loose(read) references.

But so far I haven't found a reason to distinguish between packed and 
loose(read), so your suggested bit assignment is simpler.  I will 
include it in the next version of the patch series.

> The suggested bit assignment would also allow you to create ref_value
> leaf nodes, whose presence you know about (by iterating over readdir()
> results) but not their values yet (because you haven't opened and read
> them), by marking them with REF_INCOMPLETE to be extra lazy in the
> future, if necessary.  I do not know if that much laziness buys us a
> lot, though ;-).

This would be pretty easy to implement.  Maybe I'll try it someday.

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/

[PATCH 30/30] refs: read loose references lazily

[mhagger]

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

Instead of reading the whole directory of loose references the first
time any are needed, only read them on demand, one directory at a
time.

Use a new ref_entry flag value REF_DIR_INCOMPLETE to indicate that the
entry represents a REF_DIR that hasn't been read yet.  Whenever any
entries from such a directory are needed, read all of the loose
references from that directory.

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

diff --git a/refs.c b/refs.c
index 869c9a7..d72208a 100644
--- a/refs.c
+++ b/refs.c
@@ -101,6 +101,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];
@@ -108,6 +114,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 (because these functions
+ * call sort_ref_dir() for each subdirectory).
+ */
 struct ref_dir {
 	int nr, alloc;
 
@@ -127,19 +161,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
@@ -207,11 +255,13 @@ static void free_ref_entry(struct ref_entry *entry)
 /*
  * Add entry to the end of direntry, unsorted.  entry is always stored
  * directly in direntry; no recursion into subdirectories is done.
+ * direntry must already be REF_DIR_COMPLETE.
  */
 static void add_entry(struct ref_entry *direntry, struct ref_entry *entry)
 {
 	struct ref_dir *dir;
 	assert(direntry->flag & REF_DIR);
+	assert((direntry->flag & REF_DIR) == REF_DIR_COMPLETE);
 	dir = &direntry->u.subdir;
 	ALLOC_GROW(dir->entries, dir->nr + 1, dir->alloc);
 	dir->entries[dir->nr++] = entry;
@@ -256,10 +306,12 @@ static int ref_entry_cmp(const void *a, const void *b)
 
 static void sort_ref_dir(struct ref_entry *direntry);
 
+static void read_loose_refs(struct ref_entry *direntry);
+
 /*
  * Return the entry with the given refname from direntry
- * (non-recursively), sorting direntry if necessary.  Return NULL if
- * no such entry is found.
+ * (non-recursively), reading direntry if it is REF_DIR_INCOMPLETE and
+ * sorting it if necessary.  Return NULL if no such entry is found.
  */
 static struct ref_entry *search_ref_dir(struct ref_entry *direntry,
 					const char *refname)
@@ -269,6 +321,7 @@ static struct ref_entry *search_ref_dir(struct ref_entry *direntry,
 	struct ref_dir *dir;
 
 	assert(direntry->flag & REF_DIR);
+	read_loose_refs(direntry);
 	dir = &direntry->u.subdir;
 	if (refname == NULL || !dir->nr)
 		return NULL;
@@ -303,8 +356,14 @@ static struct ref_entry *search_for_subdir(struct ref_entry *direntry,
 	if (!entry) {
 		if (!mkdir)
 			return NULL;
+		/*
+		 * 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,
-					 subdirname, REF_DIR);
+					 subdirname, REF_DIR_COMPLETE);
 		add_entry(direntry, entry);
 	}
 	assert(entry->flag & REF_DIR);
@@ -395,7 +454,8 @@ static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2
 
 /*
  * Sort the entries in direntry non-recursively (if they are not
- * already sorted) and remove any duplicate entries.
+ * already sorted) and remove any duplicate entries.  If direntry is
+ * REF_DIR_INCOMPLETE, read it from disk first.
  */
 static void sort_ref_dir(struct ref_entry *direntry)
 {
@@ -404,6 +464,7 @@ static void sort_ref_dir(struct ref_entry *direntry)
 	struct ref_dir *dir;
 
 	assert(direntry->flag & REF_DIR);
+	read_loose_refs(direntry);
 	dir = &direntry->u.subdir;
 	/*
 	 * This check also prevents passing a zero-length array to qsort(),
@@ -768,7 +829,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, "", REF_DIR);
+		refs->packed = create_dir_entry(refs, "", REF_DIR_COMPLETE);
 		if (*refs->name)
 			packed_refs_file = git_path_submodule(refs->name, "packed-refs");
 		else
@@ -797,12 +858,15 @@ static void read_loose_refs(struct ref_entry *direntry)
 	const char *path;
 	struct dirent *de;
 	const char *dirname = direntry->name;
-	int dirnamelen = strlen(dirname);
+	int dirnamelen;
 	struct strbuf refname;
 	struct ref_cache *refs;
 
 	assert(direntry->flag & REF_DIR);
-
+	if ((direntry->flag & REF_DIR) != REF_DIR_INCOMPLETE)
+		return;
+	direntry->flag = REF_DIR_COMPLETE;
+	dirnamelen = strlen(dirname);
 	refs = direntry->u.subdir.ref_cache;
 	if (*refs->name)
 		path = git_path_submodule(refs->name, "%s", dirname);
@@ -834,8 +898,9 @@ static void read_loose_refs(struct ref_entry *direntry)
 			/* Silently ignore. */
 		} else if (S_ISDIR(st.st_mode)) {
 			strbuf_addch(&refname, '/');
-			read_loose_refs(search_for_subdir(direntry,
-							  refname.buf, 1));
+			add_entry(direntry,
+				  create_dir_entry(refs, refname.buf,
+						   REF_DIR_INCOMPLETE));
 		} else {
 			if (*refs->name) {
 				hashclr(sha1);
@@ -860,8 +925,8 @@ static void read_loose_refs(struct ref_entry *direntry)
 static struct ref_entry *get_loose_refs(struct ref_cache *refs)
 {
 	if (!refs->loose) {
-		refs->loose = create_dir_entry(refs, "", REF_DIR);
-		read_loose_refs(search_for_subdir(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;
 }
-- 
1.7.10

Re: [PATCH 00/30] Read loose references lazily

[Junio C Hamano]

mhagger@alum.mit.edu writes:

> From: Michael Haggerty <mhagger@alum.mit.edu>
>
> This is the next installment of the ref-api saga.  The main result of
> this patch series is to teach git to read loose references one
> directory at a time, only when they are needed.
>
> The first nine commits are not very interesting; they convert
> get_ref_dir() and do_for_each_reflog() to use strbufs and to tighten
> up their specifications.  The search_for_subdir() function extracted
> in patch 5 will be useful later.  Patch 6 slightly reduces the amount
> of work needed to read loose refs from disk, and also changes the
> function's API in a way that will be needed later when directories are
> read one at a time.
>
> Patches 10 - 25 mostly switch a lot of code from using ref_dir
> pointers to using ref_entry pointers as arguments and return values.
> This is important, because ...

The earlier parts looked sane, but the ref_dir set of patches looked
like merely working around the fact that "struct ref_dir" does not have
the name field and you had to upcast it to ref_entry to access the full
name.

All the places that used to take ref_dir never wanted to get an entry
that represents a leaf node (i.e. ref_value kind of ref_entry), but now
because you made everybody to take ref_entry, the resulting code is much
more error prone and the static type checking done by the compiler helps
us much less when updating the code.  It can already be seen that you
had to sprinkle a lot of assert(flag & REF_DIR), but at runtime in
non-debug build that will become no-op and it is not a substitute for
the static type checking we used to have.

Can't we approach this differently so that we can keep the type safety?

Re: [PATCH 00/30] Read loose references lazily

[Michael Haggerty]

On 04/25/2012 08:39 PM, Junio C Hamano wrote:
> mhagger@alum.mit.edu writes:
>
>> From: Michael Haggerty<mhagger@alum.mit.edu>
>>
>> Patches 10 - 25 mostly switch a lot of code from using ref_dir
>> pointers to using ref_entry pointers as arguments and return values.
>> This is important, because ...
>
> The earlier parts looked sane, but the ref_dir set of patches looked
> like merely working around the fact that "struct ref_dir" does not have
> the name field and you had to upcast it to ref_entry to access the full
> name.

Yes, that plus the fact that the ref_entry::flag field is needed in 
ref_entry (to distinguish between value and directory entries) but also 
to interpret the contents of the ref_value / ref_dir.

> All the places that used to take ref_dir never wanted to get an entry
> that represents a leaf node (i.e. ref_value kind of ref_entry), but now
> because you made everybody to take ref_entry, the resulting code is much
> more error prone and the static type checking done by the compiler helps
> us much less when updating the code.  It can already be seen that you
> had to sprinkle a lot of assert(flag&  REF_DIR), but at runtime in
> non-debug build that will become no-op and it is not a substitute for
> the static type checking we used to have.
>
> Can't we approach this differently so that we can keep the type safety?

Thanks for this comment.  I've obviously been ruined by OO languages, in 
which [name + flag + struct ref_value] and [name + flag + struct 
ref_dir] (which *are* useful combinations of data) would be subclasses, 
and the downcasting from ref_entry would only have to occur in only one 
place, while the compiler could guarantee consistency everywhere else.

In C, I don't see a way to implement the equivalent semantics that is 
less annoying than the code that I submitted.

But since [name + flag + struct ref_value] and [name + flag + struct 
ref_dir] never leave the library as structs, it is indeed possible to 
write the code in a different way that leaves most functions working 
with ref_dir instead of having to use ref_entry everywhere.  I have 
implemented this and will submit it shortly.

Thanks again for your suggestion; the resulting code is indeed simpler.

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/