diff --git a/src/sys/ubixfsv2/btree.cpp b/src/sys/ubixfsv2/btree.cpp index 61b6328..4b37f7d 100644 --- a/src/sys/ubixfsv2/btree.cpp +++ b/src/sys/ubixfsv2/btree.cpp @@ -1,6 +1,7 @@ // http://www.cs.msstate.edu/~cs2314/global/BTreeAnimation/algorithm.html #include #include +#include #include #include "btree.h" #include "inode.h" @@ -8,8 +9,6 @@ using namespace std; -static int ubuCount = 0x0; - bTree::bTree(ubixfsInode * inode) : root(NULL) { if (inode == NULL) return; root = allocEmptyNode(); @@ -39,31 +38,25 @@ unsigned int curSlot = 0; bool foo = Verify(); - printf("UBU ubuCount: [0x%X]\n",++ubuCount); - if (bnode == NULL || inode == NULL) return false; tmpInode = Find(inode->name); - if (tmpInode != NULL) cout << tmpInode->name << " " << inode->name << endl; + if (tmpInode != NULL) return false; /* * Find the leaf node the inode goes into */ assert(bnode->used); -// cout << "---Inserting " << inode->name << "@" << inode << endl; +// cout << "---Inserting " << inode->name << "@" << inode << endl; while (bnode != NULL && !bnode->leafNode) { if (strcmp(inode->name, bnode->keys[0]) < 0) { - printf("UBU 1 inode->name: [%s], bnode->keys[%i]: [%s]\n",inode->name,0,bnode->keys[0]); bnode = (bNode *)bnode->childHead[0]; - printf("UBU 1-1 inode->name: [%s], bnode->keys[%i]: [%s]\n",inode->name,0,bnode->keys[0]); } else { if (strcmp(inode->name, bnode->keys[bnode->used-1]) >= 0) { - printf("UBU 2 inode->name: [%s], bnode->keys[%i]: [%s]\n",inode->name,bnode->used-1,bnode->keys[bnode->used-1]); bnode = (bNode *)bnode->childHead[bnode->used]; } else { for (unsigned int i = 1; i < bnode->used; i++) { if (strcmp(inode->name, bnode->keys[i]) < 0) { - printf("UBU 3 inode->name: [%s], bnode->keys[%i]: [%s]\n",inode->name,i,bnode->keys[i]); bnode = (bNode *)bnode->childHead[i]; break; } // if @@ -75,12 +68,13 @@ /* * */ -printf("UBU bnode->keys[0]: [%s],bnode->keys[bnode->used-1]: [%s],bnode->keys[bnode->used]: [%s]\n",bnode->keys[0],bnode->keys[bnode->used-1],bnode->keys[bnode->used]); assert(bnode); if (bnode->leafNode != true) cout << "leafnode!=true" << endl; assert(inode); + if (foo != Verify()) cout << "verify 0 failed" << endl; + if (strcmp(inode->name, bnode->keys[curSlot = 0]) < 0) tmpInode = (ubixfsInode *)bnode->childHead[curSlot]; else @@ -95,7 +89,7 @@ } // for curSlot tmpInode = (ubixfsInode *)bnode->childHead[curSlot]; } // else -printf("UBU bnode->keys[curSlot]: [%s:%i]\n",bnode->keys[curSlot],curSlot); +if (strcmp(inode->name, "q") == 0) cout << "futen: " << curSlot << endl; if (foo != Verify()) cout << "verify 1 failed" << endl; if (tmpInode == NULL) { /* @@ -117,21 +111,17 @@ inode->next = inode->prev = NULL; } // else -if (foo != Verify()) cout << "verify 3 failed" << endl; } else { ++bnode->used; } // else -if (foo != Verify()) cout << "verify 7 failed" << endl; } else { /* * Add node to leaf page. Scan through to find where it goes. */ -if (foo != Verify()) cout << "verify 4 failed" << endl; - if (strcmp(inode->name, ((ubixfsInode *)bnode->childHead[curSlot])->name) < 0) { -if (foo != Verify()) cout << "verify 4a failed" << endl; + inode->next = (ubixfsInode *)bnode->childHead[curSlot]; inode->prev = inode->next->prev; inode->next->prev = inode; @@ -139,41 +129,21 @@ bnode->childHead[curSlot] = (void *)inode; if (foo != Verify()) cout << "verify 4b failed" << endl; } else { + if (foo != Verify()) cout << "verify 4c failed" << endl; if (strcmp(inode->name, ((ubixfsInode *)bnode->childTail[curSlot])->name) > 0) { -if (foo != Verify()) { - cout << "verify 4d failed" << endl; - Info(bnode); -} - cout << "node->CT[curSlot]->name == " << ((ubixfsInode *)bnode->childTail[curSlot])->name << endl; - ubixfsInode * tmp = (ubixfsInode *)bnode->childTail[curSlot]; - if (tmp != NULL && tmp->next != NULL) cout << "next->name: " << tmp->next->name << endl; - if (inode != NULL) - printf("UBU inode->name: [%s]\n",inode->name); inode->prev = (ubixfsInode *)bnode->childTail[curSlot]; inode->next = inode->prev->next; inode->prev->next = inode; - if (inode->next != NULL) - printf("UBU inode->next->name: [%s]\n",inode->next->name); - if (inode->prev != NULL) - printf("UBU inode->prev->name: [%s]\n",inode->prev->name); - if (inode->next != NULL) inode->next->prev = inode; bnode->childTail[curSlot] = inode; -if (foo != Verify()) { - Info(bnode); - cout << "verify 4e failed" << endl; - cout << "was inserting " << inode->name << " at end of list" << endl; -} } else { ubixfsInode * tmpInode = (ubixfsInode *)bnode->childHead[curSlot]; - for (unsigned int i = 1; i <= bnode->childCount[curSlot]; i++) { -// cout << "strcmp(" << inode->name << ", " << tmpInode->name << ") == " << -// strcmp(inode->name, tmpInode->name) << endl; + for (unsigned int i = 0; i < bnode->childCount[curSlot]; i++) { if (strcmp(inode->name, tmpInode->name) < 0) { inode->next = tmpInode; inode->prev = tmpInode->prev; @@ -183,25 +153,18 @@ } // if tmpInode = tmpInode->next; } // for i - -if (foo != Verify()) cout << "verify 5 failed" << endl; } // else -if (foo != Verify()) cout << "verify 5a failed" << endl; } // else -if (foo != Verify()) cout << "verify 5b failed" << endl; } // else -if (foo != Verify()) cout << "verify 6 failed" << endl; if (++bnode->childCount[curSlot] == B_MAX_CHILD_COUNT) { -// cout << "---- before split ----" << endl; -// cout << "slot[" << curSlot << "] is full" << endl; -// cout << "slot[" << curSlot+1 << "]->childCount is: " << bnode->childCount[curSlot+1] << endl; - // Info(); -if (foo != Verify()) cout << "verify 8 failed" << endl; +// cout << "---- before split ----" << endl; +// Info(bnode); + if (curSlot != bnode->used) { int shift = bnode->used - curSlot +1; -// cout << "shift: " << shift << endl; + memmove(&bnode->childHead[curSlot+1], &bnode->childHead[curSlot], sizeof(bnode->childHead[0]) * shift); @@ -237,15 +200,10 @@ 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; -if (foo != Verify()) cout << "verify failed" << endl; - if (++bnode->used == B_MAX_KEYS) splitNode(bnode); -if (foo != Verify()) cout << "verify 2 failed" << endl; -// cout << "--- After split ---" << endl; -// Info(); + if (++bnode->used == B_MAX_KEYS) splitNode(bnode); + } // if leaf is full return true; @@ -253,7 +211,6 @@ void bTree::splitNode(bNode * oldNode) { -// cout << "---in splitNode()---" << endl; assert(oldNode); if (oldNode == NULL) return; if (oldNode->used != B_MAX_KEYS) return; @@ -264,7 +221,6 @@ unsigned int splitLoc = (B_MAX_KEYS+1) >> 1; unsigned int shift = B_MAX_KEYS - splitLoc; -// cout << "splitLoc: " << splitLoc << " shift: " << shift << endl; newNode->used = shift; newNode->parent = oldNode->parent; newNode->leafNode = oldNode->leafNode; @@ -315,20 +271,13 @@ root->used = 1; root->leafNode = false; root->present[0] = root->present[1] = true; - root->childCount[0] = oldNode->used; - root->childCount[1] = newNode->used; -//cout << "---root node begin---" << endl; -// Info(); -//cout << "---root node end---" << endl; + root->childCount[0] = root->childCount[1] = 0; +// root->childCount[0] = oldNode->used; +// root->childCount[1] = newNode->used; } else { insertNode(oldNode->parent, newNode->keys[0], newNode, NULL); if (oldNode->parent->used == B_MAX_KEYS) splitNode(oldNode->parent); } // else -// cout << "---oldNode begin---" << endl; -// Info(oldNode); -// cout << "---oldNode end---" << endl; -// cout << "---newNode---" << endl; -// Info(newNode); return; } // bTree::splitNode @@ -337,7 +286,7 @@ void * headPtr, void * tailPtr) { unsigned int curSlot = 0; if (node == NULL || key == NULL) return; - printf("UBU SPLIT!!!!\n"); + //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); @@ -404,11 +353,24 @@ ubixfsInode * inode = NULL; if (node == NULL) return; + for (unsigned int i = 0; i <= node->used; i++) { + inode = (ubixfsInode *)node->childHead[i]; + cout << "{" << node->childCount[i] << "} "; + for (unsigned int k = 0; k < node->childCount[i]; k++) { + cout << "(" << inode->name << ") "; + inode = inode->next; + } // for k + if (i != node->used) cout << "[" << node->keys[i] << "] "; + } // for i + cout << endl; + return; +#if 0 for (unsigned int i = 0; i < node->used; i++) { cout << "keys[" << i << "]: " << node->keys[i] << " "; } // for i cout << endl; cout << "node->used: " << node->used << endl; + cout << "leafNode: " << node->leafNode << endl; for (unsigned int i = 0; i <= node->used; i++) { inode = (ubixfsInode *)node->childHead[i]; cout << "node->childCount["<childCount[i] << endl; @@ -418,6 +380,7 @@ inode = inode->next; } // for j } // for i +#endif } // bTree::Info void diff --git a/src/sys/ubixfsv2/main.cpp b/src/sys/ubixfsv2/main.cpp index ea45c31..aa9a991 100644 --- a/src/sys/ubixfsv2/main.cpp +++ b/src/sys/ubixfsv2/main.cpp @@ -22,8 +22,8 @@ inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); if (inode == NULL) break; memset(inode, 0, sizeof(ubixfsInode)); -// for (int k = 0; k < (random() % 100)+5; k++) { - for (int k = 0; k < 1; k++) { + for (int k = 0; k < (random() % 100)+5; k++) { +// for (int k = 0; k < 1; k++) { inode->name[k] = (char)((random() % 26)+'a'); } // for k if (!tree->Insert(inode)) cout << "Insert() failed" << endl; @@ -129,7 +129,7 @@ strcpy(inode->name, "n"); cout << "---Inserting " << inode->name << "---" << endl; tree->Insert(inode); - +#endif i = 0; ubixfsInode * tmpInode = tmpInode = tree->GetFirstNode(); @@ -139,7 +139,7 @@ cout << tmpInode->name << endl; tmpInode = tmpInode->next; } // while -#endif + // cout << sizeof(struct bNode) << endl; // tree->Info();