thodg/got

diff --git a/include/got_error.h b/include/got_error.h
index ed60d55..266c845 100644
--- a/include/got_error.h
+++ b/include/got_error.h
@@ -71,6 +71,8 @@
 #define GOT_ERR_ANCESTRY	55
 #define GOT_ERR_FILEIDX_BAD	56
 #define GOT_ERR_BAD_REF_DATA	57
+#define GOT_ERR_TREE_DUP_ENTRY	58
+#define GOT_ERR_DIR_DUP_ENTRY	59
 
 static const struct got_error {
 	int code;
@@ -132,6 +134,8 @@ static const struct got_error {
 				"the current branch" },
 	{ GOT_ERR_FILEIDX_BAD,	"file index is corrupt" },
 	{ GOT_ERR_BAD_REF_DATA,	"could not parse reference data" },
+	{ GOT_ERR_TREE_DUP_ENTRY,"duplicate entry in tree object" },
+	{ GOT_ERR_DIR_DUP_ENTRY,"duplicate entry in directory" },
 };
 
 /*
diff --git a/lib/fileindex.c b/lib/fileindex.c
index 49b8639..fecdb10 100644
--- a/lib/fileindex.c
+++ b/lib/fileindex.c
@@ -697,26 +697,21 @@ diff_fileindex_dir(struct got_fileindex *, struct got_fileindex_entry **, DIR *,
     const char *, struct got_repository *, struct got_fileindex_diff_dir_cb *,
     void *);
 
-struct dirlist_entry {
-	SIMPLEQ_ENTRY(dirlist_entry) entry;
-	struct dirent *de;
-};
-SIMPLEQ_HEAD(dirlist_head, dirlist_entry);
-
 static const struct got_error *
-walk_dir(struct dirlist_entry **next, struct got_fileindex *fileindex,
-    struct got_fileindex_entry **ie, struct dirlist_entry *dle,
+walk_dir(struct got_pathlist_entry **next, struct got_fileindex *fileindex,
+    struct got_fileindex_entry **ie, struct got_pathlist_entry *dle,
     const char *path, DIR *dir, struct got_repository *repo,
     struct got_fileindex_diff_dir_cb *cb, void *cb_arg)
 {
 	const struct got_error *err = NULL;
+	struct dirent *de = dle->data;
 
-	if (dle->de->d_type == DT_DIR) {
+	if (de->d_type == DT_DIR) {
 		char *subpath;
 		DIR *subdir;
 
 		if (asprintf(&subpath, "%s%s%s", path,
-		    path[0] == '\0' ? "" : "/", dle->de->d_name) == -1)
+		    path[0] == '\0' ? "" : "/", de->d_name) == -1)
 			return got_error_from_errno();
 
 		subdir = opendir(subpath);
@@ -733,45 +728,7 @@ walk_dir(struct dirlist_entry **next, struct got_fileindex *fileindex,
 			return err;
 	}
 
-	*next = SIMPLEQ_NEXT(dle, entry);
-	return NULL;
-}
-
-static const struct got_error *
-insert_dirent(struct dirlist_head *dirlist, struct dirent *de)
-{
-	struct dirlist_entry *dle, *prev = NULL;
-
-	/*
-	 * Keep dirents sorted in same order as used by file index.
-	 * Git orders tree object entries based on length and then memcmp().
-	 */
-	SIMPLEQ_FOREACH(dle, dirlist, entry) {
-		int cmp;
-
-		if (dle->de->d_namlen > de->d_namlen) {
-			prev = dle;
-			continue;
-		}
-
-		cmp = strcmp(dle->de->d_name, de->d_name);
-		if (cmp == 0)
-			return NULL; /* duplicate, should not happen */
-		else if (cmp > 0)
-			break;
-		else
-			prev = dle;
-	}
-
-	dle = malloc(sizeof(*dle));
-	if (dle == NULL)
-		return got_error_from_errno();
-	dle->de = de;
-	if (prev)
-		SIMPLEQ_INSERT_AFTER(dirlist, prev, dle, entry);
-	else
-		SIMPLEQ_INSERT_TAIL(dirlist, dle, entry);
-
+	*next = TAILQ_NEXT(dle, entry);
 	return NULL;
 }
 
@@ -785,12 +742,14 @@ diff_fileindex_dir(struct got_fileindex *fileindex,
 	struct dirent *de = NULL;
 	size_t path_len = strlen(path);
 	struct got_fileindex_entry *next;
-	struct dirlist_head dirlist;
-	struct dirlist_entry *dle;
+	struct got_pathlist_head dirlist;
+	struct got_pathlist_entry *dle;
 
-	SIMPLEQ_INIT(&dirlist);
+	TAILQ_INIT(&dirlist);
 
 	while (1) {
+		struct got_pathlist_entry *new = NULL;
+
 		de = readdir(dir);
 		if (de == NULL)
 			break;
@@ -801,17 +760,23 @@ diff_fileindex_dir(struct got_fileindex *fileindex,
 		    strcmp(de->d_name, GOT_WORKTREE_GOT_DIR) == 0))
 			continue;
 
-		insert_dirent(&dirlist, de);
+		err = got_pathlist_insert(&new, &dirlist, de->d_name, de);
+		if (err)
+			goto done;
+		if (new == NULL) {
+			err = got_error(GOT_ERR_DIR_DUP_ENTRY);
+			goto done;
+		}
 	}
 
