Hi all,

Ive searched all of the web to help me, and Ive asked various people. Ive got a binary search tree program to write in MIPS, but I really have no idea where to start. Ive got the program in C++, but I dont have linux to attempt to convert in to assembly. Can anyone help please?:sad:

I've never heard of that, but seeing as how it was assigned to you, it must be doable. Do you have some jumping off point, a textbook, in class notes with an example?

Hi all,

Ive searched all of the web to help me, and Ive asked various people. Ive got a binary search tree program to write in MIPS, but I really have no idea where to start. Ive got the program in C++, but I dont have linux to attempt to convert in to assembly. Can anyone help please?:sad:

Please send me your code in C. I'll try to convert it.

I've never heard of that, but seeing as how it was assigned to you, it must be doable. Do you have some jumping off point, a textbook, in class notes with an example?

well i have binary search tree in C++. And I have just a few class notes telling me how to use MIPS. I found online a few things that might help, but Im not sure.

void test_0( int a)
{
   switch (a)
   {
      case0:
        call_0();
        break;
      case 1:
        call_1();
        break;
      case2:
        call_2();
        break;
      case 3:
        call_3();
        break;
    }
}

this translates to

test_0:
  ceqi $2,$3, 1
  hbra .L10,.L1
 
  stqd $lr, 16($sp)
  stqd $sp, -32($sp)
  ai $sp, $sp, -32
  brnz $2, .L4
  cgti $4, $3, 1
 
  brz $4,.L9 
  ceqi $5,$3,2 
  brnz $5,.L5 
  ceqi $6,$3,3 
.L10:
  brz $6,.L1 
  brsl $lr,call_3 
  br .L1 
.L9:
  nop $127
  brnz $3,.L1 
  brsl $lr,call_0 
  br .L1 
.L4:
  brsl $lr,call_1 
  br .L1 
.L5:
  nop $127
  brsl $lr,call_2
.L1:
  ai $sp,$sp,32 
  lqd $lr,16($sp) 
  nop $127
  bi $lr

Thats just one part of an example MIPS program that I found on cellperformance.com. Can anyone explain what nop or lqd or any of that is doing? If I just understand these examples then I can try to reproduce it.
\

Please send me your code in C. I'll try to convert it.

you want it on here, or by email?

well i have binary search tree in C++. And I have just a few class notes telling me how to use MIPS. I found online a few things that might help, but Im not sure.

void test_0( int a)
{
   switch (a)
   {
      case0:
        call_0();
        break;
      case 1:
        call_1();
        break;
      case2:
        call_2();
        break;
      case 3:
        call_3();
        break;
    }
}

this translates to

test_0:
  ceqi $2,$3, 1
  hbra .L10,.L1
 
  stqd $lr, 16($sp)
  stqd $sp, -32($sp)
  ai $sp, $sp, -32
  brnz $2, .L4
  cgti $4, $3, 1
 
  brz $4,.L9 
  ceqi $5,$3,2 
  brnz $5,.L5 
  ceqi $6,$3,3 
.L10:
  brz $6,.L1 
  brsl $lr,call_3 
  br .L1 
.L9:
  nop $127
  brnz $3,.L1 
  brsl $lr,call_0 
  br .L1 
.L4:
  brsl $lr,call_1 
  br .L1 
.L5:
  nop $127
  brsl $lr,call_2
.L1:
  ai $sp,$sp,32 
  lqd $lr,16($sp) 
  nop $127
  bi $lr

Thats just one part of an example MIPS program that I found on cellperformance.com. Can anyone explain what nop or lqd or any of that is doing? If I just understand these examples then I can try to reproduce it.
\

I've seen only one of those instructions: nop, which is a no operation instruction, basically it says do nothing. The format looks different from the MIPS I learned, and it was recent. Looks like you've got the same basic ones, add immediate, branch if equal, I have no idea what ceqi is though. If there are different versions of MIPS, you might try searching for code in those and translating it over to your version.

turns out that code was some instruction language by Sony. Not in fact MIPS. Anyone know how to compare a node in MIPS then insert it into a position on the tree? Also does anyone know how to do a menu in MIPS, like type in 'I' to insert?

Is there a place where I can post the code? Ive got the completed program, and wanted to post it as an example for others.

Is there a place where I can post the code? Ive got the completed program, and wanted to post it as an example for others.

I say just post it here and mark it as solved. I'm assuming that your solution involved pointers in MIPS, I don't envy you.

well here it is solved. Thanks for the help guys.

# Program 2: Bianry Search Tree in MIPS

 .data
 buffer: .space 4
 space:    .asciiz " "
 println:    .asciiz    "\n"
 i:    .asciiz " is the number we want to insert.\n"
 p:    .asciiz "Print something\n"
 d:    .asciiz " is the number we want to delete.\n"
 q:    .asciiz "Quit\n\n"
 CMD:    .asciiz    "Input command (I,P,D,Q,O): "
 input:    .asciiz    "Input inputeger: "
 result:    .asciiz    "The result is: "
 error:    .asciiz    "Please input a valid command.\n"

 .text 
 main: 
 li $s2, 0 # $s2 = the sentinel value. 

 move $a0, $s2 # value = $s2 
 li $a1, 0 # left = NULL 
 li $a2, 0 # right = NULL 
 jal node_create # call node_create 
 move $s0, $v0 # and put the result inpu to $s0. 
 
 input_loop: 
li    $v0, 4
la    $a0, CMD
syscall
li $v0, 8
la $a0, buffer
li $a1, 4
syscall
lb  $t1, 0($a0)
li $t3, 'O' 
li $t4, 'D'
li $t5, 'I'
li $t6, 'P'
li $t7, 'Q'
beq $t1, $t4, input_integer
beq $t1, $t5, input_integer 
beq $t1, $t6, print_input 
beq $t1, $t3, print_input      
beq $t1, $t7, exit 
b err
input_integer:
li    $v0, 4
la    $a0, input
syscall
li    $v0, 5
syscall
move    $t2, $v0

beq $t1, $t4, delete
beq $t1, $t5, insert 
delete:
li    $v0, 1
move    $a0, $t2
syscall
li    $v0, 4
la    $a0, d
syscall
#delete
b input_loop

insert:
# li $v0, 5 # read the input integer
# syscall 
 move $s1, $t2 # set $s1 as the integer inserted
 
# beq $s1, $s2, end_input # if $s2 is equal to $s1 then break the loop 
 
 # tree_insert (number, root); 
 move $a0, $s1 # number= $s1 
 move $a1, $s0 # root = $s0 
 jal tree_insert # call tree_insert. 
 
 b input_loop # repeat the input_loop. 
err: 
li    $v0, 4
la    $a0, error
syscall
b input_loop

 print_input: 
 
 ## Step 3: print out the left and right subtrees. 
 lw $a0, 4($s0) # print out the roots of the left child. 
 jal tree_print_input 
 
 lw $a0, 8($s0) # print out the roots of the right child. 
 jal tree_print_input 
 
 b input_loop # exit. 
 ## end of main. 

