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


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