[linux.git] / fs / hfs / btree.h

/* SPDX-License-Identifier: GPL-2.0 */
/*
 *  linux/fs/hfs/btree.h
 *
 * Copyright (C) 2001
 * Brad Boyer ([email protected])
 * (C) 2003 Ardis Technologies <[email protected]>
 */

#include "hfs_fs.h"

typedef int (*btree_keycmp)(const btree_key *, const btree_key *);

#define NODE_HASH_SIZE  256

/* B-tree mutex nested subclasses */
enum hfs_btree_mutex_classes {
	CATALOG_BTREE_MUTEX,
	EXTENTS_BTREE_MUTEX,
	ATTR_BTREE_MUTEX,
};

/* A HFS BTree held in memory */
struct hfs_btree {
	struct super_block *sb;
	struct inode *inode;
	btree_keycmp keycmp;

	u32 cnid;
	u32 root;
	u32 leaf_count;
	u32 leaf_head;
	u32 leaf_tail;
	u32 node_count;
	u32 free_nodes;
	u32 attributes;

	unsigned int node_size;
	unsigned int node_size_shift;
	unsigned int max_key_len;
	unsigned int depth;

	//unsigned int map1_size, map_size;
	struct mutex tree_lock;

	unsigned int pages_per_bnode;
	spinlock_t hash_lock;
	struct hfs_bnode *node_hash[NODE_HASH_SIZE];
	int node_hash_cnt;
};

/* A HFS BTree node in memory */
struct hfs_bnode {
	struct hfs_btree *tree;

	u32 prev;
	u32 this;
	u32 next;
	u32 parent;

	u16 num_recs;
	u8 type;
	u8 height;

	struct hfs_bnode *next_hash;
	unsigned long flags;
	wait_queue_head_t lock_wq;
	atomic_t refcnt;
	unsigned int page_offset;
	struct page *page[];
};

#define HFS_BNODE_ERROR		0
#define HFS_BNODE_NEW		1
#define HFS_BNODE_DELETED	2

struct hfs_find_data {
	btree_key *key;
	btree_key *search_key;
	struct hfs_btree *tree;
	struct hfs_bnode *bnode;
	int record;
	int keyoffset, keylength;
	int entryoffset, entrylength;
};


/* btree.c */
extern struct hfs_btree *hfs_btree_open(struct super_block *, u32, btree_keycmp);
extern void hfs_btree_close(struct hfs_btree *);
extern void hfs_btree_write(struct hfs_btree *);
extern int hfs_bmap_reserve(struct hfs_btree *, int);
extern struct hfs_bnode * hfs_bmap_alloc(struct hfs_btree *);
extern void hfs_bmap_free(struct hfs_bnode *node);

/* bnode.c */
extern void hfs_bnode_read(struct hfs_bnode *, void *, int, int);
extern u16 hfs_bnode_read_u16(struct hfs_bnode *, int);
extern u8 hfs_bnode_read_u8(struct hfs_bnode *, int);
extern void hfs_bnode_read_key(struct hfs_bnode *, void *, int);
extern void hfs_bnode_write(struct hfs_bnode *, void *, int, int);
extern void hfs_bnode_write_u16(struct hfs_bnode *, int, u16);
extern void hfs_bnode_write_u8(struct hfs_bnode *, int, u8);
extern void hfs_bnode_clear(struct hfs_bnode *, int, int);
extern void hfs_bnode_copy(struct hfs_bnode *, int,
			   struct hfs_bnode *, int, int);
extern void hfs_bnode_move(struct hfs_bnode *, int, int, int);
extern void hfs_bnode_dump(struct hfs_bnode *);
extern void hfs_bnode_unlink(struct hfs_bnode *);
extern struct hfs_bnode *hfs_bnode_findhash(struct hfs_btree *, u32);
extern struct hfs_bnode *hfs_bnode_find(struct hfs_btree *, u32);
extern void hfs_bnode_unhash(struct hfs_bnode *);
extern void hfs_bnode_free(struct hfs_bnode *);
extern struct hfs_bnode *hfs_bnode_create(struct hfs_btree *, u32);
extern void hfs_bnode_get(struct hfs_bnode *);
extern void hfs_bnode_put(struct hfs_bnode *);

/* brec.c */
extern u16 hfs_brec_lenoff(struct hfs_bnode *, u16, u16 *);
extern u16 hfs_brec_keylen(struct hfs_bnode *, u16);
extern int hfs_brec_insert(struct hfs_find_data *, void *, int);
extern int hfs_brec_remove(struct hfs_find_data *);

/* bfind.c */
extern int hfs_find_init(struct hfs_btree *, struct hfs_find_data *);
extern void hfs_find_exit(struct hfs_find_data *);
extern int __hfs_brec_find(struct hfs_bnode *, struct hfs_find_data *);
extern int hfs_brec_find(struct hfs_find_data *);
extern int hfs_brec_read(struct hfs_find_data *, void *, int);
extern int hfs_brec_goto(struct hfs_find_data *, int);


