![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to hfsp_btree.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Qemu by Fabrice Bellard] / qemu / roms / openbios / fs / hfsplus|
Return to hfsp_btree.c CVS log | Up to [Qemu by Fabrice Bellard] / qemu / roms / openbios / fs / hfsplus |
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.