bfs_tools/lib/BPlusTree.cpp

370 status_t BPlusTree::Traverse(int8 direction,void *key,uint16 *keyLength,uint16 maxLength,off_t *value)
417 	// is the current key in the current node?
430 			// reset current key
435 			// there are no nodes left, so turn back to the last key
450 	memcpy(key,keyStart,length);
456 		((char *)key)[length] = '\0';
564 status_t BPlusTree::FindKey(bplustree_node *node,uint8 *key,uint16 keyLength,uint16 *index,off_t *next)
578 	// binary search in the key array
586 		int32 cmp = CompareKeys(key,keyLength,searchKey,searchLength);
619 status_t BPlusTree::SeekDown(Stack<node_and_key> &stack,uint8 *key,uint16 keyLength)
637 		status_t status = FindKey(node,key,keyLength,&nodeAndKey.keyIndex,&nextOffset);
651 void BPlusTree::InsertKey(bplustree_node *node,uint8 *key,uint16 keyLength,off_t value,uint16 index)
673 	// move and update key length index
681 	// move keys and copy new key into them
686 	memcpy(keys + keyStart,key,keyLength);
721 status_t BPlusTree::SplitNode(bplustree_node *node,off_t nodeOffset,uint16 *_keyIndex,uint8 *key,uint16 *_keyLength,off_t *_value)
726 	//printf("before (insert \"%s\" (%d bytes) at %d):\n\n",key,*_keyLength,*_keyIndex);
743 	// "bytes" is the number of bytes written for the new key,
744 	// "bytesBefore" are the bytes before that key
745 	// "bytesAfter" are the bytes after the new key, if any
758 				// fix the key lengths for the new node
772 	// if the new key was not inserted, set the length of the keys
799 		// copy the newly inserted key
800 		memcpy(outKeys + bytesBefore,key,bytes);
805 			// copy the keys after the new key
813 	// if the new key was already inserted, we shouldn't use it again
819 	// if we have split an index node, we have to drop the first key
820 	// of the next node (which can also be the new key to insert)
910 		// finally, copy the newly inserted key (don't overwrite anything)
911 		memcpy(inKeys + bytesBefore,key,bytes);
937 	// prepare key to insert in the parent node
942 	memcpy(key,lastKey,length);
950 status_t BPlusTree::Insert(uint8 *key,uint16 keyLength,off_t value)
956 	if (SeekDown(stack,key,keyLength) != B_OK)
961 	memcpy(keyBuffer,key,keyLength);
976 			status_t status = FindKey(node,key,keyLength,&nodeAndKey.keyIndex);
1040 status_t BPlusTree::Find(uint8 *key,uint16 keyLength,off_t *value)
1046 	if (SeekDown(stack,key,keyLength) != B_OK)
1056 		status_t status = FindKey(node,key,keyLength,&nodeAndKey.keyIndex);