![[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 Darwin 0.x] / kernel / bsd / hfs / hfscommon / BTree|
Return to BTreeNodeOps.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: BTreeNodeOps.c
27:
28: Contains: Single-node operations for the BTree Module.
29:
30: Version: xxx put the technology version here xxx
31:
32: Written by: Gordon Sheridan and Bill Bruffey
33:
34: Copyright: � 1992-1997 by Apple Computer, Inc., all rights reserved.
35:
36: File Ownership:
37:
38: DRI: Don Brady
39:
40: Other Contact: Mark Day
41:
42: Technology: File Systems
43:
44: Writers:
45:
46: (msd) Mark Day
47: (djb) Don Brady
48:
49: Change History (most recent first):
50:
51: <Rhap1> 3/26/97 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/system/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 TARGET_OS_RHAPSODY && DIAGNOSTIC
167: #ifdef KERNEL
168: #include <sys/systm.h>
169: #define PRINTIT kprintf
170: #else /* !KERNEL */
171: #define PRINTIT printf
172: #endif /* KERNEL */
173:
174: static void PrintNode(const NodeDescPtr node, UInt16 nodeSize, UInt32 nodeNumber);
175: #endif
176:
177:
178:
179: /*-------------------------------------------------------------------------------
180:
181: Routine: GetNode - Call FS Agent to get node
182:
183: Function: Gets an existing BTree node from FS Agent and verifies it.
184:
185: Input: btreePtr - pointer to BTree control block
186: nodeNum - number of node to request
187:
188: Output: nodePtr - pointer to beginning of node (nil if error)
189:
190: Result:
191: noErr - success
192: != noErr - failure
193: -------------------------------------------------------------------------------*/
194:
195: OSStatus GetNode (BTreeControlBlockPtr btreePtr,
196: UInt32 nodeNum,
197: NodeRec *nodePtr )
198: {
199: OSStatus err;
200: GetBlockProcPtr getNodeProc;
201:
202:
203: LogStartTime(kTraceGetNode);
204:
205: //�� is nodeNum within proper range?
206: if( nodeNum >= btreePtr->totalNodes )
207: {
208: Panic("\pGetNode:nodeNum >= totalNodes");
209: err = fsBTInvalidNodeErr;
210: goto ErrorExit;
211: }
212:
213: nodePtr->blockSize = btreePtr->nodeSize; // indicate the size of a node
214:
215: getNodeProc = btreePtr->getBlockProc;
216: err = getNodeProc (btreePtr->fileRefNum,
217: nodeNum,
218: kGetBlock,
219: nodePtr );
220:
221: if (err != noErr)
222: {
223: Panic ("\pGetNode: getNodeProc returned error.");
224: goto ErrorExit;
225: }
226: ++btreePtr->numGetNodes;
227:
228: //
229: // Optimization
230: // Only call CheckNode if the node came from disk.
231: // If it was in the cache, we'll assume its already a valid node.
232: //
233:
234: if ( nodePtr->blockReadFromDisk ) // if we read it from disk then check it
235: {
236: err = CheckNode (btreePtr, nodePtr->buffer);
237:
238: if (err != noErr)
239: {
240: #if TARGET_OS_RHAPSODY && 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: return err;
332: }
333: ++btreePtr->numGetNewNodes;
334:
335:
336: ////////////////////////// initialize the node //////////////////////////////
337:
338: node = returnNodePtr->buffer;
339:
340: ClearNode (btreePtr, node); // clear the node
341:
342: pos = (char *)node + btreePtr->nodeSize - 2; // find address of last offset
343: *(UInt16 *)pos = sizeof (BTNodeDescriptor); // set offset to beginning of free space
344:
345:
346: return noErr;
347: }
348:
349:
350:
351: /*-------------------------------------------------------------------------------
352:
353: Routine: ReleaseNode - Call FS Agent to release node obtained by GetNode.
354:
355: Function: Informs the FS Agent that a BTree node may be released.
356:
357: Input: btreePtr - pointer to BTree control block
358: nodeNum - number of node to release
359:
360: Result: noErr - success
361: != noErr - failure
362: -------------------------------------------------------------------------------*/
363:
364: OSStatus ReleaseNode (BTreeControlBlockPtr btreePtr,
365: NodePtr nodePtr )
366: {
367: OSStatus err;
368: ReleaseBlockProcPtr releaseNodeProc;
369:
370:
371: LogStartTime(kTraceReleaseNode);
372:
373: err = noErr;
374:
375: if (nodePtr->buffer != nil)
376: {
377: releaseNodeProc = btreePtr->releaseBlockProc;
378: err = releaseNodeProc (btreePtr->fileRefNum,
379: nodePtr,
380: kReleaseBlock );
381: PanicIf (err, "\pReleaseNode: releaseNodeProc returned error.");
382: ++btreePtr->numReleaseNodes;
383: }
384:
385: nodePtr->buffer = nil;
386: nodePtr->blockHeader = nil;
387:
388: LogEndTime(kTraceReleaseNode, err);
389:
390: return err;
391: }
392:
393:
394:
395: /*-------------------------------------------------------------------------------
396:
397: Routine: UpdateNode - Mark a node as dirty and call FS Agent to release it.
398:
399: Function: Marks a BTree node dirty and informs the FS Agent that it may be released.
400:
401: //�� have another routine that clears & writes a node, so we can call
402: CheckNode from this routine.
403:
404: Input: btreePtr - pointer to BTree control block
405: nodeNum - number of node to release
406:
407: Result: noErr - success
408: != noErr - failure
409: -------------------------------------------------------------------------------*/
410:
411: OSStatus UpdateNode (BTreeControlBlockPtr btreePtr,
412: NodePtr nodePtr )
413: {
414: OSStatus err;
415: ReleaseBlockProcPtr releaseNodeProc;
416:
417:
418: err = noErr;
419:
420: if (nodePtr->buffer != nil) //�� why call UpdateNode if nil ?!?
421: {
422: if (DEBUG_BUILD)
423: {
424: if ( btreePtr->attributes & kBTVariableIndexKeysMask )
425: (void) CheckNode (btreePtr, nodePtr->buffer);
426: }
427:
428: LogStartTime(kTraceReleaseNode);
429:
430: releaseNodeProc = btreePtr->releaseBlockProc;
431: err = releaseNodeProc (btreePtr->fileRefNum,
432: nodePtr,
433: kMarkBlockDirty );
434:
435: LogEndTime(kTraceReleaseNode, err);
436:
437: M_ExitOnError (err);
438: ++btreePtr->numUpdateNodes;
439: }
440:
441: nodePtr->buffer = nil;
442: nodePtr->blockHeader = nil;
443:
444: return noErr;
445:
446: ErrorExit:
447:
448: return err;
449: }
450:
451:
452:
453: /*-------------------------------------------------------------------------------
454:
455: Routine: CheckNode - Checks the validity of a node.
456:
457: Function: Checks the validity of a node by verifying that the fLink and bLink fields
458: are within the forks EOF. The node type must be one of the four known
459: types. The node height must be less than or equal to the tree height. The
460: node must not have more than the maximum number of records, and the record
461: offsets must make sense.
462:
463: Input: btreePtr - pointer to BTree control block
464: node - pointer to node to check
465:
466: Result: noErr - success
467: fsBTInvalidNodeErr - failure
468: -------------------------------------------------------------------------------*/
469:
470: OSStatus CheckNode (BTreeControlBlockPtr btreePtr, NodeDescPtr node )
471: {
472: SInt32 index;
473: SInt32 maxRecords;
474: UInt32 maxNode;
475: UInt16 nodeSize;
476: UInt16 offset;
477: UInt16 prevOffset;
478:
479: #if DEBUG_BUILD
480: KeyPtr thisKey, lastKey = NULL;
481: KeyCompareProcPtr compareProc = NULL;
482: #endif
483:
484:
485: nodeSize = btreePtr->nodeSize;
486:
487: ///////////////////// are fLink and bLink within EOF ////////////////////////
488:
489: maxNode = (GetFileControlBlock(btreePtr->fileRefNum)->fcbEOF / nodeSize) - 1;
490:
491: if ( (node->fLink > maxNode) || (node->bLink > maxNode) )
492: return fsBTInvalidNodeErr;
493:
494:
495: /////////////// check node type (leaf, index, header, map) //////////////////
496:
497: if ( (node->type < kLeafNode) || (node->type > kMapNode) )
498: return fsBTInvalidNodeErr;
499:
500:
501: ///////////////////// is node height > tree depth? //////////////////////////
502:
503: if ( node->height > btreePtr->treeDepth )
504: return fsBTInvalidNodeErr;
505:
506:
507: //////////////////////// check number of records ////////////////////////////
508:
509: //�� can we calculate a more accurate minimum record size?
510: maxRecords = ( nodeSize - sizeof (BTNodeDescriptor) ) >> 3;
511:
512: if (node->numRecords > maxRecords)
513: return fsBTInvalidNodeErr;
514:
515:
516: ////////////////////////// check record offsets /////////////////////////////
517:
518: index = node->numRecords; // begin with free space offset
519: offset = nodeSize - (index << 1); // init offset to max free offset+2
520:
521: #if DEBUG_BUILD
522: if ( btreePtr->attributes & kBTVariableIndexKeysMask )
523: {
524: compareProc = btreePtr->keyCompareProc;
525: lastKey = NULL;
526: }
527: #endif
528:
529: do {
530: prevOffset = offset;
531: offset = GetRecordOffset (btreePtr, node, index);
532:
533: #if DEBUG_BUILD
534: if ( btreePtr->attributes & kBTVariableIndexKeysMask &&
535: index < node->numRecords &&
536: (node->type == kLeafNode || node->type == kIndexNode) )
537: {
538: thisKey = (KeyPtr) GetRecordAddress (btreePtr, node, index );
539:
540: if ( (lastKey != NULL) && (compareProc(thisKey, lastKey) >= 0) )
541: {
542: Panic ( "\p CheckNode: keys out of order! ");
543: return fsBTInvalidNodeErr;
544: }
545:
546: lastKey = thisKey;
547: }
548: #endif
549:
550: if (offset < sizeof (BTNodeDescriptor) ) // offset < minimum
551: return fsBTInvalidNodeErr;
552:
553: if (offset & 1) // offset is odd
554: return fsBTInvalidNodeErr;
555:
556: if (offset >= prevOffset) // offset >= previous offset
557: return fsBTInvalidNodeErr;
558:
559: if (offset >= nodeSize) // offset beyond end of node
560: return fsBTInvalidNodeErr;
561:
562: } while ( --index >= 0 );
563:
564:
565: return noErr;
566: }
567:
568:
569: #if TARGET_OS_RHAPSODY && DIAGNOSTIC
570: static void PrintNode(const NodeDescPtr node, UInt16 nodeSize, UInt32 nodeNumber)
571: {
572: struct row {
573: UInt16 word[8];
574: };
575: struct row *offset;
576: UInt16 rows;
577: UInt32 *lp;
578:
579: PRINTIT("Dump of B-tree node #%ld ($%08lX)\n", nodeNumber, nodeNumber);
580:
581: rows = nodeSize/16;
582: lp = (UInt32*) node;
583: offset = 0;
584:
585: while (rows-- > 0)
586: PRINTIT("%04X: %08lX %08lX %08lX %08lX\n", (u_int)offset++, *lp++, *lp++, *lp++, *lp++);
587: }
588: #endif
589:
590:
591: /*-------------------------------------------------------------------------------
592:
593: Routine: ClearNode - Clear a node to all zeroes.
594:
595: Function: Writes zeroes from beginning of node for nodeSize bytes.
596:
597: Input: btreePtr - pointer to BTree control block
598: node - pointer to node to clear
599:
600: Result: none
601: -------------------------------------------------------------------------------*/
602:
603: void ClearNode (BTreeControlBlockPtr btreePtr, NodeDescPtr node )
604: {
605: ClearMemory( node, btreePtr->nodeSize );
606: }
607:
608: /*-------------------------------------------------------------------------------
609:
610: Routine: InsertRecord - Inserts a record into a BTree node.
611:
612: Function:
613:
614: Note: Record size must be even!
615:
616: Input: btreePtr - pointer to BTree control block
617: node - pointer to node to insert the record
618: index - position record is to be inserted
619: recPtr - pointer to record to insert
620:
621: Result: noErr - success
622: fsBTFullErr - record larger than remaining free space.
623: -------------------------------------------------------------------------------*/
624:
625: Boolean InsertRecord (BTreeControlBlockPtr btreePtr,
626: NodeDescPtr node,
627: UInt16 index,
628: RecordPtr recPtr,
629: UInt16 recSize )
630: {
631: UInt16 freeSpace;
632: UInt16 indexOffset;
633: UInt16 freeOffset;
634: UInt16 bytesToMove;
635: void *src;
636: void *dst;
637:
638: //// will new record fit in node?
639:
640: freeSpace = GetNodeFreeSize (btreePtr, node);
641: //�� we could get freeOffset & calc freeSpace
642: if ( freeSpace < recSize + 2)
643: {
644: return false;
645: }
646:
647:
648: //// make hole for new record
649:
650: indexOffset = GetRecordOffset (btreePtr, node, index);
651: freeOffset = GetRecordOffset (btreePtr, node, node->numRecords);
652:
653: src = ((Ptr) node) + indexOffset;
654: dst = ((Ptr) src) + recSize;
655: bytesToMove = freeOffset - indexOffset;
656: MoveRecordsRight (src, dst, bytesToMove);
657:
658:
659: //// adjust offsets for moved records
660:
661: InsertOffset (btreePtr, node, index, recSize);
662:
663:
664: //// move in the new record
665:
666: dst = ((Ptr) node) + indexOffset;
667: MoveRecordsLeft (recPtr, dst, recSize);
668:
669: return true;
670: }
671:
672:
673:
674: /*-------------------------------------------------------------------------------
675:
676: Routine: InsertKeyRecord - Inserts a record into a BTree node.
677:
678: Function:
679:
680: Note: Record size must be even!
681:
682: Input: btreePtr - pointer to BTree control block
683: node - pointer to node to insert the record
684: index - position record is to be inserted
685: keyPtr - pointer to key for record to insert
686: keyLength - length of key (or maxKeyLength)
687: recPtr - pointer to record to insert
688: recSize - number of bytes to copy for record
689:
690: Result: noErr - success
691: fsBTFullErr - record larger than remaining free space.
692: -------------------------------------------------------------------------------*/
693:
694: Boolean InsertKeyRecord (BTreeControlBlockPtr btreePtr,
695: NodeDescPtr node,
696: UInt16 index,
697: KeyPtr keyPtr,
698: UInt16 keyLength,
699: RecordPtr recPtr,
700: UInt16 recSize )
701: {
702: UInt16 freeSpace;
703: UInt16 indexOffset;
704: UInt16 freeOffset;
705: UInt16 bytesToMove;
706: UInt8 * src;
707: UInt8 * dst;
708: UInt16 keySize;
709: UInt16 rawKeyLength;
710: UInt16 sizeOfLength;
711:
712: //// calculate actual key size
713:
714: if ( btreePtr->attributes & kBTBigKeysMask )
715: keySize = keyLength + sizeof(UInt16);
716: else
717: keySize = keyLength + sizeof(UInt8);
718:
719: if ( M_IsOdd (keySize) )
720: ++keySize; // add pad byte
721:
722:
723: //// will new record fit in node?
724:
725: freeSpace = GetNodeFreeSize (btreePtr, node);
726: //�� we could get freeOffset & calc freeSpace
727: if ( freeSpace < keySize + recSize + 2)
728: {
729: return false;
730: }
731:
732:
733: //// make hole for new record
734:
735: indexOffset = GetRecordOffset (btreePtr, node, index);
736: freeOffset = GetRecordOffset (btreePtr, node, node->numRecords);
737:
738: src = ((UInt8 *) node) + indexOffset;
739: dst = ((UInt8 *) src) + keySize + recSize;
740: bytesToMove = freeOffset - indexOffset;
741: MoveRecordsRight (src, dst, bytesToMove);
742:
743:
744: //// adjust offsets for moved records
745:
746: InsertOffset (btreePtr, node, index, keySize + recSize);
747:
748:
749: //// copy record key
750:
751: dst = ((UInt8 *) node) + indexOffset;
752:
753: if ( btreePtr->attributes & kBTBigKeysMask )
754: {
755: *((UInt16*) dst)++ = keyLength; // use keyLength rather than key.length
756: rawKeyLength = keyPtr->length16;
757: sizeOfLength = 2;
758: }
759: else
760: {
761: *dst++ = keyLength; // use keyLength rather than key.length
762: rawKeyLength = keyPtr->length8;
763: sizeOfLength = 1;
764: }
765:
766: MoveRecordsLeft ( ((UInt8 *) keyPtr) + sizeOfLength, dst, rawKeyLength); // copy key
767:
768: // any pad bytes?
769: bytesToMove = keySize - rawKeyLength;
770: if (bytesToMove)
771: ClearMemory (dst + rawKeyLength, bytesToMove); // clear pad bytes in index key
772:
773:
774: //// copy record data
775:
776: dst = ((UInt8 *) node) + indexOffset + keySize;
777: MoveRecordsLeft (recPtr, dst, recSize);
778:
779: return true;
780: }
781:
782:
783:
784: /*-------------------------------------------------------------------------------
785:
786: Routine: DeleteRecord - Deletes a record from a BTree node.
787:
788: Function:
789:
790: Input: btreePtr - pointer to BTree control block
791: node - pointer to node to insert the record
792: index - position record is to be inserted
793:
794: Result: none
795: -------------------------------------------------------------------------------*/
796:
797: void DeleteRecord (BTreeControlBlockPtr btreePtr,
798: NodeDescPtr node,
799: UInt16 index )
800: {
801: SInt16 indexOffset;
802: SInt16 nextOffset;
803: SInt16 freeOffset;
804: SInt16 bytesToMove;
805: void *src;
806: void *dst;
807:
808: //// compress records
809: indexOffset = GetRecordOffset (btreePtr, node, index);
810: nextOffset = GetRecordOffset (btreePtr, node, index + 1);
811: freeOffset = GetRecordOffset (btreePtr, node, node->numRecords);
812:
813: src = ((Ptr) node) + nextOffset;
814: dst = ((Ptr) node) + indexOffset;
815: bytesToMove = freeOffset - nextOffset;
816: MoveRecordsLeft (src, dst, bytesToMove);
817:
818: //// Adjust the offsets
819: DeleteOffset (btreePtr, node, index);
820: }
821:
822:
823:
824: /*-------------------------------------------------------------------------------
825:
826: Routine: SearchNode - Return index for record that matches key.
827:
828: Function: Returns the record index for the record that matches the search key.
829: If no record was found that matches the search key, the "insert index"
830: of where the record should go is returned instead.
831:
832: Algorithm: A binary search algorithm is used to find the specified key.
833:
834: Input: btreePtr - pointer to BTree control block
835: node - pointer to node that contains the record
836: searchKey - pointer to the key to match
837:
838: Output: index - pointer to beginning of key for record
839:
840: Result: true - success (index = record index)
841: false - key did not match anything in node (index = insert index)
842: -------------------------------------------------------------------------------*/
843: #if !TARGET_CPU_68K
844:
845: Boolean SearchNode (BTreeControlBlockPtr btreePtr,
846: NodeDescPtr node,
847: KeyPtr searchKey,
848: UInt16 *returnIndex )
849: {
850: SInt32 lowerBound;
851: SInt32 upperBound;
852: SInt32 index;
853: SInt32 result;
854: KeyPtr trialKey;
855: #if !SupportsKeyDescriptors
856: KeyCompareProcPtr compareProc = btreePtr->keyCompareProc;
857: #endif
858:
859: lowerBound = 0;
860: upperBound = node->numRecords - 1;
861:
862: while (lowerBound <= upperBound)
863: {
864: index = (lowerBound + upperBound) >> 1; // divide by 2
865:
866: trialKey = (KeyPtr) GetRecordAddress (btreePtr, node, index );
867:
868: #if SupportsKeyDescriptors
869: result = CompareKeys (btreePtr, searchKey, trialKey);
870: #else
871: result = compareProc(searchKey, trialKey);
872: #endif
873:
874: if (result < 0) upperBound = index - 1; // search < trial
875: else if (result > 0) lowerBound = index + 1; // search > trial
876: else // search = trial
877: {
878: *returnIndex = index;
879: return true;
880: }
881: }
882:
883: *returnIndex = lowerBound; // lowerBound is insert index
884: return false;
885: }
886:
887: #endif
888:
889:
890: /*-------------------------------------------------------------------------------
891:
892: Routine: GetRecordByIndex - Return pointer to key and data, and size of data.
893:
894: Function: Returns a pointer to beginning of key for record, a pointer to the
895: beginning of the data for the record, and the size of the record data
896: (does not include the size of the key).
897:
898: Input: btreePtr - pointer to BTree control block
899: node - pointer to node that contains the record
900: index - index of record to get
901:
902: Output: keyPtr - pointer to beginning of key for record
903: dataPtr - pointer to beginning of data for record
904: dataSize - size of the data portion of the record
905:
906: Result: none
907: -------------------------------------------------------------------------------*/
908:
909: OSStatus GetRecordByIndex (BTreeControlBlockPtr btreePtr,
910: NodeDescPtr node,
911: UInt16 index,
912: KeyPtr *keyPtr,
913: UInt8 * *dataPtr,
914: UInt16 *dataSize )
915: {
916: UInt16 offset;
917: UInt16 nextOffset;
918: UInt16 keySize;
919:
920: //
921: // Make sure index is valid (in range 0..numRecords-1)
922: //
923: if (index >= node->numRecords)
924: return fsBTRecordNotFoundErr;
925:
926: //// find keyPtr
927: offset = GetRecordOffset (btreePtr, node, index);
928: *keyPtr = (KeyPtr) ((Ptr)node + offset);
929:
930: //// find dataPtr
931: keySize = CalcKeySize(btreePtr, *keyPtr);
932: if ( M_IsOdd (keySize) )
933: ++keySize; // add pad byte
934:
935: offset += keySize; // add the key length to find data offset
936: *dataPtr = (UInt8 *) node + offset;
937:
938: //// find dataSize
939: nextOffset = GetRecordOffset (btreePtr, node, index + 1);
940: *dataSize = nextOffset - offset;
941:
942: return noErr;
943: }
944:
945:
946:
947: /*-------------------------------------------------------------------------------
948:
949: Routine: GetNodeDataSize - Return the amount of space used for data in the node.
950:
951: Function: Gets the size of the data currently contained in a node, excluding
952: the node header. (record data + offset overhead)
953:
954: Input: btreePtr - pointer to BTree control block
955: node - pointer to node that contains the record
956:
957: Result: - number of bytes used for data and offsets in the node.
958: -------------------------------------------------------------------------------*/
959:
960: UInt16 GetNodeDataSize (BTreeControlBlockPtr btreePtr, NodeDescPtr node )
961: {
962: UInt16 freeOffset;
963:
964: freeOffset = GetRecordOffset (btreePtr, node, node->numRecords);
965:
966: return freeOffset + (node->numRecords << 1) - sizeof (BTNodeDescriptor);
967: }
968:
969:
970:
971: /*-------------------------------------------------------------------------------
972:
973: Routine: GetNodeFreeSize - Return the amount of free space in the node.
974:
975: Function:
976:
977: Input: btreePtr - pointer to BTree control block
978: node - pointer to node that contains the record
979:
980: Result: - number of bytes of free space in the node.
981: -------------------------------------------------------------------------------*/
982:
983: UInt16 GetNodeFreeSize (BTreeControlBlockPtr btreePtr, NodeDescPtr node )
984: {
985: UInt16 freeOffset;
986:
987: freeOffset = GetRecordOffset (btreePtr, node, node->numRecords); //�� inline?
988:
989: return btreePtr->nodeSize - freeOffset - (node->numRecords << 1) - kOffsetSize;
990: }
991:
992:
993:
994: /*-------------------------------------------------------------------------------
995:
996: Routine: GetRecordOffset - Return the offset for 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 for
1003:
1004: Result: - offset (in bytes) from beginning of node of record specified by index
1005: -------------------------------------------------------------------------------*/
1006: // make this a macro (for inlining)
1007: #if 0
1008: UInt16 GetRecordOffset (BTreeControlBlockPtr btreePtr,
1009: NodeDescPtr node,
1010: UInt16 index )
1011: {
1012: void *pos;
1013:
1014:
1015: pos = (UInt8 *)node + btreePtr->nodeSize - (index << 1) - kOffsetSize;
1016:
1017: return *(short *)pos;
1018: }
1019: #endif
1020:
1021:
1022:
1023: /*-------------------------------------------------------------------------------
1024:
1025: Routine: GetRecordAddress - Return address of record "index".
1026:
1027: Function:
1028:
1029: Input: btreePtr - pointer to BTree control block
1030: node - pointer to node that contains the record
1031: index - record to obtain offset address for
1032:
1033: Result: - pointer to record "index".
1034: -------------------------------------------------------------------------------*/
1035: // make this a macro (for inlining)
1036: #if 0
1037: UInt8 * GetRecordAddress (BTreeControlBlockPtr btreePtr,
1038: NodeDescPtr node,
1039: UInt16 index )
1040: {
1041: UInt8 * pos;
1042:
1043: pos = (UInt8 *)node + GetRecordOffset (btreePtr, node, index);
1044:
1045: return pos;
1046: }
1047: #endif
1048:
1049:
1050:
1051: /*-------------------------------------------------------------------------------
1052:
1053: Routine: GetRecordSize - Return size of record "index".
1054:
1055: Function:
1056:
1057: Note: This does not work on the FreeSpace index!
1058:
1059: Input: btreePtr - pointer to BTree control block
1060: node - pointer to node that contains the record
1061: index - record to obtain record size for
1062:
1063: Result: - size of record "index".
1064: -------------------------------------------------------------------------------*/
1065:
1066: UInt16 GetRecordSize (BTreeControlBlockPtr btreePtr,
1067: NodeDescPtr node,
1068: UInt16 index )
1069: {
1070: UInt16 *pos;
1071:
1072: pos = (UInt16 *) ((Ptr)node + btreePtr->nodeSize - (index << 1) - kOffsetSize);
1073:
1074: return *(pos-1) - *pos;
1075: }
1076:
1077:
1078:
1079: /*-------------------------------------------------------------------------------
1080: Routine: GetOffsetAddress - Return address of offset for record "index".
1081:
1082: Function:
1083:
1084: Input: btreePtr - pointer to BTree control block
1085: node - pointer to node that contains the record
1086: index - record to obtain offset address for
1087:
1088: Result: - pointer to offset for record "index".
1089: -------------------------------------------------------------------------------*/
1090:
1091: UInt16 *GetOffsetAddress (BTreeControlBlockPtr btreePtr,
1092: NodeDescPtr node,
1093: UInt16 index )
1094: {
1095: void *pos;
1096:
1097: pos = (Ptr)node + btreePtr->nodeSize - (index << 1) -2;
1098:
1099: return (UInt16 *)pos;
1100: }
1101:
1102:
1103:
1104: /*-------------------------------------------------------------------------------
1105: Routine: GetChildNodeNum - Return child node number from index record "index".
1106:
1107: Function: Returns the first UInt32 stored after the key for record "index".
1108:
1109: Assumes: The node is an Index Node.
1110: The key.length stored at record "index" is ODD. //�� change for variable length index keys
1111:
1112: Input: btreePtr - pointer to BTree control block
1113: node - pointer to node that contains the record
1114: index - record to obtain child node number from
1115:
1116: Result: - child node number from record "index".
1117: -------------------------------------------------------------------------------*/
1118:
1119: UInt32 GetChildNodeNum (BTreeControlBlockPtr btreePtr,
1120: NodeDescPtr nodePtr,
1121: UInt16 index )
1122: {
1123: UInt8 * pos;
1124:
1125: pos = GetRecordAddress (btreePtr, nodePtr, index);
1126: pos += CalcKeySize(btreePtr, (BTreeKey *) pos); // key.length + size of length field
1127:
1128: return *(UInt32 *)pos;
1129: }
1130:
1131:
1132:
1133: /*-------------------------------------------------------------------------------
1134: Routine: InsertOffset - Add an offset and adjust existing offsets by delta.
1135:
1136: Function: Add an offset at 'index' by shifting 'index+1' through the last offset
1137: and adjusting them by 'delta', the size of the record to be inserted.
1138: The number of records contained in the node is also incremented.
1139:
1140: Input: btreePtr - pointer to BTree control block
1141: node - pointer to node
1142: index - index at which to insert record
1143: delta - size of record to be inserted
1144:
1145: Result: none
1146: -------------------------------------------------------------------------------*/
1147:
1148: void InsertOffset (BTreeControlBlockPtr btreePtr,
1149: NodeDescPtr node,
1150: UInt16 index,
1151: UInt16 delta )
1152: {
1153: UInt16 *src, *dst;
1154: UInt16 numOffsets;
1155:
1156: src = GetOffsetAddress (btreePtr, node, node->numRecords); // point to free offset
1157: dst = src - 1; // point to new offset
1158: numOffsets = node->numRecords++ - index; // subtract index & postincrement
1159:
1160: do {
1161: *dst++ = *src++ + delta; // to tricky?
1162: } while (numOffsets--);
1163: }
1164:
1165:
1166:
1167: /*-------------------------------------------------------------------------------
1168:
1169: Routine: DeleteOffset - Delete an offset.
1170:
1171: Function: Delete the offset at 'index' by shifting 'index+1' through the last offset
1172: and adjusting them by the size of the record 'index'.
1173: The number of records contained in the node is also decremented.
1174:
1175: Input: btreePtr - pointer to BTree control block
1176: node - pointer to node
1177: index - index at which to delete record
1178:
1179: Result: none
1180: -------------------------------------------------------------------------------*/
1181:
1182: void DeleteOffset (BTreeControlBlockPtr btreePtr,
1183: NodeDescPtr node,
1184: UInt16 index )
1185: {
1186: UInt16 *src, *dst;
1187: UInt16 numOffsets;
1188: UInt16 delta;
1189:
1190: dst = GetOffsetAddress (btreePtr, node, index);
1191: src = dst - 1;
1192: delta = *src - *dst;
1193: numOffsets = --node->numRecords - index; // predecrement numRecords & subtract index
1194:
1195: while (numOffsets--)
1196: {
1197: *--dst = *--src - delta; // work our way left
1198: }
1199: }
1200:
1201:
1202:
1203: /*-------------------------------------------------------------------------------
1204:
1205: Routine: MoveRecordsLeft - Move records left within a node.
1206:
1207: Function: Moves a number of bytes from src to dst. Safely handles overlapping
1208: ranges if the bytes are being moved to the "left". No bytes are moved
1209: if bytesToMove is zero.
1210:
1211: Input: src - pointer to source
1212: dst - pointer to destination
1213: bytesToMove - number of bytes to move records
1214:
1215: Result: none
1216: -------------------------------------------------------------------------------*/
1217: #if 0
1218: void MoveRecordsLeft (UInt8 * src,
1219: UInt8 * dst,
1220: UInt16 bytesToMove )
1221: {
1222: while (bytesToMove--)
1223: *dst++ = *src++;
1224: }
1225: #endif
1226:
1227:
1228: /*-------------------------------------------------------------------------------
1229:
1230: Routine: MoveRecordsRight - Move records right within a node.
1231:
1232: Function: Moves a number of bytes from src to dst. Safely handles overlapping
1233: ranges if the bytes are being moved to the "right". No bytes are moved
1234: if bytesToMove is zero.
1235:
1236: Input: src - pointer to source
1237: dst - pointer to destination
1238: bytesToMove - number of bytes to move records
1239:
1240: Result: none
1241: -------------------------------------------------------------------------------*/
1242: #if 0
1243: void MoveRecordsRight (UInt8 * src,
1244: UInt8 * dst,
1245: UInt16 bytesToMove )
1246: {
1247: src += bytesToMove;
1248: dst += bytesToMove;
1249:
1250: while (bytesToMove--)
1251: *--dst = *--src;
1252: }
1253: #endif
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.