fs/hfs/node.c

/*
 * libhfs - library for reading and writing Macintosh HFS volumes
 * Copyright (C) 1996-1998 Robert Leslie
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 */

# ifdef HAVE_CONFIG_H
#  include "config.h"
# endif

# include <stdlib.h>
# include <string.h>
# include <errno.h>

# include "libhfs.h"
# include "node.h"
# include "data.h"
# include "btree.h"

/* total bytes used by records (NOT including record offsets) */

# define NODEUSED(n)    \
  ((size_t) ((n).roff[(n).nd.ndNRecs] - (n).roff[0]))

/* total bytes available for new records (INCLUDING record offsets) */

# define NODEFREE(n)    \
  ((size_t) (HFS_BLOCKSZ - (n).roff[(n).nd.ndNRecs] -  \
             2 * ((n).nd.ndNRecs + 1)))

/*
 * NAME:        node->init()
 * DESCRIPTION: construct an empty node
 */
void n_init(node *np, btree *bt, int type, int height)
{
  np->bt   = bt;
  np->nnum = (unsigned long) -1;

  np->nd.ndFLink   = 0;
  np->nd.ndBLink   = 0;
  np->nd.ndType    = type;
  np->nd.ndNHeight = height;
  np->nd.ndNRecs   = 0;
  np->nd.ndResv2   = 0;

  np->rnum    = -1;
  np->roff[0] = 0x00e;

  memset(&np->data, 0, sizeof(np->data));
}

/*
 * NAME:        node->new()
 * DESCRIPTION: allocate a new b*-tree node
 */
int n_new(node *np)
{
  btree *bt = np->bt;
  unsigned long num;

  if (bt->hdr.bthFree == 0)
    ERROR(EIO, "b*-tree full");

  num = 0;
  while (num < bt->hdr.bthNNodes && BMTST(bt->map, num))
    ++num;

  if (num == bt->hdr.bthNNodes)
    ERROR(EIO, "free b*-tree node not found");

  np->nnum = num;

  BMSET(bt->map, num);
  --bt->hdr.bthFree;

  bt->flags |= HFS_BT_UPDATE_HDR;

  return 0;

fail:
  return -1;
}

/*
 * NAME:        node->free()
 * DESCRIPTION: deallocate and remove a b*-tree node
 */
int n_free(node *np)
{
  btree *bt = np->bt;
  node sib;

  if (bt->hdr.bthFNode == np->nnum)
    bt->hdr.bthFNode = np->nd.ndFLink;

  if (bt->hdr.bthLNode == np->nnum)
    bt->hdr.bthLNode = np->nd.ndBLink;

  if (np->nd.ndFLink > 0)
    {
      if (bt_getnode(&sib, bt, np->nd.ndFLink) == -1)
        goto fail;

      sib.nd.ndBLink = np->nd.ndBLink;

      if (bt_putnode(&sib) == -1)
        goto fail;
    }

  if (np->nd.ndBLink > 0)
    {
      if (bt_getnode(&sib, bt, np->nd.ndBLink) == -1)
        goto fail;

      sib.nd.ndFLink = np->nd.ndFLink;

      if (bt_putnode(&sib) == -1)
        goto fail;
    }

  BMCLR(bt->map, np->nnum);
  ++bt->hdr.bthFree;

  bt->flags |= HFS_BT_UPDATE_HDR;

  return 0;

fail:
  return -1;
}

/*
 * NAME:        compact()
 * DESCRIPTION: clean up a node, removing deleted records
 */
static
void compact(node *np)
{
  byte *ptr;
  int offset, nrecs, i;

  offset = 0x00e;
  ptr    = np->data + offset;
  nrecs  = 0;

  for (i = 0; i < np->nd.ndNRecs; ++i)
    {
      const byte *rec;
      int reclen;

      rec    = HFS_NODEREC(*np, i);
      reclen = HFS_RECLEN(*np, i);

      if (HFS_RECKEYLEN(rec) > 0)
        {
          np->roff[nrecs++] = offset;
          offset += reclen;

          if (ptr == rec)
            ptr += reclen;
          else
            {
              while (reclen--)
                *ptr++ = *rec++;
            }
        }
    }

  np->roff[nrecs] = offset;
  np->nd.ndNRecs  = nrecs;
}

/*
 * NAME:        node->search()
 * DESCRIPTION: locate a record in a node, or the record it should follow
 */
int n_search(node *np, const byte *pkey)
{
  const btree *bt = np->bt;
  byte key1[HFS_MAX_KEYLEN], key2[HFS_MAX_KEYLEN];
  int i, comp = -1;

  bt->keyunpack(pkey, key2);

  for (i = np->nd.ndNRecs; i--; )
    {
      const byte *rec;

      rec = HFS_NODEREC(*np, i);

      if (HFS_RECKEYLEN(rec) == 0)
        continue;  /* deleted record */

      bt->keyunpack(rec, key1);
      comp = bt->keycompare(key1, key2);

      if (comp <= 0)
        break;
    }

  np->rnum = i;

  return comp == 0;
}

/*
 * NAME:        node->index()
 * DESCRIPTION: create an index record from a key and node pointer
 */
void n_index(const node *np, byte *record, unsigned int *reclen)
{
  const byte *key = HFS_NODEREC(*np, 0);

  if (np->bt == &np->bt->f.vol->cat)
    {
      /* force the key length to be 0x25 */

      HFS_SETKEYLEN(record, 0x25);
      memset(record + 1, 0, 0x25);
      memcpy(record + 1, key + 1, HFS_RECKEYLEN(key));
    }
  else
    memcpy(record, key, HFS_RECKEYSKIP(key));

  d_putul(HFS_RECDATA(record), np->nnum);

  if (reclen)
    *reclen = HFS_RECKEYSKIP(record) + 4;
}

/*
 * NAME:        split()
 * DESCRIPTION: divide a node into two and insert a record
 */
static
int split(node *left, byte *record, unsigned int *reclen)
{
  btree *bt = left->bt;
  node n, *right = &n, *side = 0;
  int mark, i;

  /* create a second node by cloning the first */

  *right = *left;

  if (n_new(right) == -1)
    goto fail;

  left->nd.ndFLink  = right->nnum;
  right->nd.ndBLink = left->nnum;

  /* divide all records evenly between the two nodes */

  mark = (NODEUSED(*left) + 2 * left->nd.ndNRecs + *reclen + 2) >> 1;

  if (left->rnum == -1)
    {
      side  = left;
      mark -= *reclen + 2;
    }

  for (i = 0; i < left->nd.ndNRecs; ++i)
    {
      node *np;
      byte *rec;

      np  = (mark > 0) ? right : left;
      rec = HFS_NODEREC(*np, i);

      mark -= HFS_RECLEN(*np, i) + 2;

      HFS_SETKEYLEN(rec, 0);

      if (left->rnum == i)
        {
          side  = (mark > 0) ? left : right;
          mark -= *reclen + 2;
        }
    }

  compact(left);
  compact(right);

  /* insert the new record and store the modified nodes */

  ASSERT(side);

  n_search(side, record);
  n_insertx(side, record, *reclen);

  if (bt_putnode(left) == -1 ||
      bt_putnode(right) == -1)
    goto fail;

  /* create an index record in the parent for the new node */

  n_index(right, record, reclen);

  /* update link pointers */

  if (bt->hdr.bthLNode == left->nnum)
    {
      bt->hdr.bthLNode = right->nnum;
      bt->flags |= HFS_BT_UPDATE_HDR;
    }

  if (right->nd.ndFLink > 0)
    {
      node sib;

      if (bt_getnode(&sib, right->bt, right->nd.ndFLink) == -1)
        goto fail;

      sib.nd.ndBLink = right->nnum;

      if (bt_putnode(&sib) == -1)
        goto fail;
    }

  return 0;

fail:
  return -1;
}

