]> git.saurik.com Git - apple/xnu.git/blob - bsd/hfs/hfscommon/BTree/BTreeNodeOps.c
projects / apple / xnu.git / blob
? search:


e80c07ec55615c0780fcbd502a2c61f0de435cde
[apple/xnu.git] / bsd / hfs / hfscommon / BTree / BTreeNodeOps.c
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. \80\80\80 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 /////////////////////////////////////////////////////////////////////////////////
136
137
138
139 ////////////////////// Routines Internal To BTreeNodeOps.c //////////////////////
140
141 UInt16 GetRecordOffset (BTreeControlBlockPtr btree,
142 NodeDescPtr node,
143 UInt16 index );
144
145 UInt16 *GetOffsetAddress (BTreeControlBlockPtr btreePtr,
146 NodeDescPtr node,
147 UInt16 index );
148
149 void InsertOffset (BTreeControlBlockPtr btreePtr,
150 NodeDescPtr node,
151 UInt16 index,
152 UInt16 delta );
153
154 void DeleteOffset (BTreeControlBlockPtr btreePtr,
155 NodeDescPtr node,
156 UInt16 index );
157
158
159 /////////////////////////////////////////////////////////////////////////////////
160
161 #define GetRecordOffset(btreePtr,node,index) (*(short *) ((UInt8 *)(node) + (btreePtr)->nodeSize - ((index) << 1) - kOffsetSize))
162
163 #if HFS_DIAGNOSTIC
164 #include <sys/systm.h>
165 #define PRINTIT kprintf
166 #endif /* HFS_DIAGNOSTIC */
167
168 static void PrintNode(const NodeDescPtr node, UInt16 nodeSize, UInt32 nodeNumber);
169
170
171
172 /*-------------------------------------------------------------------------------
173
174 Routine: GetNode - Call FS Agent to get node
175
176 Function: Gets an existing BTree node from FS Agent and verifies it.
177
178 Input: btreePtr - pointer to BTree control block
179 nodeNum - number of node to request
180
181 Output: nodePtr - pointer to beginning of node (nil if error)
182
183 Result:
184 noErr - success
185 != noErr - failure
186 -------------------------------------------------------------------------------*/
187
188 OSStatus GetNode (BTreeControlBlockPtr btreePtr,
189 UInt32 nodeNum,
190 NodeRec *nodePtr )
191 {
192 OSStatus err;
193 GetBlockProcPtr getNodeProc;
194
195
196 LogStartTime(kTraceGetNode);
197
198 //\80\80 is nodeNum within proper range?
199 if( nodeNum >= btreePtr->totalNodes )
200 {
201 Panic("\pGetNode:nodeNum >= totalNodes");
202 err = fsBTInvalidNodeErr;
203 goto ErrorExit;
204 }
205
206 nodePtr->blockSize = btreePtr->nodeSize; // indicate the size of a node
207
208 getNodeProc = btreePtr->getBlockProc;
209 err = getNodeProc (btreePtr->fileRefNum,
210 nodeNum,
211 kGetBlock,
212 nodePtr );
213
214 if (err != noErr)
215 {
216 Panic ("\pGetNode: getNodeProc returned error.");
217 // nodePtr->buffer = nil;
218 goto ErrorExit;
219 }
220 ++btreePtr->numGetNodes;
221
222 //
223 // Optimization
224 // Only call CheckNode if the node came from disk.
225 // If it was in the cache, we'll assume its already a valid node.
226 //
227
228 if ( nodePtr->blockReadFromDisk ) // if we read it from disk then check it
229 {
230 err = CheckNode (btreePtr, nodePtr->buffer);
231
232 if (err != noErr)
233 {
234
235 VTOVCB(btreePtr->fileRefNum)->vcbFlags |= kHFS_DamagedVolume;
236
237 #if HFS_DIAGNOSTIC
238 if (((NodeDescPtr)nodePtr->buffer)->numRecords != 0)
239 PrintNode(nodePtr->buffer, btreePtr->nodeSize, nodeNum);
240 #endif
241
242 if (DEBUG_BUILD)
243 {
244 // With the removal of bounds checking in IsItAHint(), it's possible that
245 // GetNode() will be called to fetch a clear (all zeroes) node. We want
246 // CheckNode() to fail in this case (it does), however we don't want to assert
247 // this case because it is not really an "error". Returning an error from GetNode()
248 // in this case will cause the hint checking code to ignore the hint and revert to
249 // the full search mode.
250
251 {
252 UInt32 *cur;
253 UInt32 *lastPlusOne;
254
255 cur = nodePtr->buffer;
256 lastPlusOne = (UInt32 *) ((UInt8 *) cur + btreePtr->nodeSize);
257
258 while( cur < lastPlusOne )
259 {
260 if( *cur++ != 0 )
261 {
262 Panic ("\pGetNode: CheckNode returned error.");
263 break;
264 }
265 }
266 }
267 }
268
269 (void) TrashNode (btreePtr, nodePtr); // ignore error
270 goto ErrorExit;
271 }
272 }
273
274 LogEndTime(kTraceGetNode, noErr);
275
276 return noErr;
277
278 ErrorExit:
279 nodePtr->buffer = nil;
280 nodePtr->blockHeader = nil;
281
282 LogEndTime(kTraceGetNode, err);
283
284 return err;
285 }
286
287
288
289 /*-------------------------------------------------------------------------------
290
291 Routine: GetNewNode - Call FS Agent to get a new node
292
293 Function: Gets a new BTree node from FS Agent and initializes it to an empty
294 state.
295
296 Input: btreePtr - pointer to BTree control block
297 nodeNum - number of node to request
298
299 Output: returnNodePtr - pointer to beginning of node (nil if error)
300
301 Result: noErr - success
302 != noErr - failure
303 -------------------------------------------------------------------------------*/
304
305 OSStatus GetNewNode (BTreeControlBlockPtr btreePtr,
306 UInt32 nodeNum,
307 NodeRec *returnNodePtr )
308 {
309 OSStatus err;
310 NodeDescPtr node;
311 void *pos;
312 GetBlockProcPtr getNodeProc;
313
314
315 //////////////////////// get buffer for new node ////////////////////////////
316
317 returnNodePtr->blockSize = btreePtr->nodeSize; // indicate the size of a node
318
319 getNodeProc = btreePtr->getBlockProc;
320 err = getNodeProc (btreePtr->fileRefNum,
321 nodeNum,
322 kGetBlock+kGetEmptyBlock,
323 returnNodePtr );
324
325 if (err != noErr)
326 {
327 Panic ("\pGetNewNode: getNodeProc returned error.");
328 // returnNodePtr->buffer = nil;
329 return err;
330 }
331 ++btreePtr->numGetNewNodes;
332
333
334 ////////////////////////// initialize the node //////////////////////////////
335
336 node = returnNodePtr->buffer;
337
338 ClearNode (btreePtr, node); // clear the node
339
340 pos = (char *)node + btreePtr->nodeSize - 2; // find address of last offset
341 *(UInt16 *)pos = sizeof (BTNodeDescriptor); // set offset to beginning of free space
342
343
344 return noErr;
345 }
346
347
348
349 /*-------------------------------------------------------------------------------
350
351 Routine: ReleaseNode - Call FS Agent to release node obtained by GetNode.
352
353 Function: Informs the FS Agent that a BTree node may be released.
354
355 Input: btreePtr - pointer to BTree control block
356 nodeNum - number of node to release
357
358 Result: noErr - success
359 != noErr - failure
360 -------------------------------------------------------------------------------*/
361
362 OSStatus ReleaseNode (BTreeControlBlockPtr btreePtr,
363 NodePtr nodePtr )
364 {
365 OSStatus err;
366 ReleaseBlockProcPtr releaseNodeProc;
367
368
369 LogStartTime(kTraceReleaseNode);
370
371 err = noErr;
372
373 if (nodePtr->buffer != nil)
374 {
375 releaseNodeProc = btreePtr->releaseBlockProc;
376 err = releaseNodeProc (btreePtr->fileRefNum,
377 nodePtr,
378 kReleaseBlock );
379 PanicIf (err, "\pReleaseNode: releaseNodeProc returned error.");
380 ++btreePtr->numReleaseNodes;
381 }
382
383 nodePtr->buffer = nil;
384 nodePtr->blockHeader = nil;
385
386 LogEndTime(kTraceReleaseNode, err);
387
388 return err;
389 }
390
391
392
393
394 /*-------------------------------------------------------------------------------
395
396 Routine: TrashNode - Call FS Agent to release node obtained by GetNode, and
397 not store it...mark it as bad.
398
399 Function: Informs the FS Agent that a BTree node may be released and thrown away.
400
401 Input: btreePtr - pointer to BTree control block
402 nodeNum - number of node to release
403
404 Result: noErr - success
405 != noErr - failure
406 -------------------------------------------------------------------------------*/
407
408 OSStatus TrashNode (BTreeControlBlockPtr btreePtr,
409 NodePtr nodePtr )
410 {
411 OSStatus err;
412 ReleaseBlockProcPtr releaseNodeProc;
413
414
415 LogStartTime(kTraceReleaseNode);
416
417 err = noErr;
418
419 if (nodePtr->buffer != nil)
420 {
421 releaseNodeProc = btreePtr->releaseBlockProc;
422 err = releaseNodeProc (btreePtr->fileRefNum,
423 nodePtr,
424 kReleaseBlock | kTrashBlock );
425 PanicIf (err, "\TrashNode: releaseNodeProc returned error.");
426 ++btreePtr->numReleaseNodes;
427 }
428
429 nodePtr->buffer = nil;
430 nodePtr->blockHeader = nil;
431
432 LogEndTime(kTraceReleaseNode, err);
433
434 return err;
435 }
436
437
438
439 /*-------------------------------------------------------------------------------
440
441 Routine: UpdateNode - Mark a node as dirty and call FS Agent to release it.
442
443 Function: Marks a BTree node dirty and informs the FS Agent that it may be released.
444
445 //\80\80 have another routine that clears & writes a node, so we can call
446 CheckNode from this routine.
447
448 Input: btreePtr - pointer to BTree control block
449 nodeNum - number of node to release
450 transactionID - ID of transaction this node update is a part of
451 flags - special flags to pass to ReleaseNodeProc
452
453 Result: noErr - success
454 != noErr - failure
455 -------------------------------------------------------------------------------*/
456
457 OSStatus UpdateNode (BTreeControlBlockPtr btreePtr,
458 NodePtr nodePtr,
459 UInt32 transactionID,
460 UInt32 flags )
461 {
462 OSStatus err;
463 ReleaseBlockProcPtr releaseNodeProc;
464
465
466 err = noErr;
467
468 if (nodePtr->buffer != nil) //\80\80 why call UpdateNode if nil ?!?
469 {
470 if (DEBUG_BUILD)
471 {
472 if ( btreePtr->attributes & kBTVariableIndexKeysMask )
473 (void) CheckNode (btreePtr, nodePtr->buffer);
474 }
475
476 LogStartTime(kTraceReleaseNode);
477
478 releaseNodeProc = btreePtr->releaseBlockProc;
479 err = releaseNodeProc (btreePtr->fileRefNum,
480 nodePtr,
481 flags | kMarkBlockDirty );
482
483 LogEndTime(kTraceReleaseNode, err);
484
485 M_ExitOnError (err);
486 ++btreePtr->numUpdateNodes;
487 }
488
489 nodePtr->buffer = nil;
490 nodePtr->blockHeader = nil;
491
492 return noErr;
493
494 ErrorExit:
495
496 return err;
497 }
498
499
500
501 /*-------------------------------------------------------------------------------
502
503 Routine: CheckNode - Checks the validity of a node.
504
505 Function: Checks the validity of a node by verifying that the fLink and bLink fields
506 are within the forks EOF. The node type must be one of the four known
507 types. The node height must be less than or equal to the tree height. The
508 node must not have more than the maximum number of records, and the record
509 offsets must make sense.
510
511 Input: btreePtr - pointer to BTree control block
512 node - pointer to node to check
513
514 Result: noErr - success
515 fsBTInvalidNodeErr - failure
516 -------------------------------------------------------------------------------*/
517
518 OSStatus CheckNode (BTreeControlBlockPtr btreePtr, NodeDescPtr node )
519 {
520 SInt32 index;
521 SInt32 maxRecords;
522 UInt32 maxNode;
523 UInt16 nodeSize;
524 UInt16 offset;
525 UInt16 prevOffset;
526
527 nodeSize = btreePtr->nodeSize;
528
529 ///////////////////// are fLink and bLink within EOF ////////////////////////
530
531 maxNode = (GetFileControlBlock(btreePtr->fileRefNum)->fcbEOF / nodeSize) - 1;
532
533 if ( (node->fLink > maxNode) || (node->bLink > maxNode) )
534 return fsBTInvalidNodeErr;
535
536 /////////////// check node type (leaf, index, header, map) //////////////////
537
538 if ( (node->kind < kBTLeafNode) || (node->kind > kBTMapNode) )
539 return fsBTInvalidNodeErr;
540
541 ///////////////////// is node height > tree depth? //////////////////////////
542
543 if ( node->height > btreePtr->treeDepth )
544 return fsBTInvalidNodeErr;
545
546 //////////////////////// check number of records ////////////////////////////
547
548 //XXX can we calculate a more accurate minimum record size?
549 maxRecords = ( nodeSize - sizeof (BTNodeDescriptor) ) >> 3;
550
551 if (node->numRecords > maxRecords)
552 return fsBTInvalidNodeErr;
553
554 ////////////////////////// check record offsets /////////////////////////////
555
556 index = node->numRecords; /* start index at free space */
557 prevOffset = nodeSize - (index << 1); /* use 2 bytes past end of free space */
558
559 do {
560 offset = GetRecordOffset (btreePtr, node, index);
561
562 if (offset & 1) // offset is odd
563 return fsBTInvalidNodeErr;
564
565 if (offset >= prevOffset) // offset >= previous offset
566 return fsBTInvalidNodeErr;
567
568 /* reject keys that overflow record slot */
569 if ((node->kind == kBTLeafNode) &&
570 (index < node->numRecords) && /* ignore free space record */
571 (CalcKeySize(btreePtr, (KeyPtr) ((Ptr)node + offset)) > (prevOffset - offset))) {
572 return fsBTInvalidNodeErr;
573 }
574
575 prevOffset = offset;
576 } while ( --index >= 0 );
577
578 if (offset < sizeof (BTNodeDescriptor) ) // first offset < minimum ?
579 return fsBTInvalidNodeErr;
580
581 return noErr;
582 }
583
584
585 #if HFS_DIAGNOSTIC
586 static void PrintNode(const NodeDescPtr node, UInt16 nodeSize, UInt32 nodeNumber)
587 {
588 struct row {
589 UInt16 word[8];
590 };
591 struct row *offset;
592 UInt16 rows;
593 UInt32 *lp;
594
595 PRINTIT("Dump of B-tree node #%ld ($%08lX)\n", nodeNumber, nodeNumber);
596
597 rows = nodeSize/16;
598 lp = (UInt32*) node;
599 offset = 0;
600
601 while (rows-- > 0)
602 PRINTIT("%04X: %08lX %08lX %08lX %08lX\n", (u_int)offset++, *lp++, *lp++, *lp++, *lp++);
603 }
604 #endif
605
606
607 /*-------------------------------------------------------------------------------
608
609 Routine: ClearNode - Clear a node to all zeroes.
610
611 Function: Writes zeroes from beginning of node for nodeSize bytes.
612
613 Input: btreePtr - pointer to BTree control block
614 node - pointer to node to clear
615
616 Result: none
617 -------------------------------------------------------------------------------*/
618
619 void ClearNode (BTreeControlBlockPtr btreePtr, NodeDescPtr node )
620 {
621 ClearMemory( node, btreePtr->nodeSize );
622 }
623
624 /*-------------------------------------------------------------------------------
625
626 Routine: InsertRecord - Inserts a record into a BTree node.
627
628 Function:
629
630 Note: Record size must be even!
631
632 Input: btreePtr - pointer to BTree control block
633 node - pointer to node to insert the record
634 index - position record is to be inserted
635 recPtr - pointer to record to insert
636
637 Result: noErr - success
638 fsBTFullErr - record larger than remaining free space.
639 -------------------------------------------------------------------------------*/
640
641 Boolean InsertRecord (BTreeControlBlockPtr btreePtr,
642 NodeDescPtr node,
643 UInt16 index,
644 RecordPtr recPtr,
645 UInt16 recSize )
646 {
647 UInt16 freeSpace;
648 UInt16 indexOffset;
649 UInt16 freeOffset;
650 UInt16 bytesToMove;
651 void *src;
652 void *dst;
653
654 //// will new record fit in node?
655
656 freeSpace = GetNodeFreeSize (btreePtr, node);
657 //\80\80 we could get freeOffset & calc freeSpace
658 if ( freeSpace < recSize + 2)
659 {
660 return false;
661 }
662
663
664 //// make hole for new record
665
666 indexOffset = GetRecordOffset (btreePtr, node, index);
667 freeOffset = GetRecordOffset (btreePtr, node, node->numRecords);
668
669 src = ((Ptr) node) + indexOffset;
670 dst = ((Ptr) src) + recSize;
671 bytesToMove = freeOffset - indexOffset;
672 if (bytesToMove)
673 MoveRecordsRight (src, dst, bytesToMove);
674
675
676 //// adjust offsets for moved records
677
678 InsertOffset (btreePtr, node, index, recSize);
679
680
681 //// move in the new record
682
683 dst = ((Ptr) node) + indexOffset;
684 MoveRecordsLeft (recPtr, dst, recSize);
685
686 return true;
687 }
688
689
690
691 /*-------------------------------------------------------------------------------
692
693 Routine: InsertKeyRecord - Inserts a record into a BTree node.
694
695 Function:
696
697 Note: Record size must be even!
698
699 Input: btreePtr - pointer to BTree control block
700 node - pointer to node to insert the record
701 index - position record is to be inserted
702 keyPtr - pointer to key for record to insert
703 keyLength - length of key (or maxKeyLength)
704 recPtr - pointer to record to insert
705 recSize - number of bytes to copy for record
706
707 Result: noErr - success
708 fsBTFullErr - record larger than remaining free space.
709 -------------------------------------------------------------------------------*/
710
711 Boolean InsertKeyRecord (BTreeControlBlockPtr btreePtr,
712 NodeDescPtr node,
713 UInt16 index,
714 KeyPtr keyPtr,
715 UInt16 keyLength,
716 RecordPtr recPtr,
717 UInt16 recSize )
718 {
719 UInt16 freeSpace;
720 UInt16 indexOffset;
721 UInt16 freeOffset;
722 UInt16 bytesToMove;
723 UInt8 * src;
724 UInt8 * dst;
725 UInt16 keySize;
726 UInt16 rawKeyLength;
727 UInt16 sizeOfLength;
728
729 //// calculate actual key size
730
731 if ( btreePtr->attributes & kBTBigKeysMask )
732 keySize = keyLength + sizeof(UInt16);
733 else
734 keySize = keyLength + sizeof(UInt8);
735
736 if ( M_IsOdd (keySize) )
737 ++keySize; // add pad byte
738
739
740 //// will new record fit in node?
741
742 freeSpace = GetNodeFreeSize (btreePtr, node);
743 //\80\80 we could get freeOffset & calc freeSpace
744 if ( freeSpace < keySize + recSize + 2)
745 {
746 return false;
747 }
748
749
750 //// make hole for new record
751
752 indexOffset = GetRecordOffset (btreePtr, node, index);
753 freeOffset = GetRecordOffset (btreePtr, node, node->numRecords);
754
755 src = ((UInt8 *) node) + indexOffset;
756 dst = ((UInt8 *) src) + keySize + recSize;
757 bytesToMove = freeOffset - indexOffset;
758 if (bytesToMove)
759 MoveRecordsRight (src, dst, bytesToMove);
760
761
762 //// adjust offsets for moved records
763
764 InsertOffset (btreePtr, node, index, keySize + recSize);
765
766
767 //// copy record key
768
769 dst = ((UInt8 *) node) + indexOffset;
770
771 if ( btreePtr->attributes & kBTBigKeysMask )
772 {
773 *((UInt16*) dst)++ = keyLength; // use keyLength rather than key.length
774 rawKeyLength = keyPtr->length16;
775 sizeOfLength = 2;
776 }
777 else
778 {
779 *dst++ = keyLength; // use keyLength rather than key.length
780 rawKeyLength = keyPtr->length8;
781 sizeOfLength = 1;
782 }
783
784 MoveRecordsLeft ( ((UInt8 *) keyPtr) + sizeOfLength, dst, rawKeyLength); // copy key
785
786 // any pad bytes?
787 bytesToMove = keySize - rawKeyLength;
788 if (bytesToMove)
789 ClearMemory (dst + rawKeyLength, bytesToMove); // clear pad bytes in index key
790
791
792 //// copy record data
793
794 dst = ((UInt8 *) node) + indexOffset + keySize;
795 MoveRecordsLeft (recPtr, dst, recSize);
796
797 return true;
798 }
799
800
801
802 /*-------------------------------------------------------------------------------
803
804 Routine: DeleteRecord - Deletes a record from a BTree node.
805
806 Function:
807
808 Input: btreePtr - pointer to BTree control block
809 node - pointer to node to insert the record
810 index - position record is to be inserted
811
812 Result: none
813 -------------------------------------------------------------------------------*/
814
815 void DeleteRecord (BTreeControlBlockPtr btreePtr,
816 NodeDescPtr node,
817 UInt16 index )
818 {
819 SInt16 indexOffset;
820 SInt16 nextOffset;
821 SInt16 freeOffset;
822 SInt16 bytesToMove;
823 void *src;
824 void *dst;
825
826 //// compress records
827 indexOffset = GetRecordOffset (btreePtr, node, index);
828 nextOffset = GetRecordOffset (btreePtr, node, index + 1);
829 freeOffset = GetRecordOffset (btreePtr, node, node->numRecords);
830
831 src = ((Ptr) node) + nextOffset;
832 dst = ((Ptr) node) + indexOffset;
833 bytesToMove = freeOffset - nextOffset;
834 if (bytesToMove)
835 MoveRecordsLeft (src, dst, bytesToMove);
836
837 //// Adjust the offsets
838 DeleteOffset (btreePtr, node, index);
839
840 /* clear out new free space */
841 bytesToMove = nextOffset - indexOffset;
842 ClearMemory(GetRecordAddress(btreePtr, node, node->numRecords), bytesToMove);
843
844 }
845
846
847
848 /*-------------------------------------------------------------------------------
849
850 Routine: SearchNode - Return index for record that matches key.
851
852 Function: Returns the record index for the record that matches the search key.
853 If no record was found that matches the search key, the "insert index"
854 of where the record should go is returned instead.
855
856 Algorithm: A binary search algorithm is used to find the specified key.
857
858 Input: btreePtr - pointer to BTree control block
859 node - pointer to node that contains the record
860 searchKey - pointer to the key to match
861
862 Output: index - pointer to beginning of key for record
863
864 Result: true - success (index = record index)
865 false - key did not match anything in node (index = insert index)
866 -------------------------------------------------------------------------------*/
867 Boolean
868 SearchNode( BTreeControlBlockPtr btreePtr,
869 NodeDescPtr node,
870 KeyPtr searchKey,
871 UInt16 *returnIndex )
872 {
873 SInt32 lowerBound;
874 SInt32 upperBound;
875 SInt32 index;
876 SInt32 result;
877 KeyPtr trialKey;
878 UInt16 *offset;
879 KeyCompareProcPtr compareProc = btreePtr->keyCompareProc;
880
881 lowerBound = 0;
882 upperBound = node->numRecords - 1;
883 offset = (UInt16 *) ((UInt8 *)(node) + (btreePtr)->nodeSize - kOffsetSize);
884
885 while (lowerBound <= upperBound) {
886 index = (lowerBound + upperBound) >> 1;
887
888 trialKey = (KeyPtr) ((UInt8 *)node + *(offset - index));
889
890 result = compareProc(searchKey, trialKey);
891
892 if (result < 0) {
893 upperBound = index - 1; /* search < trial */
894 } else if (result > 0) {
895 lowerBound = index + 1; /* search > trial */
896 } else {
897 *returnIndex = index; /* search == trial */
898 return true;
899 }
900 }
901
902 *returnIndex = lowerBound; /* lowerBound is insert index */
903 return false;
904 }
905
906
907 /*-------------------------------------------------------------------------------
908
909 Routine: GetRecordByIndex - Return pointer to key and data, and size of data.
910
911 Function: Returns a pointer to beginning of key for record, a pointer to the
912 beginning of the data for the record, and the size of the record data
913 (does not include the size of the key).
914
915 Input: btreePtr - pointer to BTree control block
916 node - pointer to node that contains the record
917 index - index of record to get
918
919 Output: keyPtr - pointer to beginning of key for record
920 dataPtr - pointer to beginning of data for record
921 dataSize - size of the data portion of the record
922
923 Result: none
924 -------------------------------------------------------------------------------*/
925
926 OSStatus GetRecordByIndex (BTreeControlBlockPtr btreePtr,
927 NodeDescPtr node,
928 UInt16 index,
929 KeyPtr *keyPtr,
930 UInt8 * *dataPtr,
931 UInt16 *dataSize )
932 {
933 UInt16 offset;
934 UInt16 nextOffset;
935 UInt16 keySize;
936
937 //
938 // Make sure index is valid (in range 0..numRecords-1)
939 //
940 if (index >= node->numRecords)
941 return fsBTRecordNotFoundErr;
942
943 //// find keyPtr
944 offset = GetRecordOffset (btreePtr, node, index);
945 *keyPtr = (KeyPtr) ((Ptr)node + offset);
946
947 //// find dataPtr
948 keySize = CalcKeySize(btreePtr, *keyPtr);
949 if ( M_IsOdd (keySize) )
950 ++keySize; // add pad byte
951
952 offset += keySize; // add the key length to find data offset
953 *dataPtr = (UInt8 *) node + offset;
954
955 //// find dataSize
956 nextOffset = GetRecordOffset (btreePtr, node, index + 1);
957 *dataSize = nextOffset - offset;
958
959 return noErr;
960 }
961
962
963
964 /*-------------------------------------------------------------------------------
965
966 Routine: GetNodeDataSize - Return the amount of space used for data in the node.
967
968 Function: Gets the size of the data currently contained in a node, excluding
969 the node header. (record data + offset overhead)
970
971 Input: btreePtr - pointer to BTree control block
972 node - pointer to node that contains the record
973
974 Result: - number of bytes used for data and offsets in the node.
975 -------------------------------------------------------------------------------*/
976
977 UInt16 GetNodeDataSize (BTreeControlBlockPtr btreePtr, NodeDescPtr node )
978 {
979 UInt16 freeOffset;
980
981 freeOffset = GetRecordOffset (btreePtr, node, node->numRecords);
982
983 return freeOffset + (node->numRecords << 1) - sizeof (BTNodeDescriptor);
984 }
985
986
987
988 /*-------------------------------------------------------------------------------
989
990 Routine: GetNodeFreeSize - Return the amount of free space in the node.
991
992 Function:
993
994 Input: btreePtr - pointer to BTree control block
995 node - pointer to node that contains the record
996
997 Result: - number of bytes of free space in the node.
998 -------------------------------------------------------------------------------*/
999
1000 UInt16 GetNodeFreeSize (BTreeControlBlockPtr btreePtr, NodeDescPtr node )
1001 {
1002 UInt16 freeOffset;
1003
1004 freeOffset = GetRecordOffset (btreePtr, node, node->numRecords); //\80\80 inline?
1005
1006 return btreePtr->nodeSize - freeOffset - (node->numRecords << 1) - kOffsetSize;
1007 }
1008
1009
1010
1011 /*-------------------------------------------------------------------------------
1012
1013 Routine: GetRecordOffset - Return the offset for record "index".
1014
1015 Function:
1016
1017 Input: btreePtr - pointer to BTree control block
1018 node - pointer to node that contains the record
1019 index - record to obtain offset for
1020
1021 Result: - offset (in bytes) from beginning of node of record specified by index
1022 -------------------------------------------------------------------------------*/
1023 // make this a macro (for inlining)
1024 #if 0
1025 UInt16 GetRecordOffset (BTreeControlBlockPtr btreePtr,
1026 NodeDescPtr node,
1027 UInt16 index )
1028 {
1029 void *pos;
1030
1031
1032 pos = (UInt8 *)node + btreePtr->nodeSize - (index << 1) - kOffsetSize;
1033
1034 return *(short *)pos;
1035 }
1036 #endif
1037
1038
1039
1040 /*-------------------------------------------------------------------------------
1041
1042 Routine: GetRecordAddress - Return address of record "index".
1043
1044 Function:
1045
1046 Input: btreePtr - pointer to BTree control block
1047 node - pointer to node that contains the record
1048 index - record to obtain offset address for
1049
1050 Result: - pointer to record "index".
1051 -------------------------------------------------------------------------------*/
1052 // make this a macro (for inlining)
1053 #if 0
1054 UInt8 * GetRecordAddress (BTreeControlBlockPtr btreePtr,
1055 NodeDescPtr node,
1056 UInt16 index )
1057 {
1058 UInt8 * pos;
1059
1060 pos = (UInt8 *)node + GetRecordOffset (btreePtr, node, index);
1061
1062 return pos;
1063 }
1064 #endif
1065
1066
1067
1068 /*-------------------------------------------------------------------------------
1069
1070 Routine: GetRecordSize - Return size of record "index".
1071
1072 Function:
1073
1074 Note: This does not work on the FreeSpace index!
1075
1076 Input: btreePtr - pointer to BTree control block
1077 node - pointer to node that contains the record
1078 index - record to obtain record size for
1079
1080 Result: - size of record "index".
1081 -------------------------------------------------------------------------------*/
1082
1083 UInt16 GetRecordSize (BTreeControlBlockPtr btreePtr,
1084 NodeDescPtr node,
1085 UInt16 index )
1086 {
1087 UInt16 *pos;
1088
1089 pos = (UInt16 *) ((Ptr)node + btreePtr->nodeSize - (index << 1) - kOffsetSize);
1090
1091 return *(pos-1) - *pos;
1092 }
1093
1094
1095
1096 /*-------------------------------------------------------------------------------
1097 Routine: GetOffsetAddress - Return address of offset for record "index".
1098
1099 Function:
1100
1101 Input: btreePtr - pointer to BTree control block
1102 node - pointer to node that contains the record
1103 index - record to obtain offset address for
1104
1105 Result: - pointer to offset for record "index".
1106 -------------------------------------------------------------------------------*/
1107
1108 UInt16 *GetOffsetAddress (BTreeControlBlockPtr btreePtr,
1109 NodeDescPtr node,
1110 UInt16 index )
1111 {
1112 void *pos;
1113
1114 pos = (Ptr)node + btreePtr->nodeSize - (index << 1) -2;
1115
1116 return (UInt16 *)pos;
1117 }
1118
1119
1120
1121 /*-------------------------------------------------------------------------------
1122 Routine: GetChildNodeNum - Return child node number from index record "index".
1123
1124 Function: Returns the first UInt32 stored after the key for record "index".
1125
1126 Assumes: The node is an Index Node.
1127 The key.length stored at record "index" is ODD. //\80\80 change for variable length index keys
1128
1129 Input: btreePtr - pointer to BTree control block
1130 node - pointer to node that contains the record
1131 index - record to obtain child node number from
1132
1133 Result: - child node number from record "index".
1134 -------------------------------------------------------------------------------*/
1135
1136 UInt32 GetChildNodeNum (BTreeControlBlockPtr btreePtr,
1137 NodeDescPtr nodePtr,
1138 UInt16 index )
1139 {
1140 UInt8 * pos;
1141
1142 pos = GetRecordAddress (btreePtr, nodePtr, index);
1143 pos += CalcKeySize(btreePtr, (BTreeKey *) pos); // key.length + size of length field
1144
1145 return *(UInt32 *)pos;
1146 }
1147
1148
1149
1150 /*-------------------------------------------------------------------------------
1151 Routine: InsertOffset - Add an offset and adjust existing offsets by delta.
1152
1153 Function: Add an offset at 'index' by shifting 'index+1' through the last offset
1154 and adjusting them by 'delta', the size of the record to be inserted.
1155 The number of records contained in the node is also incremented.
1156
1157 Input: btreePtr - pointer to BTree control block
1158 node - pointer to node
1159 index - index at which to insert record
1160 delta - size of record to be inserted
1161
1162 Result: none
1163 -------------------------------------------------------------------------------*/
1164
1165 void InsertOffset (BTreeControlBlockPtr btreePtr,
1166 NodeDescPtr node,
1167 UInt16 index,
1168 UInt16 delta )
1169 {
1170 UInt16 *src, *dst;
1171 UInt16 numOffsets;
1172
1173 src = GetOffsetAddress (btreePtr, node, node->numRecords); // point to free offset
1174 dst = src - 1; // point to new offset
1175 numOffsets = node->numRecords++ - index; // subtract index & postincrement
1176
1177 do {
1178 *dst++ = *src++ + delta; // to tricky?
1179 } while (numOffsets--);
1180 }
1181
1182
1183
1184 /*-------------------------------------------------------------------------------
1185
1186 Routine: DeleteOffset - Delete an offset.
1187
1188 Function: Delete the offset at 'index' by shifting 'index+1' through the last offset
1189 and adjusting them by the size of the record 'index'.
1190 The number of records contained in the node is also decremented.
1191
1192 Input: btreePtr - pointer to BTree control block
1193 node - pointer to node
1194 index - index at which to delete record
1195
1196 Result: none
1197 -------------------------------------------------------------------------------*/
1198
1199 void DeleteOffset (BTreeControlBlockPtr btreePtr,
1200 NodeDescPtr node,
1201 UInt16 index )
1202 {
1203 UInt16 *src, *dst;
1204 UInt16 numOffsets;
1205 UInt16 delta;
1206
1207 dst = GetOffsetAddress (btreePtr, node, index);
1208 src = dst - 1;
1209 delta = *src - *dst;
1210 numOffsets = --node->numRecords - index; // predecrement numRecords & subtract index
1211
1212 while (numOffsets--)
1213 {
1214 *--dst = *--src - delta; // work our way left
1215 }
1216 }
1217
1218
mirror of XNU