/[pearpc]/src/io/prom/fs/hfs/node.c
This is repository of my old source code which isn't updated any more. Go to git.rot13.org for current projects!
ViewVC logotype

Contents of /src/io/prom/fs/hfs/node.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1 - (show annotations)
Wed Sep 5 17:11:21 2007 UTC (16 years, 6 months ago) by dpavlin
File MIME type: text/plain
File size: 9150 byte(s)
import upstream CVS
1 /*
2 * libhfs - library for reading and writing Macintosh HFS volumes
3 * Copyright (C) 1996-1998 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
21 # ifdef HAVE_CONFIG_H
22 # include "config.h"
23 # endif
24
25 # include <stdlib.h>
26 # include <string.h>
27 # include <errno.h>
28
29 # include "libhfs.h"
30 # include "node.h"
31 # include "data.h"
32 # include "btree.h"
33
34 /* total bytes used by records (NOT including record offsets) */
35
36 # define NODEUSED(n) \
37 ((size_t) ((n).roff[(n).nd.ndNRecs] - (n).roff[0]))
38
39 /* total bytes available for new records (INCLUDING record offsets) */
40
41 # define NODEFREE(n) \
42 ((size_t) (HFS_BLOCKSZ - (n).roff[(n).nd.ndNRecs] - \
43 2 * ((n).nd.ndNRecs + 1)))
44
45 /*
46 * NAME: node->init()
47 * DESCRIPTION: construct an empty node
48 */
49 void n_init(node *np, btree *bt, int type, int height)
50 {
51 np->bt = bt;
52 np->nnum = (unsigned long) -1;
53
54 np->nd.ndFLink = 0;
55 np->nd.ndBLink = 0;
56 np->nd.ndType = type;
57 np->nd.ndNHeight = height;
58 np->nd.ndNRecs = 0;
59 np->nd.ndResv2 = 0;
60
61 np->rnum = -1;
62 np->roff[0] = 0x00e;
63
64 memset(&np->data, 0, sizeof(np->data));
65 }
66
67 /*
68 * NAME: node->new()
69 * DESCRIPTION: allocate a new b*-tree node
70 */
71 int n_new(node *np)
72 {
73 btree *bt = np->bt;
74 unsigned long num;
75
76 if (bt->hdr.bthFree == 0)
77 ERROR(EIO, "b*-tree full");
78
79 num = 0;
80 while (num < bt->hdr.bthNNodes && BMTST(bt->map, num))
81 ++num;
82
83 if (num == bt->hdr.bthNNodes)
84 ERROR(EIO, "free b*-tree node not found");
85
86 np->nnum = num;
87
88 BMSET(bt->map, num);
89 --bt->hdr.bthFree;
90
91 bt->flags |= HFS_BT_UPDATE_HDR;
92
93 return 0;
94
95 fail:
96 return -1;
97 }
98
99 /*
100 * NAME: node->free()
101 * DESCRIPTION: deallocate and remove a b*-tree node
102 */
103 int n_free(node *np)
104 {
105 btree *bt = np->bt;
106 node sib;
107
108 if (bt->hdr.bthFNode == np->nnum)
109 bt->hdr.bthFNode = np->nd.ndFLink;
110
111 if (bt->hdr.bthLNode == np->nnum)
112 bt->hdr.bthLNode = np->nd.ndBLink;
113
114 if (np->nd.ndFLink > 0)
115 {
116 if (bt_getnode(&sib, bt, np->nd.ndFLink) == -1)
117 goto fail;
118
119 sib.nd.ndBLink = np->nd.ndBLink;
120
121 if (bt_putnode(&sib) == -1)
122 goto fail;
123 }
124
125 if (np->nd.ndBLink > 0)
126 {
127 if (bt_getnode(&sib, bt, np->nd.ndBLink) == -1)
128 goto fail;
129
130 sib.nd.ndFLink = np->nd.ndFLink;
131
132 if (bt_putnode(&sib) == -1)
133 goto fail;
134 }
135
136 BMCLR(bt->map, np->nnum);
137 ++bt->hdr.bthFree;
138
139 bt->flags |= HFS_BT_UPDATE_HDR;
140
141 return 0;
142
143 fail:
144 return -1;
145 }
146
147 /*
148 * NAME: compact()
149 * DESCRIPTION: clean up a node, removing deleted records
150 */
151 static
152 void compact(node *np)
153 {
154 byte *ptr;
155 int offset, nrecs, i;
156
157 offset = 0x00e;
158 ptr = np->data + offset;
159 nrecs = 0;
160
161 for (i = 0; i < np->nd.ndNRecs; ++i)
162 {
163 const byte *rec;
164 int reclen;
165
166 rec = HFS_NODEREC(*np, i);
167 reclen = HFS_RECLEN(*np, i);
168
169 if (HFS_RECKEYLEN(rec) > 0)
170 {
171 np->roff[nrecs++] = offset;
172 offset += reclen;
173
174 if (ptr == rec)
175 ptr += reclen;
176 else
177 {
178 while (reclen--)
179 *ptr++ = *rec++;
180 }
181 }
182 }
183
184 np->roff[nrecs] = offset;
185 np->nd.ndNRecs = nrecs;
186 }
187
188 /*
189 * NAME: node->search()
190 * DESCRIPTION: locate a record in a node, or the record it should follow
191 */
192 int n_search(node *np, const byte *pkey)
193 {
194 const btree *bt = np->bt;
195 byte key1[HFS_MAX_KEYLEN], key2[HFS_MAX_KEYLEN];
196 int i, comp = -1;
197
198 bt->keyunpack(pkey, key2);
199
200 for (i = np->nd.ndNRecs; i--; )
201 {
202 const byte *rec;
203
204 rec = HFS_NODEREC(*np, i);
205
206 if (HFS_RECKEYLEN(rec) == 0)
207 continue; /* deleted record */
208
209 bt->keyunpack(rec, key1);
210 comp = bt->keycompare(key1, key2);
211
212 if (comp <= 0)
213 break;
214 }
215
216 np->rnum = i;
217
218 return comp == 0;
219 }
220
221 /*
222 * NAME: node->index()
223 * DESCRIPTION: create an index record from a key and node pointer
224 */
225 void n_index(const node *np, byte *record, unsigned int *reclen)
226 {
227 const byte *key = HFS_NODEREC(*np, 0);
228
229 if (np->bt == &np->bt->f.vol->cat)
230 {
231 /* force the key length to be 0x25 */
232
233 HFS_SETKEYLEN(record, 0x25);
234 memset(record + 1, 0, 0x25);
235 memcpy(record + 1, key + 1, HFS_RECKEYLEN(key));
236 }
237 else
238 memcpy(record, key, HFS_RECKEYSKIP(key));
239
240 d_putul(HFS_RECDATA(record), np->nnum);
241
242 if (reclen)
243 *reclen = HFS_RECKEYSKIP(record) + 4;
244 }
245
246 /*
247 * NAME: split()
248 * DESCRIPTION: divide a node into two and insert a record
249 */
250 static
251 int split(node *left, byte *record, unsigned int *reclen)
252 {
253 btree *bt = left->bt;
254 node n, *right = &n, *side = 0;
255 int mark, i;
256
257 /* create a second node by cloning the first */
258
259 *right = *left;
260
261 if (n_new(right) == -1)
262 goto fail;
263
264 left->nd.ndFLink = right->nnum;
265 right->nd.ndBLink = left->nnum;
266
267 /* divide all records evenly between the two nodes */
268
269 mark = (NODEUSED(*left) + 2 * left->nd.ndNRecs + *reclen + 2) >> 1;
270
271 if (left->rnum == -1)
272 {
273 side = left;
274 mark -= *reclen + 2;
275 }
276
277 for (i = 0; i < left->nd.ndNRecs; ++i)
278 {
279 node *np;
280 byte *rec;
281
282 np = (mark > 0) ? right : left;
283 rec = HFS_NODEREC(*np, i);
284
285 mark -= HFS_RECLEN(*np, i) + 2;
286
287 HFS_SETKEYLEN(rec, 0);
288
289 if (left->rnum == i)
290 {
291 side = (mark > 0) ? left : right;
292 mark -= *reclen + 2;
293 }
294 }
295
296 compact(left);
297 compact(right);
298
299 /* insert the new record and store the modified nodes */
300
301 ASSERT(side);
302
303 n_search(side, record);
304 n_insertx(side, record, *reclen);
305
306 if (bt_putnode(left) == -1 ||
307 bt_putnode(right) == -1)
308 goto fail;
309
310 /* create an index record in the parent for the new node */
311
312 n_index(right, record, reclen);
313
314 /* update link pointers */
315
316 if (bt->hdr.bthLNode == left->nnum)
317 {
318 bt->hdr.bthLNode = right->nnum;
319 bt->flags |= HFS_BT_UPDATE_HDR;
320 }
321
322 if (right->nd.ndFLink > 0)
323 {
324 node sib;
325
326 if (bt_getnode(&sib, right->bt, right->nd.ndFLink) == -1)
327 goto fail;
328
329 sib.nd.ndBLink = right->nnum;
330
331 if (bt_putnode(&sib) == -1)
332 goto fail;
333 }
334
335 return 0;
336
337 fail:
338 return -1;
339 }
340
341 /*
342 * NAME: node->insertx()
343 * DESCRIPTION: insert a record into a node (which must already have room)
344 */
345 void n_insertx(node *np, const byte *record, unsigned int reclen)
346 {
347 int rnum, i;
348 byte *ptr;
349
350 rnum = np->rnum + 1;
351
352 /* push other records down to make room */
353
354 for (ptr = HFS_NODEREC(*np, np->nd.ndNRecs) + reclen;
355 ptr > HFS_NODEREC(*np, rnum) + reclen; --ptr)
356 *(ptr - 1) = *(ptr - 1 - reclen);
357
358 ++np->nd.ndNRecs;
359
360 for (i = np->nd.ndNRecs; i > rnum; --i)
361 np->roff[i] = np->roff[i - 1] + reclen;
362
363 /* write the new record */
364
365 memcpy(HFS_NODEREC(*np, rnum), record, reclen);
366 }
367
368 /*
369 * NAME: node->insert()
370 * DESCRIPTION: insert a new record into a node; return a record for parent
371 */
372 int n_insert(node *np, byte *record, unsigned int *reclen)
373 {
374 /* check for free space */
375
376 if (np->nd.ndNRecs >= HFS_MAX_NRECS ||
377 *reclen + 2 > NODEFREE(*np))
378 return split(np, record, reclen);
379
380 n_insertx(np, record, *reclen);
381 *reclen = 0;
382
383 return bt_putnode(np);
384 }
385
386 /*
387 * NAME: join()
388 * DESCRIPTION: combine two nodes into a single node
389 */
390 static
391 int join(node *left, node *right, byte *record, int *flag)
392 {
393 int i, offset;
394
395 /* copy records and offsets */
396
397 memcpy(HFS_NODEREC(*left, left->nd.ndNRecs),
398 HFS_NODEREC(*right, 0), NODEUSED(*right));
399
400 offset = left->roff[left->nd.ndNRecs] - right->roff[0];
401
402 for (i = 1; i <= right->nd.ndNRecs; ++i)
403 left->roff[++left->nd.ndNRecs] = offset + right->roff[i];
404
405 if (bt_putnode(left) == -1)
406 goto fail;
407
408 /* eliminate node and update link pointers */
409
410 if (n_free(right) == -1)
411 goto fail;
412
413 HFS_SETKEYLEN(record, 0);
414 *flag = 1;
415
416 return 0;
417
418 fail:
419 return -1;
420 }
421
422 /*
423 * NAME: node->delete()
424 * DESCRIPTION: remove a record from a node
425 */
426 int n_delete(node *np, byte *record, int *flag)
427 {
428 byte *rec;
429
430 rec = HFS_NODEREC(*np, np->rnum);
431
432 HFS_SETKEYLEN(rec, 0);
433 compact(np);
434
435 if (np->nd.ndNRecs == 0)
436 {
437 if (n_free(np) == -1)
438 goto fail;
439
440 HFS_SETKEYLEN(record, 0);
441 *flag = 1;
442
443 return 0;
444 }
445
446 /* see if we can join with our left sibling */
447
448 if (np->nd.ndBLink > 0)
449 {
450 node left;
451
452 if (bt_getnode(&left, np->bt, np->nd.ndBLink) == -1)
453 goto fail;
454
455 if (np->nd.ndNRecs + left.nd.ndNRecs <= HFS_MAX_NRECS &&
456 NODEUSED(*np) + 2 * np->nd.ndNRecs <= NODEFREE(left))
457 return join(&left, np, record, flag);
458 }
459
460 if (np->rnum == 0)
461 {
462 /* special case: first record changed; update parent record key */
463
464 n_index(np, record, 0);
465 *flag = 1;
466 }
467
468 return bt_putnode(np);
469
470 fail:
471 return -1;
472 }

  ViewVC Help
Powered by ViewVC 1.1.26