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