file_tree.c

Go to the documentation of this file.

/***************************************************************************
 *   Copyright (C) 2004, 2006 Symbian Software Ltd.                        *
 *   All rights reserved.                                                  *
 *   Copyright (C) 2007-2011 Mike Kinghan, imk@strudl.org                  *
 *   All rights reserved.                                                  *
 *                                                                         *
 *   Redistribution and use in source and binary forms, with or without    *
 *   modification, are permitted provided that the following conditions    *
 *   are met:                                                              *
 *                                                                         *
 *   Redistributions of source code must retain the above copyright        *
 *   notice, this list of conditions and the following disclaimer.         *
 *                                                                         *
 *   Redistributions in binary form must reproduce the above copyright     *
 *   notice, this list of conditions and the following disclaimer in the   *
 *   documentation and/or other materials provided with the distribution.  *
 *                                                                         *
 *   Neither the name of Symbian Software Ltd. nor the names of its        *
 *   contributors may be used to endorse or promote products derived from  *
 *   this software without specific prior written permission.              *
 *                                                                         *
 *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS   *
 *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT     *
 *   LIMITED TO, THE IMPLIED WARRANTIES OF  MERCHANTABILITY AND FITNESS    *
 *   FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE        *
 *   COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,   *
 *   INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,  *
 *   BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS *
 *   OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED    *
 *   AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,*
 *   OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF *
 *   THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH  *
 *   DAMAGE.                                                               *
 *                                                                         *
 **************************************************************************/

#include "file_tree.h"
#include "filesys.h"
#include "platform.h"
#include "report.h"
#include "swiss_army.h"


#define PARENT_PENDING  ((void *)-1)

#define IS_UNLINKED(ftree)      ((ftree)->parent == PARENT_PENDING)

#define IS_ROOT(ftree)  ((ftree)->parent == NULL)

#define IS_FILE(ftree)  ((ftree)->children == NULL)

#define IS_DIR(ftree)   (!IS_FILE(ftree))

#define COUNT_FILES(flags) (((flags) & FT_COUNT_FILES) == FT_COUNT_FILES)

#define COUNT_FILES_ONLY(flags) (((flags) & FT_COUNT_ALL) == FT_COUNT_FILES)

#define COUNT_DIRS(flags) (((flags) & FT_COUNT_DIRS) == FT_COUNT_DIRS)

#define COUNT_DIRS_ONLY(flags) (((flags) & FT_COUNT_ALL) == FT_COUNT_DIRS)

#define COUNT_ALL(flags) (((flags) & FT_COUNT_ALL) == FT_COUNT_ALL)

#define COUNT_CHILDREN(flags) (((flags) & FT_COUNT_CHILDREN) == FT_COUNT_CHILDREN)

struct file_tree {
    union {
        heap_str leafname;      
        file_filter_t filter;   
    } var; 
    struct file_tree * parent;   
    ptr_vector_h children;      
    unsigned files; 
};

static bool
null_filter(char const *leafname)
{
    return true;
}

static void
null_callback(  file_tree_h ft,
                char const *name,
                file_tree_traverse_state_t context)
{
}

static file_tree_h
new_node(char const *leafname, size_t len)
{
    file_tree_h ft = callocate(1,sizeof(struct file_tree));
    if (!len) {
        len = strlen(leafname);
    }
    ft->parent = PARENT_PENDING;
    ft->var.leafname = zallocate(len + 1);
    strncpy(ft->var.leafname,leafname,len);
    return ft;
}


static file_tree_h
new_file_node(char const *leafname, file_filter_t filter)
{
    file_tree_h ft = NULL;
    if (filter(leafname)) {
        ft = new_node(leafname,0);
        ft->files = 1;
    }
    return ft;
}

