fs/hfsplus/btree.c

/*
 * libhfs - library for reading and writing Macintosh HFS volumes
 * The fucntions are used to handle the various forms of btrees
 * found on HFS+ volumes.
 *
 * The functions are used to handle the various forms of btrees
 * found on HFS+ volumes.
 *
 * Copyright (C) 2000 Klaus Halfmann <klaus.halfmann@feri.de>
 * Original 1996-1998 Robert Leslie <rob@mars.org>
 * Additional work by  Brad Boyer (flar@pants.nu)  
 *
 * 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 <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <limits.h>
# include <errno.h>

# include "libhfsp.h"
# include "volume.h"
# include "btree.h"
# include "record.h"
# include "swab.h"

#ifdef HAVE_MEMSET
#    define bzero(_a_,_s_) memset (_a_,0,_s_)
#endif

/* Read the node from the given buffer and swap the bytes.
 *
 * return pointer after reading the structure
 */
char* btree_readnode(btree_node_desc* node, char *p)
{
    node->next      = bswabU32_inc(&p);
    node->prev      = bswabU32_inc(&p);
    node->kind      = bswabU8_inc(&p);
    node->height    = bswabU8_inc(&p);
    node->num_rec   = bswabU16_inc(&p);
    node->reserved  = bswabU16_inc(&p);
    return p;
} 

/* Write the node to the given buffer and swap the bytes.
 *
 * return pointer after writing the structure
 */
char* btree_writenode(btree_node_desc* node, char *p)
{
    bstoreU32_inc(&p, node->next);
    bstoreU32_inc(&p, node->prev);
    bstoreU8_inc (&p, node->kind);
    bstoreU8_inc (&p, node->height);
    bstoreU16_inc(&p, node->num_rec);
    bstoreU16_inc(&p, node->reserved);
    return p;
} 


/* read a btree header from the given buffer and swap the bytes.
 *
 * return pointer after reading the structure
 */
char* btree_readhead(btree_head* head, char *p)
{
    int i;
    head->depth         = bswabU16_inc(&p);
    head->root          = bswabU32_inc(&p);
    head->leaf_count    = bswabU32_inc(&p);
    head->leaf_head     = bswabU32_inc(&p);
    head->leaf_tail     = bswabU32_inc(&p);
    head->node_size     = bswabU16_inc(&p);
    head->max_key_len   = bswabU16_inc(&p);
    head->node_count    = bswabU32_inc(&p);
    head->free_nodes    = bswabU32_inc(&p);
    head->reserved1     = bswabU16_inc(&p);
    head->clump_size    = bswabU32_inc(&p);
    head->btree_type    = bswabU8_inc(&p);
    head->reserved2     = bswabU8_inc(&p);
    head->attributes    = bswabU32_inc(&p);
    for (i=0; i < 16; i++)
        head->reserved3[i] = bswabU32_inc(&p);
    return p;
}

/* read a btree header from the given buffer and swap the bytes.
 *
 * return pointer after reading the structure
 */
char* btree_writehead(btree_head* head, char *p)
{
    int i;
    bstoreU16_inc(&p, head->depth);
    bstoreU32_inc(&p, head->root);
    bstoreU32_inc(&p, head->leaf_count);
    bstoreU32_inc(&p, head->leaf_head);
    bstoreU32_inc(&p, head->leaf_tail);
    bstoreU16_inc(&p, head->node_size);
    bstoreU16_inc(&p, head->max_key_len);
    bstoreU32_inc(&p, head->node_count);
    bstoreU32_inc(&p, head->free_nodes);
    bstoreU16_inc(&p, head->reserved1);
    bstoreU32_inc(&p, head->clump_size);
    bstoreU8_inc (&p, head->btree_type);
    bstoreU8_inc (&p, head->reserved2);
    bstoreU32_inc(&p, head->attributes);
    for (i=0; i < 16; i++)
        bstoreU32_inc(&p, head->reserved3[i]);
    return p;
}

/* Intialize cache with default cache Size, 
 * must call node_cache_close to deallocate memory */
int node_cache_init(node_cache* cache, btree* tree, int size)
{
    int nodebufsize;
    char * buf;

    cache->size         = size;
    cache->currindex    = 0;
    nodebufsize = tree->head.node_size + sizeof(node_buf);
    buf = malloc(size *(sizeof(node_entry) + nodebufsize));
    if (!buf)
        return -1;
    cache -> nodebufsize = nodebufsize;
    cache -> entries = (node_entry*) buf;
    cache -> buffers = (char*) &cache->entries[size];
    bzero(cache->entries, size*sizeof(node_entry));
    return 0;
}

/* Like cache->buffers[i], since size of node_buf is variable */
static inline node_buf* node_buf_get(node_cache* cache, int i)
{
    return (node_buf*) (cache->buffers + (i * cache->nodebufsize));
}


/* write back a node at given node in fork with nodebuf */
static int btree_write_node(btree* bt, int index, char* nodebuf)
{
    UInt16      blkpernode  = bt->blkpernode;
    UInt16      nodeperblk  = bt->nodeperblk;

    if (blkpernode)
    {
        return volume_writetofork(bt->vol, nodebuf, bt->fork, 
                     index * blkpernode, blkpernode, HFSP_EXTENT_DATA, bt->cnid);
    }
    else // use nodeperblk, must reread other blocks, too
    {
        char buf[bt->vol->blksize];
        
        UInt16  node_size = bt->head.node_size;
        UInt16  offset    = (index % nodeperblk) * node_size;
        int     block     = index / nodeperblk;

        // read block including this one 
        void* p  = volume_readfromfork(bt->vol, buf, bt->fork, 
                     block, 1, HFSP_EXTENT_DATA, bt->cnid);
        if (p != buf)       // usually NULL
            return -1;      // evil ...
        p = &nodebuf[offset];   // node is found at that offset
        memcpy(p, nodebuf, node_size);
        if (volume_writetofork(bt->vol, buf, bt->fork, 
                     block, 1, HFSP_EXTENT_DATA, bt->cnid))
            return -1;  // evil ...
    }
    return 0; // all is fine
}

