diff --git a/src/sys/ubixfsv2/btree.cpp b/src/sys/ubixfsv2/btree.cpp index 6228c86..df5e73f 100644 --- a/src/sys/ubixfsv2/btree.cpp +++ b/src/sys/ubixfsv2/btree.cpp @@ -35,7 +35,8 @@ bNode * bnode = root; ubixfsInode * tmpInode = NULL; unsigned int curSlot = 0; - + bool foo = Verify(); + if (bnode == NULL || inode == NULL) return false; tmpInode = Find(inode->name); if (tmpInode != NULL) cout << tmpInode->name << " " << inode->name << endl; @@ -66,7 +67,7 @@ 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 @@ -82,12 +83,14 @@ tmpInode = (ubixfsInode *)bnode->childHead[curSlot]; } // else +if (foo != Verify()) cout << "verify 1 failed" << endl; 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; if (curSlot == 0) { @@ -100,31 +103,40 @@ } else { 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; if (inode->prev != NULL) inode->prev->next = inode; bnode->childHead[curSlot] = (void *)inode; - } else +if (foo != Verify()) cout << "verify 4b failed" << endl; + } else { if (strcmp(inode->name, ((ubixfsInode *)bnode->childTail[curSlot])->name) > 0) { +if (foo != Verify()) cout << "verify 4c failed" << endl; 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; + +if (foo != Verify()) cout << "verify 4d failed" << endl; } else { + ubixfsInode * tmpInode = (ubixfsInode *)bnode->childHead[curSlot]; for (unsigned int i = 1; i <= bnode->childCount[curSlot]; i++) { // cout << "strcmp(" << inode->name << ", " << tmpInode->name << ") == " << @@ -138,14 +150,22 @@ } // 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; if (curSlot != bnode->used) { int shift = bnode->used - curSlot +1; // cout << "shift: " << shift << endl; @@ -187,7 +207,10 @@ // 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 leaf is full @@ -501,3 +524,18 @@ if (key == NULL) return false; return true; } // bTree::Delete + +bool +bTree::Verify(void) { + ubixfsInode * node = GetFirstNode(); + if (node == NULL) return true; + + while (node != NULL) { + if (node->next != NULL) { +// cout << node->name << "::" << node->next->name << ":::" << strcmp(node->name, node->next->name) << endl; + if (strcmp(node->name, node->next->name) > 0) return false; + } + node = node->next; + } // while + return true; +} // bTree::Verify diff --git a/src/sys/ubixfsv2/btree.h b/src/sys/ubixfsv2/btree.h index 2348991..0f65665 100644 --- a/src/sys/ubixfsv2/btree.h +++ b/src/sys/ubixfsv2/btree.h @@ -44,6 +44,7 @@ bool Save(const char *); bool Load(const char *); void Print(void); + bool Verify(void); ~bTree(void) { }; }; // bTree #endif // !BTREE_H diff --git a/src/sys/ubixfsv2/main.cpp b/src/sys/ubixfsv2/main.cpp index 8ab20c4..9001135 100644 --- a/src/sys/ubixfsv2/main.cpp +++ b/src/sys/ubixfsv2/main.cpp @@ -88,7 +88,7 @@ strcpy(inode->name, "n"); cout << "---Inserting " << inode->name << "---" << endl; tree->Insert(inode); -#endif + i = 0; ubixfsInode * tmpInode = tmpInode = tree->GetFirstNode(); @@ -98,7 +98,7 @@ cout << tmpInode->name << endl; tmpInode = tmpInode->next; } // while - +#endif // cout << sizeof(struct bNode) << endl; // tree->Info();