static file_tree_h
get_parent(file_tree_h child)
{
    return IS_UNLINKED(child) || IS_ROOT(child) ? NULL : child->parent;
}
static void
link_in(file_tree_h parent, file_tree_h child)
{
    unsigned new_files;
    assert(!IS_ROOT(child));
    if (!parent->children) {
        parent->children = ptr_vector_new((dtor_t)file_tree_dispose,NULL);
    }
    child->parent = parent;
    ptr_vector_append(parent->children,child);
    new_files = child->files;
    if (new_files) {
        for     (       ; parent; child = parent,parent = get_parent(child)) {
            parent->files += new_files;
        }
    }
}

/* Forward declaration*/
static void
file_tree_add_symlink(  file_tree_h root,
                        fs_dir_t parent,
                        char const *symlink,
                        file_tree_callback_t callback);


static file_tree_h
new_dir_node(   file_tree_h root,
                char const *leafname,
                fs_dir_t dir,
                file_filter_t filter,
                file_tree_callback_t callback)
{
    file_tree_h ft = new_node(leafname,0);
    char const *cur_entry;
    char const *fullname = fs_cur_dir_entry(dir,&cur_entry);
    assert(cur_entry[0] == '\0');
    callback(ft,fullname,FT_ENTERING_DIR);
    ft->children = ptr_vector_new((dtor_t)file_tree_dispose,NULL);
    while((leafname = fs_read_dir(dir,&fullname)) != NULL) {
        fs_obj_type_t obj_type = fs_obj_type(fullname);
        if (FS_IS_SLINK(obj_type)) {
            file_tree_add_symlink(ft,dir,fullname,callback);
        } else {
            file_tree_h child = NULL;
            fs_dir_t subdir = fs_open_dir(fullname,dir);
            if (subdir) {
                child = new_dir_node(root,leafname,subdir,filter,callback);
                fs_close_dir(subdir);
            } else {
                child = new_file_node(leafname,filter);
                if (child) {
                    callback(child,fullname,FT_AT_FILE);
                }
            }
            if (child) {
                assert(child->files);
                link_in(ft,child);
            }
        }
    }
    fullname = fs_cur_dir_entry(dir,&cur_entry);
    assert(cur_entry[0] == '\0');
    callback(ft,fullname,FT_LEAVING_DIR);
    if (!ft->files) {
        file_tree_dispose(ft);
        ft = NULL;
    }
    return ft;
}

static file_tree_h
get_root(file_tree_h ft)
{
    if (IS_ROOT(ft)) {
        return ft;
    }
    return get_root(ft->parent);
}


static file_tree_h
seek_child(file_tree_h node, char const *childname)
{
    file_tree_h child = NULL;
    if (node->children) {
        file_tree_h *start =
            (file_tree_h *)ptr_vector_begin(node->children);
        file_tree_h *end =
            (file_tree_h *)ptr_vector_end(node->children);
        for (   ; start != end; ++start) {
            if (!strcmp(childname,(*start)->var.leafname)) {
                child = *start;
                break;
            }
        }
    }
    return child;
}


static file_tree_h
seek(file_tree_h ft, char const **path)
{
    char const *posn = *path;
    char const *end = strchr(posn,PATH_DELIM);
    fs_path_type_t path_type = fs_path_type(posn);
    if (!end) {
        end = posn + strlen(posn);
    }
    if (!IS_ROOT(ft)) {
        size_t elmlen = end - posn;
        if (fs_windows_path(path_type) && fs_absolute_path(path_type)) {
            path_type = 0;
        }
        if (ft->var.leafname[elmlen] =='\0' &&
                !strncmp(ft->var.leafname,posn,elmlen)) {
            *path = posn += elmlen;
        } else {
            return ft;
        }
    }
    if (*posn) {
        if (!fs_windows_path(path_type) || !fs_absolute_path(path_type)) {
            *path = posn = end + 1;
        }
        if (ft->children) {
            file_tree_h child = NULL;
            file_tree_h *start =
                (file_tree_h *)ptr_vector_begin(ft->children);
            file_tree_h *end =
                (file_tree_h *)ptr_vector_end(ft->children);
            for (       ; start != end && posn == *path; ++start) {
                child = seek(*start,&posn);
            }
            if (posn != *path) {
                *path = posn;
                ft = child;
            }
        }
    }
    return ft;
}

