1 /*
2 * linux/fs/hfs/brec.c
3 *
4 * Copyright (C) 1995-1997 Paul H. Hargrove
5 * This file may be distributed under the terms of the GNU Public License.
6 *
7 * This file contains the code to access records in a btree.
8 *
9 * "XXX" in a comment is a note to myself to consider changing something.
10 *
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.
14 */
15
16 #include "hfs_btree.h"
17
18 /*================ File-local functions ================*/
19
20 /*
21 * first()
22 *
23 * returns HFS_BPATH_FIRST if elem->record == 1, 0 otherwise
24 */
25 static inline int first(const struct hfs_belem *elem)
26 {
27 return (elem->record == 1) ? HFS_BPATH_FIRST : 0;
28 }
29
30 /*
31 * overflow()
32 *
33 * return HFS_BPATH_OVERFLOW if the node has no room for an
34 * additional pointer record, 0 otherwise.
35 */
36 static inline int overflow(const struct hfs_btree *tree,
37 const struct hfs_bnode *bnode)
38 {
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;
43 }
44
45 /*
46 * underflow()
47 *
48 * return HFS_BPATH_UNDERFLOW if the node will be less that 1/2 full
49 * upon removal of a pointer record, 0 otherwise.
50 */
51 static inline int underflow(const struct hfs_btree *tree,
52 const struct hfs_bnode *bnode)
53 {
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;
58 }
59
60 /*================ Global functions ================*/
61
62 /*
63 * hfs_brec_next()
64 *
65 * Description:
66 * Obtain access to a child of an internal node in a B-tree.
67 * Input Variable(s):
68 * struct hfs_brec *brec: pointer to the (struct hfs_brec) to
69 * add an element to.
70 * Output Variable(s):
71 * NONE
72 * Returns:
73 * struct hfs_belem *: pointer to the new path element or NULL
74 * Preconditions:
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.
78 * Postconditions:
79 * If the call to hfs_bnode_find() fails then 'brec' is released
80 * and a NULL is returned.
81 * Otherwise:
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
85 * child.
86 * The child is obtained with the same 'lock_type' field as its
87 * parent.
88 * The 'record' field is initialized to the last record.
89 * A pointer to the new path element is returned.
90 */
91 struct hfs_belem *hfs_brec_next(struct hfs_brec *brec)
92 {
93 struct hfs_belem *elem = brec->bottom;
94 hfs_u32 node;
95 int lock_type;
96
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);
106 }
107
108 node = hfs_get_hl(belem_record(elem));
109 lock_type = elem->bnr.lock_type;
110
111 if (!node || hfs_bnode_in_brec(node, brec)) {
112 hfs_warn("hfs_bfind: corrupt btree\n");
113 hfs_brec_relse(brec, NULL);
114 return NULL;
115 }
116
117 ++elem;
118 ++brec->bottom;
119
120 elem->bnr = hfs_bnode_find(brec->tree, node, lock_type);
121 if (!elem->bnr.bn) {
122 hfs_brec_relse(brec, NULL);
123 return NULL;
124 }
125 elem->record = elem->bnr.bn->ndNRecs;
126
127 return elem;
128 }
129
130 /*
131 * hfs_brec_lock()
132 *
133 * Description:
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.
138 * Input Variable(s):
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):
143 * NONE
144 * Returns:
145 * void
146 * Preconditions:
147 * 'brec' points to a "valid" (struct hfs_brec)
148 * Postconditions:
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.
154 */
155 void hfs_brec_lock(struct hfs_brec *brec, struct hfs_belem *elem)
156 {
157 if (!elem) {
158 elem = brec->top;
159 } else if (elem > brec->top) {
160 hfs_brec_relse(brec, elem-1);
161 }
162
163 while (elem <= brec->bottom) {
164 hfs_bnode_lock(&elem->bnr, HFS_LOCK_WRITE);
165 ++elem;
166 }
167 }
168
169 /*
170 * hfs_brec_init()
171 *
172 * Description:
173 * Obtain access to the root node of a B-tree.
174 * Note that this first must obtain access to the header node.
175 * Input Variable(s):
176 * struct hfs_brec *brec: pointer to the (struct hfs_brec) to
177 * initialize
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):
181 * NONE
182 * Returns:
183 * struct hfs_belem *: pointer to the root path element or NULL
184 * Preconditions:
185 * 'brec' points to a (struct hfs_brec).
186 * 'tree' points to a valid (struct hfs_btree).
187 * Postconditions:
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
190 * of 'brec->tree'.
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.
199 */
200 struct hfs_belem *hfs_brec_init(struct hfs_brec *brec, struct hfs_btree *tree,
201 int flags)
202 {
203 struct hfs_belem *head = &brec->elem[0];
204 struct hfs_belem *root = &brec->elem[1];
205 int lock_type = flags & HFS_LOCK_MASK;
206
207 brec->tree = tree;
208
209 head->bnr = hfs_bnode_find(tree, 0, lock_type);
210 if (!head->bnr.bn) {
211 return NULL;
212 }
213
214 root->bnr = hfs_bnode_find(tree, tree->bthRoot, lock_type);
215 if (!root->bnr.bn) {
216 hfs_bnode_relse(&head->bnr);
217 return NULL;
218 }
219
220 root->record = root->bnr.bn->ndNRecs;
221
222 brec->top = head;
223 brec->bottom = root;
224
225 brec->keep_flags = flags & HFS_BPATH_MASK;
226
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;
232 }
233
234 if (!(root->flags & brec->keep_flags)) {
235 hfs_brec_relse(brec, head);
236 }
237
238 return root;
239 }
240
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.