Project 1 Solution

1. Implementing a Dynamic Memory Allocator
This part requires you to develop a small set of dynamic memory management routines written in the MIPS assembly language. These routines should mimic at an elementary level C-library function routines that perform dynamic memory allocation and de-allocation. You will subsequently use these routines to support dynamic data structures, such as, stacks, queues, or any other structure with a linked implementation. The general memory allocation and de-allocation problem is quite involved for direct implementation in MIPS, so we focus on fixed-size data items. In this project, the memory is managed by a singly linked list.
1.1 Dynamic Memory Organization
We will be supporting allocation and de-allocation of memory blocks using a singly linked list. One memory block is defined with block_t type in C.
typedef struct _block_t {
    data_t data;                /* data_t can be anything but needs to be defined */
    struct _block_t *next;      /* Pointer to the next item in the free list if not zero */
} block_t;                      /* What is the best value for sizeof(block_t)? */
Each memory block has a pointer that points to the next block. Therefore, all the memory blocks are accessible by traversing a list. There is a global variable, FreeList, which has the first block address.
1.2 Implementing Management Functions
Implement three functions to manage a memory.
    1. void mem_init():
We use an array M with N elements of type block_t to represent the entire memory. This function does initialization of each block and builds a linked list of currently unallocated blocks. In each element (block), data field is set to zero and next field is set to the next element. You need to know the size of a block (sizeof(block_t)).
    2. block_t* mem_alloc():
This function returns the first available memory block from the linked list. It updates the linked list.
    3. void mem_dealloc(block_t *p):
This function reclaims the block p to the linked list. It adds this block at the beginning of the linked list. Thus, the block becomes the first block of the linked list.
The following codes show equivalent C functions.
#define N               /* quite a large number, such as 20 */

block_t M[N];
block_t* FreeList = M;  /* Note that Freelist contains currently unallocated blocks only */

void mem_init()
{
    int i;

    /* It's a good idea to clear the data area initially. */
    (void) memset( (void *) M, 0, N * sizeof(block_t) );

    for ( i = 1; i < N; i++ )
    {
        M[i - 1].next = &M[i];
    }

    /* Note: M[N - 1].next = NULL */
}

block_t* mem_alloc()
{
    block_t *p = FreeList;  /* Let p point where F points to */
    if ( FreeList )         /* if FreeList is not null */
    {
        FreeList = FreeList->next;
    }
    else
    {
        /* Exception */
    }

    return( p );
}

void mem_dealloc(block_t *p)
{
    if ( p ) /* if p is not null */
    {
        p->next = FreeList;
        FreeList = p; /* Update FreeList to point to the latest freed element */
    }
    else
    {
        /* Exception */
    }
}
Define two variables, M and FreeList in data segment. Use MIPS .space directive to allocate a large number of consecutive bytes with uninitialized storage.
.data
M:              .space  (number)        # Put a number in bytes, which is N * sizeof(block_t).
FreeList:       .word   M               # Initially it points to M.

2. Handling data_t Structure
Each element (block) of the linked list has one integer value in data_t structure. Data of the element is defined with the type data_t.
The following C codes gives you some clues for implementation.
typedef struct _data_t {
    int val;                    /* a word of an integer */
} data_t;                       /* What is sizeof(data_t)? */
Implement two functions that assign the val field with a specific type and one function that prints the value of the val field on the console properly according to its type.
    1. void set_data_int(data_t* p, int integer)
    2. void print_data(data_t* p)

3. Implementing Stack
A stack is a data structure where data blocks are added dynamically as the need arises. The order that blocks can be removed, though, is the reverse of the chronological order data was entered. Stack uses a LIFO (Last In First Out) principle. Data enters at the one end ("Top") and exits from the same end of the stack only. In this project, one data block is the same as the one block (block_t).
In MIPS program, define a global variable for the stack data structure, Top, in data segment. This variable has the address of the first data block in the stack. If there is no block in the stack, it points out null. Thus, it has 0 initially.
Top:    .word   0               # Top of Stack
Implement two functions for stack manipulation.
    1. void stack_push(data_t* d):
Allocate a block from FreeList (use mem_alloc()) and initialize data field of the block with parameter d. The next pointer (block_t *next) of this block points out the previous top element Top points out before this operation in order to maintain the stack properly. Set this new block on the top of the stack by setting Top to point out this block. After this function call, the depth of the stack increases by 1.
    2. data_t* stack_pop():
Return the data of the block at the top of the stack. Set Top to point out the element the next pointer points out. Deallocate this block (use mem_dealloc()). After this function call, the depth of the stack decreases by 1.

4. Evaluating Postfix Expression
MIPS program will evaluate an expression written in postfix (a.k.a. Reverse Polish) notation. In this notation, each operator appears after its operands. This expression does not need parentheses to specify the order among operators.
To evaluate a postfix expression, we make a single left-to-right scan of it. We place the operands on a stack until we find an operator. We then remove, from the stack, the correct number of operands for the operator (in this project, only two operands because all the operators are binary), perform the operation, and place the result back on the stack. We continue this process until we reach the end of the expression of the string. Finally, the answer will be placed on the top of the stack. Figure A shows an example of this processing when the input has nine tokens as "62/3-42*+".
Data (Token)
Stack[0] (Top)
Stack[1]
Stack[2]
6
6
 
 
2
6
2
 
/
6/2
 
 
3
6/2
3
 
-
6/2-3
 
 
4
6/2-3
4
 
2
6/2-3
4
2
*
6/2-3
4*2
 
+
6/2-3+4*2
 
 
Figure A: Postfix expression evaluation
Implement a function, int eval(char* e), which evaluates a postfix expression given as a string parameter (the maximum length is 64). This function uses stack_push(), stack_pop(), and set_data_int().
Expressions consist of only integers and arithmetic operators. We assume that each character of the string is a single token, hence, making the range of an integer between 0 and 9. This will simplify parsing the string expression into multiple tokens. Therefore, MIPS program receives an expression from a user input and prints its evaluation result on the console. Please test your program with many different expressions.

5. Completing the Project
Your code must report proper error messages if it finds exceptions, such as stack popup when the stack is empty. It is also an exception if the postfix evaluation string has other than digits and operators. It must report an error messages if the stack has more than one block after the evalation of an expression is completed.
Check-off Requirement: Demonstrate execution of your program in PCSPIM to TA with several postfix expressions given by TA.

Turn in your source code (you can only make one source code file and implement all the functions in it. Since each later section will use the function in previous sections, you don't need to make test program for each part.) to CSNET. One submission is required for one team. Please specify team members in the beginning part of each file. Source codes must be well-organized with sufficient comments. For declaration of each function, write comments on the name of function, required parameters (passed to which registers), and what it does.