1 files changed, 1153 insertions, 418 deletions

diff --git a/libarchive/archive_write_set_format_mtree.c b/libarchive/archive_write_set_format_mtree.c
index 3802a25..9c0613c 100644
--- a/libarchive/archive_write_set_format_mtree.c
+++ b/libarchive/archive_write_set_format_mtree.c
@@ -1,6 +1,6 @@
 /*-
- * Copyright (c) 2009,2011 Michihiro NAKAJIMA
  * Copyright (c) 2008 Joerg Sonnenberger
+ * Copyright (c) 2009-2012 Michihiro NAKAJIMA
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -38,6 +38,8 @@ __FBSDID("$FreeBSD: head/lib/libarchive/archive_write_set_format_mtree.c 201171
 #include "archive_crypto_private.h"
 #include "archive_entry.h"
 #include "archive_private.h"
+#include "archive_rb.h"
+#include "archive_string.h"
 #include "archive_write_private.h"
 
 #define INDENTNAMELEN	15
@@ -45,27 +47,39 @@ __FBSDID("$FreeBSD: head/lib/libarchive/archive_write_set_format_mtree.c 201171
 #define SET_KEYS	\
 	(F_FLAGS | F_GID | F_GNAME | F_MODE | F_TYPE | F_UID | F_UNAME)
 
-struct mtree_entry {
-	struct mtree_entry *next;
+struct attr_counter {
+	struct attr_counter *prev;
+	struct attr_counter *next;
+	struct mtree_entry *m_entry;
+	int count;
+};
 
-	char *pathname;
-	char *symlink;
-	unsigned int nlink;
-	mode_t filetype;
-	mode_t mode;
-	int64_t uid;
-	int64_t gid;
-	char *uname;
-	char *gname;
-	char *fflags_text;
-	unsigned long fflags_set;
-	unsigned long fflags_clear;
-	time_t mtime;
-	long mtime_nsec;
-	dev_t rdevmajor;
-	dev_t rdevminor;
-	int64_t size;
+struct att_counter_set {
+	struct attr_counter *uid_list;
+	struct attr_counter *gid_list;
+	struct attr_counter *mode_list;
+	struct attr_counter *flags_list;
+};
+
+struct mtree_chain {
+	struct mtree_entry *first;
+	struct mtree_entry **last;
+};
+
+/*
+ * The Data only for a directory file.
+ */
+struct dir_info {
+	struct archive_rb_tree rbtree;
+	struct mtree_chain children;
+	struct mtree_entry *chnext;
+	int virtual;
+};
 
