1 |
1275 |
phoenix |
/*
|
2 |
|
|
* linux/fs/hfs/bins_del.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 common to inserting and deleting records
|
8 |
|
|
* in a B-tree.
|
9 |
|
|
*
|
10 |
|
|
* "XXX" in a comment is a note to myself to consider changing something.
|
11 |
|
|
*
|
12 |
|
|
* In function preconditions the term "valid" applied to a pointer to
|
13 |
|
|
* a structure means that the pointer is non-NULL and the structure it
|
14 |
|
|
* points to has all fields initialized to consistent values.
|
15 |
|
|
*/
|
16 |
|
|
|
17 |
|
|
#include "hfs_btree.h"
|
18 |
|
|
|
19 |
|
|
/*================ File-local functions ================*/
|
20 |
|
|
|
21 |
|
|
/*
|
22 |
|
|
* hfs_bnode_update_key()
|
23 |
|
|
*
|
24 |
|
|
* Description:
|
25 |
|
|
* Updates the key for a bnode in its parent.
|
26 |
|
|
* The key change is propagated up the tree as necessary.
|
27 |
|
|
* Input Variable(s):
|
28 |
|
|
* struct hfs_brec *brec: the search path to update keys in
|
29 |
|
|
* struct hfs_belem *belem: the search path element with the changed key
|
30 |
|
|
* struct hfs_bnode *bnode: the bnode with the changed key
|
31 |
|
|
* int offset: the "distance" from 'belem->bn' to 'bnode':
|
32 |
|
|
* 0 if the change is in 'belem->bn',
|
33 |
|
|
* 1 if the change is in its right sibling, etc.
|
34 |
|
|
* Output Variable(s):
|
35 |
|
|
* NONE
|
36 |
|
|
* Returns:
|
37 |
|
|
* void
|
38 |
|
|
* Preconditions:
|
39 |
|
|
* 'brec' points to a valid (struct hfs_brec)
|
40 |
|
|
* 'belem' points to a valid (struct hfs_belem) in 'brec'.
|
41 |
|
|
* 'bnode' points to a valid (struct hfs_bnode) which is non-empty
|
42 |
|
|
* and is 'belem->bn' or one of its siblings.
|
43 |
|
|
* 'offset' is as described above.
|
44 |
|
|
* Postconditions:
|
45 |
|
|
* The key change is propagated up the tree as necessary.
|
46 |
|
|
*/
|
47 |
|
|
void hfs_bnode_update_key(struct hfs_brec *brec, struct hfs_belem *belem,
|
48 |
|
|
struct hfs_bnode *bnode, int offset)
|
49 |
|
|
{
|
50 |
|
|
int record = (--belem)->record + offset;
|
51 |
|
|
void *key = bnode_datastart(bnode) + 1;
|
52 |
|
|
int keysize = brec->tree->bthKeyLen;
|
53 |
|
|
struct hfs_belem *limit;
|
54 |
|
|
|
55 |
|
|
memcpy(1+bnode_key(belem->bnr.bn, record), key, keysize);
|
56 |
|
|
|
57 |
|
|
/* don't trash the header */
|
58 |
|
|
if (brec->top > &brec->elem[1]) {
|
59 |
|
|
limit = brec->top;
|
60 |
|
|
} else {
|
61 |
|
|
limit = &brec->elem[1];
|
62 |
|
|
}
|
63 |
|
|
|
64 |
|
|
while ((belem > limit) && (record == 1)) {
|
65 |
|
|
record = (--belem)->record;
|
66 |
|
|
memcpy(1+belem_key(belem), key, keysize);
|
67 |
|
|
}
|
68 |
|
|
}
|
69 |
|
|
|
70 |
|
|
/*
|
71 |
|
|
* hfs_bnode_shift_right()
|
72 |
|
|
*
|
73 |
|
|
* Description:
|
74 |
|
|
* Shifts some records from a node to its right neighbor.
|
75 |
|
|
* Input Variable(s):
|
76 |
|
|
* struct hfs_bnode* left: the node to shift records from
|
77 |
|
|
* struct hfs_bnode* right: the node to shift records to
|
78 |
|
|
* hfs_u16 first: the number of the first record in 'left' to move to 'right'
|
79 |
|
|
* Output Variable(s):
|
80 |
|
|
* NONE
|
81 |
|
|
* Returns:
|
82 |
|
|
* void
|
83 |
|
|
* Preconditions:
|
84 |
|
|
* 'left' and 'right' point to valid (struct hfs_bnode)s.
|
85 |
|
|
* 'left' contains at least 'first' records.
|
86 |
|
|
* 'right' has enough free space to hold the records to be moved from 'left'
|
87 |
|
|
* Postconditions:
|
88 |
|
|
* The record numbered 'first' and all records after it in 'left' are
|
89 |
|
|
* placed at the beginning of 'right'.
|
90 |
|
|
* The key corresponding to 'right' in its parent is NOT updated.
|
91 |
|
|
*/
|
92 |
|
|
void hfs_bnode_shift_right(struct hfs_bnode *left, struct hfs_bnode *right,
|
93 |
|
|
int first)
|
94 |
|
|
{
|
95 |
|
|
int i, adjust, nrecs;
|
96 |
|
|
unsigned size;
|
97 |
|
|
hfs_u16 *to, *from;
|
98 |
|
|
|
99 |
|
|
if ((first <= 0) || (first > left->ndNRecs)) {
|
100 |
|
|
hfs_warn("bad argument to shift_right: first=%d, nrecs=%d\n",
|
101 |
|
|
first, left->ndNRecs);
|
102 |
|
|
return;
|
103 |
|
|
}
|
104 |
|
|
|
105 |
|
|
/* initialize variables */
|
106 |
|
|
nrecs = left->ndNRecs + 1 - first;
|
107 |
|
|
size = bnode_end(left) - bnode_offset(left, first);
|
108 |
|
|
|
109 |
|
|
/* move (possibly empty) contents of right node forward */
|
110 |
|
|
memmove(bnode_datastart(right) + size,
|
111 |
|
|
bnode_datastart(right),
|
112 |
|
|
bnode_end(right) - sizeof(struct NodeDescriptor));
|
113 |
|
|
|
114 |
|
|
/* copy in new records */
|
115 |
|
|
memcpy(bnode_datastart(right), bnode_key(left,first), size);
|
116 |
|
|
|
117 |
|
|
/* fix up offsets in right node */
|
118 |
|
|
i = right->ndNRecs + 1;
|
119 |
|
|
from = RECTBL(right, i);
|
120 |
|
|
to = from - nrecs;
|
121 |
|
|
while (i--) {
|
122 |
|
|
hfs_put_hs(hfs_get_hs(from++) + size, to++);
|
123 |
|
|
}
|
124 |
|
|
adjust = sizeof(struct NodeDescriptor) - bnode_offset(left, first);
|
125 |
|
|
i = nrecs-1;
|
126 |
|
|
from = RECTBL(left, first+i);
|
127 |
|
|
while (i--) {
|
128 |
|
|
hfs_put_hs(hfs_get_hs(from++) + adjust, to++);
|
129 |
|
|
}
|
130 |
|
|
|
131 |
|
|
/* fix record counts */
|
132 |
|
|
left->ndNRecs -= nrecs;
|
133 |
|
|
right->ndNRecs += nrecs;
|
134 |
|
|
}
|
135 |
|
|
|
136 |
|
|
/*
|
137 |
|
|
* hfs_bnode_shift_left()
|
138 |
|
|
*
|
139 |
|
|
* Description:
|
140 |
|
|
* Shifts some records from a node to its left neighbor.
|
141 |
|
|
* Input Variable(s):
|
142 |
|
|
* struct hfs_bnode* left: the node to shift records to
|
143 |
|
|
* struct hfs_bnode* right: the node to shift records from
|
144 |
|
|
* hfs_u16 last: the number of the last record in 'right' to move to 'left'
|
145 |
|
|
* Output Variable(s):
|
146 |
|
|
* NONE
|
147 |
|
|
* Returns:
|
148 |
|
|
* void
|
149 |
|
|
* Preconditions:
|
150 |
|
|
* 'left' and 'right' point to valid (struct hfs_bnode)s.
|
151 |
|
|
* 'right' contains at least 'last' records.
|
152 |
|
|
* 'left' has enough free space to hold the records to be moved from 'right'
|
153 |
|
|
* Postconditions:
|
154 |
|
|
* The record numbered 'last' and all records before it in 'right' are
|
155 |
|
|
* placed at the end of 'left'.
|
156 |
|
|
* The key corresponding to 'right' in its parent is NOT updated.
|
157 |
|
|
*/
|
158 |
|
|
void hfs_bnode_shift_left(struct hfs_bnode *left, struct hfs_bnode *right,
|
159 |
|
|
int last)
|
160 |
|
|
{
|
161 |
|
|
int i, adjust, nrecs;
|
162 |
|
|
unsigned size;
|
163 |
|
|
hfs_u16 *to, *from;
|
164 |
|
|
|
165 |
|
|
if ((last <= 0) || (last > right->ndNRecs)) {
|
166 |
|
|
hfs_warn("bad argument to shift_left: last=%d, nrecs=%d\n",
|
167 |
|
|
last, right->ndNRecs);
|
168 |
|
|
return;
|
169 |
|
|
}
|
170 |
|
|
|
171 |
|
|
/* initialize variables */
|
172 |
|
|
size = bnode_offset(right, last + 1) - sizeof(struct NodeDescriptor);
|
173 |
|
|
|
174 |
|
|
/* copy records to left node */
|
175 |
|
|
memcpy(bnode_dataend(left), bnode_datastart(right), size);
|
176 |
|
|
|
177 |
|
|
/* move (possibly empty) remainder of right node backward */
|
178 |
|
|
memmove(bnode_datastart(right), bnode_datastart(right) + size,
|
179 |
|
|
bnode_end(right) - bnode_offset(right, last + 1));
|
180 |
|
|
|
181 |
|
|
/* fix up offsets */
|
182 |
|
|
nrecs = left->ndNRecs;
|
183 |
|
|
i = last;
|
184 |
|
|
from = RECTBL(right, 2);
|
185 |
|
|
to = RECTBL(left, nrecs + 2);
|
186 |
|
|
adjust = bnode_offset(left, nrecs + 1) - sizeof(struct NodeDescriptor);
|
187 |
|
|
while (i--) {
|
188 |
|
|
hfs_put_hs(hfs_get_hs(from--) + adjust, to--);
|
189 |
|
|
}
|
190 |
|
|
i = right->ndNRecs + 1 - last;
|
191 |
|
|
++from;
|
192 |
|
|
to = RECTBL(right, 1);
|
193 |
|
|
while (i--) {
|
194 |
|
|
hfs_put_hs(hfs_get_hs(from--) - size, to--);
|
195 |
|
|
}
|
196 |
|
|
|
197 |
|
|
/* fix record counts */
|
198 |
|
|
left->ndNRecs += last;
|
199 |
|
|
right->ndNRecs -= last;
|
200 |
|
|
}
|
201 |
|
|
|
202 |
|
|
/*
|
203 |
|
|
* hfs_bnode_in_brec()
|
204 |
|
|
*
|
205 |
|
|
* Description:
|
206 |
|
|
* Determines whethet a given bnode is part of a given brec.
|
207 |
|
|
* This is used to avoid deadlock in the case of a corrupted b-tree.
|
208 |
|
|
* Input Variable(s):
|
209 |
|
|
* hfs_u32 node: the number of the node to check for.
|
210 |
|
|
* struct hfs_brec* brec: the brec to check in.
|
211 |
|
|
* Output Variable(s):
|
212 |
|
|
* NONE
|
213 |
|
|
* Returns:
|
214 |
|
|
* int: 1 it found, 0 if not
|
215 |
|
|
* Preconditions:
|
216 |
|
|
* 'brec' points to a valid struct hfs_brec.
|
217 |
|
|
* Postconditions:
|
218 |
|
|
* 'brec' is unchanged.
|
219 |
|
|
*/
|
220 |
|
|
int hfs_bnode_in_brec(hfs_u32 node, const struct hfs_brec *brec)
|
221 |
|
|
{
|
222 |
|
|
const struct hfs_belem *belem = brec->bottom;
|
223 |
|
|
|
224 |
|
|
while (belem && (belem >= brec->top)) {
|
225 |
|
|
if (belem->bnr.bn && (belem->bnr.bn->node == node)) {
|
226 |
|
|
return 1;
|
227 |
|
|
}
|
228 |
|
|
--belem;
|
229 |
|
|
}
|
230 |
|
|
return 0;
|
231 |
|
|
}
|