static file_tree_h
deepen(file_tree_h ft, char const **path)
{
    char const *end = strchr(*path,PATH_DELIM);
    if (end) {
        file_tree_h child = new_node(*path,end - *path);
        child->children = ptr_vector_new((dtor_t)file_tree_dispose,NULL);
        link_in(ft,child);
        *path = end + 1;
        ft = deepen(child,path);
    }
    return ft;
}

static void
traverse(       file_tree_h ft,
            file_tree_callback_t callback,
            char *path_start,
            char *path_end)
{
    strcpy(path_end,ft->var.leafname);
    if (IS_DIR(ft)) {
        size_t leaflen = strlen(path_end);
        file_tree_h * start = (file_tree_h *)ptr_vector_begin(ft->children);
        file_tree_h * end = (file_tree_h *)ptr_vector_end(ft->children);
        callback(ft,path_start,FT_ENTERING_DIR);
        path_end[leaflen++] = PATH_DELIM;
        for (   ; start != end; ++start) {
            traverse(*start,callback,path_start,path_end + leaflen);
        }
        path_end[--leaflen] = '\0';
        callback(ft,path_start,FT_LEAVING_DIR);
    } else {
        callback(ft,path_start,FT_AT_FILE);
    }
    *path_end = '\0';
}


static void
file_tree_add_canon(    file_tree_h root,
                        char const *path,
                        file_tree_callback_t callback)
{
    char const * fullpath = path;
    heap_str parent_path = fs_split_filename(path,NULL);
    fs_dir_t parent_dir = parent_path ? fs_open_dir(parent_path,NULL) : NULL;
    fs_dir_t dir = fs_open_dir(path,parent_dir);
    file_filter_t filter;
    file_tree_h lowest;
    if (parent_path) {
        free(parent_path);
    }
    root = get_root(root);
    filter = root->var.filter;
    if (!callback) {
        callback = null_callback;
    }
    lowest = seek(root,&path);
    if (*path) {
        file_tree_h child;
        lowest = deepen(lowest,&path);
        if (!dir) {
            child = new_file_node(path,filter);
            if (child) {
                callback(child,fullpath,FT_AT_FILE);
            }
        } else {
            child = new_dir_node(root,path,dir,filter,callback);
        }
        if (child) {
            link_in(lowest,child);
        }
    } else if (dir) {
        char const * leafname;
        char const *fullname;
        while((leafname = fs_read_dir(dir,&fullname)) != NULL) {
            fs_obj_type_t obj_type = fs_obj_type(fullname);
            if (FS_IS_SLINK(obj_type)) {
                file_tree_add_symlink(root,dir,fullname,callback);
            } else {
                file_tree_h child = seek_child(lowest,leafname);
                if (!child) {
                    fs_dir_t subdir = fs_open_dir(fullname,dir);
                    if (!subdir) {
                        child = new_file_node(leafname,filter);
                        if (child) {
                            callback(child,fullname,FT_AT_FILE);
                        }
                    } else {
                        child =
                            new_dir_node(root,leafname,subdir,filter,callback);
                        fs_close_dir(subdir);
                    }
                    if (child) {
                        link_in(lowest,child);
                    }
                }
            }
        }
    }
    if (parent_dir) {
        fs_close_dir(parent_dir);
    }
    if (dir) {
        fs_close_dir(dir);
    }
}


static void
file_tree_add_symlink(  file_tree_h root,
                        fs_dir_t dir,
                        char const *symlink,
                        file_tree_callback_t callback)
{
    heap_str realpath;
    realpath = fs_real_path(symlink,NULL);
    report(GRIPE_SYMLINK,NULL,"Resolved symbolic link \"%s\"",symlink);
    if (dir) {
        size_t shared_len = 0;
        char const *entry;
        char const * dirname = fs_cur_dir_entry(dir,&entry);
        char const *shared_path  =
            fs_path_comp(dirname,realpath,&shared_len);
        while (!(shared_path == dirname && dirname[shared_len] == 0)) {
            if ((dir = fs_get_parent(dir)) == NULL) {
                break;
            }
            dirname = fs_cur_dir_entry(dir,&entry);
            shared_path  = fs_path_comp(dirname,realpath,&shared_len);
        }
    }
    if (!dir) {
        file_tree_add_canon(root,realpath,callback);
    }
    free(realpath);
}

