Y86-Simulator/insertBST.ys at master · JackCWatson/Y86-Simulator · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
# This program calls an insertBST function twice to insert two
# nodes into an existing binary search tree.
# The parameters to minBST are in %rdi and %rsi.
# %rdi contains the address of the root node. %rsi contains the
# address of a node to insert.  A node contains three 8-byte
# fields: address of left node, address of right node, value of
# node.
#
# This program isn't for the faint-hearted.
#
       .pos 0
       irmovq stack, %rsp
       irmovq node0, %rdi  #address of root node
       irmovq newN1, %rsi  #address of node to insert
       call insertBST
       irmovq node0, %rdi  #address of root node
       irmovq newN2, %rsi  #address of node to insert
       call insertBST
       halt
#
insertBST: #address of root node is in %rdi
           #address of node to insert is in %rsi

           irmovq 16, %r8
           irmovq 8, %r11

           rrmovq %rsi, %r10
           addq %r8, %r10
           mrmovq (%r10), %r10
compare:
           andq %rdi, %rdi
           je swap
           rrmovq %rdi, %r9
           addq %r8, %r9
           mrmovq (%r9), %r9
           subq %r10, %r9
           jg leftparent
           mrmovq 8(%rdi), %rdi
           jmp compare
leftparent:
           mrmovq (%rdi), %rdi
           jmp compare
swap:
           rmmovq %rsi, (%rdi)
done:  ret
#
       .pos 0x200
node0: .quad node1    #address of left child
       .quad node2    #address of right child
       .quad 10       #value in the node
node1: .quad node3
       .quad 0 #should be modified to be newNd1 (0x290)
       .quad 4
node2: .quad node4
       .quad node5
       .quad 15
node3: .quad 0
       .quad 0
       .quad 2
node4: .quad 0  #should be modified to be newNd2 (0x2a8)
       .quad 0
       .quad 12
node5: .quad 0
       .quad 0
       .quad 20
newN1: .quad 0
       .quad 0
       .quad 5
newN2: .quad 0
       .quad 0
       .quad 11
       .pos 0x400
stack: .quad 0