Vložení položky do RB-stromu


; -----------------------------------------------------------------------------
;                 Insert new entry into red-black balanced tree
; -----------------------------------------------------------------------------
; INPUT:	EAX = pointer to new entry (RBNODE with filled user data)
;		EDX = pointer to root (RBROOT)
;		ESI = callback compare function
;			INPUT:	EAX = pointer to new entry (with user data)
;				EBX = node to test
;			OUTPUT:	ZY = equal, CY = EAX.Data < EBX.Data
;				(as CMP EAX.Data,EBX.Data)
; OUTPUT:	CY = entry already exists (EBX = pointer to existing node)
;		EBX = pointer to existing entry (if CY) or new entry (=EAX)
; -----------------------------------------------------------------------------

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

RBTreeInsert:	push	ecx			; push ECX

; ------------- Initialize new node

		xor	ecx,ecx			; ECX <- 0
		mov	[eax+RB_ColorFlags],cx	; set color to red, clear flags
		mov	[eax+RBN_Left],ecx	; no left node
		mov	[eax+RBN_Right],ecx	; no right node

; ------------- Get first node

		mov	ecx,[edx+RBR_Node]	; ECX <- get first node
		jecxz	RBTreeInsert3		; tree is empty

; ------------- Next node is valid

RBTreeInsert2:	mov	ebx,ecx			; EBX <- node is valid

; ------------- Compare data

		call	esi			; test data
		jb	RBTreeInsert4		; data is lower
		stc				; set error flag
		je	RBTreeInsert9		; node already exists

; ------------- Higher data, use right branch

		mov	ecx,[ebx+RBN_Right]	; ECX <- right node
		or	ecx,ecx			; is right node valid?
		jnz	RBTreeInsert2		; right node is valid

; ------------- Insert new node to the right

		mov	[ebx+RBN_Right],eax	; insert node to the right
		call	ListAfter		; add entry into list
		jmp	short RBTreeInsert6

; ------------- Store node into root

RBTreeInsert3:	mov	ebx,edx			; EBX <- root
		call	ListAdd			; add entry into list
		mov	[edx+RBR_Node],eax	; link root to this node
		mov	[eax+RBN_Parent],ecx	; set parent to NULL
		inc	byte [eax+RB_Color]	; set color to black for root
		mov	ebx,eax			; EBX <- new node
		jmp	short RBTreeInsert8

; ------------- Lower data, use left branch

RBTreeInsert4:	mov	ecx,[ebx+RBN_Left]	; ECX <- left node
		or	ecx,ecx			; is left node valid?
		jnz	RBTreeInsert2		; left node is valid

; ------------- Insert new node to the left

		mov	[ebx+RBN_Left],eax	; insert node to the left
		call	ListBefore		; add entry into list
RBTreeInsert6:	mov	[eax+RBN_Parent],ebx	; set node as parent of new one

; ------------- Insert red color into tree

		mov	ebx,eax			; EBX <- new node
		call	RBTreeInsCol		; insert color

; ------------- Increate number of entries

RBTreeInsert8:	inc	dword [edx+RBR_Count]	; increase number of entries

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

		clc				; clear error flag
RBTreeInsert9:	pop	ecx			; pop ECX
		ret

Funkce RBTreeInsert vloží novou položku do RB-stromu. Vstupními parametry funkce jsou v registru EAX ukazatel na nově vkládanou položku s vyplněnými uživatelskými daty, v registru EDX ukazatel na kořen stromu a v registru ESI ukazatel na porovnávací callback funkci. Je-li položka úspěšně vložena, je navrácen vynulovaný příznak CF a v registru EBX je navrácen ukazatel na novou položku, jeho obsah tedy odpovídá obsahu registru EAX. Pokud již existuje položka se stejnými daty (ve stromu se nesmí vyskytovat dvě stejné položky), je navrácen příznak chyby CY (nastavený příznak CF) a registr EBX ukazuje na nalezenou položku se stejnými daty.

