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., 51 Franklin Street - Fifth Floor, Boston,
18 * MA 02110-1301, USA.
19 *
20 * $Id: btree.c,v 1.10 1998/11/02 22:08:54 rob Exp $
21 */
22
23 #include "config.h"
24
25 #include "libhfs.h"
26 #include "btree.h"
27 #include "data.h"
28 #include "file.h"
29 #include "block.h"
30 #include "node.h"
31
32 /*
33 * NAME: btree->getnode()
34 * DESCRIPTION: retrieve a numbered node from a B*-tree file
35 */
bt_getnode(node * np,btree * bt,unsigned long nnum)36 int bt_getnode(node *np, btree *bt, unsigned long nnum)
37 {
38 block *bp = &np->data;
39 const byte *ptr;
40 int i;
41
42 np->bt = bt;
43 np->nnum = nnum;
44
45 # if 0
46 fprintf(stderr, "BTREE: GET vol \"%s\" btree \"%s\" node %lu\n",
47 bt->f.vol->mdb.drVN, bt->f.name, np->nnum);
48 # endif
49
50 /* verify the node exists and is marked as in-use */
51
52 if (nnum > 0 && nnum >= bt->hdr.bthNNodes)
53 ERROR(EIO, "read nonexistent b*-tree node");
54 else if (bt->map && ! BMTST(bt->map, nnum))
55 ERROR(EIO, "read unallocated b*-tree node");
56
57 if (f_getblock(&bt->f, nnum, bp) == -1)
58 goto fail;
59
60 ptr = *bp;
61
62 d_fetchul(&ptr, &np->nd.ndFLink);
63 d_fetchul(&ptr, &np->nd.ndBLink);
64 d_fetchsb(&ptr, &np->nd.ndType);
65 d_fetchsb(&ptr, &np->nd.ndNHeight);
66 d_fetchuw(&ptr, &np->nd.ndNRecs);
67 d_fetchsw(&ptr, &np->nd.ndResv2);
68
69 if (np->nd.ndNRecs > HFS_MAX_NRECS)
70 ERROR(EIO, "too many b*-tree node records");
71
72 i = np->nd.ndNRecs + 1;
73
74 ptr = *bp + HFS_BLOCKSZ - (2 * i);
75
76 while (i--)
77 d_fetchuw(&ptr, &np->roff[i]);
78
79 return 0;
80
81 fail:
82 return -1;
83 }
84
85
86 /*
87 * NAME: btree->readhdr()
88 * DESCRIPTION: read the header node of a B*-tree
89 */
bt_readhdr(btree * bt)90 int bt_readhdr(btree *bt)
91 {
92 const byte *ptr;
93 byte *map = NULL;
94 int i;
95 unsigned long nnum;
96
97 if (bt_getnode(&bt->hdrnd, bt, 0) == -1)
98 goto fail;
99
100 if (bt->hdrnd.nd.ndType != ndHdrNode ||
101 bt->hdrnd.nd.ndNRecs != 3 ||
102 bt->hdrnd.roff[0] != 0x00e ||
103 bt->hdrnd.roff[1] != 0x078 ||
104 bt->hdrnd.roff[2] != 0x0f8 ||
105 bt->hdrnd.roff[3] != 0x1f8)
106 ERROR(EIO, "malformed b*-tree header node");
107
108 /* read header record */
109
110 ptr = HFS_NODEREC(bt->hdrnd, 0);
111
112 d_fetchuw(&ptr, &bt->hdr.bthDepth);
113 d_fetchul(&ptr, &bt->hdr.bthRoot);
114 d_fetchul(&ptr, &bt->hdr.bthNRecs);
115 d_fetchul(&ptr, &bt->hdr.bthFNode);
116 d_fetchul(&ptr, &bt->hdr.bthLNode);
117 d_fetchuw(&ptr, &bt->hdr.bthNodeSize);
118 d_fetchuw(&ptr, &bt->hdr.bthKeyLen);
119 d_fetchul(&ptr, &bt->hdr.bthNNodes);
120 d_fetchul(&ptr, &bt->hdr.bthFree);
121
122 for (i = 0; i < 76; ++i)
123 d_fetchsb(&ptr, &bt->hdr.bthResv[i]);
124
125 if (bt->hdr.bthNodeSize != HFS_BLOCKSZ)
126 ERROR(EINVAL, "unsupported b*-tree node size");
127
128 /* read map record; construct btree bitmap */
129 /* don't set bt->map until we're done, since getnode() checks it */
130
131 map = ALLOC(byte, HFS_MAP1SZ);
132 if (map == NULL)
133 ERROR(ENOMEM, NULL);
134
135 memcpy(map, HFS_NODEREC(bt->hdrnd, 2), HFS_MAP1SZ);
136 bt->mapsz = HFS_MAP1SZ;
137
138 /* read continuation map records, if any */
139
140 nnum = bt->hdrnd.nd.ndFLink;
141
142 while (nnum)
143 {
144 node n;
145 byte *newmap;
146
147 if (bt_getnode(&n, bt, nnum) == -1)
148 goto fail;
149
150 if (n.nd.ndType != ndMapNode ||
151 n.nd.ndNRecs != 1 ||
152 n.roff[0] != 0x00e ||
153 n.roff[1] != 0x1fa)
154 ERROR(EIO, "malformed b*-tree map node");
155
156 newmap = REALLOC(map, byte, bt->mapsz + HFS_MAPXSZ);
157 if (newmap == NULL)
158 ERROR(ENOMEM, NULL);
159
160 map = newmap;
161
162 memcpy(map + bt->mapsz, HFS_NODEREC(n, 0), HFS_MAPXSZ);
163 bt->mapsz += HFS_MAPXSZ;
164
165 nnum = n.nd.ndFLink;
166 }
167
168 bt->map = map;
169
170 return 0;
171
172 fail:
173 FREE(map);
174 return -1;
175 }
176
177
178 /*
179 * NAME: btree->search()
180 * DESCRIPTION: locate a data record given a search key
181 */
bt_search(btree * bt,const byte * key,node * np)182 int bt_search(btree *bt, const byte *key, node *np)
183 {
184 int found = 0;
185 unsigned long nnum;
186
187 nnum = bt->hdr.bthRoot;
188
189 if (nnum == 0)
190 ERROR(ENOENT, NULL);
191
192 while (1)
193 {
194 const byte *rec;
195
196 if (bt_getnode(np, bt, nnum) == -1)
197 {
198 found = -1;
199 goto fail;
200 }
201
202 found = n_search(np, key);
203
204 switch (np->nd.ndType)
205 {
206 case ndIndxNode:
207 if (np->rnum == -1)
208 ERROR(ENOENT, NULL);
209
210 rec = HFS_NODEREC(*np, np->rnum);
211 nnum = d_getul(HFS_RECDATA(rec));
212
213 break;
214
215 case ndLeafNode:
216 if (! found)
217 ERROR(ENOENT, NULL);
218
219 goto done;
220
221 default:
222 found = -1;
223 ERROR(EIO, "unexpected b*-tree node");
224 }
225 }
226
227 done:
228 fail:
229 return found;
230 }
231