diff --git a/src/sys/ubixfsv2/Makefile b/src/sys/ubixfsv2/Makefile index 0e4f7e2..2165acd 100644 --- a/src/sys/ubixfsv2/Makefile +++ b/src/sys/ubixfsv2/Makefile @@ -18,7 +18,7 @@ #CFLAGS -CFLAGS = -O +CFLAGS = -O3 all: $(BINARY) diff --git a/src/sys/ubixfsv2/btree.cpp b/src/sys/ubixfsv2/btree.cpp index bce5145..26fa3a1 100644 --- a/src/sys/ubixfsv2/btree.cpp +++ b/src/sys/ubixfsv2/btree.cpp @@ -8,7 +8,7 @@ #include "assert.h" using namespace std; -#define VERIFY(x, y, z, n) if ((x) != (y)) { cout << "verify " << z << " failed" << endl; Info(n); } +#define VERIFY(x, y, z, n) if ((x) != (y)) { cout << "verify " << z << " failed" << endl; PrintWholeTree(); } bTree::bTree(ubixfsInode * inode) : root(NULL) { treeDepth = 1; @@ -40,12 +40,12 @@ 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) return false; -cout << "Insert(" << inode->name << ");" << endl; +// PrintWholeTree(); +// cout << "Insert(" << inode->name << ")" << endl; //Info(bnode); ++treeLeafCount; /* @@ -56,12 +56,10 @@ while (bnode != NULL && !bnode->leaf) { if (strcmp(inode->name, bnode->keys[0]) < 0) { bnode = (bNode *)bnode->head[0]; - } - else { + } else { if (strcmp(inode->name, bnode->keys[bnode->used-1]) >= 0) { bnode = (bNode *)bnode->head[bnode->used]; - } - else { + } else { for (unsigned int i = 1; i < bnode->used; i++) { if (strcmp(inode->name, bnode->keys[i]) < 0) { bnode = (bNode *)bnode->head[i]; @@ -80,8 +78,6 @@ if (bnode->leaf != true) cout << "leafnode!=true" << endl; assert(inode); -VERIFY(foo, Verify(), 0, bnode); - if (strcmp(inode->name, bnode->keys[curSlot = 0]) < 0) tmpInode = (ubixfsInode *)bnode->head[curSlot]; else @@ -97,7 +93,6 @@ tmpInode = (ubixfsInode *)bnode->head[curSlot]; } // else -VERIFY(foo, Verify(), 1, bnode); if (tmpInode == NULL) { /* @@ -106,7 +101,6 @@ bnode->head[curSlot] = bnode->tail[curSlot] = inode; bnode->present[curSlot] = true; -VERIFY(foo, Verify(), 2, bnode); if (curSlot == 0) { if (bnode->head[1] != NULL) { @@ -119,8 +113,6 @@ inode->next = inode->prev = NULL; } // else -VERIFY(foo, Verify(), 3, bnode); - } else { ++bnode->used; } // else @@ -129,35 +121,28 @@ /* * Add node to leaf page. Scan through to find where it goes. */ -VERIFY(foo, Verify(), 4, bnode); if (strcmp(inode->name, ((ubixfsInode *)bnode->head[curSlot])->name) < 0) { -VERIFY(foo, Verify(), 5, bnode); inode->next = (ubixfsInode *)bnode->head[curSlot]; inode->prev = inode->next->prev; inode->next->prev = inode; if (inode->prev != NULL) inode->prev->next = inode; bnode->head[curSlot] = (void *)inode; -VERIFY(foo, Verify(), 6, bnode); } else { -VERIFY(foo, Verify(), 7, bnode); if (strcmp(inode->name, ((ubixfsInode *)bnode->tail[curSlot])->name) > 0) { -VERIFY(foo, Verify(), 8, bnode); inode->prev = (ubixfsInode *)bnode->tail[curSlot]; inode->next = inode->prev->next; inode->prev->next = inode; if (inode->next != NULL) inode->next->prev = inode; bnode->tail[curSlot] = inode; -VERIFY(foo, Verify(), 9, bnode); } else { -VERIFY(foo, Verify(), 10, bnode); ubixfsInode * tmpInode = (ubixfsInode *)bnode->head[curSlot]; for (unsigned int i = 0; i < bnode->childCount[curSlot]; i++) { @@ -170,14 +155,14 @@ } // 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) { @@ -245,17 +230,19 @@ unsigned int shift = B_MAX_KEYS >> 1; unsigned int splitLoc = B_MAX_KEYS - shift; ++ shift; -cout << "oldNode before split: " << endl; -Info(oldNode); -cout << "splitLoc: " << splitLoc << endl; -cout << "shift: " << shift << endl; +// cout << "oldNode before split: " << endl; +// Info(oldNode); +// cout << "splitLoc: " << splitLoc << endl; +// cout << "shift: " << shift << endl; newNode->used = oldNode->used = B_MAX_KEYS >> 1; newNode->parent = oldNode->parent; + assert(newNode->parent != oldNode); + assert(oldNode->parent != newNode); newNode->leaf = oldNode->leaf; -cout << "newNode->used: " << newNode->used << endl; -cout << "oldNode->used: " << oldNode->used << endl; +// cout << "newNode->used: " << newNode->used << endl; +// cout << "oldNode->used: " << oldNode->used << endl; memcpy(&newNode->keys[0], &oldNode->keys[splitLoc], @@ -290,6 +277,12 @@ memset(&oldNode->childCount[splitLoc], 0, sizeof(newNode->childCount[0]) * shift); + if (!newNode->leaf) { + for (unsigned int i = 0; i <= newNode->used; i++) { + ((bNode *)newNode->head[i])->parent = newNode; + } // for i + } // if newNode isn't a leaf + tmpInode = GetFirstNode(newNode); assert(tmpInode); @@ -310,19 +303,26 @@ 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; + +// cout << "parent" << endl; +// Info(newNode->parent); +// cout << "oldNode" << endl; +// Info(oldNode); +// cout << "-----" << endl; +// cout << "newNode" << endl; +// Info(newNode); +// cout << "-----" << endl; } else { - insertNode(oldNode->parent, tmpInode->name, newNode, NULL); + assert(newNode->parent != oldNode); + assert(oldNode->parent != newNode); + insertNode(newNode->parent, tmpInode->name, newNode, NULL); + assert(newNode->parent != oldNode); + assert(oldNode->parent != newNode); // if (oldNode->parent->used == B_MAX_KEYS) splitNode(oldNode->parent); } // else + assert(newNode->parent != oldNode); + assert(oldNode->parent != newNode); return; } // bTree::splitNode @@ -389,6 +389,7 @@ memset(newNode, 0, sizeof(bNode)); newNode->magic1 = B_NODE_MAGIC_1; newNode->magic2 = B_NODE_MAGIC_2; + newNode->parent = NULL; return newNode; } // bTree::allocEmptyNode @@ -397,15 +398,15 @@ bTree::Info(const bNode * node) { ubixfsInode * inode = NULL; if (node == NULL) return; - + cout << node << " | " << node->parent << endl; for (unsigned int i = 0; i <= node->used; i++) { inode = (ubixfsInode *)node->head[i]; - cout << "{" << node->childCount[i] << "} "; +// cout << "(" << node->childCount[i] << ")"; for (unsigned int k = 0; k < node->childCount[i]; k++) { - cout << "(" << inode->name << ") "; + cout << "[" << inode->name << "]"; inode = inode->next; } // for k - if (i != node->used) cout << "[" << node->keys[i] << "] "; + if (i != node->used) cout << " {" << node->keys[i] << "} "; } // for i cout << endl; return; @@ -719,6 +720,21 @@ return true; } // bTree::Verify +void +bTree::Print(bNode * node) { + if (node == NULL) return; + Info(node); + if (!node->leaf) + for (unsigned int i = 0; i <= node->used; i++) { + Print((bNode *)node->head[i]); + } // for i +} // bTree::Print + +void +bTree::PrintWholeTree(void) { + Print(root); +} // bTree::PrintWholeTree; + bTree::~bTree(void) { cout << "tree depth: " << treeDepth << endl; cout << "tree width: " << treeWidth << endl; diff --git a/src/sys/ubixfsv2/btree.h b/src/sys/ubixfsv2/btree.h index 7f6aba1..82bea8e 100644 --- a/src/sys/ubixfsv2/btree.h +++ b/src/sys/ubixfsv2/btree.h @@ -7,21 +7,22 @@ #define B_NODE_MAGIC_1 0xDEADBEEF #define B_NODE_MAGIC_2 0x1900BABE -#define B_MAX_KEYS 5 -#define B_MAX_NAME_LENGTH 256 +#define B_MAX_KEYS 15 +#define B_MAX_NAME_LENGTH 240 #define B_MAX_CHILD_COUNT 4 typedef struct bNode { uInt32 magic1 __attribute__ ((packed)); uInt32 used __attribute__ ((packed)); + bNode * parent __attribute__ ((packed)); char keys[B_MAX_KEYS][B_MAX_NAME_LENGTH] __attribute__ ((packed)); bool present[B_MAX_KEYS+1] __attribute__ ((packed)); void * head[(B_MAX_KEYS+1)*8/sizeof(void *)] __attribute__ ((packed)); void * tail[(B_MAX_KEYS+1)*8/sizeof(void *)] __attribute__ ((packed)); uInt32 childCount[B_MAX_KEYS+1] __attribute__ ((packed)); - bNode * parent __attribute__ ((packed)); - bool leaf __attribute__ ((packed)); uInt32 magic2 __attribute__ ((packed)); + bool leaf __attribute__ ((packed)); + char reserved[143] __attribute__ ((packed)); } bNode; // bNode class bTree { @@ -37,6 +38,7 @@ void insertNode(bNode *, const char *, void *, void *); bNode * findLeafNode(bNode *, const char *); bool insertInodeIntoLeaf(bNode *, ubixfsInode *); + void Print(bNode *); public: bTree(ubixfsInode *); bTree(void) : root(NULL), treeDepth(0) { }; @@ -51,6 +53,7 @@ bool Save(const char *); bool Load(const char *); void Print(void); + void PrintWholeTree(void); bool Verify(void); ~bTree(void); }; // bTree diff --git a/src/sys/ubixfsv2/inode.h b/src/sys/ubixfsv2/inode.h index 7f5931e..82ca268 100644 --- a/src/sys/ubixfsv2/inode.h +++ b/src/sys/ubixfsv2/inode.h @@ -47,6 +47,6 @@ // binodeEtc *etc ?? dataStream data __attribute__ ((packed)); int32 pad[4] __attribute__ ((packed)); - int32 smallData[1] __attribute__ ((packed)); + char smallData[3620] __attribute__ ((packed)); } ubixfsInode; #endif diff --git a/src/sys/ubixfsv2/main.cpp b/src/sys/ubixfsv2/main.cpp index 3e7a7ab..115cecc 100644 --- a/src/sys/ubixfsv2/main.cpp +++ b/src/sys/ubixfsv2/main.cpp @@ -14,21 +14,22 @@ int i = 0; ubixfsInode * inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); memset(inode, 0, sizeof(ubixfsInode)); - strcpy(inode -> name, "555"); + strcpy(inode -> name, "50"); bTree * tree = new bTree(inode); -// for (i = 0; i < 20000; i++) { - while (tree->Verify()) { + for (i = 0; i < 250000; i++) { +// while (tree->Verify()) { // if (i%1000 == 0) cout << "-_- i = "<name[k] = (char)((random() % 10)+'0'); + for (int k = 0; k < (random() % 100)+5; k++) { +// for (int k = 0; k < 100; k++) { + inode->name[k] = (char)((random() % 26)+'a'); } // for k - if (!tree->Insert(inode)) cout << "Insert() failed" << endl; - ++i; +// tree->Insert(inode); + if (!tree->Insert(inode)) cout << "Insert(" << inode->name << ") failed" << endl; +// ++i; } // for i // cout << "i made it to: " << i << endl; @@ -143,6 +144,7 @@ } // while // cout << sizeof(struct bNode) << endl; +// cout << sizeof(struct ubixfsInode) << endl; // tree->Info(); free(inode);