Procházení RB-stromem

Při procházení RB-stromem využíváme tříděný seznam položek spojený popisovači LIST.


; -----------------------------------------------------------------------------
;          Get first node (in sort order) of red-black balanced tree
; -----------------------------------------------------------------------------
; INPUT:	EDX = pointer to root (RBROOT)
; OUTPUT:	EBX = first node (NULL = none)
;		CY = no node found (EBX = NULL)
; -----------------------------------------------------------------------------

RBTreeFirst:	mov	ebx,[edx+LIST_Next]	; EBX <- first node
		test	byte [ebx+RB_Flags],RB_ROOT ; is it root?
		jz	RBTreeFirst2		; first node is valid
		xor	ebx,ebx			; EBX <- invalid node
		stc				; set error flag
RBTreeFirst2:	ret

Funkce RBTreeFirst vyhledá první uzel ve stromu, tedy položku, která je na začátku setříděného seznamu. Vstupním parametrem funkce je v registru EDX ukazatel na kořen stromu, výstupním parametrem je v registru EBX ukazatel na první položku stromu (nebo nula při chybě) a příznak chyby CF indikující, že žádná položka nebyla nalezena (tj. seznam je prázdný).

Z proměnné LIST_Next je do registru EBX načten ukazatel na první položku ve stromu. Testem příznaku RB_ROOT položky lze otestovat, zda se jedná o platnou položku. Jedná-li se opět o kořen stromu, je seznam položek prázdný. V tom případě se obsah registru EBX vynuluje a nastaví se příznak chyby CF.


; -----------------------------------------------------------------------------
;           Get last node (in sort order) of red-black balanced tree
; -----------------------------------------------------------------------------
; INPUT:	EDX = pointer to root (RBROOT)
; OUTPUT:	EBX = last node (NULL = none)
;		CY = no node found (EBX = NULL)
; -----------------------------------------------------------------------------

RBTreeLast:	mov	ebx,[edx+LIST_Prev]	; EBX <- last node
		test	byte [ebx+RB_Flags],RB_ROOT ; is it root?
		jz	RBTreeLast2		; last node is valid
		xor	ebx,ebx			; EBX <- invalid node
		stc				; set error flag
RBTreeLast2:	ret

Funkce RBTreeLast vyhledá poslední uzel ve stromu, tedy položku, která je na konci setříděného seznamu. Vstupním parametrem funkce je v registru EDX ukazatel na kořen stromu, výstupním parametrem je v registru EBX ukazatel na poslední položku stromu (nebo nula při chybě) a příznak chyby CF indikující, že žádná položka nebyla nalezena (tj. seznam je prázdný).

Z proměnné LIST_Prev je do registru EBX načten ukazatel na poslední položku ve stromu. Testem příznaku RB_ROOT položky lze otestovat, zda se jedná o platnou položku. Jedná-li se opět o kořen stromu, je seznam položek prázdný. V tom případě se obsah registru EBX vynuluje a nastaví se příznak chyby CF.


; -----------------------------------------------------------------------------
;           Get next node (in sort order) of red-black balanced tree
; -----------------------------------------------------------------------------
; INPUT:	EBX = pointer to current node (RBNODE)
; OUTPUT:	EBX = next node (NULL = none)
;		CY = no other node (EBX = NULL)
; -----------------------------------------------------------------------------

RBTreeNext:	mov	ebx,[ebx+LIST_Next]	; EBX <- next node
		test	byte [ebx+RB_Flags],RB_ROOT ; is it root?
		jz	RBTreeNext2		; next node is valid
		xor	ebx,ebx			; EBX <- invalid node
		stc				; set error flag
RBTreeNext2:	ret

Funkce RBTreeNext vyhledá následující uzel ve stromu, tedy položku, která následuje v setříděném seznamu za aktuální položkou. Vstupním parametrem funkce je v registru EBX ukazatel na aktuální položku, výstupním parametrem je v registru EBX ukazatel na další položku stromu (nebo nula při chybě) a příznak chyby CF indikující, že další položka nebyla nalezena (tj. položka je poslední položkou seznamu).

Z proměnné LIST_Next je do registru EBX načten ukazatel na další položku ve stromu. Testem příznaku RB_ROOT položky lze otestovat, zda se jedná o platnou položku. Jedná-li se opět o kořen stromu, nenásleduje další položka. V tom případě se obsah registru EBX vynuluje a nastaví se příznak chyby CF.


