RISC-V ALE Exercise Book v1.3.2

ABI-compliant Linked List Custom Search

Instructions

In this activity, you must write a program in RISC-V assembly language that has a ABI-compliant function int linked_list_search(Node *head_node, int val), similar to the one implemented in exercise 6.6. Your code will be linked to a code in C that calls the linked_list_search function and expects the return value to be the index of the node where the sum of the values is equal to val or -1 in case there isn't such a node on the linked list.

In addition to linked_list_search, you will need to implement a few utility functions that will be required for this exercise and future ones. There is no need to handle errors nor end-of-file (EOF).

• void puts ( const char * str );

  Description	Parameters	Return Value
  puts - C++ Reference	String terminated by \0	-

• char * gets ( char * str );

  Description	Parameters	Return Value
  gets - C++ Reference	Buffer to be filled	Check function documentation

• int atoi (const char * str);

  Description	Parameters	Return Value
  atoi - C++ Reference	String terminated by \0	Integer represented by the string

• char * itoa ( int value, char * str, int base );

  Description	Parameters	Return Value
  itoa - C++ Reference	Check function documentation. Only bases 10 and 16 will be tested. The tests won't be case-sensitive.	-

• void exit(int code);

  Description	Parameters	Return Value
  Calls exit syscall to finish execution.	Return code (usually used as error code).	-

lib.h:

typedef struct Node {
    int val1, val2;
    struct Node *next;
} Node;

int linked_list_search(Node *head_node, int val);
void puts ( const char *str );
char *gets ( char *str );
int atoi (const char *str);
char *itoa ( int value, char *str, int base );
void exit(int code);

Input

Test Case index and specific input depending on the test case (check example.c).

Output

Output according to the test case.

Notes and Tips

• The linked_list_search function will receive the address of the head node on register a0 and the value being searched on register a1, and must return on the register a0 the index of the node, if found, or -1 otherwise.
• The fields of the linked list node struct are VAL1, VAL2 and NEXT, in this order. VAL1 and VAL2 are the signed int values stored on the node and NEXT is the pointer to the next node on the linked list. If there isn't a next node, it will be a NULL pointer.
• To check if the received value is on the current node, the comparison VAL1 + VAL2 = received value must be made.
• A NULL pointer is represented by the value 0.
• The indexing of the list nodes starts at 0 (i.e. the head_node has index 0), and the linked list will have up to 1000 nodes in the test cases.
• All nodes will have different sum values.
• Symbols must be set as global (.globl directive) for the linker to resolve undefined references.
• The character \0 corresponds to the null byte, which has the value 0. However, using li a0, '\0' will lead to errors because the assembler interprets the value as the character '0' (which has an ASCII value of 48) rather than the null byte.
• You can test your code using the simulator's assistant from this link.