#1
  1. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2009
    Posts
    149
    Rep Power
    37

    MIPS doubly linked list


    My assignment is to take two given doubly linked lists and remove all elements from the first list that appear in the 2nd list. My approach:

    go through each element of list 2 and:
    a) if the element is in list 1, delete both nodes
    b) if the element isn't in list 1, delete that node from list 2
    c) reset my list 2 pointer to the first element node
    done when list 2 is empty (list 2 pointer's next is null)

    However, I'm definitely not correctly doing what I thought I was doing (or my approach is logically flawed?) because the test program provided by my instructor spits the same list 1 that I start with back at me.

    Code:
    # jakotheshadows
    #
    # CS3421 Lab 3
    # Fall 2011
    #
    # This program contains a function that removes elements from one list that
    # occur in another.
    
        .text
    # test program starts here
        la	$a0,list1       # load argument registers
        la	$a1,list1end
        la	$a2,list2
        la	$a3,list2end
        jal	remove          # call the function
        lw  $s0,8($v0)	# get reference to node after header
    loop:
        lw  $t0,8($s0)	# see if next pointer is null (trailer)
        li  $t1,-1
        beq $t0,$t1,done    # if so, done
        lw  $a0,0($s0)      # get data from node and print it
        li  $v0,1
        syscall
        la  $a0,space       # print a space
        li  $v0,4
        syscall
        lw  $s0,8($s0)      # get reference to next node
        b   loop            # try again
    done:
        li  $v0,10          # exit
        syscall
    # the lists
        .data
    
    # the first list
    list1:			# header
        .word 0
        .word -1
        .word l1a
    l1a:
        .word -1
        .word list1
        .word l1b
    l1b:
        .word 4
        .word l1a
        .word l1c
    l1c:
        .word 28
        .word l1b
        .word l1d
    l1d:
        .word 319
        .word l1c
        .word list1end
    list1end:		# trailer
        .word 0
        .word l1d
        .word -1
    
    # the second list
    list2:
        .word 0		# header
        .word -1
        .word l2a
    l2a:
        .word 0
        .word list2
        .word l2b
    l2b:
        .word 4
        .word l2a
        .word l2c
    l2c:
        .word 9
        .word l2b
        .word l2d
    l2d:
        .word 319
        .word l2c
        .word list2end
    list2end:		# trailer
        .word 0
        .word l2d
        .word -1
    
    space:
        .asciiz  " "
        .text
    
    # your remove function starts here:
    # $a0 list1, $a2 list2
    remove:
    	move $s0, $a0 # $s0 = list1.getHead(), $t0 has base address of list1 header
    	move $s1, $a2 # $s1 = list2.getHead(), $t1 has base address of list2 header
    	lw $t0, 8($s0)# $t0 = $s0.getNext(), $t0 has base address of list1's first element
    	lw $t1, 8($s1)# $t1 = $s1.getNext(), $t1 has base address of list2's first element
    doWhile:
    	li $t2, -1
    	lw $t3, 8($t1)
    	lw $t3, 8($t3)
    	beq $t2, $t3, return
    	lw $t2, 0($t0)# $t2 = $t0.getData(), $t2 has data from list1's current node
    	lw $t3, 0($t1)# $t3 = $t1.getData(), $t3 has data from list2's current node
    	bne $t2, $t3, skip # if($t2==$t3) the node containing identical data is removed from list1
    	lw $t2, 4($t0)# $t2 has base of previous
    	lw $t3, 8($t0)# $t3 has base of next
    	sw $t3, 8($t2)# $t2.setNext($t3)
    	sw $t2, 4($t3)# $t3.setPrev($t2), the duplicate has now been removed from list1
    	lw $t0, 8($s0)# reset $t0 to first node after the header of list1
    	lw $t2, 4($t1)# $t2 has base of previous
    	lw $t3, 8($t1)# $t3 has base of next
    	sw $t3, 8($t2)# $t2.setNext($t3)
    	sw $t2, 4($t3)# $t3.setPrev($t2), the node has been removed from list 2
    	lw $t1, 8($s1)# reset $t1 to first node after the header of list2
    skip:
    	lw $t0, 8($t0)# $t0 = $t0.getNext(), advance through list1
    	lw $t2, 8($t0)# $t2 = $t0.getNext(), check if next node is null
    	li $t3, -1 
    	bne $t3, $t2, doWhile
    	lw $t2, 4($t1)# $t2 has base of previous
    	lw $t3, 8($t1)# $t3 has base of next
    	sw $t3, 8($t2)# $t2.setNext($t3)
    	sw $t2, 4($t3)# $t3.setPrev($t2), the node has been removed from list 2
    	lw $t1, 8($s1)# reset $t1 to first node after the header of list2
    	lw $t0, 8($s1)# reset $t0 to first node after the header of list1
    	j doWhile	
    return:
    	move $v0, $s0
    	jr $ra
    output:
    -1 4 28 319
    -- program is finished running --

    expected:
    -1 28

    Am I properly changing the node references when I delete nodes, or am I just pissing in the wind? Thanks in advance for any suggestions or advice.
    Last edited by jakotheshadows; September 25th, 2011 at 06:29 PM.
  2. #2
  3. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2009
    Posts
    149
    Rep Power
    37
    After cleaning the code up by using more registers and more clearly commenting what each register was to be used for, I discovered that my problem was that $t0 and $t1 were actually at some point traversing the same list by accident. Solved!

IMN logo majestic logo threadwatch logo seochat tools logo