]> git.saurik.com Git - apple/hfs.git/blob - core/BTreeNodeOps.c
projects / apple / hfs.git / blob
? search:


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