Manipulace s RB-stromem

Následující funkce jsou podpůrné funkce používané jinými funkcemi k manipulaci s RB-stromem.

Funkce RBTreeLeft rotuje větev stromu směrem doleva. Operace rotace doleva spočívá v přestavění struktury větve tak, že namísto aktuálního uzlu se k rodiči připojí pravý potomek uzlu, aktuální uzel se stane levým potomkem pravého uzlu a levý potomek pravého uzlu se stane pravým potomkem aktuálního uzlu. Jak je zřejmé i z obrázku, změní se tak vyvážení větve stromu se zachováním pořadí třídení položek stromu.


; -----------------------------------------------------------------------------
;                    Rotate red-black balanced tree left
; -----------------------------------------------------------------------------
; INPUT:	EBX = pointer to current node (RBNODE)
;		EDX = pointer to root (RBROOT)
; NOTES:	Right node must be valid.
; -----------------------------------------------------------------------------
;                  ri-le   ri-ri             left   ri-le
;                      \   /                    \   /
;               left   right                     node   ri-ri
;                  \   /           --->             \   /
;             ...   node                      ...   right
;               \   /                           \   /
;               parent                          parent
; -----------------------------------------------------------------------------
; Local variables:
%define		RBRi	EAX			; right node
%define		RBNo	EBX			; current node
%define		RBRL	ECX			; right-left node (hardcoded)
%define		RBRLL	CL			; right-left node LOW (temp.)
%define		RBRo	EDX			; root
%define		RBPa	ESI			; parent

; ------------- Push registers

RBTreeLeft:	push	RBRi			; push RBRi
		push	RBRL			; push RBRL
		push	RBPa			; push RBPa

; ------------- Get other nodes

		mov	RBRi,[RBNo+RBN_Right]	; get right node
		mov	RBRL,[RBRi+RBN_Left]	; get right-left node
		mov	RBPa,[RBNo+RBN_Parent]	; get parent

; ------------- Link right-left node as new right node of current node

		mov	[RBNo+RBN_Right],RBRL	; set as new right node
		jecxz	RBTreeLeft2		; no right-left node
		mov	[RBRL+RBN_Parent],RBNo	; current node is its parent

; ------------- Link current node as new left node of right node

RBTreeLeft2:	mov	[RBRi+RBN_Left],RBNo	; node is left for right one
		mov	[RBNo+RBN_Parent],RBRi	; new parent for current node
		
; ------------- Link right node to root

		mov	[RBRi+RBN_Parent],RBPa	; new parent for right node
		or	RBPa,RBPa		; is parent a root?
		jnz	RBTreeLeft4		; parent is not a root
		mov	[RBRo+RBR_Node],RBRi	; link right node to root
		jmp	short RBTreeLeft8

; ------------- Link right node to valid parent

RBTreeLeft4:    xor	RBRL,RBRL		; RBRL <- 0
		cmp	RBNo,[RBPa+RBN_Right]	; was it right or left node?
		sete	RBRLL			; RBRLL <- 1 (right), 0 (left)
		mov	[RBPa+RBN_Left+RBRL*(RBN_Right-RBN_Left)],RBRi

; ------------- Pop registers

RBTreeLeft8:	pop	RBPa			; pop RBPa
		pop	RBRL			; pop RBRL
		pop	RBRi			; pop RBRi
		ret

Vstupními parametry funkce jsou v registru EBX ukazatel na aktuální uzel stromu RBNo a v registru EDX ukazatel na kořen stromu RBRo. Pravý potomek aktuálního uzlu musí být platný. Pro zvýšení přehlednosti jsou ve funkci namísto registrů používány jejich symbolické popisy odpovídající obsahu registru. Ostatní registry použité ve funkci (EAX, ECX a ESI) jsou uchovány instrukcemi PUSH/POP.

Na začátku funkce jsou připraveny ukazatele na ostatní uzly větve. Do registru RBRi (EAX) je z aktuálního uzlu RBNo (EBX) načten ukazatel na pravý uzel, do registru RBRL (ECX) je z pravého uzlu RBRi (EAX) načten ukazatel na pravý-levý uzel (tj. levý potomek pravého uzlu) a do registru RBPa (ESI) je z aktuálního uzlu RBNo (EBX) načten ukazatel na rodiče uzlu.

