JunkBox_Lib: Lib/ttree.c Source File

00001 
00011 #include  "ttree.h"
00012 #include  "jbxl_state.h"
00013 
00014 
00015 
00017 // ノード操作
00018 //
00019 
00026 tTree*  new_tTree_node(void)
00027 {
00028     tTree* pp;
00029 
00030     pp = (tList*)malloc(sizeof(tTree));
00031     if (pp==NULL) return NULL;
00032     memset(pp, 0, sizeof(tTree));
00033     pp->ldat  = init_tList_data();
00034     pp->state = JBXL_NORMAL;
00035 
00036     return pp;
00037 }
00038 
00039 
00040 
00041 tTree*  new_tTree_anchor_node(void)
00042 {
00043     tTree* pp;
00044 
00045     pp = (tList*)malloc(sizeof(tTree));
00046     if (pp==NULL) return NULL;
00047     memset(pp, 0, sizeof(tTree));
00048     pp->ldat    = init_tList_data();
00049     pp->ldat.id = TREE_ANCHOR_NODE;
00050     pp->depth   = -1;
00051     pp->state   = JBXL_STATE_ANCHOR;    // TREE_ANCHOR_NODE と同じ
00052 
00053     return pp;
00054 }
00055 
00056 
00057 
00058 tTree*  del_tTree_anchor_node(tTree* node)
00059 {
00060     tTree* pp = node;
00061 
00062     if (node!=NULL && node->ldat.id==TREE_ANCHOR_NODE) {
00063         pp = node->next;
00064         free_tTree_node(node);
00065         free(node);
00066     }
00067 
00068     return pp;    
00069 }
00070 
00071 
00072 
00080 tTree  make_tTree_node(tList_data data)
00081 {
00082     tTree pp;
00083 
00084     memset(&pp, 0, sizeof(tTree));
00085     pp.ldat  = data;
00086     pp.state = JBXL_NORMAL;
00087 
00088     return pp;
00089 }
00090 
00091 
00092 
00104 tTree*  add_tTree_node(tTree* pp, tTree* node) 
00105 {
00106     if (node==NULL) return NULL;
00107     if (pp==NULL) return node;
00108 
00109     node->prev = pp;
00110     node->ysis = NULL;
00111     node->esis = pp->yngr;
00112 
00113     if (pp->yngr!=NULL) pp->yngr->ysis = node;
00114     if (pp->next==NULL) pp->next = node;
00115     pp->yngr = node;
00116 
00117     node->depth = pp->depth + 1;
00118     pp->num++;
00119     
00120     if (node->next!=NULL) {
00121         node->next->depth = node->depth + 1;
00122         adjust_tTree_depth(node->next);
00123     }
00124 
00125     return node;
00126 }
00127 
00128 
00129 
00140 tTree*  add_tTree_node_bydata(tTree* pp, tList_data ldat) 
00141 {
00142     tTree* pt;
00143 
00144     pt = new_tTree_node();
00145     pt->ldat  = ldat;
00146     pt->depth = 0;
00147 
00148     if (pp==NULL) return pt;
00149 
00150     pt->prev = pp;
00151     pt->ysis = NULL;
00152     pt->esis = pp->yngr;
00153 
00154     if (pp->yngr!=NULL) pp->yngr->ysis = pt;
00155     if (pp->next==NULL) pp->next = pt;
00156     pp->yngr = pt;
00157 
00158     pt->depth = pp->depth + 1;
00159     pp->num++;
00160     
00161     return pt;
00162 }
00163 
00164 
00165 
00181 tTree*  add_tTree_node_byBuffer(tTree* pp, int id, int lv, Buffer key, Buffer val, void* ptr, int sz) 
00182 {
00183     tTree* pt;
00184     tList_data ldat;
00185 
00186     ldat = make_tList_data(id, lv, key, val, ptr, sz);
00187     pt   = add_tTree_node_bydata(pp, ldat);
00188 
00189     return pt;
00190 }
00191 
00192 
00193 
00209 tTree*  add_tTree_node_bystr(tTree* pp, int id, int lv, const char* key, const char* val, void* ptr, int sz) 
00210 {
00211     tTree* pt;
00212     tList_data ldat;
00213 
00214     ldat = make_tList_data_bystr(id, lv, key, val, ptr, sz);
00215     pt   = add_tTree_node_bydata(pp, ldat);
00216 
00217     return pt;
00218 }
00219 
00220 
00221 
00233 tTree*  insert_tTree_node(tTree* pp, tTree* node) 
00234 {
00235     if (node==NULL) return NULL;
00236     if (pp==NULL) return node;
00237 
00238     if (pp->next!=NULL) pp->next->esis = node;
00239     node->ysis = pp->next;
00240     node->esis = NULL;
00241 
00242     pp->next = node;
00243     node->prev = pp;
00244 
00245     node->depth = pp->depth + 1;
00246     pp->num++;
00247     
00248     if (node->next!=NULL) {
00249         node->next->depth = node->depth + 1;
00250         adjust_tTree_depth(node->next);
00251     }
00252 
00253     return node;
00254 }
00255 
00256 
00257 
00268 tTree*  insert_tTree_node_bydata(tTree* pp, tList_data ldat) 
00269 {
00270     tTree* pt;
00271 
00272     pt = new_tTree_node();
00273     pt->ldat  = ldat;
00274     pt->depth = 0;
00275 
00276     if (pp==NULL) return pt;
00277     //
00278     if (pp->next!=NULL) pp->next->esis = pt;
00279     pt->ysis = pp->next;
00280     pt->esis = NULL;
00281 
00282     pp->next = pt;
00283     pt->prev = pp;
00284 
00285     pt->depth = pp->depth + 1;
00286     pp->num++;
00287     
00288     return pt;
00289 }
00290 
00291 
00292 
00308 tTree*  insert_tTree_node_byBuffer(tTree* pp, int id, int lv, Buffer key, Buffer val, void* ptr, int sz) 
00309 {
00310     tTree* pt;
00311     tList_data ldat;
00312 
00313     ldat = make_tList_data(id, lv, key, val, ptr, sz);
00314     pt   = insert_tTree_node_bydata(pp, ldat);
00315 
00316     return pt;
00317 }
00318 
00319 
00335 tTree*  insert_tTree_node_bystr(tTree* pp, int id, int lv, const char* key, const char* val, void* ptr, int sz) 
00336 {
00337     tTree* pt;
00338     tList_data ldat;
00339 
00340     ldat = make_tList_data_bystr(id, lv, key, val, ptr, sz);
00341     pt   = insert_tTree_node_bydata(pp, ldat);
00342 
00343     return pt;
00344 }
00345 
00346 
00347 
00355 tTree*  free_tTree_node(tTree* node) 
00356 {
00357     if (node==NULL) return NULL;
00358 
00359     if (node->next!=NULL) {    // 子ノードを持つ場合
00360         tTree* ss;
00361         
00362         if (node->ldat.id!=TREE_ANCHOR_NODE) {
00363             node->next->depth--;
00364             adjust_tTree_depth(node->next);
00365         }
00366 
00367         ss = node->next;
00368         ss->prev = node->prev;
00369         while (ss->ysis!=NULL) {
00370             ss = ss->ysis;
00371             ss->prev = node->prev;
00372         } 
00373 
00374         ss->ysis = node->ysis;
00375         node->next->esis = node->esis;
00376         if (node->ysis!=NULL) node->ysis->esis = ss;
00377         if (node->esis!=NULL) node->esis->ysis = node->next;
00378 
00379         if (node->prev!=NULL) {
00380             if (node->prev->next==node) node->prev->next = node->next;
00381             if (node->prev->yngr==node) node->prev->yngr = ss;
00382         }
00383     }
00384 
00385     else {                    // 子ノードを持たない場合
00386         if (node->prev!=NULL) {
00387             if (node->prev->next==node) node->prev->next = node->ysis;
00388             if (node->prev->yngr==node) node->prev->yngr = node->esis;
00389         }
00390         if (node->ysis!=NULL) node->ysis->esis = node->esis;
00391         if (node->esis!=NULL) node->esis->ysis = node->ysis;
00392     }
00393 
00394     tTree* pp = node->prev;
00395     free_tList_data(&(node->ldat));
00396     if (node->prev!=NULL) node->prev->num += node->num - 1;
00397 
00398     return pp;
00399 }
00400 
00401 
00402 
00412 tTree*  del_tTree_node(tTree** node) 
00413 {
00414     if (node==NULL || *node==NULL) return NULL;
00415 
00416     tTree* pp = free_tTree_node(*node);
00417     free(*node);
00418     *node = NULL;
00419 
00420     return pp;
00421 }
00422 
00423 
00424 
00438 tTree*  move_tTree_node(tTree* pp, tTree* node) 
00439 {
00440     if (node==NULL || pp==NULL) return NULL;
00441 
00442     // ノードの切り離し
00443     if (node->next!=NULL) {    //     子ノードを持つ場合
00444         tTree* ss;
00445         node->next->depth--;
00446         adjust_tTree_depth(node->next);
00447 
00448         ss = node->next;
00449         ss->prev = node->prev;
00450         while (ss->ysis!=NULL) {
00451             ss = ss->ysis;
00452             ss->prev = node->prev;
00453         } 
00454 
00455         ss->ysis = node->ysis;
00456         node->next->esis = node->esis;
00457         if (node->ysis!=NULL) node->ysis->esis = ss;
00458         if (node->esis!=NULL) node->esis->ysis = node->next;
00459 
00460         if (node->prev!=NULL) {
00461             if (node->prev->next==node) node->prev->next = node->next;
00462             if (node->prev->yngr==node) node->prev->yngr = ss;
00463         }
00464     }
00465     else {                    // 子ノードを持たない場合
00466         if (node->prev!=NULL) {
00467             if (node->prev->next==node) node->prev->next = node->ysis;
00468             if (node->prev->yngr==node) node->prev->yngr = node->esis;
00469         }
00470         if (node->ysis!=NULL) node->ysis->esis = node->esis;
00471         if (node->esis!=NULL) node->esis->ysis = node->ysis;
00472     }
00473     if (node->prev!=NULL) node->prev->num += node->num - 1;
00474 
00475     // ノードの再結合（移動）
00476     node->prev = pp;
00477     node->ysis = NULL;
00478     node->esis = pp->yngr;
00479 
00480     if (pp->yngr!=NULL) pp->yngr->ysis = node;
00481     if (pp->next==NULL) pp->next = node;
00482     pp->yngr = node;
00483 
00484     node->depth = pp->depth + 1;
00485     pp->num++;
00486     
00487     if (node->next!=NULL) {
00488         node->next->depth = node->depth + 1;
00489         adjust_tTree_depth(node->next);
00490     }
00491 
00492     return node;
00493 }
00494 
00495 
00496 
00513 int  replace_all_tTree_node(tTree* tp, char* key, char* src, char* dst, int len)
00514 {
00515     int nn = 0;
00516 
00517     do { 
00518         if (ex_strncmp((char*)(tp->ldat).key.buf, (char*)key, len)) {
00519             if (ex_strncmp((char*)(tp->ldat.val.buf), (char*)src, len)) {
00520                 free_Buffer(&(tp->ldat.val));
00521                 tp->ldat.val = make_Buffer_bystr(dst);
00522                 nn++;
00523             }
00524         }
00525 
00526         if (tp->next!=NULL) nn += replace_all_tTree_node(tp->next, key, src, dst, len);
00527 
00528         tp = tp->ysis;
00529     } while(tp!=NULL);
00530 
00531     return nn;
00532 }
00533 
00534 
00535 
00536 
00538 // ツリー操作
00539 //
00540 
00550 tTree*  del_tTree(tTree** pp) 
00551 {
00552     tTree* pt;
00553 
00554     if (pp==NULL || *pp==NULL) return NULL;
00555 
00556     // 子ノードの削除
00557     if ((*pp)->next!=NULL) del_sisters_children_tTree(&((*pp)->next));
00558 
00559     // 自分自身の削除
00560     pt = (*pp)->prev;
00561     if (pt!=NULL) {
00562         if (pt->next==*pp) pt->next = (*pp)->ysis;
00563         if (pt->yngr==*pp) pt->yngr = (*pp)->esis;
00564         pt->num--;
00565     }
00566     if ((*pp)->ysis!=NULL) (*pp)->ysis->esis = (*pp)->esis;
00567     if ((*pp)->esis!=NULL) (*pp)->esis->ysis = (*pp)->ysis;
00568 
00569     free_tList_data(&((*pp)->ldat));
00570     free(*pp);
00571     *pp = NULL;
00572 
00573     return pt;
00574 }
00575 
00576 
00577 
00586 tTree*  del_children_tTree(tTree** pp) 
00587 {    
00588     if (pp==NULL || *pp==NULL) return NULL;
00589 
00590     if ((*pp)->next!=NULL) del_sisters_children_tTree(&((*pp)->next));
00591 
00592     (*pp)->num  = 0;
00593     (*pp)->next = NULL;
00594     (*pp)->yngr = NULL;
00595 
00596     return *pp;
00597 }
00598 
00599 
00608 tTree*  del_sisters_tTree(tTree** pp)
00609 {
00610     tTree* pt;
00611 
00612     if (pp==NULL || *pp==NULL) return NULL;
00613 
00614     pt = (*pp)->prev;
00615     if (pt!=NULL) {
00616         pt->next = NULL;
00617         pt->yngr = NULL;
00618         pt->num  = 0;
00619     }
00620 
00621     del_sisters_children_tTree(pp);
00622 
00623     return pt;
00624 }
00625 
00626 
00627 
00639 tTree*  del_sisters_children_tTree(tTree** pp) 
00640 {
00641     tTree* pm;
00642     tTree* pt;
00643 
00644     if (pp==NULL || *pp==NULL) return NULL;
00645     pt = (*pp)->prev;
00646 
00647     pm = *pp;
00648     while (pm->esis!=NULL) pm = pm->esis;
00649     while (pm!=NULL) {
00650         tTree* pw = pm;
00651         if (pm->next!=NULL) del_sisters_children_tTree(&(pm->next)); 
00652         pm = pm->ysis;
00653         free_tList_data(&(pw->ldat));
00654         free(pw);
00655     }
00656     *pp = NULL;
00657 
00658     pt->next = NULL;
00659     pt->yngr = NULL;
00660 
00661     return pt;
00662 }
00663 
00664 
00665 
00674 void  del_all_tTree(tTree** pp)
00675 {
00676     tTree* pm;
00677 
00678     if (pp==NULL || *pp==NULL) return;
00679 
00680     pm = *pp;
00681     while (pm->prev!=NULL) pm = pm->prev;
00682     del_tTree(&pm);
00683 
00684     *pp = NULL;
00685     return;
00686 }
00687 
00688 
00689 
00701 tTree*  add_tTree(tTree* tp, tTree* tt)
00702 {
00703     int    nn;
00704     tTree* tm;
00705     tTree* tw;
00706 
00707     if (tt==NULL) return NULL;
00708     if (tp==NULL) return tt;
00709 
00710     while(tt->esis!=NULL) tt = tt->esis;
00711     tt->esis = tp->yngr;
00712     if (tp->yngr!=NULL) tp->yngr->ysis = tt;
00713     if (tp->next==NULL) tp->next = tt;
00714 
00715     nn = 0;
00716     tm = tw = tt;
00717     while (tm!=NULL) {
00718         nn++;
00719         tm->prev  = tp;
00720         tm->depth = tp->depth + 1;
00721 
00722         if (tm->next!=NULL) {
00723             tm->next->depth = tm->depth + 1;
00724             adjust_tTree_depth(tm->next);
00725         }
00726         tw = tm;
00727         tm = tm->ysis;
00728     }
00729 
00730     tp->yngr = tw;
00731     tp->num += nn;
00732 
00733     return tt;
00734 }
00735 
00736 
00737 
00746 tTree*  div_tTree(tTree* tt)
00747 {
00748     if (tt==NULL) return NULL;
00749     if (tt->prev==NULL) return tt;
00750 
00751     if (tt->prev->next==tt) tt->prev->next = tt->ysis;
00752     if (tt->prev->yngr==tt) tt->prev->yngr = tt->esis;
00753 
00754     if (tt->ysis!=NULL) tt->ysis->esis = tt->esis;
00755     if (tt->esis!=NULL) tt->esis->ysis = tt->ysis;
00756 
00757     tt->depth = 0;
00758     if (tt->next!=NULL) {
00759         tt->next->depth = 1;
00760         adjust_tTree_depth(tt->next);
00761     }
00762 
00763     tt->prev->num--;
00764     tt->prev = NULL;
00765 
00766     return tt;
00767 }
00768 
00769 
00770 
00783 tTree*  dup_merge_tTree(tTree* pp, tTree* tp)
00784 {
00785     if (tp==NULL) return pp;
00786 
00787     if (pp!=NULL) {
00788         if (tp->ctrl!=TREE_NOSIS_NODE) while(tp->esis!=NULL) tp = tp->esis;
00789         while(tp!=NULL) {
00790             tTree* pt = dup_tList_node(tp);
00791             pt->next = pt->prev = pt->yngr = pt->ysis = pt->esis = NULL;
00792             add_tTree(pp, pt);
00793             if (tp->next!=NULL) dup_merge_tTree(pt, tp->next);
00794             if (tp->ctrl!=TREE_NOSIS_NODE) tp = tp->ysis;
00795             else                           tp = NULL;
00796         }        
00797     }
00798     else {
00799         pp = new_tTree_anchor_node();
00800         dup_merge_tTree(pp, tp);
00801         pp = del_tTree_anchor_node(pp); 
00802     }
00803 
00804     return pp;
00805 }
00806 
00807 
00808 
00843 void  merge_tTree(tTree* tp, tTree* tt)
00844 {
00845     tTree* tl;
00846     tTree* nt;
00847     tTree* nl;
00848     int    depth;
00849 
00850     if (tp==NULL || tt==NULL) return;
00851 
00852     depth = tp->depth;
00853     tl = tp;
00854     while (tt!=NULL) {
00855         if ((tt->ldat).key.buf==NULL) return;
00856         if (tl!=NULL && (tl->ldat).key.buf==NULL) return;
00857         while (tl!=NULL && strcmp((char*)((tl->ldat).key.buf), (char*)((tt->ldat).key.buf))) tl = tl->ysis;
00858 
00859         nt = tt;
00860         nl = tl;
00861         tt = tt->ysis;
00862 
00863         if (tl==NULL) {    
00864             div_tTree(nt);
00865             add_tTree(tp->prev, nt);
00866             tl = nt;
00867             return;
00868         }
00869         else if (nl->next!=NULL && nt->next!=NULL) {
00870             merge_tTree(nl->next, nt->next);
00871             tl = tl->ysis;
00872         }
00873         else {
00874             tl = tl->ysis;
00875             exchange_tTree(nl, nt);
00876         }
00877     }
00878 
00879     tp->depth = depth;
00880     adjust_tTree_depth(tp);
00881 
00882     return;
00883 }
00884 
00885 
00886 
00895 void  exchange_tTree(tTree* tl, tTree* tt)
00896 {
00897     int    dt = tt->depth;
00898     tTree* pt = tt->prev;
00899     tTree* yt = tt->ysis;
00900     tTree* et = tt->esis;
00901 
00902     if (tl->esis!=NULL) tl->esis->ysis = tt;
00903     if (tl->ysis!=NULL) tl->ysis->esis = tt;
00904     if (tl->prev!=NULL) {
00905         if (tl->prev->next==tl) tl->prev->next = tt;
00906         if (tl->prev->yngr==tl) tl->prev->yngr = tt;
00907     }
00908 
00909     tt->ysis  = tl->ysis;
00910     tt->esis  = tl->esis;
00911     tt->prev  = tl->prev;
00912     tt->depth = tl->depth;
00913     if (tt->next!=NULL) {
00914         tt->next->depth = tt->depth + 1;
00915         adjust_tTree_depth(tt->next);
00916     }
00917 
00918     if (et!=NULL) et->ysis = tl;
00919     if (yt!=NULL) yt->esis = tl;
00920     if (pt!=NULL) {
00921         if (pt->next==tt) pt->next = tl;
00922         if (pt->yngr==tt) pt->yngr = tl;
00923     }
00924 
00925     tl->ysis  = yt;
00926     tl->esis  = et;
00927     tl->prev  = pt;
00928     tl->depth = dt;
00929     if (tl->next!=NULL) {
00930         tl->next->depth = dt + 1;
00931         adjust_tTree_depth(tl->next);
00932     }
00933 }
00934 
00935 
00936 
00944 void  adjust_tTree_depth(tTree* pp)
00945 {
00946     int depth;
00947     tTree* pt;
00948     
00949     if (pp==NULL) return;
00950 
00951     depth = pp->depth;
00952     pt = pp;
00953     while (pt->ysis!=NULL) {
00954         pt = pt->ysis;
00955         pt->depth = depth;
00956         if (pt->next!=NULL) {
00957             pt->next->depth = depth + 1;
00958             adjust_tTree_depth(pt->next);
00959         }
00960     }
00961 
00962     pt = pp;
00963     while (pt->esis!=NULL) {
00964         pt = pt->esis;
00965         pt->depth = depth;
00966         if (pt->next!=NULL) {
00967             pt->next->depth = depth + 1;
00968             adjust_tTree_depth(pt->next);
00969         }
00970     }
00971 
00972     if (pp->next!=NULL) {
00973         pp->next->depth = depth + 1;
00974         adjust_tTree_depth(pp->next);
00975     }
00976 
00977     return;
00978 }
00979 
00980 
00981 
00992 void  print_tTree_tree(FILE* fp, tTree* pp, const char* space)
00993 {
00994     if (fp==NULL) fp = stderr;
00995 
00996     if (pp!=NULL) {
00997         if (pp->ctrl!=TREE_NOSIS_NODE) while(pp->esis!=NULL) pp = pp->esis;
00998         do { 
00999             int i;
01000             tList_data ld = pp->ldat;
01001 
01002             if (pp->depth>=1) {
01003                 for(i=1; i<pp->depth; i++) fprintf(fp, "%s", space);
01004                 fprintf(fp, " -> ");
01005             }
01006             fprintf(fp, "%d: %d %d %s %s\n", pp->depth, ld.id, ld.lv, ld.key.buf, ld.val.buf);
01007             if (pp->next!=NULL) print_tTree_tree(fp, pp->next, space);
01008 
01009             if (pp->ctrl!=TREE_NOSIS_NODE) pp = pp->ysis;
01010             else                           pp = NULL;
01011         } while(pp!=NULL);
01012     }
01013     else {
01014         fprintf(fp, "(Tree is NULL)\n");
01015     }
01016     fflush(fp);
01017 
01018     return;
01019 }
01020 
01021 
01022 
01032 void  print_tTree(FILE* fp, tTree* pp)
01033 {
01034     if (fp==NULL) fp = stderr;
01035 
01036     if (pp!=NULL) {
01037         if (pp->ctrl!=TREE_NOSIS_NODE) while(pp->esis!=NULL) pp = pp->esis;
01038         do { 
01039             tList_data ld = pp->ldat;
01040             //
01041             fprintf(fp, "[%d]: [%d] [%d] [%s] [%s]\n", pp->depth, ld.id, ld.lv, ld.key.buf, ld.val.buf);
01042             if (pp->next!=NULL) print_tTree(fp, pp->next);
01043 
01044             if (pp->ctrl!=TREE_NOSIS_NODE) pp = pp->ysis;
01045             else                           pp = NULL;
01046         } while(pp!=NULL);
01047     }
01048     else {
01049         fprintf(fp, "(Tree is NULL)\n");
01050     }
01051     fflush(fp);
01052 
01053     return;
01054 }
01055 
01056 
01057 
01063 tTree*  find_tTree_end(tTree* pp)
01064 {
01065     if (pp==NULL) return NULL;
01066 
01067     while(pp->prev!=NULL) pp = pp->prev;    // Top を探す
01068     while(pp->yngr!=NULL) pp = pp->yngr;
01069 
01070     return pp;
01071 }
01072 
01073 
01074 
01083 int  count_tTree(tTree* pp)
01084 {
01085     int cnt = 0;
01086 
01087     if (pp==NULL) return 0;
01088     while(pp->esis!=NULL) pp = pp->esis;
01089 
01090     do { 
01091         cnt++;
01092         if (pp->next!=NULL) cnt += count_tTree(pp->next);
01093         pp = pp->ysis;
01094     } while(pp!=NULL);
01095 
01096     return cnt;
01097 }
01098 
01099 
01100 
01101 
01103 // Pattern Matching
01104 //
01105 
01123 tTree*  strncmp_tTree(tTree* pp, const char* key, int len, int no)
01124 {
01125     tTree* pt = NULL;
01126     int nn = 0;
01127 
01128     if (pp==NULL) return NULL;
01129     if (len<=-3)  return NULL;
01130     if (no<=0) no = 1;
01131 
01132     if (ex_strncmp((char*)(pp->ldat).key.buf, key, len)) {
01133         nn++;
01134         if (no==nn) return pp;
01135     }
01136     if (pp->next!=NULL) pt = next_strncmp_vertical_tTree(pp->next, key, len, no, &nn);
01137 
01138     return pt;
01139 }
01140 
01141 
01142 
01160 tTree*  strncasecmp_tTree(tTree* pp, const char* key, int len, int no)
01161 {
01162     tTree* pt = NULL;
01163     int nn = 0;
01164 
01165     if (pp==NULL) return NULL;
01166     if (len<=-3)  return NULL;
01167     if (no<=0) no = 1;
01168 
01169     if (ex_strncasecmp((char*)(pp->ldat).key.buf, key, len)) {
01170         nn++;
01171         if (no==nn) return pp;
01172     }
01173     if (pp->next!=NULL) pt = next_strncasecmp_vertical_tTree(pp->next, key, len, no, &nn);
01174 
01175     return pt;
01176 }
01177 
01178 
01179 
01209 tTree*  cmp_sisters_tTree(tTree* tp, tTree* tr)
01210 {
01211     tTree* ta;
01212     tTree* tb = NULL;
01213     tTree* ts;
01214 
01215     ts = tp;
01216     while (ts!=NULL){
01217         ta = ts;
01218         tb = tr;
01219         while (ta!=NULL && tb!=NULL) {
01220             if (ta->ctrl==TREE_ALREADY_FOUND_NODE) break;
01221             if (tb->ctrl!=TREE_NOCMP_NODE && tb->ctrl!=TREE_NOCMP_COPY_NODE) {
01222                 if ((ta->ldat).key.buf!=NULL && (tb->ldat).key.buf!=NULL) {
01223                     if (strcmp((char*)((ta->ldat).key.buf), (char*)((tb->ldat).key.buf))) break;
01224                 }
01225                 else break;
01226             }
01227             tb->altp = ta;
01228             ta = ta->ysis;
01229             tb = tb->ysis;
01230         }
01231 
01232         if (tb==NULL) return ts;
01233 
01234         ts = ts->ysis;
01235     }
01236     if (tb!=NULL) return NULL;
01237 
01238     return ts;
01239 }
01240 
01241 
01242 
01261 int  check_match_tTree(tTree* tp, tTree* tr)
01262 {
01263     int  ret;
01264     tTree* te;
01265     tTree* ts;
01266 
01267     tTree* tt;
01268     tTree* ta;
01269     tTree* tb;
01270 
01271     if (tp==NULL || tr==NULL) return FALSE;
01272 
01273     te = find_tList_end(tr);
01274 
01275     ts = tp;
01276     while (ts!=NULL) {
01277         tt = cmp_sisters_tTree(ts, tr);      // その階層でキー値が全て一致しているか確認
01278         if (tt==NULL) return FALSE;          // 一致していなければ，FALSE
01279         
01280         ta  = tt;                            // 比べられるツリー
01281         tb  = tr;                            // 比べるパターン
01282         ret = TRUE;
01283         while (tb!=NULL && ret) {
01284             if (tb->next==NULL) ret = TRUE;
01285             // ->ta, ->tb->tx: FALSE
01286             else if (tb->next!=NULL && ta->next==NULL) ret = FALSE;
01287             // ->ta->xa, ->tb->xb: xaとxbをチェック
01288             else ret = check_match_tTree(ta->next, tb->next);
01289 
01290             ta = ta->ysis;
01291             tb = tb->ysis;
01292         }
01293 
01294         if (ret) {
01295             if (tr==te) tt->ctrl = TREE_ALREADY_FOUND_NODE;
01296             return TRUE;
01297         }
01298 
01299         ts = tt->ysis;
01300     }
01301 
01302     return FALSE;
01303 }
01304 
01305 
01306 
01327 int  find_match_tTree(tTree* pp, tTree* pt)
01328 {
01329     int   ret;
01330     tTree* pm;
01331 
01332     pm = pp;
01333     while(pp!=NULL) {
01334         ret = check_match_tTree(pp, pt);
01335         if (ret) return TRUE;
01336 
01337         if (pp->next!=NULL) {
01338             ret = find_match_tTree(pp->next, pt);
01339             if (ret) {
01340                 clear_tTree_ctrl(pm);
01341                 return TRUE;
01342             }
01343         }
01344         pp = pp->ysis;
01345     }
01346 
01347     return FALSE;
01348 }
01349 
01350 
01351 
01357 void  clear_tTree_ctrl(tTree* pp)
01358 {
01359     while (pp->esis!=NULL) pp = pp->esis;
01360 
01361     while (pp!=NULL) {
01362         pp->ctrl = TREE_NOCTRL_NODE;
01363         if (pp->next!=NULL) clear_tTree_ctrl(pp->next);
01364         pp = pp->ysis;
01365     }
01366 }
01367 
01368 
01369 
01384 tList*  find_match_tTree_endlist(tTree* pp, tTree* pt)
01385 {
01386     tTree* te;
01387     tList* lp;
01388 
01389     te = find_tTree_end(pt);
01390     while(pp->esis!=NULL) pp = pp->esis;
01391 
01392     lp = find_match_tTree_endlist_rcsv(pp, pt, te);
01393     if (lp!=NULL) clear_tTree_ctrl(pp);
01394     
01395     return lp;
01396 }
01397 
01398 
01399 
01405 tList*  find_match_tTree_endlist_rcsv(tTree* pp, tTree* pt, tTree* te)
01406 {
01407     tList* lt = NULL;
01408     tList* lp = NULL;
01409 
01410     while(pp!=NULL) {
01411         int ret = check_match_tTree(pp, pt);
01412         if (ret && te->altp!=NULL) {
01413             tList* lm = new_tList_node();
01414             lm->altp = te->altp;
01415             lt = insert_tList(lt, lm);
01416             if (lp==NULL) lp = lt;
01417             te->altp = NULL;
01418         }
01419             
01420         if (pp->next!=NULL) {
01421             tList* lm = find_match_tTree_endlist_rcsv(pp->next, pt, te);
01422             if (lm!=NULL) {
01423                 lt = insert_tList(lt, lm);
01424                 if (lp==NULL) lp = lt;
01425                 clear_tTree_ctrl(pp->next);
01426             }
01427         }
01428     
01429         if (!ret) pp = pp->ysis;    // 見つかった場合はもう一度．見つからなかった場合へ次へ．
01430     }
01431     
01432     return lp;
01433 }
01434 
01435 
01436 
01455 int replace_tTree_node(tTree* pp, tTree* pt)
01456 {
01457     int ret;
01458 
01459     if (pp==NULL || pt==NULL) return FALSE;
01460     while(pp->esis!=NULL) pp = pp->esis;
01461     
01462     ret = find_match_tTree(pp, pt);
01463     if (ret) {
01464         copy_tTree_byctrl(pt);
01465         adjust_tTree_depth(pp);
01466     }
01467 
01468     return ret;
01469 }
01470 
01471 
01472 
01482 void  copy_tTree_byctrl(tTree* pt)
01483 {
01484     while(pt!=NULL) {
01485         if (pt->altp!=NULL) {
01486             if (pt->ctrl==TREE_COPY_NODE || pt->ctrl==TREE_NOCMP_COPY_NODE) {
01487                 pt->altp->ldat.id = pt->ldat.id;        
01488                 pt->altp->ldat.lv = pt->ldat.lv;
01489                 pt->altp->ldat.sz = pt->ldat.sz;
01490 
01491                 if (pt->ldat.key.buf!=NULL) {
01492                     free_Buffer(&(pt->altp->ldat.key));
01493                     pt->altp->ldat.key = dup_Buffer(pt->ldat.key);
01494                 }
01495                 if (pt->ldat.val.buf!=NULL) {
01496                     free_Buffer(&(pt->altp->ldat.val));
01497                     pt->altp->ldat.val = dup_Buffer(pt->ldat.val);
01498                 }
01499 
01500                 if (pt->ldat.ptr!=NULL && pt->ldat.sz>0) {
01501                     if (pt->altp->ldat.ptr!=NULL) free(pt->altp->ldat.ptr);
01502                     pt->altp->ldat.ptr = (void*)malloc(pt->ldat.sz);
01503                     if (pt->altp->ldat.ptr!=NULL) memcpy(pt->altp->ldat.ptr, pt->ldat.ptr, pt->ldat.sz);
01504                 }
01505 
01506                 if (pt->ldat.lst!=NULL) {
01507                     del_all_tList(&(pt->altp->ldat.lst));
01508                     pt->altp->ldat.lst = dup_tList(pt->ldat.lst);
01509                 }
01510             }
01511         }
01512 
01513         if (pt->next!=NULL) copy_tTree_byctrl(pt->next);
01514         pt = pt->ysis;
01515     }
01516 
01517     return;
01518 }
01519 
01520 
01521 
01542 Buffer  get_value_tTree(tTree* pp, tTree* pt)
01543 {
01544     int fnd;
01545     Buffer val;
01546 
01547     val = init_Buffer();
01548     if (pp==NULL || pt==NULL) return val;
01549 
01550     while(pp->esis!=NULL) pp = pp->esis;
01551     
01552     fnd = find_match_tTree(pp, pt);
01553     if (fnd) {
01554         tTree* tt = find_tTree_end(pt);
01555         if (tt->altp!=NULL) {
01556             val = dup_Buffer(tt->altp->ldat.val);
01557         }
01558     }
01559 
01560     return val;
01561 }
01562 
01563 
01564 
01565 
01567 //
01568 
01574 tTree*  next_strncmp_vertical_tTree(tTree* pp, const char* key, int len, int no, int* nn)
01575 {
01576     do { 
01577         if (ex_strncmp((char*)(pp->ldat).key.buf, key, len)) {
01578             (*nn)++;
01579             if (no==*nn) return pp;
01580         }
01581         if (pp->next!=NULL) {
01582             tTree* tt = next_strncmp_vertical_tTree(pp->next, key, len, no, nn);
01583             if (tt!=NULL) return tt;
01584         }
01585         pp = pp->ysis;
01586     } while(pp!=NULL);
01587 
01588     return NULL;
01589 }
01590 
01591 
01592 
01598 tTree*  next_strncmp_horizon_tTree(tTree* pp, const char* key, int len, int no, int* nn)
01599 {
01600     do { 
01601         if (ex_strncmp((char*)(pp->ldat).key.buf, key, len)) {
01602             (*nn)++;
01603             if (no==*nn) return pp;
01604         }
01605         if (pp->ysis!=NULL) {
01606             tTree* tt = next_strncmp_horizon_tTree(pp->ysis, key, len, no, nn);
01607             if (tt!=NULL) return tt;
01608         }
01609         pp = pp->next;
01610     } while(pp!=NULL);
01611 
01612     return NULL;
01613 }
01614 
01615 
01616 
01622 tTree*  next_strncasecmp_vertical_tTree(tTree* pp, const char* key, int len, int no, int* nn)
01623 {
01624     do { 
01625         if (ex_strncasecmp((char*)(pp->ldat).key.buf, key, len)) {
01626             (*nn)++;
01627             if (no==*nn) return pp;
01628         }
01629         if (pp->next!=NULL) {
01630             tTree* tt = next_strncasecmp_vertical_tTree(pp->next, key, len, no, nn);
01631             if (tt!=NULL) return tt;
01632         }
01633         pp = pp->ysis;
01634     } while(pp!=NULL);
01635 
01636     return NULL;
01637 }
01638 
01639 
01640 
01646 tTree*  next_strncasecmp_horizon_tTree(tTree* pp, const char* key, int len, int no, int* nn)
01647 {
01648     do { 
01649         if (ex_strncasecmp((char*)(pp->ldat).key.buf, key, len)) {
01650             (*nn)++;
01651             if (no==*nn) return pp;
01652         }
01653         if (pp->ysis!=NULL) {
01654             tTree* tt = next_strncasecmp_horizon_tTree(pp->ysis, key, len, no, nn);
01655             if (tt!=NULL) return tt;
01656         }
01657         pp = pp->next;
01658     } while(pp!=NULL);
01659 
01660     return NULL;
01661 }
01662 
01663 
01664