Lib/ttree.c File Reference

Tiny Tree Graph 構造ライブラリ. More...

#include "ttree.h"
#include "jbxl_state.h"

Include dependency graph for ttree.c:

Functions
tTree *	new_tTree_node (void)
	ツリー用の空ノードを動的に生成．
tTree *	new_tTree_anchor_node (void)
	ツリー用の ANCHORノードを動的に生成．
tTree *	del_tTree_anchor_node (tTree *node)
	ANCHORノードを削除して，TOP（長女）へのポインターを返す．.
tTree	make_tTree_node (tList_data data)
	ツリー用ノードを静的に作成．
tTree *	add_tTree_node (tTree pp, tTree node)
	ツリー ppへノード nodeを末っ子として追加．
tTree *	add_tTree_node_bydata (tTree *pp, tList_data ldat)
	データから Treeノードをつくり出し,それを ppの子ノード（末っ子）として追加．
tTree *	add_tTree_node_byBuffer (tTree pp, int id, int lv, Buffer key, Buffer val, void ptr, int sz)
	ノードを末っ子としてリストに追加．
tTree *	add_tTree_node_bystr (tTree pp, int id, int lv, const char key, const char val, void ptr, int sz)
	ノードを末っ子としてリストに追加．
tTree *	insert_tTree_node (tTree pp, tTree node)
	ツリー ppへノード nodeを長子として追加．
tTree *	insert_tTree_node_bydata (tTree *pp, tList_data ldat)
	ノードをつくり出し,それを ppの子ノード（長子）として追加．
tTree *	insert_tTree_node_byBuffer (tTree pp, int id, int lv, Buffer key, Buffer val, void ptr, int sz)
	ノードを長子としてリストに追加．
tTree *	insert_tTree_node_bystr (tTree pp, int id, int lv, const char key, const char val, void ptr, int sz)
	ノードを長子としてリストに追加．
tTree *	free_tTree_node (tTree *node)
	ツリーノードの解放．解放されたノードが子ノードを持つ場合は，その子ノードを格上げする（木構造を詰める）
tTree *	del_tTree_node (tTree **node)
	ツリーノードの削除．削除されたノードが子ノードを持つ場合は，その子ノードを格上げする（木構造を詰める）
tTree *	move_tTree_node (tTree pp, tTree node)
	nodeを現在のツリーから切り離し，ppへ移動する．
int	replace_all_tTree_node (tTree tp, char key, char src, char dst, int len)
	対象の全てのノードのノード値を dst に書き換える．
tTree *	del_tTree (tTree **pp)
	指定したノード以下のツリーを削除する．
tTree *	del_children_tTree (tTree **pp)
	指定したノードの子ツリーを削除する．指定したノードは削除しない．
tTree *	del_sisters_tTree (tTree **pp)
	指定したノード以下のXMLツリー（ppの姉妹を含む）を削除する．
tTree *	del_sisters_children_tTree (tTree **pp)
	指定したノードの姉妹ツリー，子ツリーを削除する．
void	del_all_tTree (tTree **pp)
	ツリーの全ノードの削除．ポインタ ppのノードを含むツリー全体を削除する．
tTree *	add_tTree (tTree tp, tTree tt)
	ツリー tpへツリー ttを追加．
tTree *	div_tTree (tTree *tt)
	ツリー tp からツリー ttを分離する．
tTree *	dup_merge_tTree (tTree pp, tTree tp)
	ツリー ppの直下にツリー tpを複製する．
void	merge_tTree (tTree tp, tTree tt)
	ツリー tp にツリー tt を結合する．結合後，tt の内容は壊れる(tpとノードを交換した形になる)．
void	exchange_tTree (tTree tl, tTree tt)
	ツリー tlとツリー ttを交換する．
void	adjust_tTree_depth (tTree *pp)
	指定したノード ppを基準にして，木の深さを測り直す
void	print_tTree_tree (FILE fp, tTree pp, const char *space)
	ツリーの表示．ポインタノードのキー部のバッファをfpに表示する．
void	print_tTree (FILE fp, tTree pp)
	ツリーの表示．ポインタノードのキー部のバッファをfpに表示する．
tTree *	find_tTree_end (tTree *pp)
	ツリーの最終ノードを見つける．
int	count_tTree (tTree *pp)
	ツリーの ppノード以降のノードの数を数える．
tTree *	strncmp_tTree (tTree pp, const char key, int len, int no)
	ツリーノードのキー値のサーチ
tTree *	strncasecmp_tTree (tTree pp, const char key, int len, int no)
	ツリーノードのキー値のサーチ．大文字小文字を無視する．
tTree *	cmp_sisters_tTree (tTree tp, tTree tr)
	tpの姉妹ノードが trの姉妹ノードと同じキー値を持っているかどうかを検査する．
int	check_match_tTree (tTree tp, tTree tr)
	tpが trと同じパターン(キー値)を持っているかどうかを検査する．
int	find_match_tTree (tTree pp, tTree pt)
	ツリー pp内でツリー ptと同じパターンの枝を探す．
void	clear_tTree_ctrl (tTree *pp)
	ppツリーの ctrlをクリアする．