struct hfs_bnode_desc {
	__be32 next;		/* (V) Number of the next node at this level */
	__be32 prev;		/* (V) Number of the prev node at this level */
	u8 type;		/* (F) The type of node */
	u8 height;		/* (F) The level of this node (leaves=1) */
	__be16 num_recs;	/* (V) The number of records in this node */
	u16 reserved;
} __packed;

#define HFS_NODE_INDEX	0x00	/* An internal (index) node */
#define HFS_NODE_HEADER	0x01	/* The tree header node (node 0) */
#define HFS_NODE_MAP	0x02	/* Holds part of the bitmap of used nodes */
#define HFS_NODE_LEAF	0xFF	/* A leaf (ndNHeight==1) node */

struct hfs_btree_header_rec {
	__be16 depth;		/* (V) The number of levels in this B-tree */
	__be32 root;		/* (V) The node number of the root node */
	__be32 leaf_count;	/* (V) The number of leaf records */
	__be32 leaf_head;	/* (V) The number of the first leaf node */
	__be32 leaf_tail;	/* (V) The number of the last leaf node */
	__be16 node_size;	/* (F) The number of bytes in a node (=512) */
	__be16 max_key_len;	/* (F) The length of a key in an index node */
	__be32 node_count;	/* (V) The total number of nodes */
	__be32 free_nodes;	/* (V) The number of unused nodes */
	u16 reserved1;
	__be32 clump_size;	/* (F) clump size. not usually used. */
	u8 btree_type;		/* (F) BTree type */
	u8 reserved2;
	__be32 attributes;	/* (F) attributes */
	u32 reserved3[16];
} __packed;

#define BTREE_ATTR_BADCLOSE	0x00000001	/* b-tree not closed properly. not
						   used by hfsplus. */
#define HFS_TREE_BIGKEYS	0x00000002	/* key length is u16 instead of u8.
						   used by hfsplus. */
#define HFS_TREE_VARIDXKEYS	0x00000004	/* variable key length instead of
						   max key length. use din catalog
						   b-tree but not in extents
						   b-tree (hfsplus). */
Commit	Line	Data
b2441318	1	/* SPDX-License-Identifier: GPL-2.0 */
1da177e4 LT	2	/*
	3	* linux/fs/hfs/btree.h
	4	*
	5	* Copyright (C) 2001
	6	* Brad Boyer ([email protected])
	7	* (C) 2003 Ardis Technologies <[email protected]>
	8	*/
	9
	10	#include "hfs_fs.h"
	11
	12	typedef int (btree_keycmp)(const btree_key , const btree_key *);
	13
	14	#define NODE_HASH_SIZE 256
	15
b3b2177a DCZX	16	/* B-tree mutex nested subclasses */
	17	enum hfs_btree_mutex_classes {
	18	CATALOG_BTREE_MUTEX,
	19	EXTENTS_BTREE_MUTEX,
	20	ATTR_BTREE_MUTEX,
	21	};
	22
1da177e4 LT	23	/* A HFS BTree held in memory */
	24	struct hfs_btree {
	25	struct super_block *sb;
	26	struct inode *inode;
	27	btree_keycmp keycmp;
	28
	29	u32 cnid;
	30	u32 root;
	31	u32 leaf_count;
	32	u32 leaf_head;
	33	u32 leaf_tail;
	34	u32 node_count;
	35	u32 free_nodes;
	36	u32 attributes;
	37
	38	unsigned int node_size;
	39	unsigned int node_size_shift;
	40	unsigned int max_key_len;
	41	unsigned int depth;
	42
	43	//unsigned int map1_size, map_size;
4a941035	44	struct mutex tree_lock;
1da177e4 LT	45
	46	unsigned int pages_per_bnode;
	47	spinlock_t hash_lock;
	48	struct hfs_bnode *node_hash[NODE_HASH_SIZE];
	49	int node_hash_cnt;
	50	};
	51
	52	/* A HFS BTree node in memory */
	53	struct hfs_bnode {
	54	struct hfs_btree *tree;
	55
	56	u32 prev;
	57	u32 this;
	58	u32 next;
	59	u32 parent;
	60
	61	u16 num_recs;
	62	u8 type;
	63	u8 height;
	64
	65	struct hfs_bnode *next_hash;
	66	unsigned long flags;
	67	wait_queue_head_t lock_wq;
	68	atomic_t refcnt;
	69	unsigned int page_offset;
5e01fdff	70	struct page *page[];
1da177e4 LT	71	};
	72
	73	#define HFS_BNODE_ERROR 0
	74	#define HFS_BNODE_NEW 1
	75	#define HFS_BNODE_DELETED 2
	76
	77	struct hfs_find_data {
	78	btree_key *key;
	79	btree_key *search_key;
	80	struct hfs_btree *tree;
	81	struct hfs_bnode *bnode;
	82	int record;
	83	int keyoffset, keylength;
	84	int entryoffset, entrylength;
	85	};
	86
	87
	88	/* btree.c */
	89	extern struct hfs_btree hfs_btree_open(struct super_block , u32, btree_keycmp);
	90	extern void hfs_btree_close(struct hfs_btree *);
	91	extern void hfs_btree_write(struct hfs_btree *);
