Skip to content

Instantly share code, notes, and snippets.

@icorbrey

icorbrey/binary-search-tree.pep

Created February 7, 2020 15:55
Show Gist options
  • Save icorbrey/357c5a0d4202c9ee04b137d09e95d1ba to your computer and use it in GitHub Desktop.
Save icorbrey/357c5a0d4202c9ee04b137d09e95d1ba to your computer and use it in GitHub Desktop.
Download ZIP
Binary Search Tree in Pep/9 Assembly
Raw
binary-search-tree.pep
;; Isaac Corbrey
;; Binary Search Tree
;; 4 December 2019
BR main
;; struct node ;;
data: .EQUATE 0 ; MEMBER: The data at this node. #2d
left: .EQUATE 2 ; MEMBER: The left child of this node. #2h
right: .EQUATE 4 ; MEMBER: The right child of this node. #2h
;; main() ;;
arr: .EQUATE 2 ; LOCAL: The pointer to the array of tree input values. #2h
root: .EQUATE 0 ; LOCAL: The pointer to the root node. #2h
; Initialize input array
main: SUBsp 4,i ; Push #arr, #root
LDWa 10,i ; Allocate 5 * sizeof(int)
CALL malloc ; Allocate #2d5a
STWx arr,s ; int arr[5]
LDWa 5,i ; Load 5 -> [A]
CALL set ; arr[0] = 5
LDWa 2,i ; Load 2 -> [A]
ADDx 2,i ; Load address of arr[1]
CALL set ; arr[1] = 2
LDWa 3,i ; Load 3 -> [A]
ADDx 2,i ; Load address of arr[2]
CALL set ; arr[2] = 3
LDWa 7,i ; Load 7 -> [A]
ADDx 2,i ; Load address of arr[3]
CALL set ; arr[3] = 7
LDWa 5,i ; Load 5 -> [A]
ADDx 2,i ; Load address of arr[4]
CALL set ; arr[4] = 5
; Build binary search tree
LDWa arr,s ; Load array address
STWa -4,s ; Move #BUarr
LDWa 10,i ; Load array length
STWa -6,s ; Move #BUlen
SUBsp 6,i ; Push #BUretrn, #BUarr, #BUlen
CALL build ; build(arr, 5)
ADDsp 6,i ; Pop #BUretrn, #BUarr, #BUlen
LDWa -2,s ; Load returned address
STWa root,s ; Store root node adddress
; Inorder traversal
STRO msgIn,d ; cout << "Inorder: "
LDWa root,s ; Load root node address
STWa -2,s ; Move #root
SUBsp 2,i ; Push #INroot
CALL inord ; inorder(root)
ADDsp 2,i ; Pop #INroot
STRO newline,d ; cout << endl
; Preorder traversal
STRO msgPre,d ; cout << "Preorder: "
LDWa root,s ; Load root node address
STWa -2,s ; Move #root
SUBsp 2,i ; Push #PRroot
CALL preord ; preorder(root)
ADDsp 2,i ; Pop #PRroot
STRO newline,d ; cout << endl
; Postorder traversal
STRO msgPost,d ; cout << "Postorder: "
LDWa root,s ; Load root node address
STWa -2,s ; Move #root
SUBsp 2,i ; Push #POroot
CALL postord ; postorder(root)
ADDsp 2,i ; Pop #POroot
STRO newline,d ; cout << endl
ADDsp 4,i ; Pop #arr, #root
STOP
;; append(node* root, int data)
AProot: .EQUATE 8 ; PARAM: The pointer to the root node. #2h
APdata: .EQUATE 6 ; PARAM: The data to append to the tree. #2d
;retAdd: .EQUATE 4
APtemp1: .EQUATE 2 ; LOCAL: Temporary node address storage. #2h
APtemp2: .EQUATE 0 ; LOCAL: Temporary node address storage. #2h
; Create temporary variable
append: SUBsp 4,i ; Push #APtemp1, #APtemp2
LDWa AProot,s ; Load root node address
STWa APtemp1,s ; node* temp = root
; While the temp node does not have the new data
while1: LDWx APtemp1,s ; Load temporary node address
ADDx data,i ; Move to temp->data
CALL get ; Get temp->data
CPWa APdata,s ; Compare temp->data to data
BREQ endWh1 ; If temp->data == data, exit the loop
; Branch to left/right node branches
BRGT APleft ; If temp->data > data, go to left branch
BR APright ; If temp->data < data, go to right branch
; If temp->data > data...
APleft: LDWa APtemp1,s ; Load temporary node address
ADDa left,i ; Move to temp->left
STWa APtemp2,s ; Store in temp2
LDWa APtemp2,sf ; Get temp->left
CPWa 0x0000,i ; Compare temp->left to 0x0000
BREQ APLdne ; If temp->left doesn't exist, branch off
; If temp->left exists, traverse to it
LDWx APtemp1,s ; Load temp node
ADDx left,i ; Move to temp->left
CALL get ; Get temp->left
STWa APtemp1,s ; temp = temp->left
BR while1
; If temp->left doesn't exist, create new node
APLdne: LDWa 6,i ; Allocate 6 bytes
CALL malloc ; Allocate #2d3a
STWx APtemp2,s ; node* temp2 = new node()
ADDx data,i ; Move to temp2->data
LDWa APdata,s ; Load new data
CALL set ; temp2->data = data
LDWx APtemp1,s ; Load temp node
ADDx left,i ; Move to temp->left
LDWa APtemp2,s ; Load temp2
CALL set ; temp->left = temp2
BR endWh1
; If temp->data < data...
APright: LDWa APtemp1,s ; Load temporary node address
ADDa right,i ; Move to temp->right
STWa APtemp2,s ; Store in temp2
LDWa APtemp2,sf ; Get temp->right
CPWa 0x0000,i ; Compare temp->right to 0x0000
BREQ APRdne ; If temp->right doesn't exist, branch off
; If temp->right exists, traverse to it
LDWx APtemp1,s ; Load temp node
ADDx right,i ; Move to temp->right
CALL get ; Get temp->right
STWa APtemp1,s ; temp = temp->right
BR while1
; If temp->right doesn't exist, create new node
APRdne: LDWa 6,i ; Allocate 6 bytes
CALL malloc ; Allocate #2d3a
STWx APtemp2,s ; node* temp2 = new node()
ADDx data,i ; Move to temp2->data
LDWa APdata,s ; Load new data
CALL set ; temp2->data = data
LDWx APtemp1,s ; Load temp node
ADDx right,i ; Move to temp->right
LDWa APtemp2,s ; Load temp2
CALL set ; temp->right = temp2
BR endWh1
; End of while loop
endWh1: ADDsp 4,i ; Pop #APtemp1, #APtemp2
RET
;; node* build(int* arr, int len) ;;
BUretrn: .EQUATE 10 ; RETURN: The root node address generated. #2h
BUarr: .EQUATE 8 ; PARAM: The address of the input array. #2h
BUlen: .EQUATE 6 ; PARAM: The length of the input array. #2d
;retAdd: .EQUATE 4
BUroot: .EQUATE 2 ; LOCAL: Pointer to root node of new tree. #2h
BUi: .EQUATE 0 ; LOCAL: Iterator variable. #2d
build: SUBsp 4,i ; Push #BUroot, #BUi
; Initialize root node
LDWa 6,i ; Allocate sizeof(node)
CALL malloc ; Allocate #2d3a
STWx BUroot,s ; node* root = new node()
LDWx BUarr,s ; Load array address
CALL get ; Get arr[0]
LDWx BUroot,s ; Load root node address
ADDx data,i ; Move to root->data
CALL set ; root->data = arr[0]
; Iterate through array
LDWa 2,i ; Initialize for loop
STWa BUi,s ; Iterator i = 1
for2: CPWa BUlen,s ; Compare i to len
BRGE endFor2 ; If i >= len, exit the loop
; Append arr[i] to root
LDWx BUarr,s ; Load array address
ADDx BUi,s ; Move to arr[i]
CALL get ; Get arr[i]
STWa -4,s ; Move #APdata
LDWa BUroot,s ; Load root node address
STWa -2,s ; Move #AProot
SUBsp 4,i ; Push #AProot, #APdata
CALL append ; append(root, arr[i])
ADDsp 4,i ; Pop #AProot, #APdata
; End of for loop
LDWa BUi,s ; Load iterator variable i
ADDa 2,i ; Increment i
STWa BUi,s ; i++
BR for2 ; Loop back to start
; Return address to root node
endFor2: LDWa BUroot,s ; Load root node address
STWa BUretrn,s ; return root
ADDsp 4,i ; Pop #BUroot, #BUi
RET
;; inorder(node* root)
INroot: .EQUATE 4 ; PARAM: The address of the root node. #2h
;retAdd: .EQUATE 2
INtemp: .EQUATE 0 ; LOCAL: Temporary data storage. #2d
inord: SUBsp 2,i ; Push #INtemp
; If root doesn't exist, exit
LDWa INroot,s ; Load root node address
CPWa 0x0000,i ; Compare root to 0x0000
BREQ INret ; If root node doesn't exist, exit
; Print left child tree
LDWx INroot,s ; Load root node address
ADDx left,i ; Move to root->left
CALL get ; Get root->left
STWa -2,s ; Move #INroot
SUBsp 2,i ; Push #INroot
CALL inord ; inorder(root->left)
ADDsp 2,i ; Pop #INroot
; Print data
LDWx INroot,s ; Load root node address
ADDx data,i ; Move to root->data
CALL get ; Get root->data
STWa INtemp,s ; Store root->data in temp
DECO INtemp,s ; cout << root->data
STRO space,d ; cout << ' '
; Print right child tree
LDWx INroot,s ; Load root node address
ADDx right,i ; Move to root->right
CALL get ; Get root->right
STWa -2,s ; Move #INroot
SUBsp 2,i ; Push #INroot
CALL inord ; inorder(root->right)
ADDsp 2,i ; Pop #INroot
INret: ADDsp 2,i ; Pop #INtemp
RET
;; preorder(node* root)
PRroot: .EQUATE 4 ; PARAM: The address of the root node. #2h
;retAdd: .EQUATE 2
PRtemp: .EQUATE 0 ; LOCAL: Temporary data storage. #2d
preord: SUBsp 2,i ; Push #PRtemp
; If root doesn't exist, exit
LDWa PRroot,s ; Load root node address
CPWa 0x0000,i ; Compare root to 0x0000
BREQ PRret ; If root node doesn't exist, exit
; Print data
LDWx PRroot,s ; Load root node address
ADDx data,i ; Move to root->data
CALL get ; Get root->data
STWa PRtemp,s ; Store root->data in temp
DECO PRtemp,s ; cout << root->data
STRO space,d ; cout << ' '
; Print left child tree
LDWx PRroot,s ; Load root node address
ADDx left,i ; Move to root->left
CALL get ; Get root->left
STWa -2,s ; Move #PRroot
SUBsp 2,i ; Push #PRroot
CALL preord ; preorder(root->left)
ADDsp 2,i ; Pop #PRroot
; Print right child tree
LDWx PRroot,s ; Load root node address
ADDx right,i ; Move to root->right
CALL get ; Get root->right
STWa -2,s ; Move #PRroot
SUBsp 2,i ; Push #PRroot
CALL preord ; preorder(root->right)
ADDsp 2,i ; Pop #PRroot
PRret: ADDsp 2,i ; Pop #PRtemp
RET
;; postorder(node* root)
POroot: .EQUATE 4 ; PARAM: The address of the root node. #2h
;retAdd: .EQUATE 2
POtemp: .EQUATE 0 ; LOCAL: Temporary data storage. #2d
postord: SUBsp 2,i ; Push #POtemp
; If root doesn't exist, exit
LDWa POroot,s ; Load root node address
CPWa 0x0000,i ; Compare root to 0x0000
BREQ POret ; If root node doesn't exist, exit
; Print left child tree
LDWx PRroot,s ; Load root node address
ADDx left,i ; Move to root->left
CALL get ; Get root->left
STWa -2,s ; Move #POroot
SUBsp 2,i ; Push #POroot
CALL postord ; postorder(root->left)
ADDsp 2,i ; Pop #POroot
; Print right child tree
LDWx POroot,s ; Load root node address
ADDx right,i ; Move to root->right
CALL get ; Get root->right
STWa -2,s ; Move #POroot
SUBsp 2,i ; Push #POroot
CALL postord ; postorder(root->right)
ADDsp 2,i ; Pop #POroot
; Print data
LDWx POroot,s ; Load root node address
ADDx data,i ; Move to root->data
CALL get ; Get root->data
STWa POtemp,s ; Store root->data in temp
DECO POtemp,s ; cout << root->data
STRO space,d ; cout << ' '
POret: ADDsp 2,i ; Pop #POtemp
RET
temp: .EQUATE 0 ; LOCAL: Temporary address storage for get() and set(). #2h
;; get()
;; [X] -> Address + Offset
;; [A] <- Data at [Address + Offset]
get: SUBsp 2,i ; Push #temp
STWx temp,s ; Store [Address + Offset] in temp
LDWa temp,sf ; Load data at [temp]
ADDsp 2,i ; Pop #temp
RET
;; set()
;; [X] -> Address + Offset
;; [A] -> Data to store at [Address + Offset]
set: SUBsp 2,i ; Push #temp
STWx temp,s ; Store [Address + Offset] in temp
STWa temp,sf ; Store data at [temp]
ADDsp 2,i ; Pop #temp
RET
;; malloc()
;; [A] -> Number of bytes to allocate
;; [X] <- Address of allocated memory
bytes: .EQUATE 2 ; LOCAL: The number of bytes to allocate. #2d
addr: .EQUATE 0 ; LOCAL: The address of the memory allocated. #2h
; Allocate memory
malloc: SUBsp 4,i ; Push #bytes, #addr
STWa bytes,s ; Store number of bytes to allocate
LDWx hpPtr,d ; Store the address of the memory to allocate in [X]
ADDa hpPtr,d ; Increment the heap pointer by [A] bytes
STWa hpPtr,d ; Store the modified heap pointer
STWx addr,s ; Store allocated memory address
; Zero out allocated memory
LDWa 0,i ; Zero out [A] register
LDWx 0,i ; Initialize for loop with [X] = 0
for1: CPWx bytes,s ; Compare [X] to the number of bytes
BRGE endFor1 ; If [X] >= bytes, exit the loop
ADDx addr,s ; Get the address of the current index
CALL set ; Set the current address's value to 0
SUBx addr,s ; Get the current index back
ADDx 1,i ; Increment the index
BR for1 ; Loop back to start
; Return memory address to calling function
endFor1: LDWx addr,s ; Load allocated memory address
ADDsp 4,i ; Pop #bytes, #addr
RET
space: .ASCII " \x00"
newline: .ASCII "\n\x00"
msgIn: .ASCII "Inorder: \x00"
msgPre: .ASCII "Preorder: \x00"
msgPost: .ASCII "Postorder: \x00"
hpPtr: .ADDRSS heap ; The pointer to the heap.
heap: .BLOCK 1 ; The first block of available memory.
.END
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment