Wie erstellt man einen Baum im binären Suchbaumknoten in der MIPS-Assembly?

Question

den C-Code verwendet unter:

void insert(node ** tree, int val) 
{ 
    node *temp = NULL; 
    if(!(*tree)) 
    { 
     temp = (node *)malloc(sizeof(node)); 
     temp->left = temp->right = NULL; 
     temp->data = val; 
     *tree = temp; 
     return; 
    } 

    if(val < (*tree)->data) 
    { 
     insert(&(*tree)->left, val); 
    } 
    else if(val > (*tree)->data) 
    { 
     insert(&(*tree)->right, val); 
    } 

} 

Ich weiß nicht, wie mit einem Zeiger auf nichts zu starten, und dann einen anderen Knoten mit Wert machen, & links, rechts &. Mit anderen Worten, wenn ich den Zeiger des linken Knotens durchquere, wie würde ich den aktuellen Zeiger zum linken Knoten machen und dann nach außen zeigen, als ob er auf das gleiche Objekt von links zeigen würde.

Wie mache ich links/rechts?

right:  

    addi  $a3, $a3, 8 

    jal build 

or 
    right:  

    la a3, 8($a3) 

    jal build 

Answer 1

Wenn Sie Bare-Metal-Mips verwenden werden, werden Sie nicht ein Betriebssystem haben Ihre dynamische Zuordnung zu verwalten, so dass Sie Ihren eigenen allocator vornehmen müssen, oder einfach nur einen globalen Pool von Knoten verwenden.

Wenn Sie ein Betriebssystem verwenden, rufen Sie einfach die entsprechende Funktion/syscall.

Sie können die Stapelzuweisung nicht verwenden, da dieser Speicher freigegeben werden sollte, wenn include() den Gültigkeitsbereich verlässt.

---

Wenn Sie nicht wissen, wie etwas zu tun ist, ist es das einfachste, gcc die Arbeit für Sie erledigen zu lassen.

Zur Ausgabe lesbar aber unkommentiert Montage verwenden

gcc -S -O0 src.c 

Um den ursprünglichen C-Code als Kommentare, aber auf dekompilierten Montage, Gebrauch.

gcc -c src.c -g -O0 
objdump -S src.o > out.S 

Durch manuelles Vergleichen der beiden Ausgänge können Sie ein gutes Verständnis darüber, wie etwas zu tun.

In Ihrem Fall auf dem leicht modifizierten Code:

typedef struct node { int data; struct node * left; struct node * right; } node; 

node node_pool[30]; 
node pool_index = 29; 

void insert(node ** tree, int val) 
{ 
    node *temp = NULL; 
    if(!(*tree)) 
    { 
     temp = &node_pool[pool_index]; 
     temp->left = temp->right = NULL; 
     temp->data = val; 
     *tree = temp; 
     return; 
    } 

    if(val < (*tree)->data) 
    { 
     insert(&(*tree)->left, val); 
    } 
    else if(val > (*tree)->data) 
    { 
     insert(&(*tree)->right, val); 
    } 

} 

Dies ist die Montage von Hand kommentiert ist. Beachten Sie, dass beim Funktionsaufruf mips elf abi verwendet wird.

.comm node_pool,360,4 
#node node_pool[30]; 

    .globl pool_index 
    .data 
    .align 2 
    .type pool_index, @object 
    .size pool_index, 4 
pool_index: 
    .word 29 
#unsigned int pool_index = 29; 

    .text 
    .align 2 
    .globl insert 
    .set nomips16 
    .set nomicromips 
    .ent insert 
    .type insert, @function 
insert: 
    .frame $fp,40,$31  # vars= 8, regs= 2/0, args= 16, gp= 8 
    .mask 0xc0000000,-4 
    .fmask 0x00000000,0 
    .set noreorder 
    .set nomacro 



    addiu $sp,$sp,-40 
    sw $31,36($sp) 
    sw $fp,32($sp) 
    move $fp,$sp 
    sw $4,40($fp) 
    sw $5,44($fp) 
    sw $0,24($fp) 
    #void insert(node ** tree, int val) 
#{ 

    lw $2,40($fp) 
    lw $2,0($2) 
    bne $2,$0,$L2 
    nop 

#temp = &node_pool[pool_index--]; 
    lui $2,%hi(pool_index) 
    lw $3,%lo(pool_index)($2) 
    move $2,$3 
    sll $2,$2,2 
    sll $4,$2,2 
    subu $4,$4,$2 
    lui $2,%hi(node_pool) 
    addiu $2,$2,%lo(node_pool) 
    addu $2,$4,$2 
    sw $2,24($fp) 
    addiu $3,$3,-1 
    lui $2,%hi(pool_index) 
    sw $3,%lo(pool_index)($2) 
#temp->left = temp->right = NULL; 
    lw $2,24($fp) 
    sw $0,8($2) 
    lw $2,24($fp) 
    lw $3,8($2) 
    lw $2,24($fp) 
    sw $3,4($2) 
    lw $2,24($fp) 
    lw $3,44($fp) 
    sw $3,0($2) 
    lw $2,40($fp) 
    lw $3,24($fp) 
    sw $3,0($2) 
    j $L1 
    nop 
#if(val < (*tree)->data){ 
$L2: 
    lw $2,40($fp) 
    lw $2,0($2) 
    lw $3,0($2) 
    lw $2,44($fp) 
    slt $2,$2,$3 
    beq $2,$0,$L4 
    nop 

    lw $2,40($fp) 
    lw $2,0($2) 
    addiu $2,$2,4 
    move $4,$2 
    lw $5,44($fp) 
    jal insert 
    nop 

    j $L1 
    nop 

#insert(&(*tree)->left, val); 
# } 

$L4: 
    lw $2,40($fp) 
    lw $2,0($2) 
    lw $3,0($2) 
    lw $2,44($fp) 
    slt $2,$3,$2 
    beq $2,$0,$L1 
    nop 

    lw $2,40($fp) 
    lw $2,0($2) 
    addiu $2,$2,8 
    move $4,$2 
    lw $5,44($fp) 
    jal insert 
    nop 

# else if(val > (*tree)->data){ 
# insert(&(*tree)->right, val); 
# } 

$L1: 
    move $sp,$fp 
    lw $31,36($sp) 
    lw $fp,32($sp) 
    addiu $sp,$sp,40 
    j $31 
    nop 

---