Pravý-levý uzel bude spojen s aktuálním uzlem. Ukazatel na pravý-levý uzel RBRL (ECX) je uložen do pravého ukazatele aktuální položky RBNo (EBX). Ukazatel na aktuální položku RBNo (EBX) je uložen do ukazatele na rodiče pravého-levého uzlu RBRL (ECX), ale to jen v případě, že pravý-levý uzel je platný.

Aktuální uzel bude spojen s pravým uzlem. Ukazatel na aktuální uzel RBNo (EBX) je uložen do levého ukazatele pravého uzlu RBRi (EAX) a ukazatel na pravý uzel RBRi (EAX) je uložen do ukazatele na rodiče aktuální položky RBNo (EBX).

Nyní je potřeba spojít pravý uzel s rodičem. Ukazatel na rodiče RBPa (ESI) je nastaven do ukazatele na rodiče pravého uzlu RBRi (EAX). Testem registru RBPa (ESI) je rozlišeno, zda je rodičem jiný uzel (registr není 0) nebo zda je rodičem kořen stromu (registr je 0). Je-li rodičem kořen stromu, uloží se ukazatel na pravý uzel RBRi (EAX) do ukazatele na výchozí uzel stromu kořene stromu RBRo (EDX).

Není-li rodičem kořen stromu (tj. rodičem je jiný uzel stromu), je potřeba uložit ukazatel na pravý uzel buď do levého nebo do pravého ukazatele rodiče. V přípravě je vynulován obsah registru RBRL (ECX, bude nyní použit jako pracovní registr) a ukazatel na aktuální uzel RBNo (EBX) je porovnán s ukazatelem na pravý uzel rodiče RBPa (ESI), aby se provedl test, zda byl aktuální uzel levým nebo pravým potomkem rodiče. Pokud byl pravým potomkem, nastaví operace porovnání příznak ZF. To se využije v následující instrukci, která nastaví registr RBRLL (CL) na hodnotu 1, pokud byl uzel pravým potomkem, jinak bude hodnota registru 0. Další instrukce uloží ukazatel na pravý uzel RBRi (EAX) do levého nebo pravého ukazatele rodiče RBPa (ESI) s využitím registru RBRL (ECX) jako indexu.

Funkce RBTreeRight rotuje větev stromu směrem doprava. Operace rotace doprava spočívá v přestavění struktury větve tak, že namísto aktuálního uzlu se k rodiči připojí levý potomek uzlu, aktuální uzel se stane pravým potomkem levého uzlu a pravý potomek levého uzlu se stane levým potomkem aktuálního uzlu. Jak je zřejmé i z obrázku, změní se tak vyvážení větve stromu se zachováním pořadí třídení položek stromu.


; -----------------------------------------------------------------------------
;                    Rotate red-black balanced tree right
; -----------------------------------------------------------------------------
; INPUT:	EBX = pointer to current node (RBNODE)
;		EDX = pointer to root (RBROOT)
; NOTES:	Left node must be valid.
; -----------------------------------------------------------------------------
;           le-le   le-ri                        le-ri   right
;               \   /                                \   /
;               left   right                  le-le   node
;                  \   /           --->           \   /
;             ...   node                    ...   left
;               \   /                         \   /
;               parent                        parent
; -----------------------------------------------------------------------------
; Local variables:
%define		RBLe	EAX			; left node
%define		RBNo	EBX			; current node
%define		RBLR	ECX			; left-right node (hardcoded)
%define		RBLRL	CL			; left-right node LOW (temp.)
%define		RBRo	EDX			; root
%define		RBPa	ESI			; parent

; ------------- Push registers

RBTreeRight:	push	RBLe			; push RBLe
		push	RBLR			; push RBLR
		push	RBPa			; push RBPa

; ------------- Get other nodes

		mov	RBLe,[RBNo+RBN_Left]	; get left node
		mov	RBLR,[RBLe+RBN_Right]	; get left-right node
		mov	RBPa,[RBNo+RBN_Parent]	; get parent

; ------------- Link left-right node as new left node of current node

		mov	[RBNo+RBN_Left],RBLR	; set as new left node
		jecxz	RBTreeRight2		; no left-right node
		mov	[RBLR+RBN_Parent],RBNo	; current node is its parent

