~ubuntu-branches/ubuntu/trusty/hfsprogs/trusty-proposed
» Revision
12
: .pc/0010-Rename-custom-macro-nil-with-NULL.patch/fsck_hfs.tproj/dfalib/BTreeTreeOps.c
« back to all changes in this revision
Viewing changes to .pc/0010-Rename-custom-macro-nil-with-NULL.patch/fsck_hfs.tproj/dfalib/BTreeTreeOps.c
- browse files at revision 12
- compare with another revision
- download diff
- download tarball
- view history from revision 12
- Committer: Package Import Robot
- Author(s): Rogério Brito
- Date: 2013-10-24 01:20:15 UTC
- Revision ID: package-import@ubuntu.com-20131024012015-qsncxmr4cielybvz
Tags: 332.25-11
* debian/control: Remove DMUA flag.
* debian/rules: Override rules for which we don't have makefiles.
(Closes: #724195)
* debian/patches:
+ Change the headers to be friendlier with gbp pq.
+ Remove unreferenced patches in series file.
+ Coalesce all patches touching man pages into one.
+ Regenerate everything from patch-queue branch.
* debian/rules: Override rules for which we don't have makefiles.
(Closes: #724195)
* debian/patches:
+ Change the headers to be friendlier with gbp pq.
+ Remove unreferenced patches in series file.
+ Coalesce all patches touching man pages into one.
+ Regenerate everything from patch-queue branch.
- files added:
- .pc/.quilt_patches
- .pc/0001-Create-short-Makefiles-for-Debian.patch
- .pc/0001-Create-short-Makefiles-for-Debian.patch/fsck_hfs.tproj
- .pc/0001-Create-short-Makefiles-for-Debian.patch/fsck_hfs.tproj/dfalib
- .pc/0001-Create-short-Makefiles-for-Debian.patch/newfs_hfs.tproj
- .pc/0002-Add-exclude-Darwin-specific-code.patch
- .pc/0002-Add-exclude-Darwin-specific-code.patch/fsck_hfs.tproj
- .pc/0002-Add-exclude-Darwin-specific-code.patch/fsck_hfs.tproj/dfalib
- .pc/0002-Add-exclude-Darwin-specific-code.patch/include
- .pc/0002-Add-exclude-Darwin-specific-code.patch/newfs_hfs.tproj
- .pc/0003-Add-helper-include-files-absent-from-the-upstream-pa.patch
- .pc/0003-Add-helper-include-files-absent-from-the-upstream-pa.patch/include
- .pc/0003-Add-helper-include-files-absent-from-the-upstream-pa.patch/include/hfs
- .pc/0003-Add-helper-include-files-absent-from-the-upstream-pa.patch/include/sys
- .pc/0004-Fix-compilation-on-64-bit-arches.patch
- .pc/0004-Fix-compilation-on-64-bit-arches.patch/fsck_hfs.tproj
- .pc/0004-Fix-compilation-on-64-bit-arches.patch/fsck_hfs.tproj/dfalib
- .pc/0005-Remove-Apple-specific-p-from-strings.patch
- .pc/0005-Remove-Apple-specific-p-from-strings.patch/fsck_hfs.tproj
- .pc/0005-Remove-Apple-specific-p-from-strings.patch/fsck_hfs.tproj/dfalib
- .pc/0006-Adjust-types-for-printing.patch
- .pc/0006-Adjust-types-for-printing.patch/fsck_hfs.tproj
- .pc/0006-Adjust-types-for-printing.patch/fsck_hfs.tproj/dfalib
- .pc/0007-Fix-path-for-HFS-wrapper-block.patch
- .pc/0007-Fix-path-for-HFS-wrapper-block.patch/newfs_hfs.tproj
- .pc/0008-Provide-command-line-option-a.patch
- .pc/0008-Provide-command-line-option-a.patch/fsck_hfs.tproj
- .pc/0009-Rename-dprintf-to-dbg_printf.patch
- .pc/0009-Rename-dprintf-to-dbg_printf.patch/fsck_hfs.tproj
- .pc/0009-Rename-dprintf-to-dbg_printf.patch/fsck_hfs.tproj/dfalib
- .pc/0010-Rename-custom-macro-nil-with-NULL.patch
- .pc/0010-Rename-custom-macro-nil-with-NULL.patch/fsck_hfs.tproj
- .pc/0010-Rename-custom-macro-nil-with-NULL.patch/fsck_hfs.tproj/dfalib
- .pc/0011-Fix-types.patch
- .pc/0011-Fix-types.patch/fsck_hfs.tproj
- .pc/0012-Fix-mkfs-not-creating-UUIDs-for-new-filesystems.patch
- .pc/0012-Fix-mkfs-not-creating-UUIDs-for-new-filesystems.patch/include
- .pc/0013-Fix-manpages.patch
- .pc/0013-Fix-manpages.patch/fsck_hfs.tproj
- .pc/0013-Fix-manpages.patch/newfs_hfs.tproj
- files removed:
- .pc/00-create_makefiles.patch
- .pc/00-create_makefiles.patch/fsck_hfs.tproj
- .pc/00-create_makefiles.patch/fsck_hfs.tproj/dfalib
- .pc/00-create_makefiles.patch/newfs_hfs.tproj
- .pc/10-linux_specific_code.patch
- .pc/10-linux_specific_code.patch/fsck_hfs.tproj
- .pc/10-linux_specific_code.patch/fsck_hfs.tproj/dfalib
- .pc/10-linux_specific_code.patch/include
- .pc/10-linux_specific_code.patch/newfs_hfs.tproj
- .pc/20-apple_specific_files.patch
- .pc/20-apple_specific_files.patch/include
- .pc/20-apple_specific_files.patch/include/hfs
- .pc/20-apple_specific_files.patch/include/sys
- .pc/25-64-bit-fix.patch
- .pc/25-64-bit-fix.patch/fsck_hfs.tproj
- .pc/25-64-bit-fix.patch/fsck_hfs.tproj/dfalib
- .pc/30-formatting_strings.patch
- .pc/30-formatting_strings.patch/fsck_hfs.tproj
- .pc/30-formatting_strings.patch/fsck_hfs.tproj/dfalib
- .pc/40-printf_types.patch
- .pc/40-printf_types.patch/fsck_hfs.tproj
- .pc/40-printf_types.patch/fsck_hfs.tproj/dfalib
- .pc/50-typo-new_fs-manpage.diff
- .pc/50-typo-new_fs-manpage.diff/newfs_hfs.tproj
- .pc/60-hfs-wrapper-boot-in-usr-share.diff
- .pc/60-hfs-wrapper-boot-in-usr-share.diff/newfs_hfs.tproj
- .pc/70-diskdev_cmds_system_check-332.14.patch
- .pc/70-diskdev_cmds_system_check-332.14.patch/fsck_hfs.tproj
- .pc/80-fix_manpages.patch
- .pc/80-fix_manpages.patch/fsck_hfs.tproj
- .pc/80-fix_manpages.patch/newfs_hfs.tproj
- .pc/90-rename_dprintf.patch
- .pc/90-rename_dprintf.patch/fsck_hfs.tproj
- .pc/90-rename_dprintf.patch/fsck_hfs.tproj/dfalib
- .pc/91-remove-nils.patch
- .pc/91-remove-nils.patch/fsck_hfs.tproj
- .pc/91-remove-nils.patch/fsck_hfs.tproj/dfalib
- .pc/92-fix-types.patch
- .pc/92-fix-types.patch/fsck_hfs.tproj
- .pc/hfsplus-tools-332.14-fix-uuid.patch
- .pc/hfsplus-tools-332.14-fix-uuid.patch/include
- files modified:
- .pc/applied-patches
added
removed
.pc/0010-Rename-custom-macro-nil-with-NULL.patch/fsck_hfs.tproj/dfalib/BTreeTreeOps.c
1
/*
2
* Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
3
*
4
* @APPLE_LICENSE_HEADER_START@
5
*
6
* "Portions Copyright (c) 1999 Apple Computer, Inc. All Rights
7
* Reserved. This file contains Original Code and/or Modifications of
8
* Original Code as defined in and that are subject to the Apple Public
9
* Source License Version 1.0 (the 'License'). You may not use this file
10
* except in compliance with the License. Please obtain a copy of the
11
* License at http://www.apple.com/publicsource and read it before using
12
* this file.
13
*
14
* The Original Code and all software distributed under the License are
15
* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
16
* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
17
* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
18
* FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
19
* License for the specific language governing rights and limitations
20
* under the License."
21
*
22
* @APPLE_LICENSE_HEADER_END@
23
*/
24
/*
25
File: BTreeTreeOps.c
26
27
Contains: Multi-node tree operations for the BTree Module.
28
29
Version: xxx put the technology version here xxx
30
31
Written by: Gordon Sheridan and Bill Bruffey
32
33
Copyright: � 1992-1997, 1999 by Apple Computer, Inc., all rights reserved.
34
*/
35
36
#include "BTreePrivate.h"
37
38
#define DEBUG_TREEOPS 0
39
40
/////////////////////// Routines Internal To BTree Module ///////////////////////
41
//
42
// SearchTree
43
// InsertTree
44
//
45
////////////////////// Routines Internal To BTreeTreeOps.c //////////////////////
46
47
static OSStatus AddNewRootNode (BTreeControlBlockPtr btreePtr,
48
NodeDescPtr leftNode,
49
NodeDescPtr rightNode );
50
51
static OSStatus CollapseTree (BTreeControlBlockPtr btreePtr,
52
BlockDescriptor *blockPtr );
53
54
static OSStatus RotateLeft (BTreeControlBlockPtr btreePtr,
55
NodeDescPtr leftNode,
56
NodeDescPtr rightNode,
57
UInt16 rightInsertIndex,
58
KeyPtr keyPtr,
59
UInt8 * recPtr,
60
UInt16 recSize,
61
UInt16 *insertIndex,
62
UInt32 *insertNodeNum,
63
Boolean *recordFit,
64
UInt16 *recsRotated );
65
66
static Boolean RotateRecordLeft (BTreeControlBlockPtr btreePtr,
67
NodeDescPtr leftNode,
68
NodeDescPtr rightNode );
69
70
#if 0
71
static OSStatus SplitLeft (BTreeControlBlockPtr btreePtr,
72
BlockDescriptor *leftNode,
73
BlockDescriptor *rightNode,
74
UInt32 rightNodeNum,
75
UInt16 index,
76
KeyPtr keyPtr,
77
UInt8 * recPtr,
78
UInt16 recSize,
79
UInt16 *insertIndex,
80
UInt32 *insertNodeNum,
81
UInt16 *recsRotated );
82
#endif
83
84
85
static OSStatus InsertLevel (BTreeControlBlockPtr btreePtr,
86
TreePathTable treePathTable,
87
InsertKey *primaryKey,
88
InsertKey *secondaryKey,
89
BlockDescriptor *targetNode,
90
UInt16 index,
91
UInt16 level,
92
UInt32 *insertNode );
93
94
static OSErr InsertNode (BTreeControlBlockPtr btreePtr,
95
InsertKey *key,
96
BlockDescriptor *targetNode,
97
UInt32 node,
98
UInt16 index,
99
UInt32 *newNode,
100
UInt16 *newIndex,
101
BlockDescriptor *leftNode,
102
Boolean *updateParent,
103
Boolean *insertParent,
104
Boolean *rootSplit );
105
106
static UInt16 GetKeyLength (const BTreeControlBlock *btreePtr,
107
const BTreeKey *key,
108
Boolean forLeafNode );
109
110
static Boolean RotateRecordRight( BTreeControlBlockPtr btreePtr,
111
NodeDescPtr leftNode,
112
NodeDescPtr rightNode );
113
114
static OSStatus RotateRight( BTreeControlBlockPtr btreePtr,
115
NodeDescPtr leftNode,
116
NodeDescPtr rightNode,
117
UInt16 leftInsertIndex,
118
KeyPtr keyPtr,
119
UInt8 * recPtr,
120
UInt16 recSize,
121
UInt16 *insertIndex,
122
UInt32 *insertNodeNum,
123
Boolean *recordFit,
124
UInt16 *recsRotated );
125
126
static OSStatus SplitRight( BTreeControlBlockPtr btreePtr,
127
BlockDescriptor *nodePtr,
128
BlockDescriptor *rightNodePtr,
129
UInt32 nodeNum,
130
UInt16 index,
131
KeyPtr keyPtr,
132
UInt8 *recPtr,
133
UInt16 recSize,
134
UInt16 *insertIndexPtr,
135
UInt32 *newNodeNumPtr,
136
UInt16 *recsRotatedPtr );
137
138
#if DEBUG_TREEOPS
139
static int DoKeyCheck( NodeDescPtr nodeP, BTreeControlBlock *btcb );
140
static int DoKeyCheckAcrossNodes( NodeDescPtr theLeftNodePtr,
141
NodeDescPtr theRightNodePtr,
142
BTreeControlBlock *theTreePtr,
143
Boolean printKeys );
144
static void PrintNodeDescriptor( NodeDescPtr thePtr );
145
static void PrintKey( UInt8 * myPtr, int mySize );
146
#endif // DEBUG_TREEOPS
147
148
149
/* used by InsertLevel (and called routines) to communicate the state of an insert operation */
150
enum
151
{
152
kInsertParent = 0x0001,
153
kUpdateParent = 0x0002,
154
kNewRoot = 0x0004,
155
kInsertedInRight = 0x0008,
156
kRecordFits = 0x0010
157
};
158
159
160
//////////////////////// BTree Multi-node Tree Operations ///////////////////////
161
162
163
/*-------------------------------------------------------------------------------
164
165
Routine: SearchTree - Search BTree for key and set up Tree Path Table.
166
167
Function: Searches BTree for specified key, setting up the Tree Path Table to
168
reflect the search path.
169
170
171
Input: btreePtr - pointer to control block of BTree to search
172
keyPtr - pointer to the key to search for
173
treePathTable - pointer to the tree path table to construct
174
175
Output: nodeNum - number of the node containing the key position
176
iterator - BTreeIterator specifying record or insert position
177
178
Result: noErr - key found, index is record index
179
fsBTRecordNotFoundErr - key not found, index is insert index
180
fsBTEmptyErr - key not found, return params are nil
181
otherwise - catastrophic failure (GetNode/ReleaseNode failed)
182
-------------------------------------------------------------------------------*/
183
184
OSStatus SearchTree (BTreeControlBlockPtr btreePtr,
185
BTreeKeyPtr searchKey,
186
TreePathTable treePathTable,
187
UInt32 *nodeNum,
188
BlockDescriptor *nodePtr,
189
UInt16 *returnIndex )
190
{
191
OSStatus err;
192
SInt16 level;
193
UInt32 curNodeNum;
194
NodeRec nodeRec;
195
UInt16 index;
196
Boolean keyFound;
197
SInt8 nodeKind; // Kind of current node (index/leaf)
198
KeyPtr keyPtr;
199
UInt8 * dataPtr;
200
UInt16 dataSize;
201
202
203
curNodeNum = btreePtr->rootNode;
204
level = btreePtr->treeDepth;
205
206
if (level == 0) // is the tree empty?
207
{
208
err = fsBTEmptyErr;
209
goto ErrorExit;
210
}
211
212
//�� for debugging...
213
treePathTable [0].node = 0;
214
treePathTable [0].index = 0;
215
216
while (true)
217
{
218
//
219
// [2550929] Node number 0 is the header node. It is never a valid
220
// index or leaf node. If we're ever asked to search through node 0,
221
// something has gone wrong (typically a bad child node number, or
222
// we found a node full of zeroes that we thought was an index node).
223
//
224
if (curNodeNum == 0)
225
{
226
Panic("SearchTree: curNodeNum is zero!");
227
err = fsBTInvalidNodeErr;
228
goto ErrorExit;
229
}
230
231
err = GetNode (btreePtr, curNodeNum, &nodeRec);
232
if (err != noErr)
233
{
234
goto ErrorExit;
235
}
236
237
//
238
// [2550929] Sanity check the node height and node type. We expect
239
// particular values at each iteration in the search. This checking
240
// quickly finds bad pointers, loops, and other damage to the
241
// hierarchy of the B-tree.
242
//
243
if (((BTNodeDescriptor*)nodeRec.buffer)->height != level)
244
{
245
err = fsBTInvalidNodeErr;
246
goto ReleaseAndExit;
247
}
248
nodeKind = ((BTNodeDescriptor*)nodeRec.buffer)->kind;
249
if (level == 1)
250
{
251
// Nodes at level 1 must be leaves, by definition
252
if (nodeKind != kBTLeafNode)
253
{
254
err = fsBTInvalidNodeErr;
255
goto ReleaseAndExit;
256
}
257
}
258
else
259
{
260
// A node at any other depth must be an index node
261
if (nodeKind != kBTIndexNode)
262
{
263
err = fsBTInvalidNodeErr;
264
goto ReleaseAndExit;
265
}
266
}
267
268
keyFound = SearchNode (btreePtr, nodeRec.buffer, searchKey, &index);
269
270
treePathTable [level].node = curNodeNum;
271
272
if (nodeKind == kBTLeafNode)
273
{
274
treePathTable [level].index = index;
275
break; // were done...
276
}
277
278
if ( (keyFound != true) && (index != 0))
279
--index;
280
281
treePathTable [level].index = index;
282
283
err = GetRecordByIndex (btreePtr, nodeRec.buffer, index, &keyPtr, &dataPtr, &dataSize);
284
if (err != noErr)
285
{
286
// [2550929] If we got an error, it is probably because the index was bad
287
// (typically a corrupt node that confused SearchNode). Invalidate the node
288
// so we won't accidentally use the corrupted contents. NOTE: the Mac OS 9
289
// sources call this InvalidateNode.
290
291
(void) TrashNode(btreePtr, &nodeRec);
292
goto ErrorExit;
293
}
294
295
// Get the child pointer out of this index node. We're now done with the current
296
// node and can continue the search with the child node.
297
curNodeNum = *(UInt32 *)dataPtr;
298
err = ReleaseNode (btreePtr, &nodeRec);
299
if (err != noErr)
300
{
301
goto ErrorExit;
302
}
303
304
// The child node should be at a level one less than the parent.
305
--level;
306
}
307
308
*nodeNum = curNodeNum;
309
*nodePtr = nodeRec;
310
*returnIndex = index;
311
312
if (keyFound)
313
return noErr; // searchKey found, index identifies record in node
314
else
315
return fsBTRecordNotFoundErr; // searchKey not found, index identifies insert point
316
317
ReleaseAndExit:
318
(void) ReleaseNode(btreePtr, &nodeRec);
319
// fall into ErrorExit
320
321
ErrorExit:
322
323
*nodeNum = 0;
324
nodePtr->buffer = nil;
325
nodePtr->blockHeader = nil;
326
*returnIndex = 0;
327
328
return err;
329
}
330
331
332
333
334
////////////////////////////////// InsertTree ///////////////////////////////////
335
336
OSStatus InsertTree ( BTreeControlBlockPtr btreePtr,
337
TreePathTable treePathTable,
338
KeyPtr keyPtr,
339
UInt8 * recPtr,
340
UInt16 recSize,
341
BlockDescriptor *targetNode,
342
UInt16 index,
343
UInt16 level,
344
Boolean replacingKey,
345
UInt32 *insertNode )
346
{
347
InsertKey primaryKey;
348
OSStatus err;
349
350
primaryKey.keyPtr = keyPtr;
351
primaryKey.keyLength = GetKeyLength(btreePtr, primaryKey.keyPtr, (level == 1));
352
primaryKey.recPtr = recPtr;
353
primaryKey.recSize = recSize;
354
primaryKey.replacingKey = replacingKey;
355
primaryKey.skipRotate = false;
356
357
err = InsertLevel (btreePtr, treePathTable, &primaryKey, nil,
358
targetNode, index, level, insertNode );
359
360
return err;
361
362
} // End of InsertTree
363
364
365
////////////////////////////////// InsertLevel //////////////////////////////////
366
367
OSStatus InsertLevel (BTreeControlBlockPtr btreePtr,
368
TreePathTable treePathTable,
369
InsertKey *primaryKey,
370
InsertKey *secondaryKey,
371
BlockDescriptor *targetNode,
372
UInt16 index,
373
UInt16 level,
374
UInt32 *insertNode )
375
{
376
OSStatus err;
377
BlockDescriptor siblingNode;
378
UInt32 targetNodeNum;
379
UInt32 newNodeNum;
380
UInt16 newIndex;
381
Boolean insertParent;
382
Boolean updateParent;
383
Boolean newRoot;
384
385
#if defined(applec) && !defined(__SC__)
386
PanicIf ((level == 1) && (((NodeDescPtr)targetNode->buffer)->kind != kBTLeafNode), "\P InsertLevel: non-leaf at level 1! ");
387
#endif
388
siblingNode.buffer = nil;
389
targetNodeNum = treePathTable [level].node;
390
391
insertParent = false;
392
updateParent = false;
393
394
////// process first insert //////
395
396
err = InsertNode (btreePtr, primaryKey, targetNode, targetNodeNum, index,
397
&newNodeNum, &newIndex, &siblingNode, &updateParent, &insertParent, &newRoot );
398
M_ExitOnError (err);
399
400
if ( newRoot )
401
{
402
// Extend the treePathTable by adding an entry for the new
403
// root node that references the current targetNode.
404
//
405
// When we split right the index in the new root is 0 if the new
406
// node is the same as the target node or 1 otherwise. When the
407
// new node number and the target node number are the same then
408
// we inserted the new record into the left node (the orignial target)
409
// after the split.
410
411
treePathTable [level + 1].node = btreePtr->rootNode;
412
if ( targetNodeNum == newNodeNum )
413
treePathTable [level + 1].index = 0; //
414
else
415
treePathTable [level + 1].index = 1;
416
}
417
418
if ( level == 1 )
419
*insertNode = newNodeNum;
420
421
////// process second insert (if any) //////
422
423
if ( secondaryKey != nil )
424
{
425
Boolean temp;
426
427
// NOTE - we only get here if we have split a child node to the right and
428
// we are currently updating the child's parent. newIndex + 1 refers to
429
// the location in the parent node where we insert the new index record that
430
// represents the new child node (the new right node).
431
err = InsertNode (btreePtr, secondaryKey, targetNode, newNodeNum, newIndex + 1,
432
&newNodeNum, &newIndex, &siblingNode, &updateParent, &insertParent, &temp);
433
M_ExitOnError (err);
434
435
if ( DEBUG_BUILD && updateParent && newRoot )
436
DebugStr("InsertLevel: New root from primary key, update from secondary key...");
437
}
438
439
//////////////////////// Update Parent(s) ///////////////////////////////
440
441
if ( insertParent || updateParent )
442
{
443
BlockDescriptor parentNode;
444
UInt32 parentNodeNum;
445
KeyPtr keyPtr;
446
UInt8 * recPtr;
447
UInt16 recSize;
448
449
secondaryKey = nil;
450
451
PanicIf ( (level == btreePtr->treeDepth), "InsertLevel: unfinished insert!?");
452
453
++level;
454
455
// Get Parent Node data...
456
index = treePathTable [level].index;
457
parentNodeNum = treePathTable [level].node;
458
459
PanicIf ( parentNodeNum == 0, "InsertLevel: parent node is zero!?");
460
461
err = GetNode (btreePtr, parentNodeNum, &parentNode); // released as target node in next level up
462
M_ExitOnError (err);
463
#if defined(applec) && !defined(__SC__)
464
if (DEBUG_BUILD && level > 1)
465
PanicIf ( ((NodeDescPtr)parentNode.buffer)->kind != kBTIndexNode, "\P InsertLevel: parent node not an index node! ");
466
#endif
467
////////////////////////// Update Parent Index //////////////////////////////
468
469
if ( updateParent )
470
{
471
//���debug: check if ptr == targetNodeNum
472
GetRecordByIndex (btreePtr, parentNode.buffer, index, &keyPtr, &recPtr, &recSize);
473
PanicIf( (*(UInt32 *) recPtr) != targetNodeNum, "InsertLevel: parent ptr doesn't match target node!");
474
475
// need to delete and re-insert this parent key/ptr
476
// we delete it here and it gets re-inserted in the
477
// InsertLevel call below.
478
DeleteRecord (btreePtr, parentNode.buffer, index);
479
480
primaryKey->keyPtr = (KeyPtr) GetRecordAddress( btreePtr, targetNode->buffer, 0 );
481
primaryKey->keyLength = GetKeyLength(btreePtr, primaryKey->keyPtr, false);
482
primaryKey->recPtr = (UInt8 *) &targetNodeNum;
483
primaryKey->recSize = sizeof(targetNodeNum);
484
primaryKey->replacingKey = kReplaceRecord;
485
primaryKey->skipRotate = insertParent; // don't rotate left if we have two inserts occuring
486
}
487
488
////////////////////////// Add New Parent Index /////////////////////////////
489
490
if ( insertParent )
491
{
492
InsertKey *insertKeyPtr;
493
InsertKey insertKey;
494
495
if ( updateParent )
496
{
497
insertKeyPtr = &insertKey;
498
secondaryKey = &insertKey;
499
}
500
else
501
{
502
insertKeyPtr = primaryKey;
503
// split right but not updating parent for our left node then
504
// we want to insert the key for the new right node just after
505
// the key for our left node.
506
index++;
507
}
508
509
insertKeyPtr->keyPtr = (KeyPtr) GetRecordAddress (btreePtr, siblingNode.buffer, 0);
510
insertKeyPtr->keyLength = GetKeyLength(btreePtr, insertKeyPtr->keyPtr, false);
511
insertKeyPtr->recPtr = (UInt8 *) &((NodeDescPtr)targetNode->buffer)->fLink;
512
insertKeyPtr->recSize = sizeof(UInt32);
513
insertKeyPtr->replacingKey = kInsertRecord;
514
insertKeyPtr->skipRotate = false; // a rotate is OK during second insert
515
}
516
517
err = InsertLevel (btreePtr, treePathTable, primaryKey, secondaryKey,
518
&parentNode, index, level, insertNode );
519
M_ExitOnError (err);
520
}
521
522
err = UpdateNode (btreePtr, targetNode); // all done with target
523
M_ExitOnError (err);
524
525
err = UpdateNode (btreePtr, &siblingNode); // all done with left sibling
526
M_ExitOnError (err);
527
528
return noErr;
529
530
ErrorExit:
531
532
(void) ReleaseNode (btreePtr, targetNode);
533
(void) ReleaseNode (btreePtr, &siblingNode);
534
535
Panic ("InsertLevel: an error occured!");
536
537
return err;
538
539
} // End of InsertLevel
540
541
542
543
////////////////////////////////// InsertNode ///////////////////////////////////
544
545
static OSErr InsertNode (BTreeControlBlockPtr btreePtr,
546
InsertKey *key,
547
548
BlockDescriptor *targetNode,
549
UInt32 nodeNum,
550
UInt16 index,
551
552
UInt32 *newNodeNumPtr,
553
UInt16 *newIndex,
554
555
BlockDescriptor *siblingNode,
556
Boolean *updateParent,
557
Boolean *insertParent,
558
Boolean *rootSplit )
559
{
560
BlockDescriptor *tempNode;
561
UInt32 leftNodeNum;
562
UInt32 rightNodeNum;
563
UInt16 recsRotated;
564
OSErr err;
565
Boolean recordFit;
566
567
*rootSplit = false;
568
569
PanicIf ( targetNode->buffer == siblingNode->buffer, "InsertNode: targetNode == siblingNode, huh?");
570
571
leftNodeNum = ((NodeDescPtr) targetNode->buffer)->bLink;
572
rightNodeNum = ((NodeDescPtr) targetNode->buffer)->fLink;
573
574
575
/////////////////////// Try Simple Insert ///////////////////////////////
576
577
if ( nodeNum == leftNodeNum )
578
tempNode = siblingNode;
579
else
580
tempNode = targetNode;
581
582
recordFit = InsertKeyRecord (btreePtr, tempNode->buffer, index, key->keyPtr, key->keyLength, key->recPtr, key->recSize);
583
584
if ( recordFit )
585
{
586
*newNodeNumPtr = nodeNum;
587
*newIndex = index;
588
589
#if DEBUG_TREEOPS
590
if ( DoKeyCheck( tempNode->buffer, btreePtr ) != noErr )
591
{
592
printf( "\n%s - bad key order in node num %d: \n", __FUNCTION__ , nodeNum );
593
PrintNodeDescriptor( tempNode->buffer );
594
err = fsBTBadRotateErr;
595
goto ErrorExit;
596
}
597
#endif // DEBUG_TREEOPS
598
599
if ( (index == 0) && (((NodeDescPtr) tempNode->buffer)->height != btreePtr->treeDepth) )
600
*updateParent = true; // the first record changed so we need to update the parent
601
goto ExitThisRoutine;
602
}
603
604
605
//////////////////////// Try Rotate Left ////////////////////////////////
606
607
if ( leftNodeNum > 0 )
608
{
609
PanicIf ( siblingNode->buffer != nil, "InsertNode: siblingNode already aquired!");
610
611
if ( siblingNode->buffer == nil )
612
{
613
err = GetNode (btreePtr, leftNodeNum, siblingNode); // will be released by caller or a split below
614
M_ExitOnError (err);
615
}
616
617
PanicIf ( ((NodeDescPtr) siblingNode->buffer)->fLink != nodeNum, "InsertNode, RotateLeft: invalid sibling link!" );
618
619
if ( !key->skipRotate ) // are rotates allowed?
620
{
621
err = RotateLeft (btreePtr, siblingNode->buffer, targetNode->buffer, index, key->keyPtr, key->recPtr,
622
key->recSize, newIndex, newNodeNumPtr, &recordFit, &recsRotated );
623
M_ExitOnError (err);
624
625
if ( recordFit )
626
{
627
if ( key->replacingKey || (recsRotated > 1) || (index > 0) )
628
*updateParent = true;
629
goto ExitThisRoutine;
630
}
631
}
632
}
633
634
635
//////////////////////// Try Split Right /////////////////////////////////
636
637
(void) ReleaseNode( btreePtr, siblingNode );
638
err = SplitRight( btreePtr, targetNode, siblingNode, nodeNum, index, key->keyPtr,
639
key->recPtr, key->recSize, newIndex, newNodeNumPtr, &recsRotated );
640
M_ExitOnError (err);
641
642
// if we split root node - add new root
643
if ( ((NodeDescPtr) targetNode->buffer)->height == btreePtr->treeDepth )
644
{
645
err = AddNewRootNode( btreePtr, targetNode->buffer, siblingNode->buffer ); // Note: does not update TPT
646
M_ExitOnError (err);
647
*rootSplit = true;
648
}
649
else
650
{
651
*insertParent = true;
652
653
// update parent index node when replacingKey is true or when
654
// we inserted a new record at the beginning of our target node.
655
if ( key->replacingKey || ( index == 0 && *newIndex == 0 ) )
656
*updateParent = true;
657
}
658
659
ExitThisRoutine:
660
661
return noErr;
662
663
ErrorExit:
664
665
(void) ReleaseNode (btreePtr, siblingNode);
666
return err;
667
668
} // End of InsertNode
669
670
671
/*-------------------------------------------------------------------------------
672
Routine: DeleteTree - One_line_description.
673
674
Function: Brief_description_of_the_function_and_any_side_effects
675
676
ToDo:
677
678
Input: btreePtr - description
679
treePathTable - description
680
targetNode - description
681
index - description
682
683
Result: noErr - success
684
!= noErr - failure
685
-------------------------------------------------------------------------------*/
686
687
OSStatus DeleteTree (BTreeControlBlockPtr btreePtr,
688
TreePathTable treePathTable,
689
BlockDescriptor *targetNode,
690
UInt16 index,
691
UInt16 level )
692
{
693
OSStatus err;
694
BlockDescriptor parentNode;
695
BTNodeDescriptor *targetNodePtr;
696
UInt32 targetNodeNum;
697
Boolean deleteRequired;
698
Boolean updateRequired;
699
700
701
deleteRequired = false;
702
updateRequired = false;
703
704
targetNodeNum = treePathTable[level].node;
705
targetNodePtr = targetNode->buffer;
706
PanicIf (targetNodePtr == nil, "DeleteTree: targetNode has nil buffer!");
707
708
DeleteRecord (btreePtr, targetNodePtr, index);
709
710
//�� coalesce remaining records?
711
712
if ( targetNodePtr->numRecords == 0 ) // did we delete the last record?
713
{
714
BlockDescriptor siblingNode;
715
UInt32 siblingNodeNum;
716
717
deleteRequired = true;
718
719
////////////////// Get Siblings & Update Links //////////////////////////
720
721
siblingNodeNum = targetNodePtr->bLink; // Left Sibling Node
722
if ( siblingNodeNum != 0 )
723
{
724
err = GetNode (btreePtr, siblingNodeNum, &siblingNode);
725
M_ExitOnError (err);
726
((NodeDescPtr)siblingNode.buffer)->fLink = targetNodePtr->fLink;
727
err = UpdateNode (btreePtr, &siblingNode);
728
M_ExitOnError (err);
729
}
730
else if ( targetNodePtr->kind == kBTLeafNode ) // update firstLeafNode
731
{
732
btreePtr->firstLeafNode = targetNodePtr->fLink;
733
}
734
735
siblingNodeNum = targetNodePtr->fLink; // Right Sibling Node
736
if ( siblingNodeNum != 0 )
737
{
738
err = GetNode (btreePtr, siblingNodeNum, &siblingNode);
739
M_ExitOnError (err);
740
((NodeDescPtr)siblingNode.buffer)->bLink = targetNodePtr->bLink;
741
err = UpdateNode (btreePtr, &siblingNode);
742
M_ExitOnError (err);
743
}
744
else if ( targetNodePtr->kind == kBTLeafNode ) // update lastLeafNode
745
{
746
btreePtr->lastLeafNode = targetNodePtr->bLink;
747
}
748
749
//////////////////////// Free Empty Node ////////////////////////////////
750
751
ClearNode (btreePtr, targetNodePtr);
752
753
err = UpdateNode (btreePtr, targetNode);
754
M_ExitOnError (err);
755
err = FreeNode (btreePtr, targetNodeNum);
756
M_ExitOnError (err);
757
}
758
else if ( index == 0 ) // did we delete the first record?
759
{
760
updateRequired = true; // yes, so we need to update parent
761
}
762
763
764
if ( level == btreePtr->treeDepth ) // then targetNode->buffer is the root node
765
{
766
deleteRequired = false;
767
updateRequired = false;
768
769
if ( targetNode->buffer == nil ) // then root was freed and the btree is empty
770
{
771
btreePtr->rootNode = 0;
772
btreePtr->treeDepth = 0;
773
}
774
else if ( ((NodeDescPtr)targetNode->buffer)->numRecords == 1 )
775
{
776
err = CollapseTree (btreePtr, targetNode);
777
M_ExitOnError (err);
778
}
779
}
780
781
782
if ( updateRequired || deleteRequired )
783
{
784
++level; // next level
785
786
//// Get Parent Node and index
787
index = treePathTable [level].index;
788
err = GetNode (btreePtr, treePathTable[level].node, &parentNode);
789
M_ExitOnError (err);
790
791
if ( updateRequired )
792
{
793
KeyPtr keyPtr;
794
UInt8 * recPtr;
795
UInt16 recSize;
796
UInt32 insertNode;
797
798
//���debug: check if ptr == targetNodeNum
799
GetRecordByIndex (btreePtr, parentNode.buffer, index, &keyPtr, &recPtr, &recSize);
800
PanicIf( (*(UInt32 *) recPtr) != targetNodeNum, " DeleteTree: parent ptr doesn't match targetNodeNum!!");
801
802
// need to delete and re-insert this parent key/ptr
803
DeleteRecord (btreePtr, parentNode.buffer, index);
804
805
keyPtr = (KeyPtr) GetRecordAddress( btreePtr, targetNode->buffer, 0 );
806
recPtr = (UInt8 *) &targetNodeNum;
807
recSize = sizeof(targetNodeNum);
808
809
err = InsertTree (btreePtr, treePathTable, keyPtr, recPtr, recSize,
810
&parentNode, index, level, kReplaceRecord, &insertNode);
811
M_ExitOnError (err);
812
}
813
else // deleteRequired
814
{
815
err = DeleteTree (btreePtr, treePathTable, &parentNode, index, level);
816
M_ExitOnError (err);
817
}
818
}
819
820
821
err = UpdateNode (btreePtr, targetNode);
822
M_ExitOnError (err);
823
824
return noErr;
825
826
ErrorExit:
827
828
(void) ReleaseNode (btreePtr, targetNode);
829
(void) ReleaseNode (btreePtr, &parentNode);
830
831
return err;
832
833
} // end DeleteTree
834
835
836
837
///////////////////////////////// CollapseTree //////////////////////////////////
838
839
static OSStatus CollapseTree (BTreeControlBlockPtr btreePtr,
840
BlockDescriptor *blockPtr )
841
{
842
OSStatus err;
843
UInt32 originalRoot;
844
UInt32 nodeNum;
845
846
originalRoot = btreePtr->rootNode;
847
848
while (true)
849
{
850
if ( ((NodeDescPtr)blockPtr->buffer)->numRecords > 1)
851
break; // this will make a fine root node
852
853
if ( ((NodeDescPtr)blockPtr->buffer)->kind == kBTLeafNode)
854
break; // we've hit bottom
855
856
nodeNum = btreePtr->rootNode;
857
btreePtr->rootNode = GetChildNodeNum (btreePtr, blockPtr->buffer, 0);
858
--btreePtr->treeDepth;
859
860
//// Clear and Free Current Old Root Node ////
861
ClearNode (btreePtr, blockPtr->buffer);
862
err = UpdateNode (btreePtr, blockPtr);
863
M_ExitOnError (err);
864
err = FreeNode (btreePtr, nodeNum);
865
M_ExitOnError (err);
866
867
//// Get New Root Node
868
err = GetNode (btreePtr, btreePtr->rootNode, blockPtr);
869
M_ExitOnError (err);
870
}
871
872
if (btreePtr->rootNode != originalRoot)
873
M_BTreeHeaderDirty (btreePtr);
874
875
err = UpdateNode (btreePtr, blockPtr); // always update!
876
M_ExitOnError (err);
877
878
return noErr;
879
880
881
/////////////////////////////////// ErrorExit ///////////////////////////////////
882
883
ErrorExit:
884
(void) ReleaseNode (btreePtr, blockPtr);
885
return err;
886
}
887
888
889
890
////////////////////////////////// RotateLeft ///////////////////////////////////
891
892
/*-------------------------------------------------------------------------------
893
894
Routine: RotateLeft - One_line_description.
895
896
Function: Brief_description_of_the_function_and_any_side_effects
897
898
Algorithm: if rightIndex > insertIndex, subtract 1 for actual rightIndex
899
900
Input: btreePtr - description
901
leftNode - description
902
rightNode - description
903
rightInsertIndex - description
904
keyPtr - description
905
recPtr - description
906
recSize - description
907
908
Output: insertIndex
909
insertNodeNum - description
910
recordFit - description
911
recsRotated
912
913
Result: noErr - success
914
!= noErr - failure
915
-------------------------------------------------------------------------------*/
916
917
static OSStatus RotateLeft (BTreeControlBlockPtr btreePtr,
918
NodeDescPtr leftNode,
919
NodeDescPtr rightNode,
920
UInt16 rightInsertIndex,
921
KeyPtr keyPtr,
922
UInt8 * recPtr,
923
UInt16 recSize,
924
UInt16 *insertIndex,
925
UInt32 *insertNodeNum,
926
Boolean *recordFit,
927
UInt16 *recsRotated )
928
{
929
OSStatus err;
930
SInt32 insertSize;
931
SInt32 nodeSize;
932
SInt32 leftSize, rightSize;
933
SInt32 moveSize;
934
UInt16 keyLength;
935
UInt16 lengthFieldSize;
936
UInt16 index, moveIndex;
937
Boolean didItFit;
938
939
///////////////////// Determine If Record Will Fit //////////////////////////
940
941
keyLength = GetKeyLength(btreePtr, keyPtr, (rightNode->kind == kBTLeafNode));
942
943
// the key's length field is 8-bits in HFS and 16-bits in HFS+
944
if ( btreePtr->attributes & kBTBigKeysMask )
945
lengthFieldSize = sizeof(UInt16);
946
else
947
lengthFieldSize = sizeof(UInt8);
948
949
insertSize = keyLength + lengthFieldSize + recSize + sizeof(UInt16);
950
951
if ( M_IsOdd (insertSize) )
952
++insertSize; // add pad byte;
953
954
nodeSize = btreePtr->nodeSize;
955
956
// add size of insert record to right node
957
rightSize = nodeSize - GetNodeFreeSize (btreePtr, rightNode) + insertSize;
958
leftSize = nodeSize - GetNodeFreeSize (btreePtr, leftNode);
959
960
moveIndex = 0;
961
moveSize = 0;
962
963
while ( leftSize < rightSize )
964
{
965
if ( moveIndex < rightInsertIndex )
966
{
967
moveSize = GetRecordSize (btreePtr, rightNode, moveIndex) + 2;
968
}
969
else if ( moveIndex == rightInsertIndex )
970
{
971
moveSize = insertSize;
972
}
973
else // ( moveIndex > rightInsertIndex )
974
{
975
moveSize = GetRecordSize (btreePtr, rightNode, moveIndex - 1) + 2;
976
}
977
978
leftSize += moveSize;
979
rightSize -= moveSize;
980
++moveIndex;
981
}
982
983
if ( leftSize > nodeSize ) // undo last move
984
{
985
leftSize -= moveSize;
986
rightSize += moveSize;
987
--moveIndex;
988
}
989
990
if ( rightSize > nodeSize ) // record won't fit - failure, but not error
991
{
992
*insertIndex = 0;
993
*insertNodeNum = 0;
994
*recordFit = false;
995
*recsRotated = 0;
996
997
return noErr;
998
}
999
1000
// we've found balance point, moveIndex == number of records moved into leftNode
1001
1002
1003
//////////////////////////// Rotate Records /////////////////////////////////
1004
1005
*recsRotated = moveIndex;
1006
*recordFit = true;
1007
index = 0;
1008
1009
while ( index < moveIndex )
1010
{
1011
if ( index == rightInsertIndex ) // insert new record in left node
1012
{
1013
UInt16 leftInsertIndex;
1014
1015
leftInsertIndex = leftNode->numRecords;
1016
1017
didItFit = InsertKeyRecord (btreePtr, leftNode, leftInsertIndex,
1018
keyPtr, keyLength, recPtr, recSize);
1019
if ( !didItFit )
1020
{
1021
Panic ("RotateLeft: InsertKeyRecord (left) returned false!");
1022
err = fsBTBadRotateErr;
1023
goto ErrorExit;
1024
}
1025
1026
*insertIndex = leftInsertIndex;
1027
*insertNodeNum = rightNode->bLink;
1028
}
1029
else
1030
{
1031
didItFit = RotateRecordLeft (btreePtr, leftNode, rightNode);
1032
if ( !didItFit )
1033
{
1034
Panic ("RotateLeft: RotateRecordLeft returned false!");
1035
err = fsBTBadRotateErr;
1036
goto ErrorExit;
1037
}
1038
}
1039
1040
++index;
1041
}
1042
1043
if ( moveIndex <= rightInsertIndex ) // then insert new record in right node
1044
{
1045
rightInsertIndex -= index; // adjust for records already rotated
1046
1047
didItFit = InsertKeyRecord (btreePtr, rightNode, rightInsertIndex,
1048
keyPtr, keyLength, recPtr, recSize);
1049
if ( !didItFit )
1050
{
1051
Panic ("RotateLeft: InsertKeyRecord (right) returned false!");
1052
err = fsBTBadRotateErr;
1053
goto ErrorExit;
1054
}
1055
1056
*insertIndex = rightInsertIndex;
1057
*insertNodeNum = leftNode->fLink;
1058
}
1059
1060
#if DEBUG_TREEOPS
1061
if ( DoKeyCheck( leftNode, btreePtr ) != noErr )
1062
{
1063
printf( "\n%s - bad key order in left node num %d: \n", __FUNCTION__ , rightNode->bLink );
1064
PrintNodeDescriptor( leftNode );
1065
err = fsBTBadRotateErr;
1066
goto ErrorExit;
1067
}
1068
if ( DoKeyCheck( rightNode, btreePtr ) != noErr )
1069
{
1070
printf( "\n%s - bad key order in left node num %d: \n", __FUNCTION__ , leftNode->fLink );
1071
PrintNodeDescriptor( rightNode );
1072
err = fsBTBadRotateErr;
1073
goto ErrorExit;
1074
}
1075
#endif // DEBUG_TREEOPS
1076
1077
1078
return noErr;
1079
1080
1081
////////////////////////////// Error Exit ///////////////////////////////////
1082
1083
ErrorExit:
1084
1085
*insertIndex = 0;
1086
*insertNodeNum = 0;
1087
*recordFit = false;
1088
*recsRotated = 0;
1089
1090
return err;
1091
}
1092
1093
1094
#if 0
1095
/////////////////////////////////// SplitLeft ///////////////////////////////////
1096
1097
static OSStatus SplitLeft (BTreeControlBlockPtr btreePtr,
1098
BlockDescriptor *leftNode,
1099
BlockDescriptor *rightNode,
1100
UInt32 rightNodeNum,
1101
UInt16 index,
1102
KeyPtr keyPtr,
1103
UInt8 * recPtr,
1104
UInt16 recSize,
1105
UInt16 *insertIndex,
1106
UInt32 *insertNodeNum,
1107
UInt16 *recsRotated )
1108
{
1109
OSStatus err;
1110
NodeDescPtr left, right;
1111
UInt32 newNodeNum;
1112
Boolean recordFit;
1113
1114
1115
///////////////////////////// Compare Nodes /////////////////////////////////
1116
1117
right = rightNode->buffer;
1118
left = leftNode->buffer;
1119
1120
PanicIf ( right->bLink != 0 && left == 0, " SplitLeft: left sibling missing!?" );
1121
1122
//�� type should be kLeafNode or kIndexNode
1123
1124
if ( (right->height == 1) && (right->kind != kBTLeafNode) )
1125
return fsBTInvalidNodeErr;
1126
1127
if ( left != nil )
1128
{
1129
if ( left->fLink != rightNodeNum )
1130
return fsBTInvalidNodeErr; //�� E_BadSibling ?
1131
1132
if ( left->height != right->height )
1133
return fsBTInvalidNodeErr; //�� E_BadNodeHeight ?
1134
1135
if ( left->kind != right->kind )
1136
return fsBTInvalidNodeErr; //�� E_BadNodeType ?
1137
}
1138
1139
1140
///////////////////////////// Allocate Node /////////////////////////////////
1141
1142
err = AllocateNode (btreePtr, &newNodeNum);
1143
M_ExitOnError (err);
1144
1145
1146
/////////////// Update Forward Link In Original Left Node ///////////////////
1147
1148
if ( left != nil )
1149
{
1150
left->fLink = newNodeNum;
1151
err = UpdateNode (btreePtr, leftNode);
1152
M_ExitOnError (err);
1153
}
1154
1155
1156
/////////////////////// Initialize New Left Node ////////////////////////////
1157
1158
err = GetNewNode (btreePtr, newNodeNum, leftNode);
1159
M_ExitOnError (err);
1160
1161
left = leftNode->buffer;
1162
left->fLink = rightNodeNum;
1163
1164
1165
// Steal Info From Right Node
1166
1167
left->bLink = right->bLink;
1168
left->kind = right->kind;
1169
left->height = right->height;
1170
1171
right->bLink = newNodeNum; // update Right bLink
1172
1173
if ( (left->kind == kBTLeafNode) && (left->bLink == 0) )
1174
{
1175
// if we're adding a new first leaf node - update BTreeInfoRec
1176
1177
btreePtr->firstLeafNode = newNodeNum;
1178
M_BTreeHeaderDirty (btreePtr); //�� AllocateNode should have set the bit already...
1179
}
1180
1181
////////////////////////////// Rotate Left //////////////////////////////////
1182
1183
err = RotateLeft (btreePtr, left, right, index, keyPtr, recPtr, recSize,
1184
insertIndex, insertNodeNum, &recordFit, recsRotated);
1185
M_ExitOnError (err);
1186
1187
return noErr;
1188
1189
ErrorExit:
1190
1191
(void) ReleaseNode (btreePtr, leftNode);
1192
(void) ReleaseNode (btreePtr, rightNode);
1193
1194
//�� Free new node if allocated?
1195
1196
*insertIndex = 0;
1197
*insertNodeNum = 0;
1198
*recsRotated = 0;
1199
1200
return err;
1201
}
1202
#endif
1203
1204
1205
1206
/////////////////////////////// RotateRecordLeft ////////////////////////////////
1207
1208
static Boolean RotateRecordLeft (BTreeControlBlockPtr btreePtr,
1209
NodeDescPtr leftNode,
1210
NodeDescPtr rightNode )
1211
{
1212
UInt16 size;
1213
UInt8 * recPtr;
1214
Boolean recordFit;
1215
1216
size = GetRecordSize (btreePtr, rightNode, 0);
1217
recPtr = GetRecordAddress (btreePtr, rightNode, 0);
1218
1219
recordFit = InsertRecord (btreePtr, leftNode, leftNode->numRecords, recPtr, size);
1220
1221
if ( !recordFit )
1222
return false;
1223
1224
DeleteRecord (btreePtr, rightNode, 0);
1225
1226
return true;
1227
}
1228
1229
1230
//////////////////////////////// AddNewRootNode /////////////////////////////////
1231
1232
static OSStatus AddNewRootNode (BTreeControlBlockPtr btreePtr,
1233
NodeDescPtr leftNode,
1234
NodeDescPtr rightNode )
1235
{
1236
OSStatus err;
1237
BlockDescriptor rootNode;
1238
UInt32 rootNum;
1239
KeyPtr keyPtr;
1240
Boolean didItFit;
1241
UInt16 keyLength;
1242
1243
PanicIf (leftNode == nil, "AddNewRootNode: leftNode == nil");
1244
PanicIf (rightNode == nil, "AddNewRootNode: rightNode == nil");
1245
1246
1247
/////////////////////// Initialize New Root Node ////////////////////////////
1248
1249
err = AllocateNode (btreePtr, &rootNum);
1250
M_ExitOnError (err);
1251
1252
err = GetNewNode (btreePtr, rootNum, &rootNode);
1253
M_ExitOnError (err);
1254
1255
((NodeDescPtr)rootNode.buffer)->kind = kBTIndexNode;
1256
((NodeDescPtr)rootNode.buffer)->height = ++btreePtr->treeDepth;
1257
1258
1259
///////////////////// Insert Left Node Index Record /////////////////////////
1260
1261
keyPtr = (KeyPtr) GetRecordAddress (btreePtr, leftNode, 0);
1262
keyLength = GetKeyLength(btreePtr, keyPtr, false);
1263
1264
didItFit = InsertKeyRecord ( btreePtr, rootNode.buffer, 0, keyPtr, keyLength,
1265
(UInt8 *) &rightNode->bLink, 4 );
1266
1267
PanicIf ( !didItFit, "AddNewRootNode:InsertKeyRecord failed for left index record");
1268
1269
1270
//////////////////// Insert Right Node Index Record /////////////////////////
1271
1272
keyPtr = (KeyPtr) GetRecordAddress (btreePtr, rightNode, 0);
1273
keyLength = GetKeyLength(btreePtr, keyPtr, false);
1274
1275
didItFit = InsertKeyRecord ( btreePtr, rootNode.buffer, 1, keyPtr, keyLength,
1276
(UInt8 *) &leftNode->fLink, 4 );
1277
1278
PanicIf ( !didItFit, "AddNewRootNode:InsertKeyRecord failed for right index record");
1279
1280
1281
#if DEBUG_TREEOPS
1282
if ( DoKeyCheck( rootNode.buffer, btreePtr ) != noErr )
1283
{
1284
printf( "\n%s - bad key order in root node num %d: \n", __FUNCTION__ , rootNum );
1285
PrintNodeDescriptor( rootNode.buffer );
1286
err = fsBTBadRotateErr;
1287
goto ErrorExit;
1288
}
1289
#endif // DEBUG_TREEOPS
1290
1291
1292
/////////////////////////// Release Root Node ///////////////////////////////
1293
1294
err = UpdateNode (btreePtr, &rootNode);
1295
M_ExitOnError (err);
1296
1297
// update BTreeInfoRec
1298
1299
btreePtr->rootNode = rootNum;
1300
btreePtr->flags |= kBTHeaderDirty;
1301
1302
return noErr;
1303
1304
1305
////////////////////////////// Error Exit ///////////////////////////////////
1306
1307
ErrorExit:
1308
1309
return err;
1310
}
1311
1312
1313
static UInt16 GetKeyLength ( const BTreeControlBlock *btreePtr, const BTreeKey *key, Boolean forLeafNode )
1314
{
1315
UInt16 length;
1316
1317
if ( forLeafNode || btreePtr->attributes & kBTVariableIndexKeysMask )
1318
length = KeyLength (btreePtr, key); // just use actual key length
1319
else
1320
length = btreePtr->maxKeyLength; // fixed sized index key (i.e. HFS) //�� shouldn't we clear the pad bytes?
1321
1322
return length;
1323
}
1324
1325
1326
1327
/////////////////////////////////// SplitRight ///////////////////////////////////
1328
1329
static OSStatus SplitRight (BTreeControlBlockPtr btreePtr,
1330
BlockDescriptor *nodePtr,
1331
BlockDescriptor *rightNodePtr,
1332
UInt32 nodeNum,
1333
UInt16 index,
1334
KeyPtr keyPtr,
1335
UInt8 *recPtr,
1336
UInt16 recSize,
1337
UInt16 *insertIndexPtr,
1338
UInt32 *newNodeNumPtr,
1339
UInt16 *recsRotatedPtr )
1340
{
1341
OSStatus err;
1342
NodeDescPtr leftPtr, rightPtr;
1343
UInt32 newNodeNum;
1344
Boolean recordFit;
1345
1346
1347
///////////////////////////// Compare Nodes /////////////////////////////////
1348
1349
leftPtr = nodePtr->buffer;
1350
1351
if ( leftPtr->fLink != 0 )
1352
{
1353
err = GetNode( btreePtr, leftPtr->fLink, rightNodePtr );
1354
M_ExitOnError( err );
1355
}
1356
rightPtr = rightNodePtr->buffer;
1357
1358
PanicIf ( leftPtr->fLink != 0 && rightPtr == 0, "SplitRight: right sibling missing!?" );
1359
1360
//�� type should be kLeafNode or kIndexNode
1361
1362
if ( (leftPtr->height == 1) && (leftPtr->kind != kBTLeafNode) )
1363
return fsBTInvalidNodeErr;
1364
1365
if ( rightPtr != nil )
1366
{
1367
if ( rightPtr->bLink != nodeNum )
1368
return fsBTInvalidNodeErr; //�� E_BadSibling ?
1369
1370
if ( rightPtr->height != leftPtr->height )
1371
return fsBTInvalidNodeErr; //�� E_BadNodeHeight ?
1372
1373
if ( rightPtr->kind != leftPtr->kind )
1374
return fsBTInvalidNodeErr; //�� E_BadNodeType ?
1375
}
1376
1377
1378
///////////////////////////// Allocate Node /////////////////////////////////
1379
1380
err = AllocateNode (btreePtr, &newNodeNum);
1381
M_ExitOnError (err);
1382
1383
/////////////// Update backward Link In Original Right Node ///////////////////
1384
1385
if ( rightPtr != nil )
1386
{
1387
rightPtr->bLink = newNodeNum;
1388
err = UpdateNode (btreePtr, rightNodePtr);
1389
M_ExitOnError (err);
1390
}
1391
1392
/////////////////////// Initialize New Right Node ////////////////////////////
1393
1394
err = GetNewNode (btreePtr, newNodeNum, rightNodePtr );
1395
M_ExitOnError (err);
1396
1397
rightPtr = rightNodePtr->buffer;
1398
rightPtr->bLink = nodeNum;
1399
1400
1401
// Steal Info From Left Node
1402
1403
rightPtr->fLink = leftPtr->fLink;
1404
rightPtr->kind = leftPtr->kind;
1405
rightPtr->height = leftPtr->height;
1406
1407
leftPtr->fLink = newNodeNum; // update Left fLink
1408
1409
if ( (rightPtr->kind == kBTLeafNode) && (rightPtr->fLink == 0) )
1410
{
1411
// if we're adding a new last leaf node - update BTreeInfoRec
1412
1413
btreePtr->lastLeafNode = newNodeNum;
1414
M_BTreeHeaderDirty (btreePtr); //�� AllocateNode should have set the bit already...
1415
}
1416
1417
////////////////////////////// Rotate Right //////////////////////////////////
1418
1419
err = RotateRight (btreePtr, leftPtr, rightPtr, index, keyPtr, recPtr, recSize,
1420
insertIndexPtr, newNodeNumPtr, &recordFit, recsRotatedPtr);
1421
M_ExitOnError (err);
1422
1423
return noErr;
1424
1425
ErrorExit:
1426
1427
(void) ReleaseNode (btreePtr, nodePtr);
1428
(void) ReleaseNode (btreePtr, rightNodePtr);
1429
1430
//�� Free new node if allocated?
1431
1432
*insertIndexPtr = 0;
1433
*newNodeNumPtr = 0;
1434
*recsRotatedPtr = 0;
1435
1436
return err;
1437
1438
} /* SplitRight */
1439
1440
1441
1442
////////////////////////////////// RotateRight ///////////////////////////////////
1443
1444
/*-------------------------------------------------------------------------------
1445
1446
Routine: RotateRight - rotate half of .
1447
1448
Function: Brief_description_of_the_function_and_any_side_effects
1449
1450
Algorithm: if rightIndex > insertIndex, subtract 1 for actual rightIndex
1451
1452
Input: btreePtr - description
1453
leftNode - description
1454
rightNode - description
1455
leftInsertIndex - description
1456
keyPtr - description
1457
recPtr - description
1458
recSize - description
1459
1460
Output: insertIndex
1461
insertNodeNum - description
1462
recordFit - description
1463
recsRotated
1464
1465
Result: noErr - success
1466
!= noErr - failure
1467
-------------------------------------------------------------------------------*/
1468
1469
static OSStatus RotateRight (BTreeControlBlockPtr btreePtr,
1470
NodeDescPtr leftNodePtr,
1471
NodeDescPtr rightNodePtr,
1472
UInt16 leftInsertIndex,
1473
KeyPtr keyPtr,
1474
UInt8 *recPtr,
1475
UInt16 recSize,
1476
UInt16 *insertIndexPtr,
1477
UInt32 *newNodeNumPtr,
1478
Boolean *didRecordFitPtr,
1479
UInt16 *recsRotatedPtr )
1480
{
1481
OSStatus err;
1482
SInt32 insertSize;
1483
SInt32 nodeSize;
1484
SInt32 leftSize, rightSize;
1485
SInt32 moveSize;
1486
UInt16 keyLength;
1487
UInt16 lengthFieldSize;
1488
SInt16 index, moveIndex, myInsertIndex;
1489
Boolean didItFit;
1490
Boolean doIncrement = false;
1491
1492
///////////////////// Determine If Record Will Fit //////////////////////////
1493
1494
keyLength = GetKeyLength( btreePtr, keyPtr, (leftNodePtr->kind == kBTLeafNode) );
1495
1496
// the key's length field is 8-bits in HFS and 16-bits in HFS+
1497
if ( btreePtr->attributes & kBTBigKeysMask )
1498
lengthFieldSize = sizeof(UInt16);
1499
else
1500
lengthFieldSize = sizeof(UInt8);
1501
1502
insertSize = keyLength + lengthFieldSize + recSize + sizeof(UInt16);
1503
if ( M_IsOdd (insertSize) )
1504
++insertSize; // add pad byte;
1505
nodeSize = btreePtr->nodeSize;
1506
1507
// add size of insert record to left node
1508
rightSize = nodeSize - GetNodeFreeSize( btreePtr, rightNodePtr );
1509
leftSize = nodeSize - GetNodeFreeSize( btreePtr, leftNodePtr ) + insertSize;
1510
1511
moveIndex = leftNodePtr->numRecords - 1; // start at last record in the node
1512
moveSize = 0;
1513
1514
while ( rightSize < leftSize )
1515
{
1516
moveSize = GetRecordSize( btreePtr, leftNodePtr, moveIndex ) + 2;
1517
1518
if ( moveIndex == leftInsertIndex || leftNodePtr->numRecords == leftInsertIndex )
1519
moveSize += insertSize;
1520
1521
leftSize -= moveSize;
1522
rightSize += moveSize;
1523
--moveIndex;
1524
}
1525
1526
if ( rightSize > nodeSize ) // undo last move
1527
{
1528
leftSize += moveSize;
1529
rightSize -= moveSize;
1530
++moveIndex;
1531
}
1532
1533
if ( leftSize > nodeSize ) // record won't fit - failure, but not error
1534
{
1535
*insertIndexPtr = 0;
1536
*newNodeNumPtr = 0;
1537
*didRecordFitPtr = false;
1538
*recsRotatedPtr = 0;
1539
1540
return noErr;
1541
}
1542
1543
// we've found balance point,
1544
1545
//////////////////////////// Rotate Records /////////////////////////////////
1546
1547
*didRecordFitPtr = true;
1548
index = leftNodePtr->numRecords - 1;
1549
*recsRotatedPtr = index - moveIndex;
1550
myInsertIndex = 0;
1551
1552
// handle case where the new record is inserting after the last
1553
// record in our left node.
1554
if ( leftNodePtr->numRecords == leftInsertIndex )
1555
{
1556
didItFit = InsertKeyRecord (btreePtr, rightNodePtr, 0,
1557
keyPtr, keyLength, recPtr, recSize);
1558
if ( !didItFit )
1559
{
1560
Panic ("RotateRight: InsertKeyRecord (left) returned false!");
1561
err = fsBTBadRotateErr;
1562
goto ErrorExit;
1563
}
1564
1565
// NOTE - our insert location will slide as we insert more records
1566
doIncrement = true;
1567
*newNodeNumPtr = leftNodePtr->fLink;
1568
}
1569
1570
while ( index > moveIndex )
1571
{
1572
didItFit = RotateRecordRight( btreePtr, leftNodePtr, rightNodePtr );
1573
if ( !didItFit )
1574
{
1575
Panic ("RotateRight: RotateRecordRight returned false!");
1576
err = fsBTBadRotateErr;
1577
goto ErrorExit;
1578
}
1579
1580
if ( index == leftInsertIndex ) // insert new record in right node
1581
{
1582
didItFit = InsertKeyRecord (btreePtr, rightNodePtr, 0,
1583
keyPtr, keyLength, recPtr, recSize);
1584
if ( !didItFit )
1585
{
1586
Panic ("RotateRight: InsertKeyRecord (left) returned false!");
1587
err = fsBTBadRotateErr;
1588
goto ErrorExit;
1589
}
1590
1591
// NOTE - our insert index will slide as we insert more records
1592
doIncrement = true;
1593
myInsertIndex = -1;
1594
*newNodeNumPtr = leftNodePtr->fLink;
1595
}
1596
1597
if ( doIncrement )
1598
myInsertIndex++;
1599
--index;
1600
}
1601
1602
*insertIndexPtr = myInsertIndex;
1603
1604
if ( moveIndex >= leftInsertIndex ) // then insert new record in left node
1605
{
1606
didItFit = InsertKeyRecord (btreePtr, leftNodePtr, leftInsertIndex,
1607
keyPtr, keyLength, recPtr, recSize);
1608
if ( !didItFit )
1609
{
1610
Panic ("RotateRight: InsertKeyRecord (right) returned false!");
1611
err = fsBTBadRotateErr;
1612
goto ErrorExit;
1613
}
1614
1615
*insertIndexPtr = leftInsertIndex;
1616
*newNodeNumPtr = rightNodePtr->bLink;
1617
}
1618
1619
#if DEBUG_TREEOPS
1620
if ( DoKeyCheck( rightNodePtr, btreePtr ) != noErr )
1621
{
1622
printf( "\n%s - bad key order in right node num %d: \n", __FUNCTION__ , leftNodePtr->fLink);
1623
PrintNodeDescriptor( rightNodePtr );
1624
err = fsBTBadRotateErr;
1625
goto ErrorExit;
1626
}
1627
if ( DoKeyCheck( leftNodePtr, btreePtr ) != noErr )
1628
{
1629
printf( "\n%s - bad key order in left node num %d: \n", __FUNCTION__ , rightNodePtr->bLink);
1630
PrintNodeDescriptor( leftNodePtr );
1631
err = fsBTBadRotateErr;
1632
goto ErrorExit;
1633
}
1634
if ( DoKeyCheckAcrossNodes( leftNodePtr, rightNodePtr, btreePtr, false ) != noErr )
1635
{
1636
printf( "\n%s - bad key order across nodes left %d right %d: \n",
1637
__FUNCTION__ , rightNodePtr->bLink, leftNodePtr->fLink );
1638
PrintNodeDescriptor( leftNodePtr );
1639
PrintNodeDescriptor( rightNodePtr );
1640
err = fsBTBadRotateErr;
1641
goto ErrorExit;
1642
}
1643
#endif // DEBUG_TREEOPS
1644
1645
return noErr;
1646
1647
1648
////////////////////////////// Error Exit ///////////////////////////////////
1649
1650
ErrorExit:
1651
1652
*insertIndexPtr = 0;
1653
*newNodeNumPtr = 0;
1654
*didRecordFitPtr = false;
1655
*recsRotatedPtr = 0;
1656
1657
return err;
1658
1659
} /* RotateRight */
1660
1661
1662
1663
/////////////////////////////// RotateRecordRight ////////////////////////////////
1664
1665
static Boolean RotateRecordRight (BTreeControlBlockPtr btreePtr,
1666
NodeDescPtr leftNodePtr,
1667
NodeDescPtr rightNodePtr )
1668
{
1669
UInt16 size;
1670
UInt8 * recPtr;
1671
Boolean didRecordFit;
1672
1673
size = GetRecordSize( btreePtr, leftNodePtr, leftNodePtr->numRecords - 1 ) ;
1674
recPtr = GetRecordAddress( btreePtr, leftNodePtr, leftNodePtr->numRecords - 1 ) ;
1675
1676
didRecordFit = InsertRecord( btreePtr, rightNodePtr, 0, recPtr, size );
1677
if ( !didRecordFit )
1678
return false;
1679
1680
DeleteRecord( btreePtr, leftNodePtr, leftNodePtr->numRecords - 1 );
1681
1682
return true;
1683
1684
} /* RotateRecordRight */
1685
1686
1687
1688
#if DEBUG_TREEOPS
1689
static int DoKeyCheckAcrossNodes( NodeDescPtr theLeftNodePtr,
1690
NodeDescPtr theRightNodePtr,
1691
BTreeControlBlock *theTreePtr,
1692
Boolean printKeys )
1693
{
1694
UInt16 myLeftDataSize;
1695
UInt16 myRightDataSize;
1696
UInt16 myRightKeyLen;
1697
UInt16 myLeftKeyLen;
1698
KeyPtr myLeftKeyPtr;
1699
KeyPtr myRightKeyPtr;
1700
UInt8 * myLeftDataPtr;
1701
UInt8 * myRightDataPtr;
1702
1703
1704
GetRecordByIndex( theTreePtr, theLeftNodePtr, (theLeftNodePtr->numRecords - 1),
1705
&myLeftKeyPtr, &myLeftDataPtr, &myLeftDataSize );
1706
GetRecordByIndex( theTreePtr, theRightNodePtr, 0,
1707
&myRightKeyPtr, &myRightDataPtr, &myRightDataSize );
1708
1709
if ( theTreePtr->attributes & kBTBigKeysMask )
1710
{
1711
myRightKeyLen = myRightKeyPtr->length16;
1712
myLeftKeyLen = myLeftKeyPtr->length16;
1713
}
1714
else
1715
{
1716
myRightKeyLen = myRightKeyPtr->length8;
1717
myLeftKeyLen = myLeftKeyPtr->length8;
1718
}
1719
1720
if ( printKeys )
1721
{
1722
printf( "%s - left and right keys:\n", __FUNCTION__ );
1723
PrintKey( (UInt8 *) myLeftKeyPtr, myLeftKeyLen );
1724
PrintKey( (UInt8 *) myRightKeyPtr, myRightKeyLen );
1725
}
1726
1727
if ( CompareKeys( theTreePtr, myLeftKeyPtr, myRightKeyPtr ) >= 0 )
1728
return( -1 );
1729
1730
return( noErr );
1731
1732
} /* DoKeyCheckAcrossNodes */
1733
1734
1735
static int DoKeyCheck( NodeDescPtr nodeP, BTreeControlBlock *btcb )
1736
{
1737
SInt16 index;
1738
UInt16 dataSize;
1739
UInt16 keyLength;
1740
KeyPtr keyPtr;
1741
UInt8 *dataPtr;
1742
KeyPtr prevkeyP = nil;
1743
1744
1745
if ( nodeP->numRecords == 0 )
1746
{
1747
if ( (nodeP->fLink == 0) && (nodeP->bLink == 0) )
1748
return( -1 );
1749
}
1750
else
1751
{
1752
/*
1753
* Loop on number of records in node
1754
*/
1755
for ( index = 0; index < nodeP->numRecords; index++)
1756
{
1757
GetRecordByIndex( (BTreeControlBlock *)btcb, nodeP, (UInt16) index, &keyPtr, &dataPtr, &dataSize );
1758
1759
if (btcb->attributes & kBTBigKeysMask)
1760
keyLength = keyPtr->length16;
1761
else
1762
keyLength = keyPtr->length8;
1763
1764
if ( keyLength > btcb->maxKeyLength )
1765
{
1766
return( -1 );
1767
}
1768
1769
if ( prevkeyP != nil )
1770
{
1771
if ( CompareKeys( (BTreeControlBlockPtr)btcb, prevkeyP, keyPtr ) >= 0 )
1772
{
1773
return( -1 );
1774
}
1775
}
1776
prevkeyP = keyPtr;
1777
}
1778
}
1779
1780
return( noErr );
1781
1782
} /* DoKeyCheck */
1783
1784
static void PrintNodeDescriptor( NodeDescPtr thePtr )
1785
{
1786
printf( " fLink %d bLink %d kind %d height %d numRecords %d \n",
1787
thePtr->fLink, thePtr->bLink, thePtr->kind, thePtr->height, thePtr->numRecords );
1788
}
1789
1790
1791
static void PrintKey( UInt8 * myPtr, int mySize )
1792
{
1793
int i;
1794
1795
for ( i = 0; i < mySize+2; i++ )
1796
{
1797
printf("%02X", *(myPtr + i) );
1798
}
1799
printf("\n" );
1800
} /* PrintKey */
1801
1802
1803
#endif // DEBUG_TREEOPS
Loggerhead is a web-based interface for Breezy
Version: 2.0.1