; -----------------------------------------------------------------------------
;          Get previous node (in sort order) of red-black balanced tree
; -----------------------------------------------------------------------------
; INPUT:	EBX = pointer to current node (RBNODE)
; OUTPUT:	EBX = previous node (NULL = none)
;		CY = no other node (EBX = NULL)
; -----------------------------------------------------------------------------

RBTreePrev:	mov	ebx,[ebx+LIST_Prev]	; EBX <- previous node
		test	byte [ebx+RB_Flags],RB_ROOT ; is it root?
		jz	RBTreePrev2		; previous node is valid
		xor	ebx,ebx			; EBX <- invalid node
		stc				; set error flag
RBTreePrev2:	ret

Funkce RBTreePrev vyhledá předešlý uzel ve stromu, tedy položku, která předchází v setříděném seznamu před aktuální položkou. Vstupním parametrem funkce je v registru EBX ukazatel na aktuální položku, výstupním parametrem je v registru EBX ukazatel na předcházející položku stromu (nebo nula při chybě) a příznak chyby CF indikující, že předešlá položka nebyla nalezena (tj. položka je první položkou seznamu).

Z proměnné LIST_Prev je do registru EBX načten ukazatel na předešlou položku ve stromu. Testem příznaku RB_ROOT položky lze otestovat, zda se jedná o platnou položku. Jedná-li se opět o kořen stromu, nenásleduje předešlá položka. V tom případě se obsah registru EBX vynuluje a nastaví se příznak chyby CF.


; -----------------------------------------------------------------------------
;             Get absolute indexed node of red-black balanced tree
; -----------------------------------------------------------------------------
; INPUT:	EAX = absolute index of node
;		EDX = pointer to root (RBROOT)
; OUTPUT:	EBX = node (NULL = none, index is not valid)
;		CY = node not found, index is not valid (EBX = NULL)
; -----------------------------------------------------------------------------

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

RBTreeIndex:	push	ecx			; push ECX

; ------------- Check index validity

		mov	ecx,[edx+RBR_Count]	; ECX <- number of nodes
		xor	ebx,ebx			; EBX <- 0, invalid index
		cmp	eax,ecx			; is index valid?
		cmc				; CY = index is not valid
		jc	RBTreeIndex8		; index is not valid

; ------------- Search node from begin or end of the list?

		shr	ecx,1			; ECX <- number of nodes/2
		cmp	eax,ecx			; is it upper half?
		jae	RBTreeIndex4		; it is upper half

; ------------- Search node in bottom half of the list

		mov	ecx,eax			; ECX <- required index
		mov	ebx,[edx+LIST_Next]	; EBX <- get first node
		jecxz	RBTreeIndex7		; first node required
RBTreeIndex2:	mov	ebx,[ebx+LIST_Next]	; EBX <- get next node
		loop	RBTreeIndex2		; next node
		jmp	short RBTreeIndex7

; ------------- Search node in upper half of the list

RBTreeIndex4:	mov	ecx,[edx+RBR_Count]	; ECX <- number of nodes
		sub	ecx,eax			; ECX <- remaining nodes
		dec	ecx			; ECX <- reverse index
		mov	ebx,[edx+LIST_Prev]	; EBX <- get last node
		jecxz	RBTreeIndex7		; last node required
RBTreeIndex6:	mov	ebx,[ebx+LIST_Prev]	; EBX <- get previous node
		loop	RBTreeIndex6		; previous node

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

RBTreeIndex7:	clc				; clear error flag
RBTreeIndex8:	pop	ecx			; pop ECX
		ret

Funkce RBTreeIndex vyhledá uzel ve stromu podle indexu, tedy vyhledá položku, která se v setříděném seznamu nachází na určité pozici seznamu. Vstupními parametry funkce jsou v registru EAX absolutní index požadované položky a v registru EDX ukazatel na kořen stromu. Výstupním parametrem je v registru EBX ukazatel na hledanou položku stromu (nebo nula při chybě) a příznak chyby CF indikující, že položka s daným indexem nebyla nalezena.

Na začátku funkce je ověřena platnost požadovaného indexu položky. Do registru ECX je z kořene stromu načten počet položek a porovnán s požadovaným indexem v registru EAX. Má-li požadovaný index stejnou nebo větší hodnotu než je počet položek ve stromu, funkce se ukončí s nastaveným příznakem chyby CF a s vynulovaným registrem EBX.

