![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to BTreeNodeOps.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple XNU] / XNU / bsd / hfs / hfscommon / BTree|
Return to BTreeNodeOps.c CVS log | Up to [Apple XNU] / XNU / bsd / hfs / hfscommon / BTree |
1.1 root 1: /*
2: * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
3: *
4: * @APPLE_LICENSE_HEADER_START@
5: *
6: * The contents of this file constitute Original Code as defined in and
7: * are subject to the Apple Public Source License Version 1.1 (the
8: * "License"). You may not use this file except in compliance with the
9: * License. Please obtain a copy of the License at
10: * http://www.apple.com/publicsource and read it before using this file.
11: *
12: * This Original Code and all software distributed under the License are
13: * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
14: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
15: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
16: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
17: * License for the specific language governing rights and limitations
18: * under the License.
19: *
20: * @APPLE_LICENSE_HEADER_END@
21: */
22: /*
23: File: BTreeNodeOps.c
24:
25: Contains: Single-node operations for the BTree Module.
26:
27: Version: xxx put the technology version here xxx
28:
29: Written by: Gordon Sheridan and Bill Bruffey
30:
31: Copyright: � 1992-1999 by Apple Computer, Inc., all rights reserved.
32:
33: File Ownership:
34:
35: DRI: Don Brady
36:
37: Other Contact: Mark Day
38:
39: Technology: File Systems
40:
41: Writers:
42:
43: (msd) Mark Day
44: (djb) Don Brady
45:
46: Change History (most recent first):
47:
48: <MOSXS> 6/1/99 djb Sync up with Mac OS 8.6.
49: <MOSXS> 4/113/99 djb Fix key size checking bug in CheckNode.
50: <MOSXS> 3/19/99 djb Added key size checking to CheckNode.
51: <MOSXS> 3/26/98 djb Added PrintNode for debugging.
52: <CS5> 9/4/97 djb Removed GetRightSiblingNode and GetLeftSiblingNode - they are
53: now macros. SearchNode is now in BTreeSearchNode.a.
54: <CS4> 8/22/97 djb Turn off debugging code in CheckKey.
55: <CS3> 7/24/97 djb Add summary traces for Get/Rel Node. Made GetRecordOffset into a
56: macro. Only call CheckNode if the node came from disk.
57: <CS2> 7/21/97 msd Make GetRecordByIndex check its record index input; it now
58: returns an OSStatus.
59: <CS1> 4/23/97 djb first checked in
60:
61: <HFS3> 2/19/97 djb Changes to support big node cache.
62: <HFS2> 1/3/97 djb Added support for large keys.
63: <HFS1> 12/19/96 djb first checked in
64:
65:
66: History applicable to original Scarecrow Design:
67:
68: <6> 10/25/96 ser Changing for new VFPI
69: <5> 9/17/96 dkh Add bounds checking to GetNode. Update GetNode to not assert
70: that CheckNode failed if the node is all zeroes. This can happen
71: if the hint case if the fetched node has been deallocated
72: <4> 3/7/96 dkh Change GetNewNode() to not use kGetEmptyBlock. Instead use
73: kGetBlock to fetch a block from the disk itself. ��� Why?
74: <3> 1/22/96 dkh Add #include Memory.h
75: <2> 1/10/96 msd Change 64-bit math to use real function names from Math64.i.
76: <1> 10/18/95 rst Moved from Scarecrow project.
77:
78: <17> 7/18/95 mbb Change MoveData & ClearBytes to BlockMoveData & BlockZero.
79: <16> 1/31/95 prp GetBlockProc interface uses a 64 bit node number.
80: <15> 1/12/95 wjk Adopt Model FileSystem changes in D5.
81: <14> 9/30/94 prp Get in sync with D2 interface changes.
82: <13> 7/25/94 wjk Eliminate usage of BytePtr in favor of UInt8 *.
83: <12> 7/22/94 wjk Convert to the new set of header files.
84: <11> 12/2/93 wjk Move from Makefiles to BuildFiles. Fit into the ModernOS and
85: NRCmds environments.
86: <10> 11/30/93 wjk Change some Ptr's to BytePtr's in function definitions so they
87: agree with their prototypes.
88: <9> 8/31/93 prp Use U64SetU instead of S64Set.
89: <8> 5/21/93 gs Maintain statistical counters on Get/Release node routines.
90: <7> 5/10/93 gs Change keySize parameter to keyLength for InsertKeyRecord
91: routine. Calculate number of bytes in key from keyLength to
92: account for length and pad bytes. Add GetChildNodeNum routine.
93: <6> 3/23/93 gs Add InsertKeyRecord routine.
94: <5> 2/8/93 gs Fix bug in SearchNode that caused "off by 1" error when final
95: compare was searchKey > trialKey. Add UpdateNode.
96: <4> 12/10/92 gs Change keyLength field of key to 'length'.
97: <3> 12/8/92 gs Incorporate suggestions from preliminary code review.
98: <2> 12/2/92 gs Implement routines.
99: <1> 11/15/92 gs Define routine interfaces.
100:
101: */
102:
103: #include "../headers/BTreesPrivate.h"
104: #include "../headers/HFSInstrumentation.h"
105:
106:
107:
108: ///////////////////////// BTree Module Node Operations //////////////////////////
109: //
110: // GetNode - Call FS Agent to get node
111: // GetNewNode - Call FS Agent to get a new node
112: // ReleaseNode - Call FS Agent to release node obtained by GetNode.
113: // UpdateNode - Mark a node as dirty and call FS Agent to release it.
114: //
115: // CheckNode - Checks the validity of a node.
116: // ClearNode - Clear a node to all zeroes.
117: //
118: // InsertRecord - Inserts a record into a BTree node.
119: // InsertKeyRecord - Inserts a key and record pair into a BTree node.
120: // DeleteRecord - Deletes a record from a BTree node.
121: //
122: // SearchNode - Return index for record that matches key.
123: // LocateRecord - Return pointer to key and data, and size of data.
124: //
125: // GetNodeDataSize - Return the amount of space used for data in the node.
126: // GetNodeFreeSize - Return the amount of free space in the node.
127: //
128: // GetRecordOffset - Return the offset for record "index".
129: // GetRecordAddress - Return address of record "index".
130: // GetOffsetAddress - Return address of offset for record "index".
131: //
132: // InsertOffset - Inserts a new offset into a node.
133: // DeleteOffset - Deletes an offset from a node.
134: //
135: // MoveRecordsLeft - Move records left within a node.
136: // MoveRecordsRight - Move records right within a node.
137: //
138: /////////////////////////////////////////////////////////////////////////////////
139:
140:
141:
142: ////////////////////// Routines Internal To BTreeNodeOps.c //////////////////////
143:
144: UInt16 GetRecordOffset (BTreeControlBlockPtr btree,
145: NodeDescPtr node,
146: UInt16 index );
147:
148: UInt16 *GetOffsetAddress (BTreeControlBlockPtr btreePtr,
149: NodeDescPtr node,
150: UInt16 index );
151:
152: void InsertOffset (BTreeControlBlockPtr btreePtr,
153: NodeDescPtr node,
154: UInt16 index,
155: UInt16 delta );
156:
157: void DeleteOffset (BTreeControlBlockPtr btreePtr,
158: NodeDescPtr node,
159: UInt16 index );
160:
161:
162: /////////////////////////////////////////////////////////////////////////////////
163:
164: #define GetRecordOffset(btreePtr,node,index) (*(short *) ((UInt8 *)(node) + (btreePtr)->nodeSize - ((index) << 1) - kOffsetSize))
165:
166: #if HFS_DIAGNOSTIC
167: #include <sys/systm.h>
168: #define PRINTIT kprintf
169: #endif /* HFS_DIAGNOSTIC */
170:
171: static void PrintNode(const NodeDescPtr node, UInt16 nodeSize, UInt32 nodeNumber);
172:
173:
174:
175: /*-------------------------------------------------------------------------------
176:
177: Routine: GetNode - Call FS Agent to get node
178:
179: Function: Gets an existing BTree node from FS Agent and verifies it.
180:
181: Input: btreePtr - pointer to BTree control block
182: nodeNum - number of node to request
183:
184: Output: nodePtr - pointer to beginning of node (nil if error)
185:
186: Result:
187: noErr - success
188: != noErr - failure
189: -------------------------------------------------------------------------------*/
190:
191: OSStatus GetNode (BTreeControlBlockPtr btreePtr,
192: UInt32 nodeNum,
193: NodeRec *nodePtr )
194: {
195: OSStatus err;
196: GetBlockProcPtr getNodeProc;
197:
198:
199: LogStartTime(kTraceGetNode);
200:
201: //�� is nodeNum within proper range?
202: if( nodeNum >= btreePtr->totalNodes )
203: {
204: Panic("\pGetNode:nodeNum >= totalNodes");
205: err = fsBTInvalidNodeErr;
206: goto ErrorExit;
207: }
208:
209: nodePtr->blockSize = btreePtr->nodeSize; // indicate the size of a node
210:
211: getNodeProc = btreePtr->getBlockProc;
212: err = getNodeProc (btreePtr->fileRefNum,
213: nodeNum,
214: kGetBlock,
215: nodePtr );
216:
217: if (err != noErr)
218: {
219: Panic ("\pGetNode: getNodeProc returned error.");
220: // nodePtr->buffer = nil;
221: goto ErrorExit;
222: }
223: ++btreePtr->numGetNodes;
224:
225: //
226: // Optimization
227: // Only call CheckNode if the node came from disk.
228: // If it was in the cache, we'll assume its already a valid node.
229: //
230:
231: if ( nodePtr->blockReadFromDisk ) // if we read it from disk then check it
232: {
233: err = CheckNode (btreePtr, nodePtr->buffer);
234:
235: if (err != noErr)
236: {
237:
238: VTOVCB(btreePtr->fileRefNum)->vcbFlags |= kHFS_DamagedVolume;
239:
240: #if HFS_DIAGNOSTIC
241: if (((NodeDescPtr)nodePtr->buffer)->numRecords != 0)
242: PrintNode(nodePtr->buffer, btreePtr->nodeSize, nodeNum);
243: #endif
244:
245: if (DEBUG_BUILD)
246: {
247: // With the removal of bounds checking in IsItAHint(), it's possible that
248: // GetNode() will be called to fetch a clear (all zeroes) node. We want
249: // CheckNode() to fail in this case (it does), however we don't want to assert
250: // this case because it is not really an "error". Returning an error from GetNode()
251: // in this case will cause the hint checking code to ignore the hint and revert to
252: // the full search mode.
253:
254: {
255: UInt32 *cur;
256: UInt32 *lastPlusOne;
257:
258: cur = nodePtr->buffer;
259: lastPlusOne = (UInt32 *) ((UInt8 *) cur + btreePtr->nodeSize);
260:
261: while( cur < lastPlusOne )
262: {
263: if( *cur++ != 0 )
264: {
265: Panic ("\pGetNode: CheckNode returned error.");
266: break;
267: }
268: }
269: }
270: }
271:
272: (void) ReleaseNode (btreePtr, nodePtr); // ignore error
273: goto ErrorExit;
274: }
275: }
276:
277: LogEndTime(kTraceGetNode, noErr);
278:
279: return noErr;
280:
281: ErrorExit:
282: nodePtr->buffer = nil;
283: nodePtr->blockHeader = nil;
284:
285: LogEndTime(kTraceGetNode, err);
286:
287: return err;
288: }
289:
290:
291:
292: /*-------------------------------------------------------------------------------
293:
294: Routine: GetNewNode - Call FS Agent to get a new node
295:
296: Function: Gets a new BTree node from FS Agent and initializes it to an empty
297: state.
298:
299: Input: btreePtr - pointer to BTree control block
300: nodeNum - number of node to request
301:
302: Output: returnNodePtr - pointer to beginning of node (nil if error)
303:
304: Result: noErr - success
305: != noErr - failure
306: -------------------------------------------------------------------------------*/
307:
308: OSStatus GetNewNode (BTreeControlBlockPtr btreePtr,
309: UInt32 nodeNum,
310: NodeRec *returnNodePtr )
311: {
312: OSStatus err;
313: NodeDescPtr node;
314: void *pos;
315: GetBlockProcPtr getNodeProc;
316:
317:
318: //////////////////////// get buffer for new node ////////////////////////////
319:
320: returnNodePtr->blockSize = btreePtr->nodeSize; // indicate the size of a node
321:
322: getNodeProc = btreePtr->getBlockProc;
323: err = getNodeProc (btreePtr->fileRefNum,
324: nodeNum,
325: kGetBlock+kGetEmptyBlock,
326: returnNodePtr );
327:
328: if (err != noErr)
329: {
330: Panic ("\pGetNewNode: getNodeProc returned error.");
331: // returnNodePtr->buffer = nil;
332: return err;
333: }
334: ++btreePtr->numGetNewNodes;
335:
336:
337: ////////////////////////// initialize the node //////////////////////////////
338:
339: node = returnNodePtr->buffer;
340:
341: ClearNode (btreePtr, node); // clear the node
342:
343: pos = (char *)node + btreePtr->nodeSize - 2; // find address of last offset
344: *(UInt16 *)pos = sizeof (BTNodeDescriptor); // set offset to beginning of free space
345:
346:
347: return noErr;
348: }
349:
350:
351:
352: /*-------------------------------------------------------------------------------
353:
354: Routine: ReleaseNode - Call FS Agent to release node obtained by GetNode.
355:
356: Function: Informs the FS Agent that a BTree node may be released.
357:
358: Input: btreePtr - pointer to BTree control block
359: nodeNum - number of node to release
360:
361: Result: noErr - success
362: != noErr - failure
363: -------------------------------------------------------------------------------*/
364:
365: OSStatus ReleaseNode (BTreeControlBlockPtr btreePtr,
366: NodePtr nodePtr )
367: {
368: OSStatus err;
369: ReleaseBlockProcPtr releaseNodeProc;
370:
371:
372: LogStartTime(kTraceReleaseNode);
373:
374: err = noErr;
375:
376: if (nodePtr->buffer != nil)
377: {
378: releaseNodeProc = btreePtr->releaseBlockProc;
379: err = releaseNodeProc (btreePtr->fileRefNum,
380: nodePtr,
381: kReleaseBlock );
382: PanicIf (err, "\pReleaseNode: releaseNodeProc returned error.");
383: ++btreePtr->numReleaseNodes;
384: }
385:
386: nodePtr->buffer = nil;
387: nodePtr->blockHeader = nil;
388:
389: LogEndTime(kTraceReleaseNode, err);
390:
391: return err;
392: }
393:
394:
395:
396: /*-------------------------------------------------------------------------------
397:
398: Routine: UpdateNode - Mark a node as dirty and call FS Agent to release it.
399:
400: Function: Marks a BTree node dirty and informs the FS Agent that it may be released.
401:
402: //�� have another routine that clears & writes a node, so we can call
403: CheckNode from this routine.
404:
405: Input: btreePtr - pointer to BTree control block
406: nodeNum - number of node to release
407: transactionID - ID of transaction this node update is a part of
408: flags - special flags to pass to ReleaseNodeProc
409:
410: Result: noErr - success
411: != noErr - failure
412: -------------------------------------------------------------------------------*/
413:
414: OSStatus UpdateNode (BTreeControlBlockPtr btreePtr,
415: NodePtr nodePtr,
416: UInt32 transactionID,
417: UInt32 flags )
418: {
419: OSStatus err;
420: ReleaseBlockProcPtr releaseNodeProc;
421:
422:
423: err = noErr;
424:
425: if (nodePtr->buffer != nil) //�� why call UpdateNode if nil ?!?
426: {
427: if (DEBUG_BUILD)
428: {
429: if ( btreePtr->attributes & kBTVariableIndexKeysMask )
430: (void) CheckNode (btreePtr, nodePtr->buffer);
431: }
432:
433: LogStartTime(kTraceReleaseNode);
434:
435: releaseNodeProc = btreePtr->releaseBlockProc;
436: err = releaseNodeProc (btreePtr->fileRefNum,
437: nodePtr,
438: flags | kMarkBlockDirty );
439:
440: LogEndTime(kTraceReleaseNode, err);
441:
442: M_ExitOnError (err);
443: ++btreePtr->numUpdateNodes;
444: }
445:
446: nodePtr->buffer = nil;
447: nodePtr->blockHeader = nil;
448:
449: return noErr;
450:
451: ErrorExit:
452:
453: return err;
454: }
455:
456:
457:
458: /*-------------------------------------------------------------------------------
459:
460: Routine: CheckNode - Checks the validity of a node.
461:
462: Function: Checks the validity of a node by verifying that the fLink and bLink fields
463: are within the forks EOF. The node type must be one of the four known
464: types. The node height must be less than or equal to the tree height. The
465: node must not have more than the maximum number of records, and the record
466: offsets must make sense.
467:
468: Input: btreePtr - pointer to BTree control block
469: node - pointer to node to check
470:
471: Result: noErr - success
472: fsBTInvalidNodeErr - failure
473: -------------------------------------------------------------------------------*/
474:
475: OSStatus CheckNode (BTreeControlBlockPtr btreePtr, NodeDescPtr node )
476: {
477: SInt32 index;
478: SInt32 maxRecords;
479: UInt32 maxNode;
480: UInt16 nodeSize;
481: UInt16 offset;
482: UInt16 prevOffset;
483:
484: nodeSize = btreePtr->nodeSize;
485:
486: ///////////////////// are fLink and bLink within EOF ////////////////////////
487:
488: maxNode = (GetFileControlBlock(btreePtr->fileRefNum)->fcbEOF / nodeSize) - 1;
489:
490: if ( (node->fLink > maxNode) || (node->bLink > maxNode) )
491: return fsBTInvalidNodeErr;
492:
493: /////////////// check node type (leaf, index, header, map) //////////////////
494:
495: if ( (node->kind < kBTLeafNode) || (node->kind > kBTMapNode) )
496: return fsBTInvalidNodeErr;
497:
498: ///////////////////// is node height > tree depth? //////////////////////////
499:
500: if ( node->height > btreePtr->treeDepth )
501: return fsBTInvalidNodeErr;
502:
503: //////////////////////// check number of records ////////////////////////////
504:
505: //XXX can we calculate a more accurate minimum record size?
506: maxRecords = ( nodeSize - sizeof (BTNodeDescriptor) ) >> 3;
507:
508: if (node->numRecords > maxRecords)
509: return fsBTInvalidNodeErr;
510:
511: ////////////////////////// check record offsets /////////////////////////////
512:
513: index = node->numRecords; /* start index at free space */
514: prevOffset = nodeSize - (index << 1); /* use 2 bytes past end of free space */
515:
516: do {
517: offset = GetRecordOffset (btreePtr, node, index);
518:
519: if (offset & 1) // offset is odd
520: return fsBTInvalidNodeErr;
521:
522: if (offset >= prevOffset) // offset >= previous offset
523: return fsBTInvalidNodeErr;
524:
525: /* reject keys that overflow record slot */
526: if ((node->kind == kBTLeafNode) &&
527: (index < node->numRecords) && /* ignore free space record */
528: (CalcKeySize(btreePtr, (KeyPtr) ((Ptr)node + offset)) > (prevOffset - offset))) {
529: return fsBTInvalidNodeErr;
530: }
531:
532: prevOffset = offset;
533: } while ( --index >= 0 );
534:
535: if (offset < sizeof (BTNodeDescriptor) ) // first offset < minimum ?
536: return fsBTInvalidNodeErr;
537:
538: return noErr;
539: }
540:
541:
542: #if HFS_DIAGNOSTIC
543: static void PrintNode(const NodeDescPtr node, UInt16 nodeSize, UInt32 nodeNumber)
544: {
545: struct row {
546: UInt16 word[8];
547: };
548: struct row *offset;
549: UInt16 rows;
550: UInt32 *lp;
551:
552: PRINTIT("Dump of B-tree node #%ld ($%08lX)\n", nodeNumber, nodeNumber);
553:
554: rows = nodeSize/16;
555: lp = (UInt32*) node;
556: offset = 0;
557:
558: while (rows-- > 0)
559: PRINTIT("%04X: %08lX %08lX %08lX %08lX\n", (u_int)offset++, *lp++, *lp++, *lp++, *lp++);
560: }
561: #endif
562:
563:
564: /*-------------------------------------------------------------------------------
565:
566: Routine: ClearNode - Clear a node to all zeroes.
567:
568: Function: Writes zeroes from beginning of node for nodeSize bytes.
569:
570: Input: btreePtr - pointer to BTree control block
571: node - pointer to node to clear
572:
573: Result: none
574: -------------------------------------------------------------------------------*/
575:
576: void ClearNode (BTreeControlBlockPtr btreePtr, NodeDescPtr node )
577: {
578: ClearMemory( node, btreePtr->nodeSize );
579: }
580:
581: /*-------------------------------------------------------------------------------
582:
583: Routine: InsertRecord - Inserts a record into a BTree node.
584:
585: Function:
586:
587: Note: Record size must be even!
588:
589: Input: btreePtr - pointer to BTree control block
590: node - pointer to node to insert the record
591: index - position record is to be inserted
592: recPtr - pointer to record to insert
593:
594: Result: noErr - success
595: fsBTFullErr - record larger than remaining free space.
596: -------------------------------------------------------------------------------*/
597:
598: Boolean InsertRecord (BTreeControlBlockPtr btreePtr,
599: NodeDescPtr node,
600: UInt16 index,
601: RecordPtr recPtr,
602: UInt16 recSize )
603: {
604: UInt16 freeSpace;
605: UInt16 indexOffset;
606: UInt16 freeOffset;
607: UInt16 bytesToMove;
608: void *src;
609: void *dst;
610:
611: //// will new record fit in node?
612:
613: freeSpace = GetNodeFreeSize (btreePtr, node);
614: //�� we could get freeOffset & calc freeSpace
615: if ( freeSpace < recSize + 2)
616: {
617: return false;
618: }
619:
620:
621: //// make hole for new record
622:
623: indexOffset = GetRecordOffset (btreePtr, node, index);
624: freeOffset = GetRecordOffset (btreePtr, node, node->numRecords);
625:
626: src = ((Ptr) node) + indexOffset;
627: dst = ((Ptr) src) + recSize;
628: bytesToMove = freeOffset - indexOffset;
629: MoveRecordsRight (src, dst, bytesToMove);
630:
631:
632: //// adjust offsets for moved records
633:
634: InsertOffset (btreePtr, node, index, recSize);
635:
636:
637: //// move in the new record
638:
639: dst = ((Ptr) node) + indexOffset;
640: MoveRecordsLeft (recPtr, dst, recSize);
641:
642: return true;
643: }
644:
645:
646:
647: /*-------------------------------------------------------------------------------
648:
649: Routine: InsertKeyRecord - Inserts a record into a BTree node.
650:
651: Function:
652:
653: Note: Record size must be even!
654:
655: Input: btreePtr - pointer to BTree control block
656: node - pointer to node to insert the record
657: index - position record is to be inserted
658: keyPtr - pointer to key for record to insert
659: keyLength - length of key (or maxKeyLength)
660: recPtr - pointer to record to insert
661: recSize - number of bytes to copy for record
662:
663: Result: noErr - success
664: fsBTFullErr - record larger than remaining free space.
665: -------------------------------------------------------------------------------*/
666:
667: Boolean InsertKeyRecord (BTreeControlBlockPtr btreePtr,
668: NodeDescPtr node,
669: UInt16 index,
670: KeyPtr keyPtr,
671: UInt16 keyLength,
672: RecordPtr recPtr,
673: UInt16 recSize )
674: {
675: UInt16 freeSpace;
676: UInt16 indexOffset;
677: UInt16 freeOffset;
678: UInt16 bytesToMove;
679: UInt8 * src;
680: UInt8 * dst;
681: UInt16 keySize;
682: UInt16 rawKeyLength;
683: UInt16 sizeOfLength;
684:
685: //// calculate actual key size
686:
687: if ( btreePtr->attributes & kBTBigKeysMask )
688: keySize = keyLength + sizeof(UInt16);
689: else
690: keySize = keyLength + sizeof(UInt8);
691:
692: if ( M_IsOdd (keySize) )
693: ++keySize; // add pad byte
694:
695:
696: //// will new record fit in node?
697:
698: freeSpace = GetNodeFreeSize (btreePtr, node);
699: //�� we could get freeOffset & calc freeSpace
700: if ( freeSpace < keySize + recSize + 2)
701: {
702: return false;
703: }
704:
705:
706: //// make hole for new record
707:
708: indexOffset = GetRecordOffset (btreePtr, node, index);
709: freeOffset = GetRecordOffset (btreePtr, node, node->numRecords);
710:
711: src = ((UInt8 *) node) + indexOffset;
712: dst = ((UInt8 *) src) + keySize + recSize;
713: bytesToMove = freeOffset - indexOffset;
714: MoveRecordsRight (src, dst, bytesToMove);
715:
716:
717: //// adjust offsets for moved records
718:
719: InsertOffset (btreePtr, node, index, keySize + recSize);
720:
721:
722: //// copy record key
723:
724: dst = ((UInt8 *) node) + indexOffset;
725:
726: if ( btreePtr->attributes & kBTBigKeysMask )
727: {
728: *((UInt16*) dst)++ = keyLength; // use keyLength rather than key.length
729: rawKeyLength = keyPtr->length16;
730: sizeOfLength = 2;
731: }
732: else
733: {
734: *dst++ = keyLength; // use keyLength rather than key.length
735: rawKeyLength = keyPtr->length8;
736: sizeOfLength = 1;
737: }
738:
739: MoveRecordsLeft ( ((UInt8 *) keyPtr) + sizeOfLength, dst, rawKeyLength); // copy key
740:
741: // any pad bytes?
742: bytesToMove = keySize - rawKeyLength;
743: if (bytesToMove)
744: ClearMemory (dst + rawKeyLength, bytesToMove); // clear pad bytes in index key
745:
746:
747: //// copy record data
748:
749: dst = ((UInt8 *) node) + indexOffset + keySize;
750: MoveRecordsLeft (recPtr, dst, recSize);
751:
752: return true;
753: }
754:
755:
756:
757: /*-------------------------------------------------------------------------------
758:
759: Routine: DeleteRecord - Deletes a record from a BTree node.
760:
761: Function:
762:
763: Input: btreePtr - pointer to BTree control block
764: node - pointer to node to insert the record
765: index - position record is to be inserted
766:
767: Result: none
768: -------------------------------------------------------------------------------*/
769:
770: void DeleteRecord (BTreeControlBlockPtr btreePtr,
771: NodeDescPtr node,
772: UInt16 index )
773: {
774: SInt16 indexOffset;
775: SInt16 nextOffset;
776: SInt16 freeOffset;
777: SInt16 bytesToMove;
778: void *src;
779: void *dst;
780:
781: //// compress records
782: indexOffset = GetRecordOffset (btreePtr, node, index);
783: nextOffset = GetRecordOffset (btreePtr, node, index + 1);
784: freeOffset = GetRecordOffset (btreePtr, node, node->numRecords);
785:
786: src = ((Ptr) node) + nextOffset;
787: dst = ((Ptr) node) + indexOffset;
788: bytesToMove = freeOffset - nextOffset;
789: MoveRecordsLeft (src, dst, bytesToMove);
790:
791: //// Adjust the offsets
792: DeleteOffset (btreePtr, node, index);
793:
794: /* clear out new free space */
795: bytesToMove = nextOffset - indexOffset;
796: ClearMemory(GetRecordAddress(btreePtr, node, node->numRecords), bytesToMove);
797:
798: }
799:
800:
801:
802: /*-------------------------------------------------------------------------------
803:
804: Routine: SearchNode - Return index for record that matches key.
805:
806: Function: Returns the record index for the record that matches the search key.
807: If no record was found that matches the search key, the "insert index"
808: of where the record should go is returned instead.
809:
810: Algorithm: A binary search algorithm is used to find the specified key.
811:
812: Input: btreePtr - pointer to BTree control block
813: node - pointer to node that contains the record
814: searchKey - pointer to the key to match
815:
816: Output: index - pointer to beginning of key for record
817:
818: Result: true - success (index = record index)
819: false - key did not match anything in node (index = insert index)
820: -------------------------------------------------------------------------------*/
821: Boolean
822: SearchNode( BTreeControlBlockPtr btreePtr,
823: NodeDescPtr node,
824: KeyPtr searchKey,
825: UInt16 *returnIndex )
826: {
827: SInt32 lowerBound;
828: SInt32 upperBound;
829: SInt32 index;
830: SInt32 result;
831: KeyPtr trialKey;
832: UInt16 *offset;
833: KeyCompareProcPtr compareProc = btreePtr->keyCompareProc;
834:
835: lowerBound = 0;
836: upperBound = node->numRecords - 1;
837: offset = (UInt16 *) ((UInt8 *)(node) + (btreePtr)->nodeSize - kOffsetSize);
838:
839: while (lowerBound <= upperBound) {
840: index = (lowerBound + upperBound) >> 1;
841:
842: trialKey = (KeyPtr) ((UInt8 *)node + *(offset - index));
843:
844: result = compareProc(searchKey, trialKey);
845:
846: if (result < 0) {
847: upperBound = index - 1; /* search < trial */
848: } else if (result > 0) {
849: lowerBound = index + 1; /* search > trial */
850: } else {
851: *returnIndex = index; /* search == trial */
852: return true;
853: }
854: }
855:
856: *returnIndex = lowerBound; /* lowerBound is insert index */
857: return false;
858: }
859:
860:
861: /*-------------------------------------------------------------------------------
862:
863: Routine: GetRecordByIndex - Return pointer to key and data, and size of data.
864:
865: Function: Returns a pointer to beginning of key for record, a pointer to the
866: beginning of the data for the record, and the size of the record data
867: (does not include the size of the key).
868:
869: Input: btreePtr - pointer to BTree control block
870: node - pointer to node that contains the record
871: index - index of record to get
872:
873: Output: keyPtr - pointer to beginning of key for record
874: dataPtr - pointer to beginning of data for record
875: dataSize - size of the data portion of the record
876:
877: Result: none
878: -------------------------------------------------------------------------------*/
879:
880: OSStatus GetRecordByIndex (BTreeControlBlockPtr btreePtr,
881: NodeDescPtr node,
882: UInt16 index,
883: KeyPtr *keyPtr,
884: UInt8 * *dataPtr,
885: UInt16 *dataSize )
886: {
887: UInt16 offset;
888: UInt16 nextOffset;
889: UInt16 keySize;
890:
891: //
892: // Make sure index is valid (in range 0..numRecords-1)
893: //
894: if (index >= node->numRecords)
895: return fsBTRecordNotFoundErr;
896:
897: //// find keyPtr
898: offset = GetRecordOffset (btreePtr, node, index);
899: *keyPtr = (KeyPtr) ((Ptr)node + offset);
900:
901: //// find dataPtr
902: keySize = CalcKeySize(btreePtr, *keyPtr);
903: if ( M_IsOdd (keySize) )
904: ++keySize; // add pad byte
905:
906: offset += keySize; // add the key length to find data offset
907: *dataPtr = (UInt8 *) node + offset;
908:
909: //// find dataSize
910: nextOffset = GetRecordOffset (btreePtr, node, index + 1);
911: *dataSize = nextOffset - offset;
912:
913: return noErr;
914: }
915:
916:
917:
918: /*-------------------------------------------------------------------------------
919:
920: Routine: GetNodeDataSize - Return the amount of space used for data in the node.
921:
922: Function: Gets the size of the data currently contained in a node, excluding
923: the node header. (record data + offset overhead)
924:
925: Input: btreePtr - pointer to BTree control block
926: node - pointer to node that contains the record
927:
928: Result: - number of bytes used for data and offsets in the node.
929: -------------------------------------------------------------------------------*/
930:
931: UInt16 GetNodeDataSize (BTreeControlBlockPtr btreePtr, NodeDescPtr node )
932: {
933: UInt16 freeOffset;
934:
935: freeOffset = GetRecordOffset (btreePtr, node, node->numRecords);
936:
937: return freeOffset + (node->numRecords << 1) - sizeof (BTNodeDescriptor);
938: }
939:
940:
941:
942: /*-------------------------------------------------------------------------------
943:
944: Routine: GetNodeFreeSize - Return the amount of free space in the node.
945:
946: Function:
947:
948: Input: btreePtr - pointer to BTree control block
949: node - pointer to node that contains the record
950:
951: Result: - number of bytes of free space in the node.
952: -------------------------------------------------------------------------------*/
953:
954: UInt16 GetNodeFreeSize (BTreeControlBlockPtr btreePtr, NodeDescPtr node )
955: {
956: UInt16 freeOffset;
957:
958: freeOffset = GetRecordOffset (btreePtr, node, node->numRecords); //�� inline?
959:
960: return btreePtr->nodeSize - freeOffset - (node->numRecords << 1) - kOffsetSize;
961: }
962:
963:
964:
965: /*-------------------------------------------------------------------------------
966:
967: Routine: GetRecordOffset - Return the offset for record "index".
968:
969: Function:
970:
971: Input: btreePtr - pointer to BTree control block
972: node - pointer to node that contains the record
973: index - record to obtain offset for
974:
975: Result: - offset (in bytes) from beginning of node of record specified by index
976: -------------------------------------------------------------------------------*/
977: // make this a macro (for inlining)
978: #if 0
979: UInt16 GetRecordOffset (BTreeControlBlockPtr btreePtr,
980: NodeDescPtr node,
981: UInt16 index )
982: {
983: void *pos;
984:
985:
986: pos = (UInt8 *)node + btreePtr->nodeSize - (index << 1) - kOffsetSize;
987:
988: return *(short *)pos;
989: }
990: #endif
991:
992:
993:
994: /*-------------------------------------------------------------------------------
995:
996: Routine: GetRecordAddress - Return address of record "index".
997:
998: Function:
999:
1000: Input: btreePtr - pointer to BTree control block
1001: node - pointer to node that contains the record
1002: index - record to obtain offset address for
1003:
1004: Result: - pointer to record "index".
1005: -------------------------------------------------------------------------------*/
1006: // make this a macro (for inlining)
1007: #if 0
1008: UInt8 * GetRecordAddress (BTreeControlBlockPtr btreePtr,
1009: NodeDescPtr node,
1010: UInt16 index )
1011: {
1012: UInt8 * pos;
1013:
1014: pos = (UInt8 *)node + GetRecordOffset (btreePtr, node, index);
1015:
1016: return pos;
1017: }
1018: #endif
1019:
1020:
1021:
1022: /*-------------------------------------------------------------------------------
1023:
1024: Routine: GetRecordSize - Return size of record "index".
1025:
1026: Function:
1027:
1028: Note: This does not work on the FreeSpace index!
1029:
1030: Input: btreePtr - pointer to BTree control block
1031: node - pointer to node that contains the record
1032: index - record to obtain record size for
1033:
1034: Result: - size of record "index".
1035: -------------------------------------------------------------------------------*/
1036:
1037: UInt16 GetRecordSize (BTreeControlBlockPtr btreePtr,
1038: NodeDescPtr node,
1039: UInt16 index )
1040: {
1041: UInt16 *pos;
1042:
1043: pos = (UInt16 *) ((Ptr)node + btreePtr->nodeSize - (index << 1) - kOffsetSize);
1044:
1045: return *(pos-1) - *pos;
1046: }
1047:
1048:
1049:
1050: /*-------------------------------------------------------------------------------
1051: Routine: GetOffsetAddress - Return address of offset for record "index".
1052:
1053: Function:
1054:
1055: Input: btreePtr - pointer to BTree control block
1056: node - pointer to node that contains the record
1057: index - record to obtain offset address for
1058:
1059: Result: - pointer to offset for record "index".
1060: -------------------------------------------------------------------------------*/
1061:
1062: UInt16 *GetOffsetAddress (BTreeControlBlockPtr btreePtr,
1063: NodeDescPtr node,
1064: UInt16 index )
1065: {
1066: void *pos;
1067:
1068: pos = (Ptr)node + btreePtr->nodeSize - (index << 1) -2;
1069:
1070: return (UInt16 *)pos;
1071: }
1072:
1073:
1074:
1075: /*-------------------------------------------------------------------------------
1076: Routine: GetChildNodeNum - Return child node number from index record "index".
1077:
1078: Function: Returns the first UInt32 stored after the key for record "index".
1079:
1080: Assumes: The node is an Index Node.
1081: The key.length stored at record "index" is ODD. //�� change for variable length index keys
1082:
1083: Input: btreePtr - pointer to BTree control block
1084: node - pointer to node that contains the record
1085: index - record to obtain child node number from
1086:
1087: Result: - child node number from record "index".
1088: -------------------------------------------------------------------------------*/
1089:
1090: UInt32 GetChildNodeNum (BTreeControlBlockPtr btreePtr,
1091: NodeDescPtr nodePtr,
1092: UInt16 index )
1093: {
1094: UInt8 * pos;
1095:
1096: pos = GetRecordAddress (btreePtr, nodePtr, index);
1097: pos += CalcKeySize(btreePtr, (BTreeKey *) pos); // key.length + size of length field
1098:
1099: return *(UInt32 *)pos;
1100: }
1101:
1102:
1103:
1104: /*-------------------------------------------------------------------------------
1105: Routine: InsertOffset - Add an offset and adjust existing offsets by delta.
1106:
1107: Function: Add an offset at 'index' by shifting 'index+1' through the last offset
1108: and adjusting them by 'delta', the size of the record to be inserted.
1109: The number of records contained in the node is also incremented.
1110:
1111: Input: btreePtr - pointer to BTree control block
1112: node - pointer to node
1113: index - index at which to insert record
1114: delta - size of record to be inserted
1115:
1116: Result: none
1117: -------------------------------------------------------------------------------*/
1118:
1119: void InsertOffset (BTreeControlBlockPtr btreePtr,
1120: NodeDescPtr node,
1121: UInt16 index,
1122: UInt16 delta )
1123: {
1124: UInt16 *src, *dst;
1125: UInt16 numOffsets;
1126:
1127: src = GetOffsetAddress (btreePtr, node, node->numRecords); // point to free offset
1128: dst = src - 1; // point to new offset
1129: numOffsets = node->numRecords++ - index; // subtract index & postincrement
1130:
1131: do {
1132: *dst++ = *src++ + delta; // to tricky?
1133: } while (numOffsets--);
1134: }
1135:
1136:
1137:
1138: /*-------------------------------------------------------------------------------
1139:
1140: Routine: DeleteOffset - Delete an offset.
1141:
1142: Function: Delete the offset at 'index' by shifting 'index+1' through the last offset
1143: and adjusting them by the size of the record 'index'.
1144: The number of records contained in the node is also decremented.
1145:
1146: Input: btreePtr - pointer to BTree control block
1147: node - pointer to node
1148: index - index at which to delete record
1149:
1150: Result: none
1151: -------------------------------------------------------------------------------*/
1152:
1153: void DeleteOffset (BTreeControlBlockPtr btreePtr,
1154: NodeDescPtr node,
1155: UInt16 index )
1156: {
1157: UInt16 *src, *dst;
1158: UInt16 numOffsets;
1159: UInt16 delta;
1160:
1161: dst = GetOffsetAddress (btreePtr, node, index);
1162: src = dst - 1;
1163: delta = *src - *dst;
1164: numOffsets = --node->numRecords - index; // predecrement numRecords & subtract index
1165:
1166: while (numOffsets--)
1167: {
1168: *--dst = *--src - delta; // work our way left
1169: }
1170: }
1171:
1172:
1173:
1174: /*-------------------------------------------------------------------------------
1175:
1176: Routine: MoveRecordsLeft - Move records left within a node.
1177:
1178: Function: Moves a number of bytes from src to dst. Safely handles overlapping
1179: ranges if the bytes are being moved to the "left". No bytes are moved
1180: if bytesToMove is zero.
1181:
1182: Input: src - pointer to source
1183: dst - pointer to destination
1184: bytesToMove - number of bytes to move records
1185:
1186: Result: none
1187: -------------------------------------------------------------------------------*/
1188: #if BCOPY_BROKEN
1189: void MoveRecordsLeft (UInt8 * src,
1190: UInt8 * dst,
1191: UInt16 bytesToMove )
1192: {
1193: while (bytesToMove--)
1194: *dst++ = *src++;
1195: }
1196: #endif
1197:
1198:
1199: /*-------------------------------------------------------------------------------
1200:
1201: Routine: MoveRecordsRight - Move records right within a node.
1202:
1203: Function: Moves a number of bytes from src to dst. Safely handles overlapping
1204: ranges if the bytes are being moved to the "right". No bytes are moved
1205: if bytesToMove is zero.
1206:
1207: Input: src - pointer to source
1208: dst - pointer to destination
1209: bytesToMove - number of bytes to move records
1210:
1211: Result: none
1212: -------------------------------------------------------------------------------*/
1213: #if BCOPY_BROKEN
1214: void MoveRecordsRight (UInt8 * src,
1215: UInt8 * dst,
1216: UInt16 bytesToMove )
1217: {
1218: src += bytesToMove;
1219: dst += bytesToMove;
1220:
1221: while (bytesToMove--)
1222: *--dst = *--src;
1223: }
1224: #endif
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.