Porovnávací callback funkce má jako vstupní parametr v registru EAX ukazatel na nově vkládanou položku a v registru EBX ukazatel na testovanou položku. Porovnávací funkce navrací nastavené příznaky tak, jako by to udělala porovnávací instrukce - jsou-li položky shodné, navrátí nastavený příznak ZF a vynulovaný příznak CF. Je-li třídicí klíč nové položky menší než porovnávaná položka, navrátí vynulovaný příznak ZF a nastavený příznak CF. Je-li třídicí klíč nové položky větší, navrátí vynulovaný příznak ZF i příznak CF.

Na začátku funkce RBTreeInsert je nově vkládaná položka inicializována - je nastavena na červenou barvu, vypnut příznak kořene stromu, vynulován levý a pravý potomek.

Před vložením nové položky je nejdříve potřeba vyhledat místo, kam bude položka vložena. Do registru ECX se načte ukazatel na výchozí položku stromu z kořene stromu v EDX.

Je-li ukazatel nulový, není ve stromu žádná položka, nová položka bude první položkou stromu (funkce pokračuje na návěští RBTreeInsert3). Nová položka se přidá do seznamu položek připojením položky ke kořeni stromu pomocí funkce ListAdd. Ukazatel na položku se nastaví do kořene jako ukazatel na výchozí položku stromu. Rodič nové položky se vynuluje (rodičem je kořen). Její barva se změní na černou barvu (kořenová položka stromu má vždy černou barvu). Do registru EBX se uloží ukazatel na novou položku, zvýší se čítač položek ve stormu a funkce se úspěšně ukončí s vynulovaným příznakem chyby CF.

Je-li ukazatel na výchozí položku v registru ECX platný, uloží se do registru EBX jako ukazatel na aktuální prohledávanou položku.

Nová položka v registru EAX se porovná s testovaným uzlem v registru EBX voláním porovnávací callback funkce, jejíž adresa je v registru ESI, a vyhodnotí se navrácené příznaky výsledku porovnání. Jsou-li data nové položky shodná s daty testované položky, nastaví se příznak chyby a funkce se předčasně ukončí. V tom případě bude registr EBX obsahovat ukazatel na uzel s nalezenými shodnými daty.

Jsou-li data nové položky větší než data testované položky, bude hledání dále pokračovat pravou větví. Do registru ECX se načte ukazatel na pravého potomka a pokud je platný (tj. není nulový) použije se ukazatel v ECX jako nový ukazatel na aktuální položku a pokračuje se testem další položky. Není-li ukazatel platný (tj. je nulový), bude nová položka novým pravým potomkem. Ukazatel na novou položku se uloží jako ukazatel na pravého potomka a nová položka se přidá funkcí ListAfter do tříděného seznamu položek za aktuální položku v EBX a pokračuje se částí společnou pro oba směry.

Jsou-li data nové položky menší než data testované položky, bude hledání dále pokračovat levou větví (návěští RBTreeInsert4). Do registru ECX se načte ukazatel na levého potomka a pokud je platný (tj. není nulový) použije se ukazatel v ECX jako nový ukazatel na aktuální položku a pokračuje se testem další položky. Není-li ukazatel platný (tj. je nulový), bude nová položka novým levým potomkem. Ukazatel na novou položku se uloží jako ukazatel na levého potomka a nová položka se přidá funkcí ListBefore do tříděného seznamu položek před aktuální položku v EBX a pokračuje se částí společnou pro oba směry.

Dále v případě obou směrů se ukazatel na aktuální položku v EBX uloží jako rodič do nově vkládané položky v EAX. Funkcí RBTreeInsCol (viz dále) se vloží na pozici nové položky červená barva s obsluhou vyvážení stromu, zvýší se čítač položek ve stromu a funkce se úspěšně ukončí s vynulovaným příznakem chyby CF. Registr EBX bude v tomto případě obsahovat ukazatel na novou položku a bude shodný s registrem EAX.


