/[pearpc]/src/io/prom/fs/hfs/btree.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/btree.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: 13882 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 "btree.h"
31 # include "data.h"
32 # include "file.h"
33 # include "block.h"
34 # include "node.h"
35
36 /*
37 * NAME: btree->getnode()
38 * DESCRIPTION: retrieve a numbered node from a B*-tree file
39 */
40 int bt_getnode(node *np, btree *bt, unsigned long nnum)
41 {
42 block *bp = &np->data;
43 const byte *ptr;
44 int i;
45
46 np->bt = bt;
47 np->nnum = nnum;
48
49 # if 0
50 fprintf(stderr, "BTREE: GET vol \"%s\" btree \"%s\" node %lu\n",
51 bt->f.vol->mdb.drVN, bt->f.name, np->nnum);
52 # endif
53
54 /* verify the node exists and is marked as in-use */
55
56 if (nnum > 0 && nnum >= bt->hdr.bthNNodes)
57 ERROR(EIO, "read nonexistent b*-tree node");
58 else if (bt->map && ! BMTST(bt->map, nnum))
59 ERROR(EIO, "read unallocated b*-tree node");
60
61 if (f_getblock(&bt->f, nnum, bp) == -1)
62 goto fail;
63
64 ptr = *bp;
65
66 d_fetchul(&ptr, &np->nd.ndFLink);
67 d_fetchul(&ptr, &np->nd.ndBLink);
68 d_fetchsb(&ptr, &np->nd.ndType);
69 d_fetchsb(&ptr, &np->nd.ndNHeight);
70 d_fetchuw(&ptr, &np->nd.ndNRecs);
71 d_fetchsw(&ptr, &np->nd.ndResv2);
72
73 if (np->nd.ndNRecs > HFS_MAX_NRECS)
74 ERROR(EIO, "too many b*-tree node records");
75
76 i = np->nd.ndNRecs + 1;
77
78 ptr = *bp + HFS_BLOCKSZ - (2 * i);
79
80 while (i--)
81 d_fetchuw(&ptr, &np->roff[i]);
82
83 return 0;
84
85 fail:
86 return -1;
87 }
88
89 /*
90 * NAME: btree->putnode()
91 * DESCRIPTION: store a numbered node into a B*-tree file
92 */
93 int bt_putnode(node *np)
94 {
95 btree *bt = np->bt;
96 block *bp = &np->data;
97 byte *ptr;
98 int i;
99
100 # if 0
101 fprintf(stderr, "BTREE: PUT vol \"%s\" btree \"%s\" node %lu\n",
102 bt->f.vol->mdb.drVN, bt->f.name, np->nnum);
103 # endif
104
105 /* verify the node exists and is marked as in-use */
106
107 if (np->nnum > 0 && np->nnum >= bt->hdr.bthNNodes)
108 ERROR(EIO, "write nonexistent b*-tree node");
109 else if (bt->map && ! BMTST(bt->map, np->nnum))
110 ERROR(EIO, "write unallocated b*-tree node");
111
112 ptr = *bp;
113
114 d_storeul(&ptr, np->nd.ndFLink);
115 d_storeul(&ptr, np->nd.ndBLink);
116 d_storesb(&ptr, np->nd.ndType);
117 d_storesb(&ptr, np->nd.ndNHeight);
118 d_storeuw(&ptr, np->nd.ndNRecs);
119 d_storesw(&ptr, np->nd.ndResv2);
120
121 if (np->nd.ndNRecs > HFS_MAX_NRECS)
122 ERROR(EIO, "too many b*-tree node records");
123
124 i = np->nd.ndNRecs + 1;
125
126 ptr = *bp + HFS_BLOCKSZ - (2 * i);
127
128 while (i--)
129 d_storeuw(&ptr, np->roff[i]);
130
131 return f_putblock(&bt->f, np->nnum, bp);
132
133 fail:
134 return -1;
135 }
136
137 /*
138 * NAME: btree->readhdr()
139 * DESCRIPTION: read the header node of a B*-tree
140 */
141 int bt_readhdr(btree *bt)
142 {
143 const byte *ptr;
144 byte *map = 0;
145 int i;
146 unsigned long nnum;
147
148 if (bt_getnode(&bt->hdrnd, bt, 0) == -1)
149 goto fail;
150
151 if (bt->hdrnd.nd.ndType != ndHdrNode ||
152 bt->hdrnd.nd.ndNRecs != 3 ||
153 bt->hdrnd.roff[0] != 0x00e ||
154 bt->hdrnd.roff[1] != 0x078 ||
155 bt->hdrnd.roff[2] != 0x0f8 ||
156 bt->hdrnd.roff[3] != 0x1f8)
157 ERROR(EIO, "malformed b*-tree header node");
158
159 /* read header record */
160
161 ptr = HFS_NODEREC(bt->hdrnd, 0);
162
163 d_fetchuw(&ptr, &bt->hdr.bthDepth);
164 d_fetchul(&ptr, &bt->hdr.bthRoot);
165 d_fetchul(&ptr, &bt->hdr.bthNRecs);
166 d_fetchul(&ptr, &bt->hdr.bthFNode);
167 d_fetchul(&ptr, &bt->hdr.bthLNode);
168 d_fetchuw(&ptr, &bt->hdr.bthNodeSize);
169 d_fetchuw(&ptr, &bt->hdr.bthKeyLen);
170 d_fetchul(&ptr, &bt->hdr.bthNNodes);
171 d_fetchul(&ptr, &bt->hdr.bthFree);
172
173 for (i = 0; i < 76; ++i)
174 d_fetchsb(&ptr, &bt->hdr.bthResv[i]);
175
176 if (bt->hdr.bthNodeSize != HFS_BLOCKSZ)
177 ERROR(EINVAL, "unsupported b*-tree node size");
178
179 /* read map record; construct btree bitmap */
180 /* don't set bt->map until we're done, since getnode() checks it */
181
182 map = ALLOC(byte, HFS_MAP1SZ);
183 if (map == 0)
184 ERROR(ENOMEM, 0);
185
186 memcpy(map, HFS_NODEREC(bt->hdrnd, 2), HFS_MAP1SZ);
187 bt->mapsz = HFS_MAP1SZ;
188
189 /* read continuation map records, if any */
190
191 nnum = bt->hdrnd.nd.ndFLink;
192
193 while (nnum)
194 {
195 node n;
196 byte *newmap;
197
198 if (bt_getnode(&n, bt, nnum) == -1)
199 goto fail;
200
201 if (n.nd.ndType != ndMapNode ||
202 n.nd.ndNRecs != 1 ||
203 n.roff[0] != 0x00e ||
204 n.roff[1] != 0x1fa)
205 ERROR(EIO, "malformed b*-tree map node");
206
207 newmap = REALLOC(map, byte, bt->mapsz + HFS_MAPXSZ);
208 if (newmap == 0)
209 ERROR(ENOMEM, 0);
210
211 map = newmap;
212
213 memcpy(map + bt->mapsz, HFS_NODEREC(n, 0), HFS_MAPXSZ);
214 bt->mapsz += HFS_MAPXSZ;
215
216 nnum = n.nd.ndFLink;
217 }
218
219 bt->map = map;
220
221 return 0;
222
223 fail:
224 FREE(map);
225 return -1;
226 }
227
228 /*
229 * NAME: btree->writehdr()
230 * DESCRIPTION: write the header node of a B*-tree
231 */
232 int bt_writehdr(btree *bt)
233 {
234 byte *ptr, *map;
235 unsigned long mapsz, nnum;
236 int i;
237
238 ASSERT(bt->hdrnd.bt == bt &&
239 bt->hdrnd.nnum == 0 &&
240 bt->hdrnd.nd.ndType == ndHdrNode &&
241 bt->hdrnd.nd.ndNRecs == 3);
242
243 ptr = HFS_NODEREC(bt->hdrnd, 0);
244
245 d_storeuw(&ptr, bt->hdr.bthDepth);
246 d_storeul(&ptr, bt->hdr.bthRoot);
247 d_storeul(&ptr, bt->hdr.bthNRecs);
248 d_storeul(&ptr, bt->hdr.bthFNode);
249 d_storeul(&ptr, bt->hdr.bthLNode);
250 d_storeuw(&ptr, bt->hdr.bthNodeSize);
251 d_storeuw(&ptr, bt->hdr.bthKeyLen);
252 d_storeul(&ptr, bt->hdr.bthNNodes);
253 d_storeul(&ptr, bt->hdr.bthFree);
254
255 for (i = 0; i < 76; ++i)
256 d_storesb(&ptr, bt->hdr.bthResv[i]);
257
258 memcpy(HFS_NODEREC(bt->hdrnd, 2), bt->map, HFS_MAP1SZ);
259
260 if (bt_putnode(&bt->hdrnd) == -1)
261 goto fail;
262
263 map = bt->map + HFS_MAP1SZ;
264 mapsz = bt->mapsz - HFS_MAP1SZ;
265
266 nnum = bt->hdrnd.nd.ndFLink;
267
268 while (mapsz)
269 {
270 node n;
271
272 if (nnum == 0)
273 ERROR(EIO, "truncated b*-tree map");
274
275 if (bt_getnode(&n, bt, nnum) == -1)
276 goto fail;
277
278 if (n.nd.ndType != ndMapNode ||
279 n.nd.ndNRecs != 1 ||
280 n.roff[0] != 0x00e ||
281 n.roff[1] != 0x1fa)
282 ERROR(EIO, "malformed b*-tree map node");
283
284 memcpy(HFS_NODEREC(n, 0), map, HFS_MAPXSZ);
285
286 if (bt_putnode(&n) == -1)
287 goto fail;
288
289 map += HFS_MAPXSZ;
290 mapsz -= HFS_MAPXSZ;
291
292 nnum = n.nd.ndFLink;
293 }
294
295 bt->flags &= ~HFS_BT_UPDATE_HDR;
296
297 return 0;
298
299 fail:
300 return -1;
301 }
302
303 /* High-Level B*-Tree Routines ============================================= */
304
305 /*
306 * NAME: btree->space()
307 * DESCRIPTION: assert space for new records, or extend the file
308 */
309 int bt_space(btree *bt, unsigned int nrecs)
310 {
311 unsigned int nnodes;
312 long space;
313
314 nnodes = nrecs * (bt->hdr.bthDepth + 1);
315
316 if (nnodes <= bt->hdr.bthFree)
317 goto done;
318
319 /* make sure the extents tree has room too */
320
321 if (bt != &bt->f.vol->ext)
322 {
323 if (bt_space(&bt->f.vol->ext, 1) == -1)
324 goto fail;
325 }
326
327 space = f_alloc(&bt->f);
328 if (space == -1)
329 goto fail;
330
331 nnodes = space * (bt->f.vol->mdb.drAlBlkSiz / bt->hdr.bthNodeSize);
332
333 bt->hdr.bthNNodes += nnodes;
334 bt->hdr.bthFree += nnodes;
335
336 bt->flags |= HFS_BT_UPDATE_HDR;
337
338 bt->f.vol->flags |= HFS_VOL_UPDATE_ALTMDB;
339
340 while (bt->hdr.bthNNodes > bt->mapsz * 8)
341 {
342 byte *newmap;
343 node mapnd;
344
345 /* extend tree map */
346
347 newmap = REALLOC(bt->map, byte, bt->mapsz + HFS_MAPXSZ);
348 if (newmap == 0)
349 ERROR(ENOMEM, 0);
350
351 memset(newmap + bt->mapsz, 0, HFS_MAPXSZ);
352
353 bt->map = newmap;
354 bt->mapsz += HFS_MAPXSZ;
355
356 n_init(&mapnd, bt, ndMapNode, 0);
357 if (n_new(&mapnd) == -1)
358 goto fail;
359
360 mapnd.nd.ndNRecs = 1;
361 mapnd.roff[1] = 0x1fa;
362
363 /* link the new map node */
364
365 if (bt->hdrnd.nd.ndFLink == 0)
366 {
367 bt->hdrnd.nd.ndFLink = mapnd.nnum;
368 mapnd.nd.ndBLink = 0;
369 }
370 else
371 {
372 node n;
373 unsigned long nnum;
374
375 nnum = bt->hdrnd.nd.ndFLink;
376
377 while (1)
378 {
379 if (bt_getnode(&n, bt, nnum) == -1)
380 goto fail;
381
382 if (n.nd.ndFLink == 0)
383 break;
384
385 nnum = n.nd.ndFLink;
386 }
387
388 n.nd.ndFLink = mapnd.nnum;
389 mapnd.nd.ndBLink = n.nnum;
390
391 if (bt_putnode(&n) == -1)
392 goto fail;
393 }
394
395 if (bt_putnode(&mapnd) == -1)
396 goto fail;
397 }
398
399 done:
400 return 0;
401
402 fail:
403 return -1;
404 }
405
406 /*
407 * NAME: insertx()
408 * DESCRIPTION: recursively locate a node and insert a record
409 */
410 static
411 int insertx(node *np, byte *record, unsigned int *reclen)
412 {
413 node child;
414 byte *rec;
415 int result = 0;
416
417 if (n_search(np, record))
418 ERROR(EIO, "b*-tree record already exists");
419
420 switch (np->nd.ndType)
421 {
422 case ndIndxNode:
423 if (np->rnum == -1)
424 rec = HFS_NODEREC(*np, 0);
425 else
426 rec = HFS_NODEREC(*np, np->rnum);
427
428 if (bt_getnode(&child, np->bt, d_getul(HFS_RECDATA(rec))) == -1 ||
429 insertx(&child, record, reclen) == -1)
430 goto fail;
431
432 if (np->rnum == -1)
433 {
434 n_index(&child, rec, 0);
435 if (*reclen == 0)
436 {
437 result = bt_putnode(np);
438 goto done;
439 }
440 }
441
442 if (*reclen)
443 result = n_insert(np, record, reclen);
444
445 break;
446
447 case ndLeafNode:
448 result = n_insert(np, record, reclen);
449 break;
450
451 default:
452 ERROR(EIO, "unexpected b*-tree node");
453 }
454
455 done:
456 return result;
457
458 fail:
459 return -1;
460 }
461
462 /*
463 * NAME: btree->insert()
464 * DESCRIPTION: insert a new node record into a tree
465 */
466 int bt_insert(btree *bt, const byte *record, unsigned int reclen)
467 {
468 node root;
469 byte newrec[HFS_MAX_RECLEN];
470
471 if (bt->hdr.bthRoot == 0)
472 {
473 /* create root node */
474
475 n_init(&root, bt, ndLeafNode, 1);
476 if (n_new(&root) == -1 ||
477 bt_putnode(&root) == -1)
478 goto fail;
479
480 bt->hdr.bthDepth = 1;
481 bt->hdr.bthRoot = root.nnum;
482 bt->hdr.bthFNode = root.nnum;
483 bt->hdr.bthLNode = root.nnum;
484
485 bt->flags |= HFS_BT_UPDATE_HDR;
486 }
487 else if (bt_getnode(&root, bt, bt->hdr.bthRoot) == -1)
488 goto fail;
489
490 memcpy(newrec, record, reclen);
491
492 if (insertx(&root, newrec, &reclen) == -1)
493 goto fail;
494
495 if (reclen)
496 {
497 byte oroot[HFS_MAX_RECLEN];
498 unsigned int orootlen;
499
500 /* root node was split; create a new root */
501
502 n_index(&root, oroot, &orootlen);
503
504 n_init(&root, bt, ndIndxNode, root.nd.ndNHeight + 1);
505 if (n_new(&root) == -1)
506 goto fail;
507
508 ++bt->hdr.bthDepth;
509 bt->hdr.bthRoot = root.nnum;
510
511 bt->flags |= HFS_BT_UPDATE_HDR;
512
513 /* insert index records for new root */
514
515 n_search(&root, oroot);
516 n_insertx(&root, oroot, orootlen);
517
518 n_search(&root, newrec);
519 n_insertx(&root, newrec, reclen);
520
521 if (bt_putnode(&root) == -1)
522 goto fail;
523 }
524
525 ++bt->hdr.bthNRecs;
526 bt->flags |= HFS_BT_UPDATE_HDR;
527
528 return 0;
529
530 fail:
531 return -1;
532 }
533
534 /*
535 * NAME: deletex()
536 * DESCRIPTION: recursively locate a node and delete a record
537 */
538 static
539 int deletex(node *np, const byte *key, byte *record, int *flag)
540 {
541 node child;
542 byte *rec;
543 int found, result = 0;
544
545 found = n_search(np, key);
546
547 switch (np->nd.ndType)
548 {
549 case ndIndxNode:
550 if (np->rnum == -1)
551 ERROR(EIO, "b*-tree record not found");
552
553 rec = HFS_NODEREC(*np, np->rnum);
554
555 if (bt_getnode(&child, np->bt, d_getul(HFS_RECDATA(rec))) == -1 ||
556 deletex(&child, key, rec, flag) == -1)
557 goto fail;
558
559 if (*flag)
560 {
561 *flag = 0;
562
563 if (HFS_RECKEYLEN(rec) == 0)
564 {
565 result = n_delete(np, record, flag);
566 break;
567 }
568
569 if (np->rnum == 0)
570 {
571 /* propagate index record change into parent */
572
573 n_index(np, record, 0);
574 *flag = 1;
575 }
576
577 result = bt_putnode(np);
578 }
579
580 break;
581
582 case ndLeafNode:
583 if (found == 0)
584 ERROR(EIO, "b*-tree record not found");
585
586 result = n_delete(np, record, flag);
587 break;
588
589 default:
590 ERROR(EIO, "unexpected b*-tree node");
591 }
592
593 return result;
594
595 fail:
596 return -1;
597 }
598
599 /*
600 * NAME: btree->delete()
601 * DESCRIPTION: remove a node record from a tree
602 */
603 int bt_delete(btree *bt, const byte *key)
604 {
605 node root;
606 byte record[HFS_MAX_RECLEN];
607 int flag = 0;
608
609 if (bt->hdr.bthRoot == 0)
610 ERROR(EIO, "empty b*-tree");
611
612 if (bt_getnode(&root, bt, bt->hdr.bthRoot) == -1 ||
613 deletex(&root, key, record, &flag) == -1)
614 goto fail;
615
616 if (bt->hdr.bthDepth > 1 && root.nd.ndNRecs == 1)
617 {
618 const byte *rec;
619
620 /* root only has one record; eliminate it and decrease the tree depth */
621
622 rec = HFS_NODEREC(root, 0);
623
624 --bt->hdr.bthDepth;
625 bt->hdr.bthRoot = d_getul(HFS_RECDATA(rec));
626
627 if (n_free(&root) == -1)
628 goto fail;
629 }
630 else if (bt->hdr.bthDepth == 1 && root.nd.ndNRecs == 0)
631 {
632 /* root node was deleted */
633
634 bt->hdr.bthDepth = 0;
635 bt->hdr.bthRoot = 0;
636 }
637
638 --bt->hdr.bthNRecs;
639 bt->flags |= HFS_BT_UPDATE_HDR;
640
641 return 0;
642
643 fail:
644 return -1;
645 }
646
647 /*
648 * NAME: btree->search()
649 * DESCRIPTION: locate a data record given a search key
650 */
651 int bt_search(btree *bt, const byte *key, node *np)
652 {
653 int found = 0;
654 unsigned long nnum;
655
656 nnum = bt->hdr.bthRoot;
657
658 if (nnum == 0)
659 ERROR(ENOENT, 0);
660
661 while (1)
662 {
663 const byte *rec;
664
665 if (bt_getnode(np, bt, nnum) == -1)
666 {
667 found = -1;
668 goto fail;
669 }
670
671 found = n_search(np, key);
672
673 switch (np->nd.ndType)
674 {
675 case ndIndxNode:
676 if (np->rnum == -1)
677 ERROR(ENOENT, 0);
678
679 rec = HFS_NODEREC(*np, np->rnum);
680 nnum = d_getul(HFS_RECDATA(rec));
681
682 break;
683
684 case ndLeafNode:
685 if (! found)
686 ERROR(ENOENT, 0);
687
688 goto done;
689
690 default:
691 found = -1;
692 ERROR(EIO, "unexpected b*-tree node");
693 }
694 }
695
696 done:
697 fail:
698 return found;
699 }

  ViewVC Help
Powered by ViewVC 1.1.26