tList *	find_match_tTree_endlist (tTree pp, tTree pt)
	pp内で ptと同じパターンの枝を全て探して，その枝の最後のノードへの情報を返す．
tList *	find_match_tTree_endlist_rcsv (tTree pp, tTree pt, tTree *te)
	find_match_tTree_endlist() の補助関数
int	replace_tTree_node (tTree pp, tTree pt)
	同じパターンの枝を検索し，ptのノードの属性で置き換える．
void	copy_tTree_byctrl (tTree *pt)
	同じパターンの枝を検索し，ptのノードの属性をコピーする．
Buffer	get_value_tTree (tTree pp, tTree pt)
	同じパターンの枝を検索し，一致した枝があれば，その枝の最後のノードの値を返す．
tTree *	next_strncmp_vertical_tTree (tTree pp, const char key, int len, int no, int *nn)
	tTree 検索用補助関数．vertical は縦方向探索
tTree *	next_strncmp_horizon_tTree (tTree pp, const char key, int len, int no, int *nn)
	tTree 検索用補助関数．horizon は擬似的な横方向探索
tTree *	next_strncasecmp_vertical_tTree (tTree pp, const char key, int len, int no, int *nn)
	tTree 検索用補助関数．vertical は縦方向探索
tTree *	next_strncasecmp_horizon_tTree (tTree pp, const char key, int len, int no, int *nn)
	tTree 検索用補助関数．horizon は擬似的な横方向探索

Detailed Description

Version:

Author:: Fumi.Iseki (C)

Date:: 2008 2/1

Definition in file ttree.c.

Function Documentation

tTree* add_tTree	(	tTree *	tp,
		tTree *	tt
	)

tTree* add_tTree(tTree* tp, tTree* tt)

ツリー tpへツリー ttを追加．
add_tTree_node() との相違は，add_tTree()が先頭(tt)の姉妹ノードもツリー tpに追加する点にある．

Parameters:

	tp	追加するツリーの親となるノードへのポインタ．
	tt	追加するツリーへのポインタ．

Returns:: 追加したツリーのノードへのポインタ．失敗した場合は NULL

Definition at line 701 of file ttree.c.

References adjust_tTree_depth().

Referenced by dup_merge_tTree(), insert_json_nodes(), join_json(), and merge_tTree().

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

tTree* add_tTree_node	(	tTree *	pp,
		tTree *	node
	)

tTree* add_tTree_node(tTree* pp, tTree* node)

ツリー ppへノード nodeを追加．ポインタ ppが指すノードの子（末っ子）ノードとして node（そのもの）を追加する．
node が子ノードを持つ場合は，それも追加される．
node が姉妹ノードを持っていてもそれらは無視する（処理しない）．

Parameters:

	pp	追加するノードの親となるノードへのポインタ．
	node	追加するノードへのポインタ．node->next 以下がツリーでも良い．

Returns:: 追加したノードへのポインタ．失敗した場合は NULL

Definition at line 104 of file ttree.c.

References adjust_tTree_depth().

Referenced by json_array_parse(), and json_parse_prop().

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

tTree* add_tTree_node_byBuffer	(	tTree *	pp,
		int	id,
		int	lv,
		Buffer	key,
		Buffer	val,
		void *	ptr,
		int	sz
	)

tTree* add_tTree_node_byBuffer(tTree* pp, int id, int lv, Buffer key, Buffer val, void* ptr, int sz)

データからノードをつくり出し,それを末っ子としてリストに追加．
リストポインタ ppが指すノードの後につくり出したノードを挿入する．

Parameters:

	pp	追加する場所の手前のノードへのポインタ．
	id	追加するデータ．
	lv	追加するデータ．
	key	追加するデータ．複製
	val	追加するデータ．複製
	ptr	汎用データへのポインタ複製
	sz	*ptr のサイズ

Returns:: 追加したノードへのポインタ．

Definition at line 181 of file ttree.c.

References add_tTree_node_bydata(), and make_tList_data().

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 }

Here is the call graph for this function:

tTree* add_tTree_node_bydata	(	tTree *	pp,
		tList_data	ldat
	)

tTree* add_tTree_node_bydata(tTree* pp, tList_data ldat)

データから Treeノードをつくり出し,それを ppの子ノード（末っ子）として追加．
ldat は指定されたものがそのまま使用される．

Parameters:

	pp	追加するノードの親となるノードへのポインタ．
	ldat	追加するノードデータ．このデータがそのまま使用される．

Returns:: 追加したノードへのポインタ．

Definition at line 140 of file ttree.c.

References new_tTree_node().

Referenced by add_tTree_node_byBuffer(), and add_tTree_node_bystr().

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

tTree* add_tTree_node_bystr	(	tTree *	pp,
		int	id,
		int	lv,
		const char *	key,
		const char *	val,
		void *	ptr,
		int	sz
	)

tTree* add_tTree_node_bystr(tTree* pp, int id, int lv, const char* key, const char* val, void* ptr, int sz)

データからノードをつくり出し,それを末っ子としてリストに追加．
リストポインタ ppが指すノードの後につくり出したノードを挿入する．

