record.c

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

/*
 * libhfsp - library for reading and writing Macintosh HFS+ volumes.
 *
 * a record contains a key and a folder or file and is part
 * of a btree.
 *
 * 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: record.c,v 1.24 2000/10/17 05:58:46 hasi Exp $
 */

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

/* read a hfsp_cat_key from memory */
void* record_readkey(void* p, void* buf)
{
    hfsp_cat_key*   key = (hfsp_cat_key*) buf;
    const void*	    check;
    UInt16	    key_length, len,i;
    UInt16*	    cp;

    key->key_length = key_length    = bswabU16_inc(p);
    check = p;
    key->parent_cnid		    = bswabU32_inc(p);
    key->name.strlen = len	    = bswabU16_inc(p);
    cp = key->name.name;
    for (i=0; i < len; i++, cp++)
	*cp			    = bswabU16_inc(p);
	/* check if keylenght was correct */
    if (key_length != ((char*) p) - ((char*) check))
	 HFSP_ERROR(EINVAL, "Invalid key length in record_readkey");
    return p;	
  fail:
    return NULL;
}

/* read a hfsp_extent_key from memory */
void* record_extent_readkey(void* p, void* buf)
{
    hfsp_extent_key* key = (hfsp_extent_key*) buf;
    UInt16  key_length;

    key->key_length = key_length    = bswabU16_inc(p);
    key->fork_type		    = bswabU8_inc(p);
    key->filler			    = bswabU8_inc(p);
    if (key_length != 10)
	HFSP_ERROR(-1, "Invalid key length in record_extent_readkey");
    key->file_id		    = bswabU32_inc(p);
    key->start_block		    = bswabU32_inc(p);
    return p;	
  fail:
    return NULL;
}


/* read posix permission from memory */
static inline void* record_readperm(void *p, hfsp_perm* perm)
{
    perm->owner= bswabU32_inc(p);
    perm->group= bswabU32_inc(p);
    perm->mode = bswabU32_inc(p);
    perm->dev  = bswabU32_inc(p);
    return p;
}

/* read directory info */
static inline void* record_readDInfo(void *p, DInfo* info)
{
    info->frRect.top	= bswabU16_inc(p);
    info->frRect.left	= bswabU16_inc(p);
    info->frRect.bottom	= bswabU16_inc(p);
    info->frRect.right	= bswabU16_inc(p);
    info->frFlags	= bswabU16_inc(p);
    info->frLocation.v	= bswabU16_inc(p);
    info->frLocation.h	= bswabU16_inc(p);
    info->frView	= bswabU16_inc(p);
    return p;
}

/* read extra Directory info */
static inline void* record_readDXInfo(void *p, DXInfo* xinfo)
{
    xinfo->frScroll.v  = bswabU16_inc(p);
    xinfo->frScroll.h  = bswabU16_inc(p);
    xinfo->frOpenChain = bswabU32_inc(p);
    xinfo->frUnused    = bswabU16_inc(p);
    xinfo->frComment   = bswabU16_inc(p);
    xinfo->frPutAway   = bswabU32_inc(p);
    return p;
}

/* read a hfsp_cat_folder from memory */
static void* record_readfolder(void *p, hfsp_cat_folder* folder)
{
    folder->flags		= bswabU16_inc(p);
    folder->valence		= bswabU32_inc(p);
    folder->id			= bswabU32_inc(p);
    folder->create_date		= bswabU32_inc(p);
    folder->content_mod_date    = bswabU32_inc(p);
    folder->attribute_mod_date	= bswabU32_inc(p);
    folder->access_date		= bswabU32_inc(p);
    folder->backup_date		= bswabU32_inc(p);
    p = record_readperm	    (p, &folder->permissions);
    p = record_readDInfo    (p, &folder->user_info);
    p = record_readDXInfo   (p, &folder->finder_info);
    folder->text_encoding	= bswabU32_inc(p);
    folder->reserved		= bswabU32_inc(p);
    return p;
}

