4 * Copyright (C) 1995-1997 Paul H. Hargrove
5 * This file may be distributed under the terms of the GNU General Public License.
7 * This file contains the code to access records in a btree.
9 * "XXX" in a comment is a note to myself to consider changing something.
11 * In function preconditions the term "valid" applied to a pointer to
12 * a structure means that the pointer is non-NULL and the structure it
13 * points to has all fields initialized to consistent values.
16 #include "hfs_btree.h"
18 /*================ File-local functions ================*/
23 * returns HFS_BPATH_FIRST if elem->record == 1, 0 otherwise
25 static inline int first(const struct hfs_belem
*elem
)
27 return (elem
->record
== 1) ? HFS_BPATH_FIRST
: 0;
33 * return HFS_BPATH_OVERFLOW if the node has no room for an
34 * additional pointer record, 0 otherwise.
36 static inline int overflow(const struct hfs_btree
*tree
,
37 const struct hfs_bnode
*bnode
)
39 /* there is some algebra involved in getting this form */
40 return ((HFS_SECTOR_SIZE
- sizeof(hfs_u32
)) <
41 (bnode_end(bnode
) + (2+bnode
->ndNRecs
)*sizeof(hfs_u16
) +
42 ROUND(tree
->bthKeyLen
+1))) ? HFS_BPATH_OVERFLOW
: 0;
48 * return HFS_BPATH_UNDERFLOW if the node will be less that 1/2 full
49 * upon removal of a pointer record, 0 otherwise.
51 static inline int underflow(const struct hfs_btree
*tree
,
52 const struct hfs_bnode
*bnode
)
54 return ((bnode
->ndNRecs
* sizeof(hfs_u16
) +
55 bnode_offset(bnode
, bnode
->ndNRecs
)) <
56 (HFS_SECTOR_SIZE
- sizeof(struct NodeDescriptor
))/2) ?
57 HFS_BPATH_UNDERFLOW
: 0;
60 /*================ Global functions ================*/
66 * Obtain access to a child of an internal node in a B-tree.
68 * struct hfs_brec *brec: pointer to the (struct hfs_brec) to
73 * struct hfs_belem *: pointer to the new path element or NULL
75 * 'brec' points to a "valid" (struct hfs_brec), the last element of
76 * which corresponds to a record in a bnode of type ndIndxNode and the
77 * 'record' field indicates the index record for the desired child.
79 * If the call to hfs_bnode_find() fails then 'brec' is released
80 * and a NULL is returned.
82 * Any ancestors in 'brec' that are not needed (as determined by the
83 * 'keep_flags' field of 'brec) are released from 'brec'.
84 * A new element is added to 'brec' corresponding to the desired
86 * The child is obtained with the same 'lock_type' field as its
88 * The 'record' field is initialized to the last record.
89 * A pointer to the new path element is returned.
91 struct hfs_belem
*hfs_brec_next(struct hfs_brec
*brec
)
93 struct hfs_belem
*elem
= brec
->bottom
;
97 /* release unneeded ancestors */
98 elem
->flags
= first(elem
) |
99 overflow(brec
->tree
, elem
->bnr
.bn
) |
100 underflow(brec
->tree
, elem
->bnr
.bn
);
101 if (!(brec
->keep_flags
& elem
->flags
)) {
102 hfs_brec_relse(brec
, brec
->bottom
-1);
103 } else if ((brec
->bottom
-2 >= brec
->top
) &&
104 !(elem
->flags
& (elem
-1)->flags
)) {
105 hfs_brec_relse(brec
, brec
->bottom
-2);
108 node
= hfs_get_hl(belem_record(elem
));
109 lock_type
= elem
->bnr
.lock_type
;
111 if (!node
|| hfs_bnode_in_brec(node
, brec
)) {
112 hfs_warn("hfs_bfind: corrupt btree\n");
113 hfs_brec_relse(brec
, NULL
);
120 elem
->bnr
= hfs_bnode_find(brec
->tree
, node
, lock_type
);
122 hfs_brec_relse(brec
, NULL
);
125 elem
->record
= elem
->bnr
.bn
->ndNRecs
;
134 * This function obtains HFS_LOCK_WRITE access to the bnode
135 * containing this hfs_brec. All descendents in the path from this
136 * record to the leaf are given HFS_LOCK_WRITE access and all
137 * ancestors in the path from the root to here are released.
139 * struct hfs_brec *brec: pointer to the brec to obtain
140 * HFS_LOCK_WRITE access to some of the nodes of.
141 * struct hfs_belem *elem: the first node to lock or NULL for all
142 * Output Variable(s):
147 * 'brec' points to a "valid" (struct hfs_brec)
149 * All nodes between the indicated node and the beginning of the path
150 * are released. hfs_bnode_lock() is called in turn on each node
151 * from the indicated node to the leaf node of the path, with a
152 * lock_type argument of HFS_LOCK_WRITE. If one of those calls
153 * results in deadlock, then this function will never return.
155 void hfs_brec_lock(struct hfs_brec
*brec
, struct hfs_belem
*elem
)
159 } else if (elem
> brec
->top
) {
160 hfs_brec_relse(brec
, elem
-1);
163 while (elem
<= brec
->bottom
) {
164 hfs_bnode_lock(&elem
->bnr
, HFS_LOCK_WRITE
);
173 * Obtain access to the root node of a B-tree.
174 * Note that this first must obtain access to the header node.
176 * struct hfs_brec *brec: pointer to the (struct hfs_brec) to
178 * struct hfs_btree *btree: pointer to the (struct hfs_btree)
179 * int lock_type: the type of access to get to the nodes.
180 * Output Variable(s):
183 * struct hfs_belem *: pointer to the root path element or NULL
185 * 'brec' points to a (struct hfs_brec).
186 * 'tree' points to a valid (struct hfs_btree).
188 * If the two calls to brec_bnode_find() succeed then the return value
189 * points to a (struct hfs_belem) which corresponds to the root node
191 * Both the root and header nodes are obtained with the type of lock
192 * given by (flags & HFS_LOCK_MASK).
193 * The fields 'record' field of the root is set to its last record.
194 * If the header node is not needed to complete the appropriate
195 * operation (as determined by the 'keep_flags' field of 'brec') then
196 * it is released before this function returns.
197 * If either call to brec_bnode_find() fails, NULL is returned and the
198 * (struct hfs_brec) pointed to by 'brec' is invalid.
200 struct hfs_belem
*hfs_brec_init(struct hfs_brec
*brec
, struct hfs_btree
*tree
,
203 struct hfs_belem
*head
= &brec
->elem
[0];
204 struct hfs_belem
*root
= &brec
->elem
[1];
205 int lock_type
= flags
& HFS_LOCK_MASK
;
209 head
->bnr
= hfs_bnode_find(tree
, 0, lock_type
);
214 root
->bnr
= hfs_bnode_find(tree
, tree
->bthRoot
, lock_type
);
216 hfs_bnode_relse(&head
->bnr
);
220 root
->record
= root
->bnr
.bn
->ndNRecs
;
225 brec
->keep_flags
= flags
& HFS_BPATH_MASK
;
227 /* HFS_BPATH_FIRST not applicable for root */
228 /* and HFS_BPATH_UNDERFLOW is different */
229 root
->flags
= overflow(tree
, root
->bnr
.bn
);
230 if (root
->record
< 3) {
231 root
->flags
|= HFS_BPATH_UNDERFLOW
;
234 if (!(root
->flags
& brec
->keep_flags
)) {
235 hfs_brec_relse(brec
, head
);