static void
file_tree_init(file_tree_h ft)
{
    memset(ft,0,sizeof(struct file_tree));
    ft->var.filter = null_filter;
}

static void
file_tree_copy_init(file_tree_h dest, file_tree_const_h src)
{
    memset(dest,0,sizeof(struct file_tree));
    if (src->children) {
        file_tree_const_h *start =
            (file_tree_const_h *)ptr_vector_begin_const(src->children);
        file_tree_const_h *end =
            (file_tree_const_h *)ptr_vector_end_const(src->children);
        for     (       ; start != end; ++start) {
            file_tree_h child = file_tree_copy(*start);
            link_in(dest,child);
        }
    } else if (IS_ROOT(src)) {
        dest->var.filter = src->var.filter;
    } else {
        dest->var.leafname = clone(src->var.leafname,0);
        dest->files = src->files;
    }
}

static void
file_tree_finis(file_tree_h ft)
{
    if (ft->children) {
        ptr_vector_dispose(ft->children);
        ft->children = NULL;
    }
    if (!IS_ROOT(ft) && ft->var.leafname) {
        free(ft->var.leafname);
        ft->var.leafname = NULL;
    }
}

#ifdef DEBUG_FILE_TREE
static void
file_tree_print_name(file_tree_h ft, char const *name, int context)
{
    (void)context;
    puts(name);
}

void
file_tree_dump(file_tree_h ft)
{
    if (!IS_ROOT(ft)) {
        file_tree_dump(ft->parent);
    } else {
        file_tree_traverse(ft,file_tree_print_name);
    }
}

#endif

/* API*/

heap_str
file_tree_name(file_tree_const_h ft)
{
    heap_str full_name;
    if (IS_ROOT(ft)) {
        full_name = callocate(1,1);
    } else {
        heap_str path_name = file_tree_name(ft->parent);
        full_name =
            fs_compose_filename(path_name,ft->var.leafname);
        free(path_name);
    }
    return full_name;
}

file_tree_h
file_tree_new(void)
{
    file_tree_h ft = allocate(sizeof(struct file_tree));
    file_tree_init(ft);
    return ft;
}

file_tree_h
file_tree_copy(file_tree_const_h src)
{
    file_tree_h dest;
    assert(src);
    dest = allocate(sizeof(struct file_tree));
    file_tree_copy_init(dest,src);
    return dest;
}

void
file_tree_swap(file_tree_h lhs, file_tree_h rhs)
{
    assert(lhs);
    assert(rhs);
    PODSWAP(heap_str,&lhs->var.leafname,&rhs->var.leafname);
    PODSWAP(file_tree_h,&lhs->parent,&rhs->parent);
    PODSWAP(ptr_vector_h,&lhs->children,&rhs->children);
    PODSWAP(unsigned,&lhs->files,&rhs->files);
}

void
file_tree_assign(file_tree_h dest, file_tree_const_h src)
{
    if (dest != src) {
        file_tree_h tmp = file_tree_copy(src);
        file_tree_swap(dest,tmp);
        file_tree_dispose(tmp);
    }
}

bool
file_tree_equal(file_tree_const_h lhs, file_tree_const_h rhs)
{
    if (lhs == rhs) {
        return true;
    }
    if (!lhs->children ^ !rhs->children) {
        return false;
    }
    if (lhs->children) {
        if (ptr_vector_count(lhs->children) != ptr_vector_count(rhs->children)) {
            return false;
        }
                {
                        file_tree_const_h *lh_iter =
                                (file_tree_const_h *)ptr_vector_begin_const(lhs->children);
                        file_tree_const_h *rh_iter =
                                (file_tree_const_h *)ptr_vector_begin_const(rhs->children);
                        file_tree_const_h *lh_end =
                                (file_tree_const_h *)ptr_vector_end_const(lhs->children);
                        for     (       ; lh_iter != lh_end; ++lh_iter,++rh_iter) {
                                if (!file_tree_equal(*lh_iter,*rh_iter)) {
                                        return false;
                                }
                        }
                }
    }
    if (IS_ROOT(lhs) ^ IS_ROOT(rhs)) {
        return false;
    }
    if (IS_ROOT(lhs)) {
        return true;
    } else {
        heap_str lh_name = file_tree_name(lhs);
        heap_str rh_name = file_tree_name(rhs);
        bool eq = !strcmp(lh_name,rh_name);
        free(lh_name);
        free(rh_name);
        return eq;
    }
}


