![[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.