ttree.cpp

Go to the documentation of this file.

 
#include  "ttree.h"
#include  "jbxl_state.h"
 
 
// ノード操作
//
 
tTree*  new_tTree_node(void)
{
    tTree* pp;
 
    pp = (tList*)malloc(sizeof(tTree));
    if (pp==NULL) return NULL;
    memset(pp, 0, sizeof(tTree));
    pp->ldat  = init_tList_data();
    pp->state = JBXL_NORMAL;
 
    return pp;
}
 
 
tTree*  new_tTree_anchor_node(void)
{
    tTree* pp;
 
    pp = (tList*)malloc(sizeof(tTree));
    if (pp==NULL) return NULL;
    memset(pp, 0, sizeof(tTree));
    pp->ldat    = init_tList_data();
    pp->ldat.id = TREE_ANCHOR_NODE;
    pp->depth   = -1;
    pp->state   = JBXL_STATE_ANCHOR;    // TREE_ANCHOR_NODE と同じ
 
    return pp;
}
 
 
tTree*  del_tTree_anchor_node(tTree* node)
{
    tTree* pp = node;
 
    if (node!=NULL && node->ldat.id==TREE_ANCHOR_NODE) {
        pp = node->next;
        free_tTree_node(node);
        free(node);
    }
 
    return pp;    
}
 
 
tTree  make_tTree_node(tList_data data)
{
    tTree pp;
 
    memset(&pp, 0, sizeof(tTree));
    pp.ldat  = data;
    pp.state = JBXL_NORMAL;
 
    return pp;
}
 
 
tTree*  add_tTree_node(tTree* pp, tTree* node) 
{
    if (node==NULL) return NULL;
    if (pp==NULL) return node;
 
    if (node->ldat.id==TREE_ANCHOR_NODE) node = node->next;
    if (node==NULL) return NULL;
 
    node->prev = pp;
    node->ysis = NULL;
    node->esis = pp->yngr;
 
    if (pp->yngr!=NULL) pp->yngr->ysis = node;
    if (pp->next==NULL) pp->next = node;
    pp->yngr = node;
 
    node->depth = pp->depth + 1;
    pp->num++;
    
    if (node->next!=NULL) {
        node->next->depth = node->depth + 1;
        adjust_tTree_depth(node->next);
    }
 
    return node;
}
 
 
tTree*  add_tTree_node_bydata(tTree* pp, tList_data ldat) 
{
    tTree* pt;
 
    pt = new_tTree_node();
    pt->ldat  = ldat;
    pt->depth = 0;
 
    if (pp==NULL) return pt;
 
    pt->prev = pp;
    pt->ysis = NULL;
    pt->esis = pp->yngr;
 
    if (pp->yngr!=NULL) pp->yngr->ysis = pt;
    if (pp->next==NULL) pp->next = pt;
    pp->yngr = pt;
 
    pt->depth = pp->depth + 1;
    pp->num++;
    
    return pt;
}
 
 
tTree*  add_tTree_node_byBuffer(tTree* pp, int id, int lv, Buffer key, Buffer val, void* ptr, int sz) 
{
    tTree* pt;
    tList_data ldat;
 
    ldat = make_tList_data(id, lv, key, val, ptr, sz);
    pt   = add_tTree_node_bydata(pp, ldat);
 
    return pt;
}
 
 
tTree*  add_tTree_node_bystr(tTree* pp, int id, int lv, const char* key, const char* val, void* ptr, int sz) 
{
    tTree* pt;
    tList_data ldat;
 
    ldat = make_tList_data_bystr(id, lv, key, val, ptr, sz);
    pt   = add_tTree_node_bydata(pp, ldat);
 
    return pt;
}
 
 
tTree*  insert_tTree_node(tTree* pp, tTree* node) 
{
    if (node==NULL) return NULL;
    if (pp==NULL) return node;
 
    if (pp->next!=NULL) pp->next->esis = node;
    node->ysis = pp->next;
    node->esis = NULL;
 
    pp->next = node;
    node->prev = pp;
 
    node->depth = pp->depth + 1;
    pp->num++;
    
    if (node->next!=NULL) {
        node->next->depth = node->depth + 1;
        adjust_tTree_depth(node->next);
    }
 
    return node;
}
 
 
tTree*  insert_tTree_node_bydata(tTree* pp, tList_data ldat) 
{
    tTree* pt;
 
    pt = new_tTree_node();
    pt->ldat  = ldat;
    pt->depth = 0;
 
    if (pp==NULL) return pt;
    //
    if (pp->next!=NULL) pp->next->esis = pt;
    pt->ysis = pp->next;
    pt->esis = NULL;
 
    pp->next = pt;
    pt->prev = pp;
 
    pt->depth = pp->depth + 1;
    pp->num++;
    
    return pt;
}
 
 
tTree*  insert_tTree_node_byBuffer(tTree* pp, int id, int lv, Buffer key, Buffer val, void* ptr, int sz) 
{
    tTree* pt;
    tList_data ldat;
 
    ldat = make_tList_data(id, lv, key, val, ptr, sz);
    pt   = insert_tTree_node_bydata(pp, ldat);
 
    return pt;
}
 
 
tTree*  insert_tTree_node_bystr(tTree* pp, int id, int lv, const char* key, const char* val, void* ptr, int sz) 
{
    tTree* pt;
    tList_data ldat;
 
    ldat = make_tList_data_bystr(id, lv, key, val, ptr, sz);
    pt   = insert_tTree_node_bydata(pp, ldat);
 
    return pt;
}
 
 
tTree*  free_tTree_node(tTree* node) 
{
    if (node==NULL) return NULL;
 
    if (node->next!=NULL) {    // 子ノードを持つ場合
        tTree* ss;
        
        if (node->ldat.id!=TREE_ANCHOR_NODE) {
            node->next->depth--;
            adjust_tTree_depth(node->next);
        }
 
        ss = node->next;
        ss->prev = node->prev;
        while (ss->ysis!=NULL) {
            ss = ss->ysis;
            ss->prev = node->prev;
        } 
 
        ss->ysis = node->ysis;
        node->next->esis = node->esis;
        if (node->ysis!=NULL) node->ysis->esis = ss;
        if (node->esis!=NULL) node->esis->ysis = node->next;
 
        if (node->prev!=NULL) {
            if (node->prev->next==node) node->prev->next = node->next;
            if (node->prev->yngr==node) node->prev->yngr = ss;
        }
    }
 
    else {                    // 子ノードを持たない場合
        if (node->prev!=NULL) {
            if (node->prev->next==node) node->prev->next = node->ysis;
            if (node->prev->yngr==node) node->prev->yngr = node->esis;
        }
        if (node->ysis!=NULL) node->ysis->esis = node->esis;
        if (node->esis!=NULL) node->esis->ysis = node->ysis;
    }
 
    tTree* pp = node->prev;
    clear_tList_data(&(node->ldat));
    if (node->prev!=NULL) node->prev->num += node->num - 1;
 
    return pp;
}
 
 
tTree*  del_tTree_node(tTree** node) 
{
    if (node==NULL || *node==NULL) return NULL;
 
    tTree* pp = free_tTree_node(*node);
    free(*node);
    *node = NULL;
 
    return pp;
}
 
 
tTree*  move_tTree_node(tTree* pp, tTree* node) 
{
    if (node==NULL || pp==NULL) return NULL;
 
    // ノードの切り離し
    if (node->next!=NULL) {    //     子ノードを持つ場合
        tTree* ss;
        node->next->depth--;
        adjust_tTree_depth(node->next);
 
        ss = node->next;
        ss->prev = node->prev;
        while (ss->ysis!=NULL) {
            ss = ss->ysis;
            ss->prev = node->prev;
        } 
 
        ss->ysis = node->ysis;
        node->next->esis = node->esis;
        if (node->ysis!=NULL) node->ysis->esis = ss;
        if (node->esis!=NULL) node->esis->ysis = node->next;
 
        if (node->prev!=NULL) {
            if (node->prev->next==node) node->prev->next = node->next;
            if (node->prev->yngr==node) node->prev->yngr = ss;
        }
    }
    else {                    // 子ノードを持たない場合
        if (node->prev!=NULL) {
            if (node->prev->next==node) node->prev->next = node->ysis;
            if (node->prev->yngr==node) node->prev->yngr = node->esis;
        }
        if (node->ysis!=NULL) node->ysis->esis = node->esis;
        if (node->esis!=NULL) node->esis->ysis = node->ysis;
    }
    if (node->prev!=NULL) node->prev->num += node->num - 1;
 
    // ノードの再結合（移動）
    node->prev = pp;
    node->ysis = NULL;
    node->esis = pp->yngr;
 
    if (pp->yngr!=NULL) pp->yngr->ysis = node;
    if (pp->next==NULL) pp->next = node;
    pp->yngr = node;
 
    node->depth = pp->depth + 1;
    pp->num++;
    
    if (node->next!=NULL) {
        node->next->depth = node->depth + 1;
        adjust_tTree_depth(node->next);
    }
 
    return node;
}
 
 
int  replace_all_tTree_node(tTree* tp, char* key, char* src, char* dst, int len)
{
    int nn = 0;
 
    do { 
        if (ex_strncmp((char*)(tp->ldat).key.buf, (char*)key, len)) {
            if (ex_strncmp((char*)(tp->ldat.val.buf), (char*)src, len)) {
                free_Buffer(&(tp->ldat.val));
                tp->ldat.val = make_Buffer_bystr(dst);
                nn++;
            }
        }
 
        if (tp->next!=NULL) nn += replace_all_tTree_node(tp->next, key, src, dst, len);
 
        tp = tp->ysis;
    } while(tp!=NULL);
 
    return nn;
}
 
 
 