Parameters:

	pp	追加する場所の手前のノードへのポインタ．
	id	追加するデータ．
	lv	追加するデータ．
	key	追加するデータ．複製
	val	追加するデータ．複製
	ptr	汎用データへのポインタ複製
	sz	*ptr のサイズ

Returns:: 追加したノードへのポインタ．

Definition at line 209 of file ttree.c.

References add_tTree_node_bydata(), and make_tList_data_bystr().

Referenced by add_xml_content(), add_xml_node(), bvh_parse_hierarchy(), llsd_bin_main_parse(), and xml_main_parse().

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

void adjust_tTree_depth ( tTree * pp )

void adjust_tTree_depth(tTree* pp)

指定したノード ppを基準にして，木の深さを測り直す

Parameters:

pp

基準となるノードへのポインタ

Definition at line 944 of file ttree.c.

References adjust_tTree_depth().

Referenced by add_tTree(), add_tTree_node(), adjust_tTree_depth(), close_xml(), div_tTree(), exchange_tTree(), free_tTree_node(), insert_tTree_node(), merge_tTree(), move_tTree_node(), replace_tTree_node(), and set_xml_end_node().

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

int check_match_tTree	(	tTree *	tp,
		tTree *	tr
	)

int check_match_tTree(tTree* tp, tTree* tr)

ツリー tpがツリー trと同じパターン(キー値)を持っているかどうかを検査する．
tp のトップと tr のトップはキー値が一致している必要がある．一致していなければ，同じパターンは無しとする．
ただし，tr->ctrl が TREE_NOCMP_NODE または TREE_NOCMP_COPY_NODE のノードは比べない(常に一致とする)．

一度見つけた tpの枝の最後のノードに対しては ctrlを TREE_ALREADY_FOUND_NODE を設定するので，続けてチェックする場合などは ctrl をクリアする必要がある．

もし同じツリーパターンがある場合，trの各ノードの altpには，一番最初に見つかった対応する tpの各ノードへのポインタが格納される．

Parameters:

	tp	検索対象のツリー
	tr	検索パターンのツリー

Return values:

	TRUE	tp中に trと同じいツリーパターンが存在する．trの各ノードの altpには，一番最初に見つかった対応する tpの各ノードへのポインタが格納される．
	FALSE	tpに同じツリーパターンは無い．この場合，trのaltpの値は不定となる．

Definition at line 1261 of file ttree.c.

References check_match_tTree(), cmp_sisters_tTree(), FALSE, find_tList_end(), TREE_ALREADY_FOUND_NODE, and TRUE.

Referenced by check_match_tTree(), find_match_tTree(), and find_match_tTree_endlist_rcsv().

01263 01264 01265 01266 01267 01268 01269 01270 01271 01272 01273 01274 01275     ts = tp; 01276 01277 01278 01279 01280 01281 01282 01283 01284 01285 01286 01287 01288 01289 01290 01291 01292         } 01293 01294 01295 01296 01297         } 01298 01299 01300     } 01301 01302 01303 }

class="fragment">01262 { int ret; tTree* te; tTree* ts; tTree* tt; tTree* ta; tTree* tb; if (tp==NULL || tr==NULL) return FALSE; te = find_tList_end(tr); 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;

Here is the call graph for this function:

Here is the caller graph for this function:

void clear_tTree_ctrl ( tTree * pp )

void clear_tTree_ctrl(tTree* pp)

ppツリーの ctrlをクリアする．

Definition at line 1357 of file ttree.c.

References clear_tTree_ctrl(), and TREE_NOCTRL_NODE.

Referenced by clear_tTree_ctrl(), find_match_tTree(), find_match_tTree_endlist(), find_match_tTree_endlist_rcsv(), find_match_xml(), find_match_xml_end_node(), find_match_xml_endlist(), find_match_xml_endlist_rcsv(), get_xml_content(), get_xml_node(), and set_xml_end_node().

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

tTree* cmp_sisters_tTree	(	tTree *	tp,
		tTree *	tr
	)

tTree* cmp_sisters_tTree(tTree* tp, tTree* tr)

ノードtpの姉妹ノードがノードtrの姉妹ノードと同じパターン（キー値を比較）を持っているかどうかを検査する．

ただし，tr->ctrl が TREE_NOCMP_NODE または TREE_NOCMP_COPY_NODE のノードは比べない(常に一致とする)．
また tp->ctrl が TREE_ALREADY_FOUND_NODE の場合は，常に一致しない．
もし同じノードパターンがある場合，trの各ノードの altpには，対応する tpの各ノードへのポインタが格納される．

Parameters:

	tp	比べる姉妹ノードの長女ノード
	tr	探す姉妹ノードパターンの長女ノード

Returns:: tp中で trと同じパターンが始まるノードへのポインタ．trの各ノードの altpには，対応する tpの各ノードへのポインタが格納される．

Return values:

NULL

tpに同じ姉妹パターンは無い．この場合，trのaltpの値は不定となる．

例

以下の場合，cmp_sisters_tTree(tp, tr) は (3)へのポインタを返す．また trの Aノードの altp には (3) へのポインタが，trの Xノードのaltpには(4)へのポインタが格納される．最初に見つかったパターンのみ評価される．

tp                tr
--> A (1)         --> A         A, B, X は キー値(ldat.key.buf)
--> B (2)         --> X
--> A (3)
--> X (4)
--> A (5)
--> X (6)

Definition at line 1209 of file ttree.c.

References TREE_ALREADY_FOUND_NODE, TREE_NOCMP_COPY_NODE, and TREE_NOCMP_NODE.

Referenced by check_match_tTree().

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 }

