fs/hfsplus/bfind.c

   1 /*
   2  *  linux/fs/hfsplus/bfind.c
   3  *
   4  * Copyright (C) 2001
   5  * Brad Boyer (flar@allandria.com)
   6  * (C) 2003 Ardis Technologies <roman@ardistech.com>
   7  *
   8  * Search routines for btrees
   9  */
  10
  11 #include <linux/slab.h>
  12 #include "hfsplus_fs.h"
  13
  14 /* Find the record in bnode that best matches key (not greater than...)*/
  15 void hfsplus_find_rec(hfsplus_bnode *bnode, struct hfsplus_find_data *fd)
  16 {
  17         int cmpval;
  18         u16 off, len, keylen;
  19         int rec;
  20         int b, e;
  21
  22         b = 0;
  23         e = bnode->num_recs - 1;
  24         do {
  25                 rec = (e + b) / 2;
  26                 len = hfsplus_brec_lenoff(bnode, rec, &off);
  27                 keylen = hfsplus_brec_keylen(bnode, rec);
  28                 hfsplus_bnode_readbytes(bnode, fd->key, off, keylen);
  29                 cmpval = bnode->tree->keycmp(fd->key, fd->search_key);
  30                 if (!cmpval) {
  31                         fd->exact = 1;
  32                         e = rec;
  33                         break;
  34                 }
  35                 if (cmpval < 0)
  36                         b = rec + 1;
  37                 else
  38                         e = rec - 1;
  39         } while (b <= e);
  40         //printk("%d: %d,%d,%d\n", bnode->this, b, e, rec);
  41         if (rec != e && e >= 0) {
  42                 len = hfsplus_brec_lenoff(bnode, e, &off);
  43                 keylen = hfsplus_brec_keylen(bnode, e);
  44                 hfsplus_bnode_readbytes(bnode, fd->key, off, keylen);
  45         }
  46         fd->record = e;
  47         fd->keyoffset = off;
  48         fd->keylength = keylen;
  49         fd->entryoffset = off + keylen;
  50         fd->entrylength = len - keylen;
  51 }
  52
  53 /* Traverse a B*Tree from the root to a leaf finding best fit to key */
  54 /* Return allocated copy of node found, set recnum to best record */
  55 int hfsplus_btree_find(struct hfsplus_find_data *fd)
  56 {
  57         hfsplus_btree *tree;
  58         hfsplus_bnode *bnode;
  59         u32 data, nidx, parent;
  60         int height, err;
  61
  62         tree = fd->tree;
  63         if (fd->bnode)
  64                 hfsplus_put_bnode(fd->bnode);
  65         fd->bnode = NULL;
  66         fd->exact = 0;
  67         nidx = tree->root;
  68         if (!nidx)
  69                 return -ENOENT;
  70         height = tree->depth;
  71         err = 0;
  72         parent = 0;
  73         for (;;) {
  74                 bnode = hfsplus_find_bnode(tree, nidx);
  75                 if (!bnode) {
  76                         err = -EIO;
  77                         break;
  78                 }
  79                 if (bnode->height != height)
  80                         goto invalid;
  81                 if (bnode->kind != (--height ? HFSPLUS_NODE_NDX : HFSPLUS_NODE_LEAF))
  82                         goto invalid;
  83                 bnode->parent = parent;
  84
  85                 hfsplus_find_rec(bnode, fd);
  86                 if (fd->record < 0) {
  87                         err = -ENOENT;
  88                         goto release;
  89                 }
  90                 if (!height) {
  91                         if (!fd->exact)
  92                                 err = -ENOENT;
  93                         break;
  94                 }
  95
  96                 parent = nidx;
  97                 hfsplus_bnode_readbytes(bnode, &data, fd->entryoffset, 4);
  98                 nidx = be32_to_cpu(data);
  99                 hfsplus_put_bnode(bnode);
 100         }
 101         fd->bnode = bnode;
 102         return err;
 103
 104 invalid:
 105         printk("HFS+-fs: inconsistency in B*Tree\n");
 106         err = -EIO;
 107 release:
 108         hfsplus_put_bnode(bnode);
 109         return err;
 110 }
 111
 112 int hfsplus_btree_find_entry(struct hfsplus_find_data *fd,
 113                              void *entry, int entry_len)
 114 {
 115         int res;
 116
 117         res = hfsplus_btree_find(fd);
 118         if (res)
 119                 return res;
 120         if (fd->entrylength > entry_len)
 121                 return -EINVAL;
 122         hfsplus_bnode_readbytes(fd->bnode, entry, fd->entryoffset, fd->entrylength);
 123         return 0;
 124 }
 125
 126 int hfsplus_btree_move(struct hfsplus_find_data *fd, int cnt)
 127 {
 128         struct hfsplus_btree *tree;
 129         hfsplus_bnode *bnode;
 130         int idx, res = 0;
 131         u16 off, len, keylen;
 132
 133         bnode = fd->bnode;
 134         tree = bnode->tree;
 135
 136         if (cnt < -0xFFFF || cnt > 0xFFFF)
 137                 return -EINVAL;
 138
 139         if (cnt < 0) {
 140                 cnt = -cnt;
 141                 while (cnt > fd->record) {
 142                         cnt -= fd->record + 1;
 143                         fd->record = bnode->num_recs - 1;
 144                         idx = bnode->prev;
 145                         if (!idx) {
 146                                 res = -ENOENT;
 147                                 goto out;
 148                         }
 149                         hfsplus_put_bnode(bnode);
 150                         bnode = hfsplus_find_bnode(tree, idx);
 151                         if (!bnode) {
 152                                 res = -EIO;
 153                                 goto out;
 154                         }
 155                 }
 156                 fd->record -= cnt;
 157         } else {
 158                 while (cnt >= bnode->num_recs - fd->record) {
 159                         cnt -= bnode->num_recs - fd->record;
 160                         fd->record = 0;
 161                         idx = bnode->next;
 162                         if (!idx) {
 163                                 res = -ENOENT;
 164                                 goto out;
 165                         }
 166                         hfsplus_put_bnode(bnode);
 167                         bnode = hfsplus_find_bnode(tree, idx);
 168                         if (!bnode) {
 169                                 res = -EIO;
 170                                 goto out;
 171                         }
 172                 }
 173                 fd->record += cnt;
 174         }
 175
 176         len = hfsplus_brec_lenoff(bnode, fd->record, &off);
 177         keylen = hfsplus_brec_keylen(bnode, fd->record);
 178         fd->keyoffset = off;
 179         fd->keylength = keylen;
 180         fd->entryoffset = off + keylen;
 181         fd->entrylength = len - keylen;
 182         hfsplus_bnode_readbytes(bnode, fd->key, off, keylen);
 183 out:
 184         fd->bnode = bnode;
 185         return res;
 186 }
 187
 188 int hfsplus_find_init(hfsplus_btree *tree, struct hfsplus_find_data *fd)
 189 {
 190         fd->tree = tree;
 191         fd->bnode = NULL;
 192         fd->search_key = kmalloc(tree->max_key_len + 2, GFP_KERNEL);
 193         if (!fd->search_key)
 194                 return -ENOMEM;
 195         fd->key = kmalloc(tree->max_key_len + 2, GFP_KERNEL);
 196         if (!fd->key) {
 197                 kfree(fd->search_key);
 198                 return -ENOMEM;
 199         }
 200         dprint(DBG_BNODE_REFS, "find_init: %d (%p)\n", tree->cnid, __builtin_return_address(0));
 201         down(&tree->tree_lock);
 202         return 0;
 203 }
 204
 205 void hfsplus_find_exit(struct hfsplus_find_data *fd)
 206 {
 207         hfsplus_put_bnode(fd->bnode);
 208         kfree(fd->search_key);
 209         kfree(fd->key);
 210         dprint(DBG_BNODE_REFS, "find_exit: %d (%p)\n", fd->tree->cnid, __builtin_return_address(0));
 211         up(&fd->tree->tree_lock);
 212         fd->tree = NULL;
 213 }