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 */
36void 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 */
58int 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 */
93void 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 */
107void 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 */
147int 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 */
176void 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 */
200int 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 */
322void 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 */
349int 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 */
369int 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 */
424int 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