Pro zrychlení vyhledávání bude položka hledána buď od začátku seznamu nebo od jeho konce v závislosti na tom, kterému konci seznamu je blíže. Porovnáním požadovaného indexu v EAX s polovinou počtu položek v ECX se rozliší, zda bude výhodnější hledání od začátku (EAX < ECX/2) nebo od konce (EAX >= ECX/2).

Při hledání položky od začátku seznamu se do registru ECX uloží index požadované položky a z kořene stromu v registru EDX se načte první položka seznamu. Není třeba kontrolovat platnost položky, protože platnost indexu položky byla ověřena na začátku funkce. Je-li požadována první položka seznamu (index = 0), funkce se úspěšně ukončí. Jinak pokračuje procházením seznamu položek pomocí ukazatelů na další položky, až nalistuje hledanou položku.

Při hledání položky od konce seznamu se do registru ECX připraví počet položek seznamu a odečtením požadovaného indexu v EAX a dekrementací údaje se vypočte relativní index položky vzhledem ke konci seznamu. Z kořene stromu v registru EDX se načte poslední položka seznamu. Není třeba kontrolovat platnost položky, protože platnost indexu položky byla ověřena na začátku funkce. Je-li požadována poslední položka seznamu (index = počet - 1), funkce se úspěšně ukončí. Jinak pokračuje procházením seznamu položek pomocí ukazatelů na předešlé položky, až nalistuje hledanou položku.


; -----------------------------------------------------------------------------
;              Get relative indexed node of red-black balanced tree
; -----------------------------------------------------------------------------
; INPUT:	EAX = relative index of node (positive or negative)
;		EBX = pointer to current node
; OUTPUT:	EBX = node (NULL = none)
;		CY = node not found (EBX = NULL)
; -----------------------------------------------------------------------------

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

RBTreeIndexRel:	push	ecx			; push ECX

; ------------- Check if index is egative or positive

		or	eax,eax			; is index positive?
		mov	ecx,eax			; ECX <- relative index
		jz	RBTreeIndexRel9		; index is 0 (=this node)
		js	RBTreeIndexRel4		; index is negative

; ------------- Index is positive, find next node

RBTreeIndexRel2:call	RBTreeNext		; get next node
		jc	RBTreeIndexRel9		; no next node found
		loop	RBTreeIndexRel2		; next node
		jmp	short RBTreeIndexRel9

; ------------- Index is negative, find previous node

RBTreeIndexRel4:neg	ecx			; ECX <- relative index
RBTreeIndexRel6:call	RBTreePrev		; get previous node
		jc	RBTreeIndexRel9		; no previous node found
		loop	RBTreeIndexRel6		; previous node

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

RBTreeIndexRel9:pop	ecx			; pop ECX
		ret

Funkce RBTreeIndexRel vyhledá položku setříděného seznamu relativně k aktuální položce (jedná se tedy o posun o daný počet položek). Vstupem funkce je v registru EAX relativní index hledané položky (kladné nebo záporné číslo) a v registru EBX ukazatel na aktuální položku. Výstupem funkce je v registru EBX ukazatel na hledanou položku stromu (nebo nula při chybě) a příznak chyby CF indikující, že položka nebyla nalezena.

Na začátku funkce je testem hodnoty požadovaného indexu v EAX rozlišeno, zda se jedná o hledání směrem nahoru (EAX je kladné), dolů (EAX je záporné) nebo se jedná o tuto položku (EAX = 0, funkce se úspěšně ukončí).

Jedná-li se o hledání směrem nahoru (k vyšším indexům), posune se ukazatel pomocí funkce RBTreeNext o daný počet položek směrem vpřed. Je-li nalezen konec seznamu, funkce se předčasně ukončí s nastaveným příznakem chyby a s vynulovaným registrem EBX.

Jedná-li se o hledání směrem dolů (k nižším indexům), opraví se znaménko relativního indexu v registru ECX a ukazatel se posune pomocí funkce RBTreePrev o daný počet položek směrem zpět. Je-li nalezen začátek seznamu, funkce se předčasně ukončí s nastaveným příznakem chyby a s vynulovaným registrem EBX.