; ------------- Link current node as new right node of left node

RBTreeRight2:	mov	[RBLe+RBN_Right],RBNo	; node is right for left one
		mov	[RBNo+RBN_Parent],RBLe	; new parent for current node
		
; ------------- Link left node to root

		mov	[RBLe+RBN_Parent],RBPa	; new parent for left node
		or	RBPa,RBPa		; is parent a root?
		jnz	RBTreeRight4		; parent is not a root
		mov	[RBRo+RBR_Node],RBLe	; link left node to root
		jmp	short RBTreeRight8

; ------------- Link left node to valid parent

RBTreeRight4:	xor	RBLR,RBLR		; RBLR <- 0
		cmp	RBNo,[RBPa+RBN_Right]	; was it right or left node?
		sete	RBLRL			; RBRLL <- 1 (right), 0 (left)
		mov	[RBPa+RBN_Left+RBLR*(RBN_Right-RBN_Left)],RBLe

; ------------- Pop registers

RBTreeRight8:	pop	RBPa			; pop RBPa
		pop	RBLR			; pop RBLR
		pop	RBLe			; pop RBLe
		ret

Vstupními parametry funkce jsou v registru EBX ukazatel na aktuální uzel stromu RBNo a v registru EDX ukazatel na kořen stromu RBRo. Levý potomek aktuálního uzlu musí být platný. Pro zvýšení přehlednosti jsou ve funkci namísto registrů používány jejich symbolické popisy odpovídající obsahu registru. Ostatní registry použité ve funkci (EAX, ECX a ESI) jsou uchovány instrukcemi PUSH/POP.

Na začátku funkce jsou připraveny ukazatele na ostatní uzly větve. Do registru RBLe (EAX) je z aktuálního uzlu RBNo (EBX) načten ukazatel na levý uzel, do registru RBLR (ECX) je z levého uzlu RBLe (EAX) načten ukazatel na levý-pravý uzel (tj. pravý potomek levého uzlu) a do registru RBPa (ESI) je z aktuálního uzlu RBNo (EBX) načten ukazatel na rodiče uzlu.

Levý-pravý uzel bude spojen s aktuálním uzlem. Ukazatel na levý-pravý uzel RBLR (ECX) je uložen do levého ukazatele aktuální položky RBNo (EBX). Ukazatel na aktuální položku RBNo (EBX) je uložen do ukazatele na rodiče levého-pravého uzlu RBLR (ECX), ale to jen v případě, že levý-pravý uzel je platný.

Aktuální uzel bude spojen s levým uzlem. Ukazatel na aktuální uzel RBNo (EBX) je uložen do pravého ukazatele levého uzlu RBLe (EAX) a ukazatel na levý uzel RBLe (EAX) je uložen do ukazatele na rodiče aktuální položky RBNo (EBX).

Nyní je potřeba spojít levý uzel s rodičem. Ukazatel na rodiče RBPa (ESI) je nastaven do ukazatele na rodiče levého uzlu RBLe (EAX). Testem registru RBPa (ESI) je rozlišeno, zda je rodičem jiný uzel (registr není 0) nebo zda je rodičem kořen stromu (registr je 0). Je-li rodičem kořen stromu, uloží se ukazatel na levý uzel RBLe (EAX) do ukazatele na výchozí uzel stromu kořene stromu RBRo (EDX).

Není-li rodičem kořen stromu (tj. rodičem je jiný uzel stromu), je potřeba uložit ukazatel na levý uzel buď do levého nebo do pravého ukazatele rodiče. V přípravě je vynulován obsah registru RBLR (ECX, bude nyní použit jako pracovní registr) a ukazatel na aktuální uzel RBNo (EBX) je porovnán s ukazatelem na pravý uzel rodiče RBPa (ESI), aby se provedl test, zda byl aktuální uzel levým nebo pravým potomkem rodiče. Pokud byl pravým potomkem, nastaví operace porovnání příznak ZF. To se využije v následující instrukci, která nastaví registr RBLRL (CL) na hodnotu 1, pokud byl uzel pravým potomkem, jinak bude hodnota registru 0. Další instrukce uloží ukazatel na levý uzel RBLe (EAX) do levého nebo pravého ukazatele rodiče RBPa (ESI) s využitím registru RBLR (ECX) jako indexu.