-	dle = SIMPLEQ_FIRST(&dirlist);
+	dle = TAILQ_FIRST(&dirlist);
 	while ((*ie && got_path_is_child((*ie)->path, path, path_len)) || dle) {
 		if (dle && *ie) {
+			de = dle->data;
 			int cmp = cmp_entries((*ie)->path, path, path_len,
-			    dle->de->d_name);
+			    de->d_name);
 			if (cmp == 0) {
-				err = cb->diff_old_new(cb_arg, *ie, dle->de,
-				    path);
+				err = cb->diff_old_new(cb_arg, *ie, de, path);
 				if (err)
 					break;
 				*ie = walk_fileindex(fileindex, *ie);
@@ -824,7 +789,7 @@ diff_fileindex_dir(struct got_fileindex *fileindex,
 					break;
 				*ie = next;
 			} else {
-				err = cb->diff_new(cb_arg, dle->de, path);
+				err = cb->diff_new(cb_arg, de, path);
 				if (err)
 					break;
 				err = walk_dir(&dle, fileindex, ie, dle, path,
@@ -839,7 +804,7 @@ diff_fileindex_dir(struct got_fileindex *fileindex,
 				break;
 			*ie = next;
 		} else if (dle) {
-			err = cb->diff_new(cb_arg, dle->de, path);
+			err = cb->diff_new(cb_arg, de, path);
 			if (err)
 				break;
 			err = walk_dir(&dle, fileindex, ie, dle, path, dir,
@@ -848,13 +813,8 @@ diff_fileindex_dir(struct got_fileindex *fileindex,
 				break;
 		}
 	}
-
-	while (!SIMPLEQ_EMPTY(&dirlist)) {
-		dle = SIMPLEQ_FIRST(&dirlist);
-		SIMPLEQ_REMOVE_HEAD(&dirlist, entry);
-		free(dle);
-	}
-
+done:
+	got_pathlist_free(&dirlist);
 	return err;
 }
 
diff --git a/lib/got_lib_fileindex.h b/lib/got_lib_fileindex.h
index 12d5ee2..f0befaf 100644
--- a/lib/got_lib_fileindex.h
+++ b/lib/got_lib_fileindex.h
@@ -78,7 +78,7 @@ static inline int
 got_fileindex_cmp(const struct got_fileindex_entry *e1,
     const struct got_fileindex_entry *e2)
 {
-	return strcmp(e1->path, e2->path);
+	return got_path_cmp(e1->path, e2->path);
 }
 
 RB_PROTOTYPE(got_fileindex_tree, got_fileindex_entry, entry, got_fileindex_cmp);
diff --git a/lib/object_parse.c b/lib/object_parse.c
index 330cbe4..9d4c4bb 100644
--- a/lib/object_parse.c
+++ b/lib/object_parse.c
@@ -48,6 +48,7 @@
 #include "got_lib_pack.h"
 #include "got_lib_privsep.h"
 #include "got_lib_repository.h"
+#include "got_lib_path.h"
 
 #ifndef nitems
 #define nitems(_a) (sizeof(_a) / sizeof((_a)[0]))
@@ -664,6 +665,10 @@ got_object_parse_tree(struct got_tree_object **tree, uint8_t *buf, size_t len)
 {
 	const struct got_error *err;
 	size_t remain = len;
+	struct got_pathlist_head pathlist;
+	struct got_pathlist_entry *pe;
+
+	TAILQ_INIT(&pathlist);
 
 	*tree = calloc(1, sizeof(**tree));
 	if (*tree == NULL)
@@ -673,13 +678,19 @@ got_object_parse_tree(struct got_tree_object **tree, uint8_t *buf, size_t len)
 
 	while (remain > 0) {
 		struct got_tree_entry *te;
+		struct got_pathlist_entry *new = NULL;
 		size_t elen;
 
 		err = parse_tree_entry(&te, &elen, buf, remain);
 		if (err)
-			return err;
-		(*tree)->entries.nentries++;
-		SIMPLEQ_INSERT_TAIL(&(*tree)->entries.head, te, entry);
+			goto done;
+		err = got_pathlist_insert(&new, &pathlist, te->name, te);
+		if (err)
+			goto done;
+		if (new == NULL) {
+			err = got_error(GOT_ERR_TREE_DUP_ENTRY);
+			goto done;
+		}
 		buf += elen;
 		remain -= elen;
 	}
@@ -687,10 +698,18 @@ got_object_parse_tree(struct got_tree_object **tree, uint8_t *buf, size_t len)
 	if (remain != 0) {
 		got_object_tree_close(*tree);
 		*tree = NULL;
-		return got_error(GOT_ERR_BAD_OBJ_DATA);
+		err = got_error(GOT_ERR_BAD_OBJ_DATA);
+		goto done;
 	}
 
-	return NULL;
+	TAILQ_FOREACH(pe, &pathlist, entry) {
+		struct got_tree_entry *te = pe->data;
+		(*tree)->entries.nentries++;
+		SIMPLEQ_INSERT_TAIL(&(*tree)->entries.head, te, entry);
+	}
+done:
+	got_pathlist_free(&pathlist);
+	return err;
 }
 
 void
diff --git a/libexec/got-read-blob/Makefile b/libexec/got-read-blob/Makefile
index 564acd4..ad08409 100644
--- a/libexec/got-read-blob/Makefile
+++ b/libexec/got-read-blob/Makefile
@@ -2,7 +2,7 @@
 
 PROG=		got-read-blob
 SRCS=		got-read-blob.c delta.c error.c inflate.c object_parse.c \
-		privsep.c sha1.c
+		path.c privsep.c sha1.c
 
 CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib
 LDADD = -lutil -lz
diff --git a/libexec/got-read-commit/Makefile b/libexec/got-read-commit/Makefile
index 1470f72..2786410 100644
--- a/libexec/got-read-commit/Makefile
+++ b/libexec/got-read-commit/Makefile
@@ -2,7 +2,7 @@
 
 PROG=		got-read-commit
 SRCS=		got-read-commit.c delta.c error.c inflate.c object_parse.c \
-		privsep.c sha1.c
+		path.c privsep.c sha1.c
 
 CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib
 LDADD = -lutil -lz
diff --git a/libexec/got-read-object/Makefile b/libexec/got-read-object/Makefile
index 9cb00e1..da7839d 100644
--- a/libexec/got-read-object/Makefile
+++ b/libexec/got-read-object/Makefile
@@ -2,7 +2,7 @@
 
 PROG=		got-read-object
 SRCS=		got-read-object.c delta.c error.c inflate.c object_parse.c \
-		privsep.c sha1.c
+		path.c privsep.c sha1.c
 
 CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib
 LDADD = -lutil -lz
diff --git a/libexec/got-read-tag/Makefile b/libexec/got-read-tag/Makefile
index 64fb2ef..3526b16 100644
--- a/libexec/got-read-tag/Makefile
+++ b/libexec/got-read-tag/Makefile
@@ -2,7 +2,7 @@
 
 PROG=		got-read-tag
 SRCS=		got-read-tag.c delta.c error.c inflate.c object_parse.c \
-		privsep.c sha1.c
+		path.c privsep.c sha1.c
 
 CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib
 LDADD = -lutil -lz
diff --git a/libexec/got-read-tree/Makefile b/libexec/got-read-tree/Makefile
index 600541d..2d7e641 100644
--- a/libexec/got-read-tree/Makefile
+++ b/libexec/got-read-tree/Makefile
@@ -2,7 +2,7 @@
 
 PROG=		got-read-tree
 SRCS=		got-read-tree.c delta.c error.c inflate.c object_parse.c \
-		privsep.c sha1.c
+		path.c privsep.c sha1.c
 
 CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib
 LDADD = -lutil -lz
diff --git a/regress/cmdline/update.sh b/regress/cmdline/update.sh
index 1e8b968..32c4c6a 100755
--- a/regress/cmdline/update.sh
+++ b/regress/cmdline/update.sh
@@ -317,8 +317,8 @@ function test_update_dir_with_dot_sibling {
 	echo change > $testroot/repo/epsilon/zeta
 	git_commit $testroot/repo -m "changing epsilon/zeta"
 
-	echo "A  epsilon.txt" > $testroot/stdout.expected
-	echo "U  epsilon/zeta" >> $testroot/stdout.expected
+	echo "U  epsilon/zeta" > $testroot/stdout.expected
+	echo "A  epsilon.txt" >> $testroot/stdout.expected
 	echo -n "Updated to commit " >> $testroot/stdout.expected
 	git_show_head $testroot/repo >> $testroot/stdout.expected
 	echo >> $testroot/stdout.expected
@@ -432,10 +432,10 @@ function test_update_moves_files_to_new_dir {
 	(cd $testroot/repo && git mv epsilon/psi/chi/tau epsilon-new/psi/tau)
 	git_commit $testroot/repo -m "moving files upwards"
 
-	echo "A  epsilon-new/mu" > $testroot/stdout.expected
-	echo "A  epsilon-new/psi/tau" >> $testroot/stdout.expected
-	echo "D  epsilon/psi/chi/tau" >> $testroot/stdout.expected
+	echo "D  epsilon/psi/chi/tau" > $testroot/stdout.expected
 	echo "D  epsilon/psi/mu" >> $testroot/stdout.expected
+	echo "A  epsilon-new/mu" >> $testroot/stdout.expected
+	echo "A  epsilon-new/psi/tau" >> $testroot/stdout.expected
 	echo -n "Updated to commit " >> $testroot/stdout.expected
 	git_show_head $testroot/repo >> $testroot/stdout.expected
 	echo >> $testroot/stdout.expected