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