Here is the caller graph for this function:

void copy_tTree_byctrl ( tTree * pt )

void copy_tTree_byctrl(tTree* pt)

replace_tTree_node()の補助関数．

ツリー ptにおいて，pt->ctrl が TREE_COPY_NODE または TREE_NOCMP_COPY_NODE の場合， pt->altp のノードへ ptの属性をコピーする．
pt->ldat.sz には正確に pt->ldat.ptrのサイズが設定されている必要がある．

Definition at line 1482 of file ttree.c.

References copy_tTree_byctrl(), del_all_tList(), dup_Buffer(), dup_tList(), free_Buffer(), TREE_COPY_NODE, and TREE_NOCMP_COPY_NODE.

Referenced by copy_tTree_byctrl(), replace_tTree_node(), and set_xml_end_node().

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

int count_tTree ( tTree * pp )

int count_tTree(tTree* pp)

ツリーの ppノード以降のノードの数を数える．

Parameters:

pp

数え始めるノードへのポインタ．姉妹ノードも数える．

Returns:: ノードの数．

Definition at line 1083 of file ttree.c.

References count_tTree().

Referenced by count_tTree(), json_inverse_parse(), json_inverse_parse_opt(), and xml_inverse_parse().

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

void del_all_tTree ( tTree ** pp )

void del_all_tTree(tTree** pp)

ツリーの全ノードの削除．ポインタ ppのノードを含むツリー全体を削除する．
pp はツリー中であれば，どこを指していても良い．

Parameters:

*pp

削除を開始するノードへのポインタ．ツリー中であれば，どこを指していても良い．

Definition at line 674 of file ttree.c.

References del_tTree().

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 }

Here is the call graph for this function:

tTree* del_children_tTree ( tTree ** pp )

tTree* del_children_tTree(tTree** pp)

指定したノードの子ツリーを削除する．指定したノードは削除しない．

Parameters:

*pp

削除する子ツリーの親ノード

Returns:: 削除したツリーの親ノードへのポインタ．*pp がそのまま返る．

Definition at line 586 of file ttree.c.

References del_sisters_children_tTree().

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 }

Here is the call graph for this function:

tTree* del_sisters_children_tTree ( tTree ** pp )

tTree* del_sisters_children_tTree(tTree** pp)

指定したノードの姉妹ツリー，子ツリーを削除する．
指定したノードも削除する．

Parameters:

*pp

削除するツリーの起点ノード

Returns:: 削除したツリー郡の親ノードへのポインタ．

Attention:: 再帰処理用．親ノードに対する処理は行わないので，別途呼び出し側で行うこと．

Definition at line 639 of file ttree.c.

References del_sisters_children_tTree(), and free_tList_data().

Referenced by del_children_tTree(), del_sisters_children_tTree(), del_sisters_tTree(), and del_tTree().

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

tTree* del_sisters_tTree ( tTree ** pp )

tTree* del_sisters_tTree(tTree** pp)

指定したノード以下のXMLツリー（ppの姉妹を含む）を削除する．

Parameters:

[in,out] *pp 削除するツリーの先頭ノード．削除後は NULLになる．

Returns:: 削除したXMLツリーの親ノードへのポインタ．

Definition at line 608 of file ttree.c.

References del_sisters_children_tTree().

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 }

Here is the call graph for this function:

tTree* del_tTree ( tTree ** pp )

tTree* del_tTree(tTree** pp)

指定したノード以下のツリーを削除する．

Parameters:

`[in]`	*pp	削除するツリーの先頭ノード
`[out]`	*pp	NULL

Returns:: 削除したツリーの親ノードへのポインタ．

Definition at line 550 of file ttree.c.

References del_sisters_children_tTree(), and free_tList_data().

Referenced by clear_BVHData(), and del_all_tTree().

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

tTree* del_tTree_anchor_node ( tTree * node )

Definition at line 58 of file ttree.c.

References free_tTree_node(), and TREE_ANCHOR_NODE.

Referenced by dup_merge_tTree().

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

tTree* del_tTree_node ( tTree ** node )

tTree* del_tTree_node(tTree** node)

ツリーノードの削除．削除されたノードが子ノードを持つ場合は，その子ノードを格上げする（木構造を詰める）
node は動的に確保された変数でなければならない．

Parameters:

*node

削除するノードへのポインタ．

Returns:: 削除したノードの親ノードへのポインタ．

Definition at line 412 of file ttree.c.

References free_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 }

Here is the call graph for this function:

tTree* div_tTree ( tTree * tt )

tTree* div_tTree(tTree* tp, tTree* tt)

ツリー tp からツリー ttを分離する．

