~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/hfs/btree.h

Version: ~ [ linux-5.2-rc5 ] ~ [ linux-5.1.12 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.53 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.128 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.182 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.182 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.68 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.39.4 ] ~ [ linux-2.6.38.8 ] ~ [ linux-2.6.37.6 ] ~ [ linux-2.6.36.4 ] ~ [ linux-2.6.35.14 ] ~ [ linux-2.6.34.15 ] ~ [ linux-2.6.33.20 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

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

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp