treeop.cpp

参照网上的例子改写的多叉树的读写程序

/********************************************************
     文 件 名: tree.c
     所属项目: 
     编写单位: 
     作    者: 易剑
     编写日期: 2003-02-10
     版    本: 
     功能描述: 操作配置文件的树结构及其算法
     修改日志: 
     修改时间: 
       修 改 者: 
    修改内容: 
*********************************************************/









#include "treeOp.h"

//#include "private_tree.h"
#include "parse_cfgfile.h"


//#include "misc.h"


//#include "queue.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "mystack.h"




/*
    ===============================================================
    函数实现处
    ===============================================================
*/


/********************************************************
     函 数 名称：init_cfg
     功能描述：初始化配置文件
     参数说明：
        cfg_filepath，配置文件
        task_filepath，任务文件
        argv，命令行参数
        direct，装载行为
     返 回 值：成功返回树根结点的指针，否则返回 NULL
*********************************************************/
struct tree_node *init_cfg(char *cfg_filepath, char *task_filepath, char **argv, char *direct)
{
    struct tree_node *root            = NULL;
    struct tree_node *defaultnode    = NULL;
    
    /* 1、建立树根结点 */
    root = create_treeroot("root");
    if (NULL == root)
        return NULL;

#define _DEBUG_ 
#ifdef _DEBUG_
    createtree_fromfile(cfg_filepath, &root);
    return root;
    
#endif /* _DEBUG_ */


    /* 2、建立 [DEFAULT] 结点 */
    defaultnode = (struct tree_node *)malloc(sizeof(struct tree_node));
    if (NULL == defaultnode)
    {
        free(root);
        root = NULL;

        return NULL;
    }
    memset(defaultnode, NULL, sizeof(struct tree_node));
    strcpy(defaultnode->data, "DEFAULT");
    defaultnode->flag = 1;

    insertnode_byparent(root, defaultnode);

    /* 载入环境变量到以 defaultnode 为父结点的子树中 */
    if (direct[0] == 1)
    {
        ;//load_envvar(&defaultnode);
    }

    /* 载入配置文件 [DEFAULT] 段
        到以 defaultnode 为父结点的子树中 ,
        并覆盖上一步载入的环境变量
    */
    if (direct[1] == 1)
    {
        ;//load_cfgndvar(&defaultnode, cfg_filepath);
    }    

    /* 载入任务文件 [DEFAULT] 段到以 defaultnode 为父结点的子树中 */
    if (direct[3] == 1)
    {
        ;//load_taskdvar(&defaultnode, task_filepath);
    }

    /* 载入命令行到以 defaultnode 为父结点的子树中 */
    if (direct[4] == 1)
    {
        ;//load_cmdvar(&defaultnode, argv);
    }

    /*
        构建 defaultnode 结点的兄弟结点
    */
    /* 载入配置文件[DEFAULT] 段以外的参数，
       构建与 defaultnode 结点并列的结点 */
    if (direct[2] == 1)
    {
        load_cfgndvar(&root, cfg_filepath);
    }

    return root;
}

/********************************************************
     函 数 名称：uninit
     功能描述：释放树结点
     参数说明：
        root，树根
     返 回 值：无
*********************************************************/
void uninit(struct tree_node *root)
{
    struct tree_node *child         = NULL;
    struct tree_node *sibling     = NULL;
    struct tree_node *nextsibling     = NULL;

    /* 树根不存在或不是树根时 */
    if ((NULL == root))
        return;

    child = root->firstchild;
    if (NULL != child)
    {
        sibling = child->nextsibling;

        /* 如果是叶子结点或是空子树时 */
        if ((child->flag == 0) || (child->firstchild == NULL))
        {
            free(child);
            child = NULL;
        }
        else
        {
            uninit(child);
            child = NULL;
        }

        do
        {        
            if (NULL != sibling)
            {
                nextsibling = sibling->nextsibling;

                if ((sibling->flag == 0) || (sibling->firstchild == NULL))
                {
                    free(sibling);
                    sibling = NULL;
                }
                else
                {                    
                    uninit(sibling);                    
                    sibling = NULL;
                }
                
                sibling = nextsibling->nextsibling;
            }                    
        } while (NULL != sibling);
    }

    /* 释放根结点 */
    free(root);
    root = NULL;
}

