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