; -----------------------------------------------------------------------------
;                Insert red color into red-black balanced tree
; -----------------------------------------------------------------------------
; INPUT:	EBX = pointer to current node (RBNODE, its color is red)
;		EDX = pointer to root (RBROOT)
; -----------------------------------------------------------------------------
; Local variables:
%define		RBGr	EAX			; grand parent
%define		RBNo	EBX			; current node
%define		RBUn	ECX			; uncle
%define		RBRo	EDX			; root
%define		RBPa	ESI			; parent

; ============= RBTreeInsCol function

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

RBTreeInsCol:	push	RBGr			; push RBGr
		push	RBNo			; push RBNo
		push	RBUn			; push RBUn
		push	RBPa			; push RBPa

; ------------- Get parent

RBTreeInsCol2:	mov	RBPa,[RBNo+RBN_Parent]	; get parent
		or	RBPa,RBPa		; is parent valid?
		jz	RBTreeInsCol8		; no other parent

; ------------- Check if parent is red

		CMPRED	RBPa			; parent is red?
		jne	RBTreeInsCol8		; parent is not red

; ------------- Get grand parent and check if parent is left of grand parent
; Parent is red and therefore grandpa is always valid (because root is black)

		mov	RBGr,[RBPa+RBN_Parent]	; get grand parent
		cmp	RBPa,[RBGr+RBN_Left]	; is parent left of grandpa?
		jne	short RBTreeInsCol4	; no, it is right of grandpa

; ------------- Parent is left of grand parent

		RBTreeInsC Left, Right		; insert color for left
		jmp	short RBTreeInsCol2	; next node

; ------------- Parent is right of grand parent

RBTreeInsCol4:	RBTreeInsC Right, Left		; insert color for right
		jmp	RBTreeInsCol2		; next node

; ------------- Set root node black

RBTreeInsCol8:	mov	RBNo,[RBRo+RBR_Node]	; get root node
		SETBLK	RBNo			; set root node black

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

		pop	RBPa			; pop RBPa
		pop	RBUn			; pop RBUn
		pop	RBNo			; pop RBNo
		pop	RBGr			; pop RBGr
		ret

Funkce RBTreeInsCol je pomocnou funkcí pro funkci RBTreeInsert. Zajišťuje vyvážení stromu po vložení nové položky do stromu. Vstupními parametry funkce jsou v registru EBX ukazatel na nově vloženou položku stromu (barva nové položky byla nastavena na červenou) a v registru EDX ukazatel na kořen stromu. Funkce RBTreeInsCol a makro RBTreeInsC (viz dále) používají namísto jmen registrů jejich symbolická označení: RBGr (EAX) označuje prarodiče (tj. rodič rodiče), RBNo (EBX) je aktuální položka, RBUn (ECX) je "strýc" neboli bratr rodiče neboli sousední položka patřící ke stejnému prarodiči, RBRo (EDX) je kořen stromu a RBPa (ESI) je rodič.

Uvnitř funkce probíhá cyklus přes uzly stromu. Ukazatelem aktuálního uzlu je registr RBNo, který na začátku funkce obsahuje ukazatel na nově vloženou položku. Aktuální uzel je výchozí uzel větve, jejíž váha se díky vložení nové položky zvýšila. Aktuální uzel má červenou barvu. Pokud měla větev již předtím větší váhu a po vložení nové položky by délka narostla na více než dvojnásobnou hloubku, provede se vyvážení větve - rotace. Pokračuje se dále k nižšímu uzlu, dokud se nenarazí na uzel, který již nepotřebuje vyvážení (posledním uzlem je kořen, který má vždy černou barvou a tím dojde k přerušení iterace).

Do registru rodiče RBPa (ESI) je z aktuálního uzlu RBNo (EBX) načten ukazatel na rodiče. Je-li rodičem kořen stromu (tj. ukazatel na rodiče je nulový), funkce se ukončí s nastavením kořene stromu na černou barvu (pomocí makra SETBLK). Jinak se pomocí makra CMPRED provede test, zda má rodič červenou barvu a pokud ne, není třeba větev vyvažovat a funkce se ukončí opět s nastavením černé barvy kořene.