// ツリー操作
//
 
void    del_delete_node_tTree(tTree** pp)
{
    if (pp==NULL || *pp==NULL) return;
 
    tTree* tp = *pp;
    if (tp->ldat.id==TREE_ANCHOR_NODE) {
        tp = tp->next;
    }
    else {
        PRINT_MESG("JBXL::del_delete_node_tTree: WARNING: top node is not ANCHOR node. top addresses are not guaranteed.\n");
    }
    
    _del_delete_node_tTree(&tp);
    return;
}
 
 
void    _del_delete_node_tTree(tTree** pp)
{
    if (pp==NULL || *pp==NULL) return;
 
    tTree* tp = *pp;
    while(tp->esis!=NULL) tp = tp->esis;
 
    while(tp!=NULL) {
        if (tp->next) _del_delete_node_tTree(&(tp->next));
        // delete own
        if (tp->ctrl==TREE_DELETE_NODE || tp->ctrl_alt==TREE_DELETE_NODE) {
            tTree* tt = tp;
            del_tTree_node(&tp);
            tp = tt;
        }
        tp = tp->ysis;
    }
    return;
}
 
 
void    del_non_keep_node_tTree(tTree** pp)
{
    if (pp==NULL || *pp==NULL) return;
 
    tTree* tp = *pp;
    if (tp->ldat.id==TREE_ANCHOR_NODE) {
        tp = tp->next;
    }
    else {
        PRINT_MESG("JBXL::del_non_keep_node_tTree: WARNING: top node is not ANCHOR node. top addresses are not guaranteed.\n");
    }
    
    _del_non_keep_node_tTree(&tp);
    return;
}
 
 
void    _del_non_keep_node_tTree(tTree** pp)
{
    if (pp==NULL || *pp==NULL) return;
 
    tTree* tp = *pp;
    while(tp->esis!=NULL) tp = tp->esis;
 
    while(tp!=NULL) {
        if (tp->next) _del_non_keep_node_tTree(&(tp->next));
        // delete own
        if (tp->ctrl!=TREE_KEEP_NODE && tp->ctrl_alt!=TREE_KEEP_NODE) {
            tTree* tt = tp;
            del_tTree_node(&tp);
            tp = tt;
        }
        tp = tp->ysis;
    }
    return;
}
 
 
tTree*  del_tTree(tTree** pp) 
{
    tTree* pt;
 
    if (pp==NULL || *pp==NULL) return NULL;
 
    // 子ノードの削除
    if ((*pp)->next!=NULL) del_sisters_children_tTree(&((*pp)->next));
 
    // 自分自身の削除
    pt = (*pp)->prev;
    if (pt!=NULL) {
        if (pt->next==*pp) {
            if ((*pp)->ysis!=NULL) pt->next = (*pp)->ysis;
            else                   pt->next = (*pp)->esis;
        }
        if (pt->yngr==*pp) pt->yngr = (*pp)->esis;
        pt->num--;
    }
    if ((*pp)->ysis!=NULL) (*pp)->ysis->esis = (*pp)->esis;
    if ((*pp)->esis!=NULL) (*pp)->esis->ysis = (*pp)->ysis;
 
    clear_tList_data(&((*pp)->ldat));
    free(*pp);
    *pp = NULL;
 
    return pt;
}
 
 
tTree*  del_children_tTree(tTree** pp) 
{    
    if (pp==NULL || *pp==NULL) return NULL;
 
    if ((*pp)->next!=NULL) del_sisters_children_tTree(&((*pp)->next));
 
    (*pp)->num  = 0;
    (*pp)->next = NULL;
    (*pp)->yngr = NULL;
 
    return *pp;
}
 
 
tTree*  del_sisters_tTree(tTree** pp)
{
    tTree* pt;
 
    if (pp==NULL || *pp==NULL) return NULL;
 
    pt = (*pp)->prev;
    if (pt!=NULL) {
        pt->next = NULL;
        pt->yngr = NULL;
        pt->num  = 0;
    }
 
    del_sisters_children_tTree(pp);
 
    return pt;
}
 
 
tTree*  del_sisters_children_tTree(tTree** pp) 
{
    tTree* pm;
    tTree* pt;
 
    if (pp==NULL || *pp==NULL) return NULL;
    pt = (*pp)->prev;
 
    pm = *pp;
    while (pm->esis!=NULL) pm = pm->esis;
    while (pm!=NULL) {
        tTree* pw = pm;
        if (pm->next!=NULL) del_sisters_children_tTree(&(pm->next)); 
        pm = pm->ysis;
        clear_tList_data(&(pw->ldat));
        free(pw);
    }
    *pp = NULL;
 
    pt->next = NULL;
    pt->yngr = NULL;
 
    return pt;
}
 
 
void  del_all_tTree(tTree** pp)
{
    tTree* pm;
 
    if (pp==NULL || *pp==NULL) return;
 
    pm = *pp;
    while (pm->prev!=NULL) pm = pm->prev;
    del_tTree(&pm);
 
    *pp = NULL;
    return;
}
 
 
tTree*  add_tTree(tTree* tp, tTree* tt)
{
    int    nn;
    tTree* tm;
    tTree* tw;
 
    if (tt==NULL) return NULL;
    if (tp==NULL) return tt;
 
    while(tt->esis!=NULL) tt = tt->esis;
    tt->esis = tp->yngr;
    if (tp->yngr!=NULL) tp->yngr->ysis = tt;
    if (tp->next==NULL) tp->next = tt;
 
    nn = 0;
    tm = tw = tt;
    while (tm!=NULL) {
        nn++;
        tm->prev  = tp;
        tm->depth = tp->depth + 1;
 
        if (tm->next!=NULL) {
            tm->next->depth = tm->depth + 1;
            adjust_tTree_depth(tm->next);
        }
        tw = tm;
        tm = tm->ysis;
    }
 
    tp->yngr = tw;
    tp->num += nn;
 
    return tt;
}
 
 
tTree*  div_tTree(tTree* tt)
{
    if (tt==NULL) return NULL;
    if (tt->prev==NULL) return tt;
 
    if (tt->prev->next==tt) tt->prev->next = tt->ysis;
    if (tt->prev->yngr==tt) tt->prev->yngr = tt->esis;
 
    if (tt->ysis!=NULL) tt->ysis->esis = tt->esis;
    if (tt->esis!=NULL) tt->esis->ysis = tt->ysis;
 
    tt->depth = 0;
    if (tt->next!=NULL) {
        tt->next->depth = 1;
        adjust_tTree_depth(tt->next);
    }
 
    tt->prev->num--;
    tt->prev = NULL;
 
    return tt;
}
 
 
tTree*  dup_merge_tTree(tTree* pp, tTree* tp)
{
    if (tp==NULL) return pp;
 
    if (pp!=NULL) {
        if (tp->ctrl!=TREE_NOSIS_NODE) while(tp->esis!=NULL) tp = tp->esis;
        while(tp!=NULL) {
            tTree* pt = dup_tList_node(tp);
            pt->next = pt->prev = pt->yngr = pt->ysis = pt->esis = NULL;
            add_tTree(pp, pt);
            if (tp->next!=NULL) dup_merge_tTree(pt, tp->next);
            if (tp->ctrl!=TREE_NOSIS_NODE) tp = tp->ysis;
            else                           tp = NULL;
        }        
    }
    else {
        pp = new_tTree_anchor_node();
        dup_merge_tTree(pp, tp);
        pp = del_tTree_anchor_node(pp); 
    }
 
    return pp;
}
 
 
void  merge_tTree(tTree* tp, tTree* tt)
{
    tTree* tl;
    tTree* nt;
    tTree* nl;
    int    depth;
 
    if (tp==NULL || tt==NULL) return;
 
    depth = tp->depth;
    tl = tp;
    while (tt!=NULL) {
        if ((tt->ldat).key.buf==NULL) return;
        if (tl!=NULL && (tl->ldat).key.buf==NULL) return;
        while (tl!=NULL && strcmp((char*)((tl->ldat).key.buf), (char*)((tt->ldat).key.buf))) tl = tl->ysis;
 
        nt = tt;
        nl = tl;
        tt = tt->ysis;
 
        if (tl==NULL) {    
            div_tTree(nt);
            add_tTree(tp->prev, nt);
            tl = nt;
            return;
        }
        else if (nl->next!=NULL && nt->next!=NULL) {
            merge_tTree(nl->next, nt->next);
            tl = tl->ysis;
        }
        else {
            tl = tl->ysis;
            exchange_tTree(nl, nt);
        }
    }
 
    tp->depth = depth;
    adjust_tTree_depth(tp);
 
    return;
}
 
 
void  exchange_tTree(tTree* tl, tTree* tt)
{
    int    dt = tt->depth;
    tTree* pt = tt->prev;
    tTree* yt = tt->ysis;
    tTree* et = tt->esis;
 
    if (tl->esis!=NULL) tl->esis->ysis = tt;
    if (tl->ysis!=NULL) tl->ysis->esis = tt;
    if (tl->prev!=NULL) {
        if (tl->prev->next==tl) tl->prev->next = tt;
        if (tl->prev->yngr==tl) tl->prev->yngr = tt;
    }
 
    tt->ysis  = tl->ysis;
    tt->esis  = tl->esis;
    tt->prev  = tl->prev;
    tt->depth = tl->depth;
    if (tt->next!=NULL) {
        tt->next->depth = tt->depth + 1;
        adjust_tTree_depth(tt->next);
    }
 
    if (et!=NULL) et->ysis = tl;
    if (yt!=NULL) yt->esis = tl;
    if (pt!=NULL) {
        if (pt->next==tt) pt->next = tl;
        if (pt->yngr==tt) pt->yngr = tl;
    }
 
    tl->ysis  = yt;
    tl->esis  = et;
    tl->prev  = pt;
    tl->depth = dt;
    if (tl->next!=NULL) {
        tl->next->depth = dt + 1;
        adjust_tTree_depth(tl->next);
    }
}
 
 
void  adjust_tTree_depth(tTree* pp)
{
    int depth;
    tTree* pt;
    
    if (pp==NULL) return;
 
    depth = pp->depth;
    pt = pp;
    while (pt->ysis!=NULL) {
        pt = pt->ysis;
        pt->depth = depth;
        if (pt->next!=NULL) {
            pt->next->depth = depth + 1;
            adjust_tTree_depth(pt->next);
        }
    }
 
    pt = pp;
    while (pt->esis!=NULL) {
        pt = pt->esis;
        pt->depth = depth;
        if (pt->next!=NULL) {
            pt->next->depth = depth + 1;
            adjust_tTree_depth(pt->next);
        }
    }
 
    if (pp->next!=NULL) {
        pp->next->depth = depth + 1;
        adjust_tTree_depth(pp->next);
    }
 
    return;
}
 
 
void  print_tTree_tree(FILE* fp, tTree* pp, const char* space)
{
    if (fp==NULL) fp = stderr;
 
    if (pp!=NULL) {
        if (pp->ctrl!=TREE_NOSIS_NODE) while(pp->esis!=NULL) pp = pp->esis;
        do { 
            int i;
            tList_data ld = pp->ldat;
 
            if (pp->depth>=1) {
                for(i=1; i<pp->depth; i++) fprintf(fp, "%s", space);
                fprintf(fp, " -> ");
            }
            fprintf(fp, "%d: %d %d %s %s\n", pp->depth, ld.id, ld.lv, ld.key.buf, ld.val.buf);
            if (pp->next!=NULL) print_tTree_tree(fp, pp->next, space);
 
            if (pp->ctrl!=TREE_NOSIS_NODE) pp = pp->ysis;
            else                           pp = NULL;
        } while(pp!=NULL);
    }
    else {
        fprintf(fp, "(Tree is NULL)\n");
    }
    fflush(fp);
 
    return;
}
 
 
void  print_tTree(FILE* fp, tTree* pp)
{
    if (fp==NULL) fp = stderr;
 
    if (pp!=NULL) {
        if (pp->ctrl!=TREE_NOSIS_NODE) while(pp->esis!=NULL) pp = pp->esis;
        do { 
            tList_data ld = pp->ldat;
            //
            fprintf(fp, "[%d]: [%d] [%d] [%s] [%s]\n", pp->depth, ld.id, ld.lv, ld.key.buf, ld.val.buf);
            if (pp->next!=NULL) print_tTree(fp, pp->next);
 
            if (pp->ctrl!=TREE_NOSIS_NODE) pp = pp->ysis;
            else                           pp = NULL;
        } while(pp!=NULL);
    }
    else {
        fprintf(fp, "(Tree is NULL)\n");
    }
    fflush(fp);
 
    return;
}
 
 
tTree*  find_tTree_end(tTree* pp)
{
    if (pp==NULL) return NULL;
 
    while(pp->prev!=NULL) pp = pp->prev;    // Top を探す
    while(pp->yngr!=NULL) pp = pp->yngr;
 
    return pp;
}
 
 
int  count_tTree(tTree* pp)
{
    int cnt = 0;
 
    if (pp==NULL) return 0;
    while(pp->esis!=NULL) pp = pp->esis;
 
    do { 
        cnt++;
        if (pp->next!=NULL) cnt += count_tTree(pp->next);
        pp = pp->ysis;
    } while(pp!=NULL);
 
    return cnt;
}
 
 
 
