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

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

Include dependency graph for ttree.c:

Functions
tTree *	new_tTree_node (void)
	ツリー用の空ノードを動的に生成． More...

tTree *	new_tTree_anchor_node (void)
	ツリー用の ANCHORノードを動的に生成． More...

tTree *	del_tTree_anchor_node (tTree *node)
	ANCHORノードを削除して，TOP（長女）へのポインターを返す． More...

tTree	make_tTree_node (tList_data data)
	ツリー用ノードを静的に作成． More...

tTree *	add_tTree_node (tTree pp, tTree node)
	ツリー ppへノード nodeを末っ子として追加． More...

tTree *	add_tTree_node_bydata (tTree *pp, tList_data ldat)
	データから Treeノードをつくり出し,それを ppの子ノード（末っ子）として追加． More...

tTree *	add_tTree_node_byBuffer (tTree pp, int id, int lv, Buffer key, Buffer val, void ptr, int sz)
	ノードを末っ子としてリストに追加． More...

tTree *	add_tTree_node_bystr (tTree pp, int id, int lv, const char key, const char val, void ptr, int sz)
	ノードを末っ子としてリストに追加． More...

tTree *	insert_tTree_node (tTree pp, tTree node)
	ツリー ppへノード nodeを長子として追加． More...

tTree *	insert_tTree_node_bydata (tTree *pp, tList_data ldat)
	ノードをつくり出し,それを ppの子ノード（長子）として追加． More...

tTree *	insert_tTree_node_byBuffer (tTree pp, int id, int lv, Buffer key, Buffer val, void ptr, int sz)
	ノードを長子としてリストに追加． More...

tTree *	insert_tTree_node_bystr (tTree pp, int id, int lv, const char key, const char val, void ptr, int sz)
	ノードを長子としてリストに追加． More...

tTree *	free_tTree_node (tTree *node)
	ツリーノードの解放．解放されたノードが子ノードを持つ場合は，その子ノードを格上げする（木構造を詰める） More...

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

tTree *	move_tTree_node (tTree pp, tTree node)
	nodeを現在のツリーから切り離し，ppへ移動する． More...

int	replace_all_tTree_node (tTree tp, char key, char src, char dst, int len)
	対象の全てのノードのノード値を dst に書き換える． More...

void	del_delete_node_tTree (tTree **pp)
	ctrl==TREE_DELETE_NODE を削除する． More...

void	_del_delete_node_tTree (tTree **pp)

void	del_non_keep_node_tTree (tTree **pp)
	ctrl==TREE_KEEP_NODE 以外を削除する． More...

void	_del_non_keep_node_tTree (tTree **pp)

tTree *	del_tTree (tTree **pp)
	指定したノード以下のツリーを削除する． More...

tTree *	del_children_tTree (tTree **pp)
	指定したノードの子ツリーを削除する．指定したノードは削除しない． More...

tTree *	del_sisters_tTree (tTree **pp)
	指定したノード以下のXMLツリー（ppの姉妹を含む）を削除する． More...

tTree *	del_sisters_children_tTree (tTree **pp)
	指定したノードの姉妹ツリー，子ツリーを削除する． More...

void	del_all_tTree (tTree **pp)
	ツリーの全ノードの削除．ポインタ ppのノードを含むツリー全体を削除する． More...

tTree *	add_tTree (tTree tp, tTree tt)
	ツリー tpへツリー ttを追加． More...

tTree *	div_tTree (tTree *tt)
	ツリー tp からツリー ttを分離する． More...

tTree *	dup_merge_tTree (tTree pp, tTree tp)
	ツリー ppの直下にツリー tpを複製する． More...

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

void	exchange_tTree (tTree tl, tTree tt)
	ツリー tlとツリー ttを交換する． More...

void	adjust_tTree_depth (tTree *pp)
	指定したノード ppを基準にして，木の深さを測り直す More...

void	print_tTree_tree (FILE fp, tTree pp, const char *space)
	ツリーの表示．ポインタノードのキー部のバッファをfpに表示する． More...

void	print_tTree (FILE fp, tTree pp)
	ツリーの表示．ポインタノードのキー部のバッファをfpに表示する． More...

tTree *	find_tTree_end (tTree *pp)
	ツリーの最終ノードを見つける． More...

int	count_tTree (tTree *pp)
	ツリーの ppノード以降のノードの数を数える． More...

tTree *	strncmp_tTree (tTree pp, const char key, int len, int no)
	ツリーノードのキー値のサーチ More...

tTree *	strncasecmp_tTree (tTree pp, const char key, int len, int no)
	ツリーノードのキー値のサーチ．大文字小文字を無視する． More...

