1

オンラインで読み取り可能なものが見つからなかったため、Bツリーのメモリ内C実装を作成しています（つまり、この恐ろしいコード：http://www.freewebs.com/attractivechaos/kbtree.h.html）。

要素を挿入するときに、以前に挿入された要素を見つけられないことがあるため、うまく機能しません。また、私の一般的な実装が非常に優れているかどうか、および挿入を賢明な方法で行っているかどうかもわかりません。私がやったことを批判し、なぜそれがいつもうまくいかないのかを知ることができる人はいますか?

明らかに、B ツリーは Red-black ツリーや AVL ツリーよりも効率的です。これは、要素が各ノードのメモリに一緒に格納されるためです。それは私に興味を持った。

「順序」は要素の数であり、子ポインタの数ではないことに注意してください。理由は単純で、それが私にとってより理にかなっているからです。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define CB_BTREE_ORDER 8
#define CB_BTREE_HALF_ORDER CB_BTREE_ORDER/2

typedef struct{
    void * parent;
    void * children[CB_BTREE_ORDER + 1];
    unsigned char numElements;
} CBBTreeNode;

typedef struct{
    unsigned char found;
    CBBTreeNode * node;
    unsigned char pos;
} CBFindResult;

typedef struct{
    unsigned char keySize;
    unsigned char dataSize;
    int nodeSize;
    CBBTreeNode * root;
} CBAssociativeArray;

CBFindResult CBAssociativeArrayFind(CBAssociativeArray * self, unsigned char * key);
void CBAssociativeArrayInsert(CBAssociativeArray * self, unsigned char * key, void * data, CBFindResult pos, CBBTreeNode * right);
CBFindResult CBBTreeNodeBinarySearch(CBBTreeNode * self, unsigned char * key, unsigned char keySize);
void CBInitAssociativeArray(CBAssociativeArray * self, unsigned char keySize, unsigned char dataSize);