/********************************************************
     函 数 名称：createtree_fromfile
     功能描述：从文件中获取数据创建以为 root 根的树
     参数说明：
        filename，存储有树结构数据的文件的文件名
        root，树根
     返 回 值：无
*********************************************************/
void createtree_fromfile(char *filename, struct tree_node **root)
{
    FILE *fp = NULL;
    struct mystack s;

    if ((NULL == filename) || (*root == NULL))
        return;

    fp = fopen(filename, "r");
    if (NULL == fp)
        return;

    init_stack(&s);
    push_stack(&s, *root); /* 必须 */


    read_fromcfgfile(fp, root, &s);

    fclose(fp);
}

/********************************************************
     函 数 名称：createtree_fromfilefp
     功能描述：从文件中获取数据创建以为 root 根的树
     参数说明：
        fp，存储有树结构数据的文件的文件描述符
        root，树根
     返 回 值：无
*********************************************************/
void createtree_fromfilefp(FILE *fp, struct tree_node **root)
{
    struct mystack s;

    if ((NULL == fp) || (*root == NULL))
        return;

    init_stack(&s);
    push_stack(&s, *root); /* 必须 */

    read_fromcfgfile(fp, root, &s);    
}

/********************************************************
     函 数 名 称：dump_tree  
     功能描述：将根为 root 的树的子树(根为 path 对应的结点)导出到文件 result_filepath 中
     参数说明：
        root，树根
        path，路径，如果 path 为 NULL则将整个树导出
        result_filepath，导出文件
     返 回 值：成功返回 1，失败返回 -1
*********************************************************/
int dump_tree(struct tree_node *root, const char *result_filepath, const char *path)
{
    FILE *fp                    = NULL;
    struct tree_node *subroot    = NULL;    /* 路径 path 对应的结点 */

    if ((NULL == root) || (NULL == result_filepath))
        return -1;

    if (NULL != path)
    {    
        subroot = get_node(root, path);
        if (subroot == NULL)
            return -1;
    }
    else
    {
        subroot = root;
    }

    fp = fopen(result_filepath, "w");
    if (NULL == fp)    
        return -1;
    
    recursion_dump(subroot, fp)    ;

    fclose(fp);

    return 1;
}