Parameters:

tt

ツリーへの分離ポイント．

Returns:: 分離したツリーの元親ノードへのポインタ．失敗した場合は NULL

Definition at line 746 of file ttree.c.

References adjust_tTree_depth().

Referenced by merge_tTree().

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

tTree* dup_merge_tTree	(	tTree *	pp,
		tTree *	tp
	)

tTree* dup_merge_tTree(tTree* pp, tTree* tp)

ツリー ppの直下に（Yunger Sisterとして）ツリー tpを複製する．
pp がNULLの場合は，ツリーの深さは調整されない

Parameters:

	pp	複製されたツリーのトップとなるノード
	tp	複製するツリー

Returns:: 複製されたツリーへのポインタ．pp がNULLでない場合は pp; pp がNULLの場合は，新しく複製したツリーのトップ．

Definition at line 783 of file ttree.c.

References add_tTree(), del_tTree_anchor_node(), dup_merge_tTree(), dup_tList_node(), new_tTree_anchor_node(), and TREE_NOSIS_NODE.

Referenced by dup_merge_tTree(), and dup_merge_xml().

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

void exchange_tTree	(	tTree *	tl,
		tTree *	tt
	)

void exchange_tTree(tTree* tl, tTree* tt)

ツリー tlとツリー ttを交換する．

Parameters:

	tl	交換対象のツリー
	tt	交換対象のツリー

Definition at line 895 of file ttree.c.

References adjust_tTree_depth().

Referenced by merge_tTree().

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

int find_match_tTree	(	tTree *	pp,
		tTree *	pt
	)

int find_match_tTree(tTree* pp, tTree* pt)

ツリー pp内でツリー ptと同じパターンの枝を探す．
同じパターンの探索ではキー値のみを比較し，ノード値は比較しない．
ただし，pt->ctrl が TREE_NOCMP_NODE または TREE_NOCMP_COPY_NODE のノードは比べない(常に一致とする)．

もし同じツリーパターンがある場合，trの各ノードの altpには，一番最初に見つかった対応する ppの各ノードへのポインタが格納される．

check_match_tTree() との違い．

check_match_tTree() では比べる枝の開始ノードはppに固定される．
find_match_tTree() は pp内を移動しながら検索できる．

Parameters:

	pp	検索対象のツリー
	pt	検索パターンのツリー

Return values:

	TRUE	pp中に pt同じいツリーパターンが存在する．ptの各ノードの altpには，一番最初に見つかった対応する ppの各ノードへのポインタが格納される．
	FALSE	ppに同じツリーパターンは無い．この場合，ptのaltpの値は不定となる．

Definition at line 1327 of file ttree.c.

References check_match_tTree(), clear_tTree_ctrl(), FALSE, find_match_tTree(), and TRUE.

Referenced by find_match_tTree(), find_match_xml_end_node(), get_value_tTree(), and replace_tTree_node().

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

tList* find_match_tTree_endlist	(	tTree *	pp,
		tTree *	pt
	)

tList* find_match_tTree_endlist(tTree* pp, tTree* pt)

ツリー pp内でツリー ptと同じパターンの枝を全て探して，その枝の最後のノードへの情報をリストにして返す．
該当ノードへのポインタは返された各リストのaltp が保持している．

比較ではキー値のみを比較し，ノード値は比較しない．また，pt->ctrl が TREE_NOCMP_NODE または TREE_NOCMP_COPY_NODE のノードは比べない(常に一致とする)．

Parameters:

	pp	検索対象のツリー
	pt	検索パターンのツリー

Returns:: 該当ノードへのポインタを保持するリスト．

Definition at line 1384 of file ttree.c.

References clear_tTree_ctrl(), find_match_tTree_endlist_rcsv(), and find_tTree_end().

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 }

Here is the call graph for this function:

tList* find_match_tTree_endlist_rcsv	(	tTree *	pp,
		tTree *	pt,
		tTree *	te
	)

tList* find_match_tTree_endlist_rcsv(tTree* pp, tTree* pt, tTree* te)

find_match_tTree_endlist() の補助関数

Definition at line 1405 of file ttree.c.

References check_match_tTree(), clear_tTree_ctrl(), find_match_tTree_endlist_rcsv(), insert_tList(), and new_tList_node().

Referenced by find_match_tTree_endlist(), and find_match_tTree_endlist_rcsv().

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

tTree* find_tTree_end ( tTree * pp )

tTree* find_tTree_end(tTree* pp)

ツリーの最終ノードを見つける．

Definition at line 1063 of file ttree.c.

Referenced by find_match_tTree_endlist(), and get_value_tTree().

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 }

Here is the caller graph for this function:

tTree* free_tTree_node ( tTree * node )

tTree* free_tTree_node(tTree* node)

ツリーノードの削除．削除されたノードが子ノードを持つ場合は，その子ノードを格上げする（木構造を詰める）

Returns:: 削除したノードの親ノードへのポインタ．

Definition at line 355 of file ttree.c.

References adjust_tTree_depth(), free_tList_data(), and TREE_ANCHOR_NODE.

Referenced by del_tTree_anchor_node(), and del_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 }