Je-li rodič červený, je nutné provést vyvážení větve a opravu barev - aktuální uzel je také červený a to by bylo porušení pravidla RB-stromu. Do registru prarodiče RBGr (EAX) se z rodiče načte ukazatel na prarodiče. Vzhledem k tomu, že rodič je červený, není třeba testovat platnost prarodiče, protože může být neplatný jen v případě kořenového uzlu a ten má vždy černou barvu. Porovnáním rodiče s ukazatelem na levého potomka prarodiče se rozliší, zda je rodič levým nebo pravým potomkem prarodiče a podle toho se vyvolá makro pro vyvážení větve stromu RBTreeInsC (viz dále) - s parametry Left/Right nebo obráceně.


; ============= Macros

; ------------- Macro - insert color in one direction
; Parameters (direction word): %1 = Left (Right), %2 = Right (Left)

%macro		RBTreeInsC 2

; ------------- Get uncle as grand parent's right (left) node

		mov	RBUn,[RBGr+RBN_%2]	; get uncle
		or	RBUn,RBUn		; is uncle valid?
		jz	short %%L2		; uncle is invalid

; ------------- Check if uncle is red

		CMPRED	RBUn			; is uncle red?
		jne	short %%L2		; uncle is not red
		
; ------------- Uncle is red, set uncle and parent black, set grandpa red

		SETBLK	RBUn			; set uncle black
		SETBLK	RBPa			; set parent black
		SETRED	RBGr			; set grandpa red
		mov	RBNo,RBGr		; node <- grand parent
		jmp	short RBTreeInsCol2	; next node

; ------------- Uncle is black, check if node is right (left) node of parent 

%%L2:		cmp	RBNo,[RBPa+RBN_%2]	; is node right (left) node?
		jne	short %%L4		; node is not right (left) node

; ------------- Rotate left (right) to become node as new parent node

		push	RBNo			; push RBNo
		mov	RBNo,RBPa		; parent will be used
		call	RBTree%1		; rotate parent left (right)
		pop	RBPa			; parent <- node

; ------------- Set parent black, set grandpa red and rotate it right (left)

%%L4:		SETBLK	RBPa			; set parent black
		SETRED	RBGr			; set grandpa red
		push	RBNo			; push RBNo
		mov	RBNo,RBGr		; grandpa will be used
		call	RBTree%2		; rotate grandpa right (left)
		pop	RBNo			; pop RBNo
%endmacro

Makro RBTreeInsC zajistí vyvážení větve stromu pro daný aktuální uzel (uzel má červenou barvu a jeho rodič také, což je příznak nevyváženého stavu). Makro má dva parametry - texty názvů přilehlé a protilehlé strany. Pro vložení barvy pro levý směr jsou parametry Left a Right, pro vložení barvy pro pravý směr jsou parametry Right a Left. První parametr představuje směr, ve kterém leží rodič v uzlu prarodiče, druhý parametr představuje smět opačný. Parametry jsou v makru dosazeny do jmen proměnných (např. RBN_%2 se nahradí textem RBN_Left).

Na vstupu makra jsou platné obsahy položek RBGr (EAX, prarodič), RBPa (ESI, rodič) a RBNo (EBX, aktuální položka).

Na začátku makra je nejdříve získán strýc - tedy protější položka k rodiči, patřící ke stejnému prarodiči. Je-li aktuálním směrem směr vlevo (tj. rodič je levým potomkem prarodiče), načte se strýc z proměnné RBN_Right prarodiče. Je-li aktuálním směrem směr vpravo, načte se strýc z proměnné RBN_Left prarodiče. Je-li strýc neplatná položka, tj. ukazatel je NULL, pokračuje se dále návěštím %%L2 jakoby měl strýc černou barvu. Je-li strýc platný, provede se makrem CMPRED test, zda má strýc červenou barvu. Nemá-li červenou barvu, pokračuje se dále návěštím %%L2 stejně jako v případě neplatného ukazatele na strýce.