54640c75	92	extern int hfs_bmap_reserve(struct hfs_btree *, int);
1da177e4 LT	93	extern struct hfs_bnode * hfs_bmap_alloc(struct hfs_btree *);
	94	extern void hfs_bmap_free(struct hfs_bnode *node);
	95
	96	/* bnode.c */
	97	extern void hfs_bnode_read(struct hfs_bnode , void , int, int);
	98	extern u16 hfs_bnode_read_u16(struct hfs_bnode *, int);
	99	extern u8 hfs_bnode_read_u8(struct hfs_bnode *, int);
	100	extern void hfs_bnode_read_key(struct hfs_bnode , void , int);
	101	extern void hfs_bnode_write(struct hfs_bnode , void , int, int);
	102	extern void hfs_bnode_write_u16(struct hfs_bnode *, int, u16);
	103	extern void hfs_bnode_write_u8(struct hfs_bnode *, int, u8);
	104	extern void hfs_bnode_clear(struct hfs_bnode *, int, int);
	105	extern void hfs_bnode_copy(struct hfs_bnode *, int,
	106	struct hfs_bnode *, int, int);
	107	extern void hfs_bnode_move(struct hfs_bnode *, int, int, int);
	108	extern void hfs_bnode_dump(struct hfs_bnode *);
	109	extern void hfs_bnode_unlink(struct hfs_bnode *);
	110	extern struct hfs_bnode hfs_bnode_findhash(struct hfs_btree , u32);
	111	extern struct hfs_bnode hfs_bnode_find(struct hfs_btree , u32);
	112	extern void hfs_bnode_unhash(struct hfs_bnode *);
	113	extern void hfs_bnode_free(struct hfs_bnode *);
	114	extern struct hfs_bnode hfs_bnode_create(struct hfs_btree , u32);
	115	extern void hfs_bnode_get(struct hfs_bnode *);
	116	extern void hfs_bnode_put(struct hfs_bnode *);
	117
	118	/* brec.c */
	119	extern u16 hfs_brec_lenoff(struct hfs_bnode , u16, u16 );
	120	extern u16 hfs_brec_keylen(struct hfs_bnode *, u16);
	121	extern int hfs_brec_insert(struct hfs_find_data , void , int);
	122	extern int hfs_brec_remove(struct hfs_find_data *);
	123
	124	/* bfind.c */
	125	extern int hfs_find_init(struct hfs_btree , struct hfs_find_data );
	126	extern void hfs_find_exit(struct hfs_find_data *);
	127	extern int __hfs_brec_find(struct hfs_bnode , struct hfs_find_data );
	128	extern int hfs_brec_find(struct hfs_find_data *);
	129	extern int hfs_brec_read(struct hfs_find_data , void , int);
	130	extern int hfs_brec_goto(struct hfs_find_data *, int);
	131
	132
	133	struct hfs_bnode_desc {
	134	__be32 next; /* (V) Number of the next node at this level */
	135	__be32 prev; /* (V) Number of the prev node at this level */
	136	u8 type; /* (F) The type of node */
	137	u8 height; /* (F) The level of this node (leaves=1) */
	138	__be16 num_recs; /* (V) The number of records in this node */
	139	u16 reserved;
	140	} __packed;
	141
	142	#define HFS_NODE_INDEX 0x00 /* An internal (index) node */
	143	#define HFS_NODE_HEADER 0x01 /* The tree header node (node 0) */
	144	#define HFS_NODE_MAP 0x02 /* Holds part of the bitmap of used nodes */
	145	#define HFS_NODE_LEAF 0xFF /* A leaf (ndNHeight==1) node */
	146
	147	struct hfs_btree_header_rec {
	148	__be16 depth; /* (V) The number of levels in this B-tree */
	149	__be32 root; /* (V) The node number of the root node */
	150	__be32 leaf_count; /* (V) The number of leaf records */
	151	__be32 leaf_head; /* (V) The number of the first leaf node */
	152	__be32 leaf_tail; /* (V) The number of the last leaf node */
	153	__be16 node_size; /* (F) The number of bytes in a node (=512) */
	154	__be16 max_key_len; /* (F) The length of a key in an index node */
	155	__be32 node_count; /* (V) The total number of nodes */
	156	__be32 free_nodes; /* (V) The number of unused nodes */
157	u16 reserved1;
158	__be32 clump_size; /* (F) clump size. not usually used. */
159	u8 btree_type; /* (F) BTree type */
160	u8 reserved2;
161	__be32 attributes; /* (F) attributes */
162	u32 reserved3[16];
163	} __packed;
164
1da177e4 LT	165	#define BTREE_ATTR_BADCLOSE 0x00000001 /* b-tree not closed properly. not
	166	used by hfsplus. */
	167	#define HFS_TREE_BIGKEYS 0x00000002 /* key length is u16 instead of u8.
	168	used by hfsplus. */
	169	#define HFS_TREE_VARIDXKEYS 0x00000004 /* variable key length instead of
	170	max key length. use din catalog
	171	b-tree but not in extents
	172	b-tree (hfsplus). */