// Pattern Matching
//
 
tTree*  strncmp_tTree(tTree* pp, const char* key, int len, int no)
{
    tTree* pt = NULL;
    int nn = 0;
 
    if (pp==NULL) return NULL;
    if (len<=-3)  return NULL;
    if (no<=0) no = 1;
 
    if (ex_strncmp((char*)(pp->ldat).key.buf, key, len)) {
        nn++;
        if (no==nn) return pp;
    }
    if (pp->next!=NULL) pt = _next_strncmp_vertical_tTree(pp->next, key, len, no, &nn);
 
    return pt;
}
 
 
tTree*  strncasecmp_tTree(tTree* pp, const char* key, int len, int no)
{
    tTree* pt = NULL;
    int nn = 0;
 
    if (pp==NULL) return NULL;
    if (len<=-3)  return NULL;
    if (no<=0) no = 1;
 
    if (ex_strncasecmp((char*)(pp->ldat).key.buf, key, len)) {
        nn++;
        if (no==nn) return pp;
    }
    if (pp->next!=NULL) pt = _next_strncasecmp_vertical_tTree(pp->next, key, len, no, &nn);
 
    return pt;
}
 
 
tTree*  cmp_sisters_tTree(tTree* tp, tTree* tr)
{
    tTree* ta;
    tTree* tb = NULL;
    tTree* ts;
 
    ts = tp;
    while (ts!=NULL){
        ta = ts;
        tb = tr;
        while (ta!=NULL && tb!=NULL) {
            if (ta->ctrl==TREE_ALREADY_FOUND_NODE) break;
            if (tb->ctrl!=TREE_NOCMP_NODE && tb->ctrl!=TREE_NOCMP_COPY_NODE) {
                if ((ta->ldat).key.buf!=NULL && (tb->ldat).key.buf!=NULL) {
                    if (strcmp((char*)((ta->ldat).key.buf), (char*)((tb->ldat).key.buf))) break;
                }
                else break;
            }
            tb->altp = ta;
            ta = ta->ysis;
            tb = tb->ysis;
        }
 
        if (tb==NULL) return ts;
 
        ts = ts->ysis;
    }
    if (tb!=NULL) return NULL;
 
    return ts;
}
 
 
int  check_match_tTree(tTree* tp, tTree* tr)
{
    int  ret;
    tTree* te;
    tTree* ts;
 
    tTree* tt;
    tTree* ta;
    tTree* tb;
 
    if (tp==NULL || tr==NULL) return FALSE;
 
    te = find_tList_end(tr);
 
    ts = tp;
    while (ts!=NULL) {
        tt = cmp_sisters_tTree(ts, tr);      // その階層でキー値が全て一致しているか確認
        if (tt==NULL) return FALSE;          // 一致していなければ，FALSE
        
        ta  = tt;                            // 比べられるツリー
        tb  = tr;                            // 比べるパターン
        ret = TRUE;
        while (tb!=NULL && ret) {
            if (tb->next==NULL) ret = TRUE;
            // ->ta, ->tb->tx: FALSE
            else if (tb->next!=NULL && ta->next==NULL) ret = FALSE;
            // ->ta->xa, ->tb->xb: xaとxbをチェック
            else ret = check_match_tTree(ta->next, tb->next);
 
            ta = ta->ysis;
            tb = tb->ysis;
        }
 
        if (ret) {
            if (tr==te) tt->ctrl = TREE_ALREADY_FOUND_NODE;
            return TRUE;
        }
 
        ts = tt->ysis;
    }
 
    return FALSE;
}
 
 
int  find_match_tTree(tTree* pp, tTree* pt)
{
    int   ret;
    tTree* pm;
 
    pm = pp;
    while(pp!=NULL) {
        ret = check_match_tTree(pp, pt);
        if (ret) return TRUE;
 
        if (pp->next!=NULL) {
            ret = find_match_tTree(pp->next, pt);
            if (ret) {
                _clear_tTree_ctrl(pm);
                return TRUE;
            }
        }
        pp = pp->ysis;
    }
 
    return FALSE;
}
 
 
void  _clear_tTree_ctrl(tTree* pp)
{
    while (pp->esis!=NULL) pp = pp->esis;
 
    while (pp!=NULL) {
        pp->ctrl = TREE_NOCTRL_NODE;
        if (pp->next!=NULL) _clear_tTree_ctrl(pp->next);
        pp = pp->ysis;
    }
}
 
 
tList*  find_match_tTree_endlist(tTree* pp, tTree* pt)
{
    tTree* te;
    tList* lp;
 
    te = find_tTree_end(pt);
    while(pp->esis!=NULL) pp = pp->esis;
 
    lp = _find_match_tTree_endlist_rcsv(pp, pt, te);
    if (lp!=NULL) _clear_tTree_ctrl(pp);
    
    return lp;
}
 
 
tList*  _find_match_tTree_endlist_rcsv(tTree* pp, tTree* pt, tTree* te)
{
    tList* lt = NULL;
    tList* lp = NULL;
 
    while(pp!=NULL) {
        int ret = check_match_tTree(pp, pt);
        if (ret && te->altp!=NULL) {
            tList* lm = new_tList_node();
            lm->altp = te->altp;
            lt = insert_tList(lt, lm);
            if (lp==NULL) lp = lt;
            te->altp = NULL;
        }
            
        if (pp->next!=NULL) {
            tList* lm = _find_match_tTree_endlist_rcsv(pp->next, pt, te);
            if (lm!=NULL) {
                lt = insert_tList(lt, lm);
                if (lp==NULL) lp = lt;
                _clear_tTree_ctrl(pp->next);
            }
        }
    
        if (!ret) pp = pp->ysis;    // 見つかった場合はもう一度．見つからなかった場合へ次へ．
    }
    
    return lp;
}
 
 
int replace_tTree_node(tTree* pp, tTree* pt)
{
    int ret;
 
    if (pp==NULL || pt==NULL) return FALSE;
    while(pp->esis!=NULL) pp = pp->esis;
    
    ret = find_match_tTree(pp, pt);
    if (ret) {
        _copy_tTree_byctrl(pt);
        adjust_tTree_depth(pp);
    }
 
    return ret;
}
 
 
void  _copy_tTree_byctrl(tTree* pt)
{
    while(pt!=NULL) {
        if (pt->altp!=NULL) {
            if (pt->ctrl==TREE_COPY_NODE || pt->ctrl==TREE_NOCMP_COPY_NODE) {
                pt->altp->ldat.id = pt->ldat.id;        
                pt->altp->ldat.lv = pt->ldat.lv;
                pt->altp->ldat.sz = pt->ldat.sz;
 
                if (pt->ldat.key.buf!=NULL) {
                    free_Buffer(&(pt->altp->ldat.key));
                    pt->altp->ldat.key = dup_Buffer(pt->ldat.key);
                }
                if (pt->ldat.val.buf!=NULL) {
                    free_Buffer(&(pt->altp->ldat.val));
                    pt->altp->ldat.val = dup_Buffer(pt->ldat.val);
                }
 
                if (pt->ldat.ptr!=NULL && pt->ldat.sz>0) {
                    if (pt->altp->ldat.ptr!=NULL) free(pt->altp->ldat.ptr);
                    pt->altp->ldat.ptr = (void*)malloc(pt->ldat.sz);
                    if (pt->altp->ldat.ptr!=NULL) memcpy(pt->altp->ldat.ptr, pt->ldat.ptr, pt->ldat.sz);
                }
 
                if (pt->ldat.lst!=NULL) {
                    del_all_tList(&(pt->altp->ldat.lst));
                    pt->altp->ldat.lst = dup_tList(pt->ldat.lst);
                }
            }
        }
 
        if (pt->next!=NULL) _copy_tTree_byctrl(pt->next);
        pt = pt->ysis;
    }
 
    return;
}
 
 
Buffer  get_value_tTree(tTree* pp, tTree* pt)
{
    int fnd;
    Buffer val;
 
    val = init_Buffer();
    if (pp==NULL || pt==NULL) return val;
 
    while(pp->esis!=NULL) pp = pp->esis;
    
    fnd = find_match_tTree(pp, pt);
    if (fnd) {
        tTree* tt = find_tTree_end(pt);
        if (tt->altp!=NULL) {
            val = dup_Buffer(tt->altp->ldat.val);
        }
    }
 
    return val;
}
 
 
 
