contrib/libarchive/libarchive/archive_write_set_format_mtree.c

   1 /*-
   2  * Copyright (c) 2008 Joerg Sonnenberger
   3  * Copyright (c) 2009-2012 Michihiro NAKAJIMA
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
  16  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  17  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  18  * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
  19  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  20  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  21  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  22  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  24  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25  */
  26
  27 #include "archive_platform.h"
  28 __FBSDID("$FreeBSD$");
  29
  30 #ifdef HAVE_SYS_TYPES_H
  31 #include <sys/types.h>
  32 #endif
  33 #include <errno.h>
  34 #include <stdlib.h>
  35 #include <string.h>
  36
  37 #include "archive.h"
  38 #include "archive_digest_private.h"
  39 #include "archive_entry.h"
  40 #include "archive_entry_private.h"
  41 #include "archive_private.h"
  42 #include "archive_rb.h"
  43 #include "archive_string.h"
  44 #include "archive_write_private.h"
  45
  46 #define INDENTNAMELEN   15
  47 #define MAXLINELEN      80
  48 #define SET_KEYS        \
  49         (F_FLAGS | F_GID | F_GNAME | F_MODE | F_TYPE | F_UID | F_UNAME)
  50
  51 struct attr_counter {
  52         struct attr_counter *prev;
  53         struct attr_counter *next;
  54         struct mtree_entry *m_entry;
  55         int count;
  56 };
  57
  58 struct att_counter_set {
  59         struct attr_counter *uid_list;
  60         struct attr_counter *gid_list;
  61         struct attr_counter *mode_list;
  62         struct attr_counter *flags_list;
  63 };
  64
  65 struct mtree_chain {
  66         struct mtree_entry *first;
  67         struct mtree_entry **last;
  68 };
  69
  70 /*
  71  * The Data only for a directory file.
  72  */
  73 struct dir_info {
  74         struct archive_rb_tree rbtree;
  75         struct mtree_chain children;
  76         struct mtree_entry *chnext;
  77         int virtual;
  78 };
  79
  80 /*
  81  * The Data only for a regular file.
  82  */
  83 struct reg_info {
  84         int compute_sum;
  85         uint32_t crc;
  86         struct ae_digest digest;
  87 };
  88
  89 struct mtree_entry {
  90         struct archive_rb_node rbnode;
  91         struct mtree_entry *next;
  92         struct mtree_entry *parent;
  93         struct dir_info *dir_info;
  94         struct reg_info *reg_info;
  95
  96         struct archive_string parentdir;
  97         struct archive_string basename;
  98         struct archive_string pathname;
  99         struct archive_string symlink;
 100         struct archive_string uname;
 101         struct archive_string gname;
 102         struct archive_string fflags_text;
 103         unsigned int nlink;
 104         mode_t filetype;
 105         mode_t mode;
 106         int64_t size;
 107         int64_t uid;
 108         int64_t gid;
 109         time_t mtime;
 110         long mtime_nsec;
 111         unsigned long fflags_set;
 112         unsigned long fflags_clear;
 113         dev_t rdevmajor;
 114         dev_t rdevminor;
 115         dev_t devmajor;
 116         dev_t devminor;
 117         int64_t ino;
 118 };
 119
 120 struct mtree_writer {
 121         struct mtree_entry *mtree_entry;
 122         struct mtree_entry *root;
 123         struct mtree_entry *cur_dirent;
 124         struct archive_string cur_dirstr;
 125         struct mtree_chain file_list;
 126
 127         struct archive_string ebuf;
 128         struct archive_string buf;
 129         int first;
 130         uint64_t entry_bytes_remaining;
 131
 132         /*
 133          * Set global value.
 134          */
 135         struct {
 136                 int             processing;
 137                 mode_t          type;
 138                 int             keys;
 139                 int64_t         uid;
 140                 int64_t         gid;
 141                 mode_t          mode;
 142                 unsigned long   fflags_set;
 143                 unsigned long   fflags_clear;
 144         } set;
 145         struct att_counter_set  acs;
 146         int classic;
 147         int depth;
 148
 149         /* check sum */
 150         int compute_sum;
 151         uint32_t crc;
 152         uint64_t crc_len;
 153 #ifdef ARCHIVE_HAS_MD5
 154         archive_md5_ctx md5ctx;
 155 #endif
 156 #ifdef ARCHIVE_HAS_RMD160
 157         archive_rmd160_ctx rmd160ctx;
 158 #endif
 159 #ifdef ARCHIVE_HAS_SHA1
 160         archive_sha1_ctx sha1ctx;
 161 #endif
 162 #ifdef ARCHIVE_HAS_SHA256
 163         archive_sha256_ctx sha256ctx;
 164 #endif
 165 #ifdef ARCHIVE_HAS_SHA384
 166         archive_sha384_ctx sha384ctx;
 167 #endif
 168 #ifdef ARCHIVE_HAS_SHA512
 169         archive_sha512_ctx sha512ctx;
 170 #endif
 171         /* Keyword options */
 172         int keys;
 173 #define F_CKSUM         0x00000001              /* checksum */
 174 #define F_DEV           0x00000002              /* device type */
 175 #define F_DONE          0x00000004              /* directory done */
 176 #define F_FLAGS         0x00000008              /* file flags */
 177 #define F_GID           0x00000010              /* gid */
 178 #define F_GNAME         0x00000020              /* group name */
 179 #define F_IGN           0x00000040              /* ignore */
 180 #define F_MAGIC         0x00000080              /* name has magic chars */
 181 #define F_MD5           0x00000100              /* MD5 digest */
 182 #define F_MODE          0x00000200              /* mode */
 183 #define F_NLINK         0x00000400              /* number of links */
 184 #define F_NOCHANGE      0x00000800              /* If owner/mode "wrong", do
 185                                                  * not change */
 186 #define F_OPT           0x00001000              /* existence optional */
 187 #define F_RMD160        0x00002000              /* RIPEMD160 digest */
 188 #define F_SHA1          0x00004000              /* SHA-1 digest */
 189 #define F_SIZE          0x00008000              /* size */
 190 #define F_SLINK         0x00010000              /* symbolic link */
 191 #define F_TAGS          0x00020000              /* tags */
 192 #define F_TIME          0x00040000              /* modification time */
 193 #define F_TYPE          0x00080000              /* file type */
 194 #define F_UID           0x00100000              /* uid */
 195 #define F_UNAME         0x00200000              /* user name */
 196 #define F_VISIT         0x00400000              /* file visited */
 197 #define F_SHA256        0x00800000              /* SHA-256 digest */
 198 #define F_SHA384        0x01000000              /* SHA-384 digest */
 199 #define F_SHA512        0x02000000              /* SHA-512 digest */
 200 #define F_INO           0x04000000              /* inode number */
 201 #define F_RESDEV        0x08000000              /* device ID on which the
 202                                                  * entry resides */
 203
 204         /* Options */
 205         int dironly;            /* If it is set, ignore all files except
 206                                  * directory files, like mtree(8) -d option. */
 207         int indent;             /* If it is set, indent output data. */
 208         int output_global_set;  /* If it is set, use /set keyword to set
 209                                  * global values. When generating mtree
 210                                  * classic format, it is set by default. */
 211 };
 212
 213 #define DEFAULT_KEYS    (F_DEV | F_FLAGS | F_GID | F_GNAME | F_SLINK | F_MODE\
 214                          | F_NLINK | F_SIZE | F_TIME | F_TYPE | F_UID\
 215                          | F_UNAME)
 216 #define attr_counter_set_reset  attr_counter_set_free
 217
 218 static void attr_counter_free(struct attr_counter **);
 219 static int attr_counter_inc(struct attr_counter **, struct attr_counter *,
 220         struct attr_counter *, struct mtree_entry *);
 221 static struct attr_counter * attr_counter_new(struct mtree_entry *,
 222         struct attr_counter *);
 223 static int attr_counter_set_collect(struct mtree_writer *,
 224         struct mtree_entry *);
 225 static void attr_counter_set_free(struct mtree_writer *);
 226 static int get_global_set_keys(struct mtree_writer *, struct mtree_entry *);
 227 static int mtree_entry_add_child_tail(struct mtree_entry *,
 228         struct mtree_entry *);
 229 static int mtree_entry_create_virtual_dir(struct archive_write *, const char *,
 230         struct mtree_entry **);
 231 static int mtree_entry_cmp_node(const struct archive_rb_node *,
 232         const struct archive_rb_node *);
 233 static int mtree_entry_cmp_key(const struct archive_rb_node *, const void *);
 234 static int mtree_entry_exchange_same_entry(struct archive_write *,
 235     struct mtree_entry *, struct mtree_entry *);
 236 static void mtree_entry_free(struct mtree_entry *);
 237 static int mtree_entry_new(struct archive_write *, struct archive_entry *,
 238         struct mtree_entry **);
 239 static void mtree_entry_register_free(struct mtree_writer *);
 240 static void mtree_entry_register_init(struct mtree_writer *);
 241 static int mtree_entry_setup_filenames(struct archive_write *,
 242         struct mtree_entry *, struct archive_entry *);
 243 static int mtree_entry_tree_add(struct archive_write *, struct mtree_entry **);
 244 static void sum_init(struct mtree_writer *);
 245 static void sum_update(struct mtree_writer *, const void *, size_t);
 246 static void sum_final(struct mtree_writer *, struct reg_info *);
 247 static void sum_write(struct archive_string *, struct reg_info *);
 248 static int write_mtree_entry(struct archive_write *, struct mtree_entry *);
 249 static int write_dot_dot_entry(struct archive_write *, struct mtree_entry *);
 250
 251 #define COMPUTE_CRC(var, ch)    (var) = (var) << 8 ^ crctab[(var) >> 24 ^ (ch)]
 252 static const uint32_t crctab[] = {
 253         0x0,
 254         0x04c11db7, 0x09823b6e, 0x0d4326d9, 0x130476dc, 0x17c56b6b,
 255         0x1a864db2, 0x1e475005, 0x2608edb8, 0x22c9f00f, 0x2f8ad6d6,
 256         0x2b4bcb61, 0x350c9b64, 0x31cd86d3, 0x3c8ea00a, 0x384fbdbd,
 257         0x4c11db70, 0x48d0c6c7, 0x4593e01e, 0x4152fda9, 0x5f15adac,
 258         0x5bd4b01b, 0x569796c2, 0x52568b75, 0x6a1936c8, 0x6ed82b7f,
 259         0x639b0da6, 0x675a1011, 0x791d4014, 0x7ddc5da3, 0x709f7b7a,
 260         0x745e66cd, 0x9823b6e0, 0x9ce2ab57, 0x91a18d8e, 0x95609039,
 261         0x8b27c03c, 0x8fe6dd8b, 0x82a5fb52, 0x8664e6e5, 0xbe2b5b58,
 262         0xbaea46ef, 0xb7a96036, 0xb3687d81, 0xad2f2d84, 0xa9ee3033,
 263         0xa4ad16ea, 0xa06c0b5d, 0xd4326d90, 0xd0f37027, 0xddb056fe,
 264         0xd9714b49, 0xc7361b4c, 0xc3f706fb, 0xceb42022, 0xca753d95,
 265         0xf23a8028, 0xf6fb9d9f, 0xfbb8bb46, 0xff79a6f1, 0xe13ef6f4,
 266         0xe5ffeb43, 0xe8bccd9a, 0xec7dd02d, 0x34867077, 0x30476dc0,
 267         0x3d044b19, 0x39c556ae, 0x278206ab, 0x23431b1c, 0x2e003dc5,
 268         0x2ac12072, 0x128e9dcf, 0x164f8078, 0x1b0ca6a1, 0x1fcdbb16,
 269         0x018aeb13, 0x054bf6a4, 0x0808d07d, 0x0cc9cdca, 0x7897ab07,
 270         0x7c56b6b0, 0x71159069, 0x75d48dde, 0x6b93dddb, 0x6f52c06c,
 271         0x6211e6b5, 0x66d0fb02, 0x5e9f46bf, 0x5a5e5b08, 0x571d7dd1,
 272         0x53dc6066, 0x4d9b3063, 0x495a2dd4, 0x44190b0d, 0x40d816ba,
 273         0xaca5c697, 0xa864db20, 0xa527fdf9, 0xa1e6e04e, 0xbfa1b04b,
 274         0xbb60adfc, 0xb6238b25, 0xb2e29692, 0x8aad2b2f, 0x8e6c3698,
 275         0x832f1041, 0x87ee0df6, 0x99a95df3, 0x9d684044, 0x902b669d,
 276         0x94ea7b2a, 0xe0b41de7, 0xe4750050, 0xe9362689, 0xedf73b3e,
 277         0xf3b06b3b, 0xf771768c, 0xfa325055, 0xfef34de2, 0xc6bcf05f,
 278         0xc27dede8, 0xcf3ecb31, 0xcbffd686, 0xd5b88683, 0xd1799b34,
 279         0xdc3abded, 0xd8fba05a, 0x690ce0ee, 0x6dcdfd59, 0x608edb80,
 280         0x644fc637, 0x7a089632, 0x7ec98b85, 0x738aad5c, 0x774bb0eb,
 281         0x4f040d56, 0x4bc510e1, 0x46863638, 0x42472b8f, 0x5c007b8a,
 282         0x58c1663d, 0x558240e4, 0x51435d53, 0x251d3b9e, 0x21dc2629,
 283         0x2c9f00f0, 0x285e1d47, 0x36194d42, 0x32d850f5, 0x3f9b762c,
 284         0x3b5a6b9b, 0x0315d626, 0x07d4cb91, 0x0a97ed48, 0x0e56f0ff,
 285         0x1011a0fa, 0x14d0bd4d, 0x19939b94, 0x1d528623, 0xf12f560e,
 286         0xf5ee4bb9, 0xf8ad6d60, 0xfc6c70d7, 0xe22b20d2, 0xe6ea3d65,
 287         0xeba91bbc, 0xef68060b, 0xd727bbb6, 0xd3e6a601, 0xdea580d8,
 288         0xda649d6f, 0xc423cd6a, 0xc0e2d0dd, 0xcda1f604, 0xc960ebb3,
 289         0xbd3e8d7e, 0xb9ff90c9, 0xb4bcb610, 0xb07daba7, 0xae3afba2,
 290         0xaafbe615, 0xa7b8c0cc, 0xa379dd7b, 0x9b3660c6, 0x9ff77d71,
 291         0x92b45ba8, 0x9675461f, 0x8832161a, 0x8cf30bad, 0x81b02d74,
 292         0x857130c3, 0x5d8a9099, 0x594b8d2e, 0x5408abf7, 0x50c9b640,
 293         0x4e8ee645, 0x4a4ffbf2, 0x470cdd2b, 0x43cdc09c, 0x7b827d21,
 294         0x7f436096, 0x7200464f, 0x76c15bf8, 0x68860bfd, 0x6c47164a,
 295         0x61043093, 0x65c52d24, 0x119b4be9, 0x155a565e, 0x18197087,
 296         0x1cd86d30, 0x029f3d35, 0x065e2082, 0x0b1d065b, 0x0fdc1bec,
 297         0x3793a651, 0x3352bbe6, 0x3e119d3f, 0x3ad08088, 0x2497d08d,
 298         0x2056cd3a, 0x2d15ebe3, 0x29d4f654, 0xc5a92679, 0xc1683bce,
 299         0xcc2b1d17, 0xc8ea00a0, 0xd6ad50a5, 0xd26c4d12, 0xdf2f6bcb,
 300         0xdbee767c, 0xe3a1cbc1, 0xe760d676, 0xea23f0af, 0xeee2ed18,
 301         0xf0a5bd1d, 0xf464a0aa, 0xf9278673, 0xfde69bc4, 0x89b8fd09,
 302         0x8d79e0be, 0x803ac667, 0x84fbdbd0, 0x9abc8bd5, 0x9e7d9662,
 303         0x933eb0bb, 0x97ffad0c, 0xafb010b1, 0xab710d06, 0xa6322bdf,
 304         0xa2f33668, 0xbcb4666d, 0xb8757bda, 0xb5365d03, 0xb1f740b4
 305 };
 306
 307 static const unsigned char safe_char[256] = {
 308         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 00 - 0F */
 309         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 10 - 1F */
 310         /* !"$%&'()*+,-./  EXCLUSION:0x20( ) 0x23(#) */
 311         0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 20 - 2F */
 312         /* 0123456789:;<>?  EXCLUSION:0x3d(=) */
 313         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, /* 30 - 3F */
 314         /* @ABCDEFGHIJKLMNO */
 315         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 40 - 4F */
 316         /* PQRSTUVWXYZ[]^_ EXCLUSION:0x5c(\)  */
 317         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, /* 50 - 5F */
 318         /* `abcdefghijklmno */
 319         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 60 - 6F */
 320         /* pqrstuvwxyz{|}~ */
 321         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, /* 70 - 7F */
 322         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 80 - 8F */
 323         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 90 - 9F */
 324         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* A0 - AF */
 325         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* B0 - BF */
 326         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* C0 - CF */
 327         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* D0 - DF */
 328         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* E0 - EF */
 329         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* F0 - FF */
 330 };
 331
 332 static void
 333 mtree_quote(struct archive_string *s, const char *str)
 334 {
 335         const char *start;
 336         char buf[4];
 337         unsigned char c;
 338
 339         for (start = str; *str != '\0'; ++str) {
 340                 if (safe_char[*(const unsigned char *)str])
 341                         continue;
 342                 if (start != str)
 343                         archive_strncat(s, start, str - start);
 344                 c = (unsigned char)*str;
 345                 buf[0] = '\\';
 346                 buf[1] = (c / 64) + '0';
 347                 buf[2] = (c / 8 % 8) + '0';
 348                 buf[3] = (c % 8) + '0';
 349                 archive_strncat(s, buf, 4);
 350                 start = str + 1;
 351         }
 352
 353         if (start != str)
 354                 archive_strncat(s, start, str - start);
 355 }
 356
 357 /*
 358  * Indent a line as the mtree utility does so it is readable for people.
 359  */
 360 static void
 361 mtree_indent(struct mtree_writer *mtree)
 362 {
 363         int i, fn, nd, pd;
 364         const char *r, *s, *x;
 365
 366         if (mtree->classic) {
 367                 if (mtree->indent) {
 368                         nd = 0;
 369                         pd = mtree->depth * 4;
 370                 } else {
 371                         nd = mtree->depth?4:0;
 372                         pd = 0;
 373                 }
 374         } else
 375                 nd = pd = 0;
 376         fn = 1;
 377         s = r = mtree->ebuf.s;
 378         x = NULL;
 379         while (*r == ' ')
 380                 r++;
 381         while ((r = strchr(r, ' ')) != NULL) {
 382                 if (fn) {
 383                         fn = 0;
 384                         for (i = 0; i < nd + pd; i++)
 385                                 archive_strappend_char(&mtree->buf, ' ');
 386                         archive_strncat(&mtree->buf, s, r - s);
 387                         if (nd + (r -s) > INDENTNAMELEN) {
 388                                 archive_strncat(&mtree->buf, " \\\n", 3);
 389                                 for (i = 0; i < (INDENTNAMELEN + 1 + pd); i++)
 390                                         archive_strappend_char(&mtree->buf, ' ');
 391                         } else {
 392                                 for (i = (int)(r -s + nd);
 393                                     i < (INDENTNAMELEN + 1); i++)
 394                                         archive_strappend_char(&mtree->buf, ' ');
 395                         }
 396                         s = ++r;
 397                         x = NULL;
 398                         continue;
 399                 }
 400                 if (pd + (r - s) <= MAXLINELEN - 3 - INDENTNAMELEN)
 401                         x = r++;
 402                 else {
 403                         if (x == NULL)
 404                                 x = r;
 405                         archive_strncat(&mtree->buf, s, x - s);
 406                         archive_strncat(&mtree->buf, " \\\n", 3);
 407                         for (i = 0; i < (INDENTNAMELEN + 1 + pd); i++)
 408                                 archive_strappend_char(&mtree->buf, ' ');
 409                         s = r = ++x;
 410                         x = NULL;
 411                 }
 412         }
 413         if (fn) {
 414                 for (i = 0; i < nd + pd; i++)
 415                         archive_strappend_char(&mtree->buf, ' ');
 416                 archive_strcat(&mtree->buf, s);
 417                 s += strlen(s);
 418         }
 419         if (x != NULL && pd + strlen(s) > MAXLINELEN - 3 - INDENTNAMELEN) {
 420                 /* Last keyword is longer. */
 421                 archive_strncat(&mtree->buf, s, x - s);
 422                 archive_strncat(&mtree->buf, " \\\n", 3);
 423                 for (i = 0; i < (INDENTNAMELEN + 1 + pd); i++)
 424                         archive_strappend_char(&mtree->buf, ' ');
 425                 s = ++x;
 426         }
 427         archive_strcat(&mtree->buf, s);
 428         archive_string_empty(&mtree->ebuf);
 429 }
 430
 431 /*
 432  * Write /set keyword.
 433  * Set the most used value of uid, gid, mode and fflags, which are
 434  * collected by the attr_counter_set_collect() function.
 435  */
 436 static void
 437 write_global(struct mtree_writer *mtree)
 438 {
 439         struct archive_string setstr;
 440         struct archive_string unsetstr;
 441         struct att_counter_set *acs;
 442         int keys, oldkeys, effkeys;
 443
 444         archive_string_init(&setstr);
 445         archive_string_init(&unsetstr);
 446         keys = mtree->keys & SET_KEYS;
 447         oldkeys = mtree->set.keys;
 448         effkeys = keys;
 449         acs = &mtree->acs;
 450         if (mtree->set.processing) {
 451                 /*
 452                  * Check if the global data needs updating.
 453                  */
 454                 effkeys &= ~F_TYPE;
 455                 if (acs->uid_list == NULL)
 456                         effkeys &= ~(F_UNAME | F_UID);
 457                 else if (oldkeys & (F_UNAME | F_UID)) {
 458                         if (acs->uid_list->count < 2 ||
 459                             mtree->set.uid == acs->uid_list->m_entry->uid)
 460                                 effkeys &= ~(F_UNAME | F_UID);
 461                 }
 462                 if (acs->gid_list == NULL)
 463                         effkeys &= ~(F_GNAME | F_GID);
 464                 else if (oldkeys & (F_GNAME | F_GID)) {
 465                         if (acs->gid_list->count < 2 ||
 466                             mtree->set.gid == acs->gid_list->m_entry->gid)
 467                                 effkeys &= ~(F_GNAME | F_GID);
 468                 }
 469                 if (acs->mode_list == NULL)
 470                         effkeys &= ~F_MODE;
 471                 else if (oldkeys & F_MODE) {
 472                         if (acs->mode_list->count < 2 ||
 473                             mtree->set.mode == acs->mode_list->m_entry->mode)
 474                                 effkeys &= ~F_MODE;
 475                 }
 476                 if (acs->flags_list == NULL)
 477                         effkeys &= ~F_FLAGS;
 478                 else if ((oldkeys & F_FLAGS) != 0) {
 479                         if (acs->flags_list->count < 2 ||
 480                             (acs->flags_list->m_entry->fflags_set ==
 481                                 mtree->set.fflags_set &&
 482                              acs->flags_list->m_entry->fflags_clear ==
 483                                 mtree->set.fflags_clear))
 484                                 effkeys &= ~F_FLAGS;
 485                 }
 486         } else {
 487                 if (acs->uid_list == NULL)
 488                         keys &= ~(F_UNAME | F_UID);
 489                 if (acs->gid_list == NULL)
 490                         keys &= ~(F_GNAME | F_GID);
 491                 if (acs->mode_list == NULL)
 492                         keys &= ~F_MODE;
 493                 if (acs->flags_list == NULL)
 494                         keys &= ~F_FLAGS;
 495         }
 496         if ((keys & effkeys & F_TYPE) != 0) {
 497                 if (mtree->dironly) {
 498                         archive_strcat(&setstr, " type=dir");
 499                         mtree->set.type = AE_IFDIR;
 500                 } else {
 501                         archive_strcat(&setstr, " type=file");
 502                         mtree->set.type = AE_IFREG;
 503                 }
 504         }
 505         if ((keys & effkeys & F_UNAME) != 0) {
 506                 if (archive_strlen(&(acs->uid_list->m_entry->uname)) > 0) {
 507                         archive_strcat(&setstr, " uname=");
 508                         mtree_quote(&setstr, acs->uid_list->m_entry->uname.s);
 509                 } else {
 510                         keys &= ~F_UNAME;
 511                         if ((oldkeys & F_UNAME) != 0)
 512                                 archive_strcat(&unsetstr, " uname");
 513                 }
 514         }
 515         if ((keys & effkeys & F_UID) != 0) {
 516                 mtree->set.uid = acs->uid_list->m_entry->uid;
 517                 archive_string_sprintf(&setstr, " uid=%jd",
 518                     (intmax_t)mtree->set.uid);
 519         }
 520         if ((keys & effkeys & F_GNAME) != 0) {
 521                 if (archive_strlen(&(acs->gid_list->m_entry->gname)) > 0) {
 522                         archive_strcat(&setstr, " gname=");
 523                         mtree_quote(&setstr, acs->gid_list->m_entry->gname.s);
 524                 } else {
 525                         keys &= ~F_GNAME;
 526                         if ((oldkeys & F_GNAME) != 0)
 527                                 archive_strcat(&unsetstr, " gname");
 528                 }
 529         }
 530         if ((keys & effkeys & F_GID) != 0) {
 531                 mtree->set.gid = acs->gid_list->m_entry->gid;
 532                 archive_string_sprintf(&setstr, " gid=%jd",
 533                     (intmax_t)mtree->set.gid);
 534         }
 535         if ((keys & effkeys & F_MODE) != 0) {
 536                 mtree->set.mode = acs->mode_list->m_entry->mode;
 537                 archive_string_sprintf(&setstr, " mode=%o",
 538                     (unsigned int)mtree->set.mode);
 539         }
 540         if ((keys & effkeys & F_FLAGS) != 0) {
 541                 if (archive_strlen(
 542                     &(acs->flags_list->m_entry->fflags_text)) > 0) {
 543                         archive_strcat(&setstr, " flags=");
 544                         mtree_quote(&setstr,
 545                             acs->flags_list->m_entry->fflags_text.s);
 546                         mtree->set.fflags_set =
 547                             acs->flags_list->m_entry->fflags_set;
 548                         mtree->set.fflags_clear =
 549                             acs->flags_list->m_entry->fflags_clear;
 550                 } else {
 551                         keys &= ~F_FLAGS;
 552                         if ((oldkeys & F_FLAGS) != 0)
 553                                 archive_strcat(&unsetstr, " flags");
 554                 }
 555         }
 556         if (unsetstr.length > 0)
 557                 archive_string_sprintf(&mtree->buf, "/unset%s\n", unsetstr.s);
 558         archive_string_free(&unsetstr);
 559         if (setstr.length > 0)
 560                 archive_string_sprintf(&mtree->buf, "/set%s\n", setstr.s);
 561         archive_string_free(&setstr);
 562         mtree->set.keys = keys;
 563         mtree->set.processing = 1;
 564 }
 565
 566 static struct attr_counter *
 567 attr_counter_new(struct mtree_entry *me, struct attr_counter *prev)
 568 {
 569         struct attr_counter *ac;
 570
 571         ac = malloc(sizeof(*ac));
 572         if (ac != NULL) {
 573                 ac->prev = prev;
 574                 ac->next = NULL;
 575                 ac->count = 1;
 576                 ac->m_entry = me;
 577         }
 578         return (ac);
 579 }
 580
 581 static void
 582 attr_counter_free(struct attr_counter **top)
 583 {
 584         struct attr_counter *ac, *tac;
 585
 586         if (*top == NULL)
 587                 return;
 588         ac = *top;
 589         while (ac != NULL) {
 590                 tac = ac->next;
 591                 free(ac);
 592                 ac = tac;
 593         }
 594         *top = NULL;
 595 }
 596
 597 static int
 598 attr_counter_inc(struct attr_counter **top, struct attr_counter *ac,
 599     struct attr_counter *last, struct mtree_entry *me)
 600 {
 601         struct attr_counter *pac;
 602
 603         if (ac != NULL) {
 604                 ac->count++;
 605                 if (*top == ac || ac->prev->count >= ac->count)
 606                         return (0);
 607                 for (pac = ac->prev; pac; pac = pac->prev) {
 608                         if (pac->count >= ac->count)
 609                                 break;
 610                 }
 611                 ac->prev->next = ac->next;
 612                 if (ac->next != NULL)
 613                         ac->next->prev = ac->prev;
 614                 if (pac != NULL) {
 615                         ac->prev = pac;
 616                         ac->next = pac->next;
 617                         pac->next = ac;
 618                         if (ac->next != NULL)
 619                                 ac->next->prev = ac;
 620                 } else {
 621                         ac->prev = NULL;
 622                         ac->next = *top;
 623                         *top = ac;
 624                         ac->next->prev = ac;
 625                 }
 626         } else if (last != NULL) {
 627                 ac = attr_counter_new(me, last);
 628                 if (ac == NULL)
 629                         return (-1);
 630                 last->next = ac;
 631         }
 632         return (0);
 633 }
 634
 635 /*
 636  * Tabulate uid, gid, mode and fflags of a entry in order to be used for /set.
 637  */
 638 static int
 639 attr_counter_set_collect(struct mtree_writer *mtree, struct mtree_entry *me)
 640 {
 641         struct attr_counter *ac, *last;
 642         struct att_counter_set *acs = &mtree->acs;
 643         int keys = mtree->keys;
 644
 645         if (keys & (F_UNAME | F_UID)) {
 646                 if (acs->uid_list == NULL) {
 647                         acs->uid_list = attr_counter_new(me, NULL);
 648                         if (acs->uid_list == NULL)
 649                                 return (-1);
 650                 } else {
 651                         last = NULL;
 652                         for (ac = acs->uid_list; ac; ac = ac->next) {
 653                                 if (ac->m_entry->uid == me->uid)
 654                                         break;
 655                                 last = ac;
 656                         }
 657                         if (attr_counter_inc(&acs->uid_list, ac, last, me) < 0)
 658                                 return (-1);
 659                 }
 660         }
 661         if (keys & (F_GNAME | F_GID)) {
 662                 if (acs->gid_list == NULL) {
 663                         acs->gid_list = attr_counter_new(me, NULL);
 664                         if (acs->gid_list == NULL)
 665                                 return (-1);
 666                 } else {
 667                         last = NULL;
 668                         for (ac = acs->gid_list; ac; ac = ac->next) {
 669                                 if (ac->m_entry->gid == me->gid)
 670                                         break;
 671                                 last = ac;
 672                         }
 673                         if (attr_counter_inc(&acs->gid_list, ac, last, me) < 0)
 674                                 return (-1);
 675                 }
 676         }
 677         if (keys & F_MODE) {
 678                 if (acs->mode_list == NULL) {
 679                         acs->mode_list = attr_counter_new(me, NULL);
 680                         if (acs->mode_list == NULL)
 681                                 return (-1);
 682                 } else {
 683                         last = NULL;
 684                         for (ac = acs->mode_list; ac; ac = ac->next) {
 685                                 if (ac->m_entry->mode == me->mode)
 686                                         break;
 687                                 last = ac;
 688                         }
 689                         if (attr_counter_inc(&acs->mode_list, ac, last, me) < 0)
 690                                 return (-1);
 691                 }
 692         }
 693         if (keys & F_FLAGS) {
 694                 if (acs->flags_list == NULL) {
 695                         acs->flags_list = attr_counter_new(me, NULL);
 696                         if (acs->flags_list == NULL)
 697                                 return (-1);
 698                 } else {
 699                         last = NULL;
 700                         for (ac = acs->flags_list; ac; ac = ac->next) {
 701                                 if (ac->m_entry->fflags_set == me->fflags_set &&
 702                                     ac->m_entry->fflags_clear ==
 703                                                         me->fflags_clear)
 704                                         break;
 705                                 last = ac;
 706                         }
 707                         if (attr_counter_inc(&acs->flags_list, ac, last, me) < 0)
 708                                 return (-1);
 709                 }
 710         }
 711
 712         return (0);
 713 }
 714
 715 static void
 716 attr_counter_set_free(struct mtree_writer *mtree)
 717 {
 718         struct att_counter_set *acs = &mtree->acs;
 719
 720         attr_counter_free(&acs->uid_list);
 721         attr_counter_free(&acs->gid_list);
 722         attr_counter_free(&acs->mode_list);
 723         attr_counter_free(&acs->flags_list);
 724 }
 725
 726 static int
 727 get_global_set_keys(struct mtree_writer *mtree, struct mtree_entry *me)
 728 {
 729         int keys;
 730
 731         keys = mtree->keys;
 732
 733         /*
 734          * If a keyword has been set by /set, we do not need to
 735          * output it.
 736          */
 737         if (mtree->set.keys == 0)
 738                 return (keys);/* /set is not used. */
 739
 740         if ((mtree->set.keys & (F_GNAME | F_GID)) != 0 &&
 741              mtree->set.gid == me->gid)
 742                 keys &= ~(F_GNAME | F_GID);
 743         if ((mtree->set.keys & (F_UNAME | F_UID)) != 0 &&
 744              mtree->set.uid == me->uid)
 745                 keys &= ~(F_UNAME | F_UID);
 746         if (mtree->set.keys & F_FLAGS) {
 747                 if (mtree->set.fflags_set == me->fflags_set &&
 748                     mtree->set.fflags_clear == me->fflags_clear)
 749                         keys &= ~F_FLAGS;
 750         }
 751         if ((mtree->set.keys & F_MODE) != 0 && mtree->set.mode == me->mode)
 752                 keys &= ~F_MODE;
 753
 754         switch (me->filetype) {
 755         case AE_IFLNK: case AE_IFSOCK: case AE_IFCHR:
 756         case AE_IFBLK: case AE_IFIFO:
 757                 break;
 758         case AE_IFDIR:
 759                 if ((mtree->set.keys & F_TYPE) != 0 &&
 760                     mtree->set.type == AE_IFDIR)
 761                         keys &= ~F_TYPE;
 762                 break;
 763         case AE_IFREG:
 764         default:        /* Handle unknown file types as regular files. */
 765                 if ((mtree->set.keys & F_TYPE) != 0 &&
 766                     mtree->set.type == AE_IFREG)
 767                         keys &= ~F_TYPE;
 768                 break;
 769         }
 770
 771         return (keys);
 772 }
 773
 774 static int
 775 mtree_entry_new(struct archive_write *a, struct archive_entry *entry,
 776     struct mtree_entry **m_entry)
 777 {
 778         struct mtree_entry *me;
 779         const char *s;
 780         int r;
 781         static const struct archive_rb_tree_ops rb_ops = {
 782                 mtree_entry_cmp_node, mtree_entry_cmp_key
 783         };
 784
 785         me = calloc(1, sizeof(*me));
 786         if (me == NULL) {
 787                 archive_set_error(&a->archive, ENOMEM,
 788                     "Can't allocate memory for a mtree entry");
 789                 *m_entry = NULL;
 790                 return (ARCHIVE_FATAL);
 791         }
 792
 793         r = mtree_entry_setup_filenames(a, me, entry);
 794         if (r < ARCHIVE_WARN) {
 795                 mtree_entry_free(me);
 796                 *m_entry = NULL;
 797                 return (r);
 798         }
 799
 800         if ((s = archive_entry_symlink(entry)) != NULL)
 801                 archive_strcpy(&me->symlink, s);
 802         me->nlink = archive_entry_nlink(entry);
 803         me->filetype = archive_entry_filetype(entry);
 804         me->mode = archive_entry_mode(entry) & 07777;
 805         me->uid = archive_entry_uid(entry);
 806         me->gid = archive_entry_gid(entry);
 807         if ((s = archive_entry_uname(entry)) != NULL)
 808                 archive_strcpy(&me->uname, s);
 809         if ((s = archive_entry_gname(entry)) != NULL)
 810                 archive_strcpy(&me->gname, s);
 811         if ((s = archive_entry_fflags_text(entry)) != NULL)
 812                 archive_strcpy(&me->fflags_text, s);
 813         archive_entry_fflags(entry, &me->fflags_set, &me->fflags_clear);
 814         me->mtime = archive_entry_mtime(entry);
 815         me->mtime_nsec = archive_entry_mtime_nsec(entry);
 816         me->rdevmajor = archive_entry_rdevmajor(entry);
 817         me->rdevminor = archive_entry_rdevminor(entry);
 818         me->devmajor = archive_entry_devmajor(entry);
 819         me->devminor = archive_entry_devminor(entry);
 820         me->ino = archive_entry_ino(entry);
 821         me->size = archive_entry_size(entry);
 822         if (me->filetype == AE_IFDIR) {
 823                 me->dir_info = calloc(1, sizeof(*me->dir_info));
 824                 if (me->dir_info == NULL) {
 825                         mtree_entry_free(me);
 826                         archive_set_error(&a->archive, ENOMEM,
 827                             "Can't allocate memory for a mtree entry");
 828                         *m_entry = NULL;
 829                         return (ARCHIVE_FATAL);
 830                 }
 831                 __archive_rb_tree_init(&me->dir_info->rbtree, &rb_ops);
 832                 me->dir_info->children.first = NULL;
 833                 me->dir_info->children.last = &(me->dir_info->children.first);
 834                 me->dir_info->chnext = NULL;
 835         } else if (me->filetype == AE_IFREG) {
 836                 me->reg_info = calloc(1, sizeof(*me->reg_info));
 837                 if (me->reg_info == NULL) {
 838                         mtree_entry_free(me);
 839                         archive_set_error(&a->archive, ENOMEM,
 840                             "Can't allocate memory for a mtree entry");
 841                         *m_entry = NULL;
 842                         return (ARCHIVE_FATAL);
 843                 }
 844                 me->reg_info->compute_sum = 0;
 845         }
 846
 847         *m_entry = me;
 848         return (ARCHIVE_OK);
 849 }
 850
 851 static void
 852 mtree_entry_free(struct mtree_entry *me)
 853 {
 854         archive_string_free(&me->parentdir);
 855         archive_string_free(&me->basename);
 856         archive_string_free(&me->pathname);
 857         archive_string_free(&me->symlink);
 858         archive_string_free(&me->uname);
 859         archive_string_free(&me->gname);
 860         archive_string_free(&me->fflags_text);
 861         free(me->dir_info);
 862         free(me->reg_info);
 863         free(me);
 864 }
 865
 866 static int
 867 archive_write_mtree_header(struct archive_write *a,
 868     struct archive_entry *entry)
 869 {
 870         struct mtree_writer *mtree= a->format_data;
 871         struct mtree_entry *mtree_entry;
 872         int r, r2;
 873
 874         if (mtree->first) {
 875                 mtree->first = 0;
 876                 archive_strcat(&mtree->buf, "#mtree\n");
 877                 if ((mtree->keys & SET_KEYS) == 0)
 878                         mtree->output_global_set = 0;/* Disabled. */
 879         }
 880
 881         mtree->entry_bytes_remaining = archive_entry_size(entry);
 882
 883         /* While directory only mode, we do not handle non directory files. */
 884         if (mtree->dironly && archive_entry_filetype(entry) != AE_IFDIR)
 885                 return (ARCHIVE_OK);
 886
 887         r2 = mtree_entry_new(a, entry, &mtree_entry);
 888         if (r2 < ARCHIVE_WARN)
 889                 return (r2);
 890         r = mtree_entry_tree_add(a, &mtree_entry);
 891         if (r < ARCHIVE_WARN) {
 892                 mtree_entry_free(mtree_entry);
 893                 return (r);
 894         }
 895         mtree->mtree_entry = mtree_entry;
 896
 897         /* If the current file is a regular file, we have to
 898          * compute the sum of its content.
 899          * Initialize a bunch of checksum context. */
 900         if (mtree_entry->reg_info)
 901                 sum_init(mtree);
 902
 903         return (r2);
 904 }
 905
 906 static int
 907 write_mtree_entry(struct archive_write *a, struct mtree_entry *me)
 908 {
 909         struct mtree_writer *mtree = a->format_data;
 910         struct archive_string *str;
 911         int keys, ret;
 912
 913         if (me->dir_info) {
 914                 if (mtree->classic) {
 915                         /*
 916                          * Output a comment line to describe the full
 917                          * pathname of the entry as mtree utility does
 918                          * while generating classic format.
 919                          */
 920                         if (!mtree->dironly)
 921                                 archive_strappend_char(&mtree->buf, '\n');
 922                         if (me->parentdir.s)
 923                                 archive_string_sprintf(&mtree->buf,
 924                                     "# %s/%s\n",
 925                                     me->parentdir.s, me->basename.s);
 926                         else
 927                                 archive_string_sprintf(&mtree->buf,
 928                                     "# %s\n",
 929                                     me->basename.s);
 930                 }
 931                 if (mtree->output_global_set)
 932                         write_global(mtree);
 933         }
 934         archive_string_empty(&mtree->ebuf);
 935         str = (mtree->indent || mtree->classic)? &mtree->ebuf : &mtree->buf;
 936
 937         if (!mtree->classic && me->parentdir.s) {
 938                 /*
 939                  * If generating format is not classic one(v1), output
 940                  * a full pathname.
 941                  */
 942                 mtree_quote(str, me->parentdir.s);
 943                 archive_strappend_char(str, '/');
 944         }
 945         mtree_quote(str, me->basename.s);
 946
 947         keys = get_global_set_keys(mtree, me);
 948         if ((keys & F_NLINK) != 0 &&
 949             me->nlink != 1 && me->filetype != AE_IFDIR)
 950                 archive_string_sprintf(str, " nlink=%u", me->nlink);
 951
 952         if ((keys & F_GNAME) != 0 && archive_strlen(&me->gname) > 0) {
 953                 archive_strcat(str, " gname=");
 954                 mtree_quote(str, me->gname.s);
 955         }
 956         if ((keys & F_UNAME) != 0 && archive_strlen(&me->uname) > 0) {
 957                 archive_strcat(str, " uname=");
 958                 mtree_quote(str, me->uname.s);
 959         }
 960         if ((keys & F_FLAGS) != 0) {
 961                 if (archive_strlen(&me->fflags_text) > 0) {
 962                         archive_strcat(str, " flags=");
 963                         mtree_quote(str, me->fflags_text.s);
 964                 } else if (mtree->set.processing &&
 965                     (mtree->set.keys & F_FLAGS) != 0)
 966                         /* Overwrite the global parameter. */
 967                         archive_strcat(str, " flags=none");
 968         }
 969         if ((keys & F_TIME) != 0)
 970                 archive_string_sprintf(str, " time=%jd.%jd",
 971                     (intmax_t)me->mtime, (intmax_t)me->mtime_nsec);
 972         if ((keys & F_MODE) != 0)
 973                 archive_string_sprintf(str, " mode=%o", (unsigned int)me->mode);
 974         if ((keys & F_GID) != 0)
 975                 archive_string_sprintf(str, " gid=%jd", (intmax_t)me->gid);
 976         if ((keys & F_UID) != 0)
 977                 archive_string_sprintf(str, " uid=%jd", (intmax_t)me->uid);
 978
 979         if ((keys & F_INO) != 0)
 980                 archive_string_sprintf(str, " inode=%jd", (intmax_t)me->ino);
 981         if ((keys & F_RESDEV) != 0) {
 982                 archive_string_sprintf(str,
 983                     " resdevice=native,%ju,%ju",
 984                     (uintmax_t)me->devmajor,
 985                     (uintmax_t)me->devminor);
 986         }
 987
 988         switch (me->filetype) {
 989         case AE_IFLNK:
 990                 if ((keys & F_TYPE) != 0)
 991                         archive_strcat(str, " type=link");
 992                 if ((keys & F_SLINK) != 0) {
 993                         archive_strcat(str, " link=");
 994                         mtree_quote(str, me->symlink.s);
 995                 }
 996                 break;
 997         case AE_IFSOCK:
 998                 if ((keys & F_TYPE) != 0)
 999                         archive_strcat(str, " type=socket");
1000                 break;
1001         case AE_IFCHR:
1002                 if ((keys & F_TYPE) != 0)
1003                         archive_strcat(str, " type=char");
1004                 if ((keys & F_DEV) != 0) {
1005                         archive_string_sprintf(str,
1006                             " device=native,%ju,%ju",
1007                             (uintmax_t)me->rdevmajor,
1008                             (uintmax_t)me->rdevminor);
1009                 }
1010                 break;
1011         case AE_IFBLK:
1012                 if ((keys & F_TYPE) != 0)
1013                         archive_strcat(str, " type=block");
1014                 if ((keys & F_DEV) != 0) {
1015                         archive_string_sprintf(str,
1016                             " device=native,%ju,%ju",
1017                             (uintmax_t)me->rdevmajor,
1018                             (uintmax_t)me->rdevminor);
1019                 }
1020                 break;
1021         case AE_IFDIR:
1022                 if ((keys & F_TYPE) != 0)
1023                         archive_strcat(str, " type=dir");
1024                 break;
1025         case AE_IFIFO:
1026                 if ((keys & F_TYPE) != 0)
1027                         archive_strcat(str, " type=fifo");
1028                 break;
1029         case AE_IFREG:
1030         default:        /* Handle unknown file types as regular files. */
1031                 if ((keys & F_TYPE) != 0)
1032                         archive_strcat(str, " type=file");
1033                 if ((keys & F_SIZE) != 0)
1034                         archive_string_sprintf(str, " size=%jd",
1035                             (intmax_t)me->size);
1036                 break;
1037         }
1038
1039         /* Write a bunch of sum. */
1040         if (me->reg_info)
1041                 sum_write(str, me->reg_info);
1042
1043         archive_strappend_char(str, '\n');
1044         if (mtree->indent || mtree->classic)
1045                 mtree_indent(mtree);
1046
1047         if (mtree->buf.length > 32768) {
1048                 ret = __archive_write_output(
1049                         a, mtree->buf.s, mtree->buf.length);
1050                 archive_string_empty(&mtree->buf);
1051         } else
1052                 ret = ARCHIVE_OK;
1053         return (ret);
1054 }
1055
1056 static int
1057 write_dot_dot_entry(struct archive_write *a, struct mtree_entry *n)
1058 {
1059         struct mtree_writer *mtree = a->format_data;
1060         int ret;
1061
1062         if (n->parentdir.s) {
1063                 if (mtree->indent) {
1064                         int i, pd = mtree->depth * 4;
1065                         for (i = 0; i < pd; i++)
1066                                 archive_strappend_char(&mtree->buf, ' ');
1067                 }
1068                 archive_string_sprintf(&mtree->buf, "# %s/%s\n",
1069                         n->parentdir.s, n->basename.s);
1070         }
1071
1072         if (mtree->indent) {
1073                 archive_string_empty(&mtree->ebuf);
1074                 archive_strncat(&mtree->ebuf, "..\n\n", (mtree->dironly)?3:4);
1075                 mtree_indent(mtree);
1076         } else
1077                 archive_strncat(&mtree->buf, "..\n\n", (mtree->dironly)?3:4);
1078
1079         if (mtree->buf.length > 32768) {
1080                 ret = __archive_write_output(
1081                         a, mtree->buf.s, mtree->buf.length);
1082                 archive_string_empty(&mtree->buf);
1083         } else
1084                 ret = ARCHIVE_OK;
1085         return (ret);
1086 }
1087
1088 /*
1089  * Write mtree entries saved at attr_counter_set_collect() function.
1090  */
1091 static int
1092 write_mtree_entry_tree(struct archive_write *a)
1093 {
1094         struct mtree_writer *mtree = a->format_data;
1095         struct mtree_entry *np = mtree->root;
1096         struct archive_rb_node *n;
1097         int ret;
1098
1099         do {
1100                 if (mtree->output_global_set) {
1101                         /*
1102                          * Collect attribute information to know which value
1103                          * is frequently used among the children.
1104                          */
1105                         attr_counter_set_reset(mtree);
1106                         ARCHIVE_RB_TREE_FOREACH(n, &(np->dir_info->rbtree)) {
1107                                 struct mtree_entry *e = (struct mtree_entry *)n;
1108                                 if (attr_counter_set_collect(mtree, e) < 0) {
1109                                         archive_set_error(&a->archive, ENOMEM,
1110                                             "Can't allocate memory");
1111                                         return (ARCHIVE_FATAL);
1112                                 }
1113                         }
1114                 }
1115                 if (!np->dir_info->virtual || mtree->classic) {
1116                         ret = write_mtree_entry(a, np);
1117                         if (ret != ARCHIVE_OK)
1118                                 return (ARCHIVE_FATAL);
1119                 } else {
1120                         /* Whenever output_global_set is enabled
1121                          * output global value(/set keywords)
1122                          * even if the directory entry is not allowed
1123                          * to be written because the global values
1124                          * can be used for the children. */
1125                         if (mtree->output_global_set)
1126                                 write_global(mtree);
1127                 }
1128                 /*
1129                  * Output the attribute of all files except directory files.
1130                  */
1131                 mtree->depth++;
1132                 ARCHIVE_RB_TREE_FOREACH(n, &(np->dir_info->rbtree)) {
1133                         struct mtree_entry *e = (struct mtree_entry *)n;
1134
1135                         if (e->dir_info)
1136                                 mtree_entry_add_child_tail(np, e);
1137                         else {
1138                                 ret = write_mtree_entry(a, e);
1139                                 if (ret != ARCHIVE_OK)
1140                                         return (ARCHIVE_FATAL);
1141                         }
1142                 }
1143                 mtree->depth--;
1144
1145                 if (np->dir_info->children.first != NULL) {
1146                         /*
1147                          * Descend the tree.
1148                          */
1149                         np = np->dir_info->children.first;
1150                         if (mtree->indent)
1151                                 mtree->depth++;
1152                         continue;
1153                 } else if (mtree->classic) {
1154                         /*
1155                          * While printing mtree classic, if there are not
1156                          * any directory files(except "." and "..") in the
1157                          * directory, output two dots ".." as returning
1158                          * the parent directory.
1159                          */
1160                         ret = write_dot_dot_entry(a, np);
1161                         if (ret != ARCHIVE_OK)
1162                                 return (ARCHIVE_FATAL);
1163                 }
1164
1165                 while (np != np->parent) {
1166                         if (np->dir_info->chnext == NULL) {
1167                                 /*
1168                                  * Ascend the tree; go back to the parent.
1169                                  */
1170                                 if (mtree->indent)
1171                                         mtree->depth--;
1172                                 if (mtree->classic) {
1173                                         ret = write_dot_dot_entry(a,
1174                                                 np->parent);
1175                                         if (ret != ARCHIVE_OK)
1176                                                 return (ARCHIVE_FATAL);
1177                                 }
1178                                 np = np->parent;
1179                         } else {
1180                                 /*
1181                                  * Switch to next mtree entry in the directory.
1182                                  */
1183                                 np = np->dir_info->chnext;
1184                                 break;
1185                         }
1186                 }
1187         } while (np != np->parent);
1188
1189         return (ARCHIVE_OK);
1190 }
1191
1192 static int
1193 archive_write_mtree_finish_entry(struct archive_write *a)
1194 {
1195         struct mtree_writer *mtree = a->format_data;
1196         struct mtree_entry *me;
1197
1198         if ((me = mtree->mtree_entry) == NULL)
1199                 return (ARCHIVE_OK);
1200         mtree->mtree_entry = NULL;
1201
1202         if (me->reg_info)
1203                 sum_final(mtree, me->reg_info);
1204
1205         return (ARCHIVE_OK);
1206 }
1207
1208 static int
1209 archive_write_mtree_close(struct archive_write *a)
1210 {
1211         struct mtree_writer *mtree= a->format_data;
1212         int ret;
1213
1214         if (mtree->root != NULL) {
1215                 ret = write_mtree_entry_tree(a);
1216                 if (ret != ARCHIVE_OK)
1217                         return (ARCHIVE_FATAL);
1218         }
1219
1220         archive_write_set_bytes_in_last_block(&a->archive, 1);
1221
1222         return __archive_write_output(a, mtree->buf.s, mtree->buf.length);
1223 }
1224
1225 static ssize_t
1226 archive_write_mtree_data(struct archive_write *a, const void *buff, size_t n)
1227 {
1228         struct mtree_writer *mtree= a->format_data;
1229
1230         if (n > mtree->entry_bytes_remaining)
1231                 n = (size_t)mtree->entry_bytes_remaining;
1232         mtree->entry_bytes_remaining -= n;
1233
1234         /* We don't need to compute a regular file sum */
1235         if (mtree->mtree_entry == NULL)
1236                 return (n);
1237
1238         if (mtree->mtree_entry->filetype == AE_IFREG)
1239                 sum_update(mtree, buff, n);
1240
1241         return (n);
1242 }
1243
1244 static int
1245 archive_write_mtree_free(struct archive_write *a)
1246 {
1247         struct mtree_writer *mtree= a->format_data;
1248
1249         if (mtree == NULL)
1250                 return (ARCHIVE_OK);
1251
1252         /* Make sure we do not leave any entries. */
1253         mtree_entry_register_free(mtree);
1254         archive_string_free(&mtree->cur_dirstr);
1255         archive_string_free(&mtree->ebuf);
1256         archive_string_free(&mtree->buf);
1257         attr_counter_set_free(mtree);
1258         free(mtree);
1259         a->format_data = NULL;
1260         return (ARCHIVE_OK);
1261 }
1262
1263 static int
1264 archive_write_mtree_options(struct archive_write *a, const char *key,
1265     const char *value)
1266 {
1267         struct mtree_writer *mtree= a->format_data;
1268         int keybit = 0;
1269
1270         switch (key[0]) {
1271         case 'a':
1272                 if (strcmp(key, "all") == 0)
1273                         keybit = ~0;
1274                 break;
1275         case 'c':
1276                 if (strcmp(key, "cksum") == 0)
1277                         keybit = F_CKSUM;
1278                 break;
1279         case 'd':
1280                 if (strcmp(key, "device") == 0)
1281                         keybit = F_DEV;
1282                 else if (strcmp(key, "dironly") == 0) {
1283                         mtree->dironly = (value != NULL)? 1: 0;
1284                         return (ARCHIVE_OK);
1285                 }
1286                 break;
1287         case 'f':
1288                 if (strcmp(key, "flags") == 0)
1289                         keybit = F_FLAGS;
1290                 break;
1291         case 'g':
1292                 if (strcmp(key, "gid") == 0)
1293                         keybit = F_GID;
1294                 else if (strcmp(key, "gname") == 0)
1295                         keybit = F_GNAME;
1296                 break;
1297         case 'i':
1298                 if (strcmp(key, "indent") == 0) {
1299                         mtree->indent = (value != NULL)? 1: 0;
1300                         return (ARCHIVE_OK);
1301                 } else if (strcmp(key, "inode") == 0) {
1302                         keybit = F_INO;
1303                 }
1304                 break;
1305         case 'l':
1306                 if (strcmp(key, "link") == 0)
1307                         keybit = F_SLINK;
1308                 break;
1309         case 'm':
1310                 if (strcmp(key, "md5") == 0 ||
1311                     strcmp(key, "md5digest") == 0)
1312                         keybit = F_MD5;
1313                 if (strcmp(key, "mode") == 0)
1314                         keybit = F_MODE;
1315                 break;
1316         case 'n':
1317                 if (strcmp(key, "nlink") == 0)
1318                         keybit = F_NLINK;
1319                 break;
1320         case 'r':
1321                 if (strcmp(key, "resdevice") == 0) {
1322                         keybit = F_RESDEV;
1323                 } else if (strcmp(key, "ripemd160digest") == 0 ||
1324                     strcmp(key, "rmd160") == 0 ||
1325                     strcmp(key, "rmd160digest") == 0)
1326                         keybit = F_RMD160;
1327                 break;
1328         case 's':
1329                 if (strcmp(key, "sha1") == 0 ||
1330                     strcmp(key, "sha1digest") == 0)
1331                         keybit = F_SHA1;
1332                 if (strcmp(key, "sha256") == 0 ||
1333                     strcmp(key, "sha256digest") == 0)
1334                         keybit = F_SHA256;
1335                 if (strcmp(key, "sha384") == 0 ||
1336                     strcmp(key, "sha384digest") == 0)
1337                         keybit = F_SHA384;
1338                 if (strcmp(key, "sha512") == 0 ||
1339                     strcmp(key, "sha512digest") == 0)
1340                         keybit = F_SHA512;
1341                 if (strcmp(key, "size") == 0)
1342                         keybit = F_SIZE;
1343                 break;
1344         case 't':
1345                 if (strcmp(key, "time") == 0)
1346                         keybit = F_TIME;
1347                 else if (strcmp(key, "type") == 0)
1348                         keybit = F_TYPE;
1349                 break;
1350         case 'u':
1351                 if (strcmp(key, "uid") == 0)
1352                         keybit = F_UID;
1353                 else if (strcmp(key, "uname") == 0)
1354                         keybit = F_UNAME;
1355                 else if (strcmp(key, "use-set") == 0) {
1356                         mtree->output_global_set = (value != NULL)? 1: 0;
1357                         return (ARCHIVE_OK);
1358                 }
1359                 break;
1360         }
1361         if (keybit != 0) {
1362                 if (value != NULL)
1363                         mtree->keys |= keybit;
1364                 else
1365                         mtree->keys &= ~keybit;
1366                 return (ARCHIVE_OK);
1367         }
1368
1369         /* Note: The "warn" return is just to inform the options
1370          * supervisor that we didn't handle it.  It will generate
1371          * a suitable error if no one used this option. */
1372         return (ARCHIVE_WARN);
1373 }
1374
1375 static int
1376 archive_write_set_format_mtree_default(struct archive *_a, const char *fn)
1377 {
1378         struct archive_write *a = (struct archive_write *)_a;
1379         struct mtree_writer *mtree;
1380
1381         archive_check_magic(_a, ARCHIVE_WRITE_MAGIC, ARCHIVE_STATE_NEW, fn);
1382
1383         if (a->format_free != NULL)
1384                 (a->format_free)(a);
1385
1386         if ((mtree = calloc(1, sizeof(*mtree))) == NULL) {
1387                 archive_set_error(&a->archive, ENOMEM,
1388                     "Can't allocate mtree data");
1389                 return (ARCHIVE_FATAL);
1390         }
1391
1392         mtree->mtree_entry = NULL;
1393         mtree->first = 1;
1394         memset(&(mtree->set), 0, sizeof(mtree->set));
1395         mtree->keys = DEFAULT_KEYS;
1396         mtree->dironly = 0;
1397         mtree->indent = 0;
1398         archive_string_init(&mtree->ebuf);
1399         archive_string_init(&mtree->buf);
1400         mtree_entry_register_init(mtree);
1401         a->format_data = mtree;
1402         a->format_free = archive_write_mtree_free;
1403         a->format_name = "mtree";
1404         a->format_options = archive_write_mtree_options;
1405         a->format_write_header = archive_write_mtree_header;
1406         a->format_close = archive_write_mtree_close;
1407         a->format_write_data = archive_write_mtree_data;
1408         a->format_finish_entry = archive_write_mtree_finish_entry;
1409         a->archive.archive_format = ARCHIVE_FORMAT_MTREE;
1410         a->archive.archive_format_name = "mtree";
1411
1412         return (ARCHIVE_OK);
1413 }
1414
1415 int
1416 archive_write_set_format_mtree(struct archive *_a)
1417 {
1418         return archive_write_set_format_mtree_default(_a,
1419                 "archive_write_set_format_mtree");
1420 }
1421
1422 int
1423 archive_write_set_format_mtree_classic(struct archive *_a)
1424 {
1425         int r;
1426
1427         r = archive_write_set_format_mtree_default(_a,
1428                 "archive_write_set_format_mtree_classic");
1429         if (r == ARCHIVE_OK) {
1430                 struct archive_write *a = (struct archive_write *)_a;
1431                 struct mtree_writer *mtree;
1432
1433                 mtree = (struct mtree_writer *)a->format_data;
1434
1435                 /* Set to output a mtree archive in classic format. */
1436                 mtree->classic = 1;
1437                 /* Basically, mtree classic format uses '/set' global
1438                  * value. */
1439                 mtree->output_global_set = 1;
1440         }
1441         return (r);
1442 }
1443
1444 static void
1445 sum_init(struct mtree_writer *mtree)
1446 {
1447
1448         mtree->compute_sum = 0;
1449
1450         if (mtree->keys & F_CKSUM) {
1451                 mtree->compute_sum |= F_CKSUM;
1452                 mtree->crc = 0;
1453                 mtree->crc_len = 0;
1454         }
1455 #ifdef ARCHIVE_HAS_MD5
1456         if (mtree->keys & F_MD5) {
1457                 if (archive_md5_init(&mtree->md5ctx) == ARCHIVE_OK)
1458                         mtree->compute_sum |= F_MD5;
1459                 else
1460                         mtree->keys &= ~F_MD5;/* Not supported. */
1461         }
1462 #endif
1463 #ifdef ARCHIVE_HAS_RMD160
1464         if (mtree->keys & F_RMD160) {
1465                 if (archive_rmd160_init(&mtree->rmd160ctx) == ARCHIVE_OK)
1466                         mtree->compute_sum |= F_RMD160;
1467                 else
1468                         mtree->keys &= ~F_RMD160;/* Not supported. */
1469         }
1470 #endif
1471 #ifdef ARCHIVE_HAS_SHA1
1472         if (mtree->keys & F_SHA1) {
1473                 if (archive_sha1_init(&mtree->sha1ctx) == ARCHIVE_OK)
1474                         mtree->compute_sum |= F_SHA1;
1475                 else
1476                         mtree->keys &= ~F_SHA1;/* Not supported. */
1477         }
1478 #endif
1479 #ifdef ARCHIVE_HAS_SHA256
1480         if (mtree->keys & F_SHA256) {
1481                 if (archive_sha256_init(&mtree->sha256ctx) == ARCHIVE_OK)
1482                         mtree->compute_sum |= F_SHA256;
1483                 else
1484                         mtree->keys &= ~F_SHA256;/* Not supported. */
1485         }
1486 #endif
1487 #ifdef ARCHIVE_HAS_SHA384
1488         if (mtree->keys & F_SHA384) {
1489                 if (archive_sha384_init(&mtree->sha384ctx) == ARCHIVE_OK)
1490                         mtree->compute_sum |= F_SHA384;
1491                 else
1492                         mtree->keys &= ~F_SHA384;/* Not supported. */
1493         }
1494 #endif
1495 #ifdef ARCHIVE_HAS_SHA512
1496         if (mtree->keys & F_SHA512) {
1497                 if (archive_sha512_init(&mtree->sha512ctx) == ARCHIVE_OK)
1498                         mtree->compute_sum |= F_SHA512;
1499                 else
1500                         mtree->keys &= ~F_SHA512;/* Not supported. */
1501         }
1502 #endif
1503 }
1504
1505 static void
1506 sum_update(struct mtree_writer *mtree, const void *buff, size_t n)
1507 {
1508         if (mtree->compute_sum & F_CKSUM) {
1509                 /*
1510                  * Compute a POSIX 1003.2 checksum
1511                  */
1512                 const unsigned char *p;
1513                 size_t nn;
1514
1515                 for (nn = n, p = buff; nn--; ++p)
1516                         COMPUTE_CRC(mtree->crc, *p);
1517                 mtree->crc_len += n;
1518         }
1519 #ifdef ARCHIVE_HAS_MD5
1520         if (mtree->compute_sum & F_MD5)
1521                 archive_md5_update(&mtree->md5ctx, buff, n);
1522 #endif
1523 #ifdef ARCHIVE_HAS_RMD160
1524         if (mtree->compute_sum & F_RMD160)
1525                 archive_rmd160_update(&mtree->rmd160ctx, buff, n);
1526 #endif
1527 #ifdef ARCHIVE_HAS_SHA1
1528         if (mtree->compute_sum & F_SHA1)
1529                 archive_sha1_update(&mtree->sha1ctx, buff, n);
1530 #endif
1531 #ifdef ARCHIVE_HAS_SHA256
1532         if (mtree->compute_sum & F_SHA256)
1533                 archive_sha256_update(&mtree->sha256ctx, buff, n);
1534 #endif
1535 #ifdef ARCHIVE_HAS_SHA384
1536         if (mtree->compute_sum & F_SHA384)
1537                 archive_sha384_update(&mtree->sha384ctx, buff, n);
1538 #endif
1539 #ifdef ARCHIVE_HAS_SHA512
1540         if (mtree->compute_sum & F_SHA512)
1541                 archive_sha512_update(&mtree->sha512ctx, buff, n);
1542 #endif
1543 }
1544
1545 static void
1546 sum_final(struct mtree_writer *mtree, struct reg_info *reg)
1547 {
1548
1549         if (mtree->compute_sum & F_CKSUM) {
1550                 uint64_t len;
1551                 /* Include the length of the file. */
1552                 for (len = mtree->crc_len; len != 0; len >>= 8)
1553                         COMPUTE_CRC(mtree->crc, len & 0xff);
1554                 reg->crc = ~mtree->crc;
1555         }
1556 #ifdef ARCHIVE_HAS_MD5
1557         if (mtree->compute_sum & F_MD5)
1558                 archive_md5_final(&mtree->md5ctx, reg->digest.md5);
1559 #endif
1560 #ifdef ARCHIVE_HAS_RMD160
1561         if (mtree->compute_sum & F_RMD160)
1562                 archive_rmd160_final(&mtree->rmd160ctx, reg->digest.rmd160);
1563 #endif
1564 #ifdef ARCHIVE_HAS_SHA1
1565         if (mtree->compute_sum & F_SHA1)
1566                 archive_sha1_final(&mtree->sha1ctx, reg->digest.sha1);
1567 #endif
1568 #ifdef ARCHIVE_HAS_SHA256
1569         if (mtree->compute_sum & F_SHA256)
1570                 archive_sha256_final(&mtree->sha256ctx, reg->digest.sha256);
1571 #endif
1572 #ifdef ARCHIVE_HAS_SHA384
1573         if (mtree->compute_sum & F_SHA384)
1574                 archive_sha384_final(&mtree->sha384ctx, reg->digest.sha384);
1575 #endif
1576 #ifdef ARCHIVE_HAS_SHA512
1577         if (mtree->compute_sum & F_SHA512)
1578                 archive_sha512_final(&mtree->sha512ctx, reg->digest.sha512);
1579 #endif
1580         /* Save what types of sum are computed. */
1581         reg->compute_sum = mtree->compute_sum;
1582 }
1583
1584 #if defined(ARCHIVE_HAS_MD5) || defined(ARCHIVE_HAS_RMD160) || \
1585     defined(ARCHIVE_HAS_SHA1) || defined(ARCHIVE_HAS_SHA256) || \
1586     defined(ARCHIVE_HAS_SHA384) || defined(ARCHIVE_HAS_SHA512)
1587 static void
1588 strappend_bin(struct archive_string *s, const unsigned char *bin, int n)
1589 {
1590         static const char hex[] = "0123456789abcdef";
1591         int i;
1592
1593         for (i = 0; i < n; i++) {
1594                 archive_strappend_char(s, hex[bin[i] >> 4]);
1595                 archive_strappend_char(s, hex[bin[i] & 0x0f]);
1596         }
1597 }
1598 #endif
1599
1600 static void
1601 sum_write(struct archive_string *str, struct reg_info *reg)
1602 {
1603
1604         if (reg->compute_sum & F_CKSUM) {
1605                 archive_string_sprintf(str, " cksum=%ju",
1606                     (uintmax_t)reg->crc);
1607         }
1608
1609 #define append_digest(_s, _r, _t) \
1610         strappend_bin(_s, _r->digest._t, sizeof(_r->digest._t))
1611
1612 #ifdef ARCHIVE_HAS_MD5
1613         if (reg->compute_sum & F_MD5) {
1614                 archive_strcat(str, " md5digest=");
1615                 append_digest(str, reg, md5);
1616         }
1617 #endif
1618 #ifdef ARCHIVE_HAS_RMD160
1619         if (reg->compute_sum & F_RMD160) {
1620                 archive_strcat(str, " rmd160digest=");
1621                 append_digest(str, reg, rmd160);
1622         }
1623 #endif
1624 #ifdef ARCHIVE_HAS_SHA1
1625         if (reg->compute_sum & F_SHA1) {
1626                 archive_strcat(str, " sha1digest=");
1627                 append_digest(str, reg, sha1);
1628         }
1629 #endif
1630 #ifdef ARCHIVE_HAS_SHA256
1631         if (reg->compute_sum & F_SHA256) {
1632                 archive_strcat(str, " sha256digest=");
1633                 append_digest(str, reg, sha256);
1634         }
1635 #endif
1636 #ifdef ARCHIVE_HAS_SHA384
1637         if (reg->compute_sum & F_SHA384) {
1638                 archive_strcat(str, " sha384digest=");
1639                 append_digest(str, reg, sha384);
1640         }
1641 #endif
1642 #ifdef ARCHIVE_HAS_SHA512
1643         if (reg->compute_sum & F_SHA512) {
1644                 archive_strcat(str, " sha512digest=");
1645                 append_digest(str, reg, sha512);
1646         }
1647 #endif
1648 #undef append_digest
1649 }
1650
1651 static int
1652 mtree_entry_cmp_node(const struct archive_rb_node *n1,
1653     const struct archive_rb_node *n2)
1654 {
1655         const struct mtree_entry *e1 = (const struct mtree_entry *)n1;
1656         const struct mtree_entry *e2 = (const struct mtree_entry *)n2;
1657
1658         return (strcmp(e2->basename.s, e1->basename.s));
1659 }
1660
1661 static int
1662 mtree_entry_cmp_key(const struct archive_rb_node *n, const void *key)
1663 {
1664         const struct mtree_entry *e = (const struct mtree_entry *)n;
1665
1666         return (strcmp((const char *)key, e->basename.s));
1667 }
1668
1669 #if defined(_WIN32) || defined(__CYGWIN__)
1670 static int
1671 cleanup_backslash_1(char *p)
1672 {
1673         int mb, dos;
1674
1675         mb = dos = 0;
1676         while (*p) {
1677                 if (*(unsigned char *)p > 127)
1678                         mb = 1;
1679                 if (*p == '\\') {
1680                         /* If we have not met any multi-byte characters,
1681                          * we can replace '\' with '/'. */
1682                         if (!mb)
1683                                 *p = '/';
1684                         dos = 1;
1685                 }
1686                 p++;
1687         }
1688         if (!mb || !dos)
1689                 return (0);
1690         return (-1);
1691 }
1692
1693 static void
1694 cleanup_backslash_2(wchar_t *p)
1695 {
1696
1697         /* Convert a path-separator from '\' to  '/' */
1698         while (*p != L'\0') {
1699                 if (*p == L'\\')
1700                         *p = L'/';
1701                 p++;
1702         }
1703 }
1704 #endif
1705
1706 /*
1707  * Generate a parent directory name and a base name from a pathname.
1708  */
1709 static int
1710 mtree_entry_setup_filenames(struct archive_write *a, struct mtree_entry *file,
1711     struct archive_entry *entry)
1712 {
1713         const char *pathname;
1714         char *p, *dirname, *slash;
1715         size_t len;
1716         int ret = ARCHIVE_OK;
1717
1718         archive_strcpy(&file->pathname, archive_entry_pathname(entry));
1719 #if defined(_WIN32) || defined(__CYGWIN__)
1720         /*
1721          * Convert a path-separator from '\' to  '/'
1722          */
1723         if (cleanup_backslash_1(file->pathname.s) != 0) {
1724                 const wchar_t *wp = archive_entry_pathname_w(entry);
1725                 struct archive_wstring ws;
1726
1727                 if (wp != NULL) {
1728                         int r;
1729                         archive_string_init(&ws);
1730                         archive_wstrcpy(&ws, wp);
1731                         cleanup_backslash_2(ws.s);
1732                         archive_string_empty(&(file->pathname));
1733                         r = archive_string_append_from_wcs(&(file->pathname),
1734                             ws.s, ws.length);
1735                         archive_wstring_free(&ws);
1736                         if (r < 0 && errno == ENOMEM) {
1737                                 archive_set_error(&a->archive, ENOMEM,
1738                                     "Can't allocate memory");
1739                                 return (ARCHIVE_FATAL);
1740                         }
1741                 }
1742         }
1743 #else
1744         (void)a; /* UNUSED */
1745 #endif
1746         pathname =  file->pathname.s;
1747         if (strcmp(pathname, ".") == 0) {
1748                 archive_strcpy(&file->basename, ".");
1749                 return (ARCHIVE_OK);
1750         }
1751
1752         archive_strcpy(&(file->parentdir), pathname);
1753
1754         len = file->parentdir.length;
1755         p = dirname = file->parentdir.s;
1756
1757         /*
1758          * Remove leading '/' and '../' elements
1759          */
1760         while (*p) {
1761                 if (p[0] == '/') {
1762                         p++;
1763                         len--;
1764                 } else if (p[0] != '.')
1765                         break;
1766                 else if (p[1] == '.' && p[2] == '/') {
1767                         p += 3;
1768                         len -= 3;
1769                 } else
1770                         break;
1771         }
1772         if (p != dirname) {
1773                 memmove(dirname, p, len+1);
1774                 p = dirname;
1775         }
1776         /*
1777          * Remove "/","/." and "/.." elements from tail.
1778          */
1779         while (len > 0) {
1780                 size_t ll = len;
1781
1782                 if (len > 0 && p[len-1] == '/') {
1783                         p[len-1] = '\0';
1784                         len--;
1785                 }
1786                 if (len > 1 && p[len-2] == '/' && p[len-1] == '.') {
1787                         p[len-2] = '\0';
1788                         len -= 2;
1789                 }
1790                 if (len > 2 && p[len-3] == '/' && p[len-2] == '.' &&
1791                     p[len-1] == '.') {
1792                         p[len-3] = '\0';
1793                         len -= 3;
1794                 }
1795                 if (ll == len)
1796                         break;
1797         }
1798         while (*p) {
1799                 if (p[0] == '/') {
1800                         if (p[1] == '/')
1801                                 /* Convert '//' --> '/' */
1802                                 strcpy(p, p+1);
1803                         else if (p[1] == '.' && p[2] == '/')
1804                                 /* Convert '/./' --> '/' */
1805                                 strcpy(p, p+2);
1806                         else if (p[1] == '.' && p[2] == '.' && p[3] == '/') {
1807                                 /* Convert 'dir/dir1/../dir2/'
1808                                  *     --> 'dir/dir2/'
1809                                  */
1810                                 char *rp = p -1;
1811                                 while (rp >= dirname) {
1812                                         if (*rp == '/')
1813                                                 break;
1814                                         --rp;
1815                                 }
1816                                 if (rp > dirname) {
1817                                         strcpy(rp, p+3);
1818                                         p = rp;
1819                                 } else {
1820                                         strcpy(dirname, p+4);
1821                                         p = dirname;
1822                                 }
1823                         } else
1824                                 p++;
1825                 } else
1826                         p++;
1827         }
1828         p = dirname;
1829         len = strlen(p);
1830
1831         /*
1832          * Add "./" prefix.
1833          * NOTE: If the pathname does not have a path separator, we have
1834          * to add "./" to the head of the pathname because mtree reader
1835          * will suppose that it is v1(a.k.a classic) mtree format and
1836          * change the directory unexpectedly and so it will make a wrong
1837          * path.
1838          */
1839         if (strcmp(p, ".") != 0 && strncmp(p, "./", 2) != 0) {
1840                 struct archive_string as;
1841                 archive_string_init(&as);
1842                 archive_strcpy(&as, "./");
1843                 archive_strncat(&as, p, len);
1844                 archive_string_empty(&file->parentdir);
1845                 archive_string_concat(&file->parentdir, &as);
1846                 archive_string_free(&as);
1847                 p = file->parentdir.s;
1848                 len = archive_strlen(&file->parentdir);
1849         }
1850
1851         /*
1852          * Find out the position which points the last position of
1853          * path separator('/').
1854          */
1855         slash = NULL;
1856         for (; *p != '\0'; p++) {
1857                 if (*p == '/')
1858                         slash = p;
1859         }
1860         if (slash == NULL) {
1861                 /* The pathname doesn't have a parent directory. */
1862                 file->parentdir.length = len;
1863                 archive_string_copy(&(file->basename), &(file->parentdir));
1864                 archive_string_empty(&(file->parentdir));
1865                 *file->parentdir.s = '\0';
1866                 return (ret);
1867         }
1868
1869         /* Make a basename from file->parentdir.s and slash */
1870         *slash  = '\0';
1871         file->parentdir.length = slash - file->parentdir.s;
1872         archive_strcpy(&(file->basename),  slash + 1);
1873         return (ret);
1874 }
1875
1876 static int
1877 mtree_entry_create_virtual_dir(struct archive_write *a, const char *pathname,
1878     struct mtree_entry **m_entry)
1879 {
1880         struct archive_entry *entry;
1881         struct mtree_entry *file;
1882         int r;
1883
1884         entry = archive_entry_new();
1885         if (entry == NULL) {
1886                 *m_entry = NULL;
1887                 archive_set_error(&a->archive, ENOMEM,
1888                     "Can't allocate memory");
1889                 return (ARCHIVE_FATAL);
1890         }
1891         archive_entry_copy_pathname(entry, pathname);
1892         archive_entry_set_mode(entry, AE_IFDIR | 0755);
1893         archive_entry_set_mtime(entry, time(NULL), 0);
1894
1895         r = mtree_entry_new(a, entry, &file);
1896         archive_entry_free(entry);
1897         if (r < ARCHIVE_WARN) {
1898                 *m_entry = NULL;
1899                 archive_set_error(&a->archive, ENOMEM,
1900                     "Can't allocate memory");
1901                 return (ARCHIVE_FATAL);
1902         }
1903
1904         file->dir_info->virtual = 1;
1905
1906         *m_entry = file;
1907         return (ARCHIVE_OK);
1908 }
1909
1910 static void
1911 mtree_entry_register_add(struct mtree_writer *mtree, struct mtree_entry *file)
1912 {
1913         file->next = NULL;
1914         *mtree->file_list.last = file;
1915         mtree->file_list.last = &(file->next);
1916 }
1917
1918 static void
1919 mtree_entry_register_init(struct mtree_writer *mtree)
1920 {
1921         mtree->file_list.first = NULL;
1922         mtree->file_list.last = &(mtree->file_list.first);
1923 }
1924
1925 static void
1926 mtree_entry_register_free(struct mtree_writer *mtree)
1927 {
1928         struct mtree_entry *file, *file_next;
1929
1930         file = mtree->file_list.first;
1931         while (file != NULL) {
1932                 file_next = file->next;
1933                 mtree_entry_free(file);
1934                 file = file_next;
1935         }
1936 }
1937
1938 static int
1939 mtree_entry_add_child_tail(struct mtree_entry *parent,
1940     struct mtree_entry *child)
1941 {
1942         child->dir_info->chnext = NULL;
1943         *parent->dir_info->children.last = child;
1944         parent->dir_info->children.last = &(child->dir_info->chnext);
1945         return (1);
1946 }
1947
1948 /*
1949  * Find a entry from a parent entry with the name.
1950  */
1951 static struct mtree_entry *
1952 mtree_entry_find_child(struct mtree_entry *parent, const char *child_name)
1953 {
1954         struct mtree_entry *np;
1955
1956         if (parent == NULL)
1957                 return (NULL);
1958         np = (struct mtree_entry *)__archive_rb_tree_find_node(
1959             &(parent->dir_info->rbtree), child_name);
1960         return (np);
1961 }
1962
1963 static int
1964 get_path_component(char *name, size_t n, const char *fn)
1965 {
1966         char *p;
1967         size_t l;
1968
1969         p = strchr(fn, '/');
1970         if (p == NULL) {
1971                 if ((l = strlen(fn)) == 0)
1972                         return (0);
1973         } else
1974                 l = p - fn;
1975         if (l > n -1)
1976                 return (-1);
1977         memcpy(name, fn, l);
1978         name[l] = '\0';
1979
1980         return ((int)l);
1981 }
1982
1983 /*
1984  * Add a new entry into the tree.
1985  */
1986 static int
1987 mtree_entry_tree_add(struct archive_write *a, struct mtree_entry **filep)
1988 {
1989 #if defined(_WIN32) && !defined(__CYGWIN__)
1990         char name[_MAX_FNAME];/* Included null terminator size. */
1991 #elif defined(NAME_MAX) && NAME_MAX >= 255
1992         char name[NAME_MAX+1];
1993 #else
1994         char name[256];
1995 #endif
1996         struct mtree_writer *mtree = (struct mtree_writer *)a->format_data;
1997         struct mtree_entry *dent, *file, *np;
1998         const char *fn, *p;
1999         int l, r;
2000
2001         file = *filep;
2002         if (file->parentdir.length == 0 && file->basename.length == 1 &&
2003             file->basename.s[0] == '.') {
2004                 file->parent = file;
2005                 if (mtree->root != NULL) {
2006                         np = mtree->root;
2007                         goto same_entry;
2008                 }
2009                 mtree->root = file;
2010                 mtree_entry_register_add(mtree, file);
2011                 return (ARCHIVE_OK);
2012         }
2013
2014         if (file->parentdir.length == 0) {
2015                 archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC,
2016                     "Internal programming error "
2017                     "in generating canonical name for %s",
2018                     file->pathname.s);
2019                 return (ARCHIVE_FAILED);
2020         }
2021
2022         fn = p = file->parentdir.s;
2023
2024         /*
2025          * If the path of the parent directory of `file' entry is
2026          * the same as the path of `cur_dirent', add `file' entry to
2027          * `cur_dirent'.
2028          */
2029         if (archive_strlen(&(mtree->cur_dirstr))
2030               == archive_strlen(&(file->parentdir)) &&
2031             strcmp(mtree->cur_dirstr.s, fn) == 0) {
2032                 if (!__archive_rb_tree_insert_node(
2033                     &(mtree->cur_dirent->dir_info->rbtree),
2034                     (struct archive_rb_node *)file)) {
2035                         /* There is the same name in the tree. */
2036                         np = (struct mtree_entry *)__archive_rb_tree_find_node(
2037                             &(mtree->cur_dirent->dir_info->rbtree),
2038                             file->basename.s);
2039                         goto same_entry;
2040                 }
2041                 file->parent = mtree->cur_dirent;
2042                 mtree_entry_register_add(mtree, file);
2043                 return (ARCHIVE_OK);
2044         }
2045
2046         dent = mtree->root;
2047         for (;;) {
2048                 l = get_path_component(name, sizeof(name), fn);
2049                 if (l == 0) {
2050                         np = NULL;
2051                         break;
2052                 }
2053                 if (l < 0) {
2054                         archive_set_error(&a->archive,
2055                             ARCHIVE_ERRNO_MISC,
2056                             "A name buffer is too small");
2057                         return (ARCHIVE_FATAL);
2058                 }
2059                 if (l == 1 && name[0] == '.' && dent != NULL &&
2060                     dent == mtree->root) {
2061                         fn += l;
2062                         if (fn[0] == '/')
2063                                 fn++;
2064                         continue;
2065                 }
2066
2067                 np = mtree_entry_find_child(dent, name);
2068                 if (np == NULL || fn[0] == '\0')
2069                         break;
2070
2071                 /* Find next sub directory. */
2072                 if (!np->dir_info) {
2073                         /* NOT Directory! */
2074                         archive_set_error(&a->archive,
2075                             ARCHIVE_ERRNO_MISC,
2076                             "`%s' is not directory, we cannot insert `%s' ",
2077                             np->pathname.s, file->pathname.s);
2078                         return (ARCHIVE_FAILED);
2079                 }
2080                 fn += l;
2081                 if (fn[0] == '/')
2082                         fn++;
2083                 dent = np;
2084         }
2085         if (np == NULL) {
2086                 /*
2087                  * Create virtual parent directories.
2088                  */
2089                 while (fn[0] != '\0') {
2090                         struct mtree_entry *vp;
2091                         struct archive_string as;
2092
2093                         archive_string_init(&as);
2094                         archive_strncat(&as, p, fn - p + l);
2095                         if (as.s[as.length-1] == '/') {
2096                                 as.s[as.length-1] = '\0';
2097                                 as.length--;
2098                         }
2099                         r = mtree_entry_create_virtual_dir(a, as.s, &vp);
2100                         archive_string_free(&as);
2101                         if (r < ARCHIVE_WARN)
2102                                 return (r);
2103
2104                         if (strcmp(vp->pathname.s, ".") == 0) {
2105                                 vp->parent = vp;
2106                                 mtree->root = vp;
2107                         } else {
2108                                 __archive_rb_tree_insert_node(
2109                                     &(dent->dir_info->rbtree),
2110                                     (struct archive_rb_node *)vp);
2111                                 vp->parent = dent;
2112                         }
2113                         mtree_entry_register_add(mtree, vp);
2114                         np = vp;
2115
2116                         fn += l;
2117                         if (fn[0] == '/')
2118                                 fn++;
2119                         l = get_path_component(name, sizeof(name), fn);
2120                         if (l < 0) {
2121                                 archive_string_free(&as);
2122                                 archive_set_error(&a->archive,
2123                                     ARCHIVE_ERRNO_MISC,
2124                                     "A name buffer is too small");
2125                                 return (ARCHIVE_FATAL);
2126                         }
2127                         dent = np;
2128                 }
2129
2130                 /* Found out the parent directory where `file' can be
2131                  * inserted. */
2132                 mtree->cur_dirent = dent;
2133                 archive_string_empty(&(mtree->cur_dirstr));
2134                 archive_string_ensure(&(mtree->cur_dirstr),
2135                     archive_strlen(&(dent->parentdir)) +
2136                     archive_strlen(&(dent->basename)) + 2);
2137                 if (archive_strlen(&(dent->parentdir)) +
2138                     archive_strlen(&(dent->basename)) == 0)
2139                         mtree->cur_dirstr.s[0] = 0;
2140                 else {
2141                         if (archive_strlen(&(dent->parentdir)) > 0) {
2142                                 archive_string_copy(&(mtree->cur_dirstr),
2143                                     &(dent->parentdir));
2144                                 archive_strappend_char(
2145                                     &(mtree->cur_dirstr), '/');
2146                         }
2147                         archive_string_concat(&(mtree->cur_dirstr),
2148                             &(dent->basename));
2149                 }
2150
2151                 if (!__archive_rb_tree_insert_node(
2152                     &(dent->dir_info->rbtree),
2153                     (struct archive_rb_node *)file)) {
2154                         np = (struct mtree_entry *)__archive_rb_tree_find_node(
2155                             &(dent->dir_info->rbtree), file->basename.s);
2156                         goto same_entry;
2157                 }
2158                 file->parent = dent;
2159                 mtree_entry_register_add(mtree, file);
2160                 return (ARCHIVE_OK);
2161         }
2162
2163 same_entry:
2164         /*
2165          * We have already has the entry the filename of which is
2166          * the same.
2167          */
2168         r = mtree_entry_exchange_same_entry(a, np, file);
2169         if (r < ARCHIVE_WARN)
2170                 return (r);
2171         if (np->dir_info)
2172                 np->dir_info->virtual = 0;
2173         *filep = np;
2174         mtree_entry_free(file);
2175         return (ARCHIVE_WARN);
2176 }
2177
2178 static int
2179 mtree_entry_exchange_same_entry(struct archive_write *a, struct mtree_entry *np,
2180     struct mtree_entry *file)
2181 {
2182
2183         if ((np->mode & AE_IFMT) != (file->mode & AE_IFMT)) {
2184                 archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC,
2185                     "Found duplicate entries `%s' and its file type is "
2186                     "different",
2187                     np->pathname.s);
2188                 return (ARCHIVE_FAILED);
2189         }
2190
2191         /* Update the existent mtree entry's attributes by the new one's. */
2192         archive_string_empty(&np->symlink);
2193         archive_string_concat(&np->symlink, &file->symlink);
2194         archive_string_empty(&np->uname);
2195         archive_string_concat(&np->uname, &file->uname);
2196         archive_string_empty(&np->gname);
2197         archive_string_concat(&np->gname, &file->gname);
2198         archive_string_empty(&np->fflags_text);
2199         archive_string_concat(&np->fflags_text, &file->fflags_text);
2200         np->nlink = file->nlink;
2201         np->filetype = file->filetype;
2202         np->mode = file->mode;
2203         np->size = file->size;
2204         np->uid = file->uid;
2205         np->gid = file->gid;
2206         np->fflags_set = file->fflags_set;
2207         np->fflags_clear = file->fflags_clear;
2208         np->mtime = file->mtime;
2209         np->mtime_nsec = file->mtime_nsec;
2210         np->rdevmajor = file->rdevmajor;
2211         np->rdevminor = file->rdevminor;
2212         np->devmajor = file->devmajor;
2213         np->devminor = file->devminor;
2214         np->ino = file->ino;
2215
2216         return (ARCHIVE_WARN);
2217 }