diff --git a/src/sys/ubixfsv2/btree.cpp b/src/sys/ubixfsv2/btree.cpp index 7f38f8f..bce5145 100644 --- a/src/sys/ubixfsv2/btree.cpp +++ b/src/sys/ubixfsv2/btree.cpp @@ -19,14 +19,14 @@ if (root == NULL) return; root->used = 1; root->parent = NULL; - root->leafNode = true; + root->leaf = true; root->childCount[1] = 1; // 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; - root->childTail[1] = (void *)inode; + root->head[1] = (void *)inode; + root->tail[1] = (void *)inode; root->present[1] = true; if (inode != NULL) { @@ -53,18 +53,18 @@ */ assert(bnode->used); // cout << "---Inserting " << inode->name << "@" << inode << endl; - while (bnode != NULL && !bnode->leafNode) { + while (bnode != NULL && !bnode->leaf) { if (strcmp(inode->name, bnode->keys[0]) < 0) { - bnode = (bNode *)bnode->childHead[0]; + bnode = (bNode *)bnode->head[0]; } else { if (strcmp(inode->name, bnode->keys[bnode->used-1]) >= 0) { - bnode = (bNode *)bnode->childHead[bnode->used]; + bnode = (bNode *)bnode->head[bnode->used]; } else { for (unsigned int i = 1; i < bnode->used; i++) { if (strcmp(inode->name, bnode->keys[i]) < 0) { - bnode = (bNode *)bnode->childHead[i]; + bnode = (bNode *)bnode->head[i]; break; } // if } // for i @@ -77,24 +77,24 @@ */ assert(bnode); -if (bnode->leafNode != true) cout << "leafnode!=true" << endl; +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->childHead[curSlot]; + tmpInode = (ubixfsInode *)bnode->head[curSlot]; else if (strcmp(inode->name, bnode->keys[(curSlot = bnode->used)-1]) >= 0) - tmpInode = (ubixfsInode *)bnode->childHead[bnode->used]; + tmpInode = (ubixfsInode *)bnode->head[bnode->used]; else { for (curSlot = 1; curSlot < bnode->used; curSlot++) { if (strcmp(inode->name, bnode->keys[curSlot]) < 0) { - tmpInode = (ubixfsInode *)bnode->childHead[curSlot]; + tmpInode = (ubixfsInode *)bnode->head[curSlot]; break; } // if } // for curSlot - tmpInode = (ubixfsInode *)bnode->childHead[curSlot]; + tmpInode = (ubixfsInode *)bnode->head[curSlot]; } // else VERIFY(foo, Verify(), 1, bnode); @@ -103,14 +103,14 @@ /* * This is the first node in this leaf */ - bnode->childHead[curSlot] = bnode->childTail[curSlot] = inode; + bnode->head[curSlot] = bnode->tail[curSlot] = inode; bnode->present[curSlot] = true; VERIFY(foo, Verify(), 2, bnode); if (curSlot == 0) { - if (bnode->childHead[1] != NULL) { - ubixfsInode * iptr = (ubixfsInode *)bnode->childHead[1]; + if (bnode->head[1] != NULL) { + ubixfsInode * iptr = (ubixfsInode *)bnode->head[1]; inode->prev = iptr->prev; inode->next = iptr; iptr->prev = inode; @@ -130,36 +130,36 @@ * Add node to leaf page. Scan through to find where it goes. */ VERIFY(foo, Verify(), 4, bnode); - if (strcmp(inode->name, ((ubixfsInode *)bnode->childHead[curSlot])->name) < 0) + if (strcmp(inode->name, ((ubixfsInode *)bnode->head[curSlot])->name) < 0) { VERIFY(foo, Verify(), 5, bnode); - inode->next = (ubixfsInode *)bnode->childHead[curSlot]; + inode->next = (ubixfsInode *)bnode->head[curSlot]; inode->prev = inode->next->prev; inode->next->prev = inode; if (inode->prev != NULL) inode->prev->next = inode; - bnode->childHead[curSlot] = (void *)inode; + bnode->head[curSlot] = (void *)inode; VERIFY(foo, Verify(), 6, bnode); } else { VERIFY(foo, Verify(), 7, bnode); - if (strcmp(inode->name, ((ubixfsInode *)bnode->childTail[curSlot])->name) > 0) { + if (strcmp(inode->name, ((ubixfsInode *)bnode->tail[curSlot])->name) > 0) { VERIFY(foo, Verify(), 8, bnode); - inode->prev = (ubixfsInode *)bnode->childTail[curSlot]; + inode->prev = (ubixfsInode *)bnode->tail[curSlot]; inode->next = inode->prev->next; inode->prev->next = inode; if (inode->next != NULL) inode->next->prev = inode; - bnode->childTail[curSlot] = inode; + bnode->tail[curSlot] = inode; VERIFY(foo, Verify(), 9, bnode); } else { VERIFY(foo, Verify(), 10, bnode); - ubixfsInode * tmpInode = (ubixfsInode *)bnode->childHead[curSlot]; + ubixfsInode * tmpInode = (ubixfsInode *)bnode->head[curSlot]; for (unsigned int i = 0; i < bnode->childCount[curSlot]; i++) { if (strcmp(inode->name, tmpInode->name) < 0) { inode->next = tmpInode; @@ -187,12 +187,12 @@ if (curSlot != bnode->used) { int shift = bnode->used - curSlot +1; - memmove(&bnode->childHead[curSlot+1], - &bnode->childHead[curSlot], - sizeof(bnode->childHead[0]) * shift); - memmove(&bnode->childTail[curSlot+1], - &bnode->childTail[curSlot], - sizeof(bnode->childTail[0]) * shift); + memmove(&bnode->head[curSlot+1], + &bnode->head[curSlot], + sizeof(bnode->head[0]) * shift); + memmove(&bnode->tail[curSlot+1], + &bnode->tail[curSlot], + sizeof(bnode->tail[0]) * shift); memmove(&bnode->present[curSlot+1], &bnode->present[curSlot], sizeof(bnode->present[0]) * shift); @@ -205,13 +205,13 @@ sizeof(bnode->keys[0]) * (shift-1)); memset(bnode->keys[curSlot], 0, B_MAX_NAME_LENGTH); } else { - bnode->childHead[curSlot+1] = bnode->childHead[curSlot]; - bnode->childTail[curSlot+1] = bnode->childTail[curSlot]; + bnode->head[curSlot+1] = bnode->head[curSlot]; + bnode->tail[curSlot+1] = bnode->tail[curSlot]; bnode->childCount[curSlot+1] = bnode->childCount[curSlot]; bnode->present[curSlot+1] = bnode->present[curSlot]; } // else - ubixfsInode * tmpInode = (ubixfsInode *)bnode->childHead[curSlot]; + ubixfsInode * tmpInode = (ubixfsInode *)bnode->head[curSlot]; for (unsigned int i = 0; i < (B_MAX_CHILD_COUNT+1) >> 1; i++) { assert(tmpInode); @@ -219,8 +219,8 @@ } // for i strncpy(bnode->keys[curSlot], tmpInode->name, B_MAX_NAME_LENGTH); - bnode->childHead[curSlot+1] = (void *)tmpInode; - bnode->childTail[curSlot] = (void *)tmpInode->prev; + bnode->head[curSlot+1] = (void *)tmpInode; + bnode->tail[curSlot] = (void *)tmpInode->prev; bnode->childCount[curSlot] = (B_MAX_CHILD_COUNT+1) >> 1; bnode->childCount[curSlot+1] -= bnode->childCount[curSlot]; bnode->present[curSlot] = true; @@ -242,15 +242,17 @@ bNode * newNode = allocEmptyNode(); 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 >> 1; + unsigned int splitLoc = B_MAX_KEYS - shift; + ++ shift; +cout << "oldNode before split: " << endl; +Info(oldNode); cout << "splitLoc: " << splitLoc << endl; cout << "shift: " << shift << endl; - newNode->used = splitLoc; + newNode->used = oldNode->used = B_MAX_KEYS >> 1; newNode->parent = oldNode->parent; - newNode->leafNode = oldNode->leafNode; - oldNode->used -= newNode->used; + newNode->leaf = oldNode->leaf; cout << "newNode->used: " << newNode->used << endl; cout << "oldNode->used: " << oldNode->used << endl; @@ -267,19 +269,19 @@ memset(&oldNode->present[splitLoc], 0, sizeof(newNode->present[0]) * shift); - memcpy(&newNode->childHead[0], - &oldNode->childHead[splitLoc], - sizeof(newNode->childHead[0]) * shift); + memcpy(&newNode->head[0], + &oldNode->head[splitLoc], + sizeof(newNode->head[0]) * shift); - memset(&oldNode->childHead[splitLoc], 0, - sizeof(newNode->childHead[0]) * shift); + memset(&oldNode->head[splitLoc], 0, + sizeof(newNode->head[0]) * shift); - memcpy(&newNode->childTail[0], - &oldNode->childTail[splitLoc], - sizeof(newNode->childTail[0]) * shift); + memcpy(&newNode->tail[0], + &oldNode->tail[splitLoc], + sizeof(newNode->tail[0]) * shift); - memset(&oldNode->childTail[splitLoc], 0, - sizeof(newNode->childTail[0]) * shift); + memset(&oldNode->tail[splitLoc], 0, + sizeof(newNode->tail[0]) * shift); memcpy(&newNode->childCount[0], &oldNode->childCount[splitLoc], @@ -299,11 +301,11 @@ newNode->parent = root; // strncpy(root->keys[0], newNode->keys[0], B_MAX_NAME_LENGTH); strncpy(root->keys[0], tmpInode->name, B_MAX_NAME_LENGTH); - root->childHead[0] = oldNode; - root->childTail[0] = root->childTail[1] = NULL; - root->childHead[1] = newNode; + root->head[0] = oldNode; + root->tail[0] = root->tail[1] = NULL; + root->head[1] = newNode; root->used = 1; - root->leafNode = false; + root->leaf = false; root->present[0] = root->present[1] = true; root->childCount[0] = root->childCount[1] = 0; // root->childCount[0] = oldNode->used; @@ -334,8 +336,8 @@ curSlot = node->used; memset(node->keys[curSlot], 0, B_MAX_NAME_LENGTH); strncpy(node->keys[curSlot], key, B_MAX_NAME_LENGTH); - node->childHead[curSlot+1] = headPtr; - node->childTail[curSlot+1] = tailPtr; + node->head[curSlot+1] = headPtr; + node->tail[curSlot+1] = tailPtr; node->present[curSlot+1] = true; node->childCount[node->used] = 0; // maybe? @@ -352,12 +354,12 @@ */ int shift = node->used - curSlot +1; - memmove(&node->childHead[curSlot+1], - &node->childHead[curSlot], - sizeof(node->childHead[0]) * shift); - memmove(&node->childTail[curSlot+1], - &node->childTail[curSlot], - sizeof(node->childTail[0]) * shift); + memmove(&node->head[curSlot+1], + &node->head[curSlot], + sizeof(node->head[0]) * shift); + memmove(&node->tail[curSlot+1], + &node->tail[curSlot], + sizeof(node->tail[0]) * shift); memmove(&node->present[curSlot+1], &node->present[curSlot], sizeof(node->present[0]) * shift); @@ -371,8 +373,8 @@ memset(node->keys[curSlot], 0, B_MAX_NAME_LENGTH); strncpy(node->keys[curSlot], key, B_MAX_NAME_LENGTH); - node->childHead[curSlot+1] = headPtr; - node->childTail[curSlot+1] = tailPtr; + node->head[curSlot+1] = headPtr; + node->tail[curSlot+1] = tailPtr; node->present[curSlot+1] = true; // node->childCount[node->used] = ?; } // else @@ -397,7 +399,7 @@ if (node == NULL) return; for (unsigned int i = 0; i <= node->used; i++) { - inode = (ubixfsInode *)node->childHead[i]; + inode = (ubixfsInode *)node->head[i]; cout << "{" << node->childCount[i] << "} "; for (unsigned int k = 0; k < node->childCount[i]; k++) { cout << "(" << inode->name << ") "; @@ -413,9 +415,9 @@ } // for i cout << endl; cout << "node->used: " << node->used << endl; - cout << "leafNode: " << node->leafNode << endl; + cout << "leaf: " << node->leaf << endl; for (unsigned int i = 0; i <= node->used; i++) { - inode = (ubixfsInode *)node->childHead[i]; + inode = (ubixfsInode *)node->head[i]; cout << "node->childCount["<childCount[i] << endl; for (unsigned int j = 0; j < node->childCount[i]; j++) { assert(inode); @@ -436,12 +438,12 @@ cout << endl; for (unsigned int i = 0; i <= root->used; i++) { - cout << "CH[" << i << "]: " << root->childHead[i] << " "; + cout << "CH[" << i << "]: " << root->head[i] << " "; } // for i cout << endl; for (unsigned int i = 0; i <=root->used; i++) { - cout << "CT[" << i << "]: " << root->childTail[i] << " "; + cout << "CT[" << i << "]: " << root->tail[i] << " "; } // for i cout << endl; for (unsigned int i = 0; i < root->used; i++) { @@ -451,16 +453,16 @@ cout << "root->used: " << root->used << endl; for (unsigned int i = 0; i <= root->used; i++) { - inode = (ubixfsInode *)root->childHead[i]; + inode = (ubixfsInode *)root->head[i]; cout << "root->childCount["<childCount[i] << endl; - if (root->leafNode) { + if (root->leaf) { 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 + } // if root->leaf } // for i } // bTree::Info @@ -507,25 +509,27 @@ ubixfsInode * bTree::treeSearch(bNode * bnode, const char * key) { - if (bnode == NULL || key == NULL) return NULL; + if (bnode == NULL || key == NULL || bnode->used == 0) return NULL; - if (bnode->used == 0) return NULL; - if (bnode->leafNode) - if (bnode->childHead[0] != NULL) - return inodeSearch((ubixfsInode *)bnode->childHead[0], key); - else - return inodeSearch((ubixfsInode *)bnode->childHead[1], key); - + if (bnode->leaf) + return inodeSearch(GetFirstNode(bnode), key); +/* + * if (bnode->head[0] != NULL) + * return inodeSearch((ubixfsInode *)bnode->head[0], key); + * else + * return inodeSearch((ubixfsInode *)bnode->head[1], key); + */ // cout << "key: " << key << " keys[0]: " << bnode->keys[0] << " result: " << strcmp(key, bnode->keys[0]) << endl; + if (strcmp(key, bnode->keys[0]) < 0) - return treeSearch((bNode *)bnode->childHead[0], key); + return treeSearch((bNode *)bnode->head[0], key); if (strcmp(key, bnode->keys[bnode->used-1]) >= 0) - return treeSearch((bNode *)bnode->childHead[bnode->used], key); + return treeSearch((bNode *)bnode->head[bnode->used], key); for (unsigned int i = 1; i < bnode->used; i++) { if (strcmp(key, bnode->keys[i]) < 0) - return treeSearch((bNode *)bnode->childHead[i], key); + return treeSearch((bNode *)bnode->head[i], key); } // for i return NULL; @@ -538,24 +542,149 @@ ubixfsInode * bTree::GetFirstNode(bNode * node) { - bNode * tmpNode = node; + if (tmpNode == NULL) return NULL; - while (!tmpNode->leafNode) { + + while (!tmpNode->leaf) { for (unsigned int i = 0; i < tmpNode->used; i++) { - if (tmpNode->childHead[i] != NULL) { - tmpNode = (bNode *)tmpNode->childHead[i]; + if (tmpNode->head[i] != NULL) { + tmpNode = (bNode *)tmpNode->head[i]; break; } // if } // for i } // while for (unsigned int i = 0; i < tmpNode->used; i++) { - if (tmpNode->childHead[i] != NULL) return (ubixfsInode * )tmpNode->childHead[i]; + if (tmpNode->head[i] != NULL) return (ubixfsInode * )tmpNode->head[i]; } // for i return NULL; } // bTree::GetFirstNode +bNode * +bTree::findLeafNode(bNode * node, const char * key) { + assert(node); + assert(key); + if (node == NULL || key == NULL) return NULL; + assert(node->used); + if (node->leaf) return node; + + if (strcmp(key, node->keys[0]) < 0) + return findLeafNode((bNode *)node->head[0], key); + + if (strcmp(key, node->keys[node->used-1]) >= 0) + return findLeafNode((bNode *)node->head[node->used], key); + + for (unsigned int i = 1; i < node->used; i++) { + if (strcmp(key, node->keys[i]) < 0) + return findLeafNode((bNode *)node->head[i], key); + } // for i + + return NULL; +} // bTree::findLeafNode + +bool +bTree::insertInodeIntoLeaf(bNode * leaf, ubixfsInode * inode) { + unsigned int curSlot; + ubixfsInode * tmpInode = NULL; + assert(leaf); + assert(inode); + assert(leaf->leaf); + assert(leaf->used < B_MAX_KEYS); + + if (strcmp(inode->name, leaf->keys[curSlot = 0]) < 0) + tmpInode = (ubixfsInode *)leaf->head[curSlot]; + else + if (strcmp(inode->name, leaf->keys[(curSlot = leaf->used)-1]) >= 0) + tmpInode = (ubixfsInode *)leaf->head[leaf->used]; + else { + for (curSlot = 1; curSlot < leaf->used; curSlot++) { + if (strcmp(inode->name, leaf->keys[curSlot]) < 0) { + tmpInode = (ubixfsInode *)leaf->head[curSlot]; + break; + } // if + } // for curSlot + tmpInode = (ubixfsInode *)leaf->head[curSlot]; + } // else + + if (tmpInode == NULL) { + /* + * This is the first node in this leaf + */ + leaf->head[curSlot] = leaf->tail[curSlot] = inode; + leaf->present[curSlot] = true; + + if (curSlot == 0) { + if (leaf->head[1] != NULL) { + ubixfsInode * iptr = (ubixfsInode *)leaf->head[1]; + inode->prev = iptr->prev; + inode->next = iptr; + iptr->prev = inode; + if (inode->prev != NULL) inode->prev->next = inode; + } else { + inode->next = inode->prev = NULL; + } // else + + } else { + ++leaf->used; + } // else + } else { + /* + * Add node to leaf page. Scan through to find where it goes. + */ + + if (strcmp(inode->name, ((ubixfsInode *)leaf->head[curSlot])->name) < 0) { + + inode->next = (ubixfsInode *)leaf->head[curSlot]; + inode->prev = inode->next->prev; + inode->next->prev = inode; + if (inode->prev != NULL) inode->prev->next = inode; + leaf->head[curSlot] = (void *)inode; + + } else { + + if (strcmp(inode->name, ((ubixfsInode *)leaf->tail[curSlot])->name) > 0) +{ + inode->prev = (ubixfsInode *)leaf->tail[curSlot]; + inode->next = inode->prev->next; + inode->prev->next = inode; + + if (inode->next != NULL) inode->next->prev = inode; + leaf->tail[curSlot] = inode; + + } else { + ubixfsInode * tmpInode = (ubixfsInode *)leaf->head[curSlot]; + for (unsigned int i = 0; i < leaf->childCount[curSlot]; i++) { + if (strcmp(inode->name, tmpInode->name) < 0) { + inode->next = tmpInode; + inode->prev = tmpInode->prev; + inode->next->prev = inode; + inode->prev->next = inode; + break; + } // if + tmpInode = tmpInode->next; + } // for i + } // else + } // else + ++leaf->used; + ++leaf->childCount[curSlot]; + } // else + + return true; +} // bTree::insertInodeIntoLeaf + +bool +bTree::ins(ubixfsInode * inode) { + assert(inode); + bNode * node = findLeafNode(root, inode->name); + assert(node); + if (node->used < B_MAX_KEYS) { + + } + ++node->used; + return true; +} + bool bTree::Save(const char * filename) { if (filename == NULL) return false; diff --git a/src/sys/ubixfsv2/btree.h b/src/sys/ubixfsv2/btree.h index cdfb88c..7f6aba1 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 5 #define B_MAX_NAME_LENGTH 256 #define B_MAX_CHILD_COUNT 4 @@ -16,11 +16,11 @@ uInt32 used __attribute__ ((packed)); char keys[B_MAX_KEYS][B_MAX_NAME_LENGTH] __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)); + 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 leafNode __attribute__ ((packed)); + bool leaf __attribute__ ((packed)); uInt32 magic2 __attribute__ ((packed)); } bNode; // bNode @@ -35,6 +35,8 @@ void splitNode(bNode *); bNode * allocEmptyNode(void); void insertNode(bNode *, const char *, void *, void *); + bNode * findLeafNode(bNode *, const char *); + bool insertInodeIntoLeaf(bNode *, ubixfsInode *); public: bTree(ubixfsInode *); bTree(void) : root(NULL), treeDepth(0) { }; @@ -45,6 +47,7 @@ void Info(void); void Info(const bNode *); bool Insert(ubixfsInode *); + bool ins(ubixfsInode *); bool Save(const char *); bool Load(const char *); void Print(void); diff --git a/src/sys/ubixfsv2/main.cpp b/src/sys/ubixfsv2/main.cpp index 42a1232..3e7a7ab 100644 --- a/src/sys/ubixfsv2/main.cpp +++ b/src/sys/ubixfsv2/main.cpp @@ -14,7 +14,7 @@ int i = 0; ubixfsInode * inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); memset(inode, 0, sizeof(ubixfsInode)); - strcpy(inode -> name, "temp123"); + strcpy(inode -> name, "555"); bTree * tree = new bTree(inode); // for (i = 0; i < 20000; i++) { @@ -24,8 +24,8 @@ if (inode == NULL) break; memset(inode, 0, sizeof(ubixfsInode)); // for (int k = 0; k < (random() % 100)+5; k++) { - for (int k = 0; k < 6; k++) { - inode->name[k] = (char)((random() % 26)+'a'); + for (int k = 0; k < 3; k++) { + inode->name[k] = (char)((random() % 10)+'0'); } // for k if (!tree->Insert(inode)) cout << "Insert() failed" << endl; ++i;