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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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