diff --git a/src/sys/ubixfsv2/btree.cpp b/src/sys/ubixfsv2/btree.cpp index 71e03fd..3f7344e 100644 --- a/src/sys/ubixfsv2/btree.cpp +++ b/src/sys/ubixfsv2/btree.cpp @@ -61,16 +61,13 @@ /* * */ -cout << "--used: " << bnode->used << endl; if (strcmp(inode->name, bnode->keys[curSlot = 0]) < 0) tmpInode = (ubixfsInode *)bnode->childHead[curSlot]; else - if (strcmp(inode->name, bnode->keys[(curSlot = bnode->used)-1]) >= 0) + if (strcmp(inode->name, bnode->keys[curSlot = bnode->used]) >= 0) tmpInode = (ubixfsInode *)bnode->childHead[bnode->used]; else { -cout << "used: " << bnode->used << endl; for (curSlot = 1; curSlot < bnode->used; curSlot++) { -cout << inode->name << " ~~ " << bnode->keys[curSlot] << endl; if (strcmp(inode->name, bnode->keys[curSlot]) < 0) { tmpInode = (ubixfsInode *)bnode->childHead[curSlot]; break; @@ -123,7 +120,7 @@ bnode->childTail[curSlot] = inode; } else { ubixfsInode * tmpInode = (ubixfsInode *)bnode->childHead[curSlot]; - for (unsigned int i = 1; i < bnode->childCount[curSlot]; i++) { + for (unsigned int i = 1; i <= bnode->childCount[curSlot]; i++) { // cout << "strcmp(" << inode->name << ", " << tmpInode->name << ") == " << // strcmp(inode->name, tmpInode->name) << endl; if (strcmp(inode->name, tmpInode->name) < 0) { @@ -139,10 +136,10 @@ } // else if (++bnode->childCount[curSlot] == B_MAX_CHILD_COUNT) { - cout << "slot[" << curSlot << "] is full" << endl; - cout << "slot[" << curSlot+1 << "]->childCount is: " << bnode->childCount[curSlot+1] << endl; cout << "---- before split ----" << endl; - Info(); +cout << "slot[" << curSlot << "] is full" << endl; +cout << "slot[" << curSlot+1 << "]->childCount is: " << bnode->childCount[curSlot+1] << endl; + // Info(); if (curSlot != bnode->used) { int shift = bnode->used - curSlot +1; cout << "shift: " << shift << endl; @@ -181,10 +178,12 @@ bnode->childTail[curSlot] = (void *)tmpInode->prev; bnode->childCount[curSlot] = (B_MAX_CHILD_COUNT+1) >> 1; bnode->childCount[curSlot+1] -= bnode->childCount[curSlot]; +cout << "childCount[" << curSlot << "] : " << bnode->childCount[curSlot] << endl; +cout << "childCount[" << curSlot+1 << "] : " << bnode->childCount[curSlot+1] << endl; bnode->present[curSlot] = true; ++bnode->used; cout << "--- After split ---" << endl; -Info(); +// Info(); } // if leaf is full return true; @@ -200,7 +199,7 @@ if (newNode == NULL) return; unsigned int splitLoc = (B_MAX_KEYS+1) >> 1; - unsigned int shift = B_MAX_KEYS - splitLoc; + unsigned int shift = B_MAX_KEYS - splitLoc+1; newNode->used = (B_MAX_KEYS+1) >> 1; newNode->parent = oldNode->parent; @@ -208,9 +207,9 @@ memcpy(&newNode->keys[0], &oldNode->keys[splitLoc], - sizeof(newNode->keys[0]) * shift); + sizeof(newNode->keys[0]) * (shift+1)); - memset(&oldNode->keys[splitLoc], 0, sizeof(newNode->keys[0]) * shift); + memset(&oldNode->keys[splitLoc], 0, sizeof(newNode->keys[0]) * (shift+1)); memcpy(&newNode->present[0], &oldNode->present[splitLoc], @@ -252,7 +251,7 @@ root->childCount[1] = newNode->used; } else { if (++oldNode->parent->used == B_MAX_KEYS) splitNode(oldNode->parent); - } // esle + } // else return; } // bTree::splitNode @@ -347,18 +346,24 @@ ubixfsInode * bTree::GetFirstNode(void) { +cout << "In GetFirstNode" << endl; bNode * tmpNode = root; if (tmpNode == NULL) return NULL; - - if (root->leafNode) { - if (root->used == 0) return NULL; - if (root->used == 1 && root->childHead[0] == NULL) - return (ubixfsInode *) root->childHead[1]; - else - return (ubixfsInode *) root->childHead[0]; - } // if - while (!tmpNode->leafNode) tmpNode = (bNode *)tmpNode->childHead[0]; - return (ubixfsInode *)tmpNode->childHead[0]; + while (!tmpNode->leafNode) { + for (unsigned int i = 0; i < tmpNode->used; i++) { + if (tmpNode->childHead[i] != NULL) { + tmpNode = (bNode *)tmpNode->childHead[i]; + break; + } // if + } // for i + } // while +cout << "tmpNode->leafNode: " << tmpNode->leafNode << endl; +cout << "tmpNode->childHead[0]->name: " << ((ubixfsInode *)tmpNode->childHead[0])->name << endl; + + for (unsigned int i = 0; i < tmpNode->used; i++) { + if (tmpNode->childHead[i] != NULL) return (ubixfsInode * )tmpNode->childHead[i]; + } + return NULL; } // bTree::GetFirstNode bool diff --git a/src/sys/ubixfsv2/btree.h b/src/sys/ubixfsv2/btree.h index 00c6e38..f491326 100644 --- a/src/sys/ubixfsv2/btree.h +++ b/src/sys/ubixfsv2/btree.h @@ -7,7 +7,7 @@ #define B_NODE_MAGIC_1 0xDEADBEEF #define B_NODE_MAGIC_2 0x1900BABE -#define B_MAX_KEYS 14 +#define B_MAX_KEYS 4 #define B_MAX_NAME_LENGTH 256 #define B_MAX_CHILD_COUNT 4