]> git.saurik.com Git - apple/xnu.git/blob - bsd/hfs/hfscommon/BTree/BTreeNodeOps.c
projects / apple / xnu.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
xnu-517.tar.gz
[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 * Copyright (c) 1999-2003 Apple Computer, Inc. All Rights Reserved.
7 *
8 * This file contains Original Code and/or Modifications of Original Code
9 * as defined in and that are subject to the Apple Public Source License
10 * Version 2.0 (the 'License'). You may not use this file except in
11 * compliance with the License. Please obtain a copy of the License at
12 * http://www.opensource.apple.com/apsl/ and read it before using this
13 * file.
14 *
15 * The Original Code and all software distributed under the License are
16 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
17 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
18 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
20 * Please see the License for the specific language governing rights and
21 * limitations under the License.
22 *
23 * @APPLE_LICENSE_HEADER_END@
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-1999 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 <MOSXS> 6/1/99 djb Sync up with Mac OS 8.6.
52 <MOSXS> 4/113/99 djb Fix key size checking bug in CheckNode.
53 <MOSXS> 3/19/99 djb Added key size checking to CheckNode.
54 <MOSXS> 3/26/98 djb Added PrintNode for debugging.
55 <CS5> 9/4/97 djb Removed GetRightSiblingNode and GetLeftSiblingNode - they are
56 now macros. SearchNode is now in BTreeSearchNode.a.
57 <CS4> 8/22/97 djb Turn off debugging code in CheckKey.
58 <CS3> 7/24/97 djb Add summary traces for Get/Rel Node. Made GetRecordOffset into a
59 macro. Only call CheckNode if the node came from disk.
60 <CS2> 7/21/97 msd Make GetRecordByIndex check its record index input; it now
61 returns an OSStatus.
62 <CS1> 4/23/97 djb first checked in
63
64 <HFS3> 2/19/97 djb Changes to support big node cache.
65 <HFS2> 1/3/97 djb Added support for large keys.
66 <HFS1> 12/19/96 djb first checked in
67
68
69 History applicable to original Scarecrow Design:
70
71 <6> 10/25/96 ser Changing for new VFPI
72 <5> 9/17/96 dkh Add bounds checking to GetNode. Update GetNode to not assert
73 that CheckNode failed if the node is all zeroes. This can happen
74 if the hint case if the fetched node has been deallocated
75 <4> 3/7/96 dkh Change GetNewNode() to not use kGetEmptyBlock. Instead use
76 kGetBlock to fetch a block from the disk itself. \80\80\80 Why?
77 <3> 1/22/96 dkh Add #include Memory.h
78 <2> 1/10/96 msd Change 64-bit math to use real function names from Math64.i.
79 <1> 10/18/95 rst Moved from Scarecrow project.
80
81 <17> 7/18/95 mbb Change MoveData & ClearBytes to BlockMoveData & BlockZero.
82 <16> 1/31/95 prp GetBlockProc interface uses a 64 bit node number.
83 <15> 1/12/95 wjk Adopt Model FileSystem changes in D5.
84 <14> 9/30/94 prp Get in sync with D2 interface changes.
85 <13> 7/25/94 wjk Eliminate usage of BytePtr in favor of UInt8 *.
86 <12> 7/22/94 wjk Convert to the new set of header files.
87 <11> 12/2/93 wjk Move from Makefiles to BuildFiles. Fit into the ModernOS and
88 NRCmds environments.
89 <10> 11/30/93 wjk Change some Ptr's to BytePtr's in function definitions so they
90 agree with their prototypes.
91 <9> 8/31/93 prp Use U64SetU instead of S64Set.
92 <8> 5/21/93 gs Maintain statistical counters on Get/Release node routines.
93 <7> 5/10/93 gs Change keySize parameter to keyLength for InsertKeyRecord
94 routine. Calculate number of bytes in key from keyLength to
95 account for length and pad bytes. Add GetChildNodeNum routine.
96 <6> 3/23/93 gs Add InsertKeyRecord routine.
97 <5> 2/8/93 gs Fix bug in SearchNode that caused "off by 1" error when final
98 compare was searchKey > trialKey. Add UpdateNode.
99 <4> 12/10/92 gs Change keyLength field of key to 'length'.
100 <3> 12/8/92 gs Incorporate suggestions from preliminary code review.
101 <2> 12/2/92 gs Implement routines.
102 <1> 11/15/92 gs Define routine interfaces.
103
104 */
105
106 #include "../headers/BTreesPrivate.h"
107
108
109
110 ///////////////////////// BTree Module Node Operations //////////////////////////
111 //
112 // GetNode - Call FS Agent to get node
113 // GetNewNode - Call FS Agent to get a new node
114 // ReleaseNode - Call FS Agent to release node obtained by GetNode.
115 // UpdateNode - Mark a node as dirty and call FS Agent to release it.
116 //
117 // CheckNode - Checks the validity of a node.
118 // ClearNode - Clear a node to all zeroes.
119 //
120 // InsertRecord - Inserts a record into a BTree node.
121 // InsertKeyRecord - Inserts a key and record pair into a BTree node.
122 // DeleteRecord - Deletes a record from a BTree node.
123 //
124 // SearchNode - Return index for record that matches key.
125 // LocateRecord - Return pointer to key and data, and size of data.
126 //
127 // GetNodeDataSize - Return the amount of space used for data in the node.
128 // GetNodeFreeSize - Return the amount of free space in the node.
129 //
130 // GetRecordOffset - Return the offset for record "index".
131 // GetRecordAddress - Return address of record "index".
132 // GetOffsetAddress - Return address of offset for record "index".
133 //
134 // InsertOffset - Inserts a new offset into a node.
135 // DeleteOffset - Deletes an offset from a node.
136 //
137 /////////////////////////////////////////////////////////////////////////////////
138
139
140
141 ////////////////////// Routines Internal To BTreeNodeOps.c //////////////////////
142
143 UInt16 GetRecordOffset (BTreeControlBlockPtr btree,
144 NodeDescPtr node,
145 UInt16 index );
146
147 UInt16 *GetOffsetAddress (BTreeControlBlockPtr btreePtr,
148 NodeDescPtr node,
149 UInt16 index );
150
151 void InsertOffset (BTreeControlBlockPtr btreePtr,
152 NodeDescPtr node,
153 UInt16 index,
154 UInt16 delta );
155
156 void DeleteOffset (BTreeControlBlockPtr btreePtr,
157 NodeDescPtr node,
158 UInt16 index );
159
160
161 /////////////////////////////////////////////////////////////////////////////////
162
163 #define GetRecordOffset(btreePtr,node,index) (*(short *) ((UInt8 *)(node) + (btreePtr)->nodeSize - ((index) << 1) - kOffsetSize))
164
165 #if HFS_DIAGNOSTIC
166 #include <sys/systm.h>
167 #define PRINTIT kprintf
168 #endif /* HFS_DIAGNOSTIC */
169
170 static void PrintNode(const NodeDescPtr node, UInt16 nodeSize, UInt32 nodeNumber);
171
172
173
174 /*-------------------------------------------------------------------------------
175
176 Routine: GetNode - Call FS Agent to get node
177
178 Function: Gets an existing BTree node from FS Agent and verifies it.
179
180 Input: btreePtr - pointer to BTree control block
181 nodeNum - number of node to request
182
183 Output: nodePtr - pointer to beginning of node (nil if error)
184
185 Result:
186 noErr - success
187 != noErr - failure
188 -------------------------------------------------------------------------------*/
189
190 OSStatus GetNode (BTreeControlBlockPtr btreePtr,
191 UInt32 nodeNum,
192 NodeRec *nodePtr )
193 {
194 OSStatus err;
195 GetBlockProcPtr getNodeProc;
196
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 return noErr;
275
276 ErrorExit:
277 nodePtr->buffer = nil;
278 nodePtr->blockHeader = nil;
279
280 return err;
281 }
282
283
284
285 /*-------------------------------------------------------------------------------
286
287 Routine: GetNewNode - Call FS Agent to get a new node
288
289 Function: Gets a new BTree node from FS Agent and initializes it to an empty
290 state.
291
292 Input: btreePtr - pointer to BTree control block
293 nodeNum - number of node to request
294
295 Output: returnNodePtr - pointer to beginning of node (nil if error)
296
297 Result: noErr - success
298 != noErr - failure
299 -------------------------------------------------------------------------------*/
300
301 OSStatus GetNewNode (BTreeControlBlockPtr btreePtr,
302 UInt32 nodeNum,
303 NodeRec *returnNodePtr )
304 {
305 OSStatus err;
306 NodeDescPtr node;
307 void *pos;
308 GetBlockProcPtr getNodeProc;
309
310
311 //////////////////////// get buffer for new node ////////////////////////////
312
313 returnNodePtr->blockSize = btreePtr->nodeSize; // indicate the size of a node
314
315 getNodeProc = btreePtr->getBlockProc;
316 err = getNodeProc (btreePtr->fileRefNum,
317 nodeNum,
318 kGetBlock+kGetEmptyBlock,
319 returnNodePtr );
320
321 if (err != noErr)
322 {
323 Panic ("\pGetNewNode: getNodeProc returned error.");
324 // returnNodePtr->buffer = nil;
325 return err;
326 }
327 ++btreePtr->numGetNewNodes;
328
329
330 ////////////////////////// initialize the node //////////////////////////////
331
332 node = returnNodePtr->buffer;
333
334 ClearNode (btreePtr, node); // clear the node
335
336 pos = (char *)node + btreePtr->nodeSize - 2; // find address of last offset
337 *(UInt16 *)pos = sizeof (BTNodeDescriptor); // set offset to beginning of free space
338
339
340 return noErr;
341 }
342
343
344
345 /*-------------------------------------------------------------------------------
346
347 Routine: ReleaseNode - Call FS Agent to release node obtained by GetNode.
348
349 Function: Informs the FS Agent that a BTree node may be released.
350
351 Input: btreePtr - pointer to BTree control block
352 nodeNum - number of node to release
353
354 Result: noErr - success
355 != noErr - failure
356 -------------------------------------------------------------------------------*/
357
358 OSStatus ReleaseNode (BTreeControlBlockPtr btreePtr,
359 NodePtr nodePtr )
360 {
361 OSStatus err;
362 ReleaseBlockProcPtr releaseNodeProc;
363
364
365 err = noErr;
366
367 if (nodePtr->buffer != nil)
368 {
369 releaseNodeProc = btreePtr->releaseBlockProc;
370 err = releaseNodeProc (btreePtr->fileRefNum,
371 nodePtr,
372 kReleaseBlock );
373 PanicIf (err, "\pReleaseNode: releaseNodeProc returned error.");
374 ++btreePtr->numReleaseNodes;
375 }
376
377 nodePtr->buffer = nil;
378 nodePtr->blockHeader = nil;
379
380 return err;
381 }
382
383
384
385
386 /*-------------------------------------------------------------------------------
387
388 Routine: TrashNode - Call FS Agent to release node obtained by GetNode, and
389 not store it...mark it as bad.
390
391 Function: Informs the FS Agent that a BTree node may be released and thrown away.
392
393 Input: btreePtr - pointer to BTree control block
394 nodeNum - number of node to release
395
396 Result: noErr - success
397 != noErr - failure
398 -------------------------------------------------------------------------------*/
399
400 OSStatus TrashNode (BTreeControlBlockPtr btreePtr,
401 NodePtr nodePtr )
402 {
403 OSStatus err;
404 ReleaseBlockProcPtr releaseNodeProc;
405
406
407 err = noErr;
408
409 if (nodePtr->buffer != nil)
410 {
411 releaseNodeProc = btreePtr->releaseBlockProc;
412 err = releaseNodeProc (btreePtr->fileRefNum,
413 nodePtr,
414 kReleaseBlock | kTrashBlock );
415 PanicIf (err, "\TrashNode: releaseNodeProc returned error.");
416 ++btreePtr->numReleaseNodes;
417 }
418
419 nodePtr->buffer = nil;
420 nodePtr->blockHeader = nil;
421
422 return err;
423 }
424
425
426
427 /*-------------------------------------------------------------------------------
428
429 Routine: UpdateNode - Mark a node as dirty and call FS Agent to release it.
430
431 Function: Marks a BTree node dirty and informs the FS Agent that it may be released.
432
433 //\80\80 have another routine that clears & writes a node, so we can call
434 CheckNode from this routine.
435
436 Input: btreePtr - pointer to BTree control block
437 nodeNum - number of node to release
438 transactionID - ID of transaction this node update is a part of
439 flags - special flags to pass to ReleaseNodeProc
440
441 Result: noErr - success
442 != noErr - failure
443 -------------------------------------------------------------------------------*/
444
445 OSStatus UpdateNode (BTreeControlBlockPtr btreePtr,
446 NodePtr nodePtr,
447 UInt32 transactionID,
448 UInt32 flags )
449 {
450 OSStatus err;
451 ReleaseBlockProcPtr releaseNodeProc;
452
453
454 err = noErr;
455
456 if (nodePtr->buffer != nil) //\80\80 why call UpdateNode if nil ?!?
457 {
458 if (DEBUG_BUILD)
459 {
460 if ( btreePtr->attributes & kBTVariableIndexKeysMask )
461 (void) CheckNode (btreePtr, nodePtr->buffer);
462 }
463
464 releaseNodeProc = btreePtr->releaseBlockProc;
465 err = releaseNodeProc (btreePtr->fileRefNum,
466 nodePtr,
467 flags | kMarkBlockDirty );
468 ++btreePtr->numUpdateNodes;
469 M_ExitOnError (err);
470 }
471
472 nodePtr->buffer = nil;
473 nodePtr->blockHeader = nil;
474
475 return noErr;
476
477 ErrorExit:
478
479 return err;
480 }
481
482
483
484 /*-------------------------------------------------------------------------------
485
486 Routine: CheckNode - Checks the validity of a node.
487
488 Function: Checks the validity of a node by verifying that the fLink and bLink fields
489 are within the forks EOF. The node type must be one of the four known
490 types. The node height must be less than or equal to the tree height. The
491 node must not have more than the maximum number of records, and the record
492 offsets must make sense.
493
494 Input: btreePtr - pointer to BTree control block
495 node - pointer to node to check
496
497 Result: noErr - success
498 fsBTInvalidNodeErr - failure
499 -------------------------------------------------------------------------------*/
500
501 OSStatus CheckNode (BTreeControlBlockPtr btreePtr, NodeDescPtr node )
502 {
503 SInt32 index;
504 SInt32 maxRecords;
505 UInt32 maxNode;
506 UInt16 nodeSize;
507 UInt16 offset;
508 UInt16 prevOffset;
509
510 nodeSize = btreePtr->nodeSize;
511
512 ///////////////////// are fLink and bLink within EOF ////////////////////////
513
514 maxNode = (GetFileControlBlock(btreePtr->fileRefNum)->fcbEOF / nodeSize) - 1;
515
516 if ( (node->fLink > maxNode) || (node->bLink > maxNode) )
517 return fsBTInvalidNodeErr;
518
519 /////////////// check node type (leaf, index, header, map) //////////////////
520
521 if ( (node->kind < kBTLeafNode) || (node->kind > kBTMapNode) )
522 return fsBTInvalidNodeErr;
523
524 ///////////////////// is node height > tree depth? //////////////////////////
525
526 if ( node->height > btreePtr->treeDepth )
527 return fsBTInvalidNodeErr;
528
529 //////////////////////// check number of records ////////////////////////////
530
531 //XXX can we calculate a more accurate minimum record size?
532 maxRecords = ( nodeSize - sizeof (BTNodeDescriptor) ) >> 3;
533
534 if (node->numRecords == 0 || node->numRecords > maxRecords)
535 return fsBTInvalidNodeErr;
536
537 ////////////////////////// check record offsets /////////////////////////////
538
539 index = node->numRecords; /* start index at free space */
540 prevOffset = nodeSize - (index << 1); /* use 2 bytes past end of free space */
541
542 do {
543 offset = GetRecordOffset (btreePtr, node, index);
544
545 if (offset & 1) // offset is odd
546 return fsBTInvalidNodeErr;
547
548 if (offset >= prevOffset) // offset >= previous offset
549 return fsBTInvalidNodeErr;
550
551 /* reject keys that overflow record slot */
552 if ((node->kind == kBTLeafNode) &&
553 (index < node->numRecords) && /* ignore free space record */
554 (CalcKeySize(btreePtr, (KeyPtr) ((Ptr)node + offset)) > (prevOffset - offset))) {
555 return fsBTInvalidNodeErr;
556 }
557
558 prevOffset = offset;
559 } while ( --index >= 0 );
560
561 if (offset < sizeof (BTNodeDescriptor) ) // first offset < minimum ?
562 return fsBTInvalidNodeErr;
563
564 return noErr;
565 }
566
567
568 #if HFS_DIAGNOSTIC
569 static void PrintNode(const NodeDescPtr node, UInt16 nodeSize, UInt32 nodeNumber)
570 {
571 struct row {
572 UInt16 word[8];
573 };
574 struct row *offset;
575 UInt16 rows;
576 UInt32 *lp;
577
578 PRINTIT("Dump of B-tree node #%ld ($%08lX)\n", nodeNumber, nodeNumber);
579
580 rows = nodeSize/16;
581 lp = (UInt32*) node;
582 offset = 0;
583
584 while (rows-- > 0)
585 PRINTIT("%04X: %08lX %08lX %08lX %08lX\n", (u_int)offset++, *lp++, *lp++, *lp++, *lp++);
586 }
587 #endif
588
589
590 /*-------------------------------------------------------------------------------
591
592 Routine: ClearNode - Clear a node to all zeroes.
593
594 Function: Writes zeroes from beginning of node for nodeSize bytes.
595
596 Input: btreePtr - pointer to BTree control block
597 node - pointer to node to clear
598
599 Result: none
600 -------------------------------------------------------------------------------*/
601
602 void ClearNode (BTreeControlBlockPtr btreePtr, NodeDescPtr node )
603 {
604 ClearMemory( node, btreePtr->nodeSize );
605 }
606
607 /*-------------------------------------------------------------------------------
608
609 Routine: InsertRecord - Inserts a record into a BTree node.
610
611 Function:
612
613 Note: Record size must be even!
614
615 Input: btreePtr - pointer to BTree control block
616 node - pointer to node to insert the record
617 index - position record is to be inserted
618 recPtr - pointer to record to insert
619
620 Result: noErr - success
621 fsBTFullErr - record larger than remaining free space.
622 -------------------------------------------------------------------------------*/
623
624 Boolean InsertRecord (BTreeControlBlockPtr btreePtr,
625 NodeDescPtr node,
626 UInt16 index,
627 RecordPtr recPtr,
628 UInt16 recSize )
629 {
630 UInt16 freeSpace;
631 UInt16 indexOffset;
632 UInt16 freeOffset;
633 UInt16 bytesToMove;
634 void *src;
635 void *dst;
636
637 //// will new record fit in node?
638
639 freeSpace = GetNodeFreeSize (btreePtr, node);
640 //\80\80 we could get freeOffset & calc freeSpace
641 if ( freeSpace < recSize + 2)
642 {
643 return false;
644 }
645
646
647 //// make hole for new record
648
649 indexOffset = GetRecordOffset (btreePtr, node, index);
650 freeOffset = GetRecordOffset (btreePtr, node, node->numRecords);
651
652 src = ((Ptr) node) + indexOffset;
653 dst = ((Ptr) src) + recSize;
654 bytesToMove = freeOffset - indexOffset;
655 if (bytesToMove)
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 //\80\80 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 if (bytesToMove)
742 MoveRecordsRight (src, dst, bytesToMove);
743
744
745 //// adjust offsets for moved records
746
747 InsertOffset (btreePtr, node, index, keySize + recSize);
748
749
750 //// copy record key
751
752 dst = ((UInt8 *) node) + indexOffset;
753
754 if ( btreePtr->attributes & kBTBigKeysMask )
755 {
756 *((UInt16*) dst)++ = keyLength; // use keyLength rather than key.length
757 rawKeyLength = keyPtr->length16;
758 sizeOfLength = 2;
759 }
760 else
761 {
762 *dst++ = keyLength; // use keyLength rather than key.length
763 rawKeyLength = keyPtr->length8;
764 sizeOfLength = 1;
765 }
766
767 MoveRecordsLeft ( ((UInt8 *) keyPtr) + sizeOfLength, dst, rawKeyLength); // copy key
768
769 // any pad bytes?
770 bytesToMove = keySize - rawKeyLength;
771 if (bytesToMove)
772 ClearMemory (dst + rawKeyLength, bytesToMove); // clear pad bytes in index key
773
774
775 //// copy record data
776
777 dst = ((UInt8 *) node) + indexOffset + keySize;
778 MoveRecordsLeft (recPtr, dst, recSize);
779
780 return true;
781 }
782
783
784
785 /*-------------------------------------------------------------------------------
786
787 Routine: DeleteRecord - Deletes a record from a BTree node.
788
789 Function:
790
791 Input: btreePtr - pointer to BTree control block
792 node - pointer to node to insert the record
793 index - position record is to be inserted
794
795 Result: none
796 -------------------------------------------------------------------------------*/
797
798 void DeleteRecord (BTreeControlBlockPtr btreePtr,
799 NodeDescPtr node,
800 UInt16 index )
801 {
802 SInt16 indexOffset;
803 SInt16 nextOffset;
804 SInt16 freeOffset;
805 SInt16 bytesToMove;
806 void *src;
807 void *dst;
808
809 //// compress records
810 indexOffset = GetRecordOffset (btreePtr, node, index);
811 nextOffset = GetRecordOffset (btreePtr, node, index + 1);
812 freeOffset = GetRecordOffset (btreePtr, node, node->numRecords);
813
814 src = ((Ptr) node) + nextOffset;
815 dst = ((Ptr) node) + indexOffset;
816 bytesToMove = freeOffset - nextOffset;
817 if (bytesToMove)
818 MoveRecordsLeft (src, dst, bytesToMove);
819
820 //// Adjust the offsets
821 DeleteOffset (btreePtr, node, index);
822
823 /* clear out new free space */
824 bytesToMove = nextOffset - indexOffset;
825 ClearMemory(GetRecordAddress(btreePtr, node, node->numRecords), bytesToMove);
826
827 }
828
829
830
831 /*-------------------------------------------------------------------------------
832
833 Routine: SearchNode - Return index for record that matches key.
834
835 Function: Returns the record index for the record that matches the search key.
836 If no record was found that matches the search key, the "insert index"
837 of where the record should go is returned instead.
838
839 Algorithm: A binary search algorithm is used to find the specified key.
840
841 Input: btreePtr - pointer to BTree control block
842 node - pointer to node that contains the record
843 searchKey - pointer to the key to match
844
845 Output: index - pointer to beginning of key for record
846
847 Result: true - success (index = record index)
848 false - key did not match anything in node (index = insert index)
849 -------------------------------------------------------------------------------*/
850 Boolean
851 SearchNode( BTreeControlBlockPtr btreePtr,
852 NodeDescPtr node,
853 KeyPtr searchKey,
854 UInt16 *returnIndex )
855 {
856 SInt32 lowerBound;
857 SInt32 upperBound;
858 SInt32 index;
859 SInt32 result;
860 KeyPtr trialKey;
861 UInt16 *offset;
862 KeyCompareProcPtr compareProc = btreePtr->keyCompareProc;
863
864 lowerBound = 0;
865 upperBound = node->numRecords - 1;
866 offset = (UInt16 *) ((UInt8 *)(node) + (btreePtr)->nodeSize - kOffsetSize);
867
868 while (lowerBound <= upperBound) {
869 index = (lowerBound + upperBound) >> 1;
870
871 trialKey = (KeyPtr) ((UInt8 *)node + *(offset - index));
872
873 result = compareProc(searchKey, trialKey);
874
875 if (result < 0) {
876 upperBound = index - 1; /* search < trial */
877 } else if (result > 0) {
878 lowerBound = index + 1; /* search > trial */
879 } else {
880 *returnIndex = index; /* search == trial */
881 return true;
882 }
883 }
884
885 *returnIndex = lowerBound; /* lowerBound is insert index */
886 return false;
887 }
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); //\80\80 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. //\80\80 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
mirror of XNU