/* flush the node at cache index */
static int node_cache_flush_node(btree* bt, int index)
{
    node_entry  *e          = &bt->cache.entries[index];
    int         result      = 0;
    int         node_index  = e->index;

    // Only write back valid, dirty nodes
    if(e->index && (e->flags & NODE_DIRTY))
    {
        node_buf* b = node_buf_get(&bt->cache, index);
        if (!b->index)
        {
            hfsp_error = "cache inconsistency in node_cache_flush_node";
            return -1;
        }
        // Write back node header to cached memory
        btree_writenode(&b->desc, b->node);
        result = btree_write_node(bt, node_index, b->node);
        b->index = 0;   // invalidate block entry
    }
    e->index = 0;       // invalidate cache entry
    return result; // all is fine
}

/* flush the cache */
static int node_cache_flush(btree* bt)
{
    int i, size = bt->cache.size;
    int result = 0;

    for (i=0; i < size; i++)
    {
        node_entry* e = &bt->cache.entries[i];
        if(e->index && (e->flags & NODE_DIRTY))
            if (node_cache_flush_node(bt, i))
                result = -1;
    }
    return result;
}

static int node_cache_close(btree* bt)
{
    int result = 0;
    if (!bt->cache.entries) // not (fully) intialized ?
        return result;
    result = node_cache_flush(bt);
    free(bt->cache.entries);
    return result;
}

/* Load the cach node indentified by index with 
 * the node identified by node_index.
 *
 * Set the inital flags as given.
 */

static node_buf* node_cache_load_buf
    (btree* bt, node_cache* cache, int index, UInt16 node_index, int flags)
{
    node_buf    *result     = node_buf_get(cache ,index);
    UInt16      blkpernode  = bt->blkpernode;
    UInt16      nodeperblk  = bt->nodeperblk;
    node_entry  *e          = &cache->entries[index];
    UInt32      block;
    void        *p;

    if (blkpernode)
    {
        block = node_index * blkpernode;
        p     = volume_readfromfork(bt->vol, result->node, bt->fork, 
                     block, blkpernode, HFSP_EXTENT_DATA, bt->cnid);
        if (!p)
            return NULL;        // evil ...
        
        btree_readnode(&result->desc, p);
    }
    else // use nodeperblk
    {
        char buf[bt->vol->blksize];
        
        UInt16 node_size = bt->head.node_size;
        UInt16 offset = node_index % nodeperblk * node_size;
        block = node_index / nodeperblk;
        p     = volume_readfromfork(bt->vol, buf, bt->fork, 
                     block, 1, HFSP_EXTENT_DATA, bt->cnid);
        if (p != buf)           // usually NULL
            return NULL;        // evil ...
        p = &buf[offset];   // node is found at that offset
        memcpy(&result->node, p , node_size);
        btree_readnode(&result->desc, p);
        
    }

    result->index   = node_index;

    e -> priority   = result->desc.height * DEPTH_FACTOR;
    e -> index      = node_index;
    e -> flags      = flags;
    return result;
}

/* Mark node at given index dirty in cache.
 */
inline static void btree_dirty_node(btree* bt, UInt16 index)
{
    node_cache* cache   = &bt->cache;
    node_entry  *e      = &cache->entries[index];
    e->flags |= NODE_DIRTY;
}

/* Read node at given index, using cache.
 *
 * Make node with given flag, usually NODE_CLEAN/NODE_DIRTY
 */
node_buf* btree_node_by_index(btree* bt, UInt16 index, int flags)
{
    node_cache* cache = &bt->cache;
    int         oldindex, lruindex;
    int         currindex = cache->currindex;
    UInt32      prio;
    node_entry  *e;

    // Shortcut acces to current node, will not change priorities
    if (cache->entries[currindex].index == index)
    {
        cache->entries[currindex].flags |= flags;
        return node_buf_get(cache ,currindex);
    }
    oldindex = currindex;
    if (currindex == 0)
        currindex = cache->size;
    currindex--;
    lruindex = oldindex;            // entry to be flushed when needed
    prio     = 0;                   // current priority
    while (currindex != oldindex)   // round robin
    {
        e = &cache->entries[currindex];
        if (e->index == index)      // got it
        {
            if (e->priority != 0)   // already top, uuh
                e->priority--;
            cache->currindex = currindex;
            e -> flags      |= flags;
            return node_buf_get(cache ,currindex);
        }
        else
        {
            if (!e->index) // free entry, well
            {
                lruindex = currindex;
                prio     = UINT_MAX; // remember empty entry
            }
            if (e->priority != UINT_MAX) // already least, uuh
                e->priority++;
        }
        if (prio < e->priority)
        {
            lruindex = currindex;
            prio     = e->priority;
        }
        if (currindex == 0)
            currindex = cache->size;
        currindex--;
    }
    e = &cache->entries[lruindex];
    cache->currindex = lruindex;
    if (e->flags & NODE_DIRTY)
           node_cache_flush_node(bt, lruindex);
    return node_cache_load_buf  (bt, cache, lruindex, index, flags);
}

