메모리 내 B 트리 삽입 구현

Question

읽을 수있는 온라인이 없음 (예 :이 끔찍한 코드 : http://www.freewebs.com/attractivechaos/kbtree.h.html) 때문에 B- 트리의 메모리 내 C 구현을 작성했습니다.

요소를 삽입 할 때 이전에 삽입 된 요소를 찾지 못하기 때문에 제대로 작동하지 않습니다. 또한 일반적인 구현이 매우 훌륭하고 현명한 방법으로 삽입 작업을 수행하는지 잘 모르겠습니다. 누구든지 내가 한 것을 비판하고 왜 항상 작동하지 않는지 알아낼 수 있습니까?

분명히 요소는 각 노드의 메모리에 함께 저장되기 때문에 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; 
} 

감사합니다.

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

이 매우 어리석은이었다 추가 잊어. 알고리즘은 많은 무작위 삽입과 함께 작동합니다.