1 |
1275 |
phoenix |
/*
|
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 General 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 |
|
|
}
|