format PE64 GUI 4.0
entry Start
include 'win64axp.inc'
TT_MAX_ENTRIES fix 1024
IDI_MAIN = 17
ID_DLGMAIN = 37
ID_EXPRESSION = 39
ID_RESULT = 200
struct NODE ; 32 bytes in size
LEFT dq ? ; left child
RIGHT dq ? ; right child
UP dq ? ; parent
COL db ? ; 0 for black, 1 for red \
db ?,?,? ; unused
NUM dd ? ; number
ends
LG_NODE_SIZE fix 5 ; log2(sizeof.NODE)
section '.text' code readable executable
Start:
push rbp
invoke InitCommonControls
invoke GetModuleHandle,NULL
invoke DialogBoxParam,rax,ID_DLGMAIN,NULL,DlgProc,NULL
invoke ExitProcess,0
proc DlgProc,.hDlg,.uMsg,.wParam,.lParam
mov [.hDlg],rcx
mov [.uMsg],rdx
mov [.wParam],r8
mov [.lParam],r9
mov eax,dword[.uMsg]
cmp eax,WM_COMMAND
je .wmcommand
cmp eax,WM_CLOSE
je .wmclose
cmp eax,WM_INITDIALOG
je .wminitdialog
.default:
xor eax, eax
ret
.wmcommand:
movzx edx,word[.wParam+2]
movzx eax,word[.wParam]
cmp eax,ID_EXPRESSION
jne .default
cmp edx, EN_CHANGE
jne .default
.edit_changed:
invoke SendDlgItemMessage,[.hDlg],ID_EXPRESSION,WM_GETTEXT,1023,InputString
push rsi rdi
call TT_Clear
lea rsi,[InputString]
.read_next: call SkipSpaces
cmp byte[rsi],0
je .read_done
call ParseInteger
mov ecx,eax
call TT_FindNode
jmp .read_next
.read_done: lea rdi,[ResultString]
call TT_InOrderTraverse
xor eax,eax
stosb
pop rdi rsi
invoke SetDlgItemText,[.hDlg],ID_RESULT,ResultString
jmp .default
.wmclose:
invoke EndDialog,[.hDlg],0
jmp .default
.wminitdialog:
invoke SendDlgItemMessage,[.hDlg],ID_EXPRESSION,EM_LIMITTEXT,1022,0
.processed:
mov eax,1
.return:
ret
endp
; return in rax address of node that corresponds to number in ecx
; if ecx is not in table, then a new node is made
; if table is full, then TTNull is returned
; NOTE: insertion code is stolen from wikipedia
align 16
TT_FindNode:
mov edx,dword[TTEntries]
test edx,edx
jnz .OldTree
.NewTree: lea rax,[TT]
add edx,1
mov dword[TTEntries],edx
mov qword[rax+NODE.UP],TTHead
mov qword[rax+NODE.LEFT],TTNull
mov qword[rax+NODE.RIGHT],TTNull
mov dword[rax+NODE.COL],0
mov dword[rax+NODE.NUM],ecx
mov qword[TTHead+NODE.LEFT],rax
ret
align 16
.TreeFull: lea rax,[TTNull]
ret
; this can be called to skip the previous branch if it is known that the tree is not empty
align 16
.OldTree:
mov r10,qword[TTHead+NODE.LEFT]
mov edx,dword[TTEntries]
lea r11d,[rdx+1]
shl rdx,LG_NODE_SIZE
lea rdx,[rdx+TT]
.Compare:
mov r8,qword[r10+NODE.LEFT]
mov r9,qword[r10+NODE.RIGHT]
mov eax,dword[r10+NODE.NUM]
cmp eax,ecx
jg .GoLeft
jl .GoRight
.Found: mov rax,r10
ret
.GoLeft: cmp r8,TTNull
je .MakeNewLeft
mov r10,r8
jmp .Compare
.GoRight: cmp r9,TTNull
je .MakeNewRight
mov r10,r9
jmp .Compare
.MakeNewLeft: cmp r11d,TT_MAX_ENTRIES
ja .TreeFull
mov qword[r10+NODE.LEFT],rdx
jmp .FixTree
.MakeNewRight: cmp r11d,TT_MAX_ENTRIES
ja .TreeFull
mov qword[r10+NODE.RIGHT],rdx
.FixTree: mov dword[TTEntries],r11d
mov qword[rdx+NODE.UP],r10
mov qword[rdx+NODE.LEFT],TTNull
mov qword[rdx+NODE.RIGHT],TTNull
mov dword[rdx+NODE.COL],1 ; set color to red
mov dword[rdx+NODE.NUM],ecx
mov rax,rdx ; this is the node to return
.FixNode: ; node is in rdx
; Case 1: The current node N is at the root of the tree. In this case, it is repainted black to satisfy property 2 (the root is black). Since this adds one black node to every path at once, property 5 (all paths from any given node to its leaf nodes contain the same number of black nodes) is not violated.
.Case1: mov r8,qword[rdx+NODE.UP]
cmp r8,TTHead
jne .Case2
mov byte[rdx+NODE.COL],0 ; set as black
ret
; Case 2: The current node's parent P is black, so property 4 (both children of every red node are black) is not invalidated. In this case, the tree is still valid. Property 5 (all paths from any given node to its leaf nodes contain the same number of black nodes) is not threatened, because the current node N has two black leaf children, but because N is red, the paths through each of its children have the same number of black nodes as the path through the leaf it replaced, which was black, and so this property remains satisfied.
.Case2: cmp byte[r8+NODE.COL],0
jne .Case3
ret
; Case 3: If both the parent P and the uncle U are red, then both of them can be repainted black and the grandparent G becomes red (to maintain property 5 (all paths from any given node to its leaf nodes contain the same number of black nodes)). Now, the current red node N has a black parent. Since any path through the parent or uncle must pass through the grandparent, the number of black nodes on these paths has not changed. However, the grandparent G may now violate properties 2 (The root is black) or 4 (Both children of every red node are black) (property 4 possibly being violated since G may have a red parent). To fix this, the entire procedure is recursively performed on G from case 1
.Case3: mov r9,qword[r8+NODE.UP] ; r8 must have a parent
mov r10,qword[r9+NODE.LEFT]
mov r11,qword[r9+NODE.RIGHT]
cmp r8,r10
cmove r10,r11
cmp r10,TTNull
je .Case4
cmp byte[r10+NODE.COL],0
je .Case4
mov rdx,r9
mov byte[r8+NODE.COL],0
mov byte[r9+NODE.COL],1
mov byte[r10+NODE.COL],0
jmp .FixNode
; Case 4: The parent P is red but the uncle U is black; also, the current node N is the right child of P, and P in turn is the left child of its parent G. In this case, a left rotation on P that switches the roles of the current node N and
.Case4: mov r10,qword[r9+NODE.UP] ; r10 = great grandparent of rdx
.Case4A: cmp rdx,qword[r8+NODE.RIGHT]
jne .Case4B
cmp r8,qword[r9+NODE.LEFT]
jne .Case4B
mov r11,qword[rdx+NODE.LEFT]
mov qword[r9+NODE.LEFT],rdx
mov qword[rdx+NODE.LEFT],r8
mov qword[r8+NODE.RIGHT],r11
mov qword[r8+NODE.UP],rdx
mov qword[rdx+NODE.UP],r9
mov qword[r11+NODE.UP],r8
jmp .Case4Done
.Case4B: cmp rdx,qword[r8+NODE.LEFT]
jne .Case5
cmp r8,qword[r9+NODE.RIGHT]
jne .Case5
mov r11,qword[rdx+NODE.RIGHT]
mov qword[r9+NODE.RIGHT],rdx
mov qword[rdx+NODE.RIGHT],r8
mov qword[r8+NODE.LEFT],r11
mov qword[r8+NODE.UP],rdx
mov qword[rdx+NODE.UP],r9
mov qword[r11+NODE.UP],r8
.Case4Done: xchg rdx,r8
; Case 5: The parent P is red but the uncle U is black, the current node N is the left child of P, and P is the left child of its parent G. In this case, a right rotation on G is performed; the result is a tree where the former parent P is now the parent of both the current node N and the former grandparent G.
.Case5:
mov r11,qword[r10+NODE.RIGHT]
cmp r11,r9
cmove r11,r8
mov qword[r10+NODE.RIGHT],r11
mov r11,qword[r10+NODE.LEFT]
cmp r11,r9
cmove r11,r8
mov qword[r10+NODE.LEFT],r11
mov qword[r8+NODE.UP],r10
mov byte[r8+NODE.COL],0
mov qword[r9+NODE.UP],r8
mov byte[r9+NODE.COL],1
mov r11,qword[r8+NODE.RIGHT]
mov r10,qword[r8+NODE.LEFT]
cmp rdx,r10
jne .Case5Left
.Case5Right: mov qword[r8+NODE.RIGHT],r9
mov qword[r9+NODE.LEFT],r11
mov qword[r11+NODE.UP],r9
ret
.Case5Left: mov qword[r8+NODE.LEFT],r9
mov qword[r9+NODE.RIGHT],r10
mov qword[r10+NODE.UP],r9
ret
; Clears the transposition table
align 16
TT_Clear:
mov qword[TTHead+NODE.LEFT],TTNull
mov dword[TTEntries],0
ret
; Prints the table to rdi
align 16
TT_InOrderTraverse:
mov rcx,qword[TTHead+NODE.LEFT]
.entry: cmp rcx,TTNull
je .ret
push rcx
mov rcx,[rcx+NODE.LEFT]
call .entry
mov rcx,[rsp]
call TT_PrintNode
pop rcx
mov rcx,[rcx+NODE.RIGHT]
call .entry
.ret: ret
; Prints node at rcx
align 16
TT_PrintNode:
movsxd rax,dword[rcx+NODE.NUM]
call PrintInteger
mov eax,' '
stosb
ret
PrintInteger: ; rax: number
push rbp
push rdx
mov rbp,rsp
test rax,rax
jns .l1
mov byte[rdi],'-'
add rdi,1
neg rax
.l1: xor edx,edx
div [OutputBase]
push rdx
test rax,rax
jnz .l1
.l2: pop rax
cmp al,9
jbe @f
add al,'a'-10-'0'
@@: add al,'0'
stosb
cmp rsp,rbp
jb .l2
pop rdx
pop rbp
ret
ParseInteger: ; string at rsi, integer to rax
xor ecx,ecx
xor eax,eax
xor edx,edx
cmp byte[rsi],'-'
je .neg
cmp byte[rsi],'+'
je .pos
jmp .next
.neg: not rdx
.pos: add rsi,1
.next: mov cl,byte[rsi]
test cl,cl
jz .done
sub cl,'0'
js .done
cmp cl,9
ja .done
add rsi,1
imul rax,[OutputBase]
add rax,rcx
jmp .next
.done: xor rax,rdx
sub rax,rdx
ret
SkipSpaces: ; rsi string
; skip over anything that is not a digit or NULL
sub rsi,1
@@: add rsi,1
cmp byte[rsi],0
je .done
cmp byte[rsi],'0'
jb @b
cmp byte[rsi],'9'
ja @b
.done: ret
section '.data' data readable writeable
align 8
OutputBase dq 10
align 4
TTEntries dd ?
InputString rb 1024
ResultString rb 1024
align 64
TTHead NODE
TTNull NODE
TT rb sizeof.NODE*TT_MAX_ENTRIES
section '.idata' import data readable writeable
library kernel32,'KERNEL32.DLL',\
user32,'USER32.DLL',\
gdi32,'GDI32.DLL',\
comctl32,'COMCTL32.DLL'
include 'api/kernel32.inc'
include 'api/user32.inc'
include 'api/gdi32.inc'
import comctl32,\
InitCommonControls,'InitCommonControls'
section '.rsrc' resource data readable
directory RT_DIALOG,dialogs
resource dialogs,\
ID_DLGMAIN,LANG_ENGLISH+SUBLANG_DEFAULT,calculator
dialog calculator,'red-black sorter',10,10,384,60,DS_CENTER+DS_MODALFRAME+WS_SYSMENU+WS_MINIMIZEBOX,0,0;ID_MENUMAIN
dialogitem 'STATIC','enter number to sort separated by spaces',-1, 2,02,380,8, WS_VISIBLE+SS_LEFT+WS_GROUP
dialogitem 'EDIT','',ID_EXPRESSION, 2,14,380,12,WS_VISIBLE+WS_TABSTOP+WS_BORDER+ES_AUTOHSCROLL
dialogitem 'EDIT','',ID_RESULT, 2,30,380,12,WS_VISIBLE+WS_BORDER+WS_TABSTOP+ES_READONLY+ES_AUTOHSCROLL
enddialog
Index
> Tutorials and Examples > rather simple example of red-black trees
07 Feb 2014, 18:29