Here is the call graph for this function:

Here is the caller graph for this function:

Buffer get_value_tTree	(	tTree *	pp,
		tTree *	pt
	)

Buffer get_value_tTree(tTree* pp, tTree* pt)

ツリー pp内でツリー ptと同じパターンの枝を検索し，ppに一致したパターンの枝があれば，その枝の最後のノードの値を返す．

Parameters:

	pp	検索対象のツリー
	pt	検索するパターン

Returns:: ptの最後のノードに対応する ppのノードのノード値

例

以下の場合，Y(*) のノード値が返る．

tp                           tr
A --> B --> E                C --> M --> Y
  --> C --> M --> X               
              --> Y(*)         
        --> N

Definition at line 1542 of file ttree.c.

References dup_Buffer(), find_match_tTree(), find_tTree_end(), and init_Buffer().

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 }

Here is the call graph for this function:

tTree* insert_tTree_node	(	tTree *	pp,
		tTree *	node
	)

tTree* insert_tTree_node(tTree* pp, tTree* node)

ツリー ppへノード nodeを追加．ポインタ ppが指すノードの子（長子）ノードとして node（そのもの）を追加する．
node が子ノードを持つ場合は，それも追加される．
node が姉妹ノードを持っていてもそれらは無視する（処理しない）．

Parameters:

	pp	追加するノードの親となるノードへのポインタ．
	node	追加するノードへのポインタ．node->next 以下がツリーでも良い．

Returns:: 追加したノードへのポインタ．失敗した場合は NULL

Definition at line 233 of file ttree.c.

References adjust_tTree_depth().

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 }

Here is the call graph for this function:

tTree* insert_tTree_node_byBuffer	(	tTree *	pp,
		int	id,
		int	lv,
		Buffer	key,
		Buffer	val,
		void *	ptr,
		int	sz
	)

tTree* insert_tTree_node_byBuffer(tTree* pp, int id, int lv, Buffer key, Buffer val, void* ptr, int sz)

データからノードをつくり出し,それを長子としてリストに追加．
リストポインタ ppが指すノードの後につくり出したノードを挿入する．

Parameters:

	pp	追加する場所の手前のノードへのポインタ．
	id	追加するデータ．
	lv	追加するデータ．
	key	追加するデータ．複製
	val	追加するデータ．複製
	ptr	汎用データへのポインタ複製
	sz	*ptr のサイズ

Returns:: 追加したノードへのポインタ．

Definition at line 308 of file ttree.c.

References insert_tTree_node_bydata(), and make_tList_data().

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 }

Here is the call graph for this function:

tTree* insert_tTree_node_bydata	(	tTree *	pp,
		tList_data	ldat
	)

tTree* insert_tTree_node_bydata(tTree* pp, tList_data ldat)

データから tTreeノードをつくり出し,それを ppの子ノード（長子）として追加．
ldat は指定されたものがそのまま使用される．

Parameters:

	pp	追加するノードの親となるノードへのポインタ．
	ldat	追加するノードデータ．このデータがそのまま使用される．

Returns:: 追加したノードへのポインタ．

Definition at line 268 of file ttree.c.

References new_tTree_node().

Referenced by insert_tTree_node_byBuffer(), and insert_tTree_node_bystr().

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

tTree* insert_tTree_node_bystr	(	tTree *	pp,
		int	id,
		int	lv,
		const char *	key,
		const char *	val,
		void *	ptr,
		int	sz
	)

tTree* insert_tTree_node_bystr(tTree* pp, int id, int lv, const char* key, const char* val, void* ptr, int sz)

データからノードをつくり出し,それを長子としてリストに追加．
リストポインタ ppが指すノードの後につくり出したノードを挿入する．

Parameters:

	pp	追加する場所の手前のノードへのポインタ．
	id	追加するデータ．
	lv	追加するデータ．
	key	追加するデータ．複製
	val	追加するデータ．複製
	ptr	汎用データへのポインタ複製
	sz	*ptr のサイズ

Returns:: 追加したノードへのポインタ．

Definition at line 335 of file ttree.c.

References insert_tTree_node_bydata(), and make_tList_data_bystr().

Referenced by insert_xml_node().

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

tTree make_tTree_node ( tList_data data )

tTree make_tTree_node(tList_data data)

ツリー用ノードを静的に作成．

Parameters:

data

ノードデータ

Returns:: 作られたノード．

Definition at line 80 of file ttree.c.

References JBXL_NORMAL.

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 }

void merge_tTree	(	tTree *	tp,
		tTree *	tt
	)

void merge_tTree(tTree* tp, tTree* tt)

ツリー tp にツリー tt を結合する．結合後，tt の内容は壊れる(tpとノードを交換した形になる)．

tt が tpの一部と同じ構造(キー値)を持つ場合，末端ノードは ttのノードで置き換える．tp に存在しない枝は追加される．
ツリーの深さは tpを深さを元に再計算される．

Parameters:

`[in,out]`	tp	in: tt の結合ポイント．out: 結合後のツリー．
`[in,out]`	tt	in: 結合するツリー．out: 内容は破壊される．要注意

例