tTree *	cmp_sisters_tTree (tTree tp, tTree tr)
	tpの姉妹ノードが trの姉妹ノードと同じキー値を持っているかどうかを検査する． More...

int	check_match_tTree (tTree tp, tTree tr)
	tpが trと同じパターン(キー値)を持っているかどうかを検査する． More...

int	find_match_tTree (tTree pp, tTree pt)
	ツリー pp内でツリー ptと同じパターンの枝を探す． More...

void	_clear_tTree_ctrl (tTree *pp)
	ppツリーの ctrlをクリアする． More...

tList *	find_match_tTree_endlist (tTree pp, tTree pt)
	pp内で ptと同じパターンの枝を全て探して，その枝の最後のノードへの情報を返す． More...

tList *	_find_match_tTree_endlist_rcsv (tTree pp, tTree pt, tTree *te)
	find_match_tTree_endlist() の補助関数 More...

int	replace_tTree_node (tTree pp, tTree pt)
	同じパターンの枝を検索し，ptのノードの属性で置き換える． More...

void	_copy_tTree_byctrl (tTree *pt)
	同じパターンの枝を検索し，ptのノードの属性をコピーする． More...

Buffer	get_value_tTree (tTree pp, tTree pt)
	同じパターンの枝を検索し，一致した枝があれば，その枝の最後のノードの値を返す． More...

tTree *	_next_strncmp_vertical_tTree (tTree pp, const char key, int len, int no, int *nn)
	tTree 検索用補助関数．vertical は縦方向探索 More...

tTree *	_next_strncmp_horizon_tTree (tTree pp, const char key, int len, int no, int *nn)
	tTree 検索用補助関数．horizon は擬似的な横方向探索 More...

tTree *	_next_strncasecmp_vertical_tTree (tTree pp, const char key, int len, int no, int *nn)
	tTree 検索用補助関数．vertical は縦方向探索 More...

tTree *	_next_strncasecmp_horizon_tTree (tTree pp, const char key, int len, int no, int *nn)
	tTree 検索用補助関数．horizon は擬似的な横方向探索 More...

Detailed Description

Version

Author: Fumi.Iseki (C)

Date: 2008 2/1

Definition in file ttree.c.

Function Documentation

◆ _clear_tTree_ctrl()

void _clear_tTree_ctrl ( tTree * pp )

void _clear_tTree_ctrl(tTree* pp)

ppツリーの ctrlをクリアする． find_match_tTree(tTree* pp, tTree* pt) の補助関数

Definition at line 1420 of file ttree.c.

 {
     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;
     }
 }

References TREE_NOCTRL_NODE.

Referenced by _find_match_tTree_endlist_rcsv(), _find_match_xml_endlist_rcsv(), find_match_tTree(), find_match_tTree_endlist(), find_match_xml(), find_match_xml_end_node(), find_match_xml_endlist(), get_xml_content(), get_xml_node(), and set_xml_end_node().

Here is the caller graph for this function:

◆ _copy_tTree_byctrl()

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 1541 of file ttree.c.

 {
     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;
 }

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

Referenced by replace_tTree_node(), and set_xml_end_node().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _del_delete_node_tTree()

void _del_delete_node_tTree ( tTree ** pp )

Definition at line 551 of file ttree.c.

 {
     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;
 }

References del_tTree_node(), and TREE_DELETE_NODE.

Referenced by del_delete_node_tTree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _del_non_keep_node_tTree()

void _del_non_keep_node_tTree ( tTree ** pp )

Definition at line 597 of file ttree.c.

 {
     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;
 }

References del_tTree_node(), and TREE_KEEP_NODE.

Referenced by del_non_keep_node_tTree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _find_match_tTree_endlist_rcsv()

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 1466 of file ttree.c.

 {
     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;
 }

References _clear_tTree_ctrl(), check_match_tTree(), insert_tList(), and new_tList_node().

Referenced by find_match_tTree_endlist().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _next_strncasecmp_horizon_tTree()

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 1700 of file ttree.c.

 {
     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;
 }

References ex_strncasecmp(), and len.

Here is the call graph for this function:

◆ _next_strncasecmp_vertical_tTree()

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 1677 of file ttree.c.

 {
     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;
 }

References ex_strncasecmp(), and len.

Referenced by strncasecmp_tTree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _next_strncmp_horizon_tTree()

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 1654 of file ttree.c.

 {
     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;
 }

References ex_strncmp(), and len.

Here is the call graph for this function:

◆ _next_strncmp_vertical_tTree()

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 1631 of file ttree.c.

 {
     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;
 }

