libisofs-legacy/libisofs/ecma119_tree.c

542 lines
14 KiB
C
Raw Permalink Normal View History

2006-08-24 19:24:38 +00:00
/* vim: set noet ts=8 sts=8 sw=8 : */
#include <string.h>
#include <wchar.h>
#include <stdlib.h>
#include <assert.h>
#include "ecma119.h"
#include "ecma119_tree.h"
#include "tree.h"
#include "util.h"
2007-06-05 22:01:26 +00:00
#include "eltorito.h"
2006-08-24 19:24:38 +00:00
static size_t calc_dirent_len(struct ecma119_tree_node *n)
{
int ret = n->iso_name ? strlen(n->iso_name) + 33 : 34;
2006-08-24 19:24:38 +00:00
if (ret % 2) ret++;
return ret;
}
static void
replace_node_mode(struct ecma119_write_target *t, struct stat *st)
{
if ( S_ISDIR(st->st_mode) ) {
if ( t->replace_mode & 0x02 ) {
/* replace dir mode with specific */
st->st_mode &= S_IFMT;
st->st_mode |= t->dir_mode;
} else if (t->replace_mode & 0x01) {
/* replace dir mode with default */
/* read perm */
mode_t new_mode = (st->st_mode & S_IFMT) | 0444;
/* search bit if any */
if ( st->st_mode & 0111)
new_mode |= 0111;
st->st_mode = new_mode;
}
} else {
if ( t->replace_mode & 0x04 ) {
/* replace file mode with specific */
st->st_mode &= S_IFMT;
st->st_mode |= t->file_mode;
} else if (t->replace_mode & 0x01) {
/* replace file mode with default */
/* read perm */
mode_t new_mode = (st->st_mode & S_IFMT) | 0444;
/* execute bit if any */
if ( st->st_mode & 0111)
new_mode |= 0111;
st->st_mode = new_mode;
}
}
if ( t->replace_mode & 0x08 ) {
/* replace gid mode with specific */
st->st_gid = t->gid;
} else if (t->replace_mode & 0x01) {
st->st_gid = 0;
}
if ( t->replace_mode & 0x10 ) {
/* replace gid mode with specific */
st->st_uid = t->uid;
} else if (t->replace_mode & 0x01) {
st->st_uid = 0;
}
}
2006-08-24 19:24:38 +00:00
static struct ecma119_tree_node*
create_ecma119_node(struct ecma119_write_target *t,
struct ecma119_tree_node *parent,
struct iso_tree_node *iso)
2006-08-24 19:24:38 +00:00
{
struct ecma119_tree_node *ret;
char *(*iso_name)(const char *, const char *) = ISO_ISDIR(iso) ?
((t->iso_level == 1) ? iso_1_dirid : iso_2_dirid)
: ((t->iso_level == 1) ? iso_1_fileid : iso_2_fileid);
char *(*iso_r_name)(const char *, const char *, int) =
ISO_ISDIR(iso) ? iso_r_dirid : iso_r_fileid;
2006-08-24 19:24:38 +00:00
assert(t && (!parent || parent->type == ECMA119_DIR) && iso );
2006-08-24 19:24:38 +00:00
ret = calloc(1, sizeof(struct ecma119_tree_node));
/*
* If selected one ISO relaxed constraints other than NO_DIR_REALOCATION,
* we use the function that computes the relaxed name, otherwise normal
* function for specified level is used.
*/
ret->iso_name = iso->name ?
( t->relaxed_constraints & ~ECMA119_NO_DIR_REALOCATION ?
iso_r_name(iso->name, t->input_charset, t->relaxed_constraints) :
iso_name(iso->name, t->input_charset)
) : NULL;
2006-08-24 19:24:38 +00:00
ret->dirent_len = calc_dirent_len(ret);
ret->attrib = iso->attrib;
if ( t->rockridge && t->replace_mode )
replace_node_mode(t, &ret->attrib);
if (!iso->name)
ret->full_name = NULL;
else if ( strcmp(t->input_charset,t->ouput_charset) )
ret->full_name = convert_str(iso->name, t->input_charset,
t->ouput_charset);
else
ret->full_name = strdup(iso->name);
2006-08-24 19:24:38 +00:00
ret->target = t;
ret->parent = parent;
return ret;
}
static struct ecma119_tree_node*
create_dir(struct ecma119_write_target *t,
struct ecma119_tree_node *parent,
struct iso_tree_node_dir *iso)
{
struct ecma119_tree_node *ret;
assert(t && (!parent || parent->type == ECMA119_DIR)
&& iso && S_ISDIR(iso->node.attrib.st_mode));
ret = create_ecma119_node(t, parent, (struct iso_tree_node*) iso);
2006-08-24 19:24:38 +00:00
ret->type = ECMA119_DIR;
ret->info.dir.real_parent = parent;
ret->info.dir.depth = parent ? parent->info.dir.depth + 1 : 1;
ret->info.dir.nchildren = 0;
ret->info.dir.children = calloc(1, sizeof(void*) * iso->nchildren);
2006-08-24 19:24:38 +00:00
return ret;
}
static struct ecma119_tree_node*
create_file(struct ecma119_write_target *t,
struct ecma119_tree_node *parent,
struct iso_tree_node_file *iso)
2006-08-24 19:24:38 +00:00
{
struct ecma119_tree_node *ret;
struct iso_file *file;
2006-08-24 19:24:38 +00:00
assert(t && iso && parent && parent->type == ECMA119_DIR);
ret = create_ecma119_node(t, parent, (struct iso_tree_node*) iso);
ret->type = ECMA119_FILE;
/* get iso_file struct */
file = iso_file_table_lookup(t->file_table, iso);
if ( file == NULL ) {
file = iso_file_new(iso);
iso_file_table_add_file(t->file_table, file);
file->ino = ++t->ino;
} else {
/* increment number of hard-links */
file->nlink++;
}
ret->attrib.st_nlink = file->nlink;
ret->attrib.st_ino = file->ino;
ret->info.file = file;
return ret;
}
static struct ecma119_tree_node*
create_placeholder(struct ecma119_write_target *t,
struct ecma119_tree_node *parent,
struct ecma119_tree_node *real)
{
struct ecma119_tree_node *ret;
assert(t && real && real->type == ECMA119_DIR
&& parent && parent->type == ECMA119_DIR);
2006-08-24 19:24:38 +00:00
ret = calloc(1, sizeof(struct ecma119_tree_node));
ret->iso_name = real->iso_name; /* TODO strdup? */
/* FIXME
* if we strdup above, if name changes in mangle_all,
* this probably keeps as original.
* if not, both change, but we need to update dirent_len.
* I think that attributes of a placeholder must be taken from
* real_me, not keept here.
* FIXME
* Another question is that real is a dir, while placeholder is
* a file, and ISO name restricctions are different, what to do?
*/
ret->dirent_len = real->dirent_len;
ret->attrib = real->attrib;
ret->full_name = strdup(real->full_name);
2006-08-24 19:24:38 +00:00
ret->target = t;
ret->parent = parent;
ret->type = ECMA119_PLACEHOLDER;
ret->info.real_me = real;
ret->attrib.st_nlink = 1;
ret->attrib.st_ino = ++t->ino;
return ret;
}
static struct ecma119_tree_node*
create_symlink(struct ecma119_write_target *t,
struct ecma119_tree_node *parent,
struct iso_tree_node_symlink *iso)
{
struct ecma119_tree_node *ret;
assert(t && iso && parent && parent->type == ECMA119_DIR);
ret = create_ecma119_node(t, parent, (struct iso_tree_node*) iso);
ret->iso_name = iso->node.name ? ((t->iso_level == 1) ?
iso_1_fileid(iso->node.name, t->input_charset)
: iso_2_fileid(iso->node.name, t->input_charset))
: NULL;
ret->type = ECMA119_SYMLINK;
ret->info.dest = iso->dest; /* TODO strdup? */
ret->attrib.st_nlink = 1;
ret->attrib.st_ino = ++t->ino;
2006-08-24 19:24:38 +00:00
return ret;
}
2007-06-05 22:01:26 +00:00
static struct ecma119_tree_node*
create_boot_catalog(struct ecma119_write_target *t,
struct ecma119_tree_node *parent,
struct iso_tree_node_boot_catalog *iso)
{
struct ecma119_tree_node *ret;
struct iso_file *file;
assert(t && iso && parent && parent->type == ECMA119_DIR);
/*
* This will simply create a ECMA119 file, with the only difference
* that the iso_file is not taken from table, but from boot catalog
*/
ret = create_ecma119_node(t, parent, (struct iso_tree_node*) iso);
ret->type = ECMA119_FILE;
file = iso->catalog->file;
file->ino = ++t->ino;
ret->attrib.st_nlink = file->nlink;
ret->attrib.st_ino = file->ino;
ret->info.file = file;
return ret;
}
2006-08-24 19:24:38 +00:00
static struct ecma119_tree_node*
create_tree(struct ecma119_write_target *t,
struct ecma119_tree_node *parent,
struct iso_tree_node *iso)
{
struct ecma119_tree_node *ret = NULL;
2006-08-24 19:24:38 +00:00
assert(t && iso);
if ( iso->hide_flags & LIBISO_HIDE_ON_RR )
return NULL;
2007-06-05 22:01:26 +00:00
switch ( iso->type ) {
case LIBISO_NODE_FILE:
ret = create_file(t, parent, (struct iso_tree_node_file*)iso);
break;
2007-06-05 22:01:26 +00:00
case LIBISO_NODE_SYMLINK:
if ( !t->rockridge )
printf("Can't add symlinks to a non ISO tree. Skipping %s \n",
iso->name);
else
ret = create_symlink(t, parent, (struct iso_tree_node_symlink*)iso);
break;
2007-06-05 22:01:26 +00:00
case LIBISO_NODE_DIR:
{
size_t i;
struct iso_tree_node_dir *dir = (struct iso_tree_node_dir*)iso;
ret = create_dir(t, parent, dir);
for (i = 0; i < dir->nchildren; i++) {
struct ecma119_tree_node *child;
child = create_tree(t, ret, dir->children[i]);
if (child)
ret->info.dir.children[ret->info.dir.nchildren++] = child;
}
}
break;
2007-06-05 22:01:26 +00:00
case LIBISO_NODE_BOOTCATALOG:
ret = create_boot_catalog(t, parent,
(struct iso_tree_node_boot_catalog*)iso);
break;
default:
/* should never happen */
assert( 0 );
break;
2006-08-24 19:24:38 +00:00
}
return ret;
}
void
ecma119_tree_free(struct ecma119_tree_node *root)
{
size_t i;
if (root->type == ECMA119_DIR) {
for (i=0; i < root->info.dir.nchildren; i++) {
ecma119_tree_free(root->info.dir.children[i]);
2006-08-24 19:24:38 +00:00
}
free(root->info.dir.children);
2006-08-24 19:24:38 +00:00
}
free(root->iso_name);
free(root->full_name);
2006-08-24 19:24:38 +00:00
free(root);
}
static size_t
max_child_name_len(struct ecma119_tree_node *root)
{
size_t ret = 0, i;
assert(root->type == ECMA119_DIR);
for (i=0; i < root->info.dir.nchildren; i++) {
size_t len = strlen(root->info.dir.children[i]->iso_name);
2006-08-24 19:24:38 +00:00
ret = MAX(ret, len);
}
return ret;
}
static void
reparent(struct ecma119_tree_node *child,
struct ecma119_tree_node *parent)
{
int found = 0;
size_t i;
struct ecma119_tree_node *placeholder;
assert(child && parent && parent->type == ECMA119_DIR && child->parent);
/* replace the child in the original parent with a placeholder */
for (i=0; i < child->parent->info.dir.nchildren; i++) {
if (child->parent->info.dir.children[i] == child) {
placeholder = create_placeholder(child->target,
child->parent, child);
child->parent->info.dir.children[i] = placeholder;
2006-08-24 19:24:38 +00:00
found = 1;
break;
}
}
assert(found);
/* add the child to its new parent */
child->parent = parent;
parent->info.dir.nchildren++;
parent->info.dir.children = realloc( parent->info.dir.children,
sizeof(void*) * parent->info.dir.nchildren );
parent->info.dir.children[parent->info.dir.nchildren-1] = child;
2006-08-24 19:24:38 +00:00
}
/**
* Reorder the tree, if necessary, to ensure that
* - the depth is at most 8
* - each path length is at most 255 characters
*/
static void
reorder_tree(struct ecma119_write_target *t,
struct ecma119_tree_node *root,
2006-08-24 19:24:38 +00:00
struct ecma119_tree_node *cur)
{
size_t max_path;
assert(root && cur && cur->type == ECMA119_DIR);
cur->info.dir.depth = cur->parent ? cur->parent->info.dir.depth + 1 : 1;
cur->info.dir.path_len = cur->parent ? cur->parent->info.dir.path_len
+ strlen(cur->iso_name) : 0;
max_path = cur->info.dir.path_len + cur->info.dir.depth
+ max_child_name_len(cur);
if (cur->info.dir.depth > 8 || max_path > 255) {
if (t->rockridge) {
reparent(cur, root);
/* we are appended to the root's children now, so there is no
* need to recurse (the root will hit us again) */
} else {
/* we need to delete cur */
size_t i,j;
struct ecma119_tree_node *parent = cur->parent;
printf("Can't dirs deeper than 8 without RR. Skipping %s\n",
cur->full_name);
for (i=0; i < parent->info.dir.nchildren; ++i) {
if (parent->info.dir.children[i] == cur) {
break;
}
}
assert ( i < parent->info.dir.nchildren);
for ( j = i; j < parent->info.dir.nchildren - 1; ++j)
parent->info.dir.children[j] = parent->info.dir.children[j+1];
parent->info.dir.nchildren--;
ecma119_tree_free(cur);
}
2006-08-24 19:24:38 +00:00
} else {
size_t i;
for (i=0; i < cur->info.dir.nchildren; i++) {
if (cur->info.dir.children[i]->type == ECMA119_DIR)
reorder_tree(t, root, cur->info.dir.children[i]);
2006-08-24 19:24:38 +00:00
}
}
}
static int
cmp_node(const void *f1, const void *f2)
{
struct ecma119_tree_node *f = *((struct ecma119_tree_node**)f1);
struct ecma119_tree_node *g = *((struct ecma119_tree_node**)f2);
return strcmp(f->iso_name, g->iso_name);
2006-08-24 19:24:38 +00:00
}
static void
sort_tree(struct ecma119_tree_node *root)
{
size_t i;
assert(root && root->type == ECMA119_DIR);
qsort(root->info.dir.children, root->info.dir.nchildren,
sizeof(void*), cmp_node);
for (i=0; i < root->info.dir.nchildren; i++) {
if (root->info.dir.children[i]->type == ECMA119_DIR)
sort_tree(root->info.dir.children[i]);
2006-08-24 19:24:38 +00:00
}
}
/**
* Change num_change characters of the given filename in order to ensure the
* name is unique. If the name is short enough (depending on the ISO level),
* we can append the characters instead of changing them.
*
* \p seq_num is the index of this file in the sequence of identical filenames.
*
* For example, seq_num=3, num_change=2, name="HELLOTHERE.TXT" changes name to
* "HELLOTHE03.TXT"
*/
static void
mangle_name(char **name, int num_change, int level, int seq_num)
{
char *dot = strrchr(*name, '.');
char *semi = strrchr(*name, ';');
size_t len = strlen(*name);
char base[len+1], ext[len+1];
char fmt[12];
size_t baselen, extlen;
if (num_change >= len) {
return;
}
strncpy(base, *name, len+1);
if (dot) {
base[dot - *name] = '\0';
strncpy(ext, dot+1, len+1);
if (semi) {
ext[semi - dot - 1] = '\0';
}
} else {
base[len-2] = '\0';
ext[0] = '\0';
}
baselen = strlen(base);
extlen = strlen(ext);
if (level == 1 && baselen + num_change > 8) {
base[8 - num_change] = '\0';
} else if (level != 1 && baselen + extlen + num_change > 30) {
base[30 - extlen - num_change] = '\0';
}
sprintf(fmt, "%%s%%0%1dd.%%s;1", num_change);
*name = realloc(*name, baselen + extlen + num_change + 4);
sprintf(*name, fmt, base, seq_num, ext);
}
static void
mangle_all(struct ecma119_tree_node *dir)
{
size_t i, j, k;
struct ecma119_dir_info d = dir->info.dir;
2006-08-24 19:24:38 +00:00
size_t n_change;
int changed;
assert(dir->type == ECMA119_DIR);
do {
changed = 0;
for (i=0; i < d.nchildren; i++) {
/* find the number of consecutive equal names */
j = 1;
while ( i+j < d.nchildren &&
!strcmp(d.children[i]->iso_name,
d.children[i+j]->iso_name) )
2006-08-24 19:24:38 +00:00
j++;
if (j == 1) continue;
/* mangle the names */
changed = 1;
n_change = j / 10 + 1;
for (k=0; k < j; k++) {
mangle_name(&(d.children[i+k]->iso_name),
2006-08-24 19:24:38 +00:00
n_change,
dir->target->iso_level,
k);
d.children[i+k]->dirent_len =
calc_dirent_len(d.children[i+k]);
}
/* skip ahead by the number of mangled names */
i += j - 1;
}
} while (changed);
for (i=0; i < d.nchildren; i++) {
if (d.children[i]->type == ECMA119_DIR)
mangle_all(d.children[i]);
}
}
struct ecma119_tree_node*
ecma119_tree_create(struct ecma119_write_target *t,
struct iso_tree_node *iso_root)
{
t->root = create_tree(t, NULL, iso_root);
if ( !(t->relaxed_constraints & ECMA119_NO_DIR_REALOCATION) )
reorder_tree(t, t->root, t->root);
2006-08-24 19:24:38 +00:00
sort_tree(t->root);
mangle_all(t->root);
return t->root;
}
void
ecma119_tree_print(struct ecma119_tree_node *root, int spaces)
{
size_t i;
char sp[spaces+1];
memset(sp, ' ', spaces);
sp[spaces] = '\0';
printf("%s%s\n", sp, root->iso_name);
2006-08-24 19:24:38 +00:00
if (root->type == ECMA119_DIR)
for (i=0; i < root->info.dir.nchildren; i++)
ecma119_tree_print(root->info.dir.children[i], spaces+2);
2006-08-24 19:24:38 +00:00
}