/** intialize the btree with the first entry in the fork */
static int btree_init(btree* bt, volume* vol, hfsp_fork_raw* fork)
{ 
    char                *p;
    char                buf[vol->blksize]; 
    UInt16              node_size;
    btree_node_desc*    node = &bt->head_node;
    int                 alloc_size;

    bt->vol     = vol;
    bt->fork    = fork;
    p   = volume_readfromfork(vol, buf, fork, 0, 1,
                 HFSP_EXTENT_DATA, bt->cnid);
    if (!p)
        return -1;
    p = btree_readnode(node, p);
    if (node->kind != HFSP_NODE_HEAD)
        return -1;   // should not happen ?
    p = btree_readhead(&bt->head, p);
    node_size   = bt->head.node_size;

    bt->blkpernode = node_size / vol->blksize;

    if (bt->blkpernode == 0)    // maybe the other way round ?
        bt->nodeperblk = vol->blksize / node_size;

    alloc_size = node_size - HEADER_RESERVEDOFFSET; // sizeof(node_desc) + sizeof(header) 
    /* Sometimes the node_size is bigger than the volume-blocksize
     * so here I reread the node when needed */
    { // need new block for allocation
        char nodebuf[node_size];
        if (bt->blkpernode > 1)
        {
            p = volume_readfromfork(vol, nodebuf, fork, 0, bt->blkpernode,
                 HFSP_EXTENT_DATA, bt->cnid);
            p += HEADER_RESERVEDOFFSET; // skip header
        }
        
        bt->alloc_bits = malloc(alloc_size);
        if (!bt->alloc_bits)
            return ENOMEM;
        memcpy(bt->alloc_bits, p, alloc_size);
    }

    /*** for debugging ***/ 
    bt->attributes = 0;

    if (node_cache_init(&bt->cache, bt, bt->head.depth + EXTRA_CACHESIZE))
        return -1;

    return 0;
}

/** Intialize catalog btree, so that btree_close can safely be called. */
void btree_reset(btree* bt)
{
    bt->alloc_bits    = NULL;
    bt->cache.entries = NULL;
}
 
/** Intialize catalog btree */
int btree_init_cat(btree* bt, volume* vol, hfsp_fork_raw* fork)
{ 
    int result = btree_init(bt,vol,fork);       // super (...)
    bt->cnid  = HFSP_CAT_CNID;
    bt->kcomp = record_key_compare;
    bt->kread = record_readkey;
    bt->rread = record_readentry;
    bt->max_rec_size = sizeof(hfsp_cat_entry);
        // this is a bit too large due to alignment/padding
    return result;
}

/** Intialize catalog btree */
int btree_init_extent(btree* bt, volume* vol, hfsp_fork_raw* fork)
{ 
    int result = btree_init(bt,vol,fork);       // super (...)
    bt->cnid  = HFSP_EXT_CNID;
    bt->kcomp = record_extent_key_compare;
    bt->kread = record_extent_readkey;
    bt->rread = record_extent_readrecord;
    bt->max_rec_size = sizeof(hfsp_extent);
    return result;
}

/** close the btree and free any resources */
int btree_close(btree* bt)
{
    int result = 0;
    
    node_cache_close(bt);
    // a dirty header without alloc_bits must not happen, mmh
    if ((bt->attributes & BTREE_HEADDIRTY) && bt->alloc_bits)
    {
        btree_head*         head        = &bt->head;
        btree_node_desc*    node        = &bt->head_node;
        UInt16              node_size   = head->node_size; 
        UInt16              alloc_size  = node_size - HEADER_RESERVEDOFFSET; 
        char                buf[node_size];
        void                *p;
        
        p = btree_writenode(node, buf);
        p = btree_writehead(head, p);
        memcpy(p, bt->alloc_bits, alloc_size);
        result = btree_write_node(bt, 0, buf);
    }
    if (bt->alloc_bits)
        free(bt->alloc_bits);
    return result;
}

/* returns pointer to key given by index in current node.
 *
 * Assumes that current node is not NODE_HEAD ...
 * index may be == num_rec in whcih case a pointer
 * to the first free byte is returned ...
 */   
void* btree_key_by_index(btree* bt, node_buf* buf, UInt16 index)
{
    UInt16              node_size, off_pos;
    btree_record_offset offset;

    if (index > buf->desc.num_rec)      // oops out of range
    {
        hfsp_error = "btree_key_by_index: index out of range";
        return NULL;
    }
    node_size       = bt->head.node_size; 
        // The offsets are found at the end of the node ...
    off_pos         = node_size - (index +1) * sizeof(btree_record_offset);
        // position of offset at end of node
   if (off_pos >= node_size)    // oops out of range
    {
        hfsp_error = "btree_key_by_index: off_pos out of range";
        return NULL;
    }
    offset = bswabU16(*((btree_record_offset*) (buf->node + off_pos)));
    if (offset >= node_size)    // oops out of range
    {
        hfsp_error = "btree_key_by_index: offset out of range";
        return NULL;
    }
  
    // now we have the offset and can read the key ...
    return buf->node + offset;
}

/** return allocation status of node given by index in btree */

int btree_check_nodealloc(btree* bt, UInt16 node)
{
    btree_head* head        = &bt->head;
    btree_node_desc* desc   = &bt->head_node;
    UInt16      node_size   = head->node_size;
    UInt16      node_num    = desc->next;
    UInt32      node_count  = head->node_count;
    char*       alloc_bits  = bt->alloc_bits + 128; // skip reserved node
    int         bit         = node & 0x07;
    int         alloc_size  = node_size - 256; 
            // sizeof(node_desc) + sizeof(header) + 128 - 8
    node_buf*   nbuf        = NULL;
      
    if (node >= node_count)
        HFSP_ERROR(-1, "Node index out of range.");
    node  >>= 3;
    // First must check bits in saved allocation bits from node header
    if (node < alloc_size)
        return (alloc_bits[node] & (0x80 >> bit)); /* Bit one is 0x80 ! */
    // Now load matching node by iterating over MAP-Nodes
    node -= alloc_size; 
    while (node_num && node >= node_size)
    {
        nbuf = btree_node_by_index(bt, node_num, NODE_CLEAN);
        if (!nbuf)
            HFSP_ERROR(-1, "Unable to fetch map node");
        desc = &nbuf->desc;
        if (desc->kind != HFSP_NODE_MAP)
            HFSP_ERROR(-1, "Invalid chain of map nodes");
        node -= node_size;
        node  = desc->next;
    }
    if (!nbuf)
        HFSP_ERROR(-1, "Oops this code is wrong");  // Should not happen, oops
    return (nbuf->node[node] & (0x80 >> bit));      /* Bit one is 0x80 ! */
fail:
    return -1;
}