References ex_strncmp(), and len.

Referenced by strncmp_tTree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ add_tTree()

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 778 of file ttree.c.

 {
     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;
 }

References adjust_tTree_depth().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ add_tTree_node()

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 97 of file ttree.c.

 {
     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;
 }

References adjust_tTree_depth(), and TREE_ANCHOR_NODE.

Referenced by json_array_parse(), and json_parse_prop().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ add_tTree_node_byBuffer()

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 175 of file ttree.c.

 {
     tTree* pt;
     tList_data ldat;
  
     ldat = make_tList_data(id, lv, key, val, ptr, sz);
     pt   = add_tTree_node_bydata(pp, ldat);
  
     return pt;
 }

References add_tTree_node_bydata(), and make_tList_data().

Here is the call graph for this function:

◆ add_tTree_node_bydata()

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 135 of file ttree.c.

 {
     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;
 }

References new_tTree_node().

Referenced by add_tTree_node_byBuffer(), and add_tTree_node_bystr().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ add_tTree_node_bystr()

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 202 of file ttree.c.

 {
     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;
 }

References add_tTree_node_bydata(), and make_tList_data_bystr().

Referenced by add_xml_content_node(), add_xml_node(), bvh_parse_hierarchy(), json_append_array_int_val(), json_append_array_real_val(), json_append_array_str_val(), json_append_obj_int_val(), json_append_obj_real_val(), json_append_obj_str_val(), llsd_bin_main_parse(), and xml_main_parse().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ adjust_tTree_depth()

void adjust_tTree_depth ( tTree * pp )

void adjust_tTree_depth(tTree* pp)

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

Parameters

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

Definition at line 1016 of file ttree.c.

 {
     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;
 }

Referenced by add_tTree(), add_tTree_node(), 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().

Here is the caller graph for this function:

◆ check_match_tTree()

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 1325 of file ttree.c.

 {
     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;
 }

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

Referenced by _find_match_tTree_endlist_rcsv(), and find_match_tTree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ cmp_sisters_tTree()

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 1274 of file ttree.c.

 {
     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;
 }

References TREE_ALREADY_FOUND_NODE, TREE_NOCMP_COPY_NODE, and TREE_NOCMP_NODE.

Referenced by check_match_tTree().

Here is the caller graph for this function:

◆ count_tTree()

int count_tTree ( tTree * pp )

int count_tTree(tTree* pp)

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

Parameters

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

Returns: ノードの数．

Definition at line 1151 of file ttree.c.

 {
     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;
 }

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

Here is the caller graph for this function:

◆ del_all_tTree()

void del_all_tTree ( tTree ** pp )

void del_all_tTree(tTree** pp)

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

Parameters

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

Definition at line 752 of file ttree.c.

 {
     tTree* pm;
  
     if (pp==NULL || *pp==NULL) return;
  
     pm = *pp;
     while (pm->prev!=NULL) pm = pm->prev;
     del_tTree(&pm);
  
     *pp = NULL;
     return;
 }

References del_tTree().

Here is the call graph for this function:

◆ del_children_tTree()

tTree* del_children_tTree ( tTree ** pp )

tTree* del_children_tTree(tTree** pp)

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

Parameters

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

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

Definition at line 666 of file ttree.c.

 {    
     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;
 }

References del_sisters_children_tTree().

Here is the call graph for this function:

◆ del_delete_node_tTree()

void del_delete_node_tTree ( tTree ** pp )

void del_delete_node_tTree(tTree** pp)

ctrl または　ctrl_alt が TREE_DELETE_NODE のノードを削除する

pp はアンカーノードである必要がある．アンカーノードでない場合，*ppが削除されるとリストを見失う．

Definition at line 534 of file ttree.c.

 {
     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;
 }

References _del_delete_node_tTree(), PRINT_MESG, and TREE_ANCHOR_NODE.

Here is the call graph for this function:

◆ del_non_keep_node_tTree()

void del_non_keep_node_tTree ( tTree ** pp )

void del_non_keep_node_tTree(tTree** pp)

ctrl または ctrl_alt が TREE_KEEP_NODE 以外のノードを削除する

pp はアンカーノードである必要がある．アンカーノードでない場合，*ppが削除されるとリストを見失う．

Definition at line 580 of file ttree.c.

 {
     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;
 }

References _del_non_keep_node_tTree(), PRINT_MESG, and TREE_ANCHOR_NODE.

Here is the call graph for this function:

◆ del_sisters_children_tTree()

tTree* del_sisters_children_tTree ( tTree ** pp )

