![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to BTreeScanner.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple Darwin 0.x] / kernel / bsd / hfs / hfscommon / BTree|
Return to BTreeScanner.c CVS log | Up to [Apple Darwin 0.x] / kernel / bsd / hfs / hfscommon / BTree |
1.1 ! root 1: /* ! 2: * Copyright (c) 1999 Apple Computer, Inc. All rights reserved. ! 3: * ! 4: * @APPLE_LICENSE_HEADER_START@ ! 5: * ! 6: * Portions Copyright (c) 1999 Apple Computer, Inc. All Rights ! 7: * Reserved. This file contains Original Code and/or Modifications of ! 8: * Original Code as defined in and that are subject to the Apple Public ! 9: * Source License Version 1.1 (the "License"). You may not use this file ! 10: * except in compliance with the License. Please obtain a copy of the ! 11: * License at http://www.apple.com/publicsource and read it before using ! 12: * this file. ! 13: * ! 14: * The Original Code and all software distributed under the License are ! 15: * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER ! 16: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, ! 17: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, ! 18: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the ! 19: * License for the specific language governing rights and limitations ! 20: * under the License. ! 21: * ! 22: * @APPLE_LICENSE_HEADER_END@ ! 23: */ ! 24: ! 25: /* ! 26: File: BTreeScanner.c ! 27: ! 28: Contains: Routines for quick reading of B-Tree records (not in sorted order). ! 29: ! 30: Using a caller-supplied buffer, these routines read in a buffer full ! 31: of B-tree nodes. Pointers to the leaf records' key and data are ! 32: returned one at a time. The buffer is refilled as needed. It is the ! 33: caller's responsibility to flush any changes to the B-tree before ! 34: starting a scan. ! 35: ! 36: These routines were designed for use by CatSearch and MountCheck. ! 37: ! 38: NOTE: Records will not be returned in sorted order. Within a given node, ! 39: they will be in order, but the nodes may not be read in sorted order. ! 40: ! 41: Version: HFS Plus 1.0 ! 42: ! 43: Written by: Mark Day ! 44: ! 45: Copyright: � 1997 by Apple Computer, Inc., all rights reserved. ! 46: ! 47: File Ownership: ! 48: ! 49: DRI: Mark Day ! 50: ! 51: Other Contact: Don Brady ! 52: ! 53: Technology: File Systems ! 54: ! 55: Writers: ! 56: ! 57: (msd) Mark Day ! 58: (DSH) Deric Horn ! 59: (djb) Don Brady ! 60: ! 61: Change History (most recent first): ! 62: ! 63: <CS3> 8/1/97 msd Don't prefill node buffer in BTScanInitialize (fixes MountCheck ! 64: error with empty extents B-Tree). Remove extraneous enum for ! 65: timeOutErr. ! 66: <CS2> 7/30/97 DSH Casting for SC, needed for DFA compiles. ! 67: <CS1> 7/28/97 msd first checked in ! 68: <0> 7/24/97 msd Begin implementation. ! 69: ! 70: */ ! 71: ! 72: #include "../headers/FileMgrInternal.h" ! 73: #include "../headers/HFSBtreesPriv.h" ! 74: #include "../headers/BTreesPrivate.h" ! 75: #include "../headers/BTreeScanner.h" ! 76: ! 77: ! 78: //====================================================================== ! 79: // Exported Routines: ! 80: // ! 81: // BTScanInitialize - Set up to start or resume a scan ! 82: // BTScanTerminate - Obtain state to later resume a scan ! 83: // BTScanNextRecord - Get the next record ! 84: // BTScanCacheNode - Make sure the current node is in the cache ! 85: // ! 86: // Internal Routines: ! 87: // ! 88: // FindNextLeafNode - Point to the next leaf node after the current ! 89: // node. More nodes will be read if needed (and ! 90: // allowed by the caller). ! 91: // ReadMultipleNodes - Read one or more nodes into a buffer. ! 92: //====================================================================== ! 93: ! 94: ! 95: ! 96: ! 97: OSErr FindNextLeafNode(BTScanState *scanState, Boolean avoidIO); ! 98: OSErr ReadMultipleNodes(BTScanState *scanState); ! 99: ! 100: ! 101: ! 102: ! 103: //_________________________________________________________________________________ ! 104: // ! 105: // Routine: BTScanInitialize ! 106: // ! 107: // Purpose: Prepare to start a new BTree scan, or resume a previous one. ! 108: // ! 109: // Inputs: ! 110: // btreeFile The B-Tree's file control block ! 111: // startingNode Initial node number ! 112: // startingRecord Initial record number within node ! 113: // recordsFound Number of valid records found so far ! 114: // buffer Start of buffer used to hold B-Tree data ! 115: // bufferSize Size (in bytes) of buffer ! 116: // ! 117: // Outputs: ! 118: // scanState Scanner's current state; pass to other scanner calls ! 119: // ! 120: // Notes: ! 121: // To begin a new scan and see all records in the B-Tree, pass zeroes for ! 122: // startingNode, startingRecord, and recordsFound. ! 123: // ! 124: // To resume a scan from the point of a previous BTScanTerminate, use the ! 125: // values returned by BTScanTerminate as input for startingNode, startingRecord, ! 126: // and recordsFound. ! 127: // ! 128: // When resuming a scan, the caller should check the B-tree's write count. If ! 129: // it is different from the write count when the scan was terminated, then the ! 130: // tree may have changed and the current state may be incorrect. In particular, ! 131: // you may see some records more than once, or never see some records. Also, ! 132: // the scanner may not be able to detect when all leaf records have been seen, ! 133: // and will have to scan through many empty nodes. ! 134: // ! 135: // ���Perhaps the write count should be managed by BTScanInitialize and ! 136: // �� BTScanTerminate? This would avoid the caller having to peek at ! 137: // �� internal B-Tree structures. ! 138: //_________________________________________________________________________________ ! 139: ! 140: OSErr BTScanInitialize( ! 141: const FCB * btreeFile, ! 142: UInt32 startingNode, ! 143: UInt32 startingRecord, ! 144: UInt32 recordsFound, ! 145: void * buffer, ! 146: UInt32 bufferSize, ! 147: BTScanState * scanState) ! 148: { ! 149: BTreeControlBlock *btcb; ! 150: ! 151: // ! 152: // Make sure this is a valid B-Tree file ! 153: // ! 154: btcb = (BTreeControlBlock *) btreeFile->fcbBTCBPtr; ! 155: if (btcb == NULL) ! 156: return fsBTInvalidFileErr; ! 157: ! 158: // ! 159: // Make sure buffer size is big enough, and a multiple of the ! 160: // B-Tree node size ! 161: // ! 162: if (buffer == NULL || bufferSize < btcb->nodeSize) ! 163: return paramErr; ! 164: bufferSize = (bufferSize / btcb->nodeSize) * btcb->nodeSize; ! 165: ! 166: // ! 167: // Set up the scanner's state ! 168: // ! 169: scanState->buffer = buffer; ! 170: scanState->bufferSize = bufferSize; ! 171: scanState->btcb = btcb; ! 172: scanState->nodeNum = startingNode; ! 173: scanState->recordNum = startingRecord; ! 174: scanState->currentNode = buffer; ! 175: scanState->nodesLeftInBuffer = 0; // no nodes currently in buffer ! 176: scanState->recordsFound = recordsFound; ! 177: scanState->lastCachedNode = 0; // no nodes have been cached ! 178: ! 179: ! 180: return noErr; ! 181: } ! 182: ! 183: ! 184: ! 185: //_________________________________________________________________________________ ! 186: // ! 187: // Routine: BTScanTerminate ! 188: // ! 189: // Purpose: Return state information about a scan so that it can be resumed ! 190: // later via BTScanInitialize. ! 191: // ! 192: // Inputs: ! 193: // scanState Scanner's current state ! 194: // ! 195: // Outputs: ! 196: // nextNode Node number to resume a scan (pass to BTScanInitialize) ! 197: // nextRecord Record number to resume a scan (pass to BTScanInitialize) ! 198: // recordsFound Valid records seen so far (pass to BTScanInitialize) ! 199: //_________________________________________________________________________________ ! 200: ! 201: OSErr BTScanTerminate( ! 202: const BTScanState * scanState, ! 203: UInt32 * startingNode, ! 204: UInt32 * startingRecord, ! 205: UInt32 * recordsFound) ! 206: { ! 207: *startingNode = scanState->nodeNum; ! 208: *startingRecord = scanState->recordNum; ! 209: *recordsFound = scanState->recordsFound; ! 210: ! 211: return noErr; ! 212: } ! 213: ! 214: ! 215: ! 216: //_________________________________________________________________________________ ! 217: // ! 218: // Routine: BTScanNextRecord ! 219: // ! 220: // Purpose: Return the next leaf record in a scan. ! 221: // ! 222: // Inputs: ! 223: // scanState Scanner's current state ! 224: // avoidIO If true, don't do any I/O to refill the buffer ! 225: // ! 226: // Outputs: ! 227: // key Key of found record (points into buffer) ! 228: // data Data of found record (points into buffer) ! 229: // dataSize Size of data in found record ! 230: // ! 231: // Result: ! 232: // noErr Found a valid record ! 233: // btNotFound No more records ! 234: // ??? Needed to do I/O to get next node, but avoidIO set ! 235: // ! 236: // Notes: ! 237: // This routine returns pointers to the found record's key and data. It ! 238: // does not copy the key or data to a caller-supplied buffer (like ! 239: // GetBTreeRecord would). The caller must not modify the key or data. ! 240: //_________________________________________________________________________________ ! 241: ! 242: OSErr BTScanNextRecord( ! 243: BTScanState * scanState, ! 244: Boolean avoidIO, ! 245: void * * key, ! 246: void * * data, ! 247: UInt32 * dataSize) ! 248: { ! 249: OSStatus err; ! 250: UInt16 dataSizeShort; ! 251: ! 252: err = noErr; ! 253: ! 254: // ! 255: // If this is the first call, there won't be any nodes in the buffer, so go ! 256: // find the first first leaf node (if any). ! 257: // ! 258: if (scanState->nodesLeftInBuffer == 0) ! 259: err = FindNextLeafNode(scanState, avoidIO); ! 260: ! 261: while (err == noErr) { ! 262: // See if we have a record in the current node ! 263: err = GetRecordByIndex(scanState->btcb, scanState->currentNode, scanState->recordNum, ! 264: (KeyPtr *) key, (UInt8 **) data, &dataSizeShort); ! 265: if (err == noErr) { ! 266: ++scanState->recordsFound; ! 267: ++scanState->recordNum; ! 268: *dataSize = dataSizeShort; ! 269: return noErr; ! 270: } ! 271: ! 272: // We're done with the current node. See if we've returned all the records ! 273: if (scanState->recordsFound >= scanState->btcb->leafRecords) ! 274: return btNotFound; ! 275: ! 276: // Move to the first record of the next leaf node ! 277: scanState->recordNum = 0; ! 278: err = FindNextLeafNode(scanState, avoidIO); ! 279: } ! 280: ! 281: // ! 282: // If we got an EOF error from FindNextLeafNode, then there are no more leaf ! 283: // records to be found. ! 284: // ! 285: if (err == eofErr) ! 286: err = btNotFound; ! 287: ! 288: return err; ! 289: } ! 290: ! 291: ! 292: ! 293: //_________________________________________________________________________________ ! 294: // ! 295: // Routine: BTScanCacheNode ! 296: // ! 297: // Purpose: Make sure that the node just returned is in the cache. ! 298: // ! 299: // Inputs: ! 300: // scanState Scanner's current state ! 301: //_________________________________________________________________________________ ! 302: ! 303: OSErr BTScanCacheNode(BTScanState *scanState) ! 304: { ! 305: OSStatus err; ! 306: NodeRec nodeRec; ! 307: ! 308: err = noErr; ! 309: ! 310: if (scanState->lastCachedNode != scanState->nodeNum) { ! 311: err = GetNode(scanState->btcb, scanState->nodeNum, &nodeRec); ! 312: if (err == noErr) ! 313: err = ReleaseNode(scanState->btcb, &nodeRec); ! 314: scanState->lastCachedNode = scanState->nodeNum; ! 315: } ! 316: ! 317: return err; ! 318: } ! 319: ! 320: ! 321: ! 322: //_________________________________________________________________________________ ! 323: // ! 324: // Routine: FindNextLeafNode ! 325: // ! 326: // Purpose: Point to the next leaf node in the buffer. Read more nodes ! 327: // into the buffer if needed (and allowed). ! 328: // ! 329: // Inputs: ! 330: // scanState Scanner's current state ! 331: // avoidIO If true, don't do any I/O to refill the buffer ! 332: // ! 333: // Result: ! 334: // noErr Found a valid record ! 335: // eofErr No more nodes in file ! 336: // ??? Needed to do I/O to get next node, but avoidIO set ! 337: //_________________________________________________________________________________ ! 338: ! 339: OSErr FindNextLeafNode(BTScanState *scanState, Boolean avoidIO) ! 340: { ! 341: OSErr err; ! 342: ! 343: err = noErr; // Assume everything will be OK ! 344: ! 345: while (1) { ! 346: if (scanState->nodesLeftInBuffer == 0) { ! 347: // Time to read some more nodes into the buffer ! 348: if (avoidIO) { ! 349: return fsBTTimeOutErr; ! 350: } ! 351: else { ! 352: // read some more nodes into buffer ! 353: scanState->currentNode = scanState->buffer; ! 354: err = ReadMultipleNodes(scanState); ! 355: if (err != noErr) break; ! 356: } ! 357: } ! 358: else { ! 359: // Adjust the node counters and point to the next node in the buffer ! 360: ++scanState->nodeNum; ! 361: --scanState->nodesLeftInBuffer; ! 362: (UInt8 *) scanState->currentNode += scanState->btcb->nodeSize; ! 363: ! 364: // If we've looked at all nodes in the tree, then we're done ! 365: if (scanState->nodeNum > scanState->btcb->totalNodes) ! 366: return eofErr; ! 367: } ! 368: ! 369: //�� CheckNode returns an error on empty nodes (all zeros) ! 370: // err = CheckNode(scanState->btcb, scanState->currentNode); ! 371: // if (err != noErr) break; ! 372: ! 373: if (scanState->currentNode->type == kLeafNode) ! 374: break; ! 375: } ! 376: ! 377: return err; ! 378: } ! 379: ! 380: ! 381: ! 382: //_________________________________________________________________________________ ! 383: // ! 384: // Routine: ReadMultipleNodes ! 385: // ! 386: // Purpose: Read one or more nodes into the buffer. ! 387: // ! 388: // Inputs: ! 389: // scanState Scanner's current state ! 390: // ! 391: // Result: ! 392: // noErr One or nodes were read ! 393: // eofErr No nodes left in file, none in buffer ! 394: //_________________________________________________________________________________ ! 395: ! 396: OSErr ReadMultipleNodes(BTScanState *scanState) ! 397: { ! 398: #if TARGET_OS_MAC ! 399: OSErr err = noErr; ! 400: UInt32 nodeSize; // size of one B-Tree node ! 401: UInt32 currentPosition; // current offset in bytes from start of B-Tree file ! 402: UInt32 bytesToRead; // number of bytes left to read into buffer ! 403: ExtendedVCB *vcb; // volume that B-Tree resides on ! 404: UInt32 actualBytes; // bytes actually read by CacheReadInPlace ! 405: HIOParam iopb; // used by CacheReadInPlace ! 406: ! 407: nodeSize = scanState->btcb->nodeSize; ! 408: vcb = GetFileControlBlock(scanState->btcb->fileRefNum)->fcbVPtr; ! 409: ! 410: iopb.ioRefNum = scanState->btcb->fileRefNum; ! 411: iopb.ioPermssn = fsRdPerm; ! 412: iopb.ioBuffer = scanState->buffer; ! 413: iopb.ioPosMode = fsAtMark | (noCacheMask << 8); ! 414: iopb.ioActCount = 0; ! 415: ! 416: currentPosition = scanState->nodeNum * nodeSize; ! 417: bytesToRead = scanState->bufferSize; ! 418: ! 419: while (bytesToRead > 0) { ! 420: err = CacheReadInPlace(vcb, &iopb, currentPosition, bytesToRead, &actualBytes); ! 421: ! 422: if (err != noErr || actualBytes == 0) ! 423: break; ! 424: ! 425: bytesToRead -= actualBytes; ! 426: iopb.ioActCount += actualBytes; ! 427: currentPosition += actualBytes; ! 428: } ! 429: ! 430: scanState->nodesLeftInBuffer = iopb.ioActCount / nodeSize; ! 431: ! 432: if (err == fxRangeErr && iopb.ioActCount == 0) ! 433: err = eofErr; ! 434: else ! 435: err = noErr; ! 436: ! 437: if (scanState->nodesLeftInBuffer == 0 && err == noErr) ! 438: err = eofErr; ! 439: ! 440: return err; ! 441: #else ! 442: #pragma unused(scanState) ! 443: return noErr; ! 444: #endif ! 445: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.