/********************************************************
  函 数 名：get_value
  功能描述：得到 path 对应的结点的 value 域值；
            如果该结点为内部结点，
            则得到第一个类型为 flag 的子结点的路径
  参数说明：
      root，树根
      path，路径
      flag，如果返回是下一个并列结点的路径，则 flag 的返回值为 8
  返 回 值：成功返回得到的子结点路径或 value域值，失败返回 NULL
*********************************************************/
char *get_value(struct tree_node *root, const char *path, int *flag)
{
    struct tree_node *node = NULL;        /* 目标结点 */
    struct tree_node *firstchild = NULL;/* 目标结点的第一个孩子 */
    struct tree_node *sibling = NULL;   /* 目标孩子的其它孩子 */
    char *value = NULL;
    int valuelen = 0;

    if ((NULL == root) || (NULL == path) || (NULL == flag))
        return NULL;

    node  = get_node(root, path);
    if (NULL == node)
        return NULL;

    if (node->flag == NODE_IS_LEAF)                /* 是叶子 */
    {
        value = (char *)malloc(strlen(node->data)+1);
        if (NULL == value)
            return NULL;

        strcpy(value, node->data);

        return value;
    }
    else if (node->flag == NODE_IS_BRANCH)            /* 是树枝 */
    {
        firstchild = node->firstchild;
        if (firstchild != NULL)
        {
            if (firstchild->flag == *flag)
            {
                /* 别忘记了路径之间要用 ":" 隔开，故要加 2 */
                valuelen = strlen(path)+strlen(firstchild->data)+2;
                value = (char *)malloc(valuelen);
                if (NULL == value)
                    return NULL;

                memset(value, '\0', valuelen);
                strcpy(value, path);
                strcat(value, ":");
                strcat(value, firstchild->data);

                *flag = 8;
                return value;
            }
            else    /* 从其它兄弟中寻找 */
            {
                sibling = firstchild->nextsibling;
                while (sibling != NULL)
                {
                    if (sibling->flag == *flag)
                    {
                        /* 别忘记了路径之间要用 ":" 隔开，故要加 2 */
                        valuelen = strlen(path)+strlen(sibling->data)+2;
                        value = (char *)malloc(valuelen);
                        if (NULL == value)
                            return NULL;

                        memset(value, '\0', valuelen);
                        strcpy(value, path);
                        strcat(value, ":");
                        strcat(value, sibling->data);

                        *flag = 8;
                        return value;
                    }

                    sibling = sibling->nextsibling;
                }
            }
        }
    }

    return NULL;
}

/********************************************************
     函 数 名：node_is_exist
     功能描述：判断路径是否是合法路径
     参数说明：
        root，树根
        path，待判断的路径
     返 回 值：成功返回1，失败返回-1
*********************************************************/
int node_is_exist(struct tree_node *root, const char *path)
{
    char *value = NULL;
    int flag = NODE_IS_LEAF;
    
    value = get_value(root, path, &flag);
    if ((NULL != value) && (NEXT_NODE_EXIST != flag))
        return 1;
    else
        return -1;
}
/********************************************************
     函 数 名：get_next_path     功能描述：得到与 path 并列的下一类型为 flag 的路径
     参数说明：
        root，树根
        path，路径
     返 回 值：成功返回得到的路径，失败返回 NULL
*********************************************************/
char *get_next_path(struct tree_node *root, const char *path, int flag)
{
    struct tree_node *node = NULL;        /* 结点 */    
    struct tree_node *sibling = NULL;   /* 兄弟结点 */

    char *nextpath    = NULL;
    int nextpathlen    = 0;
    int pathlen        = 0;
    int len            = 0;

    if ((NULL == root) || (NULL == path))
        return NULL;

    node  = get_node(root, path);
    if (NULL == node)                    /* 路径为 path 的结点不存在 */
        return NULL;

    sibling = node->nextsibling;
    while (sibling != NULL)
    {
        if (sibling->flag == flag)
        {
            len = strlen(node->data);
            pathlen = strlen(path);
            nextpathlen = pathlen - len + strlen(sibling->data) + 1;
            nextpath = (char *)malloc(nextpathlen);
            if (nextpath == NULL)
                return NULL;
            
            memset(nextpath, NULL, nextpathlen);
            strncpy(nextpath, path, pathlen-len);
            strcat(nextpath, sibling->data);

            return nextpath;
        }

        sibling = sibling->nextsibling;
    }

    return NULL;
}

/********************************************************
     函 数 名：get_next_path2
     功能描述：得到下一个并列结点的路径和结点类型
     参数说明：
        root，树根
        path，路径
        flag，输出参数，下一结点的类型
     返 回 值：成功返回得到的路径，失败返回 NULL
*********************************************************/
char *get_next_path2(struct tree_node *root, const char *path, int *flag)
{
    struct tree_node *node = NULL;        /* 结点 */    
    struct tree_node *sibling = NULL;   /* 兄弟结点 */

    char *nextpath    = NULL;
    int nextpathlen    = 0;
    int pathlen        = 0;
    int len            = 0;

    if ((NULL == root) || (NULL == path) || (NULL == flag))
        return NULL;