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


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