btree.c

open source bios with linux platform, very good and can be reused.

/*
 * 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 fucntions are used to handle the various forms of btrees
 * found on HFS+ volumes.
 *
 * Copyright (C) 2000 Klaus Halfmann <[e-mail]>
 * Original 1996-1998 Robert Leslie <[e-mail]>
 * Additional work by  Brad Boyer ([e-mail])  
 *
 * 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.
 *
 * $Id: btree.c,v 1.14 2000/10/25 05:43:04 hasi Exp $
 */

#include "openbios/config.h"
#include "libhfsp.h"
#include "volume.h"
#include "btree.h"
#include "record.h"
#include "swab.h"

/* Read the node from the given buffer and swap the bytes.
 *
 * return pointer after reading the structure
 */
static void* btree_readnode(btree* bt, btree_node_desc* node, void *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;
} 

/* read a btree header from the given buffer and swap the bytes.
 *
 * return pointer after reading the structure
 */
static void* btree_readhead(btree* bt, btree_head* head, void *p)
{
	UInt32 *q;
        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);
	    // skip reserved bytes
	q=((UInt32*) p);
	// ((UInt32*) p) += 16;
	q+=16;
	return q;
}

/* Priority of the depth of the node compared to LRU value.
 * Should be the average number of keys per node but these vary. */
#define DEPTH_FACTOR	1000

/* Cache size is height of tree + this value 
 * Really big numbers wont help in case of ls -R
 */
#define EXTRA_CACHESIZE	3 

/* Not in use by now ... */
#define CACHE_DIRTY 0x0001

/* Intialize cache with default cache Size, 
 * must call node_cache_close to deallocate memory */
static 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));
}
   
/* flush the cache NYI */
static void node_cache_flush(node_cache* cache)
{
    // NYI
}

/* flush the node at index */
static void node_cache_flush_node(node_cache* cache, int index)
{
    // NYI
    cache -> entries[index].index = 0;	// invalidate entry
}

static void node_cache_close(node_cache* cache)
{
    if (!cache->entries) // not (fully) intialized ?
	return;
    node_cache_flush(cache);
    free(cache->entries);
}

/* Load the cach node indentified by index with 
 * the node identified by node_index */

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

    if (!p)
	return NULL;	// evil ...

    result->index   = node_index;
    btree_readnode(bt, &result->desc, p);

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

/* Read node at given index, using cache.
 */
node_buf* btree_node_by_index(btree* bt, UInt16 index)
{
    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)
	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;
	    return node_buf_get(cache ,currindex);
	}
	else
	{
	    if (!e->index)
	    {
		lruindex = currindex;
		break;	// empty entry, load it
	    }
	    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 & CACHE_DIRTY)
           node_cache_flush_node(    cache, lruindex);
    return node_cache_load_buf  (bt, cache, lruindex, index);
}

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

    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(bt, &node, p);
    if (node.kind != HFSP_NODE_HEAD)
	return -1;   // should not happen ?
    p = btree_readhead(bt, &bt->head, p);

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

    if (bt->blkpernode == 0 || vol->blksize *
	    bt->blkpernode != node_size)
	return -1;  // should never happen ...

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

    // Allocate buffer 
    // bt->buf = malloc(node_size);
    // if (!bt->buf)
    //	return ENOMEM;

    return 0;
}

/** Intialize catalog btree, so that btree_close can safely be called. */
void btree_reset(btree* bt)
{
    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;
    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;
    return result;
}

/** close the btree and free any resources */
void btree_close(btree* bt)
{
    node_cache_close(&bt->cache);
    // free(bt->buf);
}

/* returns pointer to key given by index in current node.
 *
 * Assumes that current node is not NODE_HEAD ...
 */   
void* btree_key_by_index(btree* bt, node_buf* buf, UInt16 index)
{
    UInt16  node_size	    = bt->head.node_size; 
	// The offsets are found at the end of the node ...
    UInt16  off_pos	    = node_size - (index +1) * sizeof(btree_record_offset);
 	// position of offset at end of node
    btree_record_offset* offset = 
	(btree_record_offset*) (buf->node + off_pos);
	
    // now we have the offset and can read the key ...
#ifdef CONFIG_LITTLE_ENDIAN
    return buf->node + bswap_16(*offset);
#else
    return buf->node + *offset;
#endif
}
    

#ifdef DEBUG

/* print btree header node information */
void btree_printhead(btree_head* head)
{
    UInt32 attr;
    printf("  depth       : %#X\n",  head->depth);
    printf("  root        : %#lX\n", head->root);
    printf("  leaf_count  : %#lX\n", head->leaf_count);
    printf("  leaf_head   : %#lX\n", head->leaf_head);
    printf("  leaf_tail   : %#lX\n", head->leaf_tail);
    printf("  node_size   : %#X\n",  head->node_size);
    printf("  max_key_len : %#X\n",  head->max_key_len);
    printf("  node_count  : %#lX\n", head->node_count);
    printf("  free_nodes  : %#lX\n", head->free_nodes);
    printf("  reserved1   : %#X\n",  head->reserved1);
    printf("  clump_size  : %#lX\n", head->clump_size);
    printf("  btree_type  : %#X\n",  head->btree_type);
    attr = head->attributes;
    printf("  reserved2   : %#X\n",  head->reserved2);
    if (attr & HFSPLUS_BAD_CLOSE)
        printf(" HFSPLUS_BAD_CLOSE *** ");
    else
        printf(" !HFSPLUS_BAD_CLOSE");
    if (attr & HFSPLUS_TREE_BIGKEYS)
        printf(" HFSPLUS_TREE_BIGKEYS ");
    else
        printf("  !HFSPLUS_TREE_BIGKEYS");
    if (attr & HFSPLUS_TREE_VAR_NDXKEY_SIZE)
        printf(" HFSPLUS_TREE_VAR_NDXKEY_SIZE");
    else
        printf(" !HFSPLUS_TREE_VAR_NDXKEY_SIZE");
    if (attr & HFSPLUS_TREE_UNUSED)
        printf(" HFSPLUS_TREE_UNUSED ***\n");
    printf("\n");
}

/* Dump all the node information to stdout */
void btree_print(btree* bt)
{ 
    btree_node_desc* node;

    btree_printhead(&bt->head);

    node = &bt->node;
    printf("next     : %#lX\n", node->next);
    printf("prev     : %#lX\n", node->prev);
    printf("height   : %#X\n",  node->height);
    printf("num_rec  : %#X\n",  node->num_rec);
    printf("reserved : %#X\n",  node->reserved);
    printf("height   : %#X\n",  node->height);                                      switch(node->kind)
    { 
	case HFSP_NODE_NDX  :
	    printf("HFSP_NODE_NDX\n");
	    break;
	case HFSP_NODE_HEAD :
	    printf("HFSP_NODE_HEAD\n");
	    break;
	case HFSP_NODE_MAP  :
	    printf("HFSP_NODE_MAP\n");
	    break;
	case HFSP_NODE_LEAF :
	    printf("HFSP_NODE_LEAF\n");
	    break;
	default:
	    printf("*** Unknown Node type ***\n");
    } 
} 

#endif