/* Remove the key and an (eventual) record from the btree.
 * Warning, you must WRITELOCK the btree before calling this 
 */
int btree_remove_record(btree* bt, UInt16 node_index, UInt16 keyind)
{
    node_buf*        node    = btree_node_by_index(bt, node_index, NODE_DIRTY);
    btree_node_desc* desc    = &node->desc;
    int              num_rec = desc->num_rec;
    void*            curr    = btree_key_by_index(bt, node, keyind);

    if (keyind != num_rec) // Last record needs no special action
    {
        void    *next     = btree_key_by_index(bt, node, keyind+1);
        void    *last     = btree_key_by_index(bt, node, num_rec);
        // difference needed to update the backpointers
        int     diff      = ((char*) next) - ((char*) curr);
        // hfsp_key* key  = (hfsp_key*) curr; 
        // UInt16  help   = key->key_length;
        // size of the block to move "down"
        int     size      = ((char*) last) - ((char*) next);
        UInt16  node_size = bt->head.node_size;
        int   i,n, off_pos;
        btree_record_offset* offsets;
        btree_record_offset old; 

        memmove(curr, next, size);

        // Now care about the backpointers,
        off_pos = node_size - (num_rec + 1) * sizeof(btree_record_offset);
        offsets = (btree_record_offset*) (node->node + off_pos);

        // fprintf(stderr, 
        //    "moving backpointers in node %d by %4x (%d)\n",
        //    node_index, diff, help);

        // The backpointer at keyind is already correct
        n   = num_rec - keyind;
        old = 0xffff; 
            // will override former index to free area, thats ok
        for (i=0; i <= n; i++)
        {
            btree_record_offset off = offsets[i];
            // fprintf(stderr, "moving backpointers %4x, %4x\n", off, old);
            offsets[i] = old;
            
            old = off - diff; // adjust the backpointer
        }
    }
    desc->num_rec = num_rec - 1;

    if (desc->kind == HFSP_NODE_LEAF)
    {
        bt->head.leaf_count --;
        bt->attributes |= BTREE_HEADDIRTY;
    }
    
    return 0;
}

/* insert a key and an (eventual) record into the btree.
 * Warning, you must WRITELOCK the btree before calling this.
 * keyind may well be == num_rec indicating an append.
 *
 * node_index number of the node in the tree.
 * keyind   the index where the key/record should be insert in the node
 * key      the key (+ record) to append
 * len      the lenght of the key or key + record
 */