/*
 * NAME:        node->insertx()
 * DESCRIPTION: insert a record into a node (which must already have room)
 */
void n_insertx(node *np, const byte *record, unsigned int reclen)
{
  int rnum, i;
  byte *ptr;

  rnum = np->rnum + 1;

  /* push other records down to make room */

  for (ptr = HFS_NODEREC(*np, np->nd.ndNRecs) + reclen;
       ptr > HFS_NODEREC(*np, rnum) + reclen; --ptr)
    *(ptr - 1) = *(ptr - 1 - reclen);

  ++np->nd.ndNRecs;

  for (i = np->nd.ndNRecs; i > rnum; --i)
    np->roff[i] = np->roff[i - 1] + reclen;

  /* write the new record */

  memcpy(HFS_NODEREC(*np, rnum), record, reclen);
}

/*
 * NAME:        node->insert()
 * DESCRIPTION: insert a new record into a node; return a record for parent
 */
int n_insert(node *np, byte *record, unsigned int *reclen)
{
  /* check for free space */

  if (np->nd.ndNRecs >= HFS_MAX_NRECS ||
      *reclen + 2 > NODEFREE(*np))
    return split(np, record, reclen);

  n_insertx(np, record, *reclen);
  *reclen = 0;

  return bt_putnode(np);
}

/*
 * NAME:        join()
 * DESCRIPTION: combine two nodes into a single node
 */
static
int join(node *left, node *right, byte *record, int *flag)
{
  int i, offset;

  /* copy records and offsets */

  memcpy(HFS_NODEREC(*left, left->nd.ndNRecs),
         HFS_NODEREC(*right, 0), NODEUSED(*right));

  offset = left->roff[left->nd.ndNRecs] - right->roff[0];

  for (i = 1; i <= right->nd.ndNRecs; ++i)
    left->roff[++left->nd.ndNRecs] = offset + right->roff[i];

  if (bt_putnode(left) == -1)
    goto fail;

  /* eliminate node and update link pointers */

  if (n_free(right) == -1)
    goto fail;

  HFS_SETKEYLEN(record, 0);
  *flag = 1;

  return 0;

fail:
  return -1;
}

/*
 * NAME:        node->delete()
 * DESCRIPTION: remove a record from a node
 */
