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