1 /*
2 * hfsutils - tools for reading and writing Macintosh HFS volumes
3 * Copyright (C) 1996, 1997 Robert Leslie
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
18 */
19
20 # include <stdlib.h>
21 # include <string.h>
22 # include <errno.h>
23
24 # include "internal.h"
25 # include "data.h"
26 # include "btree.h"
27 # include "node.h"
28
29 # define NODESPACE(n) \
30 (HFS_BLOCKSZ - (n).roff[(n).nd.ndNRecs] - 2 * ((n).nd.ndNRecs + 1))
31
32 /*
33 * NAME: node->init()
34 * DESCRIPTION: construct an empty node
35 */
n_init(node * np,btree * bt,int type,int height)36 void n_init(node *np, btree *bt, int type, int height)
37 {
38 np->bt = bt;
39 np->nnum = -1;
40
41 np->nd.ndFLink = 0;
42 np->nd.ndBLink = 0;
43 np->nd.ndType = type;
44 np->nd.ndNHeight = height;
45 np->nd.ndNRecs = 0;
46 np->nd.ndResv2 = 0;
47
48 np->rnum = -1;
49 np->roff[0] = 0x00e;
50
51 memset(np->data, 0, sizeof(np->data));
52 }
53
54 /*
55 * NAME: node->new()
56 * DESCRIPTION: allocate a new b*-tree node
57 */
n_new(node * np)58 int n_new(node *np)
59 {
60 btree *bt = np->bt;
61 unsigned long num;
62
63 if (bt->hdr.bthFree == 0)
64 {
65 ERROR(EIO, "b*-tree full");
66 return -1;
67 }
68
69 num = 0;
70 while (num < bt->hdr.bthNNodes && BMTST(bt->map, num))
71 ++num;
72
73 if (num == bt->hdr.bthNNodes)
74 {
75 ERROR(EIO, "free b*-tree node not found");
76 return -1;
77 }
78
79 np->nnum = num;
80
81 BMSET(bt->map, num);
82 --bt->hdr.bthFree;
83
84 bt->flags |= HFS_UPDATE_BTHDR;
85
86 return 0;
87 }
88
89 /*
90 * NAME: node->free()
91 * DESCRIPTION: deallocate a b*-tree node
92 */
n_free(node * np)93 void n_free(node *np)
94 {
95 btree *bt = np->bt;
96
97 BMCLR(bt->map, np->nnum);
98 ++bt->hdr.bthFree;
99
100 bt->flags |= HFS_UPDATE_BTHDR;
101 }
102
103 /*
104 * NAME: node->compact()
105 * DESCRIPTION: clean up a node, removing deleted records
106 */
n_compact(node * np)107 void n_compact(node *np)
108 {
109 unsigned char *ptr;
110 int offset, nrecs, i;
111
112 offset = 0x00e;
113 ptr = np->data + offset;
114 nrecs = 0;
115
116 for (i = 0; i < np->nd.ndNRecs; ++i)
117 {
118 unsigned char *rec;
119 int reclen;
120
121 rec = HFS_NODEREC(*np, i);
122 reclen = np->roff[i + 1] - np->roff[i];
123
124 if (HFS_RECKEYLEN(rec) > 0)
125 {
126 np->roff[nrecs++] = offset;
127 offset += reclen;
128
129 if (ptr == rec)
130 ptr += reclen;
131 else
132 {
133 while (reclen--)
134 *ptr++ = *rec++;
135 }
136 }
137 }
138
139 np->roff[nrecs] = offset;
140 np->nd.ndNRecs = nrecs;
141 }
142
143 /*
144 * NAME: node->search()
145 * DESCRIPTION: locate a record in a node, or the record it should follow
146 */
n_search(node * np,unsigned char * key)147 int n_search(node *np, unsigned char *key)
148 {
149 btree *bt = np->bt;
150 int i, comp = -1;
151
152 for (i = np->nd.ndNRecs; i--; )
153 {
154 unsigned char *rec;
155
156 rec = HFS_NODEREC(*np, i);
157
158 if (HFS_RECKEYLEN(rec) == 0)
159 continue; /* deleted record */
160
161 comp = bt->compare(rec, key);
162
163 if (comp <= 0)
164 break;
165 }
166
167 np->rnum = i;
168
169 return comp == 0;
170 }
171
172 /*
173 * NAME: node->index()
174 * DESCRIPTION: create an index record from a key and node pointer
175 */
n_index(btree * bt,unsigned char * key,unsigned long nnum,unsigned char * record,int * reclen)176 void n_index(btree *bt, unsigned char *key, unsigned long nnum,
177 unsigned char *record, int *reclen)
178 {
179 if (bt == &bt->f.vol->cat)
180 {
181 /* force the key length to be 0x25 */
182
183 HFS_RECKEYLEN(record) = 0x25;
184 memset(record + 1, 0, 0x25);
185 memcpy(record + 1, key + 1, HFS_RECKEYLEN(key));
186 }
187 else
188 memcpy(record, key, HFS_RECKEYSKIP(key));
189
190 d_putl(HFS_RECDATA(record), nnum);
191
192 if (reclen)
193 *reclen = HFS_RECKEYSKIP(record) + 4;
194 }
195
196 /*
197 * NAME: node->split()
198 * DESCRIPTION: divide a node into two and insert a record
199 */
n_split(node * left,unsigned char * record,int * reclen)200 int n_split(node *left, unsigned char *record, int *reclen)
201 {
202 node right;
203 int nrecs, i, mid;
204 unsigned char *rec;
205
206 right = *left;
207 right.nd.ndBLink = left->nnum;
208
209 if (n_new(&right) < 0)
210 return -1;
211
212 left->nd.ndFLink = right.nnum;
213 nrecs = left->nd.ndNRecs;
214
215 /*
216 * Ensure node split leaves enough room for new record.
217 * The size calculations used are based on the NODESPACE() macro, but
218 * I don't know what the extra 2's and 1's are needed for.
219 * John Witford <jwitford@hutch.com.au>
220 */
221 n_search(&right, record);
222 mid = nrecs/2;
223 for(;;)
224 {
225 if (right.rnum < mid)
226 {
227 if ( mid > 0
228 && left->roff[mid] + *reclen + 2 > HFS_BLOCKSZ - 2 * (mid + 1))
229 {
230 --mid;
231 if (mid > 0)
232 continue;
233 }
234 }
235 else
236 {
237 if ( mid < nrecs
238 && right.roff[nrecs] - right.roff[mid] + left->roff[0] + *reclen + 2 > HFS_BLOCKSZ - 2 * (mid + 1))
239 {
240 ++mid;
241 if (mid < nrecs)
242 continue;
243 }
244 }
245 break;
246 }
247
248 for (i = 0; i < nrecs; ++i)
249 {
250 if (i < mid)
251 rec = HFS_NODEREC(right, i);
252 else
253 rec = HFS_NODEREC(*left, i);
254
255 HFS_RECKEYLEN(rec) = 0;
256 }
257
258 /* original code ...
259 for (i = 0; i < nrecs; ++i)
260 {
261 if (i < nrecs / 2)
262 rec = HFS_NODEREC(right, i);
263 else
264 rec = HFS_NODEREC(*left, i);
265
266 HFS_RECKEYLEN(rec) = 0;
267 }
268 */
269 n_compact(left);
270 n_compact(&right);
271
272 n_search(&right, record);
273 if (right.rnum >= 0)
274 n_insertx(&right, record, *reclen);
275 else
276 {
277 n_search(left, record);
278 n_insertx(left, record, *reclen);
279 }
280
281 /* store the new/modified nodes */
282
283 if (bt_putnode(left) < 0 ||
284 bt_putnode(&right) < 0)
285 return -1;
286
287 /* create an index record for the new node in the parent */
288
289 n_index(right.bt, HFS_NODEREC(right, 0), right.nnum, record, reclen);
290
291 /* update link pointers */
292
293 if (left->bt->hdr.bthLNode == left->nnum)
294 {
295 left->bt->hdr.bthLNode = right.nnum;
296 left->bt->flags |= HFS_UPDATE_BTHDR;
297 }
298
299 if (right.nd.ndFLink)
300 {
301 node n;
302
303 n.bt = right.bt;
304 n.nnum = right.nd.ndFLink;
305
306 if (bt_getnode(&n) < 0)
307 return -1;
308
309 n.nd.ndBLink = right.nnum;
310
311 if (bt_putnode(&n) < 0)
312 return -1;
313 }
314
315 return 0;
316 }
317
318 /*
319 * NAME: node->insertx()
320 * DESCRIPTION: insert a record into a node (which must already have room)
321 */
n_insertx(node * np,unsigned char * record,int reclen)322 void n_insertx(node *np, unsigned char *record, int reclen)
323 {
324 int rnum, i;
325 unsigned char *ptr;
326
327 rnum = np->rnum + 1;
328
329 /* push other records down to make room */
330
331 for (ptr = HFS_NODEREC(*np, np->nd.ndNRecs) + reclen;
332 ptr > HFS_NODEREC(*np, rnum) + reclen; --ptr)
333 *(ptr - 1) = *(ptr - 1 - reclen);
334
335 ++np->nd.ndNRecs;
336
337 for (i = np->nd.ndNRecs; i > rnum; --i)
338 np->roff[i] = np->roff[i - 1] + reclen;
339
340 /* write the new record */
341
342 memcpy(HFS_NODEREC(*np, rnum), record, reclen);
343 }
344
345 /*
346 * NAME: node->insert()
347 * DESCRIPTION: insert a new record into a node; return a record for parent
348 */
n_insert(node * np,unsigned char * record,int * reclen)349 int n_insert(node *np, unsigned char *record, int *reclen)
350 {
351 n_compact(np);
352
353 /* check for free space */
354
355 if (np->nd.ndNRecs >= HFS_MAXRECS ||
356 *reclen + 2 > NODESPACE(*np))
357 return n_split(np, record, reclen);
358
359 n_insertx(np, record, *reclen);
360 *reclen = 0;
361
362 return bt_putnode(np);
363 }
364
365 /*
366 * NAME: node->merge()
367 * DESCRIPTION: combine two nodes into a single node
368 */
n_merge(node * right,node * left,unsigned char * record,int * flag)369 int n_merge(node *right, node *left, unsigned char *record, int *flag)
370 {
371 int i, offset;
372
373 /* copy records and offsets */
374
375 memcpy(HFS_NODEREC(*left, left->nd.ndNRecs), HFS_NODEREC(*right, 0),
376 right->roff[right->nd.ndNRecs] - right->roff[0]);
377
378 offset = left->roff[left->nd.ndNRecs] - right->roff[0];
379
380 for (i = 1; i <= right->nd.ndNRecs; ++i)
381 left->roff[++left->nd.ndNRecs] = offset + right->roff[i];
382
383 /* update link pointers */
384
385 left->nd.ndFLink = right->nd.ndFLink;
386
387 if (bt_putnode(left) < 0)
388 return -1;
389
390 if (right->bt->hdr.bthLNode == right->nnum)
391 {
392 right->bt->hdr.bthLNode = left->nnum;
393 right->bt->flags |= HFS_UPDATE_BTHDR;
394 }
395
396 if (right->nd.ndFLink)
397 {
398 node n;
399
400 n.bt = right->bt;
401 n.nnum = right->nd.ndFLink;
402
403 if (bt_getnode(&n) < 0)
404 return -1;
405
406 n.nd.ndBLink = left->nnum;
407
408 if (bt_putnode(&n) < 0)
409 return -1;
410 }
411
412 n_free(right);
413
414 HFS_RECKEYLEN(record) = 0;
415 *flag = 1;
416
417 return 0;
418 }
419
420 /*
421 * NAME: node->delete()
422 * DESCRIPTION: remove a record from a node
423 */
n_delete(node * np,unsigned char * record,int * flag)424 int n_delete(node *np, unsigned char *record, int *flag)
425 {
426 node left;
427 unsigned char *rec;
428
429 rec = HFS_NODEREC(*np, np->rnum);
430
431 HFS_RECKEYLEN(rec) = 0;
432 n_compact(np);
433
434 /* see if we can merge with our left sibling */
435
436 left.bt = np->bt;
437 left.nnum = np->nd.ndBLink;
438
439 if (left.nnum > 0)
440 {
441 if (bt_getnode(&left) < 0)
442 return -1;
443
444 if (np->nd.ndNRecs + left.nd.ndNRecs <= HFS_MAXRECS &&
445 np->roff[np->nd.ndNRecs] - np->roff[0] +
446 2 * np->nd.ndNRecs <= NODESPACE(left))
447 return n_merge(np, &left, record, flag);
448 }
449
450 if (np->rnum == 0)
451 {
452 /* special case: first record changed; update parent record key */
453
454 n_index(np->bt, HFS_NODEREC(*np, 0), np->nnum, record, 0);
455 *flag = 1;
456 }
457
458 return bt_putnode(np);
459 }
460