/* read file info */
static inline void* record_readFInfo(void *p, FInfo* info)
{
    info->fdType	= bswabU32_inc(p);
    info->fdCreator	= bswabU32_inc(p);
    info->fdFlags	= bswabU16_inc(p);
    info->fdLocation.v	= bswabU16_inc(p);
    info->fdLocation.h	= bswabU16_inc(p);
    info->fdFldr	= bswabU16_inc(p);
    return p;
}

/* read extra File info */
static inline void* record_readFXInfo(void *p, FXInfo* xinfo)
{
    SInt16 *q;
    xinfo->fdIconID	= bswabU16_inc(p);
    q=(SInt16*) p;
    q+=4; // skip unused
    p=(void *)q;
    xinfo->fdComment	= bswabU16_inc(p);
    xinfo->fdPutAway	= bswabU32_inc(p);
    return p;
}

/* read a hfsp_cat_file from memory */
static void* record_readfile(void *p, hfsp_cat_file* file)
{
    file->flags			= bswabU16_inc(p);
    file->reserved1		= bswabU32_inc(p);
    file->id			= bswabU32_inc(p);
    file->create_date		= bswabU32_inc(p);
    file->content_mod_date	= bswabU32_inc(p);
    file->attribute_mod_date	= bswabU32_inc(p);
    file->access_date		= bswabU32_inc(p);
    file->backup_date		= bswabU32_inc(p);
    p = record_readperm	    (p, &file->permissions);
    p = record_readFInfo    (p, &file->user_info);
    p = record_readFXInfo   (p, &file->finder_info);
    file->text_encoding		= bswabU32_inc(p);
    file->reserved2		= bswabU32_inc(p);
    p =	    volume_readfork (p, &file->data_fork);
    return  volume_readfork (p, &file->res_fork);
}

/* read a hfsp_cat_thread from memory */
static void* record_readthread(void *p, hfsp_cat_thread* entry)
{
    int	    i;
    UInt16  len;
    UInt16* cp;

    entry->         reserved	= bswabU16_inc(p);
    entry->	    parentID	= bswabU32_inc(p);
    entry->nodeName.strlen = len= bswabU16_inc(p);
    cp = entry->nodeName.name;
    if (len > 255)
        HFSP_ERROR(-1, "Invalid key length in record thread");
    for (i=0; i < len; i++, cp++)
	*cp			 = bswabU16_inc(p);
    return p;
 fail:
    return NULL;
}

/* read a hfsp_cat_entry from memory */
static void* record_readentry(void *p, hfsp_cat_entry* entry)
{
    UInt16 type = bswabU16_inc(p);
    entry->type = type;
    switch (type)
    {
	case HFSP_FOLDER:
	    return record_readfolder(p, &entry->u.folder);
	case HFSP_FILE:
	    return record_readfile  (p, &entry->u.file);
	case HFSP_FOLDER_THREAD:
	case HFSP_FILE_THREAD:
	    return record_readthread(p, &entry->u.thread);
	default:
	    HFSP_ERROR(-1, "Unexpected record type in record_readentry");
    } ;
  fail:
    return NULL;
}


/* Most of the functions here will not change the node in the btree,
   But this must be changed in the future ... */


/* intialize the record with the given index entry in the btree. */
static int record_init(record* r, btree* bt, node_buf* buf, UInt16 index)
{
    void *p;
    r-> tree   = bt;
    p = btree_key_by_index(bt,buf,index);
    if (!p)
	return -1;
    p = record_readkey  (p, &r->key);
    if (!p)
	return -1;
    p = record_readentry(p, &r->record);
    if (!p)
	return -1;
    r->node_index = buf->index;
    r-> keyind    = index;

    return 0;
}

/* intialize the record with the given index entry in the btree. */
static int record_init_extent(extent_record* r, btree* bt, node_buf* buf, UInt16 index)
{
    void *p;
    r-> tree   = bt;
    p = btree_key_by_index(bt, buf,index);
    if (!p)
	return -1;
    p = record_extent_readkey(p, &r->key);
    if (!p)
	return -1;
    p = volume_readextent(p, r->extent);
    if (!p)
	return -1;
    r->node_index = buf->index;
    r-> keyind    = index;

    return 0;
}

