MIPSアセンブリのバイナリ検索ツリーノードにツリーを構築する方法は？

Question

以下のCコードの使用：私は何を指すポインタで始まり、その後、別の値を持つノード、&左、右の&を作る方法がわからない

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); 
    } 

} 

を。言い換えれば、ノードのポインタを左にトラバースするとき、現在のポインタを左のノードを指し示すようにして、左の同じオブジェクトを指しているかのように外側に向けるのはどうでしょうか？

左/右に移動するには？あなたはベアメタルMIPSを使用します場合

right:  

    addi  $a3, $a3, 8 

    jal build 

or 
    right:  

    la a3, 8($a3) 

    jal build 

Answer 1

、あなたの動的な割り当てを管理するためのOSを持っていないので、あなた自身のアロケータを作成する必要があり、あるいは単にノードのグローバルプールを使用します。

OSをお使いの場合は、適切な関数/ syscallを呼び出してください。

include()が有効範囲外になったときにメモリを解放する必要があるため、スタック割り当ては使用できません。

---

あなたが何かをする方法がわからないときは、gccにあなたの仕事をさせるのが最も簡単です。出力可読しかしコメントアウトアセンブリ

、コメントなどが、逆コンパイルアセンブリの使用を元のCコードを取得する

gcc -S -O0 src.c 

を使用します。

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

手動で両方の出力を比較することで、何かを行う方法をよく理解できます。あなたのケースでは

は、わずかに変更されたコードに：

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); 
    } 

} 

これは、手動でコメントしたアセンブリです。関数呼び出しでmips elf abiを使用していることに注意してください。

.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 

---