Task: Write a CASM assembler program that augments our linked list program with
ID: 3837841 • Letter: T
Question
Task: Write a CASM assembler program that augments our linked list program with two new subroutines:
insert_sorted(int newvalue, node* head_ptr) -- returns the address of the new node if head_ptr is null, otherwise it returns head_ptr
print_list(node* head_ptr)
Note that insert_sorted() returns the address of the new node if head_ptr is NULL (the number 0.) This occurs when the list is empty. The main program needs to be able to permanently save the head of the chain. So the main program just assigns to its head point whatever insert_sorted returns.
To allocate a new "node" in the linked list, simply get the memory location from a variable FREEMEMPTR, and use that address. Make sure to add 2 to FREEMEMPTR (which is just a simple integer variable) so that next time you don't reclaim memory that is already used.
print_list() merely spins through the entire list and prints out the list, one after the other, using STD 4095.
Rubric:
30
Program functions correctly for all test cases (see below)
10
Proper structures are used (assembler templates and array templates)
10
Comments exist
Test cases:
1. print_list prints an empty list correctly
2. print_list prints a list with 1 or more elements correctly (in right order)
3. insert_sorted creates a list with one node and returns that address when head_ptr == NULL
4. insert_sorted() puts a new node into the middle of an existing list correctly (in the correct place)
5. insert_sorted() puts a new node into an existing list at the end if the new value is greater than all the values in the list
Image of the linked list in memory:
;-------------------------------------------------------------------------
HEAD: NUM 2500 ; pointer to first node
FREEMEMPTR: NUM 2508 ; next free spot after end of the chain
=2500
NUM 46 ; first node in the list
NUM *+1 ; pointer to next free slot (will be 2501)
NUM 99 ; second node in list
NUM *+1
NUM 17 ; third node in the list
NUM *+1
NUM 57 ; third node in the list
NUM 0 ; NULL, end of list marker
The directive NUM *+1 means to add 1 to the current memory pointer as it is being assembled. Think of the *, when it is used as an operand to NUM, as being "this memory location right here, i.e. the address of this NUM."
30
Program functions correctly for all test cases (see below)
10
Proper structures are used (assembler templates and array templates)
10
Comments exist
Explanation / Answer
Answer
Below is the required code:
sortedInsert(node**, node*):
str fp, [sp, #-4]!
add fp, sp, #0
sub sp, sp, #20
str r0, [fp, #-16]
str r1, [fp, #-20]
ldr r3, [fp, #-16]
ldr r3, [r3]
cmp r3, #0
beq .L2
ldr r3, [fp, #-16]
ldr r3, [r3]
ldr r2, [r3]
ldr r3, [fp, #-20]
ldr r3, [r3]
cmp r2, r3
blt .L3
.L2:
ldr r3, [fp, #-16]
ldr r2, [r3]
ldr r3, [fp, #-20]
str r2, [r3, #4]
ldr r3, [fp, #-16]
ldr r2, [fp, #-20]
str r2, [r3]
b .L4
.L3:
ldr r3, [fp, #-16]
ldr r3, [r3]
str r3, [fp, #-8]
.L6:
ldr r3, [fp, #-8]
ldr r3, [r3, #4]
cmp r3, #0
beq .L5
ldr r3, [fp, #-8]
ldr r3, [r3, #4]
ldr r2, [r3]
ldr r3, [fp, #-20]
ldr r3, [r3]
cmp r2, r3
bge .L5
ldr r3, [fp, #-8]
ldr r3, [r3, #4]
str r3, [fp, #-8]
b .L6
.L5:
ldr r3, [fp, #-8]
ldr r2, [r3, #4]
ldr r3, [fp, #-20]
str r2, [r3, #4]
ldr r3, [fp, #-8]
ldr r2, [fp, #-20]
str r2, [r3, #4]
.L4:
mov r0, r0 @ nop
sub sp, fp, #0
ldr fp, [sp], #4
bx lr
newNode(int):
stmfd sp!, {fp, lr}
add fp, sp, #4
sub sp, sp, #16
str r0, [fp, #-16]
mov r0, #8
bl malloc
mov r3, r0
str r3, [fp, #-8]
ldr r3, [fp, #-8]
ldr r2, [fp, #-16]
str r2, [r3]
ldr r3, [fp, #-8]
mov r2, #0
str r2, [r3, #4]
ldr r3, [fp, #-8]
mov r0, r3
sub sp, fp, #4
ldmfd sp!, {fp, lr}
bx lr
.LC0:
.ascii "%d "
printList(node*):
stmfd sp!, {fp, lr}
add fp, sp, #4
sub sp, sp, #16
str r0, [fp, #-16]
ldr r3, [fp, #-16]
str r3, [fp, #-8]
.L11:
ldr r3, [fp, #-8]
cmp r3, #0
beq .L12
ldr r3, [fp, #-8]
ldr r3, [r3]
mov r1, r3
ldr r0, .L13
bl printf
ldr r3, [fp, #-8]
ldr r3, [r3, #4]
str r3, [fp, #-8]
b .L11
.L12:
mov r0, r0 @ nop
sub sp, fp, #4
ldmfd sp!, {fp, lr}
bx lr
.L13:
.word .LC0
.LC1:
.ascii "
Created Linked List"
main:
stmfd sp!, {fp, lr}
add fp, sp, #4
sub sp, sp, #8
mov r3, #0
str r3, [fp, #-12]
mov r0, #7
bl newNode(int)
str r0, [fp, #-8]
sub r3, fp, #12
ldr r1, [fp, #-8]
mov r0, r3
bl sortedInsert(node**, node*)
ldr r0, .L17
bl puts
ldr r3, [fp, #-12]
mov r0, r3
bl printList(node*)
mov r3, #0
mov r0, r3
sub sp, fp, #4
ldmfd sp!, {fp, lr}
bx lr
.L17:
.word .LC1
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.