fs/hfsplus/btree.h

/*
 * libhfs - library for reading and writing Macintosh HFS volumes.
 *
 * The fucntions are used to handle the various forms of btrees
 * found on HFS+ volumes.
 *
 * Copyright (C) 2000 Klaus Halfmann <klaus.halfmann@feri.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., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 */

/* Read the node from the given buffer and swap the bytes.
 *
 * return pointer after reading the structure
 */
char* btree_readnode(btree_node_desc* node, char *p);

/* read a btree header from the given buffer and swap the bytes.
 *
 * return pointer after reading the structure
 */
char* btree_readhead(btree_head* head, char *p);

/** Intialize catalog btree, so that btree_close can safely be called. */
extern void btree_reset(btree* bt);

/** Intialize catalog btree */
extern int btree_init_cat(btree* bt, volume* vol, hfsp_fork_raw* fork);

/** Intialize extents btree */
extern int btree_init_extent(btree* bt, volume* vol, hfsp_fork_raw* fork);

/** close the btree and free any resources */
extern int btree_close(btree* bt);

/* Read node at given index.
 *
 * Make node with given flag, usually NODE_CLEAN/NODE_DIRTY
 */
extern node_buf* btree_node_by_index(btree* bt, UInt16 index, int flags);

/* returns pointer to key given by index in current node */
extern void* btree_key_by_index(btree* bt, node_buf* buf, UInt16 index);

/* remove the key and record from the btree.
 * Warning, you must WRITELOCK the btree before calling this */
extern int btree_remove_record(btree* bt, UInt16 node_index, UInt16 recind);

/* insert a key and an (eventual) record into the btree.
 * Warning, you must WRITELOCK the btree before calling this */
extern int btree_insert_record(btree* bt, UInt16 node_index, UInt16 keyind,
                        void* key, int len);

// --------------- Cache Handling ------------

/* 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
 * Must be enough to cache all nodes (+ Map nodes !)
 * used during tree reorganizations to avoid
 * inconsistent states before flush
 */
#define EXTRA_CACHESIZE 3 

/* Intialize cache with default cache Size, 
 * must call node_cache_close to deallocate memory */
extern int node_cache_init(node_cache* cache, btree* tree, int size);

/** return allocation status of node given by index in btree */
extern int btree_check_nodealloc(btree* bt, UInt16 node);

1	dpavlin	1	/*
2			* libhfs - library for reading and writing Macintosh HFS volumes.
3			*
4			* The fucntions are used to handle the various forms of btrees
5			* found on HFS+ volumes.
6			*
7			* Copyright (C) 2000 Klaus Halfmann <klaus.halfmann@feri.de>
8			* Original 1996-1998 Robert Leslie <rob@mars.org>
9			* Additional work by Brad Boyer (flar@pants.nu)
10			*
11			* This program is free software; you can redistribute it and/or modify
12			* it under the terms of the GNU General Public License as published by
13			* the Free Software Foundation; either version 2 of the License, or
14			* (at your option) any later version.
15			*
16			* This program is distributed in the hope that it will be useful,
17			* but WITHOUT ANY WARRANTY; without even the implied warranty of
18			* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19			* GNU General Public License for more details.
20			*
21			* You should have received a copy of the GNU General Public License
22			* along with this program; if not, write to the Free Software
23			* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
24			*
25			*/
26
27			/* Read the node from the given buffer and swap the bytes.
28			*
29			* return pointer after reading the structure
30			*/
31			char* btree_readnode(btree_node_desc* node, char *p);
32
33			/* read a btree header from the given buffer and swap the bytes.
34			*
35			* return pointer after reading the structure
36			*/
37			char* btree_readhead(btree_head* head, char *p);
38
39			/** Intialize catalog btree, so that btree_close can safely be called. */
40			extern void btree_reset(btree* bt);
41
42			/** Intialize catalog btree */
43			extern int btree_init_cat(btree* bt, volume* vol, hfsp_fork_raw* fork);
44
45			/** Intialize extents btree */
46			extern int btree_init_extent(btree* bt, volume* vol, hfsp_fork_raw* fork);
47
48			/** close the btree and free any resources */
49			extern int btree_close(btree* bt);
50
51			/* Read node at given index.
52			*
53			* Make node with given flag, usually NODE_CLEAN/NODE_DIRTY
54			*/
55			extern node_buf* btree_node_by_index(btree* bt, UInt16 index, int flags);
56
57			/* returns pointer to key given by index in current node */
58			extern void* btree_key_by_index(btree* bt, node_buf* buf, UInt16 index);
59
60			/* remove the key and record from the btree.
61			* Warning, you must WRITELOCK the btree before calling this */
62			extern int btree_remove_record(btree* bt, UInt16 node_index, UInt16 recind);
63
64			/* insert a key and an (eventual) record into the btree.
65			* Warning, you must WRITELOCK the btree before calling this */
66			extern int btree_insert_record(btree* bt, UInt16 node_index, UInt16 keyind,
67			void* key, int len);
68
69			// --------------- Cache Handling ------------
70
71			/* Priority of the depth of the node compared to LRU value.
72			* Should be the average number of keys per node but these vary. */
73			#define DEPTH_FACTOR 1000
74
75			/* Cache size is height of tree + this value
76			* Really big numbers wont help in case of ls -R
77			* Must be enough to cache all nodes (+ Map nodes !)
78			* used during tree reorganizations to avoid
79			* inconsistent states before flush
80			*/
81			#define EXTRA_CACHESIZE 3
82
83			/* Intialize cache with default cache Size,
84			* must call node_cache_close to deallocate memory */
85			extern int node_cache_init(node_cache* cache, btree* tree, int size);
86
87			/** return allocation status of node given by index in btree */
88			extern int btree_check_nodealloc(btree* bt, UInt16 node);
89