![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to btree.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Qemu by Fabrice Bellard] / qemu / roms / openbios / fs / hfs|
Return to btree.c CVS log | Up to [Qemu by Fabrice Bellard] / qemu / roms / openbios / fs / hfs |
1.1 root 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: */
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: */
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: */
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: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.