Má-li strýc červenou barvu, provede se oprava barev. V této chvíli má aktuální položka červenou barvu a její rodič a strýc také. Znamená to, že větev s aktuálním uzlem je stejně dlouhá nebo delší než sousední větev, ale ještě ne na tolik, aby se větev rotovala. Provede se tedy pouze oprava barev nastavením barvy strýce a rodiče na černou barvu pomocí makra SETBLK a změnou barvy prarodiče na červenou barvu pomocí makra SETRED. Prarodič bude nová aktuální položka a provede se pro ni nový test a vyvážení větve.

Má-li strýc černou barvu, provede se test, zda je nově vložená položka na stejné straně jako je strýc, tj. zda se nachází na "vnitřní" straně rodiče, směrem ke strýci. V tom případě se stal uzel nevyváženým a je potřeba ho vyvážit rotací opačným směrem tak, aby se aktuální uzel stal novým rodičem a jeho původní rodič aby se stal jeho potomkem na vnější straně. Tím se zkrátí větev s aktuální položkou. Pokud se tedy koriguje rodič v levém směru, aktuální položka se nachází v pravém směru od rodiče, provede se rotace vlevo, původní rodič se stane nyní levým potomkem aktuální položky. A obráceně. Rodič se stane novou aktuální položkou a původní aktuální položka se stává novým rodičem.

Po případné rotaci větve následuje vyvážení uzlu prarodiče. Barva rodiče se pomocí makra SETBLK nastaví na černou, barva prarodiče pomocí makra SETRED na červenou a uzel s prarodičem se rotuje v obráceném směru než je směr rodiče, tím se rodič dostane na místo prarodiče a větev se dostane do vyváženého stavu.


; -----------------------------------------------------------------------------
;         Insert new entry into red-black balanced tree with address
; -----------------------------------------------------------------------------
; INPUT:	EAX = pointer to new entry (RBNODE)
;		EDX = pointer to root (RBROOT)
; OUTPUT:	CY = entry already exists (EBX = pointer to existing node)
;		EBX = pointer to existing entry (if CY) or new entry (=EAX)
; -----------------------------------------------------------------------------

RBTreeInsAddr:	push	esi			; push ESI
		mov	esi,RBTreeInsAddr4	; ESI <- callback function
		call	RBTreeInsert		; insert new entry
		pop	esi			; pop ESI
		ret

; ------------- Callback compare function for address

RBTreeInsAddr4:	cmp	eax,ebx			; compare nodes
		ret

Funkce RBTreeInsAddr vloží do RB-stromu novou položku, strom bude tříděn podle adresy položek. Takový strom je nutné prohledávat pomocí funkce RBTreeSrcAddr. Vstupními parametry funkce jsou v registru EAX ukazatel na novou položku stromu a v registru EDX ukazatel na kořen stromu.

Je-li položka úspěšně vložena, je navrácen vynulovaný příznak CF a v registru EBX je navrácen ukazatel na novou položku. Jeho obsah tedy odpovídá obsahu registru EAX. Pokud již existuje položka se stejnou adresou (ve stromu se nesmí vyskytovat dvě stejné položky), je navrácen příznak chyby CY (nastavený příznak CF) a registr EBX ukazuje na nalezenou položku se stejnou adresou.

Funkce volá obsluhu funkce RBTreeInsert a předává jí ukazatel na vlastní porovnávací funkci RBTreeInsAddr4, která porovnává adresy položek.


; -----------------------------------------------------------------------------
;     Insert new entry into red-black balanced tree with WORD data unsigned
; -----------------------------------------------------------------------------
; INPUT:	EAX = pointer to new entry (RBNODE with filled WORD user data)
;		EDX = pointer to root (RBROOT)
; OUTPUT:	CY = entry already exists (EBX = pointer to existing node)
;		EBX = pointer to existing entry (if CY) or new entry (=EAX)
; -----------------------------------------------------------------------------

RBTreeInsertW:	push	esi			; push ESI
		mov	esi,RBTreeInsertW4	; ESI <- callback function
		call	RBTreeInsert		; insert new entry
		pop	esi			; pop ESI
		ret

; ------------- Callback compare function for WORD data unsigned

