CS U380 - List of Ints Lab 6 - List of Ints

Purpose:

Further practice in writing MIPS programs including the use of pointers and structures. Introduction:
  This is a simple lab which you should be able to complete within your lab session.

A linked list is made up of a set of nodes, each defined with the C language "struct" declaration shown below:

/* Node declaration for linked list */
struct node {
    struct node *next;        /* pointer to next node */
    int value;                /* place to hold integer value */
};

In MIPS terms, a node is an area of size 8 bytes. The word at the address of the node, plus the offset zero, is a pointer, and the word at the address of the node, plus 4, is an integer.

A node pointer is either NULL or it points to an actual node.   For this exercise we will use a linked list as a way to store a ordered set of integers.  Integers will be stored in stack order with the first node in the list holding the most recently inserted integer and the last node in the list holding the first integer inserted.

Your assignment is to write a procedure called "newnode", in MIPS assembly language, that adds a node to such a list.  The procedure takes a single integer argument, creates a new instance of a node, and links it into the list in the proper place.  The C language program shown below demonstrates how to write and test your procedure (stdio.h and stdlib.h must be included)

static struct node *head = NULL;    /* global pointer to head of list */

/*
  Maintains a list of ints by inserting each
  new element at the front.
*/

void newnode(int value) {
  struct node *temp = malloc(sizeof(struct node));
  temp->next = head;
  temp->value = value;
  head = temp;
}

/*
 Prints the integers in the list.
*/

void printlist(void) {
  struct node *ptr;

  ptr = head;
  while (ptr!=0) {
    printf("%d\n", ptr->value);
    ptr = ptr->next;
  }
}
 

main() { /* test program for newnode */

  newnode(5);
  newnode(1);
  newnode(0);
  newnode(6);
  newnode(1);
  newnode(10);

  printlist();

}
 

The MIPS instruction that implements the line
ptr= ptr->next;
is "lw $s2,0($s2)", if $s2 holds the value of next.

Prelab:

Study the C version of the linked list program - make certain you understand how it works.  Think about how you would rewrite the function "newnode" in MIPS assembly language, then write on paper or in a file a preliminary version.  Assume that there is a procedure malloc for allocating memory (as in C) and a printlist procedure for printing a list.
  Task 1: Create a lab6 directory and copy the lab file: /course/csu380jc/.www/lab6/lab6.s

Task 2: Study the "main:" procedure, figure out how it operates. It is currently is set to insert the following numbers (5, 1, 0, 6, 1, 10).

Task 3: Go to the empty "newnode:" procedure and fill it in using the MIPS version that you developed in the prelab.  The procedure "newnode" receives the integer in $a0 and returns nothing.  It adds its new node to the list pointed to by the static variable called "head".

Your program should work for any arbitrary non-negative number of integer values.
 

Here is output for the C version above:

10
1
6
0
1
5
 

 For Checkoff:

Show me your MIPS code and run your program inserting the values in the following list: (100, 99, 691, 0, 42, 12, 42, 24). You will need to edit the main function to insert that list instead of the given one.
This page last modified 03/10/2008.