1 /*
2 * linux/fs/hfs/hfs_btree.h
3 *
4 * Copyright (C) 1995-1997 Paul H. Hargrove
5 * This file may be distributed under the terms of the GNU General Public License.
6 *
7 * This file contains the declarations of the private B-tree
8 * structures and functions.
9 *
10 * "XXX" in a comment is a note to myself to consider changing something.
11 */
12
13 #ifndef _HFS_BTREE_H
14 #define _HFS_BTREE_H
15
16 #include "hfs.h"
17
18 /*================ Variable-like macros ================*/
19
20 /* The stickiness of a (struct hfs_bnode) */
21 #define HFS_NOT_STICKY 0
22 #define HFS_STICKY 1
23
24 /* The number of hash buckets in a B-tree's bnode cache */
25 #define HFS_CACHELEN 17 /* primes are best? */
26
27 /*
28 * Legal values for the 'ndType' field of a (struct NodeDescriptor)
29 *
30 * Reference: _Inside Macintosh: Files_ p. 2-65
31 */
32 #define ndIndxNode 0x00 /* An internal (index) node */
33 #define ndHdrNode 0x01 /* The tree header node (node 0) */
34 #define ndMapNode 0x02 /* Holds part of the bitmap of used nodes */
35 #define ndLeafNode 0xFF /* A leaf (ndNHeight==1) node */
36
37 /*
38 * Legal values for the bthAtrb field of a (struct BTHdrRec)
39 *
40 * Reference: TN 1150
41 */
42 #define bthBadClose 0x00000001 /* b-tree not closed properly. not
43 used by hfsplus. */
44 #define bthBigKeys 0x00000002 /* key length is u16 instead of u8.
45 used by hfsplus. */
46 #define bthVarIndxKeys 0x00000004 /* variable key length instead of
47 max key length. use din catalog
48 b-tree but not in extents
49 b-tree (hfsplus). */
50
51 /*================ Function-like macros ================*/
52
53 /* Access the cache slot which should contain the desired node */
54 #define bhash(tree, node) ((tree)->cache[(node) % HFS_CACHELEN])
55
56 /* round up to multiple of sizeof(hfs_u16) */
57 #define ROUND(X) ((X + sizeof(hfs_u16) - 1) & ~(sizeof(hfs_u16)-1))
58
59 /* Refer to the (base-1) array of offsets in a bnode */
60 #define RECTBL(X,N) \
61 (((hfs_u16 *)(hfs_buffer_data((X)->buf)+HFS_SECTOR_SIZE))-(N))
62
63 /*================ Private data types ================*/
64
65 /*
66 * struct BTHdrRec
67 *
68 * The B-tree header record
69 *
70 * This data structure is stored in the first node (512-byte block) of
71 * each B-tree file. It contains important information about the
72 * B-tree. Most fields vary over the life of the tree and are
73 * indicated by a 'V' in the comments. The other fields are fixed for
74 * the life of the tree and are indicated by a 'F'.
75 *
76 * Reference: _Inside Macintosh: Files_ pp. 2-68 through 2-69 */
77 struct BTHdrRec {
78 hfs_word_t bthDepth; /* (V) The number of levels in this B-tree */
79 hfs_lword_t bthRoot; /* (V) The node number of the root node */
80 hfs_lword_t bthNRecs; /* (V) The number of leaf records */
81 hfs_lword_t bthFNode; /* (V) The number of the first leaf node */
82 hfs_lword_t bthLNode; /* (V) The number of the last leaf node */
83 hfs_word_t bthNodeSize; /* (F) The number of bytes in a node (=512) */
84 hfs_word_t bthKeyLen; /* (F) The length of a key in an index node */
85 hfs_lword_t bthNNodes; /* (V) The total number of nodes */
86 hfs_lword_t bthFree; /* (V) The number of unused nodes */
87 hfs_word_t bthResv1; /* reserved */
88 hfs_lword_t bthClpSiz; /* (F) clump size. not usually used. */
89 hfs_byte_t bthType; /* (F) BTree type */
90 hfs_byte_t bthResv2; /* reserved */
91 hfs_lword_t bthAtrb; /* (F) attributes */
92 hfs_lword_t bthResv3[16]; /* Reserved */
93 } __attribute__((packed));
94
95 /*
96 * struct NodeDescriptor
97 *
98 * The B-tree node descriptor.
99 *
100 * This structure begins each node in the B-tree file. It contains
101 * important information about the node's contents. 'V' and 'F' in
102 * the comments indicate fields that are variable or fixed over the
103 * life of a node, where the 'life' of a node is defined as the period
104 * between leaving and reentering the free pool.
105 *
106 * Reference: _Inside Macintosh: Files_ p. 2-64
107 */
108 struct NodeDescriptor {
109 hfs_lword_t ndFLink; /* (V) Number of the next node at this level */
110 hfs_lword_t ndBLink; /* (V) Number of the prev node at this level */
111 hfs_byte_t ndType; /* (F) The type of node */
112 hfs_byte_t ndNHeight; /* (F) The level of this node (leaves=1) */
113 hfs_word_t ndNRecs; /* (V) The number of records in this node */
114 hfs_word_t ndResv2; /* Reserved */
115 } __attribute__((packed));
116
117 /*
118 * typedef hfs_cmpfn
119 *
120 * The type 'hfs_cmpfn' is a comparison function taking 2 keys and
121 * returning a positive, negative or zero integer according to the
122 * ordering of the two keys (just like strcmp() does for strings).
123 */
124 typedef int (*hfs_cmpfn)(const void *, const void *);
125
126 /*
127 * struct hfs_bnode
128 *
129 * An in-core B-tree node
130 *
131 * This structure holds information from the NodeDescriptor in native
132 * byte-order, a pointer to the buffer which contains the actual
133 * node and fields necessary for locking access to the node during
134 * updates. The use of the locking fields is explained with the
135 * locking functions.
136 */
137 struct hfs_bnode {
138 int magic; /* Magic number to guard against
139 wild pointers */
140 hfs_buffer buf; /* The buffer containing the
141 actual node */
142 struct hfs_btree *tree; /* The tree to which this node
143 belongs */
144 struct hfs_bnode *prev; /* Next node in this hash bucket */
145 struct hfs_bnode *next; /* Previous node in this hash
146 bucket */
147 int sticky; /* Boolean: non-zero means keep
148 this node in-core (set for
149 root and head) */
150 hfs_u32 node; /* Node number */
151 hfs_u16 nodeSize; /* node size */
152 hfs_u16 keyLen; /* key length */
153 /* locking related fields: */
154 hfs_wait_queue wqueue; /* Wait queue for write access */
155 hfs_wait_queue rqueue; /* Wait queue for read or reserve
156 access */
157 int count; /* Number of processes accessing
158 this node */
159 int resrv; /* Boolean, true means a process
160 had placed a 'reservation' on
161 this node */
162 int lock; /* Boolean, true means some
163 process has exclusive access,
164 so KEEP OUT */
165 /* fields from the NodeDescriptor in native byte-order: */
166 hfs_u32 ndFLink;
167 hfs_u32 ndBLink;
168 hfs_u16 ndNRecs;
169 hfs_u8 ndType;
170 hfs_u8 ndNHeight;
171 };
172
173 /*
174 * struct hfs_btree
175 *
176 * An in-core B-tree.
177 *
178 * This structure holds information from the BTHdrRec, MDB
179 * (superblock) and other information needed to work with the B-tree.
180 */
181 struct hfs_btree {
182 int magic; /* Magic number to
183 guard against wild
184 pointers */
185 hfs_cmpfn compare; /* Comparison function
186 for this tree */
187 struct hfs_bnode head; /* in-core copy of node 0 */
188 struct hfs_bnode *root; /* Pointer to the in-core
189 copy of the root node */
190 hfs_sysmdb sys_mdb; /* The "device" holding
191 the filesystem */
192 int reserved; /* bnodes claimed but
193 not yet used */
194 struct hfs_bnode /* The bnode cache */
195 *cache[HFS_CACHELEN];
196 struct hfs_cat_entry entry; /* Fake catalog entry */
197 int lock;
198 hfs_wait_queue wait;
199 int dirt;
200 int keySize;
201 /* Fields from the BTHdrRec in native byte-order: */
202 hfs_u32 bthRoot;
203 hfs_u32 bthNRecs;
204 hfs_u32 bthFNode;
205 hfs_u32 bthLNode;
206 hfs_u32 bthNNodes;
207 hfs_u32 bthFree;
208 hfs_u16 bthKeyLen;
209 hfs_u16 bthDepth;
210 };
211
212 /*================ Global functions ================*/
213
214 /* Convert a (struct hfs_bnode *) and an index to the value of the
215 n-th offset in the bnode (N >= 1) to the offset */
bnode_offset(const struct hfs_bnode * bnode,int n)216 extern inline hfs_u16 bnode_offset(const struct hfs_bnode *bnode, int n)
217 { return hfs_get_hs(RECTBL(bnode,n)); }
218
219 /* Convert a (struct hfs_bnode *) and an index to the size of the
220 n-th record in the bnode (N >= 1) */
bnode_rsize(const struct hfs_bnode * bnode,int n)221 extern inline hfs_u16 bnode_rsize(const struct hfs_bnode *bnode, int n)
222 { return bnode_offset(bnode, n+1) - bnode_offset(bnode, n); }
223
224 /* Convert a (struct hfs_bnode *) to the offset of the empty part */
bnode_end(const struct hfs_bnode * bnode)225 extern inline hfs_u16 bnode_end(const struct hfs_bnode *bnode)
226 { return bnode_offset(bnode, bnode->ndNRecs + 1); }
227
228 /* Convert a (struct hfs_bnode *) to the number of free bytes it contains */
bnode_freespace(const struct hfs_bnode * bnode)229 extern inline hfs_u16 bnode_freespace(const struct hfs_bnode *bnode)
230 { return HFS_SECTOR_SIZE - bnode_end(bnode)
231 - (bnode->ndNRecs + 1)*sizeof(hfs_u16); }
232
233 /* Convert a (struct hfs_bnode *) X and an index N to
234 the address of the record N in the bnode (N >= 1) */
bnode_datastart(const struct hfs_bnode * bnode)235 extern inline void *bnode_datastart(const struct hfs_bnode *bnode)
236 { return (void *)(hfs_buffer_data(bnode->buf)+sizeof(struct NodeDescriptor)); }
237
238 /* Convert a (struct hfs_bnode *) to the address of the empty part */
bnode_dataend(const struct hfs_bnode * bnode)239 extern inline void *bnode_dataend(const struct hfs_bnode *bnode)
240 { return (void *)(hfs_buffer_data(bnode->buf) + bnode_end(bnode)); }
241
242 /* Convert various pointers to address of record's key */
bnode_key(const struct hfs_bnode * bnode,int n)243 extern inline void *bnode_key(const struct hfs_bnode *bnode, int n)
244 { return (void *)(hfs_buffer_data(bnode->buf) + bnode_offset(bnode, n)); }
belem_key(const struct hfs_belem * elem)245 extern inline void *belem_key(const struct hfs_belem *elem)
246 { return bnode_key(elem->bnr.bn, elem->record); }
brec_key(const struct hfs_brec * brec)247 extern inline void *brec_key(const struct hfs_brec *brec)
248 { return belem_key(brec->bottom); }
249
250 /* Convert various pointers to the address of a record */
bkey_record(const struct hfs_bkey * key)251 extern inline void *bkey_record(const struct hfs_bkey *key)
252 { return (void *)key + ROUND(key->KeyLen + 1); }
bnode_record(const struct hfs_bnode * bnode,int n)253 extern inline void *bnode_record(const struct hfs_bnode *bnode, int n)
254 { return bkey_record(bnode_key(bnode, n)); }
belem_record(const struct hfs_belem * elem)255 extern inline void *belem_record(const struct hfs_belem *elem)
256 { return bkey_record(belem_key(elem)); }
brec_record(const struct hfs_brec * brec)257 extern inline void *brec_record(const struct hfs_brec *brec)
258 { return bkey_record(brec_key(brec)); }
259
260 /*================ Function Prototypes ================*/
261
262 /* balloc.c */
263 extern int hfs_bnode_bitop(struct hfs_btree *, hfs_u32, int);
264 extern struct hfs_bnode_ref hfs_bnode_alloc(struct hfs_btree *);
265 extern int hfs_bnode_free(struct hfs_bnode_ref *);
266 extern void hfs_btree_extend(struct hfs_btree *);
267
268 /* bins_del.c */
269 extern void hfs_bnode_update_key(struct hfs_brec *, struct hfs_belem *,
270 struct hfs_bnode *, int);
271 extern void hfs_bnode_shift_right(struct hfs_bnode *, struct hfs_bnode *, int);
272 extern void hfs_bnode_shift_left(struct hfs_bnode *, struct hfs_bnode *, int);
273 extern int hfs_bnode_in_brec(hfs_u32 node, const struct hfs_brec *brec);
274
275 /* bnode.c */
276 extern void hfs_bnode_read(struct hfs_bnode *, struct hfs_btree *,
277 hfs_u32, int);
278 extern void hfs_bnode_relse(struct hfs_bnode_ref *);
279 extern struct hfs_bnode_ref hfs_bnode_find(struct hfs_btree *, hfs_u32, int);
280 extern void hfs_bnode_lock(struct hfs_bnode_ref *, int);
281 extern void hfs_bnode_delete(struct hfs_bnode *);
282 extern void hfs_bnode_commit(struct hfs_bnode *);
283
284 /* brec.c */
285 extern void hfs_brec_lock(struct hfs_brec *, struct hfs_belem *);
286 extern struct hfs_belem *hfs_brec_init(struct hfs_brec *, struct hfs_btree *,
287 int);
288 extern struct hfs_belem *hfs_brec_next(struct hfs_brec *);
289
290 #endif
291