; -----------------------------------------------------------------------------
;                    Verify node in red-black balanced tree
; -----------------------------------------------------------------------------
; INPUT:	EBX = pointer to node (RBNODE)
;		EDX = pointer to root (RBROOT)
; OUTPUT:	EAX = index of the node (or -1 = node not found)
;		CY = node not found (EAX = -1)
; NOTES: This function can be used to verify that tree contains the node.
; -----------------------------------------------------------------------------

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

RBTreeVerify:	push	ebx			; push EBX
		push	ecx			; push ECX

; ------------- Get last node

		mov	ecx,ebx			; ECX <- node to find
		mov	eax,[edx+RBR_Count]	; EAX <- number of nodes
		dec	eax			; EAX <- index of last node
		call	RBTreeLast		; get last node
		jc	RBTreeVerify8		; no last node (and EAX = -1)

; ------------- Search node

RBTreeVerify2:	cmp	ecx,ebx			; is it searched node?
		je	RBTreeVerify8		; node found OK
		dec	eax			; EAX <- decrease node index
		call	RBTreePrev		; get previous node
		jnc	RBTreeVerify2		; previous node OK, continue

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

RBTreeVerify8:	pop	ecx			; pop ECX
		pop	ebx			; pop EBX
		ret

Funkce RBTreeVerify slouží k ověření, zda položka patří do daného RB-stromu. Vstupními parametry funkce jsou v registru EBX ukazatel na hledanou položku a v registru EDX ukazatel na kořen stromu. Je-li položka ve stromu nalezena, navrátí funkce v registru EAX index položky a vynuluje příznak CF. Není-li nalezena, navrátí index položky -1 a nastavený příznak chyby CF.

Funkce si připraví do registru ECX adresu položky k vyhledání, do registru EAX si připraví index poslední položky seznamu a pomocí funkce RBTreeLast zjistí ukazatel na poslední položku seznamu. Neexistuje-li poslední položka seznamu (tj. seznam je prázdný), funkce se ukončí s nastaveným příznakem chyby a s registrem EAX nastaveným na -1 (protože počet položek v seznamu = 0).

Během vyhledávání položek je adresa každé položky porovnána, zda se jedná o hledanou položku, v tom případě je funkce ukončena s vynulovaným příznakem chyby, registr EAX obsahuje index položky. Jinak je index položky dekrementován a pomocí funkce RBTreePrev je vyhledána předcházející položka seznamu. Není-li nalezena žádná další předešlá položka (tj. dosáhlo se začátku seznamu), je funkce ukončena s příznakem chyby CF, registr EAX obsahuje hodnotu -1 (ukazatel indexu podtekl pod 0).


; -----------------------------------------------------------------------------
;              Get index of the node in red-black balanced tree
; -----------------------------------------------------------------------------
; INPUT:	EBX = pointer to node (RBNODE)
; OUTPUT:	EAX = index of the node
;		EDX = pointer to root (RBROOT)
; NOTES:	Node must be included in a valid red-black tree.
; -----------------------------------------------------------------------------

RBTreeGetInx:	xor	eax,eax			; EAX <- 0, node index
		mov	edx,ebx			; EDX <- current node
		dec	eax			; EAX <- -1, preset index
RBTreeGetInx2:	mov	edx,[edx+LIST_Prev]	; EBX <- get previous node
		inc	eax			; EAX <- increase node index
		test	byte [edx+RB_Flags],RB_ROOT ; is it root?
		jz	RBTreeGetInx2		; node is valid, try next one
		ret

Funkce RBTreeGetInx slouží k zjištění indexu položky v seznamu a k nalezení kořene stromu. Na rozdíl od předešlé funkce musí být položka seznamu začleněná do nějakého platného RB-stromu. Vstupním parametrem funkce je v registru EBX ukazatel na hledanou položku. Výstupním parametrem je v registru EAX index položky ve stromu a v registru EDX ukazatel na kořen stromu. Vzhledem k tomu, že položka musí být začleněná do platného stromu, není funkcí navracen žádný chybový kód.

Funkce přednastaví v registru EAX ukazatel indexu položky na hodnotu -1 a do registru EDX si připraví ukazatel na aktuální položku. Poté prochází seznam tříděných položek směrem k počátku seznamu, přičemž postupně inkrementuje index položky, a to do té doby, než narazí na kořen stromu (rozpozná ho podle nastaveného příznaku RB_ROOT), jehož adresu navrátí v registru EDX.