CBFindResult CBAssociativeArrayFind(CBAssociativeArray * self, unsigned char * key){
    CBFindResult result;
    CBBTreeNode * node = self->root;
    for (;;) {
        result = CBBTreeNodeBinarySearch(node, key, self->keySize);
        if (result.found){
            result.node = node;
            return result;
        }else{
            if (node->children[result.pos])
                node = node->children[result.pos];
            else{
                result.node = node;
                return result;
            }
        }
    }
}
void CBAssociativeArrayInsert(CBAssociativeArray * self, unsigned char * key, void * data, CBFindResult pos, CBBTreeNode * right){
    // See if we can insert data in this node
    unsigned char * keys = (unsigned char *)(pos.node + 1);
    unsigned char * dataElements = keys + self->keySize * CB_BTREE_ORDER;
    if (pos.node->numElements < CB_BTREE_ORDER) {
        if (pos.node->numElements > pos.pos){
            memmove(keys + (pos.pos + 1) * self->keySize, keys + pos.pos * self->keySize, (pos.node->numElements - pos.pos) * self->keySize);
            memmove(dataElements + (pos.pos + 1) * self->dataSize, dataElements + pos.pos * self->dataSize, (pos.node->numElements - pos.pos) * self->dataSize);
            memmove(pos.node->children + pos.pos + 2, pos.node->children + pos.pos + 1, (pos.node->numElements - pos.pos) *  sizeof(*pos.node->children));
        }
        memcpy(keys + pos.pos * self->keySize, key, self->keySize);
        memcpy(dataElements + pos.pos * self->dataSize, data, self->dataSize);
        pos.node->children[pos.pos + 1] = right;
        pos.node->numElements++;
    }else{
        CBBTreeNode * new = malloc(self->nodeSize);
        unsigned char * newKeys = (unsigned char *)(new + 1);
        unsigned char * newData = newKeys + self->keySize * CB_BTREE_ORDER;
        new->numElements = CB_BTREE_HALF_ORDER;
        pos.node->numElements = CB_BTREE_HALF_ORDER;
        unsigned char * midKey;
        unsigned char * midVal;
        if (pos.pos >= CB_BTREE_HALF_ORDER) {
            if (pos.pos == CB_BTREE_HALF_ORDER) {
                memcpy(newKeys, keys + CB_BTREE_HALF_ORDER * self->keySize, CB_BTREE_HALF_ORDER * self->keySize);
                memcpy(newData, dataElements + CB_BTREE_HALF_ORDER * self->dataSize, CB_BTREE_HALF_ORDER * self->dataSize);
                memcpy(new->children + 1, pos.node->children + CB_BTREE_HALF_ORDER + 1, CB_BTREE_HALF_ORDER * sizeof(*new->children));
                new->children[0] = right;
                midKey = key;
                midVal = data;
            }else{
                if (pos.pos > CB_BTREE_HALF_ORDER + 1){
                    memcpy(newKeys, keys + (CB_BTREE_HALF_ORDER + 1) * self->keySize, (pos.pos - CB_BTREE_HALF_ORDER - 1) * self->keySize);
                    memcpy(newData, dataElements + (CB_BTREE_HALF_ORDER + 1) * self->dataSize, (pos.pos - CB_BTREE_HALF_ORDER - 1)  * self->dataSize);
                }
                memcpy(newKeys + (pos.pos - CB_BTREE_HALF_ORDER - 1) * self->keySize, key, self->keySize);
                memcpy(newData + (pos.pos - CB_BTREE_HALF_ORDER - 1) * self->dataSize, data, self->dataSize);
                memcpy(newKeys + (pos.pos - CB_BTREE_HALF_ORDER) * self->keySize, keys + pos.pos * self->keySize, (CB_BTREE_ORDER - pos.pos) * self->keySize);
                memcpy(newData + (pos.pos - CB_BTREE_HALF_ORDER) * self->dataSize, dataElements + pos.pos * self->dataSize, (CB_BTREE_ORDER - pos.pos) * self->dataSize); // o 0 i 1 ii 2 iii 3 iv
                memcpy(new->children, pos.node->children + CB_BTREE_HALF_ORDER + 1, (pos.pos - CB_BTREE_HALF_ORDER) * sizeof(*new->children));
                new->children[pos.pos - CB_BTREE_HALF_ORDER] = right;
                if (CB_BTREE_ORDER > pos.pos)
                    memcpy(new->children + pos.pos - CB_BTREE_HALF_ORDER + 1, pos.node->children + pos.pos + 1, (CB_BTREE_ORDER - pos.pos) * sizeof(*new->children));
                midKey = keys + CB_BTREE_HALF_ORDER * self->keySize;
                midVal = dataElements + CB_BTREE_HALF_ORDER * self->dataSize;
            }
        }else{
            memcpy(newKeys, keys + CB_BTREE_HALF_ORDER * self->keySize, CB_BTREE_HALF_ORDER * self->keySize);
            memcpy(newData, dataElements + CB_BTREE_HALF_ORDER * self->dataSize, CB_BTREE_HALF_ORDER * self->dataSize);
            memcpy(new->children, pos.node->children + CB_BTREE_HALF_ORDER, (CB_BTREE_HALF_ORDER + 1) * sizeof(*new->children));
            memmove(keys + (pos.pos + 1) * self->keySize, keys + pos.pos * self->keySize, (CB_BTREE_HALF_ORDER - pos.pos) * self->keySize);
            memmove(dataElements + (pos.pos + 1) * self->dataSize, dataElements + pos.pos * self->dataSize, (CB_BTREE_HALF_ORDER - pos.pos) * self->dataSize);
            if (CB_BTREE_HALF_ORDER > 1 + pos.pos)
                memmove(pos.node->children + pos.pos + 2, pos.node->children + pos.pos + 1, (CB_BTREE_HALF_ORDER - pos.pos - 1) * self->dataSize);
            memcpy(keys + pos.pos * self->keySize, key, self->keySize);
            memcpy(dataElements + pos.pos * self->dataSize, data, self->dataSize);
            pos.node->children[pos.pos + 1] = right;
            midKey = keys + CB_BTREE_HALF_ORDER * self->keySize;
            midVal = dataElements + CB_BTREE_HALF_ORDER * self->dataSize;
        }
        if ( ! pos.node->parent) {
            self->root = malloc(self->nodeSize);
            self->root->numElements = 0;
            self->root->parent = NULL;
            pos.node->parent = self->root;
            self->root->children[0] = pos.node;
        }
        new->parent = pos.node->parent;
        CBFindResult res = CBBTreeNodeBinarySearch(pos.node->parent, midKey, self->keySize);
        res.node = pos.node->parent;
        return CBAssociativeArrayInsert(self, midKey, midVal, res, new);
    }
}
CBFindResult CBBTreeNodeBinarySearch(CBBTreeNode * self, unsigned char * key, unsigned char keySize){
    CBFindResult res;
    res.found = 0;
    if ( ! self->numElements) {
        res.pos = 0;
        return res;
    }
    unsigned char left = 0;
    unsigned char right = self->numElements - 1;
    unsigned char * keys = (unsigned char *)(self + 1);
    int cmp;
    while (left <= right) {
        res.pos = (right+left)/2;
        cmp = memcmp(key, keys + res.pos * keySize, keySize);
        if (cmp == 0) {
            res.found = 1;
            break;
        }else if (cmp < 0){
            if ( ! res.pos)
                break;
            right = res.pos - 1;
        }else
            left = res.pos + 1;
    }
    if (cmp > 0)
        res.pos++;
    return res;
}
void CBInitAssociativeArray(CBAssociativeArray * self, unsigned char keySize, unsigned char dataSize){
    self->keySize = keySize;
    self->dataSize = dataSize;
    self->nodeSize = sizeof(*self->root) + (keySize + dataSize) * CB_BTREE_ORDER;
    self->root = malloc(self->nodeSize);
    self->root->parent = NULL;
    self->root->numElements = 0;
    for (unsigned char x = 0; x < CB_BTREE_ORDER + 1; x++)
        self->root->children[x] = NULL;
}

int main(){
    srand(1);
    CBAssociativeArray array;
    CBInitAssociativeArray(&array, 10, 10);
    int size = CB_BTREE_ORDER * (CB_BTREE_ORDER + 2) * 10;;
    unsigned char * keys = malloc(size);
    for (int x = 0; x < size; x++) {
        keys[x] = rand();
    }
    for (int x = 0; x < size; x += 10) {
        CBAssociativeArrayInsert(&array, keys + x, keys + x, CBAssociativeArrayFind(&array, keys + x), NULL);
        for (int y = 0; y <= x; y += 10) {
            if ( ! CBAssociativeArrayFind(&array, keys + y).found) {
                printf("RANDOM FIND FAIL %u - %u\n", y, x);
                return 1;
            }
        }
    }
    return 0;
}

ありがとう。

4

1 に答える 1

1

問題は memcpy または memmove 操作とは関係ありません。ノードを分割するときに、親ポインターを変更するのを忘れていました。

ノードが分割された後にこれを追加すると、機能します。

if (new->children[0])
    for (unsigned char x = 0; x < CB_BTREE_HALF_ORDER + 1; x++) {
        CBBTreeNode * child = new->children[x];
        child->parent = new;
    }

これを追加するのを忘れたのは非常に愚かでした。アルゴリズムは、多くのランダムな挿入で機能するようになりました。

于 2012-11-19T22:38:21.343 に答える