diff --git a/src/sys/ubixfsv2/btree.cpp b/src/sys/ubixfsv2/btree.cpp index 4b37f7d..4574449 100644 --- a/src/sys/ubixfsv2/btree.cpp +++ b/src/sys/ubixfsv2/btree.cpp @@ -8,8 +8,12 @@ #include "assert.h" using namespace std; +#define VERIFY(x, y, z, n) if ((x) != (y)) { cout << "verify " << z << " failed" << endl; Info(n); } bTree::bTree(ubixfsInode * inode) : root(NULL) { + treeDepth = 1; + treeWidth = 0; + treeLeafCount = 0; if (inode == NULL) return; root = allocEmptyNode(); if (root == NULL) return; @@ -41,6 +45,9 @@ if (bnode == NULL || inode == NULL) return false; tmpInode = Find(inode->name); if (tmpInode != NULL) return false; +cout << "Insert(" << inode->name << ");" << endl; +//Info(bnode); + ++treeLeafCount; /* * Find the leaf node the inode goes into */ @@ -73,7 +80,7 @@ if (bnode->leafNode != true) cout << "leafnode!=true" << endl; assert(inode); -if (foo != Verify()) cout << "verify 0 failed" << endl; +VERIFY(foo, Verify(), 0, bnode); if (strcmp(inode->name, bnode->keys[curSlot = 0]) < 0) tmpInode = (ubixfsInode *)bnode->childHead[curSlot]; @@ -89,16 +96,17 @@ } // for curSlot tmpInode = (ubixfsInode *)bnode->childHead[curSlot]; } // else -if (strcmp(inode->name, "q") == 0) cout << "futen: " << curSlot << endl; -if (foo != Verify()) cout << "verify 1 failed" << endl; + +VERIFY(foo, Verify(), 1, bnode); + if (tmpInode == NULL) { /* * This is the first node in this leaf */ bnode->childHead[curSlot] = bnode->childTail[curSlot] = inode; bnode->present[curSlot] = true; -if (foo != Verify()) cout << "verify 2 failed" << endl; +VERIFY(foo, Verify(), 2, bnode); if (curSlot == 0) { if (bnode->childHead[1] != NULL) { @@ -111,6 +119,8 @@ inode->next = inode->prev = NULL; } // else +VERIFY(foo, Verify(), 3, bnode); + } else { ++bnode->used; } // else @@ -119,29 +129,36 @@ /* * Add node to leaf page. Scan through to find where it goes. */ +VERIFY(foo, Verify(), 4, bnode); if (strcmp(inode->name, ((ubixfsInode *)bnode->childHead[curSlot])->name) < 0) { +VERIFY(foo, Verify(), 5, bnode); inode->next = (ubixfsInode *)bnode->childHead[curSlot]; inode->prev = inode->next->prev; inode->next->prev = inode; if (inode->prev != NULL) inode->prev->next = inode; bnode->childHead[curSlot] = (void *)inode; -if (foo != Verify()) cout << "verify 4b failed" << endl; +VERIFY(foo, Verify(), 6, bnode); + } else { -if (foo != Verify()) cout << "verify 4c failed" << endl; +VERIFY(foo, Verify(), 7, bnode); if (strcmp(inode->name, ((ubixfsInode *)bnode->childTail[curSlot])->name) > 0) { +VERIFY(foo, Verify(), 8, bnode); inode->prev = (ubixfsInode *)bnode->childTail[curSlot]; inode->next = inode->prev->next; inode->prev->next = inode; if (inode->next != NULL) inode->next->prev = inode; bnode->childTail[curSlot] = inode; +VERIFY(foo, Verify(), 9, bnode); } else { +VERIFY(foo, Verify(), 10, bnode); + ubixfsInode * tmpInode = (ubixfsInode *)bnode->childHead[curSlot]; for (unsigned int i = 0; i < bnode->childCount[curSlot]; i++) { if (strcmp(inode->name, tmpInode->name) < 0) { @@ -153,10 +170,15 @@ } // if tmpInode = tmpInode->next; } // for i +VERIFY(foo, Verify(), 11, bnode); } // else +VERIFY(foo, Verify(), 12, bnode); } // else +VERIFY(foo, Verify(), 13, bnode); } // else +VERIFY(foo, Verify(), 14, bnode); + if (++bnode->childCount[curSlot] == B_MAX_CHILD_COUNT) { // cout << "---- before split ----" << endl; @@ -201,16 +223,17 @@ bnode->childCount[curSlot] = (B_MAX_CHILD_COUNT+1) >> 1; bnode->childCount[curSlot+1] -= bnode->childCount[curSlot]; bnode->present[curSlot] = true; - + ++treeWidth; if (++bnode->used == B_MAX_KEYS) splitNode(bnode); } // if leaf is full - +// Info(bnode); return true; } // bTree::Insert void bTree::splitNode(bNode * oldNode) { + ubixfsInode * tmpInode = NULL; assert(oldNode); if (oldNode == NULL) return; if (oldNode->used != B_MAX_KEYS) return; @@ -259,12 +282,17 @@ memset(&oldNode->childCount[splitLoc], 0, sizeof(newNode->childCount[0]) * (shift+1)); + tmpInode = GetFirstNode(newNode); + assert(tmpInode); + if (oldNode == root) { // allocate a new root node + ++treeDepth; root = allocEmptyNode(); oldNode->parent = root; newNode->parent = root; - strncpy(root->keys[0], newNode->keys[0], B_MAX_NAME_LENGTH); + // strncpy(root->keys[0], newNode->keys[0], B_MAX_NAME_LENGTH); + strncpy(root->keys[0], tmpInode->name, B_MAX_NAME_LENGTH); root->childHead[0] = oldNode; root->childTail[0] = root->childTail[1] = NULL; root->childHead[1] = newNode; @@ -274,9 +302,18 @@ root->childCount[0] = root->childCount[1] = 0; // root->childCount[0] = oldNode->used; // root->childCount[1] = newNode->used; +cout << "parent" << endl; +Info(newNode->parent); +cout << "oldNode" << endl; +Info(oldNode); +cout << "-----" << endl; +cout << "newNode" << endl; +Info(newNode); +cout << "-----" << endl; + } else { - insertNode(oldNode->parent, newNode->keys[0], newNode, NULL); - if (oldNode->parent->used == B_MAX_KEYS) splitNode(oldNode->parent); + insertNode(oldNode->parent, tmpInode->name, newNode, NULL); + // if (oldNode->parent->used == B_MAX_KEYS) splitNode(oldNode->parent); } // else return; } // bTree::splitNode @@ -286,7 +323,7 @@ void * headPtr, void * tailPtr) { unsigned int curSlot = 0; if (node == NULL || key == NULL) return; - //printf("UBU SPLIT!!!!\n"); + if (strcmp(key, node->keys[node->used-1]) >= 0){ curSlot = node->used; memset(node->keys[curSlot], 0, B_MAX_NAME_LENGTH); @@ -294,7 +331,7 @@ node->childHead[curSlot+1] = headPtr; node->childTail[curSlot+1] = tailPtr; node->present[curSlot+1] = true; -// node->childCount[node->used] = ?; + node->childCount[node->used] = 0; // maybe? } else { @@ -333,7 +370,7 @@ node->present[curSlot+1] = true; // node->childCount[node->used] = ?; } // else - ++node->used; + if (++node->used == B_MAX_KEYS) splitNode(node); return; } // bTree::insertNode @@ -488,10 +525,15 @@ return NULL; } // bTree::treeSearch -ubixfsInode * +ubixfsInode * bTree::GetFirstNode(void) { + return GetFirstNode(root); +} // bTree::GetFirstNode - bNode * tmpNode = root; +ubixfsInode * +bTree::GetFirstNode(bNode * node) { + + bNode * tmpNode = node; if (tmpNode == NULL) return NULL; while (!tmpNode->leafNode) { for (unsigned int i = 0; i < tmpNode->used; i++) { @@ -504,7 +546,7 @@ for (unsigned int i = 0; i < tmpNode->used; i++) { if (tmpNode->childHead[i] != NULL) return (ubixfsInode * )tmpNode->childHead[i]; - } + } // for i return NULL; } // bTree::GetFirstNode @@ -541,3 +583,9 @@ } // while return true; } // bTree::Verify + +bTree::~bTree(void) { + cout << "tree depth: " << treeDepth << endl; + cout << "tree width: " << treeWidth << endl; + cout << "tree leaf count: " << treeLeafCount << endl; +} // bTree::~bTree diff --git a/src/sys/ubixfsv2/btree.h b/src/sys/ubixfsv2/btree.h index 0f65665..ca49612 100644 --- a/src/sys/ubixfsv2/btree.h +++ b/src/sys/ubixfsv2/btree.h @@ -27,6 +27,9 @@ class bTree { protected: bNode * root; + uInt32 treeDepth; + uInt32 treeWidth; + uInt32 treeLeafCount; ubixfsInode * treeSearch(bNode *, const char *); ubixfsInode * inodeSearch(ubixfsInode *, const char *); void splitNode(bNode *); @@ -34,9 +37,10 @@ void insertNode(bNode *, const char *, void *, void *); public: bTree(ubixfsInode *); - bTree(void) : root(NULL) { }; + bTree(void) : root(NULL), treeDepth(0) { }; ubixfsInode * Find(const char *); ubixfsInode * GetFirstNode(void); + ubixfsInode * GetFirstNode(bNode *); bool Delete(const char *); void Info(void); void Info(const bNode *); @@ -45,6 +49,6 @@ bool Load(const char *); void Print(void); bool Verify(void); - ~bTree(void) { }; + ~bTree(void); }; // bTree #endif // !BTREE_H diff --git a/src/sys/ubixfsv2/main.cpp b/src/sys/ubixfsv2/main.cpp index aa9a991..42a1232 100644 --- a/src/sys/ubixfsv2/main.cpp +++ b/src/sys/ubixfsv2/main.cpp @@ -17,16 +17,18 @@ strcpy(inode -> name, "temp123"); bTree * tree = new bTree(inode); - for (i = 0; i < 2000; i++) { - // if (i%1000 == 0) cout << "-_- i = "<Verify()) { +// if (i%1000 == 0) cout << "-_- i = "<name[k] = (char)((random() % 26)+'a'); } // for k if (!tree->Insert(inode)) cout << "Insert() failed" << endl; + ++i; } // for i // cout << "i made it to: " << i << endl; @@ -144,5 +146,6 @@ // tree->Info(); free(inode); + delete tree; return 0; }