]> git.saurik.com Git - apple/hfs.git/blame_incremental - livefiles_hfs_plugin/lf_hfs_btree.h
projects / apple / hfs.git / blame_incremental
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (non-incremental) | history | HEAD
hfs-556.100.11.tar.gz
[apple/hfs.git] / livefiles_hfs_plugin / lf_hfs_btree.h
... / ...
CommitLineData
1//
2// lf_hfs_btree.h
3// livefiles_hfs
4//
5// Created by Yakov Ben Zaken on 20/03/2018.
6//
7
8#ifndef lf_hfs_btree_h
9#define lf_hfs_btree_h
10
11
12#include "lf_hfs_file_mgr_internal.h"
13#include "lf_hfs_btrees_internal.h"
14
15
16/////////////////////////////////// Constants ///////////////////////////////////
17
18#define kBTreeVersion 1
19#define kMaxTreeDepth 16
20
21
22#define kHeaderNodeNum 0
23#define kKeyDescRecord 1
24
25
26// Header Node Record Offsets
27enum {
28 kHeaderRecOffset = 0x000E,
29 kKeyDescRecOffset = 0x0078,
30 kHeaderMapRecOffset = 0x00F8
31};
32
33#define kMinNodeSize 512
34
35#define kMinRecordSize 6
36// where is minimum record size enforced?
37
38// miscellaneous BTree constants
39enum {
40 kOffsetSize = 2
41};
42
43// Insert Operations
44typedef enum {
45 kInsertRecord = 0,
46 kReplaceRecord = 1
47} InsertType;
48
49// illegal string attribute bits set in mask
50#define kBadStrAttribMask 0xCF
51
52
53
54//////////////////////////////////// Macros /////////////////////////////////////
55
56#define M_NodesInMap(mapSize) ((mapSize) << 3)
57
58#define M_ClearBitNum(integer,bitNumber) ((integer) &= (~(1<<(bitNumber))))
59#define M_SetBitNum(integer,bitNumber) ((integer) |= (1<<(bitNumber)))
60#define M_IsOdd(integer) (((integer) & 1) != 0)
61#define M_IsEven(integer) (((integer) & 1) == 0)
62
63#define M_MapRecordSize(nodeSize) (nodeSize - sizeof (BTNodeDescriptor) - 6)
64#define M_HeaderMapRecordSize(nodeSize) (nodeSize - sizeof(BTNodeDescriptor) - sizeof(BTHeaderRec) - 128 - 8)
65
66#define M_SWAP_BE16_ClearBitNum(integer,bitNumber) ((integer) &= SWAP_BE16(~(1<<(bitNumber))))
67#define M_SWAP_BE16_SetBitNum(integer,bitNumber) ((integer) |= SWAP_BE16(1<<(bitNumber)))
68
69///////////////////////////////////// Types /////////////////////////////////////
70
71typedef struct BTreeControlBlock { // fields specific to BTree CBs
72
73 u_int8_t keyCompareType; /* Key string Comparison Type */
74 u_int8_t btreeType;
75 u_int16_t treeDepth;
76 FileReference fileRefNum; // refNum of btree file
77 KeyCompareProcPtr keyCompareProc;
78 u_int32_t rootNode;
79 u_int32_t leafRecords;
80 u_int32_t firstLeafNode;
81 u_int32_t lastLeafNode;
82 u_int16_t nodeSize;
83 u_int16_t maxKeyLength;
84 u_int32_t totalNodes;
85 u_int32_t freeNodes;
86
87 u_int16_t reserved3; // 4-byte alignment
88
89 // new fields
90 int16_t version;
91 u_int32_t flags; // dynamic flags
92 u_int32_t attributes; // persistent flags
93 u_int32_t writeCount;
94 u_int32_t lastfsync; /* Last time that this was fsynced */
95
96 GetBlockProcPtr getBlockProc;
97 ReleaseBlockProcPtr releaseBlockProc;
98 SetEndOfForkProcPtr setEndOfForkProc;
99
100 // statistical information
101 u_int32_t numGetNodes;
102 u_int32_t numGetNewNodes;
103 u_int32_t numReleaseNodes;
104 u_int32_t numUpdateNodes;
105 u_int32_t numMapNodesRead; // map nodes beyond header node
106 u_int32_t numHintChecks;
107 u_int32_t numPossibleHints; // Looks like a formated hint
108 u_int32_t numValidHints; // Hint used to find correct record.
109 u_int32_t reservedNodes;
110 BTreeIterator iterator; // useable when holding exclusive b-tree lock
111
112#if DEBUG
113 void *madeDirtyBy[2];
114#endif
115} BTreeControlBlock, *BTreeControlBlockPtr;
116
117u_int32_t CalcKeySize(const BTreeControlBlock *btcb, const BTreeKey *key);
118#define CalcKeySize(btcb, key) ( ((btcb)->attributes & kBTBigKeysMask) ? ((key)->length16 + 2) : ((key)->length8 + 1) )
119
120u_int32_t KeyLength(const BTreeControlBlock *btcb, const BTreeKey *key);
121#define KeyLength(btcb, key) ( ((btcb)->attributes & kBTBigKeysMask) ? (key)->length16 : (key)->length8 )
122
123
124
125typedef enum {
126 kBTHeaderDirty = 0x00000001
127} BTreeFlags;
128
129static inline void M_BTreeHeaderDirty(BTreeControlBlock *bt) {
130#if DEBUG
131 bt->madeDirtyBy[0] = __builtin_return_address(0);
132 bt->madeDirtyBy[1] = __builtin_return_address(1);
133#endif
134 bt->flags |= kBTHeaderDirty;
135}
136
137typedef int8_t *NodeBuffer;
138typedef BlockDescriptor NodeRec, *NodePtr; //remove this someday...
139
140
141
142
143//// Tree Path Table - constructed by SearchTree, used by InsertTree and DeleteTree
144
145typedef struct {
146 u_int32_t node; // node number
147 u_int16_t index;
148 u_int16_t reserved; // align size to a power of 2
149} TreePathRecord, *TreePathRecordPtr;
150
151typedef TreePathRecord TreePathTable [kMaxTreeDepth];
152
153
154//// InsertKey - used by InsertTree, InsertLevel and InsertNode
155
156struct InsertKey {
157 BTreeKeyPtr keyPtr;
158 u_int8_t * recPtr;
159 u_int16_t keyLength;
160 u_int16_t recSize;
161 Boolean replacingKey;
162 Boolean skipRotate;
163};
164
165typedef struct InsertKey InsertKey;
166
167
168//// For Notational Convenience
169
170typedef BTNodeDescriptor* NodeDescPtr;
171typedef u_int8_t *RecordPtr;
172typedef BTreeKeyPtr KeyPtr;
173
174
175//////////////////////////////////// Globals ////////////////////////////////////
176
177
178//////////////////////////////////// Macros /////////////////////////////////////
179// Exit function on error
180#define M_ExitOnError( result ) do { if ( ( result ) != noErr ) goto ErrorExit; } while(0)
181
182// Test for passed condition and return if true
183#define M_ReturnErrorIf( condition, error ) do { if ( condition ) return( error ); } while(0)
184
185//////////////////////////////// Key Operations /////////////////////////////////
186
187int32_t CompareKeys (BTreeControlBlockPtr btreePtr,
188 KeyPtr searchKey,
189 KeyPtr trialKey );
190
191//////////////////////////////// Map Operations /////////////////////////////////
192
193OSStatus AllocateNode (BTreeControlBlockPtr btreePtr,
194 u_int32_t *nodeNum);
195
196OSStatus FreeNode (BTreeControlBlockPtr btreePtr,
197 u_int32_t nodeNum);
198
199OSStatus ExtendBTree (BTreeControlBlockPtr btreePtr,
200 u_int32_t nodes );
201
202u_int32_t CalcMapBits (BTreeControlBlockPtr btreePtr);
203
204
205void BTUpdateReserve (BTreeControlBlockPtr btreePtr,
206 int nodes);
207
208//////////////////////////////// Misc Operations ////////////////////////////////
209
210u_int16_t CalcKeyRecordSize (u_int16_t keySize,
211 u_int16_t recSize );
212
213OSStatus VerifyHeader (FCB *filePtr,
214 BTHeaderRec *header );
215
216OSStatus UpdateHeader (BTreeControlBlockPtr btreePtr,
217 Boolean forceWrite );
218
219OSStatus FindIteratorPosition (BTreeControlBlockPtr btreePtr,
220 BTreeIteratorPtr iterator,
221 BlockDescriptor *left,
222 BlockDescriptor *middle,
223 BlockDescriptor *right,
224 u_int32_t *nodeNum,
225 u_int16_t *index,
226 Boolean *foundRecord );
227
228OSStatus CheckInsertParams (FCB *filePtr,
229 BTreeIterator *iterator,
230 FSBufferDescriptor *record,
231 u_int16_t recordLen );
232
233OSStatus TrySimpleReplace (BTreeControlBlockPtr btreePtr,
234 NodeDescPtr nodePtr,
235 BTreeIterator *iterator,
236 FSBufferDescriptor *record,
237 u_int16_t recordLen,
238 Boolean *recordInserted );
239
240OSStatus IsItAHint (BTreeControlBlockPtr btreePtr,
241 BTreeIterator *iterator,
242 Boolean *answer );
243
244extern OSStatus TreeIsDirty(BTreeControlBlockPtr btreePtr);
245
246//////////////////////////////// Node Operations ////////////////////////////////
247
248//// Node Operations
249
250OSStatus GetNode (BTreeControlBlockPtr btreePtr,
251 u_int32_t nodeNum,
252 u_int32_t flags,
253 NodeRec *returnNodePtr );
254
255/* Flags for GetNode() */
256#define kGetNodeHint 0x1 /* If set, the node is being looked up using a hint */
257
258OSStatus GetLeftSiblingNode (BTreeControlBlockPtr btreePtr,
259 NodeDescPtr node,
260 NodeRec *left );
261
262#define GetLeftSiblingNode(btree,node,left) GetNode ((btree), ((NodeDescPtr)(node))->bLink, 0, (left))
263
264OSStatus GetRightSiblingNode (BTreeControlBlockPtr btreePtr,
265 NodeDescPtr node,
266 NodeRec *right );
267
268#define GetRightSiblingNode(btree,node,right) GetNode ((btree), ((NodeDescPtr)(node))->fLink, 0, (right))
269
270
271OSStatus GetNewNode (BTreeControlBlockPtr btreePtr,
272 u_int32_t nodeNum,
273 NodeRec *returnNodePtr );
274
275OSStatus ReleaseNode (BTreeControlBlockPtr btreePtr,
276 NodePtr nodePtr );
277
278OSStatus TrashNode (BTreeControlBlockPtr btreePtr,
279 NodePtr nodePtr );
280
281OSStatus UpdateNode (BTreeControlBlockPtr btreePtr,
282 NodePtr nodePtr,
283 u_int32_t transactionID,
284 u_int32_t flags );
285
286//// Node Buffer Operations
287
288void ClearNode (BTreeControlBlockPtr btreePtr,
289 NodeDescPtr node );
290
291u_int16_t GetNodeDataSize (BTreeControlBlockPtr btreePtr,
292 NodeDescPtr node );
293
294u_int16_t GetNodeFreeSize (BTreeControlBlockPtr btreePtr,
295 NodeDescPtr node );
296
297
298//// Record Operations
299
300Boolean InsertRecord (BTreeControlBlockPtr btreePtr,
301 NodeDescPtr node,
302 u_int16_t index,
303 RecordPtr recPtr,
304 u_int16_t recSize );
305
306Boolean InsertKeyRecord (BTreeControlBlockPtr btreePtr,
307 NodeDescPtr node,
308 u_int16_t index,
309 KeyPtr keyPtr,
310 u_int16_t keyLength,
311 RecordPtr recPtr,
312 u_int16_t recSize );
313
314void DeleteRecord (BTreeControlBlockPtr btree,
315 NodeDescPtr node,
316 u_int16_t index );
317
318
319Boolean SearchNode (BTreeControlBlockPtr btree,
320 NodeDescPtr node,
321 KeyPtr searchKey,
322 u_int16_t *index );
323
324OSStatus GetRecordByIndex (BTreeControlBlockPtr btree,
325 NodeDescPtr node,
326 u_int16_t index,
327 KeyPtr *keyPtr,
328 u_int8_t * *dataPtr,
329 u_int16_t *dataSize );
330
331u_int8_t * GetRecordAddress (BTreeControlBlockPtr btree,
332 NodeDescPtr node,
333 u_int16_t index );
334
335#define GetRecordAddress(btreePtr,node,index) ((u_int8_t *)(node) + (*(short *) ((u_int8_t *)(node) + (btreePtr)->nodeSize - ((index) << 1) - kOffsetSize)))
336
337
338u_int16_t GetRecordSize (BTreeControlBlockPtr btree,
339 NodeDescPtr node,
340 u_int16_t index );
341
342u_int32_t GetChildNodeNum (BTreeControlBlockPtr btreePtr,
343 NodeDescPtr nodePtr,
344 u_int16_t index );
345
346void MoveRecordsLeft (u_int8_t * src,
347 u_int8_t * dst,
348 u_int16_t bytesToMove );
349
350#define MoveRecordsLeft(src,dst,bytes) bcopy((src),(dst),(bytes))
351
352void MoveRecordsRight (u_int8_t * src,
353 u_int8_t * dst,
354 u_int16_t bytesToMove );
355
356#define MoveRecordsRight(src,dst,bytes) bcopy((src),(dst),(bytes))
357
358
359//////////////////////////////// Tree Operations ////////////////////////////////
360
361OSStatus SearchTree (BTreeControlBlockPtr btreePtr,
362 BTreeKeyPtr keyPtr,
363 TreePathTable treePathTable,
364 u_int32_t *nodeNum,
365 BlockDescriptor *nodePtr,
366 u_int16_t *index );
367
368OSStatus InsertTree (BTreeControlBlockPtr btreePtr,
369 TreePathTable treePathTable,
370 KeyPtr keyPtr,
371 u_int8_t * recPtr,
372 u_int16_t recSize,
373 BlockDescriptor *targetNode,
374 u_int16_t index,
375 u_int16_t level,
376 Boolean replacingKey,
377 u_int32_t *insertNode );
378
379OSStatus DeleteTree (BTreeControlBlockPtr btreePtr,
380 TreePathTable treePathTable,
381 BlockDescriptor *targetNode,
382 u_int16_t index,
383 u_int16_t level );
384
385OSStatus BTFlushPath (FCB *filePtr);
386
387OSStatus BTSetLastSync (FCB *filePtr,
388 u_int32_t lastsync);
389#endif /* lf_hfs_btree_h */
mirror of hfs