summaryrefslogtreecommitdiffstats
path: root/qemu/roms/openbios/fs/hfsplus/hfsp_btree.c
diff options
context:
space:
mode:
Diffstat (limited to 'qemu/roms/openbios/fs/hfsplus/hfsp_btree.c')
-rw-r--r--qemu/roms/openbios/fs/hfsplus/hfsp_btree.c372
1 files changed, 0 insertions, 372 deletions
diff --git a/qemu/roms/openbios/fs/hfsplus/hfsp_btree.c b/qemu/roms/openbios/fs/hfsplus/hfsp_btree.c
deleted file mode 100644
index 24eca924c..000000000
--- a/qemu/roms/openbios/fs/hfsplus/hfsp_btree.c
+++ /dev/null
@@ -1,372 +0,0 @@
-/*
- * 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 <khalfmann@libra.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., 51 Franklin Street - Fifth Floor, Boston,
- * MA 02110-1301, USA.
- *
- * $Id: btree.c,v 1.14 2000/10/25 05:43:04 hasi Exp $
- */
-
-#include "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_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_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 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;
- 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(&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(&node, p);
- if (node.kind != HFSP_NODE_HEAD)
- return -1; // should not happen ?
- btree_readhead(&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 + bswabU16(*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