tp                           tr
A --> B --> E                A --> B --> X
  --> C --> M --> X            --> C --> M
              --> Y            --> D
        --> N

以上の場合，merge_tTree(tp, tr) を実行すると以下のようになる．

tp
A --> B --> E 
        --> X (tr)
  --> C --> M (tr)
        --> N 
  --> D (tr)

tt
A --> B 
  --> C --> M --> X (tp)
              --> Y (tp)

Definition at line 843 of file ttree.c.

References add_tTree(), adjust_tTree_depth(), div_tTree(), exchange_tTree(), and merge_tTree().

Referenced by merge_tTree().

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

tTree* move_tTree_node	(	tTree *	pp,
		tTree *	node
	)

tTree* move_tTree_node(tTree* pp, tTree* node)

nodeを現在のツリーから切り離し，ppへ移動する．

元のツリーに於いて，nodeが子ノードを持つ場合は，その子ノードを格上げする（木構造を詰める）
移動に於いては，node が姉妹ノードを持っていてもそれらは無視する．
nodeを削除しないで del_tTree_node(), add_tTree_node() を実行するようなもの．

Parameters:

	pp	移動先で親となるノードへのポインタ．
	node	移動するノードへのポインタ．node->next 以下がツリーでも良い．

Returns:: 移動したノードノードへのポインタ．

Definition at line 438 of file ttree.c.

References adjust_tTree_depth().

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 }

Here is the call graph for this function:

tTree* new_tTree_anchor_node ( void )

Definition at line 41 of file ttree.c.

References init_tList_data(), JBXL_STATE_ANCHOR, and TREE_ANCHOR_NODE.

Referenced by dup_merge_tTree(), and xml_parse_seq().

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

tTree* new_tTree_node ( void )

tTree* new_tTree_node(void)

ツリー用の空ノードを動的に生成．

Returns:: 生成されたノードへのポインタ．

Definition at line 26 of file ttree.c.

References init_tList_data(), and JBXL_NORMAL.

Referenced by add_tTree_node_bydata(), and insert_tTree_node_bydata().

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

tTree* next_strncasecmp_horizon_tTree	(	tTree *	pp,
		const char *	key,
		int	len,
		int	no,
		int *	nn
	)

tTree* next_strncasecmp_horizon_tTree (tTree* pp, const char* key, int len, int no, int* nn)

tTree 検索用補助関数．horizon は擬似的な横方向探索（完全な横方向探索ではない）

Definition at line 1646 of file ttree.c.

References ex_strncasecmp(), and next_strncasecmp_horizon_tTree().

Referenced by next_strncasecmp_horizon_tTree().

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

tTree* next_strncasecmp_vertical_tTree	(	tTree *	pp,
		const char *	key,
		int	len,
		int	no,
		int *	nn
	)

tTree* next_strncasecmp_vertical_tTree(tTree* pp, const char* key, int len, int no, int* nn)

tTree 検索用補助関数．vertical は縦方向探索

Definition at line 1622 of file ttree.c.

References ex_strncasecmp(), and next_strncasecmp_vertical_tTree().

Referenced by next_strncasecmp_vertical_tTree(), and strncasecmp_tTree().

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

tTree* next_strncmp_horizon_tTree	(	tTree *	pp,
		const char *	key,
		int	len,
		int	no,
		int *	nn
	)

tTree* next_strncmp_horizon_tTree (tTree* pp, const char* key, int len, int no, int* nn)

tTree 検索用補助関数．horizon は擬似的な横方向探索（完全な横方向探索ではない）

Definition at line 1598 of file ttree.c.

References ex_strncmp(), and next_strncmp_horizon_tTree().

Referenced by next_strncmp_horizon_tTree().

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

tTree* next_strncmp_vertical_tTree	(	tTree *	pp,
		const char *	key,
		int	len,
		int	no,
		int *	nn
	)

tTree* next_strncmp_vertical_tTree(tTree* pp, const char* key, int len, int no, int* nn)

tTree 検索用補助関数．vertical は縦方向探索

Definition at line 1574 of file ttree.c.

References ex_strncmp(), and next_strncmp_vertical_tTree().

Referenced by next_strncmp_vertical_tTree(), and strncmp_tTree().

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

void print_tTree	(	FILE *	fp,
		tTree *	pp
	)

void print_tTree(FILE* fp, tTree* pp)

ツリーの表示．ポインタ pp以降の全てのノードのキー部のバッファを fpに表示する． pp->ctrl が TREE_NOSIS_NODE の場合は，ppの姉妹ノードは出力しない．

Parameters:

	fp	出力するファイルへのポインタ．NULLの場合は stderr
	pp	表示を開始するノードへのポインタ．

Definition at line 1032 of file ttree.c.

References print_tTree(), and TREE_NOSIS_NODE.

Referenced by print_tTree().

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

void print_tTree_tree	(	FILE *	fp,
		tTree *	pp,
		const char *	space
	)

void print_tTree_tree(FILE* fp, tTree* pp, const char* space)

ツリーの表示．ポインタ pp以降の全てのノードのキー部のバッファを fpに表示する． pp->ctrl が TREE_NOSIS_NODE の場合は，ppの姉妹ノードは出力しない．