int btree_insert_record(btree* bt, UInt16 node_index, UInt16 keyind,
                        void* key, int len)
{
    node_buf*           node    = btree_node_by_index(bt, node_index, NODE_DIRTY);
    btree_node_desc*    desc    = &node->desc;
    int                 num_rec = desc->num_rec;
    UInt16              node_size= bt->head.node_size;
    void                *curr,*last;    // Pointer for calculations
    int                 size, total; 
    int                 i,n,off_pos;
    btree_record_offset* offsets;

    curr    = btree_key_by_index(bt, node, keyind);
    last    = btree_key_by_index(bt, node, num_rec);
        // size of the block to move "up"
    size     = ((char*) last) - ((char*) curr);
    total    = ((char*) last) - node->node; 
    
                // account for backpointers, too 
    if ((total + len) > (node_size - num_rec * sizeof(btree_record_offset)))
        return -1;  // need to split/repartition node first, NYI

    memmove(curr + len, curr, size);
    // printf("Moving to [%p %p]\n", curr+len, curr+len+size);
    memcpy (curr      , key , len);     // Copy the key / record

    num_rec ++;
    // Now care about the backpointers,
    off_pos = node_size - (num_rec + 1) * sizeof(btree_record_offset);
    offsets = (btree_record_offset*) (node->node + off_pos);

    // Recalculate backpointers
    n = num_rec - keyind;
    // printf("Copying to [%p %p]\n", offsets, &offsets[n]);
    for (i=0; i < n; i++)
        offsets[i] = offsets[i+1] + len;
    desc->num_rec = num_rec; // Adjust node descriptor

    if (desc->kind == HFSP_NODE_LEAF)
    {
        bt->head.leaf_count ++;
        bt->attributes |= BTREE_HEADDIRTY;
    }
    
    return 0;
}
1	dpavlin	1	/*
2			* libhfs - library for reading and writing Macintosh HFS volumes
3			* The fucntions are used to handle the various forms of btrees
4			* found on HFS+ volumes.
5			*
6			* The functions are used to handle the various forms of btrees
7			* found on HFS+ volumes.
8			*
9			* Copyright (C) 2000 Klaus Halfmann <klaus.halfmann@feri.de>
10			* Original 1996-1998 Robert Leslie <rob@mars.org>
11			* Additional work by Brad Boyer (flar@pants.nu)
12			*
13			* This program is free software; you can redistribute it and/or modify
14			* it under the terms of the GNU General Public License as published by
15			* the Free Software Foundation; either version 2 of the License, or
16			* (at your option) any later version.
17			*
18			* This program is distributed in the hope that it will be useful,
19			* but WITHOUT ANY WARRANTY; without even the implied warranty of
20			* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21			* GNU General Public License for more details.
22			*
23			* You should have received a copy of the GNU General Public License
24			* along with this program; if not, write to the Free Software
25			* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
26			*
27			*/
28
29			# ifdef HAVE_CONFIG_H
30			# include "config.h"
31			# endif
32
33			# include <stdio.h>
34			# include <stdlib.h>
35			# include <string.h>
36			# include <limits.h>
37			# include <errno.h>
38
39			# include "libhfsp.h"
40			# include "volume.h"
41			# include "btree.h"
42			# include "record.h"
43			# include "swab.h"
44
45			#ifdef HAVE_MEMSET
46			# define bzero(_a_,_s_) memset (_a_,0,_s_)
47			#endif
48
49			/* Read the node from the given buffer and swap the bytes.
50			*
51			* return pointer after reading the structure
52			*/
53			char* btree_readnode(btree_node_desc* node, char *p)
54			{
55			node->next = bswabU32_inc(&p);
56			node->prev = bswabU32_inc(&p);
57			node->kind = bswabU8_inc(&p);
58			node->height = bswabU8_inc(&p);
59			node->num_rec = bswabU16_inc(&p);
60			node->reserved = bswabU16_inc(&p);
61			return p;
62			}
63
64			/* Write the node to the given buffer and swap the bytes.
65			*
66			* return pointer after writing the structure
67			*/
68			char* btree_writenode(btree_node_desc* node, char *p)
69			{
70			bstoreU32_inc(&p, node->next);
71			bstoreU32_inc(&p, node->prev);
72			bstoreU8_inc (&p, node->kind);
73			bstoreU8_inc (&p, node->height);
74			bstoreU16_inc(&p, node->num_rec);
75			bstoreU16_inc(&p, node->reserved);
76			return p;
77			}
78
79
80			/* read a btree header from the given buffer and swap the bytes.
81			*
82			* return pointer after reading the structure
83			*/
84			char* btree_readhead(btree_head* head, char *p)
85			{
86			int i;
87			head->depth = bswabU16_inc(&p);
88			head->root = bswabU32_inc(&p);
89			head->leaf_count = bswabU32_inc(&p);
90			head->leaf_head = bswabU32_inc(&p);
91			head->leaf_tail = bswabU32_inc(&p);
92			head->node_size = bswabU16_inc(&p);
93			head->max_key_len = bswabU16_inc(&p);
94			head->node_count = bswabU32_inc(&p);
95			head->free_nodes = bswabU32_inc(&p);
96			head->reserved1 = bswabU16_inc(&p);
97			head->clump_size = bswabU32_inc(&p);
98			head->btree_type = bswabU8_inc(&p);
99			head->reserved2 = bswabU8_inc(&p);
100			head->attributes = bswabU32_inc(&p);
101			for (i=0; i < 16; i++)
102			head->reserved3[i] = bswabU32_inc(&p);
103			return p;
104			}
105
106			/* read a btree header from the given buffer and swap the bytes.
107			*
108			* return pointer after reading the structure
109			*/
110			char* btree_writehead(btree_head* head, char *p)
111			{
112			int i;
113			bstoreU16_inc(&p, head->depth);
114			bstoreU32_inc(&p, head->root);
115			bstoreU32_inc(&p, head->leaf_count);
116			bstoreU32_inc(&p, head->leaf_head);
117			bstoreU32_inc(&p, head->leaf_tail);
118			bstoreU16_inc(&p, head->node_size);
119			bstoreU16_inc(&p, head->max_key_len);
120			bstoreU32_inc(&p, head->node_count);
121			bstoreU32_inc(&p, head->free_nodes);
122			bstoreU16_inc(&p, head->reserved1);
123			bstoreU32_inc(&p, head->clump_size);
124			bstoreU8_inc (&p, head->btree_type);
125			bstoreU8_inc (&p, head->reserved2);
126			bstoreU32_inc(&p, head->attributes);
127			for (i=0; i < 16; i++)
128			bstoreU32_inc(&p, head->reserved3[i]);
129			return p;
130			}
131
132			/* Intialize cache with default cache Size,
133			* must call node_cache_close to deallocate memory */
134			int node_cache_init(node_cache* cache, btree* tree, int size)
135			{
136			int nodebufsize;
137			char * buf;
138
139			cache->size = size;
140			cache->currindex = 0;
141			nodebufsize = tree->head.node_size + sizeof(node_buf);
142			buf = malloc(size *(sizeof(node_entry) + nodebufsize));
143			if (!buf)
144			return -1;
145			cache -> nodebufsize = nodebufsize;
146			cache -> entries = (node_entry*) buf;
147			cache -> buffers = (char*) &cache->entries[size];
148			bzero(cache->entries, size*sizeof(node_entry));
149			return 0;
150			}
151
152			/* Like cache->buffers[i], since size of node_buf is variable */
153			static inline node_buf* node_buf_get(node_cache* cache, int i)
154			{
155			return (node_buf) (cache->buffers + (i cache->nodebufsize));
156			}
157
158
159			/* write back a node at given node in fork with nodebuf */
160			static int btree_write_node(btree* bt, int index, char* nodebuf)
161			{
162			UInt16 blkpernode = bt->blkpernode;
163			UInt16 nodeperblk = bt->nodeperblk;
164
165			if (blkpernode)
166			{
167			return volume_writetofork(bt->vol, nodebuf, bt->fork,
168			index * blkpernode, blkpernode, HFSP_EXTENT_DATA, bt->cnid);
169			}
170			else // use nodeperblk, must reread other blocks, too
171			{
172			char buf[bt->vol->blksize];
173
174			UInt16 node_size = bt->head.node_size;
175			UInt16 offset = (index % nodeperblk) * node_size;
176			int block = index / nodeperblk;
177
178			// read block including this one
179			void* p = volume_readfromfork(bt->vol, buf, bt->fork,
180			block, 1, HFSP_EXTENT_DATA, bt->cnid);
181			if (p != buf) // usually NULL
182			return -1; // evil ...
183			p = &nodebuf[offset]; // node is found at that offset
184			memcpy(p, nodebuf, node_size);
185			if (volume_writetofork(bt->vol, buf, bt->fork,
186			block, 1, HFSP_EXTENT_DATA, bt->cnid))
187			return -1; // evil ...
188			}
189			return 0; // all is fine
190			}
191
192			/* flush the node at cache index */
193			static int node_cache_flush_node(btree* bt, int index)
194			{
195			node_entry *e = &bt->cache.entries[index];
196			int result = 0;
197			int node_index = e->index;
198
199			// Only write back valid, dirty nodes
200			if(e->index && (e->flags & NODE_DIRTY))
201			{
202			node_buf* b = node_buf_get(&bt->cache, index);
203			if (!b->index)
204			{
205			hfsp_error = "cache inconsistency in node_cache_flush_node";
206			return -1;
207			}
208			// Write back node header to cached memory
209			btree_writenode(&b->desc, b->node);
210			result = btree_write_node(bt, node_index, b->node);
211			b->index = 0; // invalidate block entry
212			}
213			e->index = 0; // invalidate cache entry
214			return result; // all is fine
215			}
216
217			/* flush the cache */
218			static int node_cache_flush(btree* bt)
219			{
220			int i, size = bt->cache.size;
221			int result = 0;
222
223			for (i=0; i < size; i++)
224			{
225			node_entry* e = &bt->cache.entries[i];
226			if(e->index && (e->flags & NODE_DIRTY))
227			if (node_cache_flush_node(bt, i))
228			result = -1;
229			}
230			return result;
231			}
232
233			static int node_cache_close(btree* bt)
234			{
235			int result = 0;
236			if (!bt->cache.entries) // not (fully) intialized ?
237			return result;
238			result = node_cache_flush(bt);
239			free(bt->cache.entries);
240			return result;
241			}
242
243			/* Load the cach node indentified by index with
244			* the node identified by node_index.
245			*
246			* Set the inital flags as given.
247			*/
248
249			static node_buf* node_cache_load_buf
250			(btree* bt, node_cache* cache, int index, UInt16 node_index, int flags)
251			{
252			node_buf *result = node_buf_get(cache ,index);
253			UInt16 blkpernode = bt->blkpernode;
254			UInt16 nodeperblk = bt->nodeperblk;
255			node_entry *e = &cache->entries[index];
256			UInt32 block;
257			void *p;
258
259			if (blkpernode)
260			{
261			block = node_index * blkpernode;
262			p = volume_readfromfork(bt->vol, result->node, bt->fork,
263			block, blkpernode, HFSP_EXTENT_DATA, bt->cnid);
264			if (!p)
265			return NULL; // evil ...
266
267			btree_readnode(&result->desc, p);
268			}
269			else // use nodeperblk
270			{
271			char buf[bt->vol->blksize];
272
273			UInt16 node_size = bt->head.node_size;
274			UInt16 offset = node_index % nodeperblk * node_size;
275			block = node_index / nodeperblk;
276			p = volume_readfromfork(bt->vol, buf, bt->fork,
277			block, 1, HFSP_EXTENT_DATA, bt->cnid);
278			if (p != buf) // usually NULL
279			return NULL; // evil ...
280			p = &buf[offset]; // node is found at that offset
281			memcpy(&result->node, p , node_size);
282			btree_readnode(&result->desc, p);
283
284			}
285
286			result->index = node_index;
287
288			e -> priority = result->desc.height * DEPTH_FACTOR;
289			e -> index = node_index;
290			e -> flags = flags;
291			return result;
292			}
293
294			/* Mark node at given index dirty in cache.
295			*/
296			inline static void btree_dirty_node(btree* bt, UInt16 index)
297			{
298			node_cache* cache = &bt->cache;
299			node_entry *e = &cache->entries[index];
300			e->flags \|= NODE_DIRTY;
301			}
302
303			/* Read node at given index, using cache.
304			*
305			* Make node with given flag, usually NODE_CLEAN/NODE_DIRTY
306			*/
307			node_buf* btree_node_by_index(btree* bt, UInt16 index, int flags)
308			{
309			node_cache* cache = &bt->cache;
310			int oldindex, lruindex;
311			int currindex = cache->currindex;
312			UInt32 prio;
313			node_entry *e;
314
315			// Shortcut acces to current node, will not change priorities
316			if (cache->entries[currindex].index == index)
317			{
318			cache->entries[currindex].flags \|= flags;
319			return node_buf_get(cache ,currindex);
320			}
321			oldindex = currindex;
322			if (currindex == 0)
323			currindex = cache->size;
324			currindex--;
325			lruindex = oldindex; // entry to be flushed when needed
326			prio = 0; // current priority
327			while (currindex != oldindex) // round robin
328			{
329			e = &cache->entries[currindex];
330			if (e->index == index) // got it
331			{
332			if (e->priority != 0) // already top, uuh
333			e->priority--;
334			cache->currindex = currindex;
335			e -> flags \|= flags;
336			return node_buf_get(cache ,currindex);
337			}
338			else
339			{
340			if (!e->index) // free entry, well
341			{
342			lruindex = currindex;
343			prio = UINT_MAX; // remember empty entry
344			}
345			if (e->priority != UINT_MAX) // already least, uuh
346			e->priority++;
347			}
348			if (prio < e->priority)
349			{
350			lruindex = currindex;
351			prio = e->priority;
352			}
353			if (currindex == 0)
354			currindex = cache->size;
355			currindex--;
356			}
357			e = &cache->entries[lruindex];
358			cache->currindex = lruindex;
359			if (e->flags & NODE_DIRTY)
360			node_cache_flush_node(bt, lruindex);
361			return node_cache_load_buf (bt, cache, lruindex, index, flags);
362			}
363
364			/** intialize the btree with the first entry in the fork */
365			static int btree_init(btree* bt, volume* vol, hfsp_fork_raw* fork)
366			{
367			char *p;
368			char buf[vol->blksize];
369			UInt16 node_size;
370			btree_node_desc* node = &bt->head_node;
371			int alloc_size;
372
373			bt->vol = vol;
374			bt->fork = fork;
375			p = volume_readfromfork(vol, buf, fork, 0, 1,
376			HFSP_EXTENT_DATA, bt->cnid);
377			if (!p)
378			return -1;
379			p = btree_readnode(node, p);
380			if (node->kind != HFSP_NODE_HEAD)
381			return -1; // should not happen ?
382			p = btree_readhead(&bt->head, p);
383			node_size = bt->head.node_size;
384
385			bt->blkpernode = node_size / vol->blksize;
386
387			if (bt->blkpernode == 0) // maybe the other way round ?
388			bt->nodeperblk = vol->blksize / node_size;
389
390			alloc_size = node_size - HEADER_RESERVEDOFFSET; // sizeof(node_desc) + sizeof(header)
391			/* Sometimes the node_size is bigger than the volume-blocksize
392			* so here I reread the node when needed */
393			{ // need new block for allocation
394			char nodebuf[node_size];
395			if (bt->blkpernode > 1)
396			{
397			p = volume_readfromfork(vol, nodebuf, fork, 0, bt->blkpernode,
398			HFSP_EXTENT_DATA, bt->cnid);
399			p += HEADER_RESERVEDOFFSET; // skip header
400			}
401
402			bt->alloc_bits = malloc(alloc_size);
403			if (!bt->alloc_bits)
404			return ENOMEM;
405			memcpy(bt->alloc_bits, p, alloc_size);
406			}
407
408			/* for debugging */
409			bt->attributes = 0;
410
411			if (node_cache_init(&bt->cache, bt, bt->head.depth + EXTRA_CACHESIZE))
412			return -1;
413
414			return 0;
415			}
416
417			/** Intialize catalog btree, so that btree_close can safely be called. */
418			void btree_reset(btree* bt)
419			{
420			bt->alloc_bits = NULL;
421			bt->cache.entries = NULL;
422			}
423
424			/** Intialize catalog btree */
425			int btree_init_cat(btree* bt, volume* vol, hfsp_fork_raw* fork)
426			{
427			int result = btree_init(bt,vol,fork); // super (...)
428			bt->cnid = HFSP_CAT_CNID;
429			bt->kcomp = record_key_compare;
430			bt->kread = record_readkey;
431			bt->rread = record_readentry;
432			bt->max_rec_size = sizeof(hfsp_cat_entry);
433			// this is a bit too large due to alignment/padding
434			return result;
435			}
436
437			/** Intialize catalog btree */
438			int btree_init_extent(btree* bt, volume* vol, hfsp_fork_raw* fork)
439			{
440			int result = btree_init(bt,vol,fork); // super (...)
441			bt->cnid = HFSP_EXT_CNID;
442			bt->kcomp = record_extent_key_compare;
443			bt->kread = record_extent_readkey;
444			bt->rread = record_extent_readrecord;
445			bt->max_rec_size = sizeof(hfsp_extent);
446			return result;
447			}
448
449			/** close the btree and free any resources */
450			int btree_close(btree* bt)
451			{
452			int result = 0;
453
454			node_cache_close(bt);
455			// a dirty header without alloc_bits must not happen, mmh
456			if ((bt->attributes & BTREE_HEADDIRTY) && bt->alloc_bits)
457			{
458			btree_head* head = &bt->head;
459			btree_node_desc* node = &bt->head_node;
460			UInt16 node_size = head->node_size;
461			UInt16 alloc_size = node_size - HEADER_RESERVEDOFFSET;
462			char buf[node_size];
463			void *p;
464
465			p = btree_writenode(node, buf);
466			p = btree_writehead(head, p);
467			memcpy(p, bt->alloc_bits, alloc_size);
468			result = btree_write_node(bt, 0, buf);
469			}
470			if (bt->alloc_bits)
471			free(bt->alloc_bits);
472			return result;
473			}
474
475			/* returns pointer to key given by index in current node.
476			*
477			* Assumes that current node is not NODE_HEAD ...
478			* index may be == num_rec in whcih case a pointer
479			* to the first free byte is returned ...
480			*/
481			void* btree_key_by_index(btree* bt, node_buf* buf, UInt16 index)
482			{
483			UInt16 node_size, off_pos;
484			btree_record_offset offset;
485
486			if (index > buf->desc.num_rec) // oops out of range
487			{
488			hfsp_error = "btree_key_by_index: index out of range";
489			return NULL;
490			}
491			node_size = bt->head.node_size;
492			// The offsets are found at the end of the node ...
493			off_pos = node_size - (index +1) * sizeof(btree_record_offset);
494			// position of offset at end of node
495			if (off_pos >= node_size) // oops out of range
496			{
497			hfsp_error = "btree_key_by_index: off_pos out of range";
498			return NULL;
499			}
500			offset = bswabU16(((btree_record_offset) (buf->node + off_pos)));
501			if (offset >= node_size) // oops out of range
502			{
503			hfsp_error = "btree_key_by_index: offset out of range";
504			return NULL;
505			}
506
507			// now we have the offset and can read the key ...
508			return buf->node + offset;
509			}
510
511			/** return allocation status of node given by index in btree */
512
513			int btree_check_nodealloc(btree* bt, UInt16 node)
514			{
515			btree_head* head = &bt->head;
516			btree_node_desc* desc = &bt->head_node;
517			UInt16 node_size = head->node_size;
518			UInt16 node_num = desc->next;
519			UInt32 node_count = head->node_count;
520			char* alloc_bits = bt->alloc_bits + 128; // skip reserved node
521			int bit = node & 0x07;
522			int alloc_size = node_size - 256;
523			// sizeof(node_desc) + sizeof(header) + 128 - 8
524			node_buf* nbuf = NULL;
525
526			if (node >= node_count)
527			HFSP_ERROR(-1, "Node index out of range.");
528			node >>= 3;
529			// First must check bits in saved allocation bits from node header
530			if (node < alloc_size)
531			return (alloc_bits[node] & (0x80 >> bit)); /* Bit one is 0x80 ! */
532			// Now load matching node by iterating over MAP-Nodes
533			node -= alloc_size;
534			while (node_num && node >= node_size)
535			{
536			nbuf = btree_node_by_index(bt, node_num, NODE_CLEAN);
537			if (!nbuf)
538			HFSP_ERROR(-1, "Unable to fetch map node");
539			desc = &nbuf->desc;
540			if (desc->kind != HFSP_NODE_MAP)
541			HFSP_ERROR(-1, "Invalid chain of map nodes");
542			node -= node_size;
543			node = desc->next;
544			}
545			if (!nbuf)
546			HFSP_ERROR(-1, "Oops this code is wrong"); // Should not happen, oops
547			return (nbuf->node[node] & (0x80 >> bit)); /* Bit one is 0x80 ! */
548			fail:
549			return -1;
550			}
551
552			/* Remove the key and an (eventual) record from the btree.
553			* Warning, you must WRITELOCK the btree before calling this
554			*/
555			int btree_remove_record(btree* bt, UInt16 node_index, UInt16 keyind)
556			{
557			node_buf* node = btree_node_by_index(bt, node_index, NODE_DIRTY);
558			btree_node_desc* desc = &node->desc;
559			int num_rec = desc->num_rec;
560			void* curr = btree_key_by_index(bt, node, keyind);
561
562			if (keyind != num_rec) // Last record needs no special action
563			{
564			void *next = btree_key_by_index(bt, node, keyind+1);
565			void *last = btree_key_by_index(bt, node, num_rec);
566			// difference needed to update the backpointers
567			int diff = ((char) next) - ((char) curr);
568			// hfsp_key* key = (hfsp_key*) curr;
569			// UInt16 help = key->key_length;
570			// size of the block to move "down"
571			int size = ((char) last) - ((char) next);
572			UInt16 node_size = bt->head.node_size;
573			int i,n, off_pos;
574			btree_record_offset* offsets;
575			btree_record_offset old;
576
577			memmove(curr, next, size);
578
579			// Now care about the backpointers,
580			off_pos = node_size - (num_rec + 1) * sizeof(btree_record_offset);
581			offsets = (btree_record_offset*) (node->node + off_pos);
582
583			// fprintf(stderr,
584			// "moving backpointers in node %d by %4x (%d)\n",
585			// node_index, diff, help);
586
587			// The backpointer at keyind is already correct
588			n = num_rec - keyind;
589			old = 0xffff;
590			// will override former index to free area, thats ok
591			for (i=0; i <= n; i++)
592			{
593			btree_record_offset off = offsets[i];
594			// fprintf(stderr, "moving backpointers %4x, %4x\n", off, old);
595			offsets[i] = old;
596
597			old = off - diff; // adjust the backpointer
598			}
599			}
600			desc->num_rec = num_rec - 1;
601
602			if (desc->kind == HFSP_NODE_LEAF)
603			{
604			bt->head.leaf_count --;
605			bt->attributes \|= BTREE_HEADDIRTY;
606			}
607
608			return 0;
609			}
610
611			/* insert a key and an (eventual) record into the btree.
612			* Warning, you must WRITELOCK the btree before calling this.
613			* keyind may well be == num_rec indicating an append.
614			*
615			* node_index number of the node in the tree.
616			* keyind the index where the key/record should be insert in the node
617			* key the key (+ record) to append
618			* len the lenght of the key or key + record
619			*/
620			int btree_insert_record(btree* bt, UInt16 node_index, UInt16 keyind,
621			void* key, int len)
622			{
623			node_buf* node = btree_node_by_index(bt, node_index, NODE_DIRTY);
624			btree_node_desc* desc = &node->desc;
625			int num_rec = desc->num_rec;
626			UInt16 node_size= bt->head.node_size;
627			void curr,last; // Pointer for calculations
628			int size, total;
629			int i,n,off_pos;
630			btree_record_offset* offsets;
631
632			curr = btree_key_by_index(bt, node, keyind);
633			last = btree_key_by_index(bt, node, num_rec);
634			// size of the block to move "up"
635			size = ((char) last) - ((char) curr);
636			total = ((char*) last) - node->node;
637
638			// account for backpointers, too
639			if ((total + len) > (node_size - num_rec * sizeof(btree_record_offset)))
640			return -1; // need to split/repartition node first, NYI
641
642			memmove(curr + len, curr, size);
643			// printf("Moving to [%p %p]\n", curr+len, curr+len+size);
644			memcpy (curr , key , len); // Copy the key / record
645
646			num_rec ++;
647			// Now care about the backpointers,
648			off_pos = node_size - (num_rec + 1) * sizeof(btree_record_offset);
649			offsets = (btree_record_offset*) (node->node + off_pos);
650
651			// Recalculate backpointers
652			n = num_rec - keyind;
653			// printf("Copying to [%p %p]\n", offsets, &offsets[n]);
654			for (i=0; i < n; i++)
655			offsets[i] = offsets[i+1] + len;
656			desc->num_rec = num_rec; // Adjust node descriptor
657
658			if (desc->kind == HFSP_NODE_LEAF)
659			{
660			bt->head.leaf_count ++;
661			bt->attributes \|= BTREE_HEADDIRTY;
662			}
663
664			return 0;
665			}