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