RBTreeInsertW4:	push	eax			; push EAX
		mov	ax,[eax+RB_DataW]	; AX <- user data
		cmp	ax,[ebx+RB_DataW]	; test data
		pop	eax			; pop EAX
		ret

Funkce RBTreeInsertW vloží do RB-stromu novou položku s vyplněnými uživatelskými daty v proměnné RB_DataW bez znaménka, strom bude tříděn podle obsahu této položky. Takový strom je nutné prohledávat pomocí funkce RBTreeSrcW. Vstupními parametry funkce jsou v registru EAX ukazatel na novou položku stromu (s vyplněnými daty v RB_DataW) a v registru EDX ukazatel na kořen stromu.

Je-li položka úspěšně vložena, je navrácen vynulovaný příznak CF a v registru EBX je navrácen ukazatel na novou položku. Jeho obsah tedy odpovídá obsahu registru EAX. Pokud již existuje položka se stejnými daty (ve stromu se nesmí vyskytovat dvě stejné položky), je navrácen příznak chyby CY (nastavený příznak CF) a registr EBX ukazuje na nalezenou položku se stejnými daty.

Funkce volá obsluhu funkce RBTreeInsert a předává jí ukazatel na vlastní porovnávací funkci RBTreeInsertW4, která porovnává obsahy položky RB_DataW bez znaménka.


; -----------------------------------------------------------------------------
;      Insert new entry into red-black balanced tree with WORD data signed
; -----------------------------------------------------------------------------
; INPUT:	EAX = pointer to new entry (RBNODE with filled WORD user data)
;		EDX = pointer to root (RBROOT)
; OUTPUT:	CY = entry already exists (EBX = pointer to existing node)
;		EBX = pointer to existing entry (if CY) or new entry (=EAX)
; -----------------------------------------------------------------------------

RBTreeInsertWS:	push	esi			; push ESI
		mov	esi,RBTreeInsertWS4	; ESI <- callback function
		call	RBTreeInsert		; insert new entry
		pop	esi			; pop ESI
		ret

; ------------- Callback compare function for WORD data signed

RBTreeInsertWS4:push	eax			; push EAX
		push	edx			; push EDX
		mov	ax,[eax+RB_DataW]	; AX <- user data
		add	ax,8000h		; AX <- convert to unsigned
		mov	dx,[ebx+RB_DataW]	; DX <- tested data
		add	dx,8000h		; DX <- convert to unsigned
		cmp	ax,dx			; compare data
		pop	edx			; pop EDX
		pop	eax			; pop EAX
		ret

Funkce RBTreeInsertWS je obměnou funkce RBTreeInsertW. Vloží do RB-stromu novou položku s vyplněnými uživatelskými daty v proměnné RB_DataW se znaménkem, strom bude tříděn podle obsahu této položky. Takový strom je nutné prohledávat pomocí funkce RBTreeSrcWS. Vstupními parametry funkce jsou v registru EAX ukazatel na novou položku stromu (s vyplněnými daty v RB_DataW) a v registru EDX ukazatel na kořen stromu.

Je-li položka úspěšně vložena, je navrácen vynulovaný příznak CF a v registru EBX je navrácen ukazatel na novou položku. Jeho obsah tedy odpovídá obsahu registru EAX. Pokud již existuje položka se stejnými daty (ve stromu se nesmí vyskytovat dvě stejné položky), je navrácen příznak chyby CY (nastavený příznak CF) a registr EBX ukazuje na nalezenou položku se stejnými daty.

Funkce volá obsluhu funkce RBTreeInsert a předává jí ukazatel na vlastní porovnávací funkci RBTreeInsertWS4, která porovnává obsahy položky RB_DataW se znaménkem.


; -----------------------------------------------------------------------------
;   Insert new entry into red-black balanced tree with DWORD data unsigned
; -----------------------------------------------------------------------------
; INPUT:	EAX = pointer to new entry (RBNODE with filled DWORD user data)
;		EDX = pointer to root (RBROOT)
; OUTPUT:	CY = entry already exists (EBX = pointer to existing node)
;		EBX = pointer to existing entry (if CY) or new entry (=EAX)
; -----------------------------------------------------------------------------

