; =============================================================================
;
; Litos - Red-black balanced tree
;
; =============================================================================
; A red-black tree is a type of self-balancing binary search tree. Each node
; has a color attribute, the value of which is either red or black.
;
; Requirements:
; 1. Every node is either red or black
; 2. The root is alwys black
; 3. All leaves (dummy empty nodes NULL) are black
; 4. Both children of every red node are black
; 5. All paths from any given node to its leaf nodes contain the same
; number of black nodes
; =============================================================================
CODE_SECTION 32
; ------------- Macro - initialized red-black tree root
%macro RBTREE 0
LISTHEAD ; list of entries
db RB_BLACK ; color of node
db RB_ROOT ; flags
dw 0 ; data WORD
dd 0 ; pointer to first node (0=none)
dd 0 ; number of nodes
%endmacro
; ------------- Macro - initialized red-black tree node
%macro RBTREENODE 0
LISTHEAD ; list of entries
db RB_BLACK ; color of node
db 0 ; flags
dw 0 ; data WORD
dd 0 ; parent node (NULL=root)
dd 0 ; left node (NULL=none)
dd 0 ; right node (NULL=none)
%endmacro
; ------------- Macro - set color of node to red (%1 = pointer to node)
%macro SETRED 1
mov byte [%1+RB_Color],RB_RED
%endmacro
; ------------- Macro - set color of node to black (%1 = pointer to node)
%macro SETBLK 1
mov byte [%1+RB_Color],RB_BLACK
%endmacro
; ------------- Macro - test color for red, ZY=is red (%1 = pointer to node)
%macro CMPRED 1
cmp byte [%1+RB_Color],RB_RED
%endmacro
; ------------- Macro - test color for black, ZY=is black (%1=pointer to node)
%macro CMPBLK 1
cmp byte [%1+RB_Color],RB_BLACK
%endmacro
; -----------------------------------------------------------------------------
; Initialize red-black balanced tree root
; -----------------------------------------------------------------------------
; INPUT: EDX = pointer to root (RBROOT)
; -----------------------------------------------------------------------------
RBTreeInit: LISTINIT edx ; initialize list of entries
mov dword [edx+RB_ColorFlags],RB_BLACK+(RB_ROOT<<8)
and dword [edx+RBR_Node],byte 0 ; no first node
and dword [edx+RBR_Count],byte 0 ; no entry
ret
; -----------------------------------------------------------------------------
; 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
; ------------- Get first node
;RBTreeFirst: mov ebx,[edx+RBR_Node] ; EBX <- first node
; or ebx,ebx ; any node?
; stc ; set error flag
; jz RBTreeFirst8 ; no node found
; ------------- Push registers
; push eax ; push EAX
; ------------- Find leftmost node
; xchg eax,ebx ; EAX <- first node
;RBTreeFirst4: xchg eax,ebx ; EBX <- next node
; mov eax,[ebx+RBN_Left] ; EAX <- next left node
; or eax,eax ; valid left node?
; jnz RBTreeFirst4 ; get next node
; ------------- Pop registers
; pop eax ; pop EAX
;RBTreeFirst8: ret
; -----------------------------------------------------------------------------
; 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
; ------------- Get first node
;RBTreeLast: mov ebx,[edx+RBR_Node] ; EBX <- first node
; or ebx,ebx ; any node?
; stc ; set error flag
; jz RBTreeLast8 ; no node found
; ------------- Push registers
; push eax ; push EAX
; ------------- Find rightmost node
; xchg eax,ebx ; EAX <- first node
;RBTreeLast4: xchg eax,ebx ; EBX <- next node
; mov eax,[ebx+RBN_Right] ; EAX <- next right node
; or eax,eax ; valid right node?
; jnz RBTreeLast4 ; get next node
; ------------- Pop registers
; pop eax ; pop EAX
;RBTreeLast8: ret
; -----------------------------------------------------------------------------
; 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
; ------------- Push registers
;RBTreeNext: push eax ; push EAX
; ------------- Get right node
; mov eax,[ebx+RBN_Right] ; EAX <- right node
; or eax,eax ; is right node valid?
; jz RBTreeNext4 ; right node is not valid
; ------------- Find leftmost node of right branch
;RBTreeNext2: xchg eax,ebx ; EBX <- node is valid
; mov eax,[ebx+RBN_Left] ; EAX <- next left node
; or eax,eax ; is next left node valid?
; jnz RBTreeNext2 ; get next left node
; jmp short RBTreeNext8 ; end of chain
; ------------- Get next parent
;RBTreeNext4: mov eax,[ebx+RBN_Parent] ; EAX <- parent
; or eax,eax ; is parent valid?
; xchg eax,ebx ; EAX <- node, EBX <- parent
; stc ; set error flag
; jz RBTreeNext8 ; no other parent
; ------------- Check if this parent is on the right from current node
; cmp eax,[ebx+RBN_Left] ; is it left node?
; jne RBTreeNext4 ; no, it is right node
; ------------- Pop registers
;RBTreeNext8: pop eax ; pop EAX
; ret
; -----------------------------------------------------------------------------
; 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
; ------------- Push registers
;RBTreePrev: push eax ; push EAX
; ------------- Get left node
; mov eax,[ebx+RBN_Left] ; EAX <- left node
; or eax,eax ; is left node valid?
; jz RBTreePrev4 ; left node is not valid
; ------------- Find rightmost node of left branch
;RBTreePrev2: xchg eax,ebx ; EBX <- node is valid
; mov eax,[ebx+RBN_Right] ; EAX <- next right node
; or eax,eax ; is next right node valid?
; jnz RBTreePrev2 ; get next right node
; jmp short RBTreePrev8 ; end of chain
; ------------- Get next parent
;RBTreePrev4: mov eax,[ebx+RBN_Parent] ; EAX <- next parent
; or eax,eax ; is parent valid?
; xchg eax,ebx ; EAX <- node, EBX <- parent
; stc ; set error flag
; jz RBTreePrev8 ; no other parent
; ------------- Check if this parent is on the left from current node
; cmp eax,[ebx+RBN_Right] ; is it right node?
; jne RBTreePrev4 ; no, it is left node
; ------------- Pop registers
;RBTreePrev8: pop eax ; pop EAX
; ret
; -----------------------------------------------------------------------------
; 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
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
call RBTreeFirst ; get first node
jecxz RBTreeIndex8 ; first node required
RBTreeIndex2: call RBTreeNext ; get next node
loop RBTreeIndex2 ; next node
jmp short RBTreeIndex8
; ------------- 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
call RBTreeLast ; get last node
jecxz RBTreeIndex8 ; last node required
RBTreeIndex6: call RBTreePrev ; get previous node
loop RBTreeIndex6 ; previous node
; ------------- Pop registers
RBTreeIndex8: pop ecx ; pop ECX
ret
; -----------------------------------------------------------------------------
; 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
; -----------------------------------------------------------------------------
; Find index of the node of 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 as verification that tree contains the node.
; -----------------------------------------------------------------------------
; ------------- Push registers
RBTreeFindInx: push ebx ; push EBX
push ecx ; push ECX
mov ecx,ebx ; ECX <- node to find
; ------------- Get last node
mov eax,[edx+RBR_Count] ; EAX <- number of nodes
dec eax ; EAX <- index of last node
call RBTreeLast ; get last node
jc RBTreeFindInx9 ; no last node
; ------------- Search node
RBTreeFindInx2: cmp ecx,ebx ; is it searched node?
je RBTreeFindInx9 ; node found
dec eax ; decrease node index
call RBTreePrev ; get previous node
jnc RBTreeFindInx2 ; node found OK
; ------------- Pop registers
RBTreeFindInx9: pop ecx ; pop ECX
pop ebx ; pop EBX
ret
; -----------------------------------------------------------------------------
; Search node in red-black balanced tree with address
; -----------------------------------------------------------------------------
; INPUT: EAX = address of node to find
; EDX = pointer to root (RBROOT)
; OUTPUT: CY = node not found
; -----------------------------------------------------------------------------
; ------------- Push registers
RBTreeSrcAddr: push ebx ; push EBX
push ecx ; push ECX
; ------------- Get first node
mov ecx,[edx+RBR_Node] ; get first node
jecxz RBTreeSrcAddr6 ; there is no node in tree
; ------------- Next node is valid
RBTreeSrcAddr2: mov ebx,ecx ; node is valid
; ------------- Compare data
xor ecx,ecx ; ECX <- 0
cmp eax,ebx ; test address
je RBTreeSrcAddr8 ; node found OK
; ------------- Get next node
seta cl ; CL <- 1 (right), 0 (left)
mov ecx,[ebx+RBN_Left+ecx*(RBN_Right-RBN_Left)] ; next node
or ecx,ecx ; is next node valid?
jnz RBTreeSrcAddr2 ; next node is valid
; ------------- Error, node not found
RBTreeSrcAddr6: stc ; flag - node not found
; ------------- Pop registers
RBTreeSrcAddr8: pop ecx ; pop ECX
pop ebx ; pop EBX
ret
; -----------------------------------------------------------------------------
; Search node in red-black balanced tree with WORD data
; -----------------------------------------------------------------------------
; INPUT: AX = data to find
; EDX = pointer to root (RBROOT)
; OUTPUT: CY = node not found (EBX = NULL)
; EBX = pointer to found node (NULL = node not found)
; -----------------------------------------------------------------------------
; ------------- Push registers
RBTreeSrcW: push ecx ; push ECX
; ------------- Get first node
mov ecx,[edx+RBR_Node] ; get first node
jecxz RBTreeSrcW6 ; there is no node in tree
; ------------- Next node is valid
RBTreeSrcW2: mov ebx,ecx ; node is valid
; ------------- Compare data
xor ecx,ecx ; ECX <- 0
cmp ax,[ebx+RB_DataW] ; test data
je RBTreeSrcW8 ; node found OK
; ------------- Get next node
seta cl ; CL <- 1 (right), 0 (left)
mov ecx,[ebx+RBN_Left+ecx*(RBN_Right-RBN_Left)] ; next node
or ecx,ecx ; is next node valid?
jnz RBTreeSrcW2 ; next node is valid
; ------------- Error, node not found
RBTreeSrcW6: xor ebx,ebx ; EBX <- 0, node not found
stc ; flag - node not found
; ------------- Pop registers
RBTreeSrcW8: pop ecx ; pop ECX
ret
; -----------------------------------------------------------------------------
; Search node in red-black balanced tree with DWORD data
; -----------------------------------------------------------------------------
; INPUT: EAX = data to find
; EDX = pointer to root (RBROOT)
; OUTPUT: CY = node not found (EBX = NULL)
; EBX = pointer to found node (NULL = node not found)
; -----------------------------------------------------------------------------
; ------------- Push registers
RBTreeSrcDW: push ecx ; push ECX
; ------------- Get first node
mov ecx,[edx+RBR_Node] ; get first node
jecxz RBTreeSrcDW6 ; there is no node in the tree
; ------------- Next node is valid
RBTreeSrcDW2: mov ebx,ecx ; EBX <- node is valid
; ------------- Compare data
xor ecx,ecx ; ECX <- 0
cmp eax,[ebx+RBN_Data] ; test data
je RBTreeSrcDW8 ; node find OK
; ------------- Get next node
seta cl ; CL <- 1 (right), 0 (left)
mov ecx,[ebx+RBN_Left+ecx*(RBN_Right-RBN_Left)] ; next node
or ecx,ecx ; is next node valid?
jnz RBTreeSrcDW2 ; next node is valid
; ------------- Error, node not found
RBTreeSrcDW6: xor ebx,ebx ; EBX <- 0, node not found
stc ; flag - node not found
; ------------- Pop registers
RBTreeSrcDW8: pop ecx ; pop ECX
ret
; -----------------------------------------------------------------------------
; Search node in red-black balanced tree with callback compare function
; -----------------------------------------------------------------------------
; INPUT: EAX = user data to find (or node with data)
; EDX = pointer to root (RBROOT)
; ESI = callback compare function
; INPUT: EAX = user data to find (or node with data)
; EBX = node to test
; OUTPUT: ZY = equal, CY = EAX.Data < EBX.Data
; (as CMP EAX.Data,EBX.Data)
; OUTPUT: CY = node not found (EBX = NULL)
; EBX = pointer to found node (NULL = node not found)
; -----------------------------------------------------------------------------
; ------------- Push registers
RBTreeSrcFnc: push ecx ; push ECX
; ------------- Get first node
mov ecx,[edx+RBR_Node] ; get first node
jecxz RBTreeSrcFnc6 ; there is no node in the tree
; ------------- Next node is valid
RBTreeSrcFnc2: mov ebx,ecx ; EBX <- node is valid
; ------------- Compare data
xor ecx,ecx ; ECX <- 0
call esi ; test data
je RBTreeSrcFnc8 ; node find OK
; ------------- Get next node
seta cl ; CL <- 1 (right), 0 (left)
mov ecx,[ebx+RBN_Left+ecx*(RBN_Right-RBN_Left)] ; next node
or ecx,ecx ; is next node valid?
jnz RBTreeSrcFnc2 ; next node is valid
; ------------- Error, node not found
RBTreeSrcFnc6: xor ebx,ebx ; EBX <- 0, node not found
stc ; flag - node not found
; ------------- Pop registers
RBTreeSrcFnc8: pop ecx ; pop ECX
ret
; -----------------------------------------------------------------------------
; Search nearest higher node in red-black tree with callback compare function
; -----------------------------------------------------------------------------
; INPUT: EAX = user data to find (or node with data)
; EDX = pointer to root (RBROOT)
; ESI = callback compare function
; INPUT: EAX = user data to find (or node with data)
; EBX = node to test
; OUTPUT: ZY = equal, CY = EAX.Data < EBX.Data
; (as CMP EAX.Data,EBX.Data)
; OUTPUT: CY = node not found (EBX = NULL)
; EBX = pointer to found nearest higher or equal node (NULL=none)
; -----------------------------------------------------------------------------
; ------------- Push registers
RBTreeSrcHigh: push ecx ; push ECX
push edi ; push EDI
; ------------- Get first node
xor edi,edi ; EDI <- 0, no nearest node
mov ecx,[edx+RBR_Node] ; get first node
jecxz RBTreeSrcHigh6 ; there is no node in the tree
; ------------- Next node is valid
RBTreeSrcHigh2: mov ebx,ecx ; EBX <- node is valid
; ------------- Compare data
xor ecx,ecx ; ECX <- 0
call esi ; test data
je RBTreeSrcHigh8 ; node find OK
ja RBTreeSrcHigh4 ; data is above node
mov edi,ebx ; EDI <- save higher node
; ------------- Get next node
RBTreeSrcHigh4: seta cl ; CL <- 1 (right), 0 (left)
mov ecx,[ebx+RBN_Left+ecx*(RBN_Right-RBN_Left)] ; next node
or ecx,ecx ; is next node valid?
jnz RBTreeSrcHigh2 ; next node is valid
; ------------- Equal node not found
RBTreeSrcHigh6: mov ebx,edi ; EBX <- nearest node
cmp ebx,byte 1 ; set error flag CY if NULL
; ------------- Pop registers
RBTreeSrcHigh8: pop edi ; pop EDI
pop ecx ; pop ECX
ret
; -----------------------------------------------------------------------------
; Search nearest lower node in red-black tree with callback compare function
; -----------------------------------------------------------------------------
; INPUT: EAX = user data to find (or node with data)
; EDX = pointer to root (RBROOT)
; ESI = callback compare function
; INPUT: EAX = user data to find (or node with data)
; EBX = node to test
; OUTPUT: ZY = equal, CY = EAX.Data < EBX.Data
; (as CMP EAX.Data,EBX.Data)
; OUTPUT: CY = node not found (EBX = NULL)
; EBX = pointer to found nearest lower or equal node (NULL=none)
; -----------------------------------------------------------------------------
; ------------- Push registers
RBTreeSrcLow: push ecx ; push ECX
push edi ; push EDI
; ------------- Get first node
xor edi,edi ; EDI <- 0, no nearest node
mov ecx,[edx+RBR_Node] ; get first node
jecxz RBTreeSrcLow6 ; there is no node in the tree
; ------------- Next node is valid
RBTreeSrcLow2: mov ebx,ecx ; EBX <- node is valid
; ------------- Compare data
xor ecx,ecx ; ECX <- 0
call esi ; test data
je RBTreeSrcLow8 ; node find OK
jb RBTreeSrcLow4 ; data is below node
mov edi,ebx ; EDI <- save lower node
; ------------- Get next node
RBTreeSrcLow4: seta cl ; CL <- 1 (right), 0 (left)
mov ecx,[ebx+RBN_Left+ecx*(RBN_Right-RBN_Left)] ; next node
or ecx,ecx ; is next node valid?
jnz RBTreeSrcLow2 ; next node is valid
; ------------- Equal node not found
RBTreeSrcLow6: mov ebx,edi ; EBX <- nearest node
cmp ebx,byte 1 ; set error flag CY if NULL
; ------------- Pop registers
RBTreeSrcLow8: pop edi ; pop EDI
pop ecx ; pop ECX
ret
; -----------------------------------------------------------------------------
; 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
%undef RBRi ; right node
%undef RBNo ; current node
%undef RBRL ; right-left node (hardcoded)
%undef RBRLL ; right-left node LOW (temp.)
%undef RBRo ; root
%undef RBPa ; parent
; -----------------------------------------------------------------------------
; 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
%undef RBLe ; right node
%undef RBNo ; current node
%undef RBLR ; right-left node (hardcoded)
%undef RBLRL ; right-left node LOW (temp.)
%undef RBRo ; root
%undef RBPa ; parent
; -----------------------------------------------------------------------------
; Replace node of red-black balanced tree
; -----------------------------------------------------------------------------
; INPUT: EAX = pointer to new node (RBN)
; EBX = pointer to old node (RBN)
; EDX = pointer to root (RBR)
; -----------------------------------------------------------------------------
; Local variables:
%define RBNew EAX ; new node
%define RBOld EBX ; old node
%define RBTm ECX ; temporary (hardcoded)
%define RBTmL CL ; temporary LOW
%define RBRo EDX ; root
; ------------- Push registers
RBTreeReplace: push RBTm ; push RBTm
; ------------- Relink entries in the list
mov RBTm,[RBOld+LIST_Prev] ; RBTm <- previous entry
call ListDelEBX ; delete entry from the list
push ebx ; push EBX
mov ebx,RBTm ; EBX <- previous entry
call ListAfter ; link entry after previous one
pop ebx ; pop EBX
; ------------- Copy color
mov RBTmL,[RBOld+RB_Color] ; get color from old node
mov [RBNew+RB_Color],RBTmL ; set color to new node
; ------------- Check if parent is ROOT
mov RBTm,[RBOld+RBN_Parent] ; get parent of old node
jecxz RBTreeReplace3 ; parent is root
; ------------- Link to parent
cmp RBOld,[RBTm+RBN_Left] ; is it left node?
jne RBTreeReplace2 ; it is not left node
mov [RBTm+RBN_Left],RBNew ; link as left node
jmp short RBTreeReplace4
RBTreeReplace2: mov [RBTm+RBN_Right],RBNew ; link as right node
jmp short RBTreeReplace4
; ------------- Link to parent in root
RBTreeReplace3: mov [RBRo+RBR_Node],RBNew ; link from root
RBTreeReplace4: mov [RBNew+RBN_Parent],RBTm ; link to parent from new node
; ------------- Link to left child
mov RBTm,[RBOld+RBN_Left] ; get left child
jecxz RBTreeReplace6 ; left child is not valid
mov [RBTm+RBN_Parent],RBNew ; link from left child
RBTreeReplace6: mov [RBNew+RBN_Left],RBTm ; link to left child
; ------------- Link to right child
mov RBTm,[RBOld+RBN_Right] ; get right child
jecxz RBTreeReplace8 ; right child is not valid
mov [RBTm+RBN_Parent],RBNew ; link from right child
RBTreeReplace8: mov [RBNew+RBN_Right],RBTm ; link to right child
; ------------- Pop registers
pop RBTm ; pop RBTm
ret
%undef RBNew ; new node
%undef RBOld ; old node
%undef RBTm ; temporary (hardcoded)
%undef RBTmL ; temporary LOW
%undef RBRo ; root
; -----------------------------------------------------------------------------
; Insert red color into red-black balanced tree
; -----------------------------------------------------------------------------
; INPUT: EBX = pointer to current node (RBNODE)
; EDX = pointer to root (RBROOT)
; NOTES: Entry point is RBTreeInsCol.
; -----------------------------------------------------------------------------
; Local variables:
%define RBGr EAX ; grand parent
%define RBNo EBX ; current node
%define RBUn ECX ; uncle
%define RBRo EDX ; root
%define RBPa ESI ; parent
; ============= 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
; ============= 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 near RBTreeInsCol8 ; no other parent
; ------------- Check if parent is red
CMPRED RBPa ; parent is red?
jne near 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
RBTreeInsCol3: jmp short RBTreeInsCol2 ; next node
; ------------- Parent is right of grand parent
RBTreeInsCol4: RBTreeInsC Right, Left ; insert color for right
jmp short RBTreeInsCol3 ; 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
%undef RBGr ; grand parent
%undef RBNo ; current node
%undef RBUn ; uncle
%undef RBRo ; root
%undef RBPa ; parent
; -----------------------------------------------------------------------------
; 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
or ecx,ecx ; is any node in the tree?
jnz RBTreeInsert2 ; tree is not empty
; ------------- Store node into root
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
; ------------- Next node is valid
RBTreeInsert2: mov ebx,ecx ; EBX <- node is valid
; ------------- Compare data
call esi ; test data
jb RBTreeInsert3 ; 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 RBTreeInsert4
; ------------- Lower data, use left branch
RBTreeInsert3: 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
RBTreeInsert4: 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
; -----------------------------------------------------------------------------
; 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)
; NOTES: Entry point is RBTreeInsertW.
; -----------------------------------------------------------------------------
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
; -----------------------------------------------------------------------------
; Insert new entry into red-black balanced tree with WORD data
; -----------------------------------------------------------------------------
; 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)
; NOTES: Entry point is RBTreeInsertW.
; -----------------------------------------------------------------------------
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
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
; -----------------------------------------------------------------------------
; Insert new entry into red-black balanced tree with DWORD data
; -----------------------------------------------------------------------------
; 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)
; NOTES: Entry point is RBTreeInsertDW.
; -----------------------------------------------------------------------------
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 DWORD data
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
; -----------------------------------------------------------------------------
; Delete color of node from red-black balanced tree
; -----------------------------------------------------------------------------
; INPUT: EAX = pointer to parent of node (RBNODE, NULL=root)
; EBX = pointer to deleted node (RBNODE, node must be unlinked)
; EDX = pointer to root (RBROOT)
; NOTES: Entry point is RBTreeDelCol.
; -----------------------------------------------------------------------------
; Local variables:
%define RBPa EAX ; parent
%define RBNo EBX ; deleted node
%define RBNe ECX ; nephew (hardcoded)
%define RBNeL CL ; nephew LOW (temporary reg.)
%define RBRo EDX ; root
%define RBBr ESI ; brother
; ============= Macros
; ------------- Macro - check if left (right) nephew is black
; Parameters: %1 = Left (Right), %2 = jump label if nephew is not black
%macro TESTNE 2
mov RBNe,[RBBr+RBN_%1] ; get nephew
jecxz %%black ; nephew is not valid
CMPBLK RBNe ; is nephew black?
jne %2 ; nephew is not black
%%black:
%endmacro
; ------------- Macro - delete color in one direction
; Parameters (direction word): %1 = Left (Right), %2 = Right (Left)
%macro RBTreeDelC 2
; ------------- Get brother node from right (left) and check if it is red
; Node is black or invalid and therefore its brother is always valid
mov RBBr,[RBPa+RBN_%2] ; get brother node
CMPRED RBBr ; is brother node red?
jne short %%L2 ; brother node is not red
; ------------- Set brother node black, set parent red a rotate it left (right)
SETBLK RBBr ; set brother node black
SETRED RBPa ; set parent node red
push RBNo ; push RBNo
mov RBNo,RBPa ; parent node will be used
call RBTree%1 ; rotate parent left (right)
pop RBNo ; pop RBNo
mov RBBr,[RBPa+RBN_%2] ; get new brother node
; ------------- Check if left (right) nephew is black
%%L2: TESTNE %1, %%L4 ; check left (right) nephew
; ------------- Check if right (left) nephew is black
TESTNE %2, %%L4 ; check right (left) nephew
; ------------- Set brother to red
SETRED RBBr ; set brother to red
mov RBNo,RBPa ; node <- parent
mov RBPa,[RBNo+RBN_Parent] ; get new parent
jmp RBTreeDelCol2 ; next node
; ------------- Check if right (left) nephew is black
%%L4: TESTNE %2, %%L6 ; check right (left) nephew
; ------------- Set left (right) nephew to black
mov RBNe,[RBBr+RBN_%1] ; get left (right) nephew
jecxz %%L5 ; nephew is not valid
SETBLK RBNe ; set nephew black
; ------------- Set brother red and rotate it right (left)
%%L5: SETRED RBBr ; set brother red
push RBNo ; push RBNo
mov RBNo,RBBr ; node <- brother
call RBTree%2 ; rotate brother right (left)
pop RBNo ; pop RBNo
mov RBBr,[RBPa+RBN_%2] ; get new brother node
; ------------- Copy parent's color to brother
%%L6: mov RBNeL,[RBPa+RB_Color] ; get parent's color
mov [RBBr+RB_Color],RBNeL ; set brother's color
SETBLK RBPa ; set parent black
; ------------- Set right (left) nephew to black
mov RBNe,[RBBr+RBN_%2] ; get right (left) nephew
jecxz %%L8 ; nephew is not valid
SETBLK RBNe ; set nephew black
; ------------- Rotate parent left (right)
%%L8: mov RBNo,RBPa ; parent will be used
call RBTree%1 ; rotate parent left (right)
mov RBNo,[RBRo+RBR_Node] ; get root node
%endmacro
; ============= RBTreeDelCol function
; ------------- Push registers
RBTreeDelCol: push RBPa ; push RBPa
push RBNo ; push RBNo
push RBNe ; push RBNe
push RBBr ; push RBBr
; ------------- Node must be black or invalid
RBTreeDelCol2: or RBNo,RBNo ; is node valid?
jz short RBTreeDelCol3 ; node is not valid
CMPBLK RBNo ; is node black?
jne near RBTreeDelCol4 ; node is not black
; ------------- Node must not be a root node
RBTreeDelCol3: cmp RBNo,[RBRo+RBR_Node] ; is it root node?
je near RBTreeDelCol4 ; it is root node
; ------------- Check if current node is left node of parent
cmp RBNo,[RBPa+RBN_Left] ; is current node left node?
jne near RBTreeDelCol5 ; it is not left node
; ------------- Node is left node
RBTreeDelC Left, Right ; delete color for left
RBTreeDelCol4: jmp RBTreeDelCol6 ; quit
; ------------- Node is right node
RBTreeDelCol5: RBTreeDelC Right, Left ; delete color for right
; ------------- Set node to black
RBTreeDelCol6: or RBNo,RBNo ; is node valid?
jz short RBTreeDelCol8 ; node is invalid
SETBLK RBNo ; set node to black
; ------------- Pop registers
RBTreeDelCol8: pop RBBr ; pop RBBr
pop RBNe ; pop RBNe
pop RBNo ; pop RBNo
pop RBPa ; pop RBPa
ret
%undef RBPa ; parent
%undef RBNo ; deleted node
%undef RBNe ; nephew
%undef RBNeL ; nephew LOW (temporary reg.)
%undef RBRo ; root
%undef RBBr ; brother
; -----------------------------------------------------------------------------
; Delete node from red-black balanced tree
; -----------------------------------------------------------------------------
; INPUT: EBX = pointer to deleted node (RBNODE)
; EDX = pointer to root (RBROOT)
; NOTES: RBNODE memory block is not destroyed.
; -----------------------------------------------------------------------------
; Local variables:
%define RBPa EAX ; parent
%define RBPaL AL ; parent LOW
%define RBNo EBX ; current node
%define RBCo ECX ; color
%define RBCoL CL ; color LOW
%define RBRo EDX ; root
%define RBOl ESI ; old node
%define RBCh EDI ; child
; ------------- Push registers
RBTreeDelete: push RBPa ; push RBPa
push RBNo ; push RBNo
push RBCo ; push RBCo
push RBOl ; push RBOl
push RBCh ; push RBCh
; ------------- Decrease number of entries
dec dword [RBRo+RBR_Count] ; decrease number of entries
; ------------- Detach entry from the list
call ListDelEBX ; delete node
; ------------- Get child node from right node if left node is not valid
mov RBCh,[RBNo+RBN_Right] ; RBCh <- get right node
mov RBOl,[RBNo+RBN_Left] ; RBOl <- get left node
or RBOl,RBOl ; ir left node valid?
jz RBTreeDelete6 ; left node is not valid
; ------------- Get child node from left node if right node is not valid
xchg RBOl,RBCh ; child <- left, old <- right
or RBOl,RBOl ; is right node valid?
jz RBTreeDelete6 ; right node is not valid
; ------------- Find leftmost node of right node
mov RBCh,RBOl ; child <- save right node
mov RBOl,RBNo ; old <- save current node
RBTreeDelete1: mov RBNo,RBCh ; node <- right/left
mov RBCh,[RBNo+RBN_Left] ; child <- get left node
or RBCh,RBCh ; is left node valid?
jnz RBTreeDelete1 ; next left node
; ------------- Get right child, parent and color of the node
mov RBCh,[RBNo+RBN_Right] ; child <- get right node
mov RBPa,[RBNo+RBN_Parent] ; parent <- get parent
mov RBCoL,[RBNo+RB_Color] ; color <- get color
; ------------- Link parent to right child
or RBCh,RBCh ; is child valid?
jz RBTreeDelete2 ; child is not valid
mov [RBCh+RBN_Parent],RBPa ; child <- set new parent
; ------------- If parent is old (deleted) node link it as its right node
RBTreeDelete2: cmp RBOl,RBPa ; is parent equal to old node?
jne RBTreeDelete3 ; parent is not old node
mov [RBPa+RBN_Right],RBCh ; set child as right of parent
mov RBPa,RBNo ; parent <- node
jmp short RBTreeDelete4
RBTreeDelete3: mov [RBPa+RBN_Left],RBCh ; set child as left of parent
; ------------- Copy color, right and left node from old node to current one
RBTreeDelete4: push RBPa ; push RBPa (old parent)
mov RBPaL,[RBOl+RB_Color] ; color
mov [RBNo+RB_Color],RBPaL
mov RBPa,[RBOl+RBN_Left] ; left node
mov [RBNo+RBN_Left],RBPa
mov RBPa,[RBOl+RBN_Right] ; right node
mov [RBNo+RBN_Right],RBPa
mov RBPa,[RBOl+RBN_Parent] ; parent
mov [RBNo+RBN_Parent],RBPa
; ------------- Link current node to parent
or RBPa,RBPa ; is parent valid?
jz RBTreeDelete56 ; parent is not valid
cmp [RBPa+RBN_Left],RBOl ; old node=left node of parent?
jne RBTreeDelete52 ; no
mov [RBPa+RBN_Left],RBNo ; node -> left node of parent
jmp short RBTreeDelete58
RBTreeDelete52: mov [RBPa+RBN_Right],RBNo ; node -> right node of parent
jmp short RBTreeDelete58
RBTreeDelete56: mov [RBRo+RBR_Node],RBNo ; node -> root node
; ------------- Link current node as parent of old left node
RBTreeDelete58: mov RBPa,[RBOl+RBN_Left] ; RBPa <- get old left node
mov [RBPa+RBN_Parent],RBNo ; node -> parent of left node
; ------------- Link current node as parent of old right node
mov RBPa,[RBOl+RBN_Right] ; RBPa <- get old right node
or RBPa,RBPa ; is old right node valid?
jz RBTreeDelete59 ; old right node is not valid
mov [RBPa+RBN_Parent],RBNo ; node -> parent of right node
RBTreeDelete59: pop RBPa ; pop RBPa (old parent)
jmp short RBTreeDelete7 ; delete color
; ------------- Get parent and color of current node
RBTreeDelete6: mov RBPa,[RBNo+RBN_Parent] ; RBPa <- get current parent
mov RBCoL,[RBNo+RB_Color] ; RBCoL <- get current color
; ------------- Link parent as new parent of the child
or RBCh,RBCh ; is child valid?
jz RBTreeDelete62 ; child is not valid
mov [RBCh+RBN_Parent],RBPa ; parent -> parent of the child
; ------------- Link child to the parent
RBTreeDelete62: or RBPa,RBPa ; is parent valid?
jz RBTreeDelete66 ; parent is not valid
cmp RBNo,[RBPa+RBN_Left] ; is current node left child?
jne RBTreeDelete64 ; is it not left child
mov [RBPa+RBN_Left],RBCh ; link child as left child
jmp short RBTreeDelete7
RBTreeDelete64: mov [RBPa+RBN_Right],RBCh ; link child as right child
jmp short RBTreeDelete7
RBTreeDelete66: mov [RBRo+RBR_Node],RBCh ; child -> root node
; ------------- Delete color
RBTreeDelete7: cmp RBCoL,RB_BLACK ; is it black color?
jne RBTreeDelete8 ; it is not black color
mov ebx,RBCh ; EBX <- child node
call RBTreeDelCol ; delete color
; ------------- Pop registers
RBTreeDelete8: pop RBCh ; pop RBCh
pop RBOl ; pop RBOl
pop RBCo ; pop RBCo
pop RBNo ; pop RBNo
pop RBPa ; pop RBPa
ret
; -----------------------------------------------------------------------------
; Debug test red-black tree
; -----------------------------------------------------------------------------
%ifdef DEBUG_RBTREE
TestRBTree: call DebOutClear
mov esi,TestTreeText1
call DebOutText
; ------------- Create random nodes
mov ecx,1000
mov edx,TestTree
TestRBTree1: call RandByte
test al,7
jnz TestRBTree2
; ------------- Delete one random node
mov eax,[TestTree+RBR_Count]
dec eax
call RandMaxDWord
call RBTreeIndex
jc TestRBTree1
call RBTreeDelete
xchg eax,ebx
call SysMemFree
jmp short TestRBTree1
; ------------- Create one random node
TestRBTree2: mov eax,RBNODE_size+4
call SysMemAlloc
push eax
call RandDWord
xchg eax,esi
pop eax
mov [eax+RBN_Data],esi
call RBTreeInsertDW
loop TestRBTree1
; ------------- Limit number of nodes
TestRBTree3: mov eax,[TestTree+RBR_Count]
cmp eax,byte 100
jbe TestRBTree4
dec eax
call RandMaxDWord
call RBTreeIndex
call RBTreeDelete
xchg eax,ebx
call SysMemFree
jmp short TestRBTree3
; ------------- Display nodes
TestRBTree4: call RBTreeFirst
jc TestRBTree7
TestRBTree5: mov eax,[ebx+RBN_Data]
call DebOutNum
add byte [VideoPos],15
and byte [VideoPos],~0fh
cmp byte [VideoPos],70
jb TestRBTree6
call DebNewLine
TestRBTree6: call RBTreeNext
jnc TestRBTree5
TestRBTree7: jmp $
; -----------------------------------------------------------------------------
; Data
; -----------------------------------------------------------------------------
DATA_SECTION
TestTree: RBTREE ; test tree
TestTreeText1: db 'Test Red-Black Tree...',10,0
%endif ; DEBUG_RBTREE
|
