diff --git a/src/sys/ubixfsv2/btree.cpp b/src/sys/ubixfsv2/btree.cpp index 3f7344e..74fb015 100644 --- a/src/sys/ubixfsv2/btree.cpp +++ b/src/sys/ubixfsv2/btree.cpp @@ -16,7 +16,7 @@ root->leafNode = true; root->childCount[1] = 1; -cout << "---Creating " << inode->name << "---" << endl; +cout << "---Creating " << inode->name << "@" << inode << endl; strncpy(root->keys[0], inode->name, B_MAX_NAME_LENGTH); // insert pointer to data page to the right of the data root->childHead[1] = (void *)inode; @@ -41,9 +41,9 @@ * Find the leaf node the inode goes into */ 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) bnode = (bNode *)bnode->childHead[0]; else if (strcmp(inode->name, bnode->keys[bnode->used-1]) >= 0) @@ -61,10 +61,18 @@ /* * */ +assert(bnode->leafNode); +assert(inode); + +cout << inode->name << " ~~ " << bnode->keys[0] << " == "; +cout << strcmp(inode->name, bnode->keys[0]) << endl; +cout << inode->name << " ~~ " << bnode->keys[bnode->used-1] << " == "; +cout << strcmp(inode->name, bnode->keys[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]) >= 0) + if (strcmp(inode->name, bnode->keys[(curSlot = bnode->used)-1]) >= 0) tmpInode = (ubixfsInode *)bnode->childHead[bnode->used]; else { for (curSlot = 1; curSlot < bnode->used; curSlot++) { @@ -136,10 +144,10 @@ } // else 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(); +// cout << "---- before split ----" << endl; +// 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,7 +189,7 @@ cout << "childCount[" << curSlot << "] : " << bnode->childCount[curSlot] << endl; cout << "childCount[" << curSlot+1 << "] : " << bnode->childCount[curSlot+1] << endl; bnode->present[curSlot] = true; - ++bnode->used; + if (++bnode->used == B_MAX_KEYS) splitNode(bnode); cout << "--- After split ---" << endl; // Info(); } // if leaf is full @@ -191,6 +199,7 @@ void bTree::splitNode(bNode * oldNode) { +cout << "---in splitNode()---" << endl; assert(oldNode); if (oldNode == NULL) return; if (oldNode->used != B_MAX_KEYS) return; @@ -199,41 +208,46 @@ if (newNode == NULL) return; unsigned int splitLoc = (B_MAX_KEYS+1) >> 1; - unsigned int shift = B_MAX_KEYS - splitLoc+1; + unsigned int shift = B_MAX_KEYS - splitLoc; - newNode->used = (B_MAX_KEYS+1) >> 1; +cout << "splitLoc: " << splitLoc << " shift: " << shift << endl; + newNode->used = shift; newNode->parent = oldNode->parent; newNode->leafNode = oldNode->leafNode; + oldNode->used -= newNode->used+1; memcpy(&newNode->keys[0], &oldNode->keys[splitLoc], - sizeof(newNode->keys[0]) * (shift+1)); + sizeof(newNode->keys[0]) * shift); - memset(&oldNode->keys[splitLoc], 0, sizeof(newNode->keys[0]) * (shift+1)); + memset(&oldNode->keys[splitLoc], 0, sizeof(newNode->keys[0]) * shift); memcpy(&newNode->present[0], &oldNode->present[splitLoc], - sizeof(newNode->present[0]) * shift); + sizeof(newNode->present[0]) * (shift+1)); - memset(&oldNode->present[splitLoc], 0, sizeof(newNode->present[0]) * shift); + memset(&oldNode->present[splitLoc], 0, sizeof(newNode->present[0])*(shift+1)); memcpy(&newNode->childHead[0], &oldNode->childHead[splitLoc], - sizeof(newNode->childHead[0]) * shift); + sizeof(newNode->childHead[0]) * (shift+1)); - memset(&oldNode->childHead[splitLoc], 0, sizeof(newNode->childHead[0]) * shift); + memset(&oldNode->childHead[splitLoc], 0, + sizeof(newNode->childHead[0]) * (shift+1)); memcpy(&newNode->childTail[0], &oldNode->childTail[splitLoc], - sizeof(newNode->childTail[0]) * shift); + sizeof(newNode->childTail[0]) * (shift+1)); - memset(&oldNode->childTail[splitLoc], 0, sizeof(newNode->childTail[0]) * shift); + memset(&oldNode->childTail[splitLoc], 0, + sizeof(newNode->childTail[0]) * (shift+1)); memcpy(&newNode->childCount[0], &oldNode->childCount[splitLoc], - sizeof(newNode->childCount[0]) * shift); + sizeof(newNode->childCount[0]) * (shift+1)); - memset(&oldNode->childCount[splitLoc], 0, sizeof(newNode->childCount[0]) * shift); + memset(&oldNode->childCount[splitLoc], 0, + sizeof(newNode->childCount[0]) * (shift+1)); if (oldNode == root) { // allocate a new root node @@ -249,9 +263,18 @@ 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; } else { 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 @@ -267,20 +290,62 @@ } // bTree::allocEmptyNode void -bTree::Info(void) { +bTree::Info(const bNode * node) { ubixfsInode * inode = NULL; - if (root == NULL) return; - cout << "root->used: " << root->used << endl; - for (unsigned int i = 0; i <= root->used; i++) { - inode = (ubixfsInode *)root->childHead[i]; -cout << "root->childCount[i]: " << root->childCount[i] << endl; - for (unsigned int j = 0; j < root->childCount[i]; j++) { + if (node == NULL) return; + + 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; + for (unsigned int i = 0; i <= node->used; i++) { + inode = (ubixfsInode *)node->childHead[i]; +cout << "node->childCount["<childCount[i] << endl; + for (unsigned int j = 0; j < node->childCount[i]; j++) { assert(inode); cout << "[" << i << "].[" << j << "]->" << inode->name << endl; inode = inode->next; } // for j } // for i +} // bTree::Info +void +bTree::Info(void) { + ubixfsInode * inode = NULL; + if (root == NULL) return; + for (unsigned int i = 0; i <= root->used; i++) { + cout << "CC[" << i << "]: " << root->childCount[i] << " "; + } // for i + + cout << endl; + for (unsigned int i = 0; i <= root->used; i++) { + cout << "CH[" << i << "]: " << root->childHead[i] << " "; + } // for i + + cout << endl; + for (unsigned int i = 0; i <=root->used; i++) { + cout << "CT[" << i << "]: " << root->childTail[i] << " "; + } // for i + cout << endl; + for (unsigned int i = 0; i < root->used; i++) { + cout << "keys[" << i << "]: " << root->keys[i] << " "; + } // for i + cout << endl; + +cout << "root->used: " << root->used << endl; + for (unsigned int i = 0; i <= root->used; i++) { + inode = (ubixfsInode *)root->childHead[i]; +cout << "root->childCount["<childCount[i] << endl; + if (root->leafNode) { +cout << "root contains leaf node" << endl; + for (unsigned int j = 0; j < root->childCount[i]; j++) { + assert(inode); + cout << "[" << i << "].[" << j << "]->" << inode->name << endl; + inode = inode->next; + } // for j + } // if root->leafNode + } // for i } // bTree::Info void @@ -346,7 +411,7 @@ ubixfsInode * bTree::GetFirstNode(void) { -cout << "In GetFirstNode" << endl; + bNode * tmpNode = root; if (tmpNode == NULL) return NULL; while (!tmpNode->leafNode) { @@ -357,8 +422,6 @@ } // 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]; diff --git a/src/sys/ubixfsv2/btree.h b/src/sys/ubixfsv2/btree.h index f491326..72365de 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 4 +#define B_MAX_KEYS 14 #define B_MAX_NAME_LENGTH 256 #define B_MAX_CHILD_COUNT 4 @@ -15,7 +15,7 @@ uInt32 magic1 __attribute__ ((packed)); uInt32 used __attribute__ ((packed)); char keys[B_MAX_KEYS][B_MAX_NAME_LENGTH] __attribute__ ((packed)); - bool present[B_MAX_KEYS] __attribute__ ((packed)); + bool present[B_MAX_KEYS+1] __attribute__ ((packed)); void * childHead[(B_MAX_KEYS+1)*8/sizeof(void *)] __attribute__ ((packed)); void * childTail[(B_MAX_KEYS+1)*8/sizeof(void *)] __attribute__ ((packed)); uInt32 childCount[B_MAX_KEYS+1] __attribute__ ((packed)); @@ -38,6 +38,7 @@ ubixfsInode * GetFirstNode(void); bool Delete(const char *); void Info(void); + void Info(const bNode *); bool Insert(ubixfsInode *); bool Save(const char *); bool Load(const char *); diff --git a/src/sys/ubixfsv2/main.cpp b/src/sys/ubixfsv2/main.cpp index 2c1fc90..57265c2 100644 --- a/src/sys/ubixfsv2/main.cpp +++ b/src/sys/ubixfsv2/main.cpp @@ -1,5 +1,6 @@ -#include #include +#include +#include #include "inode.h" #include "superblock.h" #include "vfs.h" @@ -15,58 +16,68 @@ strcpy(inode -> name, "h"); bTree * tree = new bTree(inode); + for (i = 0; i < 100; i++) { + inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); + memset(inode, 0, sizeof(ubixfsInode)); + for (int k = 0; k < (random() % 100)+5; k++) { + inode->name[k] = (char)((random() % 26)+'a'); + } // for k + tree->Insert(inode); + } // for i +#if 0 inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); memset(inode, 0, sizeof(ubixfsInode)); strcpy(inode->name, "m"); -cout << "---Inserting " << inode->name << "---" << endl; tree->Insert(inode); inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); memset(inode, 0, sizeof(ubixfsInode)); strcpy(inode->name, "a"); -cout << "---Inserting " << inode->name << "---" << endl; tree->Insert(inode); inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); memset(inode, 0, sizeof(ubixfsInode)); strcpy(inode->name, "b"); -cout << "---Inserting " << inode->name << "---" << endl; tree->Insert(inode); inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); memset(inode, 0, sizeof(ubixfsInode)); strcpy(inode->name, "c"); -cout << "---Inserting " << inode->name << "---" << endl; tree->Insert(inode); inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); memset(inode, 0, sizeof(ubixfsInode)); strcpy(inode->name, "d"); -cout << "---Inserting " << inode->name << "---" << endl; tree->Insert(inode); inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); memset(inode, 0, sizeof(ubixfsInode)); strcpy(inode->name, "e"); -cout << "---Inserting " << inode->name << "---" << endl; tree->Insert(inode); inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); memset(inode, 0, sizeof(ubixfsInode)); strcpy(inode->name, "f"); -cout << "---Inserting " << inode->name << "---" << endl; - tree->Insert(inode); - - inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); - memset(inode, 0, sizeof(ubixfsInode)); - strcpy(inode->name, "g"); -cout << "---Inserting " << inode->name << "---" << endl; tree->Insert(inode); inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); memset(inode, 0, sizeof(ubixfsInode)); strcpy(inode->name, "j"); -cout << "---Inserting " << inode->name << "---" << endl; + tree->Insert(inode); + + inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); + memset(inode, 0, sizeof(ubixfsInode)); + strcpy(inode->name, "h"); + tree->Insert(inode); + + inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); + memset(inode, 0, sizeof(ubixfsInode)); + strcpy(inode->name, "eee"); + tree->Insert(inode); + + inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); + memset(inode, 0, sizeof(ubixfsInode)); + strcpy(inode->name, "ee"); tree->Insert(inode); inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); @@ -74,7 +85,8 @@ strcpy(inode->name, "n"); cout << "---Inserting " << inode->name << "---" << endl; tree->Insert(inode); - +#endif + i = 0; ubixfsInode * tmpInode = tree->GetFirstNode(); if (tmpInode == NULL) cout << "GetFirstNode() returns null" << endl; while (tmpInode != NULL) { @@ -82,7 +94,7 @@ tmpInode = tmpInode->next; } // while cout << sizeof(struct bNode) << endl; - tree->Info(); + free(inode); return 0; }