diff --git a/src/sys/ubixfsv2/btree.cpp b/src/sys/ubixfsv2/btree.cpp index a83ed21..61b6328 100644 --- a/src/sys/ubixfsv2/btree.cpp +++ b/src/sys/ubixfsv2/btree.cpp @@ -8,6 +8,8 @@ using namespace std; +static int ubuCount = 0x0; + bTree::bTree(ubixfsInode * inode) : root(NULL) { if (inode == NULL) return; root = allocEmptyNode(); @@ -37,6 +39,8 @@ 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; @@ -46,24 +50,33 @@ assert(bnode->used); // cout << "---Inserting " << inode->name << "@" << inode << endl; while (bnode != NULL && !bnode->leafNode) { - if (strcmp(inode->name, bnode->keys[0]) < 0) + 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]; - else - if (strcmp(inode->name, bnode->keys[bnode->used-1]) >= 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 } // for i } // else + } } // while /* * */ +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); @@ -82,7 +95,7 @@ } // for curSlot tmpInode = (ubixfsInode *)bnode->childHead[curSlot]; } // else - +printf("UBU bnode->keys[curSlot]: [%s:%i]\n",bnode->keys[curSlot],curSlot); if (foo != Verify()) cout << "verify 1 failed" << endl; if (tmpInode == NULL) { /* @@ -135,9 +148,18 @@ 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()) { @@ -315,7 +337,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); @@ -327,7 +349,7 @@ } else { - for (curSlot = 0; curSlot <= node->used; curSlot++) { + for (curSlot = 0; curSlot < node->used; curSlot++) { if (strcmp(key, node->keys[curSlot]) < 0) break; } // for @@ -447,7 +469,13 @@ ubixfsInode * bTree::Find(const char * key) { - return treeSearch(root, key); + ubixfsInode * tmp = GetFirstNode(); + while (tmp!=NULL) { + if (strcmp(tmp->name, key) == 0) return tmp; + tmp = tmp->next; + } + return NULL; +// return treeSearch(root, key); } // bTree::Find ubixfsInode * diff --git a/src/sys/ubixfsv2/main.cpp b/src/sys/ubixfsv2/main.cpp index f0e1202..ea45c31 100644 --- a/src/sys/ubixfsv2/main.cpp +++ b/src/sys/ubixfsv2/main.cpp @@ -10,6 +10,7 @@ int main(void) { + int a = 0,aa = 0,aaa = 0; int i = 0; ubixfsInode * inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); memset(inode, 0, sizeof(ubixfsInode)); @@ -21,12 +22,52 @@ 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 < (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; } // for i // cout << "i made it to: " << i << endl; + +#if 0 + for (a = 'a';a <= 'a';a++) { + for (aa = 'a';aa <= 'b';aa++) { + for (aaa = 'a';aaa <= 'z';aaa++) { + inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); + memset(inode,0x0,sizeof(ubixfsInode)); + inode->name[0] = a; + inode->name[1] = aa; + inode->name[2] = aaa; + if (!tree->Insert(inode)) cout << "Insert() failed" << endl; + } + } + } + for (a = 'c';a <= 'c';a++) { + for (aa = 'a';aa <= 'b';aa++) { + for (aaa = 'a';aaa <= 'z';aaa++) { + inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); + memset(inode,0x0,sizeof(ubixfsInode)); + inode->name[0] = a; + inode->name[1] = aa; + inode->name[2] = aaa; + if (!tree->Insert(inode)) cout << "Insert() failed" << endl; + } + } + } + for (a = 'b';a <= 'b';a++) { + for (aa = 'a';aa <= 'b';aa++) { + for (aaa = 'a';aaa <= 'z';aaa++) { + inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); + memset(inode,0x0,sizeof(ubixfsInode)); + inode->name[0] = a; + inode->name[1] = aa; + inode->name[2] = aaa; + if (!tree->Insert(inode)) cout << "Insert() failed" << endl; + } + } + } +#endif #if 0 inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); memset(inode, 0, sizeof(ubixfsInode));