כרמי מרימוביץ

אתר אישי

סכום אברי עץ בינרי

struct node {
    struct node *left;
    struct node *right;
    long long value;
};

long long sum(struct node *node) {
    if (node == NULL)
        return (0);

    return (sum(node->left) + node->value + sum(node->right));
}

sum:
    bne a0, zero, work  // if (node != NULL) goto work
    jalr   zero, 0(ra)  // return
work:
    addi   sp, sp, -24    // 3 dwords on stack
    sd  ra, 0(sp)         // save: return address
    sd  a0, 8(sp)         //       node

    ld  a0, 0(a0)       // node->left
    jal ra, sum         // sum(node->left)

    ld  t0, 8(sp)       // node
    ld  t1, 16(t0)      // node->value
    add t1, t1, a0      / node->value + sum(node->left)
    sd  t1, 16(sp)      // save 

    ld  a0, 8(t0)     // node->right
    jal ra, sum       // sum(node->right)

    ld  t0, 16(sp)      // restore node->value + sum(node->left)
    add a0, a0, t0      // node->value + sum(node->left) + sum(node->right)

    ld  ra, 0(sp)
    addi    sp, sp, 24

    jalr zero, 0(ra)    // return