fs/hfs/hfs_btree.h

   1 /*
   2  * linux/fs/hfs/hfs_btree.h
   3  *
   4  * Copyright (C) 1995-1997  Paul H. Hargrove
   5  * This file may be distributed under the terms of the GNU General Public License.
   6  *
   7  * This file contains the declarations of the private B-tree
   8  * structures and functions.
   9  *
  10  * "XXX" in a comment is a note to myself to consider changing something.
  11  */
  12
  13 #ifndef _HFS_BTREE_H
  14 #define _HFS_BTREE_H
  15
  16 #include "hfs.h"
  17
  18 /*================ Variable-like macros ================*/
  19
  20 /* The stickiness of a (struct hfs_bnode) */
  21 #define HFS_NOT_STICKY  0
  22 #define HFS_STICKY      1
  23
  24 /* The number of hash buckets in a B-tree's bnode cache */
  25 #define HFS_CACHELEN    17      /* primes are best? */
  26
  27 /*
  28  * Legal values for the 'ndType' field of a (struct NodeDescriptor)
  29  *
  30  * Reference: _Inside Macintosh: Files_ p. 2-65
  31  */
  32 #define ndIndxNode      0x00    /* An internal (index) node */
  33 #define ndHdrNode       0x01    /* The tree header node (node 0) */
  34 #define ndMapNode       0x02    /* Holds part of the bitmap of used nodes */
  35 #define ndLeafNode      0xFF    /* A leaf (ndNHeight==1) node */
  36
  37 /*
  38  * Legal values for the bthAtrb field of a (struct BTHdrRec)
  39  *
  40  * Reference: TN 1150
  41  */
  42 #define bthBadClose     0x00000001  /* b-tree not closed properly. not
  43                                        used by hfsplus. */
  44 #define bthBigKeys      0x00000002  /* key length is u16 instead of u8.
  45                                        used by hfsplus. */
  46 #define bthVarIndxKeys  0x00000004  /* variable key length instead of
  47                                        max key length. use din catalog
  48                                        b-tree but not in extents
  49                                        b-tree (hfsplus). */
  50
  51 /*================ Function-like macros ================*/
  52
  53 /* Access the cache slot which should contain the desired node */
  54 #define bhash(tree, node) ((tree)->cache[(node) % HFS_CACHELEN])
  55
  56 /* round up to multiple of sizeof(hfs_u16) */
  57 #define ROUND(X) ((X + sizeof(hfs_u16) - 1) & ~(sizeof(hfs_u16)-1))
  58
  59 /* Refer to the (base-1) array of offsets in a bnode */
  60 #define RECTBL(X,N) \
  61         (((hfs_u16 *)(hfs_buffer_data((X)->buf)+HFS_SECTOR_SIZE))-(N))
  62
  63 /*================ Private data types ================*/
  64
  65 /*
  66  * struct BTHdrRec
  67  *
  68  * The B-tree header record
  69  *
  70  * This data structure is stored in the first node (512-byte block) of
  71  * each B-tree file.  It contains important information about the
  72  * B-tree.  Most fields vary over the life of the tree and are
  73  * indicated by a 'V' in the comments.  The other fields are fixed for
  74  * the life of the tree and are indicated by a 'F'.
  75  *
  76  * Reference: _Inside Macintosh: Files_ pp. 2-68 through 2-69 */
  77 struct BTHdrRec {
  78         hfs_word_t  bthDepth;   /* (V) The number of levels in this B-tree */
  79         hfs_lword_t bthRoot;    /* (V) The node number of the root node */
  80         hfs_lword_t bthNRecs;   /* (V) The number of leaf records */
  81         hfs_lword_t bthFNode;   /* (V) The number of the first leaf node */
  82         hfs_lword_t bthLNode;   /* (V) The number of the last leaf node */
  83         hfs_word_t  bthNodeSize;        /* (F) The number of bytes in a node (=512) */
  84         hfs_word_t  bthKeyLen;  /* (F) The length of a key in an index node */
  85         hfs_lword_t bthNNodes;  /* (V) The total number of nodes */
  86         hfs_lword_t bthFree;    /* (V) The number of unused nodes */
  87         hfs_word_t  bthResv1;   /* reserved */
  88         hfs_lword_t bthClpSiz;  /* (F) clump size. not usually used. */
  89         hfs_byte_t  bthType;    /* (F) BTree type */
  90         hfs_byte_t  bthResv2;   /* reserved */
  91         hfs_lword_t bthAtrb;    /* (F) attributes */
  92         hfs_lword_t bthResv3[16]; /* Reserved */
  93 } __attribute__((packed));
  94
  95 /*
  96  * struct NodeDescriptor
  97  *
  98  * The B-tree node descriptor.
  99  *
 100  * This structure begins each node in the B-tree file.  It contains
 101  * important information about the node's contents.  'V' and 'F' in
 102  * the comments indicate fields that are variable or fixed over the
 103  * life of a node, where the 'life' of a node is defined as the period
 104  * between leaving and reentering the free pool.
 105  *
 106  * Reference: _Inside Macintosh: Files_ p. 2-64
 107  */
 108 struct NodeDescriptor {
 109         hfs_lword_t ndFLink;    /* (V) Number of the next node at this level */
 110         hfs_lword_t ndBLink;    /* (V) Number of the prev node at this level */
 111         hfs_byte_t  ndType;     /* (F) The type of node */
 112         hfs_byte_t  ndNHeight;  /* (F) The level of this node (leaves=1) */
 113         hfs_word_t  ndNRecs;    /* (V) The number of records in this node */
 114         hfs_word_t  ndResv2;    /* Reserved */
 115 } __attribute__((packed));
 116
 117 /*
 118  * typedef hfs_cmpfn
 119  *
 120  * The type 'hfs_cmpfn' is a comparison function taking 2 keys and
 121  * returning a positive, negative or zero integer according to the
 122  * ordering of the two keys (just like strcmp() does for strings).
 123  */
 124 typedef int (*hfs_cmpfn)(const void *, const void *);
 125
 126 /*
 127  * struct hfs_bnode
 128  *
 129  * An in-core B-tree node
 130  *
 131  * This structure holds information from the NodeDescriptor in native
 132  * byte-order, a pointer to the buffer which contains the actual
 133  * node and fields necessary for locking access to the node during
 134  * updates.  The use of the locking fields is explained with the
 135  * locking functions.
 136  */
 137 struct hfs_bnode {
 138         int                 magic;   /* Magic number to guard against
 139                                         wild pointers */
 140         hfs_buffer          buf;     /* The buffer containing the
 141                                         actual node */
 142         struct hfs_btree    *tree;   /* The tree to which this node
 143                                         belongs */
 144         struct hfs_bnode    *prev;   /* Next node in this hash bucket */
 145         struct hfs_bnode    *next;   /* Previous node in this hash
 146                                         bucket */
 147         int                 sticky;  /* Boolean: non-zero means keep
 148                                         this node in-core (set for
 149                                         root and head) */
 150         hfs_u32             node;    /* Node number */
 151         hfs_u16             nodeSize; /* node size */
 152         hfs_u16             keyLen;  /* key length */
 153         /* locking related fields: */
 154         hfs_wait_queue      wqueue;  /* Wait queue for write access */
 155         hfs_wait_queue      rqueue;  /* Wait queue for read or reserve
 156                                         access */
 157         int                 count;   /* Number of processes accessing
 158                                         this node */
 159         int                 resrv;   /* Boolean, true means a process
 160                                         had placed a 'reservation' on
 161                                         this node */
 162         int                 lock;    /* Boolean, true means some
 163                                         process has exclusive access,
 164                                         so KEEP OUT */
 165         /* fields from the NodeDescriptor in native byte-order: */
 166         hfs_u32             ndFLink;
 167         hfs_u32             ndBLink;
 168         hfs_u16             ndNRecs;
 169         hfs_u8              ndType;
 170         hfs_u8              ndNHeight;
 171 };
 172
 173 /*
 174  * struct hfs_btree
 175  *
 176  * An in-core B-tree.
 177  *
 178  * This structure holds information from the BTHdrRec, MDB
 179  * (superblock) and other information needed to work with the B-tree.
 180  */
 181 struct hfs_btree {
 182         int                     magic;         /* Magic number to
 183                                                   guard against wild
 184                                                   pointers */
 185         hfs_cmpfn               compare;       /* Comparison function
 186                                                   for this tree */
 187         struct hfs_bnode        head;          /* in-core copy of node 0 */
 188         struct hfs_bnode        *root;         /* Pointer to the in-core
 189                                                   copy of the root node */
 190         hfs_sysmdb              sys_mdb;       /* The "device" holding
 191                                                   the filesystem */
 192         int                     reserved;      /* bnodes claimed but
 193                                                   not yet used */
 194         struct hfs_bnode                       /* The bnode cache */
 195                                 *cache[HFS_CACHELEN];
 196         struct hfs_cat_entry    entry;         /* Fake catalog entry */
 197         int                     lock;
 198         hfs_wait_queue          wait;
 199         int                     dirt;
 200         int                     keySize;
 201         /* Fields from the BTHdrRec in native byte-order: */
 202         hfs_u32                 bthRoot;
 203         hfs_u32                 bthNRecs;
 204         hfs_u32                 bthFNode;
 205         hfs_u32                 bthLNode;
 206         hfs_u32                 bthNNodes;
 207         hfs_u32                 bthFree;
 208         hfs_u16                 bthKeyLen;
 209         hfs_u16                 bthDepth;
 210 };
 211
 212 /*================ Global functions ================*/
 213
 214 /* Convert a (struct hfs_bnode *) and an index to the value of the
 215    n-th offset in the bnode (N >= 1) to the offset */
 216 extern inline hfs_u16 bnode_offset(const struct hfs_bnode *bnode, int n)
 217 { return hfs_get_hs(RECTBL(bnode,n)); }
 218
 219 /* Convert a (struct hfs_bnode *) and an index to the size of the
 220    n-th record in the bnode (N >= 1) */
 221 extern inline hfs_u16 bnode_rsize(const struct hfs_bnode *bnode, int n)
 222 { return bnode_offset(bnode, n+1) - bnode_offset(bnode, n); }
 223
 224 /* Convert a (struct hfs_bnode *) to the offset of the empty part */
 225 extern inline hfs_u16 bnode_end(const struct hfs_bnode *bnode)
 226 { return bnode_offset(bnode, bnode->ndNRecs + 1); }
 227
 228 /* Convert a (struct hfs_bnode *) to the number of free bytes it contains */
 229 extern inline hfs_u16 bnode_freespace(const struct hfs_bnode *bnode)
 230 { return HFS_SECTOR_SIZE - bnode_end(bnode)
 231           - (bnode->ndNRecs + 1)*sizeof(hfs_u16); }
 232
 233 /* Convert a (struct hfs_bnode *) X and an index N to
 234    the address of the record N in the bnode (N >= 1) */
 235 extern inline void *bnode_datastart(const struct hfs_bnode *bnode)
 236 { return (void *)(hfs_buffer_data(bnode->buf)+sizeof(struct NodeDescriptor)); }
 237
 238 /* Convert a (struct hfs_bnode *) to the address of the empty part */
 239 extern inline void *bnode_dataend(const struct hfs_bnode *bnode)
 240 { return (void *)(hfs_buffer_data(bnode->buf) + bnode_end(bnode)); }
 241
 242 /* Convert various pointers to address of record's key */
 243 extern inline void *bnode_key(const struct hfs_bnode *bnode, int n)
 244 { return (void *)(hfs_buffer_data(bnode->buf) + bnode_offset(bnode, n)); }
 245 extern inline void *belem_key(const struct hfs_belem *elem)
 246 { return bnode_key(elem->bnr.bn, elem->record); }
 247 extern inline void *brec_key(const struct hfs_brec *brec)
 248 { return belem_key(brec->bottom); }
 249
 250 /* Convert various pointers to the address of a record */
 251 extern inline void *bkey_record(const struct hfs_bkey *key)
 252 { return (void *)key + ROUND(key->KeyLen + 1); }
 253 extern inline void *bnode_record(const struct hfs_bnode *bnode, int n)
 254 { return bkey_record(bnode_key(bnode, n)); }
 255 extern inline void *belem_record(const struct hfs_belem *elem)
 256 { return bkey_record(belem_key(elem)); }
 257 extern inline void *brec_record(const struct hfs_brec *brec)
 258 { return bkey_record(brec_key(brec)); }
 259
 260 /*================ Function Prototypes ================*/
 261
 262 /* balloc.c */
 263 extern int hfs_bnode_bitop(struct hfs_btree *, hfs_u32, int);
 264 extern struct hfs_bnode_ref hfs_bnode_alloc(struct hfs_btree *);
 265 extern int hfs_bnode_free(struct hfs_bnode_ref *);
 266 extern void hfs_btree_extend(struct hfs_btree *);
 267
 268 /* bins_del.c */
 269 extern void hfs_bnode_update_key(struct hfs_brec *, struct hfs_belem *,
 270                                  struct hfs_bnode *, int);
 271 extern void hfs_bnode_shift_right(struct hfs_bnode *, struct hfs_bnode *, int);
 272 extern void hfs_bnode_shift_left(struct hfs_bnode *, struct hfs_bnode *, int);
 273 extern int hfs_bnode_in_brec(hfs_u32 node, const struct hfs_brec *brec);
 274
 275 /* bnode.c */
 276 extern void hfs_bnode_read(struct hfs_bnode *, struct hfs_btree *,
 277                            hfs_u32, int);
 278 extern void hfs_bnode_relse(struct hfs_bnode_ref *);
 279 extern struct hfs_bnode_ref hfs_bnode_find(struct hfs_btree *, hfs_u32, int);
 280 extern void hfs_bnode_lock(struct hfs_bnode_ref *, int);
 281 extern void hfs_bnode_delete(struct hfs_bnode *);
 282 extern void hfs_bnode_commit(struct hfs_bnode *);
 283
 284 /* brec.c */
 285 extern void hfs_brec_lock(struct hfs_brec *, struct hfs_belem *);
 286 extern struct hfs_belem *hfs_brec_init(struct hfs_brec *, struct hfs_btree *,
 287                                        int);
 288 extern struct hfs_belem *hfs_brec_next(struct hfs_brec *);
 289
 290 #endif