RBTreeInsertDW:	push	esi			; push ESI
		mov	esi,RBTreeInsertDW4	; ESI <- callback function
		call	RBTreeInsert		; insert new entry
		pop	esi			; pop ESI
		ret

; ------------- Callback compare function for WORD data unsigned

RBTreeInsertDW4:push	eax			; push EAX
		mov	eax,[eax+RBN_Data]	; EAX <- user data
		cmp	eax,[ebx+RBN_Data]	; test data
		pop	eax			; pop EAX
		ret

Funkce RBTreeInsertDW vloží do RB-stromu novou položku s vyplněnými uživatelskými daty (dvojslovo bez znaménka) na offsetu RBN_Data, strom bude tříděn podle obsahu těchto dat. Takový strom je nutné prohledávat pomocí funkce RBTreeSrcDW. Vstupními parametry funkce jsou v registru EAX ukazatel na novou položku stromu (s vyplněnými daty v RBN_Data) a v registru EDX ukazatel na kořen stromu.

Je-li položka úspěšně vložena, je navrácen vynulovaný příznak CF a v registru EBX je navrácen ukazatel na novou položku. Jeho obsah tedy odpovídá obsahu registru EAX. Pokud již existuje položka se stejnými daty (ve stromu se nesmí vyskytovat dvě stejné položky), je navrácen příznak chyby CY (nastavený příznak CF) a registr EBX ukazuje na nalezenou položku se stejnými daty.

Funkce volá obsluhu funkce RBTreeInsert a předává jí ukazatel na vlastní porovnávací funkci RBTreeInsertDW4, která porovnává obsahy položky RBN_Data bez znaménka.


; -----------------------------------------------------------------------------
;    Insert new entry into red-black balanced tree with DWORD data signed
; -----------------------------------------------------------------------------
; INPUT:	EAX = pointer to new entry (RBNODE with filled DWORD user data)
;		EDX = pointer to root (RBROOT)
; OUTPUT:	CY = entry already exists (EBX = pointer to existing node)
;		EBX = pointer to existing entry (if CY) or new entry (=EAX)
; -----------------------------------------------------------------------------

RBTreeInsertDWS:push	esi			; push ESI
		mov	esi,RBTreeInsertDS4	; ESI <- callback function
		call	RBTreeInsert		; insert new entry
		pop	esi			; pop ESI
		ret

; ------------- Callback compare function for DWORD data signed

RBTreeInsertDS4:push	eax			; push EAX
		push	edx			; push EDX
		mov	eax,[eax+RBN_Data]	; EAX <- user data
		add	eax,80000000h		; EAX <- convert to unsigned
		mov	edx,[ebx+RBN_Data]	; EDX <- tested data
		add	edx,80000000h		; EDX <- convert to unsigned
		cmp	eax,edx			; compare data
		pop	edx			; pop EDX
		pop	eax			; pop EAX
		ret

Funkce RBTreeInsertDWS je obměnou funkce RBTreeInsertDW. Vloží do RB-stromu novou položku s vyplněnými uživatelskými daty (dvojslovo se znaménkem) na offsetu RBN_Data, strom bude tříděn podle obsahu této položky. Takový strom je nutné prohledávat pomocí funkce RBTreeSrcDWS. Vstupními parametry funkce jsou v registru EAX ukazatel na novou položku stromu (s vyplněnými daty v RBN_Data) a v registru EDX ukazatel na kořen stromu.

Je-li položka úspěšně vložena, je navrácen vynulovaný příznak CF a v registru EBX je navrácen ukazatel na novou položku. Jeho obsah tedy odpovídá obsahu registru EAX. Pokud již existuje položka se stejnými daty (ve stromu se nesmí vyskytovat dvě stejné položky), je navrácen příznak chyby CY (nastavený příznak CF) a registr EBX ukazuje na nalezenou položku se stejnými daty.

Funkce volá obsluhu funkce RBTreeInsert a předává jí ukazatel na vlastní porovnávací funkci RBTreeInsertDS4, která porovnává obsahy položky RBN_Data se znaménkem.