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