+/*
+ * The Data only for a regular file.
+ */
+struct reg_info {
 	int compute_sum;
 	uint32_t crc;
 #ifdef ARCHIVE_HAS_MD5
@@ -88,23 +102,51 @@ struct mtree_entry {
 #endif
 };
 
-struct attr_counter {
-	struct attr_counter *prev;
-	struct attr_counter *next;
-	int count;
-	struct mtree_entry *m_entry;
+struct mtree_entry {
+	struct archive_rb_node rbnode;
+	struct mtree_entry *next;
+	struct mtree_entry *parent;
+	struct dir_info *dir_info;
+	struct reg_info *reg_info;
+
+	struct archive_string parentdir;
+	struct archive_string basename;
+	struct archive_string pathname;
+	struct archive_string symlink;
+	struct archive_string uname;
+	struct archive_string gname;
+	struct archive_string fflags_text;
+	unsigned int nlink;
+	mode_t filetype;
+	mode_t mode;
+	int64_t size;
+	int64_t uid;
+	int64_t gid;
+	time_t mtime;
+	long mtime_nsec;
+	unsigned long fflags_set;
+	unsigned long fflags_clear;
+	dev_t rdevmajor;
+	dev_t rdevminor;
 };
 
 struct mtree_writer {
 	struct mtree_entry *mtree_entry;
+	struct mtree_entry *root;
+	struct mtree_entry *cur_dirent;
+	struct archive_string cur_dirstr;
+	struct mtree_chain file_list;
+
 	struct archive_string ebuf;
 	struct archive_string buf;
 	int first;
 	uint64_t entry_bytes_remaining;
+
+	/*
+	 * Set global value.
+	 */
 	struct {
-		int		output;
-		int		processed;
-		struct archive_string parent;
+		int		processing;
 		mode_t		type;
 		int		keys;
 		int64_t		uid;
@@ -112,14 +154,11 @@ struct mtree_writer {
 		mode_t		mode;
 		unsigned long	fflags_set;
 		unsigned long	fflags_clear;
-
-		struct attr_counter *uid_list;
-		struct attr_counter *gid_list;
-		struct attr_counter *mode_list;
-		struct attr_counter *flags_list;
-		struct mtree_entry *me_first;
-		struct mtree_entry **me_last;
 	} set;
+	struct att_counter_set	acs;
+	int classic;
+	int depth;
+
 	/* check sum */
 	int compute_sum;
 	uint32_t crc;
@@ -173,27 +212,51 @@ struct mtree_writer {
 #define	F_SHA512	0x02000000		/* SHA-512 digest */
 
 	/* Options */
-	int dironly;		/* if the dironly is 1, ignore everything except
-				 * directory type files. like mtree(8) -d option.
-				 */
-	int indent;		/* if the indent is 1, indent writing data. */
+	int dironly;		/* If it is set, ignore all files except
+				 * directory files, like mtree(8) -d option. */
+	int indent;		/* If it is set, indent output data. */
+	int output_global_set;	/* If it is set, use /set keyword to set
+				 * global values. When generating mtree
+				 * classic format, it is set by default. */
 };
 
 #define DEFAULT_KEYS	(F_DEV | F_FLAGS | F_GID | F_GNAME | F_SLINK | F_MODE\
 			 | F_NLINK | F_SIZE | F_TIME | F_TYPE | F_UID\
 			 | F_UNAME)
+#define attr_counter_set_reset	attr_counter_set_free
 
-static struct attr_counter * new_attr_count(struct mtree_entry *,
-	struct attr_counter *);
-static void free_attr_count(struct attr_counter **);
-static int inc_attr_count(struct attr_counter **, struct attr_counter *,
+static void attr_counter_free(struct attr_counter **);
+static int attr_counter_inc(struct attr_counter **, struct attr_counter *,
 	struct attr_counter *, struct mtree_entry *);
-static int collect_set_values(struct mtree_writer *, struct mtree_entry *);
-static int get_keys(struct mtree_writer *, struct mtree_entry *);
+static struct attr_counter * attr_counter_new(struct mtree_entry *,
+	struct attr_counter *);
+static int attr_counter_set_collect(struct mtree_writer *,
+	struct mtree_entry *);
+static void attr_counter_set_free(struct mtree_writer *);
+static int get_global_set_keys(struct mtree_writer *, struct mtree_entry *);
+static int mtree_entry_add_child_tail(struct mtree_entry *,
+	struct mtree_entry *);
+static int mtree_entry_create_virtual_dir(struct archive_write *, const char *,
+	struct mtree_entry **);
+static int mtree_entry_cmp_node(const struct archive_rb_node *,
+	const struct archive_rb_node *);
+static int mtree_entry_cmp_key(const struct archive_rb_node *, const void *);
+static int mtree_entry_exchange_same_entry(struct archive_write *,
+    struct mtree_entry *, struct mtree_entry *);
+static void mtree_entry_free(struct mtree_entry *);
+static int mtree_entry_new(struct archive_write *, struct archive_entry *,
+	struct mtree_entry **);
+static void mtree_entry_register_free(struct mtree_writer *);
+static void mtree_entry_register_init(struct mtree_writer *);
+static int mtree_entry_setup_filenames(struct archive_write *,
+	struct mtree_entry *, struct archive_entry *);
+static int mtree_entry_tree_add(struct archive_write *, struct mtree_entry **);
 static void sum_init(struct mtree_writer *);
 static void sum_update(struct mtree_writer *, const void *, size_t);
-static void sum_final(struct mtree_writer *, struct mtree_entry *);
-static void sum_write(struct archive_string *, struct mtree_entry *);
+static void sum_final(struct mtree_writer *, struct reg_info *);
+static void sum_write(struct archive_string *, struct reg_info *);
+static int write_mtree_entry(struct archive_write *, struct mtree_entry *);
+static int write_dot_dot_entry(struct archive_write *, struct mtree_entry *);
 
 #define	COMPUTE_CRC(var, ch)	(var) = (var) << 8 ^ crctab[(var) >> 24 ^ (ch)]
 static const uint32_t crctab[] = {
@@ -251,26 +314,30 @@ static const uint32_t crctab[] = {
 	0xa2f33668, 0xbcb4666d, 0xb8757bda, 0xb5365d03, 0xb1f740b4
 };
 
-static int
-mtree_safe_char(char c)
-{
-	if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'))
-		return 1;
-	if (c >= '0' && c <= '9')
-		return 1;
-	if (c == 35 || c == 61 || c == 92)
-		return 0; /* #, = and \ are always quoted */
-	
-	if (c >= 33 && c <= 47) /* !"$%&'()*+,-./ */
-		return 1;
-	if (c >= 58 && c <= 64) /* :;<>?@ */
-		return 1;
-	if (c >= 91 && c <= 96) /* []^_` */
-		return 1;
-	if (c >= 123 && c <= 126) /* {|}~ */
-		return 1;
-	return 0;
-}
+static const unsigned char safe_char[256] = {
+	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 00 - 0F */
+	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 10 - 1F */
+	/* !"$%&'()*+,-./  EXCLUSION:0x20( ) 0x23(#) */
+	0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 20 - 2F */
+	/* 0123456789:;<>?  EXCLUSION:0x3d(=) */
+	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, /* 30 - 3F */
+	/* @ABCDEFGHIJKLMNO */
+	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 40 - 4F */
+	/* PQRSTUVWXYZ[]^_ EXCLUSION:0x5c(\)  */
+	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, /* 50 - 5F */
+	/* `abcdefghijklmno */
+	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 60 - 6F */
+	/* pqrstuvwxyz{|}~ */
+	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, /* 70 - 7F */
+	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 80 - 8F */
+	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 90 - 9F */
+	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* A0 - AF */
+	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* B0 - BF */
+	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* C0 - CF */
+	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* D0 - DF */
+	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* E0 - EF */
+	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* F0 - FF */
+};
 
 static void
 mtree_quote(struct archive_string *s, const char *str)
@@ -280,7 +347,7 @@ mtree_quote(struct archive_string *s, const char *str)
 	unsigned char c;
 
 	for (start = str; *str != '\0'; ++str) {
-		if (mtree_safe_char(*str))
+		if (safe_char[*(const unsigned char *)str])
 			continue;
 		if (start != str)
 			archive_strncat(s, start, str - start);
@@ -303,9 +370,19 @@ mtree_quote(struct archive_string *s, const char *str)
 static void
 mtree_indent(struct mtree_writer *mtree)
 {
-	int i, fn;
+	int i, fn, nd, pd;
 	const char *r, *s, *x;
 
+	if (mtree->classic) {
+		if (mtree->indent) {
+			nd = 0;
+			pd = mtree->depth * 4;
+		} else {
+			nd = mtree->depth?4:0;
+			pd = 0;
+		}
+	} else
+		nd = pd = 0;
 	fn = 1;
 	s = r = mtree->ebuf.s;
 	x = NULL;
@@ -314,37 +391,46 @@ mtree_indent(struct mtree_writer *mtree)
 	while ((r = strchr(r, ' ')) != NULL) {
 		if (fn) {
 			fn = 0;
+			for (i = 0; i < nd + pd; i++)
+				archive_strappend_char(&mtree->buf, ' ');
 			archive_strncat(&mtree->buf, s, r - s);
-			if (r -s > INDENTNAMELEN) {
+			if (nd + (r -s) > INDENTNAMELEN) {
 				archive_strncat(&mtree->buf, " \\\n", 3);
-				for (i = 0; i < (INDENTNAMELEN + 1); i++)
+				for (i = 0; i < (INDENTNAMELEN + 1 + pd); i++)
 					archive_strappend_char(&mtree->buf, ' ');
 			} else {
-				for (i = r -s; i < (INDENTNAMELEN + 1); i++)
+				for (i = (int)(r -s + nd);
+				    i < (INDENTNAMELEN + 1); i++)
 					archive_strappend_char(&mtree->buf, ' ');
 			}
 			s = ++r;
 			x = NULL;
 			continue;
 		}
-		if (r - s <= MAXLINELEN - 3 - INDENTNAMELEN)
+		if (pd + (r - s) <= MAXLINELEN - 3 - INDENTNAMELEN)
 			x = r++;
 		else {
 			if (x == NULL)
 				x = r;
 			archive_strncat(&mtree->buf, s, x - s);
 			archive_strncat(&mtree->buf, " \\\n", 3);
-			for (i = 0; i < (INDENTNAMELEN + 1); i++)
+			for (i = 0; i < (INDENTNAMELEN + 1 + pd); i++)
 				archive_strappend_char(&mtree->buf, ' ');
 			s = r = ++x;
 			x = NULL;
 		}
 	}
-	if (x != NULL && strlen(s) > MAXLINELEN - 3 - INDENTNAMELEN) {
+	if (fn) {
+		for (i = 0; i < nd + pd; i++)
+			archive_strappend_char(&mtree->buf, ' ');
+		archive_strcat(&mtree->buf, s);
+		s += strlen(s);
+	}
+	if (x != NULL && pd + strlen(s) > MAXLINELEN - 3 - INDENTNAMELEN) {
 		/* Last keyword is longer. */
 		archive_strncat(&mtree->buf, s, x - s);
 		archive_strncat(&mtree->buf, " \\\n", 3);
-		for (i = 0; i < (INDENTNAMELEN + 1); i++)
+		for (i = 0; i < (INDENTNAMELEN + 1 + pd); i++)
 			archive_strappend_char(&mtree->buf, ' ');
 		s = ++x;
 	}
@@ -352,163 +438,70 @@ mtree_indent(struct mtree_writer *mtree)
 	archive_string_empty(&mtree->ebuf);
 }
 
-#if !defined(_WIN32) || defined(__CYGWIN__)
-static size_t
-dir_len(struct mtree_entry *me)
-{
-	const char *path, *r;
-
-	path = me->pathname;
-	r = strrchr(path, '/');
-	if (r == NULL)
-		return (0);
-	/* Include a separator size */
-	return (r - path + 1);
-}
-
-#else /* _WIN32 && !__CYGWIN__ */
-/*
- * Note: We should use wide-character for findng '\' character,
- * a directory separator on Windows, because some character-set have
- * been using the '\' character for a part of its multibyte character
- * code.
- */
-static size_t
-dir_len(struct mtree_entry *me)
-{
-	wchar_t wc;
-	const char *path;
-	const char *p, *rp;
-	size_t al, l, size;
-
-	path = me->pathname;
-	al = l = -1;
-	for (p = path; *p != '\0'; ++p) {
-		if (*p == '\\')
-			al = l = p - path;
-		else if (*p == '/')
-			al = p - path;
-	}
-	if (l == -1)
-		goto alen;
-	size = p - path;
-	rp = p = path;
-	while (*p != '\0') {
-		l = mbtowc(&wc, p, size);
-		if (l == -1)
-			goto alen;
-		if (l == 1 && (wc == L'/' || wc == L'\\'))
-			rp = p;
-		p += l;
-		size -= l;
-	}
-	return (rp - path + 1);
-alen:
-	if (al == -1)
-		return (0);
-	return (al + 1);
-}
-#endif /* _WIN32 && !__CYGWIN__ */
-
-/*
- * Test if a parent directory of the current entry is changed.
- */
-static int
-parent_dir_changed(struct archive_string *dir, struct mtree_entry *me)
-{
-	const char *path;
-	size_t l;
-
-	l = dir_len(me);
-	path = me->pathname;
-	if (archive_strlen(dir) > 0) {
-		if (l == 0) {
-			archive_string_empty(dir);
-			return (1);
-		}
-		if (strncmp(dir->s, path, l) == 0)
-			return (0); /* The parent directory is the same. */
-	} else if (l == 0)
-		return (0);	    /* The parent directory is the same. */
-	archive_strncpy(dir, path, l);
-	return (1);
-}
-
 /*
  * Write /set keyword.
  * Set most used value of uid,gid,mode and fflags, which are
- * collected by collect_set_values() function.
+ * collected by attr_counter_set_collect() function.
  */
 static void
 write_global(struct mtree_writer *mtree)
 {
 	struct archive_string setstr;
 	struct archive_string unsetstr;
-	const char *name;
+	struct att_counter_set *acs;
 	int keys, oldkeys, effkeys;
-	struct attr_counter *ac;
 
 	archive_string_init(&setstr);
 	archive_string_init(&unsetstr);
 	keys = mtree->keys & SET_KEYS;
 	oldkeys = mtree->set.keys;
 	effkeys = keys;
-	if (mtree->set.processed) {
+	acs = &mtree->acs;
+	if (mtree->set.processing) {
 		/*
 		 * Check if the global data needs updating.
 		 */
 		effkeys &= ~F_TYPE;
-		if (oldkeys & (F_UNAME | F_UID)) {
-			ac = mtree->set.uid_list;
-			do {
-				if (mtree->set.uid == ac->m_entry->uid) {
-					effkeys &= ~(F_UNAME | F_UID);
-					break;
-				}
-				if (ac->next != NULL &&
-				    ac->next->count == ac->count)
-					continue;
-			} while (0);
+		if (acs->uid_list == NULL)
+			effkeys &= ~(F_UNAME | F_UID);
+		else if (oldkeys & (F_UNAME | F_UID)) {
+			if (acs->uid_list->count < 2 ||
+			    mtree->set.uid == acs->uid_list->m_entry->uid)
+				effkeys &= ~(F_UNAME | F_UID);
 		}
-		if (oldkeys & (F_GNAME | F_GID)) {
-			ac = mtree->set.gid_list;
-			do {
-				if (mtree->set.gid == ac->m_entry->gid) {
-					effkeys &= ~(F_GNAME | F_GID);
-					break;
-				}
-				if (ac->next != NULL &&
-				    ac->next->count == ac->count)
-					continue;
-			} while (0);
+		if (acs->gid_list == NULL)
+			effkeys &= ~(F_GNAME | F_GID);
+		else if (oldkeys & (F_GNAME | F_GID)) {
+			if (acs->gid_list->count < 2 ||
+			    mtree->set.gid == acs->gid_list->m_entry->gid)
+				effkeys &= ~(F_GNAME | F_GID);
 		}
-		if (oldkeys & F_MODE) {
-			ac = mtree->set.mode_list;
-			do {
-				if (mtree->set.mode == ac->m_entry->mode) {
-					effkeys &= ~F_MODE;
-					break;
-				}
-				if (ac->next != NULL &&
-				    ac->next->count == ac->count)
-					continue;
-			} while (0);
+		if (acs->mode_list == NULL)
+			effkeys &= ~F_MODE;
+		else if (oldkeys & F_MODE) {
+			if (acs->mode_list->count < 2 ||
+			    mtree->set.mode == acs->mode_list->m_entry->mode)
+				effkeys &= ~F_MODE;
 		}
-		if ((oldkeys & F_FLAGS) != 0) {
-			ac = mtree->set.flags_list;
-			do {
-				if (ac->m_entry->fflags_set ==
-					mtree->set.fflags_set &&
-				    ac->m_entry->fflags_clear ==
-					mtree->set.fflags_clear) {
-					effkeys &= ~F_FLAGS;
-					break;
-				}
-				if (ac->next != NULL &&
-				    ac->next->count == ac->count)
-					continue;
-			} while (0);
+		if (acs->flags_list == NULL)
+			effkeys &= ~F_FLAGS;
+		else if ((oldkeys & F_FLAGS) != 0) {
+			if (acs->flags_list->count < 2 ||
+			    (acs->flags_list->m_entry->fflags_set ==
+				mtree->set.fflags_set &&
+			     acs->flags_list->m_entry->fflags_clear ==
+				mtree->set.fflags_clear))
+				effkeys &= ~F_FLAGS;
 		}
+	} else {
+		if (acs->uid_list == NULL)
+			keys &= ~(F_UNAME | F_UID);
+		if (acs->gid_list == NULL)
+			keys &= ~(F_GNAME | F_GID);
+		if (acs->mode_list == NULL)
+			keys &= ~F_MODE;
+		if (acs->flags_list == NULL)
+			keys &= ~F_FLAGS;
 	}
 	if ((keys & effkeys & F_TYPE) != 0) {
 		if (mtree->dironly) {
@@ -520,10 +513,9 @@ write_global(struct mtree_writer *mtree)
 		}
 	}
 	if ((keys & effkeys & F_UNAME) != 0) {
-		name = mtree->set.uid_list->m_entry->uname;
-		if (name != NULL) {
+		if (archive_strlen(&(acs->uid_list->m_entry->uname)) > 0) {
 			archive_strcat(&setstr, " uname=");
-			mtree_quote(&setstr, name);
+			mtree_quote(&setstr, acs->uid_list->m_entry->uname.s);
 		} else {
 			keys &= ~F_UNAME;
 			if ((oldkeys & F_UNAME) != 0)
@@ -531,15 +523,14 @@ write_global(struct mtree_writer *mtree)
 		}
 	}
 	if ((keys & effkeys & F_UID) != 0) {
-		mtree->set.uid = mtree->set.uid_list->m_entry->uid;
+		mtree->set.uid = acs->uid_list->m_entry->uid;
 		archive_string_sprintf(&setstr, " uid=%jd",
 		    (intmax_t)mtree->set.uid);
 	}
 	if ((keys & effkeys & F_GNAME) != 0) {
-		name = mtree->set.gid_list->m_entry->gname;
-		if (name != NULL) {
+		if (archive_strlen(&(acs->gid_list->m_entry->gname)) > 0) {
 			archive_strcat(&setstr, " gname=");
-			mtree_quote(&setstr, name);
+			mtree_quote(&setstr, acs->gid_list->m_entry->gname.s);
 		} else {
 			keys &= ~F_GNAME;
 			if ((oldkeys & F_GNAME) != 0)
@@ -547,24 +538,25 @@ write_global(struct mtree_writer *mtree)
 		}
 	}
 	if ((keys & effkeys & F_GID) != 0) {
-		mtree->set.gid = mtree->set.gid_list->m_entry->gid;
+		mtree->set.gid = acs->gid_list->m_entry->gid;
 		archive_string_sprintf(&setstr, " gid=%jd",
 		    (intmax_t)mtree->set.gid);
 	}
 	if ((keys & effkeys & F_MODE) != 0) {
-		mtree->set.mode = mtree->set.mode_list->m_entry->mode;
+		mtree->set.mode = acs->mode_list->m_entry->mode;
 		archive_string_sprintf(&setstr, " mode=%o",
 		    (unsigned int)mtree->set.mode);
 	}
 	if ((keys & effkeys & F_FLAGS) != 0) {
-		name = mtree->set.flags_list->m_entry->fflags_text;
-		if (name != NULL) {
+		if (archive_strlen(
+		    &(acs->flags_list->m_entry->fflags_text)) > 0) {
 			archive_strcat(&setstr, " flags=");
-			mtree_quote(&setstr, name);
+			mtree_quote(&setstr,
+			    acs->flags_list->m_entry->fflags_text.s);
 			mtree->set.fflags_set =
-			    mtree->set.flags_list->m_entry->fflags_set;
+			    acs->flags_list->m_entry->fflags_set;
 			mtree->set.fflags_clear =
-			    mtree->set.flags_list->m_entry->fflags_clear;
+			    acs->flags_list->m_entry->fflags_clear;
 		} else {
 			keys &= ~F_FLAGS;
 			if ((oldkeys & F_FLAGS) != 0)
@@ -578,16 +570,11 @@ write_global(struct mtree_writer *mtree)
 		archive_string_sprintf(&mtree->buf, "/set%s\n", setstr.s);
 	archive_string_free(&setstr);
 	mtree->set.keys = keys;
-	mtree->set.processed = 1;
-
-	free_attr_count(&mtree->set.uid_list);
-	free_attr_count(&mtree->set.gid_list);
-	free_attr_count(&mtree->set.mode_list);
-	free_attr_count(&mtree->set.flags_list);
+	mtree->set.processing = 1;
 }
 
 static struct attr_counter *
-new_attr_count(struct mtree_entry *me, struct attr_counter *prev)
+attr_counter_new(struct mtree_entry *me, struct attr_counter *prev)
 {
 	struct attr_counter *ac;
 
@@ -602,7 +589,7 @@ new_attr_count(struct mtree_entry *me, struct attr_counter *prev)
 }
 
 static void
-free_attr_count(struct attr_counter **top)
+attr_counter_free(struct attr_counter **top)
 {
 	struct attr_counter *ac, *tac;
 
@@ -618,7 +605,7 @@ free_attr_count(struct attr_counter **top)
 }
 
 static int
-inc_attr_count(struct attr_counter **top, struct attr_counter *ac,
+attr_counter_inc(struct attr_counter **top, struct attr_counter *ac,
     struct attr_counter *last, struct mtree_entry *me)
 {
 	struct attr_counter *pac;
@@ -647,7 +634,7 @@ inc_attr_count(struct attr_counter **top, struct attr_counter *ac,
 			ac->next->prev = ac;
 		}
 	} else {
-		ac = new_attr_count(me, last);
+		ac = attr_counter_new(me, last);
 		if (ac == NULL)
 			return (-1);
 		last->next = ac;
@@ -655,93 +642,99 @@ inc_attr_count(struct attr_counter **top, struct attr_counter *ac,
 	return (0);
 }
 
+/*
+ * Tabulate uid,gid,mode and fflags of a entry in order to be used for /set.
+ */
 static int
-collect_set_values(struct mtree_writer *mtree, struct mtree_entry *me)
+attr_counter_set_collect(struct mtree_writer *mtree, struct mtree_entry *me)
 {
-	int keys = mtree->keys;
 	struct attr_counter *ac, *last;
+	struct att_counter_set *acs = &mtree->acs;
+	int keys = mtree->keys;
 
 	if (keys & (F_UNAME | F_UID)) {
-		if (mtree->set.uid_list == NULL) {
-			mtree->set.uid_list = new_attr_count(me, NULL);
-			if (mtree->set.uid_list == NULL)
+		if (acs->uid_list == NULL) {
+			acs->uid_list = attr_counter_new(me, NULL);
+			if (acs->uid_list == NULL)
 				return (-1);
 		} else {
 			last = NULL;
-			for (ac = mtree->set.uid_list; ac; ac = ac->next) {
+			for (ac = acs->uid_list; ac; ac = ac->next) {
 				if (ac->m_entry->uid == me->uid)
 					break;
 				last = ac;
 			}
-			if (inc_attr_count(
-			    &mtree->set.uid_list, ac, last, me) < 0)
+			if (attr_counter_inc(&acs->uid_list, ac, last, me) < 0)
 				return (-1);
 		}
 	}
 	if (keys & (F_GNAME | F_GID)) {
-		if (mtree->set.gid_list == NULL) {
-			mtree->set.gid_list = new_attr_count(me, NULL);
-			if (mtree->set.gid_list == NULL)
+		if (acs->gid_list == NULL) {
+			acs->gid_list = attr_counter_new(me, NULL);
+			if (acs->gid_list == NULL)
 				return (-1);
 		} else {
 			last = NULL;
-			for (ac = mtree->set.gid_list; ac; ac = ac->next) {
+			for (ac = acs->gid_list; ac; ac = ac->next) {
 				if (ac->m_entry->gid == me->gid)
 					break;
 				last = ac;
 			}
-			if (inc_attr_count(
-			    &mtree->set.gid_list, ac, last, me) < 0)
+			if (attr_counter_inc(&acs->gid_list, ac, last, me) < 0)
 				return (-1);
 		}
 	}
 	if (keys & F_MODE) {
-		if (mtree->set.mode_list == NULL) {
-			mtree->set.mode_list = new_attr_count(me, NULL);
-			if (mtree->set.mode_list == NULL)
+		if (acs->mode_list == NULL) {
+			acs->mode_list = attr_counter_new(me, NULL);
+			if (acs->mode_list == NULL)
 				return (-1);
 		} else {
 			last = NULL;
-			for (ac = mtree->set.mode_list; ac; ac = ac->next) {
+			for (ac = acs->mode_list; ac; ac = ac->next) {
 				if (ac->m_entry->mode == me->mode)
 					break;
 				last = ac;
 			}
-			if (inc_attr_count(
-			    &mtree->set.mode_list, ac, last, me) < 0)
+			if (attr_counter_inc(&acs->mode_list, ac, last, me) < 0)
 				return (-1);
 		}
 	}
 	if (keys & F_FLAGS) {
-		if (mtree->set.flags_list == NULL) {
-			mtree->set.flags_list = new_attr_count(me, NULL);
-			if (mtree->set.flags_list == NULL)
+		if (acs->flags_list == NULL) {
+			acs->flags_list = attr_counter_new(me, NULL);
+			if (acs->flags_list == NULL)
 				return (-1);
 		} else {
 			last = NULL;
-			for (ac = mtree->set.flags_list; ac; ac = ac->next) {
+			for (ac = acs->flags_list; ac; ac = ac->next) {
 				if (ac->m_entry->fflags_set == me->fflags_set &&
-				    ac->m_entry->fflags_clear == me->fflags_clear)
+				    ac->m_entry->fflags_clear ==
+							me->fflags_clear)
 					break;
 				last = ac;
 			}
-			if (inc_attr_count(
-			    &mtree->set.flags_list, ac, last, me) < 0)
+			if (attr_counter_inc(&acs->flags_list, ac, last, me) < 0)
 				return (-1);
 		}
 	}
 
-	/*
-	 * Save a entry.
-	 */
-	me->next = NULL;
-	*mtree->set.me_last = me;
-	mtree->set.me_last = &me->next;
 	return (0);
 }
 
+static void
+attr_counter_set_free(struct mtree_writer *mtree)
+{
+	struct att_counter_set *acs = &mtree->acs;
+
+	attr_counter_free(&acs->uid_list);
+	attr_counter_free(&acs->gid_list);
+	attr_counter_free(&acs->mode_list);
+	attr_counter_free(&acs->flags_list);
+}
+
 static int
-get_keys(struct mtree_writer *mtree, struct mtree_entry *me)
+get_global_set_keys(struct mtree_writer *mtree, struct mtree_entry *me)
 {
 	int keys;
 
@@ -788,56 +781,92 @@ get_keys(struct mtree_writer *mtree, struct mtree_entry *me)
 	return (keys);
 }
 
-static struct mtree_entry *
-new_mtree_entry(struct archive_entry *entry)
+static int
+mtree_entry_new(struct archive_write *a, struct archive_entry *entry,
+    struct mtree_entry **m_entry)
 {
 	struct mtree_entry *me;
 	const char *s;
+	int r;
+	static const struct archive_rb_tree_ops rb_ops = {
+		mtree_entry_cmp_node, mtree_entry_cmp_key
+	};
 
 	me = calloc(1, sizeof(*me));
-	if (me == NULL)
-		return (NULL);
-	me->pathname = strdup(archive_entry_pathname(entry));
+	if (me == NULL) {
+		archive_set_error(&a->archive, ENOMEM,
+		    "Can't allocate memory for a mtree entry");
+		*m_entry = NULL;
+		return (ARCHIVE_FATAL);
+	}
+
+	r = mtree_entry_setup_filenames(a, me, entry);
+	if (r < ARCHIVE_WARN) {
+		mtree_entry_free(me);
+		*m_entry = NULL;
+		return (r);
+	}
+
 	if ((s = archive_entry_symlink(entry)) != NULL)
-		me->symlink = strdup(s);
-	else
-		me->symlink = NULL;
+		archive_strcpy(&me->symlink, s);
 	me->nlink = archive_entry_nlink(entry);
 	me->filetype = archive_entry_filetype(entry);
 	me->mode = archive_entry_mode(entry) & 07777;
 	me->uid = archive_entry_uid(entry);
 	me->gid = archive_entry_gid(entry);
 	if ((s = archive_entry_uname(entry)) != NULL)
-		me->uname = strdup(s);
-	else
-		me->uname = NULL;
+		archive_strcpy(&me->uname, s);
 	if ((s = archive_entry_gname(entry)) != NULL)
-		me->gname = strdup(s);
-	else
-		me->gname = NULL;
+		archive_strcpy(&me->gname, s);
 	if ((s = archive_entry_fflags_text(entry)) != NULL)
-		me->fflags_text = strdup(s);
-	else
-		me->fflags_text = NULL;
+		archive_strcpy(&me->fflags_text, s);
 	archive_entry_fflags(entry, &me->fflags_set, &me->fflags_clear);
 	me->mtime = archive_entry_mtime(entry);
 	me->mtime_nsec = archive_entry_mtime_nsec(entry);
 	me->rdevmajor =	archive_entry_rdevmajor(entry);
 	me->rdevminor = archive_entry_rdevminor(entry);
 	me->size = archive_entry_size(entry);
-	me->compute_sum = 0;
+	if (me->filetype == AE_IFDIR) {
+		me->dir_info = calloc(1, sizeof(*me->dir_info));
+		if (me->dir_info == NULL) {
+			mtree_entry_free(me);
+			archive_set_error(&a->archive, ENOMEM,
+			    "Can't allocate memory for a mtree entry");
+			*m_entry = NULL;
+			return (ARCHIVE_FATAL);
+		}
+		__archive_rb_tree_init(&me->dir_info->rbtree, &rb_ops);
+		me->dir_info->children.first = NULL;
+		me->dir_info->children.last = &(me->dir_info->children.first);
+		me->dir_info->chnext = NULL;
+	} else if (me->filetype == AE_IFREG) {
+		me->reg_info = calloc(1, sizeof(*me->reg_info));
+		if (me->reg_info == NULL) {
+			mtree_entry_free(me);
+			archive_set_error(&a->archive, ENOMEM,
+			    "Can't allocate memory for a mtree entry");
+			*m_entry = NULL;
+			return (ARCHIVE_FATAL);
+		}
+		me->reg_info->compute_sum = 0;
+	}
 
-	return (me);
+	*m_entry = me;
+	return (ARCHIVE_OK);
 }
 
 static void
-free_mtree_entry(struct mtree_entry *me)
+mtree_entry_free(struct mtree_entry *me)
 {
-	free(me->pathname);
-	free(me->symlink);
-	free(me->uname);
-	free(me->gname);
-	free(me->fflags_text);
+	archive_string_free(&me->parentdir);
+	archive_string_free(&me->basename);
+	archive_string_free(&me->pathname);
+	archive_string_free(&me->symlink);
+	archive_string_free(&me->uname);
+	archive_string_free(&me->gname);
+	archive_string_free(&me->fflags_text);
+	free(me->dir_info);
+	free(me->reg_info);
 	free(me);
 }
 
@@ -846,66 +875,100 @@ archive_write_mtree_header(struct archive_write *a,
     struct archive_entry *entry)
 {
 	struct mtree_writer *mtree= a->format_data;
+	struct mtree_entry *mtree_entry;
+	int r, r2;
 
 	if (mtree->first) {
 		mtree->first = 0;
 		archive_strcat(&mtree->buf, "#mtree\n");
 		if ((mtree->keys & SET_KEYS) == 0)
-			mtree->set.output = 0;/* Disalbed. */
+			mtree->output_global_set = 0;/* Disalbed. */
 	}
 
 	mtree->entry_bytes_remaining = archive_entry_size(entry);
+
+	/* While directory only mode, we do not handle non directory files. */
 	if (mtree->dironly && archive_entry_filetype(entry) != AE_IFDIR)
 		return (ARCHIVE_OK);
 
-	mtree->mtree_entry = new_mtree_entry(entry);
-	if (mtree->mtree_entry == NULL) {
-		archive_set_error(&a->archive, ENOMEM,
-		    "Can't allocate mtree entry");
-		return (ARCHIVE_FATAL);
+	r2 = mtree_entry_new(a, entry, &mtree_entry);
+	if (r2 < ARCHIVE_WARN)
+		return (r2);
+	r = mtree_entry_tree_add(a, &mtree_entry);
+	if (r < ARCHIVE_WARN) {
+		mtree_entry_free(mtree_entry);
+		return (r);
 	}
+	mtree->mtree_entry = mtree_entry;
 
-	mtree->compute_sum = 0;
-
-	/* If current file is not a regular file, we do not have to
-	 * compute the sum of its content. */ 
-	if (archive_entry_filetype(entry) != AE_IFREG)
-		return (ARCHIVE_OK);
-		
-	/* Initialize a bunch of sum check context. */
-	sum_init(mtree);
+	/* If the current file is a regular file, we have to
+	 * compute the sum of its content.
+	 * Initialize a bunch of sum check context. */
+	if (mtree_entry->reg_info)
+		sum_init(mtree);
 
-	return (ARCHIVE_OK);
+	return (r2);
 }
 
 static int
-write_entry(struct archive_write *a, struct mtree_entry *me)
+write_mtree_entry(struct archive_write *a, struct mtree_entry *me)
 {
 	struct mtree_writer *mtree = a->format_data;
 	struct archive_string *str;
 	int keys, ret;
 
+	if (me->dir_info) {
+		if (mtree->classic) {
+			/*
+			 * Output a comment line to describe the full
+			 * pathname of the entry as mtree utility does
+			 * while generating classic format.
+			 */
+			if (!mtree->dironly)
+				archive_strappend_char(&mtree->buf, '\n');
+			if (me->parentdir.s)
+				archive_string_sprintf(&mtree->buf,
+				    "# %s/%s\n",
+				    me->parentdir.s, me->basename.s);
+			else
+				archive_string_sprintf(&mtree->buf,
+				    "# %s\n",
+				    me->basename.s);
+		}
+		if (mtree->output_global_set)
+			write_global(mtree);
+	}
 	archive_string_empty(&mtree->ebuf);
-	str = (mtree->indent)? &mtree->ebuf : &mtree->buf;
-	mtree_quote(str, me->pathname);
-	keys = get_keys(mtree, me);
+	str = (mtree->indent || mtree->classic)? &mtree->ebuf : &mtree->buf;
+
+	if (!mtree->classic && me->parentdir.s) {
+		/*
+		 * If generating format is not classic one(v1), output
+		 * a full pathname.
+		 */
+		mtree_quote(str, me->parentdir.s);
+		archive_strappend_char(str, '/');
+	}
+	mtree_quote(str, me->basename.s);
+
+	keys = get_global_set_keys(mtree, me);
 	if ((keys & F_NLINK) != 0 &&
 	    me->nlink != 1 && me->filetype != AE_IFDIR)
 		archive_string_sprintf(str, " nlink=%u", me->nlink);
 
-	if ((keys & F_GNAME) != 0 && me->gname != NULL) {
+	if ((keys & F_GNAME) != 0 && archive_strlen(&me->gname) > 0) {
 		archive_strcat(str, " gname=");
-		mtree_quote(str, me->gname);
+		mtree_quote(str, me->gname.s);
 	}
-	if ((keys & F_UNAME) != 0 && me->uname != NULL) {
+	if ((keys & F_UNAME) != 0 && archive_strlen(&me->uname) > 0) {
 		archive_strcat(str, " uname=");
-		mtree_quote(str, me->uname);
+		mtree_quote(str, me->uname.s);
 	}
 	if ((keys & F_FLAGS) != 0) {
-		if (me->fflags_text != NULL) {
+		if (archive_strlen(&me->fflags_text) > 0) {
 			archive_strcat(str, " flags=");
-			mtree_quote(str, me->fflags_text);
-		} else if (mtree->set.processed &&
+			mtree_quote(str, me->fflags_text.s);
+		} else if (mtree->set.processing &&
 		    (mtree->set.keys & F_FLAGS) != 0)
 			/* Overwrite the global parameter. */
 			archive_strcat(str, " flags=none");
@@ -926,7 +989,7 @@ write_entry(struct archive_write *a, struct mtree_entry *me)
 			archive_strcat(str, " type=link");
 		if ((keys & F_SLINK) != 0) {
 			archive_strcat(str, " link=");
-			mtree_quote(str, me->symlink);
+			mtree_quote(str, me->symlink.s);
 		}
 		break;
 	case AE_IFSOCK:
@@ -972,15 +1035,48 @@ write_entry(struct archive_write *a, struct mtree_entry *me)
 	}
 
 	/* Write a bunch of sum. */
-	if (me->filetype == AE_IFREG)
-		sum_write(str, me);
+	if (me->reg_info)
+		sum_write(str, me->reg_info);
+
+	archive_strappend_char(str, '\n');
+	if (mtree->indent || mtree->classic)
+		mtree_indent(mtree);
+
+	if (mtree->buf.length > 32768) {
+		ret = __archive_write_output(
+			a, mtree->buf.s, mtree->buf.length);
+		archive_string_empty(&mtree->buf);
+	} else
+		ret = ARCHIVE_OK;
+	return (ret);
+}
 
-	archive_strcat(str, "\n");
-	if (mtree->indent)
+static int
+write_dot_dot_entry(struct archive_write *a, struct mtree_entry *n)
+{
+	struct mtree_writer *mtree = a->format_data;
+	int ret;
+
+	if (n->parentdir.s) {
+		if (mtree->indent) {
+			int i, pd = mtree->depth * 4;
+			for (i = 0; i < pd; i++)
+				archive_strappend_char(&mtree->buf, ' ');
+		}
+		archive_string_sprintf(&mtree->buf, "# %s/%s\n",
+			n->parentdir.s, n->basename.s);
+	}
+
+	if (mtree->indent) {
+		archive_string_empty(&mtree->ebuf);
+		archive_strncat(&mtree->ebuf, "..\n\n", (mtree->dironly)?3:4);
 		mtree_indent(mtree);
+	} else
+		archive_strncat(&mtree->buf, "..\n\n", (mtree->dironly)?3:4);
 
 	if (mtree->buf.length > 32768) {
-		ret = __archive_write_output(a, mtree->buf.s, mtree->buf.length);
+		ret = __archive_write_output(
+			a, mtree->buf.s, mtree->buf.length);
 		archive_string_empty(&mtree->buf);
 	} else
 		ret = ARCHIVE_OK;
@@ -988,29 +1084,106 @@ write_entry(struct archive_write *a, struct mtree_entry *me)
 }
 
 /*
- * Write mtree entries saved at collect_set_values() function.
+ * Write mtree entries saved at attr_counter_set_collect() function.
  */
 static int
-write_mtree_entries(struct archive_write *a)
+write_mtree_entry_tree(struct archive_write *a)
 {
 	struct mtree_writer *mtree = a->format_data;
-	struct mtree_entry *me, *tme;
+	struct mtree_entry *np = mtree->root;
+	struct archive_rb_node *n;
 	int ret;
 
-	for (me = mtree->set.me_first; me; me = me->next) {
-		ret = write_entry(a, me);
-		if (ret != ARCHIVE_OK)
-			return (ARCHIVE_FATAL);
-	}
+	do {
+		if (mtree->output_global_set) {
+			/*
+			 * Collect attribute infomation to know which value
+			 * is frequently used among the children.
+			 */
+			attr_counter_set_reset(mtree);
+			ARCHIVE_RB_TREE_FOREACH(n, &(np->dir_info->rbtree)) {
+				struct mtree_entry *e = (struct mtree_entry *)n;
+				if (attr_counter_set_collect(mtree, e) < 0) {
+					archive_set_error(&a->archive, ENOMEM,
+					    "Can't allocate memory");
+					return (ARCHIVE_FATAL);
+				}
+			}
+		}
+		if (!np->dir_info->virtual || mtree->classic) {
+			ret = write_mtree_entry(a, np);
+			if (ret != ARCHIVE_OK)
+				return (ARCHIVE_FATAL);
+		} else {
+			/* Whenever output_global_set is enabled
+			 * output global value(/set keywords)
+			 * even if the directory entry is not allowd
+			 * to be written because the global values
+			 * can be used for the children. */
+			if (mtree->output_global_set)
+				write_global(mtree);
+		}
+		/*
+		 * Output the attribute of all files except directory files.
+		 */
+		mtree->depth++;
+		ARCHIVE_RB_TREE_FOREACH(n, &(np->dir_info->rbtree)) {
+			struct mtree_entry *e = (struct mtree_entry *)n;
+
+			if (e->dir_info)
+				mtree_entry_add_child_tail(np, e);
+			else {
+				ret = write_mtree_entry(a, e);
+				if (ret != ARCHIVE_OK)
+					return (ARCHIVE_FATAL);
+			}
+		}
+		mtree->depth--;
+
+		if (np->dir_info->children.first != NULL) {
+			/*
+			 * Descend the tree.
+			 */
+			np = np->dir_info->children.first;
+			if (mtree->indent)
+				mtree->depth++;
+			continue;
+		} else if (mtree->classic) {
+			/*
+			 * While printing mtree classic, if there are not
+			 * any directory files(except "." and "..") in the
+			 * directory, output two dots ".." as returning
+			 * the parent directory.
+			 */
+			ret = write_dot_dot_entry(a, np);
+			if (ret != ARCHIVE_OK)
+				return (ARCHIVE_FATAL);
+		}
+
+		while (np != np->parent) {
+			if (np->dir_info->chnext == NULL) {
+				/*
+				 * Ascend the tree; go back to the parent.
+				 */
+				if (mtree->indent)
+					mtree->depth--;
+				if (mtree->classic) {
+					ret = write_dot_dot_entry(a,
+						np->parent);
+					if (ret != ARCHIVE_OK)
+						return (ARCHIVE_FATAL);
+				}
+				np = np->parent;
+			} else {
+				/*
+				 * Switch to next mtree entry in the directory.
+				 */
+				np = np->dir_info->chnext;
+				break;
+			}
+		}
+	} while (np != np->parent); 
 
-	me = mtree->set.me_first;
-	while (me != NULL) {
-		tme = me->next;
-		free_mtree_entry(me);
-		me = tme;
-	}
-	mtree->set.me_first = NULL;
-	mtree->set.me_last = &mtree->set.me_first;
 	return (ARCHIVE_OK);
 }
 
@@ -1019,40 +1192,15 @@ archive_write_mtree_finish_entry(struct archive_write *a)
 {
 	struct mtree_writer *mtree = a->format_data;
 	struct mtree_entry *me;
-	int ret;
 
 	if ((me = mtree->mtree_entry) == NULL)
 		return (ARCHIVE_OK);
 	mtree->mtree_entry = NULL;
 
-	if (me->filetype == AE_IFREG)
-		sum_final(mtree, me);
+	if (me->reg_info)
+		sum_final(mtree, me->reg_info);
 
-	if (mtree->set.output) {
-		if (!mtree->dironly) {
-			if (archive_strlen(&mtree->set.parent) == 0)
-				parent_dir_changed(&mtree->set.parent, me);
-			if (parent_dir_changed(&mtree->set.parent, me)) {
-				/* Write /set keyword */
-				write_global(mtree);
-				/* Write entries saved by
-				 * collect_set_values() function. */
-				ret = write_mtree_entries(a);
-				if (ret != ARCHIVE_OK)
-					return (ARCHIVE_FATAL);
-			}
-		}
-		/* Tabulate uid,gid,mode and fflags of a entry
-		 * in order to be used for /set. and, at this time
-		 * we do not write a entry.  */
-		collect_set_values(mtree, me);
-		return (ARCHIVE_OK);
-	} else {
-		/* Write the current entry and free it. */
-		ret = write_entry(a, me);
-		free_mtree_entry(me);
-	}
-	return (ret == ARCHIVE_OK ? ret : ARCHIVE_FATAL);
+	return (ARCHIVE_OK);
 }
 
 static int
@@ -1061,9 +1209,8 @@ archive_write_mtree_close(struct archive_write *a)
 	struct mtree_writer *mtree= a->format_data;
 	int ret;
 
-	if (mtree->set.output && mtree->set.me_first != NULL) {
-		write_global(mtree);
-		ret = write_mtree_entries(a);
+	if (mtree->root != NULL) {
+		ret = write_mtree_entry_tree(a);
 		if (ret != ARCHIVE_OK)
 			return (ARCHIVE_FATAL);
 	}
@@ -1079,7 +1226,7 @@ archive_write_mtree_data(struct archive_write *a, const void *buff, size_t n)
 	struct mtree_writer *mtree= a->format_data;
 
 	if (n > mtree->entry_bytes_remaining)
-		n = mtree->entry_bytes_remaining;
+		n = (size_t)mtree->entry_bytes_remaining;
 	mtree->entry_bytes_remaining -= n;
 
 	/* We don't need to compute a regular file sum */
@@ -1096,25 +1243,16 @@ static int
 archive_write_mtree_free(struct archive_write *a)
 {
 	struct mtree_writer *mtree= a->format_data;
-	struct mtree_entry *me, *tme;
 
 	if (mtree == NULL)
 		return (ARCHIVE_OK);
 
 	/* Make sure we dot not leave any entries. */
-	me = mtree->set.me_first;
-	while (me != NULL) {
-		tme = me->next;
-		free_mtree_entry(me);
-		me = tme;
-	}
+	mtree_entry_register_free(mtree);
+	archive_string_free(&mtree->cur_dirstr);
 	archive_string_free(&mtree->ebuf);
 	archive_string_free(&mtree->buf);
-	archive_string_free(&mtree->set.parent);
-	free_attr_count(&mtree->set.uid_list);
-	free_attr_count(&mtree->set.gid_list);
-	free_attr_count(&mtree->set.mode_list);
-	free_attr_count(&mtree->set.flags_list);
+	attr_counter_set_free(mtree);
 	free(mtree);
 	a->format_data = NULL;
 	return (ARCHIVE_OK);
@@ -1209,7 +1347,7 @@ archive_write_mtree_options(struct archive_write *a, const char *key,
 		else if (strcmp(key, "uname") == 0)
 			keybit = F_UNAME;
 		else if (strcmp(key, "use-set") == 0) {
-			mtree->set.output = (value != NULL)? 1: 0;
+			mtree->output_global_set = (value != NULL)? 1: 0;
 			return (ARCHIVE_OK);
 		}
 		break;
@@ -1222,17 +1360,19 @@ archive_write_mtree_options(struct archive_write *a, const char *key,
 		return (ARCHIVE_OK);
 	}
 
-	return (ARCHIVE_FAILED);
+	/* Note: The "warn" return is just to inform the options
+	 * supervisor that we didn't handle it.  It will generate
+	 * a suitable error if no one used this option. */
+	return (ARCHIVE_WARN);
 }
 
-int
-archive_write_set_format_mtree(struct archive *_a)
+static int
+archive_write_set_format_mtree_default(struct archive *_a, const char *fn)
 {
 	struct archive_write *a = (struct archive_write *)_a;
 	struct mtree_writer *mtree;
 
-	archive_check_magic(_a, ARCHIVE_WRITE_MAGIC,
-	    ARCHIVE_STATE_NEW, "archive_write_set_format_mtree");
+	archive_check_magic(_a, ARCHIVE_WRITE_MAGIC, ARCHIVE_STATE_NEW, fn);
 
 	if (a->format_free != NULL)
 		(a->format_free)(a);
@@ -1246,14 +1386,12 @@ archive_write_set_format_mtree(struct archive *_a)
 	mtree->mtree_entry = NULL;
 	mtree->first = 1;
 	memset(&(mtree->set), 0, sizeof(mtree->set));
-	archive_string_init(&mtree->set.parent);
 	mtree->keys = DEFAULT_KEYS;
 	mtree->dironly = 0;
 	mtree->indent = 0;
 	archive_string_init(&mtree->ebuf);
 	archive_string_init(&mtree->buf);
-	mtree->set.me_first = NULL;
-	mtree->set.me_last = &mtree->set.me_first;
+	mtree_entry_register_init(mtree);
 	a->format_data = mtree;
 	a->format_free = archive_write_mtree_free;
 	a->format_name = "mtree";
@@ -1268,9 +1406,41 @@ archive_write_set_format_mtree(struct archive *_a)
 	return (ARCHIVE_OK);
 }
 
+int
+archive_write_set_format_mtree(struct archive *_a)
+{
+	return archive_write_set_format_mtree_default(_a,
+		"archive_write_set_format_mtree");
+}
+
+int
+archive_write_set_format_mtree_classic(struct archive *_a)
+{
+	int r;
+
+	r = archive_write_set_format_mtree_default(_a,
+		"archive_write_set_format_mtree_classic");
+	if (r == ARCHIVE_OK) {
+		struct archive_write *a = (struct archive_write *)_a;
+		struct mtree_writer *mtree;
+
+		mtree = (struct mtree_writer *)a->format_data;
+
+		/* Set to output a mtree archive in classic format. */
+		mtree->classic = 1;
+		/* Basically, mtree classic format uses '/set' global
+		 * value. */
+		mtree->output_global_set = 1;
+	}
+	return (r);
+}
+
 static void
 sum_init(struct mtree_writer *mtree)
 {
+
+	mtree->compute_sum = 0;
+
 	if (mtree->keys & F_CKSUM) {
 		mtree->compute_sum |= F_CKSUM;
 		mtree->crc = 0;
@@ -1367,7 +1537,7 @@ sum_update(struct mtree_writer *mtree, const void *buff, size_t n)
 }
 
 static void
-sum_final(struct mtree_writer *mtree, struct mtree_entry *me)
+sum_final(struct mtree_writer *mtree, struct reg_info *reg)
 {
 
 	if (mtree->compute_sum & F_CKSUM) {
@@ -1375,34 +1545,34 @@ sum_final(struct mtree_writer *mtree, struct mtree_entry *me)
 		/* Include the length of the file. */
 		for (len = mtree->crc_len; len != 0; len >>= 8)
 			COMPUTE_CRC(mtree->crc, len & 0xff);
-		me->crc = ~mtree->crc;
+		reg->crc = ~mtree->crc;
 	}
 #ifdef ARCHIVE_HAS_MD5
 	if (mtree->compute_sum & F_MD5)
-		archive_md5_final(&mtree->md5ctx, me->buf_md5);
+		archive_md5_final(&mtree->md5ctx, reg->buf_md5);
 #endif
 #ifdef ARCHIVE_HAS_RMD160
 	if (mtree->compute_sum & F_RMD160)
-		archive_rmd160_final(&mtree->rmd160ctx, me->buf_rmd160);
+		archive_rmd160_final(&mtree->rmd160ctx, reg->buf_rmd160);
 #endif
 #ifdef ARCHIVE_HAS_SHA1
 	if (mtree->compute_sum & F_SHA1)
-		archive_sha1_final(&mtree->sha1ctx, me->buf_sha1);
+		archive_sha1_final(&mtree->sha1ctx, reg->buf_sha1);
 #endif
 #ifdef ARCHIVE_HAS_SHA256
 	if (mtree->compute_sum & F_SHA256)
-		archive_sha256_final(&mtree->sha256ctx, me->buf_sha256);
+		archive_sha256_final(&mtree->sha256ctx, reg->buf_sha256);
 #endif
 #ifdef ARCHIVE_HAS_SHA384
 	if (mtree->compute_sum & F_SHA384)
-		archive_sha384_final(&mtree->sha384ctx, me->buf_sha384);
+		archive_sha384_final(&mtree->sha384ctx, reg->buf_sha384);
 #endif
 #ifdef ARCHIVE_HAS_SHA512
 	if (mtree->compute_sum & F_SHA512)
-		archive_sha512_final(&mtree->sha512ctx, me->buf_sha512);
+		archive_sha512_final(&mtree->sha512ctx, reg->buf_sha512);
 #endif
 	/* Save what types of sum are computed. */
-	me->compute_sum = mtree->compute_sum;
+	reg->compute_sum = mtree->compute_sum;
 }
 
 #if defined(ARCHIVE_HAS_MD5) || defined(ARCHIVE_HAS_RMD160) || \
@@ -1422,47 +1592,612 @@ strappend_bin(struct archive_string *s, const unsigned char *bin, int n)
 #endif
 
 static void
-sum_write(struct archive_string *str, struct mtree_entry *me)
+sum_write(struct archive_string *str, struct reg_info *reg)
 {
 
-	if (me->compute_sum & F_CKSUM) {
+	if (reg->compute_sum & F_CKSUM) {
 		archive_string_sprintf(str, " cksum=%ju",
-		    (uintmax_t)me->crc);
+		    (uintmax_t)reg->crc);
 	}
 #ifdef ARCHIVE_HAS_MD5
-	if (me->compute_sum & F_MD5) {
+	if (reg->compute_sum & F_MD5) {
 		archive_strcat(str, " md5digest=");
-		strappend_bin(str, me->buf_md5, sizeof(me->buf_md5));
+		strappend_bin(str, reg->buf_md5, sizeof(reg->buf_md5));
 	}
 #endif
 #ifdef ARCHIVE_HAS_RMD160
-	if (me->compute_sum & F_RMD160) {
+	if (reg->compute_sum & F_RMD160) {
 		archive_strcat(str, " rmd160digest=");
-		strappend_bin(str, me->buf_rmd160, sizeof(me->buf_rmd160));
+		strappend_bin(str, reg->buf_rmd160, sizeof(reg->buf_rmd160));
 	}
 #endif
 #ifdef ARCHIVE_HAS_SHA1
-	if (me->compute_sum & F_SHA1) {
+	if (reg->compute_sum & F_SHA1) {
 		archive_strcat(str, " sha1digest=");
-		strappend_bin(str, me->buf_sha1, sizeof(me->buf_sha1));
+		strappend_bin(str, reg->buf_sha1, sizeof(reg->buf_sha1));
 	}
 #endif
 #ifdef ARCHIVE_HAS_SHA256
-	if (me->compute_sum & F_SHA256) {
+	if (reg->compute_sum & F_SHA256) {
 		archive_strcat(str, " sha256digest=");
-		strappend_bin(str, me->buf_sha256, sizeof(me->buf_sha256));
+		strappend_bin(str, reg->buf_sha256, sizeof(reg->buf_sha256));
 	}
 #endif
 #ifdef ARCHIVE_HAS_SHA384
-	if (me->compute_sum & F_SHA384) {
+	if (reg->compute_sum & F_SHA384) {
 		archive_strcat(str, " sha384digest=");
-		strappend_bin(str, me->buf_sha384, sizeof(me->buf_sha384));
+		strappend_bin(str, reg->buf_sha384, sizeof(reg->buf_sha384));
 	}
 #endif
 #ifdef ARCHIVE_HAS_SHA512
-	if (me->compute_sum & F_SHA512) {
+	if (reg->compute_sum & F_SHA512) {
 		archive_strcat(str, " sha512digest=");
-		strappend_bin(str, me->buf_sha512, sizeof(me->buf_sha512));
+		strappend_bin(str, reg->buf_sha512, sizeof(reg->buf_sha512));
+	}
+#endif
+}
+
+static int
+mtree_entry_cmp_node(const struct archive_rb_node *n1,
+    const struct archive_rb_node *n2)
+{
+	const struct mtree_entry *e1 = (const struct mtree_entry *)n1;
+	const struct mtree_entry *e2 = (const struct mtree_entry *)n2;
+
+	return (strcmp(e2->basename.s, e1->basename.s));
+}
+
+static int
+mtree_entry_cmp_key(const struct archive_rb_node *n, const void *key)
+{
+	const struct mtree_entry *e = (const struct mtree_entry *)n;
+
+	return (strcmp((const char *)key, e->basename.s));
+}
+
+#if defined(_WIN32) || defined(__CYGWIN__)
+static int
+cleanup_backslash_1(char *p)
+{
+	int mb, dos;
+
+	mb = dos = 0;
+	while (*p) {
+		if (*(unsigned char *)p > 127)
+			mb = 1;
+		if (*p == '\\') {
+			/* If we have not met any multi-byte characters,
+			 * we can replace '\' with '/'. */
+			if (!mb)
+				*p = '/';
+			dos = 1;
+		}
+		p++;
+	}
+	if (!mb || !dos)
+		return (0);
+	return (-1);
+}
+
+static void
+cleanup_backslash_2(wchar_t *p)
+{
+
+	/* Convert a path-separator from '\' to  '/' */
+	while (*p != L'\0') {
+		if (*p == L'\\')
+			*p = L'/';
+		p++;
+	}
+}
+#endif
+
+/*
+ * Generate a parent directory name and a base name from a pathname.
+ */
+static int
+mtree_entry_setup_filenames(struct archive_write *a, struct mtree_entry *file,
+    struct archive_entry *entry)
+{
+	const char *pathname;
+	char *p, *dirname, *slash;
+	size_t len;
+	int ret = ARCHIVE_OK;
+
+	archive_strcpy(&file->pathname, archive_entry_pathname(entry));
+#if defined(_WIN32) || defined(__CYGWIN__)
+	/*
+	 * Convert a path-separator from '\' to  '/'
+	 */
+	if (cleanup_backslash_1(file->pathname.s) != 0) {
+		const wchar_t *wp = archive_entry_pathname_w(entry);
+		struct archive_wstring ws;
+
+		if (wp != NULL) {
+			int r;
+			archive_string_init(&ws);
+			archive_wstrcpy(&ws, wp);
+			cleanup_backslash_2(ws.s);
+			archive_string_empty(&(file->pathname));
+			r = archive_string_append_from_wcs(&(file->pathname),
+			    ws.s, ws.length);
+			archive_wstring_free(&ws);
+			if (r < 0 && errno == ENOMEM) {
+				archive_set_error(&a->archive, ENOMEM,
+				    "Can't allocate memory");
+				return (ARCHIVE_FATAL);
+			}
+		}
+	}
+#else
+	(void)a; /* UNUSED */
+#endif
+	pathname =  file->pathname.s;
+	if (strcmp(pathname, ".") == 0) {
+		archive_strcpy(&file->basename, ".");
+		return (ARCHIVE_OK);
+	}
+
+	archive_strcpy(&(file->parentdir), pathname);
+
+	len = file->parentdir.length;
+	p = dirname = file->parentdir.s;
+
+	/*
+	 * Remove leading '/' and '../' elements
+	 */
+	while (*p) {
+		if (p[0] == '/') {
+			p++;
+			len--;
+		} else if (p[0] != '.')
+			break;
+		else if (p[1] == '.' && p[2] == '/') {
+			p += 3;
+			len -= 3;
+		} else
+			break;
+	}
+	if (p != dirname) {
+		memmove(dirname, p, len+1);
+		p = dirname;
+	}
+	/*
+	 * Remove "/","/." and "/.." elements from tail.
+	 */
+	while (len > 0) {
+		size_t ll = len;
+
+		if (len > 0 && p[len-1] == '/') {
+			p[len-1] = '\0';
+			len--;
+		}
+		if (len > 1 && p[len-2] == '/' && p[len-1] == '.') {
+			p[len-2] = '\0';
+			len -= 2;
+		}
+		if (len > 2 && p[len-3] == '/' && p[len-2] == '.' &&
+		    p[len-1] == '.') {
+			p[len-3] = '\0';
+			len -= 3;
+		}
+		if (ll == len)
+			break;
+	}
+	while (*p) {
+		if (p[0] == '/') {
+			if (p[1] == '/')
+				/* Convert '//' --> '/' */
+				strcpy(p, p+1);
+			else if (p[1] == '.' && p[2] == '/')
+				/* Convert '/./' --> '/' */
+				strcpy(p, p+2);
+			else if (p[1] == '.' && p[2] == '.' && p[3] == '/') {
+				/* Convert 'dir/dir1/../dir2/'
+				 *     --> 'dir/dir2/'
+				 */
+				char *rp = p -1;
+				while (rp >= dirname) {
+					if (*rp == '/')
+						break;
+					--rp;
+				}
+				if (rp > dirname) {
+					strcpy(rp, p+3);
+					p = rp;
+				} else {
+					strcpy(dirname, p+4);
+					p = dirname;
+				}
+			} else
+				p++;
+		} else
+			p++;
+	}
+	p = dirname;
+	len = strlen(p);
+
+	/*
+	 * Add "./" prefiex.
+	 * NOTE: If the pathname does not have a path separator, we have
+	 * to add "./" to the head of the pathename because mtree reader
+	 * will suppose that it is v1(a.k.a classic) mtree format and
+	 * change the directory unexpectedly and so it will make a wrong
+	 * path.
+	 */
+	if (strcmp(p, ".") != 0 && strncmp(p, "./", 2) != 0) {
+		struct archive_string as;
+		archive_string_init(&as);
+		archive_strcpy(&as, "./");
+		archive_strncat(&as, p, len);
+		archive_string_empty(&file->parentdir);
+		archive_string_concat(&file->parentdir, &as);
+		archive_string_free(&as);
+		p = file->parentdir.s;
+		len = archive_strlen(&file->parentdir);
+	}
+
+	/*
+	 * Find out the position which points the last position of
+	 * path separator('/').
+	 */
+	slash = NULL;
+	for (; *p != '\0'; p++) {
+		if (*p == '/')
+			slash = p;
+	}
+	if (slash == NULL) {
+		/* The pathname doesn't have a parent directory. */
+		file->parentdir.length = len;
+		archive_string_copy(&(file->basename), &(file->parentdir));
+		archive_string_empty(&(file->parentdir));
+		*file->parentdir.s = '\0';
+		return (ret);
+	}
+
+	/* Make a basename from dirname and slash */
+	*slash  = '\0';
+	file->parentdir.length = slash - dirname;
+	archive_strcpy(&(file->basename),  slash + 1);
+	return (ret);
+}
+
+static int
+mtree_entry_create_virtual_dir(struct archive_write *a, const char *pathname,
+    struct mtree_entry **m_entry)
+{
+	struct archive_entry *entry;
+	struct mtree_entry *file;
+	int r;
+
+	entry = archive_entry_new();
+	if (entry == NULL) {
+		*m_entry = NULL;
+		archive_set_error(&a->archive, ENOMEM,
+		    "Can't allocate memory");
+		return (ARCHIVE_FATAL);
 	}
+	archive_entry_copy_pathname(entry, pathname);
+	archive_entry_set_mode(entry, AE_IFDIR | 0755);
+	archive_entry_set_mtime(entry, time(NULL), 0);
+
+	r = mtree_entry_new(a, entry, &file);
+	archive_entry_free(entry);
+	if (r < ARCHIVE_WARN) {
+		*m_entry = NULL;
+		archive_set_error(&a->archive, ENOMEM,
+		    "Can't allocate memory");
+		return (ARCHIVE_FATAL);
+	}
+
+	file->dir_info->virtual = 1;
+
+	*m_entry = file;
+	return (ARCHIVE_OK);
+}
+
+static void
+mtree_entry_register_add(struct mtree_writer *mtree, struct mtree_entry *file)
+{
+        file->next = NULL;
+        *mtree->file_list.last = file;
+        mtree->file_list.last = &(file->next);
+}
+
+static void
+mtree_entry_register_init(struct mtree_writer *mtree)
+{
+	mtree->file_list.first = NULL;
+	mtree->file_list.last = &(mtree->file_list.first);
+}
+
+static void
+mtree_entry_register_free(struct mtree_writer *mtree)
+{
+	struct mtree_entry *file, *file_next;
+
+	file = mtree->file_list.first;
+	while (file != NULL) {
+		file_next = file->next;
+		mtree_entry_free(file);
+		file = file_next;
+	}
+}
+
+static int
+mtree_entry_add_child_tail(struct mtree_entry *parent,
+    struct mtree_entry *child)
+{
+	child->dir_info->chnext = NULL;
+	*parent->dir_info->children.last = child;
+	parent->dir_info->children.last = &(child->dir_info->chnext);
+	return (1);
+}
+
+/*
+ * Find a entry from a parent entry with the name.
+ */
+static struct mtree_entry *
+mtree_entry_find_child(struct mtree_entry *parent, const char *child_name)
+{
+	struct mtree_entry *np;
+
+	if (parent == NULL)
+		return (NULL);
+	np = (struct mtree_entry *)__archive_rb_tree_find_node(
+	    &(parent->dir_info->rbtree), child_name);
+	return (np);
+}
+
+static int
+get_path_component(char *name, size_t n, const char *fn)
+{
+	char *p;
+	size_t l;
+
+	p = strchr(fn, '/');
+	if (p == NULL) {
+		if ((l = strlen(fn)) == 0)
+			return (0);
+	} else
+		l = p - fn;
+	if (l > n -1)
+		return (-1);
+	memcpy(name, fn, l);
+	name[l] = '\0';
+
+	return ((int)l);
+}
+
+/*
+ * Add a new entry into the tree.
+ */
+static int
+mtree_entry_tree_add(struct archive_write *a, struct mtree_entry **filep)
+{
+#if defined(_WIN32) && !defined(__CYGWIN__)
+	char name[_MAX_FNAME];/* Included null terminator size. */
+#elif defined(NAME_MAX) && NAME_MAX >= 255
+	char name[NAME_MAX+1];
+#else
+	char name[256];
 #endif
+	struct mtree_writer *mtree = (struct mtree_writer *)a->format_data;
+	struct mtree_entry *dent, *file, *np;
+	const char *fn, *p;
+	int l, r;
+
+	file = *filep;
+	if (file->parentdir.length == 0 && file->basename.length == 1 &&
+	    file->basename.s[0] == '.') {
+		file->parent = file;
+		if (mtree->root != NULL) {
+			np = mtree->root;
+			goto same_entry;
+		}
+		mtree->root = file;
+		mtree_entry_register_add(mtree, file);
+		return (ARCHIVE_OK);
+	}
+
+	if (file->parentdir.length == 0) {
+		archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC,
+		    "Internal programing error "
+		    "in generating canonical name for %s",
+		    file->pathname.s);
+		return (ARCHIVE_FAILED);
+	}
+
+	fn = p = file->parentdir.s;
+
+	/*
+	 * If the path of the parent directory of `file' entry is
+	 * the same as the path of `cur_dirent', add `file' entry to
+	 * `cur_dirent'.
+	 */
+	if (archive_strlen(&(mtree->cur_dirstr))
+	      == archive_strlen(&(file->parentdir)) &&
+	    strcmp(mtree->cur_dirstr.s, fn) == 0) {
+		if (!__archive_rb_tree_insert_node(
+		    &(mtree->cur_dirent->dir_info->rbtree),
+		    (struct archive_rb_node *)file)) {
+			/* There is the same name in the tree. */
+			np = (struct mtree_entry *)__archive_rb_tree_find_node(
+			    &(mtree->cur_dirent->dir_info->rbtree),
+			    file->basename.s);
+			goto same_entry;
+		}
+		file->parent = mtree->cur_dirent;
+		mtree_entry_register_add(mtree, file);
+		return (ARCHIVE_OK);
+	}
+
+	dent = mtree->root;
+	for (;;) {
+		l = get_path_component(name, sizeof(name), fn);
+		if (l == 0) {
+			np = NULL;
+			break;
+		}
+		if (l < 0) {
+			archive_set_error(&a->archive,
+			    ARCHIVE_ERRNO_MISC,
+			    "A name buffer is too small");
+			return (ARCHIVE_FATAL);
+		}
+		if (l == 1 && name[0] == '.' && dent != NULL &&
+		    dent == mtree->root) {
+			fn += l;
+			if (fn[0] == '/')
+				fn++;
+			continue;
+		}
+
+		np = mtree_entry_find_child(dent, name);
+		if (np == NULL || fn[0] == '\0')
+			break;
+
+		/* Find next sub directory. */
+		if (!np->dir_info) {
+			/* NOT Directory! */
+			archive_set_error(&a->archive,
+			    ARCHIVE_ERRNO_MISC,
+			    "`%s' is not directory, we cannot insert `%s' ",
+			    np->pathname.s, file->pathname.s);
+			return (ARCHIVE_FAILED);
+		}
+		fn += l;
+		if (fn[0] == '/')
+			fn++;
+		dent = np;
+	}
+	if (np == NULL) {
+		/*
+		 * Create virtual parent directories.
+		 */
+		while (fn[0] != '\0') {
+			struct mtree_entry *vp;
+			struct archive_string as;
+
+			archive_string_init(&as);
+			archive_strncat(&as, p, fn - p + l);
+			if (as.s[as.length-1] == '/') {
+				as.s[as.length-1] = '\0';
+				as.length--;
+			}
+			r = mtree_entry_create_virtual_dir(a, as.s, &vp);
+			archive_string_free(&as);
+			if (r < ARCHIVE_WARN)
+				return (r);
+
+			if (strcmp(vp->pathname.s, ".") == 0) {
+				vp->parent = vp;
+				mtree->root = vp;
+			} else {
+				__archive_rb_tree_insert_node(
+				    &(dent->dir_info->rbtree),
+				    (struct archive_rb_node *)vp);
+				vp->parent = dent;
+			}
+			mtree_entry_register_add(mtree, vp);
+			np = vp;
+
+			fn += l;
+			if (fn[0] == '/')
+				fn++;
+			l = get_path_component(name, sizeof(name), fn);
+			if (l < 0) {
+				archive_string_free(&as);
+				archive_set_error(&a->archive,
+				    ARCHIVE_ERRNO_MISC,
+				    "A name buffer is too small");
+				return (ARCHIVE_FATAL);
+			}
+			dent = np;
+		}
+
+		/* Found out the parent directory where `file' can be
+		 * inserted. */
+		mtree->cur_dirent = dent;
+		archive_string_empty(&(mtree->cur_dirstr));
+		archive_string_ensure(&(mtree->cur_dirstr),
+		    archive_strlen(&(dent->parentdir)) +
+		    archive_strlen(&(dent->basename)) + 2);
+		if (archive_strlen(&(dent->parentdir)) +
+		    archive_strlen(&(dent->basename)) == 0)
+			mtree->cur_dirstr.s[0] = 0;
+		else {
+			if (archive_strlen(&(dent->parentdir)) > 0) {
+				archive_string_copy(&(mtree->cur_dirstr),
+				    &(dent->parentdir));
+				archive_strappend_char(
+				    &(mtree->cur_dirstr), '/');
+			}
+			archive_string_concat(&(mtree->cur_dirstr),
+			    &(dent->basename));
+		}
+
+		if (!__archive_rb_tree_insert_node(
+		    &(dent->dir_info->rbtree),
+		    (struct archive_rb_node *)file)) {
+			np = (struct mtree_entry *)__archive_rb_tree_find_node(
+			    &(dent->dir_info->rbtree), file->basename.s);
+			goto same_entry;
+		}
+		file->parent = dent;
+		mtree_entry_register_add(mtree, file);
+		return (ARCHIVE_OK);
+	}
+
+same_entry:
+	/*
+	 * We have already has the entry the filename of which is
+	 * the same.
+	 */
+	r = mtree_entry_exchange_same_entry(a, np, file);
+	if (r < ARCHIVE_WARN)
+		return (r);
+	if (np->dir_info)
+		np->dir_info->virtual = 0;
+	*filep = np;
+	mtree_entry_free(file);
+	return (ARCHIVE_WARN);
+}
+
+static int
+mtree_entry_exchange_same_entry(struct archive_write *a, struct mtree_entry *np,
+    struct mtree_entry *file)
+{
+
+	if ((np->mode & AE_IFMT) != (file->mode & AE_IFMT)) {
+		archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC,
+		    "Found duplicate entries `%s' and its file type is "
+		    "different",
+		    np->pathname.s);
+		return (ARCHIVE_FAILED);
+	}
+
+	/* Update the existent mtree entry's attributes by the new one's. */
+	archive_string_empty(&np->symlink);
+	archive_string_concat(&np->symlink, &file->symlink);
+	archive_string_empty(&np->uname);
+	archive_string_concat(&np->uname, &file->uname);
+	archive_string_empty(&np->gname);
+	archive_string_concat(&np->gname, &file->gname);
+	archive_string_empty(&np->fflags_text);
+	archive_string_concat(&np->fflags_text, &file->fflags_text);
+	np->nlink = file->nlink;
+	np->filetype = file->filetype;
+	np->mode = file->mode;
+	np->size = file->size;
+	np->uid = file->uid;
+	np->gid = file->gid;
+	np->fflags_set = file->fflags_set;
+	np->fflags_clear = file->fflags_clear;
+	np->mtime = file->mtime;
+	np->mtime_nsec = file->mtime_nsec;
+	np->rdevmajor = file->rdevmajor;
+	np->rdevminor = file->rdevminor;
+
+	return (ARCHIVE_WARN);
 }