TREE - Stromový seznam

Stromový seznam slouží k hierarchické organizaci položek do stromové struktury.

Parent - ukazatel na rodiče položky. Je-li ukazatel NULL, nemá položka žádného rodiče a jedná se o kořen stromu.

Prev a Next - ukazatelé na předcházejícího a následujícího potomka majícího stejného rodiče, tedy ukazatelé na sourozence. Položky (sourozenci) jsou zacyklené do kruhu. Jedná-li se pouze o jednoho potomka, ukazují ukazatele Prev a Next samy na sebe.

Child - ukazatel na jednoho z potomků. Je-li ukazatel NULL, nemá položka žádného potomka.


; ------------- Tree list entry

struc		TREE

		resb	LIST_size	; 0: sibling list
TREE_Child:	resd	1		; 8: pointer to a child (NULL=none)
TREE_Parent:	resd	1		; 0Ch: pointer to parent (NULL=none)

endstruc				; size 16 bytes

; ------------- Macro - initialized tree list entry

%macro		TREEHEAD 0
		LISTHEAD		; sibling list
		dd	NULL		; no children
		dd	NULL		; pointer to parent (NULL=none)
%endmacro

Struktura TREE popisuje položku stromového seznamu. Zřetězení potomků stejného rodiče (tedy zřetězení sourozenců) je zajištěno dvojitě spojeným seznamem LIST. Ukazatel TREE_Child je adresa jednoho z potomků (NULL=není žádný potomek). Ukazatel TREE_Parent je adresa rodiče položky (NULL=není rodič, jedná se o kořen stromu).

Makro TREEHEAD je inicializovaná položka stromu - seznam sousedních potomků je prázdný (tj. ukazatele ukazují samy na sebe), ukazatel na potomka je NULL (položka nemá žádného potomka) a ukazatel na rodiče je také NULL (položka nemá žádného rodiče, je kořenem stromu).


; ------------- Macro - initialize tree list entry (%1=tree list entry)

%macro		TREEINIT 1
		LISTINIT %1		; initialize sibling list
		and	dword [%1+TREE_Child],byte 0 ; no children
		and	dword [%1+TREE_Parent],byte 0 ; no parent
%endmacro

; ------------- Macro - add tree list entry into tree list
; %1=destination entry (parent), %2=new entry, %3 and %4=temporary registers
; TREE_Child must contain either child list or NULL, other entries are ignored

%macro		TREEADD	4
		mov	%3,[%1+TREE_Child] ; get a child
		or	%3,%3		; is any child?
		jz	%%L		; there is no child
		LISTADD	%3,%2,%4	; add new entry into sibling list
%%L:		mov	[%1+TREE_Child],%2 ; set new entry as new child
		mov	[%2+TREE_Parent],%1 ; link parent to new entry
%endmacro

; ------------- Macro - delete (detach) tree list entry from the tree list
; %1=tree list entry (it must not be root!), %2 and %3=temporary registers

%macro		TREEDEL	3
		LISTDEL	%1,%2,%3	; detach from sibling list
		mov	%3,[%1+TREE_Parent] ; get parent
		cmp	%1,%2		; is list empty?
		jne	%%L		; list is not empty
		xor	%2,%2		; invalid child
%%L:		mov	[%3+TREE_Child],%2 ; set new child

%endmacro

Makro TREEINIT inicializuje položku stromu. Jejím parametrem je adresa nebo registr ukazující na položku stromu. Makro inicializuje seznam sourozenců na prázdný (tj. aby ukazatele ukazovaly samy na sebe) a vynuluje ukazatel na potomka a rodiče.

Makro TREEADD připojí položku stromu jako potomka k jiné položce stromu. Prvním parametrem je registr s ukazatelem na cílovou položku, ke které se má nová položka připojit. Druhým parametrem je registr s ukazatelem na nově přidávanou položku. Nová položka musí mít inicializovaný ukazatel TREE_Child - musí obsahovat buď seznam potomků nebo NULL. Ostatní ukazatele se ignorují. Třetím a čtvrtým parametrem jsou pomocné registry, které makro použije. Do registru %3 se nejdříve připraví ukazatel na potomka cílové položky. Pokud nějaký potomek existuje (tj. ukazatel je nenulový), připojí se k němu nová položka do řetězce sourozenců pomocí makra LISTADD. Následně se nastaví nová položka jako nový potomek cílové položky a ukazatel na cílovou položku se nastaví jako rodič nově přidávané položky.

Makro TREEDEL odpojí položku ze stromu. Pvním parametrem makra je registr s ukazatelem na rušenou položku. Položka nesmí být kořenem stromu (tj. ukazatel na rodiče nesmí být NULL). Druhý a třetí parametr jsou pomocné registry. Makro nejdříve odpojí rušenou položku z řetězce sourozenců (pomocí makra LISTDEL). Nastaví nového potomka rodiče a to buď na následujícího sourozence rušené položky nebo na NULL (pokud nenásleduje další sourozenec).


; -----------------------------------------------------------------------------
;                         Initialize tree list entry
; -----------------------------------------------------------------------------
; INPUT:	EBX = tree list entry
; -----------------------------------------------------------------------------

TreeInit:	TREEINIT ebx		; initialize tree list entry
		ret

; -----------------------------------------------------------------------------
;                     Add tree list entry into tree list
; -----------------------------------------------------------------------------
; INPUT:	EAX = new tree list entry
;		EBX = destination (parent) tree list entry
; NOTES:	Only TREE_Child must be initialized in new entry (it must
;		 contain either child list or null), other entries are ignored.
; -----------------------------------------------------------------------------

TreeAdd:	push	ecx		; push ECX
		push	edx		; push EDX
		TREEADD	ebx,eax,ecx,edx	; add new tree list entry into the list
		pop	edx		; pop EDX
		pop	ecx		; pop ECX
		ret

; -----------------------------------------------------------------------------
;             Delete (detach) tree list entry from the tree list
; -----------------------------------------------------------------------------
; INPUT:	EAX = tree list entry to delete (it must not be root entry!)
; -----------------------------------------------------------------------------

TreeDel:	push	ecx		; push ECX
		push	edx		; push EDX
		TREEDEL	eax,ecx,edx	; delete tree list entry
		pop	edx		; pop EDX
		pop	ecx		; pop ECX
		ret

Funkce TreeInit inicializuje položku stromu. Na vstupu funkce obsahuje registr EBX ukazatel na položku stromu. Funkce inicializuje seznam sourozenců na prázdný (tj. aby ukazatele ukazovaly samy na sebe) a vynuluje ukazatel na potomka a rodiče.

Funkce TreeAdd připojí položku stromu jako potomka k jiné položce stromu. Na vstupu funkce obsahuje registr EAX ukazatel na nově přidávanou položku, registr EBX obsahuje ukazatel na cílovou položku, ke které se má nová položka připojit. Nová položka musí mít inicializovaný ukazatel TREE_Child - musí obsahovat buď seznam potomků nebo NULL. Ostatní ukazatele se ignorují.

Funkce TreeDel odpojí položku ze stromu. Na vstupu funkce obsahuje registr EAX ukazatel na rušenou položku. Položka nesmí být kořenem stromu (tj. ukazatel na rodiče nesmí být NULL).