//
 
tTree*  _next_strncmp_vertical_tTree(tTree* pp, const char* key, int len, int no, int* nn)
{
    do { 
        if (ex_strncmp((char*)(pp->ldat).key.buf, key, len)) {
            (*nn)++;
            if (no==*nn) return pp;
        }
        if (pp->next!=NULL) {
            tTree* tt = _next_strncmp_vertical_tTree(pp->next, key, len, no, nn);
            if (tt!=NULL) return tt;
        }
        pp = pp->ysis;
    } while(pp!=NULL);
 
    return NULL;
}
 
 
tTree*  _next_strncmp_horizon_tTree(tTree* pp, const char* key, int len, int no, int* nn)
{
    do { 
        if (ex_strncmp((char*)(pp->ldat).key.buf, key, len)) {
            (*nn)++;
            if (no==*nn) return pp;
        }
        if (pp->ysis!=NULL) {
            tTree* tt = _next_strncmp_horizon_tTree(pp->ysis, key, len, no, nn);
            if (tt!=NULL) return tt;
        }
        pp = pp->next;
    } while(pp!=NULL);
 
    return NULL;
}
 
 
tTree*  _next_strncasecmp_vertical_tTree(tTree* pp, const char* key, int len, int no, int* nn)
{
    do { 
        if (ex_strncasecmp((char*)(pp->ldat).key.buf, key, len)) {
            (*nn)++;
            if (no==*nn) return pp;
        }
        if (pp->next!=NULL) {
            tTree* tt = _next_strncasecmp_vertical_tTree(pp->next, key, len, no, nn);
            if (tt!=NULL) return tt;
        }
        pp = pp->ysis;
    } while(pp!=NULL);
 
    return NULL;
}
 
 
tTree*  _next_strncasecmp_horizon_tTree(tTree* pp, const char* key, int len, int no, int* nn)
{
    do { 
        if (ex_strncasecmp((char*)(pp->ldat).key.buf, key, len)) {
            (*nn)++;
            if (no==*nn) return pp;
        }
        if (pp->ysis!=NULL) {
            tTree* tt = _next_strncasecmp_horizon_tTree(pp->ysis, key, len, no, nn);
            if (tt!=NULL) return tt;
        }
        pp = pp->next;
    } while(pp!=NULL);
 
    return NULL;
}