Return to hfsp_btree.c CVS log

Up to [Qemu by Fabrice Bellard] / qemu / roms / openbios / fs / hfsplus

Annotation of qemu/roms/openbios/fs/hfsplus/hfsp_btree.c, revision 1.1

1.1     ! root        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 fucntions are used to handle the various forms of btrees
        !             7:  * found on HFS+ volumes.
        !             8:  *
        !             9:  * Copyright (C) 2000 Klaus Halfmann <[email protected]>
        !            10:  * Original 1996-1998 Robert Leslie <[email protected]>
        !            11:  * Additional work by  Brad Boyer ([email protected])
        !            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., 51 Franklin Street - Fifth Floor, Boston,
        !            26:  * MA 02110-1301, USA.
        !            27:  *
        !            28:  * $Id: btree.c,v 1.14 2000/10/25 05:43:04 hasi Exp $
        !            29:  */
        !            30: 
        !            31: #include "config.h"
        !            32: #include "libhfsp.h"
        !            33: #include "volume.h"
        !            34: #include "btree.h"
        !            35: #include "record.h"
        !            36: #include "swab.h"
        !            37: 
        !            38: /* Read the node from the given buffer and swap the bytes.
        !            39:  *
        !            40:  * return pointer after reading the structure
        !            41:  */
        !            42: static void* btree_readnode(btree_node_desc* node, void *p)
        !            43: {
        !            44:     node->next     = bswabU32_inc(p);
        !            45:     node->prev     = bswabU32_inc(p);
        !            46:     node->kind     = bswabU8_inc(p);
        !            47:     node->height    = bswabU8_inc(p);
        !            48:     node->num_rec   = bswabU16_inc(p);
        !            49:     node->reserved  = bswabU16_inc(p);
        !            50:     return p;
        !            51: }
        !            52: 
        !            53: /* read a btree header from the given buffer and swap the bytes.
        !            54:  *
        !            55:  * return pointer after reading the structure
        !            56:  */
        !            57: static void* btree_readhead(btree_head* head, void *p)
        !            58: {
        !            59:        UInt32 *q;
        !            60:         head->depth        = bswabU16_inc(p);
        !            61:         head->root         = bswabU32_inc(p);
        !            62:         head->leaf_count    = bswabU32_inc(p);
        !            63:         head->leaf_head            = bswabU32_inc(p);
        !            64:         head->leaf_tail            = bswabU32_inc(p);
        !            65:         head->node_size            = bswabU16_inc(p);
        !            66:         head->max_key_len   = bswabU16_inc(p);
        !            67:         head->node_count    = bswabU32_inc(p);
        !            68:         head->free_nodes    = bswabU32_inc(p);
        !            69:         head->reserved1            = bswabU16_inc(p);
        !            70:         head->clump_size    = bswabU32_inc(p);
        !            71:         head->btree_type    = bswabU8_inc(p);
        !            72:         head->reserved2            = bswabU8_inc(p);
        !            73:         head->attributes    = bswabU32_inc(p);
        !            74:            // skip reserved bytes
        !            75:        q=((UInt32*) p);
        !            76:        // ((UInt32*) p) += 16;
        !            77:        q+=16;
        !            78:        return q;
        !            79: }
        !            80: 
        !            81: /* Priority of the depth of the node compared to LRU value.
        !            82:  * Should be the average number of keys per node but these vary. */
        !            83: #define DEPTH_FACTOR   1000
        !            84: 
        !            85: /* Cache size is height of tree + this value
        !            86:  * Really big numbers wont help in case of ls -R
        !            87:  */
        !            88: #define EXTRA_CACHESIZE        3
        !            89: 
        !            90: /* Not in use by now ... */
        !            91: #define CACHE_DIRTY 0x0001
        !            92: 
        !            93: /* Intialize cache with default cache Size,
        !            94:  * must call node_cache_close to deallocate memory */
        !            95: static int node_cache_init(node_cache* cache, btree* tree, int size)
        !            96: {
        !            97:     int nodebufsize;
        !            98:     char * buf;
        !            99: 
        !           100:     cache->size                = size;
        !           101:     cache->currindex   = 0;
        !           102:     nodebufsize = tree->head.node_size + sizeof(node_buf);
        !           103:     buf = malloc(size *(sizeof(node_entry) + nodebufsize));
        !           104:     if (!buf)
        !           105:        return -1;
        !           106:     cache -> nodebufsize = nodebufsize;
        !           107:     cache -> entries = (node_entry*) buf;
        !           108:     cache -> buffers = (char*) &cache->entries[size];
        !           109:     bzero(cache->entries, size*sizeof(node_entry));
        !           110:     return 0;
        !           111: }
        !           112: 
        !           113: /* Like cache->buffers[i], since size of node_buf is variable */
        !           114: static inline node_buf* node_buf_get(node_cache* cache, int i)
        !           115: {
        !           116:     return (node_buf*) (cache->buffers + (i * cache->nodebufsize));
        !           117: }
        !           118: 
        !           119: /* flush the node at index */
        !           120: static void node_cache_flush_node(node_cache* cache, int index)
        !           121: {
        !           122:     // NYI
        !           123:     cache -> entries[index].index = 0; // invalidate entry
        !           124: }
        !           125: 
        !           126: static void node_cache_close(node_cache* cache)
        !           127: {
        !           128:     if (!cache->entries) // not (fully) intialized ?
        !           129:        return;
        !           130:     free(cache->entries);
        !           131: }
        !           132: 
        !           133: /* Load the cach node indentified by index with
        !           134:  * the node identified by node_index */
        !           135: 
        !           136: static node_buf* node_cache_load_buf
        !           137:     (btree* bt, node_cache* cache, int index, UInt16 node_index)
        !           138: {
        !           139:     node_buf   *result     = node_buf_get(cache ,index);
        !           140:     UInt32     blkpernode  = bt->blkpernode;
        !           141:     UInt32     block       = node_index * blkpernode;
        !           142:     void*      p           = volume_readfromfork(bt->vol, result->node, bt->fork,
        !           143:                             block, blkpernode, HFSP_EXTENT_DATA, bt->cnid);
        !           144:     node_entry *e          = &cache->entries[index];
        !           145: 
        !           146:     if (!p)
        !           147:        return NULL;    // evil ...
        !           148: 
        !           149:     result->index   = node_index;
        !           150:     btree_readnode(&result->desc, p);
        !           151: 
        !           152:     e -> priority   = result->desc.height * DEPTH_FACTOR;
        !           153:     e -> index     = node_index;
        !           154:     return result;
        !           155: }
        !           156: 
        !           157: /* Read node at given index, using cache.
        !           158:  */
        !           159: node_buf* btree_node_by_index(btree* bt, UInt16 index)
        !           160: {
        !           161:     node_cache*        cache = &bt->cache;
        !           162:     int                oldindex, lruindex;
        !           163:     int                currindex = cache->currindex;
        !           164:     UInt32     prio;
        !           165:     node_entry *e;
        !           166: 
        !           167:     // Shortcut acces to current node, will not change priorities
        !           168:     if (cache->entries[currindex].index == index)
        !           169:        return node_buf_get(cache ,currindex);
        !           170:     oldindex = currindex;
        !           171:     if (currindex == 0)
        !           172:        currindex = cache->size;
        !           173:     currindex--;
        !           174:     lruindex = oldindex;           // entry to be flushed when needed
        !           175:     prio     = 0;                  // current priority
        !           176:     while (currindex != oldindex)   // round robin
        !           177:     {
        !           178:        e = &cache->entries[currindex];
        !           179:        if (e->index == index)      // got it
        !           180:        {
        !           181:            if (e->priority != 0)   // already top, uuh
        !           182:                e->priority--;
        !           183:            cache->currindex = currindex;
        !           184:            return node_buf_get(cache ,currindex);
        !           185:        }
        !           186:        else
        !           187:        {
        !           188:            if (!e->index)
        !           189:            {
        !           190:                lruindex = currindex;
        !           191:                break;  // empty entry, load it
        !           192:            }
        !           193:            if (e->priority != UINT_MAX) // already least, uuh
        !           194:                e->priority++;
        !           195:        }
        !           196:        if (prio < e->priority)
        !           197:        {
        !           198:            lruindex = currindex;
        !           199:            prio = e->priority;
        !           200:        }
        !           201:        if (currindex == 0)
        !           202:            currindex = cache->size;
        !           203:        currindex--;
        !           204:     }
        !           205:     e = &cache->entries[lruindex];
        !           206:     cache->currindex = lruindex;
        !           207:     if (e->flags & CACHE_DIRTY)
        !           208:            node_cache_flush_node(    cache, lruindex);
        !           209:     return node_cache_load_buf  (bt, cache, lruindex, index);
        !           210: }
        !           211: 
        !           212: /** intialize the btree with the first entry in the fork */
        !           213: static int btree_init(btree* bt, volume* vol, hfsp_fork_raw* fork)
        !           214: {
        !           215:     void           *p;
        !           216:     char           buf[vol->blksize];
        !           217:     UInt16         node_size;
        !           218:     btree_node_desc node;
        !           219: 
        !           220:     bt->vol    = vol;
        !           221:     bt->fork   = fork;
        !           222:     p  = volume_readfromfork(vol, buf, fork, 0, 1,
        !           223:                 HFSP_EXTENT_DATA, bt->cnid);
        !           224:     if (!p)
        !           225:        return -1;
        !           226:     p = btree_readnode(&node, p);
        !           227:     if (node.kind != HFSP_NODE_HEAD)
        !           228:        return -1;   // should not happen ?
        !           229:     btree_readhead(&bt->head, p);
        !           230: 
        !           231:     node_size = bt->head.node_size;
        !           232:     bt->blkpernode = node_size / vol->blksize;
        !           233: 
        !           234:     if (bt->blkpernode == 0 || vol->blksize *
        !           235:            bt->blkpernode != node_size)
        !           236:        return -1;  // should never happen ...
        !           237: 
        !           238:     node_cache_init(&bt->cache, bt, bt->head.depth + EXTRA_CACHESIZE);
        !           239: 
        !           240:     // Allocate buffer
        !           241:     // bt->buf = malloc(node_size);
        !           242:     // if (!bt->buf)
        !           243:     // return ENOMEM;
        !           244: 
        !           245:     return 0;
        !           246: }
        !           247: 
        !           248: /** Intialize catalog btree, so that btree_close can safely be called. */
        !           249: void btree_reset(btree* bt)
        !           250: {
        !           251:     bt->cache.entries = NULL;
        !           252: }
        !           253: 
        !           254: /** Intialize catalog btree */
        !           255: int btree_init_cat(btree* bt, volume* vol, hfsp_fork_raw* fork)
        !           256: {
        !           257:     int result = btree_init(bt,vol,fork);      // super (...)
        !           258:     bt->cnid  = HFSP_CAT_CNID;
        !           259:     bt->kcomp = record_key_compare;
        !           260:     bt->kread = record_readkey;
        !           261:     return result;
        !           262: }
        !           263: 
        !           264: /** Intialize catalog btree */
        !           265: int btree_init_extent(btree* bt, volume* vol, hfsp_fork_raw* fork)
        !           266: {
        !           267:     int result = btree_init(bt,vol,fork);      // super (...)
        !           268:     bt->cnid  = HFSP_EXT_CNID;
        !           269:     bt->kcomp = record_extent_key_compare;
        !           270:     bt->kread = record_extent_readkey;
        !           271:     return result;
        !           272: }
        !           273: 
        !           274: /** close the btree and free any resources */
        !           275: void btree_close(btree* bt)
        !           276: {
        !           277:     node_cache_close(&bt->cache);
        !           278:     // free(bt->buf);
        !           279: }
        !           280: 
        !           281: /* returns pointer to key given by index in current node.
        !           282:  *
        !           283:  * Assumes that current node is not NODE_HEAD ...
        !           284:  */
        !           285: void* btree_key_by_index(btree* bt, node_buf* buf, UInt16 index)
        !           286: {
        !           287:     UInt16  node_size      = bt->head.node_size;
        !           288:        // The offsets are found at the end of the node ...
        !           289:     UInt16  off_pos        = node_size - (index +1) * sizeof(btree_record_offset);
        !           290:        // position of offset at end of node
        !           291:     btree_record_offset* offset =
        !           292:        (btree_record_offset*) (buf->node + off_pos);
        !           293: 
        !           294:     // now we have the offset and can read the key ...
        !           295: #ifdef CONFIG_LITTLE_ENDIAN
        !           296:     return buf->node + bswabU16(*offset);
        !           297: #else
        !           298:     return buf->node + *offset;
        !           299: #endif
        !           300: }
        !           301: 
        !           302: 
        !           303: #ifdef DEBUG
        !           304: 
        !           305: /* print btree header node information */
        !           306: void btree_printhead(btree_head* head)
        !           307: {
        !           308:     UInt32 attr;
        !           309:     printf("  depth       : %#X\n",  head->depth);
        !           310:     printf("  root        : %#lX\n", head->root);
        !           311:     printf("  leaf_count  : %#lX\n", head->leaf_count);
        !           312:     printf("  leaf_head   : %#lX\n", head->leaf_head);
        !           313:     printf("  leaf_tail   : %#lX\n", head->leaf_tail);
        !           314:     printf("  node_size   : %#X\n",  head->node_size);
        !           315:     printf("  max_key_len : %#X\n",  head->max_key_len);
        !           316:     printf("  node_count  : %#lX\n", head->node_count);
        !           317:     printf("  free_nodes  : %#lX\n", head->free_nodes);
        !           318:     printf("  reserved1   : %#X\n",  head->reserved1);
        !           319:     printf("  clump_size  : %#lX\n", head->clump_size);
        !           320:     printf("  btree_type  : %#X\n",  head->btree_type);
        !           321:     attr = head->attributes;
        !           322:     printf("  reserved2   : %#X\n",  head->reserved2);
        !           323:     if (attr & HFSPLUS_BAD_CLOSE)
        !           324:         printf(" HFSPLUS_BAD_CLOSE *** ");
        !           325:     else
        !           326:         printf(" !HFSPLUS_BAD_CLOSE");
        !           327:     if (attr & HFSPLUS_TREE_BIGKEYS)
        !           328:         printf(" HFSPLUS_TREE_BIGKEYS ");
        !           329:     else
        !           330:         printf("  !HFSPLUS_TREE_BIGKEYS");
        !           331:     if (attr & HFSPLUS_TREE_VAR_NDXKEY_SIZE)
        !           332:         printf(" HFSPLUS_TREE_VAR_NDXKEY_SIZE");
        !           333:     else
        !           334:         printf(" !HFSPLUS_TREE_VAR_NDXKEY_SIZE");
        !           335:     if (attr & HFSPLUS_TREE_UNUSED)
        !           336:         printf(" HFSPLUS_TREE_UNUSED ***\n");
        !           337:     printf("\n");
        !           338: }
        !           339: 
        !           340: /* Dump all the node information to stdout */
        !           341: void btree_print(btree* bt)
        !           342: {
        !           343:     btree_node_desc* node;
        !           344: 
        !           345:     btree_printhead(&bt->head);
        !           346: 
        !           347:     node = &bt->node;
        !           348:     printf("next     : %#lX\n", node->next);
        !           349:     printf("prev     : %#lX\n", node->prev);
        !           350:     printf("height   : %#X\n",  node->height);
        !           351:     printf("num_rec  : %#X\n",  node->num_rec);
        !           352:     printf("reserved : %#X\n",  node->reserved);
        !           353:     printf("height   : %#X\n",  node->height);                                      switch(node->kind)
        !           354:     {
        !           355:        case HFSP_NODE_NDX  :
        !           356:            printf("HFSP_NODE_NDX\n");
        !           357:            break;
        !           358:        case HFSP_NODE_HEAD :
        !           359:            printf("HFSP_NODE_HEAD\n");
        !           360:            break;
        !           361:        case HFSP_NODE_MAP  :
        !           362:            printf("HFSP_NODE_MAP\n");
        !           363:            break;
        !           364:        case HFSP_NODE_LEAF :
        !           365:            printf("HFSP_NODE_LEAF\n");
        !           366:            break;
        !           367:        default:
        !           368:            printf("*** Unknown Node type ***\n");
        !           369:     }
        !           370: }
        !           371: 
        !           372: #endif

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.