int n_delete(node *np, byte *record, int *flag)
{
  byte *rec;

  rec = HFS_NODEREC(*np, np->rnum);

  HFS_SETKEYLEN(rec, 0);
  compact(np);

  if (np->nd.ndNRecs == 0)
    {
      if (n_free(np) == -1)
        goto fail;

      HFS_SETKEYLEN(record, 0);
      *flag = 1;

      return 0;
    }

  /* see if we can join with our left sibling */

  if (np->nd.ndBLink > 0)
    {
      node left;

      if (bt_getnode(&left, np->bt, np->nd.ndBLink) == -1)
        goto fail;

      if (np->nd.ndNRecs + left.nd.ndNRecs <= HFS_MAX_NRECS &&
          NODEUSED(*np) + 2 * np->nd.ndNRecs <= NODEFREE(left))
        return join(&left, np, record, flag);
    }

  if (np->rnum == 0)
    {
      /* special case: first record changed; update parent record key */

      n_index(np, record, 0);
      *flag = 1;
    }

  return bt_putnode(np);

fail:
  return -1;
}
1	dpavlin	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 "node.h"
31			# include "data.h"
32			# include "btree.h"
33
34			/* total bytes used by records (NOT including record offsets) */
35
36			# define NODEUSED(n) \
37			((size_t) ((n).roff[(n).nd.ndNRecs] - (n).roff[0]))
38
39			/* total bytes available for new records (INCLUDING record offsets) */
40
41			# define NODEFREE(n) \
42			((size_t) (HFS_BLOCKSZ - (n).roff[(n).nd.ndNRecs] - \
43			2 * ((n).nd.ndNRecs + 1)))
44
45			/*
46			* NAME: node->init()
47			* DESCRIPTION: construct an empty node
48			*/
49			void n_init(node np, btree bt, int type, int height)
50			{
51			np->bt = bt;
52			np->nnum = (unsigned long) -1;
53
54			np->nd.ndFLink = 0;
55			np->nd.ndBLink = 0;
56			np->nd.ndType = type;
57			np->nd.ndNHeight = height;
58			np->nd.ndNRecs = 0;
59			np->nd.ndResv2 = 0;
60
61			np->rnum = -1;
62			np->roff[0] = 0x00e;
63
64			memset(&np->data, 0, sizeof(np->data));
65			}
66
67			/*
68			* NAME: node->new()
69			* DESCRIPTION: allocate a new b*-tree node
70			*/
71			int n_new(node *np)
72			{
73			btree *bt = np->bt;
74			unsigned long num;
75
76			if (bt->hdr.bthFree == 0)
77			ERROR(EIO, "b*-tree full");
78
79			num = 0;
80			while (num < bt->hdr.bthNNodes && BMTST(bt->map, num))
81			++num;
82
83			if (num == bt->hdr.bthNNodes)
84			ERROR(EIO, "free b*-tree node not found");
85
86			np->nnum = num;
87
88			BMSET(bt->map, num);
89			--bt->hdr.bthFree;
90
91			bt->flags \|= HFS_BT_UPDATE_HDR;
92
93			return 0;
94
95			fail:
96			return -1;
97			}
98
99			/*
100			* NAME: node->free()
101			* DESCRIPTION: deallocate and remove a b*-tree node
102			*/
103			int n_free(node *np)
104			{
105			btree *bt = np->bt;
106			node sib;
107
108			if (bt->hdr.bthFNode == np->nnum)
109			bt->hdr.bthFNode = np->nd.ndFLink;
110
111			if (bt->hdr.bthLNode == np->nnum)
112			bt->hdr.bthLNode = np->nd.ndBLink;
113
114			if (np->nd.ndFLink > 0)
115			{
116			if (bt_getnode(&sib, bt, np->nd.ndFLink) == -1)
117			goto fail;
118
119			sib.nd.ndBLink = np->nd.ndBLink;
120
121			if (bt_putnode(&sib) == -1)
122			goto fail;
123			}
124
125			if (np->nd.ndBLink > 0)
126			{
127			if (bt_getnode(&sib, bt, np->nd.ndBLink) == -1)
128			goto fail;
129
130			sib.nd.ndFLink = np->nd.ndFLink;
131
132			if (bt_putnode(&sib) == -1)
133			goto fail;
134			}
135
136			BMCLR(bt->map, np->nnum);
137			++bt->hdr.bthFree;
138
139			bt->flags \|= HFS_BT_UPDATE_HDR;
140
141			return 0;
142
143			fail:
144			return -1;
145			}
146
147			/*
148			* NAME: compact()
149			* DESCRIPTION: clean up a node, removing deleted records
150			*/
151			static
152			void compact(node *np)
153			{
154			byte *ptr;
155			int offset, nrecs, i;
156
157			offset = 0x00e;
158			ptr = np->data + offset;
159			nrecs = 0;
160
161			for (i = 0; i < np->nd.ndNRecs; ++i)
162			{
163			const byte *rec;
164			int reclen;
165
166			rec = HFS_NODEREC(*np, i);
167			reclen = HFS_RECLEN(*np, i);
168
169			if (HFS_RECKEYLEN(rec) > 0)
170			{
171			np->roff[nrecs++] = offset;
172			offset += reclen;
173
174			if (ptr == rec)
175			ptr += reclen;
176			else
177			{
178			while (reclen--)
179			ptr++ = rec++;
180			}
181			}
182			}
183
184			np->roff[nrecs] = offset;
185			np->nd.ndNRecs = nrecs;
186			}
187
188			/*
189			* NAME: node->search()
190			* DESCRIPTION: locate a record in a node, or the record it should follow
191			*/
192			int n_search(node np, const byte pkey)
193			{
194			const btree *bt = np->bt;
195			byte key1[HFS_MAX_KEYLEN], key2[HFS_MAX_KEYLEN];
196			int i, comp = -1;
197
198			bt->keyunpack(pkey, key2);
199
200			for (i = np->nd.ndNRecs; i--; )
201			{
202			const byte *rec;
203
204			rec = HFS_NODEREC(*np, i);
205
206			if (HFS_RECKEYLEN(rec) == 0)
207			continue; /* deleted record */
208
209			bt->keyunpack(rec, key1);
210			comp = bt->keycompare(key1, key2);
211
212			if (comp <= 0)
213			break;
214			}
215
216			np->rnum = i;
217
218			return comp == 0;
219			}
220
221			/*
222			* NAME: node->index()
223			* DESCRIPTION: create an index record from a key and node pointer
224			*/
225			void n_index(const node np, byte record, unsigned int *reclen)
226			{
227			const byte key = HFS_NODEREC(np, 0);
228
229			if (np->bt == &np->bt->f.vol->cat)
230			{
231			/* force the key length to be 0x25 */
232
233			HFS_SETKEYLEN(record, 0x25);
234			memset(record + 1, 0, 0x25);
235			memcpy(record + 1, key + 1, HFS_RECKEYLEN(key));
236			}
237			else
238			memcpy(record, key, HFS_RECKEYSKIP(key));
239
240			d_putul(HFS_RECDATA(record), np->nnum);
241
242			if (reclen)
243			*reclen = HFS_RECKEYSKIP(record) + 4;
244			}
245
246			/*
247			* NAME: split()
248			* DESCRIPTION: divide a node into two and insert a record
249			*/
250			static
251			int split(node left, byte record, unsigned int *reclen)
252			{
253			btree *bt = left->bt;
254			node n, right = &n, side = 0;
255			int mark, i;
256
257			/* create a second node by cloning the first */
258
259			right = left;
260
261			if (n_new(right) == -1)
262			goto fail;
263
264			left->nd.ndFLink = right->nnum;
265			right->nd.ndBLink = left->nnum;
266
267			/* divide all records evenly between the two nodes */
268
269			mark = (NODEUSED(left) + 2 left->nd.ndNRecs + *reclen + 2) >> 1;
270
271			if (left->rnum == -1)
272			{
273			side = left;
274			mark -= *reclen + 2;
275			}
276
277			for (i = 0; i < left->nd.ndNRecs; ++i)
278			{
279			node *np;
280			byte *rec;
281
282			np = (mark > 0) ? right : left;
283			rec = HFS_NODEREC(*np, i);
284
285			mark -= HFS_RECLEN(*np, i) + 2;
286
287			HFS_SETKEYLEN(rec, 0);
288
289			if (left->rnum == i)
290			{
291			side = (mark > 0) ? left : right;
292			mark -= *reclen + 2;
293			}
294			}
295
296			compact(left);
297			compact(right);
298
299			/* insert the new record and store the modified nodes */
300
301			ASSERT(side);
302
303			n_search(side, record);
304			n_insertx(side, record, *reclen);
305
306			if (bt_putnode(left) == -1 \|\|
307			bt_putnode(right) == -1)
308			goto fail;
309
310			/* create an index record in the parent for the new node */
311
312			n_index(right, record, reclen);
313
314			/* update link pointers */
315
316			if (bt->hdr.bthLNode == left->nnum)
317			{
318			bt->hdr.bthLNode = right->nnum;
319			bt->flags \|= HFS_BT_UPDATE_HDR;
320			}
321
322			if (right->nd.ndFLink > 0)
323			{
324			node sib;
325
326			if (bt_getnode(&sib, right->bt, right->nd.ndFLink) == -1)
327			goto fail;
328
329			sib.nd.ndBLink = right->nnum;
330
331			if (bt_putnode(&sib) == -1)
332			goto fail;
333			}
334
335			return 0;
336
337			fail:
338			return -1;
339			}
340
341			/*
342			* NAME: node->insertx()
343			* DESCRIPTION: insert a record into a node (which must already have room)
344			*/
345			void n_insertx(node np, const byte record, unsigned int reclen)
346			{
347			int rnum, i;
348			byte *ptr;
349
350			rnum = np->rnum + 1;
351
352			/* push other records down to make room */
353
354			for (ptr = HFS_NODEREC(*np, np->nd.ndNRecs) + reclen;
355			ptr > HFS_NODEREC(*np, rnum) + reclen; --ptr)
356			(ptr - 1) = (ptr - 1 - reclen);
357
358			++np->nd.ndNRecs;
359
360			for (i = np->nd.ndNRecs; i > rnum; --i)
361			np->roff[i] = np->roff[i - 1] + reclen;
362
363			/* write the new record */
364
365			memcpy(HFS_NODEREC(*np, rnum), record, reclen);
366			}
367
368			/*
369			* NAME: node->insert()
370			* DESCRIPTION: insert a new record into a node; return a record for parent
371			*/
372			int n_insert(node np, byte record, unsigned int *reclen)
373			{
374			/* check for free space */
375
376			if (np->nd.ndNRecs >= HFS_MAX_NRECS \|\|
377			reclen + 2 > NODEFREE(np))
378			return split(np, record, reclen);
379
380			n_insertx(np, record, *reclen);
381			*reclen = 0;
382
383			return bt_putnode(np);
384			}
385
386			/*
387			* NAME: join()
388			* DESCRIPTION: combine two nodes into a single node
389			*/
390			static
391			int join(node left, node right, byte record, int flag)
392			{
393			int i, offset;
394
395			/* copy records and offsets */
396
397			memcpy(HFS_NODEREC(*left, left->nd.ndNRecs),
398			HFS_NODEREC(right, 0), NODEUSED(right));
399
400			offset = left->roff[left->nd.ndNRecs] - right->roff[0];
401
402			for (i = 1; i <= right->nd.ndNRecs; ++i)
403			left->roff[++left->nd.ndNRecs] = offset + right->roff[i];
404
405			if (bt_putnode(left) == -1)
406			goto fail;
407
408			/* eliminate node and update link pointers */
409
410			if (n_free(right) == -1)
411			goto fail;
412
413			HFS_SETKEYLEN(record, 0);
414			*flag = 1;
415
416			return 0;
417
418			fail:
419			return -1;
420			}
421
422			/*
423			* NAME: node->delete()
424			* DESCRIPTION: remove a record from a node
425			*/
426			int n_delete(node np, byte record, int *flag)
427			{
428			byte *rec;
429
430			rec = HFS_NODEREC(*np, np->rnum);
431
432			HFS_SETKEYLEN(rec, 0);
433			compact(np);
434
435			if (np->nd.ndNRecs == 0)
436			{
437			if (n_free(np) == -1)
438			goto fail;
439
440			HFS_SETKEYLEN(record, 0);
441			*flag = 1;
442
443			return 0;
444			}
445
446			/* see if we can join with our left sibling */
447
448			if (np->nd.ndBLink > 0)
449			{
450			node left;
451
452			if (bt_getnode(&left, np->bt, np->nd.ndBLink) == -1)
453			goto fail;
454
455			if (np->nd.ndNRecs + left.nd.ndNRecs <= HFS_MAX_NRECS &&
456			NODEUSED(np) + 2 np->nd.ndNRecs <= NODEFREE(left))
457			return join(&left, np, record, flag);
458			}
459
460			if (np->rnum == 0)
461			{
462			/* special case: first record changed; update parent record key */
463
464			n_index(np, record, 0);
465			*flag = 1;
466			}
467
468			return bt_putnode(np);
469
470			fail:
471			return -1;
472			}