BTREE算法C语言实现 [复制链接]

论坛徽章:: 0

11楼 [报告]

发表于 2007-12-07 15:04 |只看该作者

回复 #10 ldap 的帖子

void init_btree32_i_walker(walker *cc)
{
    if (cc == NULL) {
        return;
    }

    cc->pos = 0;
    cc->out = WALKER_OUT_INIT;
    cc->beg = 0;
}

bnode32_i *walker_btree32_i(bnode32_i *node, int16 pos, void **index, int32 *key, walker *cc)
{
    int16 i;

    Assert(key != NULL);
    Assert(pos >= 0);
    Assert(cc != NULL);

    if (node == NULL) {
        return NULL;
    }

    /* enter last out scene */
    if (cc->out == WALKER_OUT_LEAF)
        goto leaf;
    if (cc->out == WALKER_OUT_ROOT)
        goto start;

    cc->pos = pos;

start:
    /* trace to bottom */
    for(;;) {
        if (node->child[0] != NULL) {
            node = node->child[cc->pos];
            cc->pos = 0;
            continue;
        }
        break;
    }

leaf:
    /* current node must be leaf node */
    for (i = cc->beg; i < node->num; i++) {
        *key = node->key[i];
        *index = node->index[i];
        cc->out = WALKER_OUT_LEAF;
        cc->beg = i + 1;
        return node;
    }

prev:
    /* output the last key of root */
    if (node->parent == NULL) {
        return NULL;
    }

    /* output the key of previus middle node */
    if (node->pos < node->parent->num) {
        *key = node->parent->key[node->pos];
        *index = node->parent->index[node->pos];

        cc->pos = node->pos + 1;
        node = node->parent;

        cc->out = WALKER_OUT_ROOT;
        cc->beg = 0;
        return node;
    }

    /* have output the all key in the middle node,*/
    /* so must output the up node. */

    node = node->parent;
    goto prev;
}

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

ldap

丰衣足食

论坛徽章:: 0

12楼 [报告]

发表于 2007-12-07 15:05 |只看该作者

回复 #11 ldap 的帖子

void free_btree32_i(bnode32_i *node)
{
    int16    pos = 0;
    bnode32_i    *freenode;

    if (node == NULL) {
        return;
    }

start:
    /* trace to bottom */
    for(;;) {
        if (node->child[0] != NULL) {
            node = node->child[pos];
            pos = 0;
            continue;
        }
        break;
    }
prev:
    if (node->parent == NULL) {
        /* free root */
        node = btree_free(node);
        return;
    }

    if (node->pos < node->parent->num) {

        /* free child */

        pos = node->pos + 1;
        freenode = node;
        node = node->parent;

        freenode = btree_free(freenode);

        goto start;
    }

    /* free right node */
    freenode = node;
    node = node->parent;
    freenode = btree_free(freenode);

    goto prev;
}

bnode32_i *root_btree32_i(bnode32_i *node)
{
    Assert(node != NULL);

    for(;;) {
        if (node->parent != NULL) {
            node = node->parent;
        }
        else {
            break;
        }
    }

    return node;
}