Lines Matching defs:btreePtr
108 static OSStatus AddNewRootNode (BTreeControlBlockPtr btreePtr,
112 static OSStatus CollapseTree (BTreeControlBlockPtr btreePtr,
115 static OSStatus RotateLeft (BTreeControlBlockPtr btreePtr,
127 static Boolean RotateRecordLeft (BTreeControlBlockPtr btreePtr,
131 static OSStatus SplitLeft (BTreeControlBlockPtr btreePtr,
145 static OSStatus InsertLevel (BTreeControlBlockPtr btreePtr,
154 static OSErr InsertNode (BTreeControlBlockPtr btreePtr,
166 static u_int16_t GetKeyLength (const BTreeControlBlock *btreePtr,
183 Input: btreePtr - pointer to control block of BTree to search
196 OSStatus SearchTree (BTreeControlBlockPtr btreePtr,
215 curNodeNum = btreePtr->rootNode;
216 level = btreePtr->treeDepth;
243 err = GetNode (btreePtr, curNodeNum, 0, &nodeRec);
283 keyFound = SearchNode (btreePtr, nodeRec.buffer, searchKey, &index);
298 err = GetRecordByIndex (btreePtr, nodeRec.buffer, index, &keyPtr, &dataPtr, &dataSize);
306 (void) TrashNode(btreePtr, &nodeRec);
313 err = ReleaseNode (btreePtr, &nodeRec);
333 (void) ReleaseNode(btreePtr, &nodeRec);
351 OSStatus InsertTree ( BTreeControlBlockPtr btreePtr,
366 primaryKey.keyLength = GetKeyLength(btreePtr, primaryKey.keyPtr, (level == 1));
372 err = InsertLevel (btreePtr, treePathTable, &primaryKey, nil,
382 OSStatus InsertLevel (BTreeControlBlockPtr btreePtr,
412 ModifyBlockStart(btreePtr->fileRefNum, targetNode);
416 err = InsertNode (btreePtr, primaryKey, targetNode, targetNodeNum, index,
429 treePathTable [level + 1].node = btreePtr->rootNode;
442 err = InsertNode (btreePtr, secondaryKey, targetNode, newNodeNum, newIndex,
465 PanicIf ( (level == btreePtr->treeDepth), "\p InsertLevel: unfinished insert!?");
475 err = GetNode (btreePtr, parentNodeNum, 0, &parentNode); // released as target node in next level up
486 ModifyBlockStart(btreePtr->fileRefNum, &parentNode);
489 GetRecordByIndex (btreePtr, parentNode.buffer, index, &keyPtr, &recPtr, &recSize);
495 DeleteRecord (btreePtr, parentNode.buffer, index);
497 primaryKey->keyPtr = (KeyPtr) GetRecordAddress( btreePtr, targetNode->buffer, 0 );
498 primaryKey->keyLength = GetKeyLength(btreePtr, primaryKey->keyPtr, false);
521 insertKeyPtr->keyPtr = (KeyPtr) GetRecordAddress (btreePtr, leftNode.buffer, 0);
522 insertKeyPtr->keyLength = GetKeyLength(btreePtr, insertKeyPtr->keyPtr, false);
529 err = InsertLevel (btreePtr, treePathTable, primaryKey, secondaryKey,
534 err = UpdateNode (btreePtr, targetNode, 0, kLockTransaction); // all done with target
537 err = UpdateNode (btreePtr, &leftNode, 0, kLockTransaction); // all done with left sibling
544 (void) ReleaseNode (btreePtr, targetNode);
545 (void) ReleaseNode (btreePtr, &leftNode);
557 static OSErr InsertNode (BTreeControlBlockPtr btreePtr,
603 recordFit = InsertKeyRecord (btreePtr, targetNode->buffer, index, key->keyPtr, key->keyLength, key->recPtr, key->recSize);
610 if ( (index == 0) && (((NodeDescPtr) targetNode->buffer)->height != btreePtr->treeDepth) )
623 err = GetNode (btreePtr, leftNodeNum, 0, leftNode); // will be released by caller or a split below
626 ModifyBlockStart(btreePtr->fileRefNum, leftNode);
633 err = RotateLeft (btreePtr, leftNode->buffer, rightNode->buffer, index, key->keyPtr, key->recPtr,
651 err = SplitLeft (btreePtr, leftNode, rightNode, node, index, key->keyPtr,
657 if ( ((NodeDescPtr) rightNode->buffer)->height == btreePtr->treeDepth )
659 err = AddNewRootNode (btreePtr, leftNode->buffer, rightNode->buffer); // Note: does not update TPT
675 (void) ReleaseNode (btreePtr, leftNode);
688 Input: btreePtr - description
697 OSStatus DeleteTree (BTreeControlBlockPtr btreePtr,
723 ModifyBlockStart(btreePtr->fileRefNum, targetNode);
725 DeleteRecord (btreePtr, targetNodePtr, index);
744 err = GetNode (btreePtr, siblingNodeNum, 0, &siblingNode);
748 ModifyBlockStart(btreePtr->fileRefNum, &siblingNode);
751 err = UpdateNode (btreePtr, &siblingNode, 0, kLockTransaction);
756 btreePtr->firstLeafNode = targetNodePtr->fLink;
762 err = GetNode (btreePtr, siblingNodeNum, 0, &siblingNode);
766 ModifyBlockStart(btreePtr->fileRefNum, &siblingNode);
769 err = UpdateNode (btreePtr, &siblingNode, 0, kLockTransaction);
774 btreePtr->lastLeafNode = targetNodePtr->bLink;
779 ClearNode (btreePtr, targetNodePtr);
781 err = UpdateNode (btreePtr, targetNode, 0, kLockTransaction);
784 err = FreeNode (btreePtr, targetNodeNum);
793 if ( level == btreePtr->treeDepth ) // then targetNode->buffer is the root node
800 btreePtr->rootNode = 0;
801 btreePtr->treeDepth = 0;
805 err = CollapseTree (btreePtr, targetNode);
817 err = GetNode (btreePtr, treePathTable[level].node, 0, &parentNode);
828 ModifyBlockStart(btreePtr->fileRefNum, &parentNode);
831 GetRecordByIndex (btreePtr, parentNode.buffer, index, &keyPtr, &recPtr, &recSize);
835 DeleteRecord (btreePtr, parentNode.buffer, index);
837 keyPtr = (KeyPtr) GetRecordAddress( btreePtr, targetNode->buffer, 0 );
841 err = InsertTree (btreePtr, treePathTable, keyPtr, recPtr, recSize,
847 err = DeleteTree (btreePtr, treePathTable, &parentNode, index, level);
853 err = UpdateNode (btreePtr, targetNode, 0, kLockTransaction);
860 (void) ReleaseNode (btreePtr, targetNode);
861 (void) ReleaseNode (btreePtr, &parentNode);
871 static OSStatus CollapseTree (BTreeControlBlockPtr btreePtr,
878 originalRoot = btreePtr->rootNode;
881 ModifyBlockStart(btreePtr->fileRefNum, blockPtr);
891 nodeNum = btreePtr->rootNode;
892 btreePtr->rootNode = GetChildNodeNum (btreePtr, blockPtr->buffer, 0);
893 --btreePtr->treeDepth;
896 ClearNode (btreePtr, blockPtr->buffer);
897 err = UpdateNode (btreePtr, blockPtr, 0, kLockTransaction);
899 err = FreeNode (btreePtr, nodeNum);
903 err = GetNode (btreePtr, btreePtr->rootNode, 0, blockPtr);
907 ModifyBlockStart(btreePtr->fileRefNum, blockPtr);
910 if (btreePtr->rootNode != originalRoot)
911 M_BTreeHeaderDirty (btreePtr);
913 err = UpdateNode (btreePtr, blockPtr, 0, kLockTransaction); // always update!
922 (void) ReleaseNode (btreePtr, blockPtr);
938 Input: btreePtr - description
955 static OSStatus RotateLeft (BTreeControlBlockPtr btreePtr,
979 keyLength = GetKeyLength(btreePtr, keyPtr, (rightNode->kind == kBTLeafNode));
982 if ( btreePtr->attributes & kBTBigKeysMask )
992 nodeSize = btreePtr->nodeSize;
995 rightSize = nodeSize - GetNodeFreeSize (btreePtr, rightNode) + insertSize;
996 leftSize = nodeSize - GetNodeFreeSize (btreePtr, leftNode);
1004 moveSize = GetRecordSize (btreePtr, rightNode, moveIndex) + 2;
1012 moveSize = GetRecordSize (btreePtr, rightNode, moveIndex - 1) + 2;
1054 didItFit = InsertKeyRecord (btreePtr, leftNode, leftInsertIndex,
1068 didItFit = RotateRecordLeft (btreePtr, leftNode, rightNode);
1084 didItFit = InsertKeyRecord (btreePtr, rightNode, rightInsertIndex,
1117 static OSStatus SplitLeft (BTreeControlBlockPtr btreePtr,
1162 err = AllocateNode (btreePtr, &newNodeNum);
1171 ModifyBlockStart(btreePtr->fileRefNum, leftNode);
1174 err = UpdateNode (btreePtr, leftNode, 0, kLockTransaction);
1181 err = GetNewNode (btreePtr, newNodeNum, leftNode);
1185 ModifyBlockStart(btreePtr->fileRefNum, leftNode);
1203 btreePtr->firstLeafNode = newNodeNum;
1204 M_BTreeHeaderDirty (btreePtr); //�� AllocateNode should have set the bit already...
1209 err = RotateLeft (btreePtr, left, right, index, keyPtr, recPtr, recSize,
1218 (void) ReleaseNode (btreePtr, leftNode);
1219 (void) ReleaseNode (btreePtr, rightNode);
1234 static Boolean RotateRecordLeft (BTreeControlBlockPtr btreePtr,
1242 size = GetRecordSize (btreePtr, rightNode, 0);
1243 recPtr = GetRecordAddress (btreePtr, rightNode, 0);
1245 recordFit = InsertRecord (btreePtr, leftNode, leftNode->numRecords, recPtr, size);
1250 DeleteRecord (btreePtr, rightNode, 0);
1258 static OSStatus AddNewRootNode (BTreeControlBlockPtr btreePtr,
1278 err = AllocateNode (btreePtr, &rootNum);
1281 err = GetNewNode (btreePtr, rootNum, &rootNode);
1285 ModifyBlockStart(btreePtr->fileRefNum, &rootNode);
1288 ((NodeDescPtr)rootNode.buffer)->height = ++btreePtr->treeDepth;
1293 keyPtr = (KeyPtr) GetRecordAddress (btreePtr, leftNode, 0);
1294 keyLength = GetKeyLength(btreePtr, keyPtr, false);
1296 didItFit = InsertKeyRecord ( btreePtr, rootNode.buffer, 0, keyPtr, keyLength,
1304 keyPtr = (KeyPtr) GetRecordAddress (btreePtr, rightNode, 0);
1305 keyLength = GetKeyLength(btreePtr, keyPtr, false);
1307 didItFit = InsertKeyRecord ( btreePtr, rootNode.buffer, 1, keyPtr, keyLength,
1315 err = UpdateNode (btreePtr, &rootNode, 0, kLockTransaction);
1320 btreePtr->rootNode = rootNum;
1321 btreePtr->flags |= kBTHeaderDirty;
1334 static u_int16_t GetKeyLength ( const BTreeControlBlock *btreePtr, const BTreeKey *key, Boolean forLeafNode )
1338 if ( forLeafNode || btreePtr->attributes & kBTVariableIndexKeysMask )
1339 length = KeyLength (btreePtr, key); // just use actual key length
1341 length = btreePtr->maxKeyLength; // fixed sized index key (i.e. HFS) //�� shouldn't we clear the pad bytes?