hfscommon/BTree/BTreeTreeOps.c

31 	Contains:	Multi-node tree operations for the BTree Module.
56 	   <CS5>	 12/8/97	djb		Radar #2200632, CollapseTree wasn't marking root node dirty.
157 									 u_int32_t					 node,
172 //////////////////////// BTree Multi-node Tree Operations ///////////////////////
187 Output:		nodeNum			- number of the node containing the key position
204 	int16_t		level;					//	Expected depth of current node
205 	u_int32_t	curNodeNum;				//	Current node we're searching
209 	int8_t		nodeKind;				//	Kind of current node (index/leaf)
225 	treePathTable [0].node		= 0;
231         //	[2550929] Node number 0 is the header node.  It is never a valid
232         //	index or leaf node.  If we're ever asked to search through node 0,
233         //	something has gone wrong (typically a bad child node number, or
234         //	we found a node full of zeroes that we thought was an index node).
250         //	[2550929] Sanity check the node height and node type.  We expect
257 //		Panic("Incorrect node height");
267  //		Panic("Incorrect node type: expected leaf");
274             //	A node at any other depth must be an index node
277 //		Panic("Incorrect node type: expected index");
285         treePathTable [level].node		= curNodeNum;
302             //	(typically a corrupt node that confused SearchNode).  Invalidate the node
310         //	Get the child pointer out of this index node.  We're now done with the current
311         //	node and can continue the search with the child node.
319         //	The child node should be at a level one less than the parent.
328 		return	noErr;			// searchKey found, index identifies record in node
406 	targetNodeNum = treePathTable [level].node;
423 		// root node that references the current targetNode.
426 		// the target node, then we'll have to update the second
427 		// key in the new root node.
429 		treePathTable [level + 1].node  = btreePtr->rootNode;
471 		parentNodeNum = treePathTable [level].node;
473 		PanicIf ( parentNodeNum == 0, " InsertLevel: parent node is zero!?");
475 		err = GetNode (btreePtr, parentNodeNum, 0, &parentNode);	// released as target node in next level up
479 			PanicIf ( ((NodeDescPtr)parentNode.buffer)->kind != kBTIndexNode, " InsertLevel: parent node not an index node! ");
490 			PanicIf( (*(u_int32_t *) recPtr) != targetNodeNum, " InsertLevel: parent ptr doesn't match target node!");
561 							 u_int32_t				 node,
588 	if (node == leftNodeNum) {
598 		// we can assume right node is initialized.
607 		*newNode  = node;
629 		PanicIf ( ((NodeDescPtr) leftNode->buffer)->fLink != node, " InsertNode, RotateLeft: invalid sibling link!" );
650 		// might not have left node...
651 		err = SplitLeft (btreePtr, leftNode, rightNode, node, index, key->keyPtr,
655 		// if we split root node - add new root
718 	targetNodeNum = treePathTable[level].node;
793 	if ( level == btreePtr->treeDepth )		// then targetNode->buffer is the root node
817 		err = GetNode (btreePtr, treePathTable[level].node, 0, &parentNode);
886 			break;							// this will make a fine root node
994 	// add size of insert record to right node
1048 		if ( index == rightInsertIndex )	// insert new record in left node
1080 	if ( moveIndex <= rightInsertIndex )	// then insert new record in right node
1201 		// if we're adding a new first leaf node - update BTreeInfoRec
1221 	//�� Free new node if allocated?