b input_loop

  
 node_create: 
 # set up the stack: 
 subu $sp, $sp, 32 
 sw $ra, 28($sp) 
 sw $fp, 24($sp) 
 sw $s0, 20($sp) 
 sw $s1, 16($sp) 
 sw $s2, 12($sp) 
 sw $s3, 8($sp) 
 addu $fp, $sp, 32 
 # capture the parameters: 
 move $s0, $a0 # $s0 = value 
 move $s1, $a1 # $s1 = left
 move $s2, $a2 # $s2 = right 
 
 li $a0, 12 # it needs 12 bytes for a new node. 
 li $v0, 9 # sbrk is syscall 9. 
 syscall 
 move $s3, $v0 
 
 beqz $s3, ERRORMEM 
 
 sw $s0, 0($s3) # node->number = number 
 sw $s1, 4($s3) # node->left = left 
 sw $s2, 8($s3) # node->right = right 
 
 move $v0, $s3 # put return value input into v0. 
 # release the stack frame: 
 lw $ra, 28($sp) # restore the Return Address. 
 lw $fp, 24($sp) # restore the Frame Poinputer. 
 lw $s0, 20($sp) # restore $s0. 
 lw $s1, 16($sp) # restore $s1. 
 lw $s2, 12($sp) # restore $s2. 
 lw $s3, 8($sp) # restore $s3. 
 addu $sp, $sp, 32 # restore the Stack Poinputer. 
 jr $ra # return. 
 ## end of node_create. 
 
 ## tree_insert (value, root): make a new node with the given value 
 ## Register usage: 
 ## $s0 - value 
 ## $s1 - root node
 ## $s2 - a new node 
 ## $s3 - a pointer for the root to the assigned value (root_value) 
 ## $s4 - temporary pointer

 tree_insert:  # set up the stack frame: 
 subu $sp, $sp, 32 
 sw $ra, 28($sp) 
 sw $fp, 24($sp) 
 sw $s0, 20($sp) 
 sw $s1, 16($sp) 
 sw $s2, 12($sp) 
 sw $s3, 8($sp) 
 sw $s3, 4($sp) 
 addu $fp, $sp, 32 

 # grab the parameters: 
 move $s0, $a0 # $s0 = value 
 move $s1, $a1 # $s1 = root 
 
 # make a new node: 
 # new_node = node_create (value, 0, 0); 
 move $a0, $s0 # value = $s0 
 li $a1, 0 # left = 0 
 li $a2, 0 # right = 0 
 jal node_create # call node_create 
 move $s2, $v0 # save the result. 
 
 
 SLOOP: 
 lw $s3, 0($s1) # root_value = root->value; 
 ble $s0, $s3, SLEFT # if (valueue <= s3) goto SLEFT; 
 b SRIGHT # goto SRIGHT; 
 
 SLEFT: 
 lw $s4, 4($s1) # ptr = root->left; 
 beqz $s4, add_left # if (ptr == 0) goto add_left; 
 move $s1, $s4 # root = ptr; 
 b SLOOP # goto SLOOP;
 
 add_left: 
 sw $s2, 4($s1) # root->left = new_node; 
 b end_SLOOP # goto end_SLOOP; 
 
 SRIGHT: 
 lw $s4, 8($s1) # ptr = root->right; 
 beqz $s4, add_right # if (ptr == 0) goto add_right; 
 move $s1, $s4 # root = ptr; 
 b SLOOP # goto SLOOP; 
 
 add_right: 
 sw $s2, 8($s1) # root->right = new_node; 
 b end_SLOOP # goto end_SLOOP; 
 
 end_SLOOP: 
 
 # release the stack frame: 
 lw $ra, 28($sp) # restore the Return Address. 
 lw $fp, 24($sp) # restore the Frame Pointers. 
 lw $s0, 20($sp) # restore $s0. 
 lw $s1, 16($sp) # restore $s1. 
 lw $s2, 12($sp) # restore $s2. 
 lw $s3, 8($sp) # restore $s3. 
 lw $s4, 4($sp) # restore $s4. 
 addu $sp, $sp, 32 # restore the Stack Pointers. 
 jr $ra # return. 
 ## end of node_create. 
 
 ## Do an inorder traversal of the tree, printing out each value. 
 ## Register usage: 
 ## s0 - the tree. 
 tree_print_input: 
 # set up the stack frame:
 subu $sp, $sp, 32 
 sw $ra, 28($sp) 
 sw $fp, 24($sp) 
 sw $s0, 20($sp) 
 addu $fp, $sp, 32 
 # grab the parameter: 
 move $s0, $a0 # $s0 = tree 
 
 beqz $s0, tree_print_input_end # if tree == NULL, then return. 
 
 lw $a0, 4($s0) # recurse left. 
 jal tree_print_input 
 
 # prinput the value of the node: 
 lw $a0, 0($s0) # prinput the value, and 
 li $v0, 1 
 syscall 
 la $a0, println # also prinput a println. 
 li $v0, 4 
 syscall 
 
 lw $a0, 8($s0) # recurse right. 
 jal tree_print_input 
 
 tree_print_input_end: # clean up and return: 
 lw $ra, 28($sp) # restore the Return Address. 
 lw $fp, 24($sp) # restore the Frame Poinputer. 
 lw $s0, 20($sp) # restore $s0. 
 addu $sp, $sp, 32 # restore the Stack Poinputer. 
 jr $ra # return. 
 ## end of tree_print_input. 

 tree_print_input2: 
 # set up the stack frame:
 subu $sp, $sp, 32 
 sw $ra, 28($sp) 
 sw $fp, 24($sp) 
 sw $s0, 20($sp) 
 addu $fp, $sp, 32 
 # grab the parameter: 
 move $s0, $a0 # $s0 = tree 
 
 beqz $s0, tree_print_input_end # if tree == NULL, then return, if not conintue. 
 
 lw $a0, 8($s0) # recurse to the left of the tree. 
 jal tree_print_input2 
 
 # prinput the value of the node: 
 lw $a0, 0($s0) # prinput the value, and 
 li $v0, 1 
 syscall 
 la $a0, println # also prinput a println. 
 li $v0, 4 
 syscall 
 
 lw $a0, 4($s0) # recurse to the right of the tree. 
 jal tree_print_input2 
 
 tree_print_input_end2: # clean up and return: 
 lw $ra, 28($sp) # restore the Return Address. 
 lw $fp, 24($sp) # restore the Frame Pointer. 
 lw $s0, 20($sp) # restore $s0. 
 addu $sp, $sp, 32 # restore the Stack Pointer. 
 jr $ra  
 # end of tree_print_input. 
  
 # The routine to call when sbrk fails; It will jump to exit the program. 
 ERRORMEM: 
 la $a0, ERRORMEM_MSG
 li $v0, 4 
 syscall 
 j exit 
 
 ## The routine to call to exit the program.
 exit: 
 li $v0, 10 
 syscall 
 ## exit the program
 
 
 ## Here is where the data for this program is stored: 
 .data 

ERRORMEM_MSG: .asciiz "Out of memory!\n" 
 
 ## end of BinarySearchTree.asm

How did you figure out how to do all of this? I have a similar assignment and I can't seem to get it working.

This article has been dead for over six months. Start a new discussion instead.