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