tTree* del_sisters_children_tTree(tTree** pp)

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

Parameters

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

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

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

Definition at line 718 of file ttree.c.

 {
     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;
 }

References clear_tList_data().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ del_sisters_tTree()

tTree* del_sisters_tTree ( tTree ** pp )

tTree* del_sisters_tTree(tTree** pp)

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

Parameters

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

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

Definition at line 688 of file ttree.c.

 {
     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;
 }

References del_sisters_children_tTree().

Here is the call graph for this function:

◆ del_tTree()

tTree* del_tTree ( tTree ** pp )

tTree* del_tTree(tTree** pp)

指定したノード以下のツリーを削除する．姉妹ノードは削除しない．

Parameters

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

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

Definition at line 628 of file ttree.c.

 {
     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;
 }

References clear_tList_data(), and del_sisters_children_tTree().

Referenced by clear_BVHData(), and del_all_tTree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ del_tTree_anchor_node()

tTree* del_tTree_anchor_node ( tTree * node )

Definition at line 53 of file ttree.c.

 {
     tTree* pp = node;
  
     if (node!=NULL && node->ldat.id==TREE_ANCHOR_NODE) {
         pp = node->next;
         free_tTree_node(node);
         free(node);
     }
  
     return pp;    
 }

References free_tTree_node(), and TREE_ANCHOR_NODE.

Referenced by dup_merge_tTree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ del_tTree_node()

tTree* del_tTree_node ( tTree ** node )

tTree* del_tTree_node(tTree** node)

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

Parameters

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

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

Definition at line 400 of file ttree.c.

 {
     if (node==NULL || *node==NULL) return NULL;
  
     tTree* pp = free_tTree_node(*node);
     free(*node);
     *node = NULL;
  
     return pp;
 }

References free_tTree_node().

Referenced by _del_delete_node_tTree(), and _del_non_keep_node_tTree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ div_tTree()

tTree* div_tTree ( tTree * tt )

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

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

Parameters

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

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

Definition at line 822 of file ttree.c.

 {
     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;
 }

References adjust_tTree_depth().

Referenced by merge_tTree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ dup_merge_tTree()

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 858 of file ttree.c.

 {
     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;
 }

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

Referenced by dup_merge_xml().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ exchange_tTree()

void exchange_tTree	(	tTree *	tl,
		tTree *	tt
	)

void exchange_tTree(tTree* tl, tTree* tt)

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

Parameters

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

Definition at line 968 of file ttree.c.

 {
     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);
     }
 }

References adjust_tTree_depth().

Referenced by merge_tTree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ find_match_tTree()

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 1390 of file ttree.c.

 {
     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;
 }

References _clear_tTree_ctrl(), check_match_tTree(), FALSE, and TRUE.

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ find_match_tTree_endlist()

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 1446 of file ttree.c.

 {
     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;
 }

References _clear_tTree_ctrl(), _find_match_tTree_endlist_rcsv(), and find_tTree_end().

Here is the call graph for this function:

◆ find_tTree_end()

tTree* find_tTree_end ( tTree * pp )

tTree* find_tTree_end(tTree* pp)

ツリーの最終ノードを見つける．最終ノード：最後に追加されたノード．

Definition at line 1132 of file ttree.c.

 {
     if (pp==NULL) return NULL;
  
     while(pp->prev!=NULL) pp = pp->prev;    // Top を探す
     while(pp->yngr!=NULL) pp = pp->yngr;
  
     return pp;
 }

Referenced by find_match_tTree_endlist(), and get_value_tTree().

Here is the caller graph for this function:

◆ free_tTree_node()

tTree* free_tTree_node ( tTree * node )

tTree* free_tTree_node(tTree* node)

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

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

Definition at line 344 of file ttree.c.

 {
     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;
 }

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

Referenced by del_tTree_anchor_node(), and del_tTree_node().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_value_tTree()

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 1600 of file ttree.c.

 {
     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;
 }

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

Here is the call graph for this function:

◆ insert_tTree_node()

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 225 of file ttree.c.

 {
     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;
 }

References adjust_tTree_depth().

Here is the call graph for this function:

◆ insert_tTree_node_byBuffer()

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 298 of file ttree.c.

 {
     tTree* pt;
     tList_data ldat;
  
     ldat = make_tList_data(id, lv, key, val, ptr, sz);
     pt   = insert_tTree_node_bydata(pp, ldat);
  
     return pt;
 }

References insert_tTree_node_bydata(), and make_tList_data().

Here is the call graph for this function:

◆ insert_tTree_node_bydata()

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 259 of file ttree.c.

 {
     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;
 }