bool
file_tree_set_filter(file_tree_h ft, file_filter_t filter)
{
    if (!file_tree_is_empty(ft)) {
        return false;
    }
    ft->var.filter = filter;
    return true;
}

void
file_tree_dispose(file_tree_h ft)
{
    if (ft) {
        file_tree_finis(ft);
        free(ft);
    }
}

void
file_tree_add(  file_tree_h root,
                char const *path,
                file_tree_callback_t callback)
{
    fs_obj_type_t obj_type = fs_file_or_dir(path);
    if (FS_IS_SLINK(obj_type)) {
        file_tree_add_symlink(root,NULL,path,callback);
    } else {
        heap_str fullpath = fs_real_path(path,NULL);
        file_tree_add_canon(root,fullpath,callback);
        free(fullpath);
    }
}

void
file_tree_traverse(     file_tree_h ft,
                    file_tree_callback_t callback)
{
    callback(ft,NULL,FT_ENTERING_TREE);
    if (ft->children) {
        file_tree_h * start;
        file_tree_h * end;
        heap_str pathstack = callocate(1,PATH_MAX);
        strcpy(pathstack,FS_ROOT_PREFIX);
        start = (file_tree_h *)ptr_vector_begin(ft->children);
        end = (file_tree_h *)ptr_vector_end(ft->children);
        for (   ; start != end; ++start) {
            traverse(*start,callback,pathstack,pathstack + strlen(pathstack));
        }
        free(pathstack);
    }
    callback(ft,NULL,FT_LEAVING_TREE);
}

bool
file_tree_is_empty(file_tree_const_h ft)
{
    if (!IS_ROOT(ft)) {
        return false;
    }
    return !ft->children || ptr_vector_count(ft->children) == 0;
}

size_t
file_tree_count(file_tree_const_h ft, unsigned flags, file_tree_count_t *counter)
{
    file_tree_count_t count = {0,0,0};
    int count_children = COUNT_CHILDREN(flags);
    int count_dirs = COUNT_DIRS(flags);
    int count_files = COUNT_FILES(flags);
    if (!count_children && count_files && !count_dirs) {
        count.files = ft->files;
    } else {
        if (!IS_ROOT(ft)) {
            if (!count_children) {
                if (IS_DIR(ft)) {
                    count.dirs += count_dirs;
                } else {
                    count.files += count_files;
                }
            }
        }
        if (IS_DIR(ft)) {
            file_tree_h * start = (file_tree_h *)ptr_vector_begin(ft->children);
            file_tree_h * end = (file_tree_h *)ptr_vector_end(ft->children);
            for (       ; start != end; ++ start) {
                if (count_children) {
                    ++count.children;
                    if (IS_DIR(*start)) {
                        count.dirs += count_dirs;
                    } else {
                        count.files += count_files;
                    }
                } else {
                    file_tree_count(*start,flags,&count);
                }
            }
        }
    }
    if (counter) {
        *counter = count;
    }
    return count.files + count.dirs;
}


file_tree_const_h
file_tree_child(file_tree_const_h ft, size_t which)
{
    file_tree_h child = NULL;
    if (IS_DIR(ft)) {
        size_t children = ptr_vector_count(ft->children);
        if (children) {
            if (which == FT_LAST) {
                which = children - 1;
            }
            if (which < children) {
                child = *(file_tree_h *)ptr_vector_at(ft->children,which);
            }
        }
    }
    return child;
}

/* EOF*/