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


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