/* intialize the record to the first record of the tree
 * which is (per design) the root node.
 */
int record_init_root(record* r, btree* tree)
{
    // Position to first leaf node ...
    UInt32 leaf_head = tree->head.leaf_head;
    node_buf* buf = btree_node_by_index(tree, leaf_head);
    if (!buf)
	return -1;
    return record_init(r, tree, buf, 0);
}

/* Compare two cat_keys ... */
int record_key_compare(void* k1, void* k2)
{
    hfsp_cat_key* key1 = (hfsp_cat_key*) k1;
    hfsp_cat_key* key2 = (hfsp_cat_key*) k2;
    int diff = key2->parent_cnid - key1->parent_cnid;
    if (!diff) // same parent
	diff = fast_unicode_compare(&key1->name, &key2->name); 
    return diff;
}

/* Compare two extent_keys ... */
int record_extent_key_compare(void* k1, void* k2)
{
    hfsp_extent_key* key1 = (hfsp_extent_key*) k1;
    hfsp_extent_key* key2 = (hfsp_extent_key*) k2;
    int diff = key2->fork_type - key1->fork_type;
    if (!diff) // same type
    {
	diff = key2->file_id - key1->file_id;
	if (!diff) // same file
	    diff = key2->start_block - key1->start_block;
    }
    return diff;
}

/* Position node in btree so that key might be inside */
static node_buf* record_find_node(btree* tree, void *key)
{
    int			start, end, mid, comp;  // components of a binary search
    void		*p = NULL;
    char		curr_key[tree->head.max_key_len];
		    // The current key under examination
    hfsp_key_read	readkey	    = tree->kread;
    hfsp_key_compare	key_compare = tree->kcomp;
    UInt32		index;
    node_buf*		node = btree_node_by_index(tree, tree->head.root);
    if (!node)
	HFSP_ERROR(-1, "record_find_node: Cant position to root node");
    while (node->desc.kind == HFSP_NODE_NDX)
    {
	mid = start = 0;
	end  = node->desc.num_rec;
	comp = -1;
	while (start < end)
	{
	    mid = (start + end) >> 1;
	    p = btree_key_by_index(tree, node, mid);
	    if (!p)
		HFSP_ERROR(-1, "record_find_node: unexpected error");
	    p = readkey  (p, curr_key);
	    if (!p)
		HFSP_ERROR(-1, "record_find_node: unexpected error");
	    comp = key_compare(curr_key, key);
	    if (comp > 0)
		start = mid + 1;
	    else if (comp < 0)
		end = mid;
	    else 
		break;
	}
	if (!p) // Empty tree, fascinating ...
	    HFSP_ERROR(-1, "record_find_node: unexpected empty node");
	if (comp < 0)	// mmh interesting key is before this key ...
	{
	    if (mid == 0)
		return NULL;  // nothing before this key ..
	    p = btree_key_by_index(tree, node, mid-1);
	    if (!p)
		HFSP_ERROR(-1, "record_find_node: unexpected error");
	    p = readkey  (p, curr_key);
	    if (!p)
		HFSP_ERROR(-1, "record_find_node: unexpected error");
	}
	    
	index = bswabU32_inc(p);
	node = btree_node_by_index(tree, index);
    }
    return node;	// go on and use the found node
  fail:
    return NULL;
}

/* search for the given key in the btree.
 * 
 * returns pointer to memory just after key or NULL
 * In any case *keyind recives the index where the
 * key was found (or could be inserted.)
 */
static void *
record_find_key(btree* tree, void* key, int* keyind, UInt16* node_index)
{
    node_buf* buf = record_find_node(tree, key);
    if (buf)
    {
	int		    comp  = -1;
	int		    start = 0; // components of a binary search
	int		    end   = buf->desc.num_rec;
	int		    mid   = -1;
	void		    *p    = NULL;
	char		    curr_key[tree->head.max_key_len];
	hfsp_key_read	    readkey	= tree->kread;
	hfsp_key_compare    key_compare = tree->kcomp;