file_systems/bfs/BPlusTree.cpp

34 /*!	Simple array used for the duplicate handling in the B+Tree. This is an
1152 /*!	This will find a free duplicate fragment in the given bplustree_node.
1164 		// does the value link to a duplicate fragment?
1171 			FATAL(("Could not get duplicate fragment at %" B_PRIdOFF ", inode %"
1208 		// If it's a duplicate fragment, try to insert it into that, or if it
1209 		// doesn't fit anymore, create a new duplicate node
1213 			bplustree_node* duplicate = cachedDuplicate.SetToWritable(
1215 			if (duplicate == NULL)
1218 			duplicate_array* array = duplicate->FragmentAt(
1235 				if (duplicate->FragmentsUsed(fNodeSize) < 2) {
1237 					// reuse it as a duplicate node
1240 					memmove(duplicate->DuplicateArray(), array,
1242 					duplicate->left_link = duplicate->right_link
1245 					array = duplicate->DuplicateArray();
1248 					// Create a new duplicate node
1251 						// The old duplicate has not been touched, so we can
1260 					// Copy the array from the fragment node to the duplicate
1271 				// Update the main pointer to link to a duplicate node
1283 		// Put the value into a dedicated duplicate node
1285 		// search for free space in the duplicate nodes of that key
1288 		const bplustree_node* duplicate;
1292 			duplicate = cachedDuplicate.SetTo(duplicateOffset, false);
1293 			if (duplicate == NULL)
1296 			array = duplicate->DuplicateArray();
1299 				FATAL(("_InsertDuplicate: Invalid array size in duplicate %"
1305 				&& (oldValue = duplicate->RightLink()) != BPLUSTREE_NULL);
1316 			// no space left - add a new duplicate node
1335 	// Search for a free duplicate fragment or create a new one
1336 	// to insert the duplicate value into
1342 		// allocate a new duplicate fragment node
1708 			// first round, check for duplicate entries
1712 			// is this a duplicate entry?
1824 /*!	Removes the duplicate index/value pair from the tree.
1837 	bplustree_node* duplicate = cachedDuplicate.SetToWritable(transaction,
1839 	if (duplicate == NULL)
1842 	// if it's a duplicate fragment, remove the entry from there
1844 		duplicate_array* array = duplicate->FragmentAt(
1872 			if (duplicate->FragmentsUsed(fNodeSize) == 1) {
1883 	// Remove value from a duplicate node!
1888 	if (duplicate->LeftLink() != BPLUSTREE_NULL) {
1889 		FATAL(("invalid duplicate node: first left link points to %" B_PRIdOFF
1890 			", inode %" B_PRIdOFF "!\n", duplicate->LeftLink(), fStream->ID()));
1894 	// Search the duplicate nodes until the entry could be found (and removed)
1895 	while (duplicate != NULL) {
1896 		array = duplicate->DuplicateArray();
1900 			FATAL(("_RemoveDuplicate: Invalid array size in duplicate %"
1911 		if ((duplicateOffset = duplicate->RightLink()) == BPLUSTREE_NULL)
1915 		duplicate = cachedDuplicate.SetToWritable(transaction, duplicateOffset,
1918 	if (duplicate == NULL)
1921 	// The entry got removed from the duplicate node, but we might want to free
1925 		off_t left = duplicate->LeftLink();
1926 		off_t right = duplicate->RightLink();
1930 			// Free empty duplicate page, link their siblings together, and
1931 			// update the duplicate link if needed (ie. when we either remove
1932 			// the last duplicate node or have a new first one)
1935 				// the duplicate link points to us
1941 					// replace the duplicate link with that value, it's no
1942 					// duplicate anymore
1945 					// Move the duplicate link to the next node
1958 				&& (duplicate = cachedDuplicate.SetToWritable(transaction, left,
1960 				duplicate->right_link = HOST_ENDIAN_TO_BFS_INT64(right);
1963 				// and convert the duplicate entry back into a normal entry
1964 				array = duplicate->DuplicateArray();
1967 					&& duplicate->LeftLink() == BPLUSTREE_NULL
1974 				&& (duplicate = cachedDuplicate.SetToWritable(transaction,
1976 				duplicate->left_link = HOST_ENDIAN_TO_BFS_INT64(left);
1978 				// Again, we may need to turn the duplicate entry back into a
1980 				array = duplicate->DuplicateArray();
1983 					&& duplicate->RightLink() == BPLUSTREE_NULL
1992 			// If the number of entries fits in a duplicate fragment, then
2011 				memmove(duplicate, array,
2013 				memset((off_t*)duplicate + NUM_FRAGMENT_VALUES + 1, 0,
2121 			// first round, check for duplicate entries
2127 			// Is this a duplicate entry?
2380 			// Walk the duplicate nodes
2391 					dprintf("inode %" B_PRIdOFF ": duplicate node at %"
2407 						isFragmentNode ? "fragment" : "duplicate",
2436 					dprintf("inode %" B_PRIdOFF ": duplicate at %" B_PRIdOFF
2445 							dprintf("inode %" B_PRIdOFF ": duplicate at %"
2460 					dprintf("inode %" B_PRIdOFF ": duplicate at %" B_PRIdOFF
2630 	first entry - if you need to know when this happens, use the "duplicate"
2631 	parameter which is 0 for no duplicate, 1 for the first, and 2 for all
2641 	uint16 maxLength, off_t* value, uint16* duplicate)
2690 				if (duplicate)
2691 					*duplicate = 2;
2704 	if (duplicate)
2705 		*duplicate = 0;
2771 	// duplicate fragments?
2788 			if (duplicate)
2789 				*duplicate = 1;
2875 	// TODO: duplicate handling!
2951 	// the duplicate fragment handling is currently hard-coded to a node size