References new_tTree_node().

Referenced by insert_tTree_node_byBuffer(), and insert_tTree_node_bystr().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ insert_tTree_node_bystr()

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 325 of file ttree.c.

 {
     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;
 }

References insert_tTree_node_bydata(), and make_tList_data_bystr().

Referenced by insert_xml_node().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ make_tTree_node()

tTree make_tTree_node ( tList_data data )

tTree make_tTree_node(tList_data data)

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

Parameters

data ノードデータ

Returns: 作られたノード．

Definition at line 74 of file ttree.c.

 {
     tTree pp;
  
     memset(&pp, 0, sizeof(tTree));
     pp.ldat  = data;
     pp.state = JBXL_NORMAL;
  
     return pp;
 }

References JBXL_NORMAL.

◆ merge_tTree()

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 917 of file ttree.c.

 {
     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;
 }

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

Here is the call graph for this function:

◆ move_tTree_node()

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 425 of file ttree.c.

 {
     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;
 }

References adjust_tTree_depth().

Here is the call graph for this function:

◆ new_tTree_anchor_node()

tTree* new_tTree_anchor_node ( void )

Definition at line 37 of file ttree.c.

 {
     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;
 }

References init_tList_data(), JBXL_STATE_ANCHOR, and TREE_ANCHOR_NODE.

Referenced by dup_merge_tTree(), and xml_parse_seq().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ new_tTree_node()

tTree* new_tTree_node ( void )

tTree* new_tTree_node(void)

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

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

Definition at line 23 of file ttree.c.

 {
     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;
 }

References init_tList_data(), and JBXL_NORMAL.

Referenced by add_tTree_node_bydata(), and insert_tTree_node_bydata().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ print_tTree()

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 1102 of file ttree.c.

 {
     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;
 }

References TREE_NOSIS_NODE.

◆ print_tTree_tree()

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 1063 of file ttree.c.

 {
     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;
 }

References TREE_NOSIS_NODE.

◆ replace_all_tTree_node()

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 499 of file ttree.c.

 {
     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;
 }

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

Here is the call graph for this function:

◆ replace_tTree_node()

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 1515 of file ttree.c.

 {
     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;
 }

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

Here is the call graph for this function:

◆ strncasecmp_tTree()

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 1226 of file ttree.c.

 {
     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;
 }

References _next_strncasecmp_vertical_tTree(), ex_strncasecmp(), and len.

Here is the call graph for this function:

◆ strncmp_tTree()

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 1190 of file ttree.c.

 {
     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;
 }

References _next_strncmp_vertical_tTree(), ex_strncmp(), and len.

Referenced by get_node_content().

Here is the call graph for this function:

Here is the caller graph for this function:

Functions

Detailed Description

Function Documentation

◆ _clear_tTree_ctrl()

◆ _copy_tTree_byctrl()

◆ _del_delete_node_tTree()

◆ _del_non_keep_node_tTree()

◆ _find_match_tTree_endlist_rcsv()

◆ _next_strncasecmp_horizon_tTree()

◆ _next_strncasecmp_vertical_tTree()

◆ _next_strncmp_horizon_tTree()

◆ _next_strncmp_vertical_tTree()

◆ add_tTree()

◆ add_tTree_node()

◆ add_tTree_node_byBuffer()

◆ add_tTree_node_bydata()

◆ add_tTree_node_bystr()

◆ adjust_tTree_depth()

◆ check_match_tTree()

◆ cmp_sisters_tTree()

◆ count_tTree()

◆ del_all_tTree()

◆ del_children_tTree()

◆ del_delete_node_tTree()

◆ del_non_keep_node_tTree()

◆ del_sisters_children_tTree()

◆ del_sisters_tTree()

◆ del_tTree()

◆ del_tTree_anchor_node()

◆ del_tTree_node()

◆ div_tTree()

◆ dup_merge_tTree()

◆ exchange_tTree()

◆ find_match_tTree()

◆ find_match_tTree_endlist()

◆ find_tTree_end()

◆ free_tTree_node()

◆ get_value_tTree()

◆ insert_tTree_node()

◆ insert_tTree_node_byBuffer()

◆ insert_tTree_node_bydata()

◆ insert_tTree_node_bystr()

◆ make_tTree_node()

◆ merge_tTree()

◆ move_tTree_node()

◆ new_tTree_anchor_node()

◆ new_tTree_node()

◆ print_tTree()

◆ print_tTree_tree()

◆ replace_all_tTree_node()

◆ replace_tTree_node()

◆ strncasecmp_tTree()

◆ strncmp_tTree()