Parameters:

	fp	出力するファイルへのポインタ．NULLの場合は stderr
	pp	表示を開始するノードへのポインタ．
	space	出力の書式を揃えるための空白．

Definition at line 992 of file ttree.c.

References print_tTree_tree(), and TREE_NOSIS_NODE.

Referenced by print_tTree_tree().

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

int replace_all_tTree_node	(	tTree *	tp,
		char *	key,
		char *	src,
		char *	dst,
		int	len
	)

void replace_all_tTree_node(tTree* pp, char* key, char* src, char* dst, int len)

ツリー pp内で keyをキー，srcをノード値として持つ全てのノードのノード値を dst に書き換える．

Parameters:

	tp	置換対象のツリー
	key	サーチキー
	src	置換対象のノード値
	dst	置換後のノード値
	len	1以上: 一致させる長さ．
	len	TLIST_MATCH_COMPLETE (0): 完全一致．
	len	TLIST_MATCH_TLISTKEY (-1): pl->key.buf の長さに合わせる．
	len	TLIST_MATCH_STRINGKEY (-2): key の長さに合わせる．

Returns:: 置き換えたノードの数

Definition at line 513 of file ttree.c.

References ex_strncmp(), free_Buffer(), make_Buffer_bystr, and replace_all_tTree_node().

Referenced by replace_all_tTree_node().

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

int replace_tTree_node	(	tTree *	pp,
		tTree *	pt
	)

void replace_tTree_node(tTree* pp, tTree* pt)

ツリー pp内でツリー ptと同じパターン（キー値を比較）の枝を検索し，ppに一致したパターンの枝があれば，
その枝の各ノードに対して，対応するそれぞれの（pt->ctrl が TREE_COPY_NODE または TREE_NOCMP_COPY_NODE である）
ptのノードの属性で置き換える．
パターンの一致（検索）では ldat.key（キー値）が比較される．

置き換える属性は ldat.id, ldat.lv, ldat.sz, ldat.key, ldat.val, ldat.ptr, ldat.lst
置き換えを行うのは pt->ctrl が TREE_COPY_NODE または TREE_NOCMP_COPY_NODE の場合のみである．(重要)
ldat.val, ldat.ptr, ldat.lst については，ptで値が設定されていなければ，置き換えを行わない．

Parameters:

	pp	置き換え対象のツリー
	pt	置き換えるツリー

Return values:

	TRUE	置換する枝を見つけた．正常に置換されたかどうかは不明．
	FALSE	置換する枝を見つけられなかった．

Definition at line 1455 of file ttree.c.

References adjust_tTree_depth(), copy_tTree_byctrl(), FALSE, and find_match_tTree().

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 }

Here is the call graph for this function:

tTree* strncasecmp_tTree	(	tTree *	pp,
		const char *	key,
		int	len,
		int	no
	)

tTree* strncasecmp_tTree(tTree* pp, const char* key, int len, int no)

ツリーノードのキー値のサーチ．大文字小文字を無視する．
ポインタ pp以降のノードで,キー部の文字列が keyと前方一致（部分的も可）するノードの内 no番目にあるのを捜し出す．

Parameters:

	pp	サーチを開始するノードへのポインタ．
	key	サーチキー（文字列）．大文字，小文字を区別しない．
	len	1以上: 一致させる長さ．
	len	TLIST_MATCH_COMPLETE (0): 完全一致．
	len	TLIST_MATCH_TLISTKEY (-1): pl->key.buf の長さに合わせる．
	len	TLIST_MATCH_STRINGKEY (-2): key の長さに合わせる．
	no	一致した物の中で何番目の物を返すか指定する．1から数える．

Returns:: 一致したノードへのポインタ

Return values:

NULL

一致したものが無い

Definition at line 1160 of file ttree.c.

References ex_strncasecmp(), and next_strncasecmp_vertical_tTree().

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 }

Here is the call graph for this function:

tTree* strncmp_tTree	(	tTree *	pp,
		const char *	key,
		int	len,
		int	no
	)

tTree* strncmp_tTree(tTree* pp, const char* key, int len, int no)

ツリーノードのキー値のサーチ．
ポインタ pp以降のノードで,キー部の文字列が keyと前方一致（部分的も可）するノードの内 no番目にあるのを捜し出す．

Parameters:

	pp	サーチを開始するノードへのポインタ．
	key	サーチキー（文字列）．
	len	1以上: 一致させる長さ．
	len	TLIST_MATCH_COMPLETE (0): 完全一致．
	len	TLIST_MATCH_TLISTKEY (-1): pl->key.buf の長さに合わせる．
	len	TLIST_MATCH_STRINGKEY (-2): key の長さに合わせる．
	no	一致した物の中で何番目の物を返すか指定する．1から数える．

Returns:: 一致したノードへのポインタ

Return values:

NULL

一致したものが無い

Definition at line 1123 of file ttree.c.

References ex_strncmp(), and next_strncmp_vertical_tTree().

Referenced by get_node_content().

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

Lib/ttree.c File Reference

Functions

Detailed Description

Function Documentation