OpenCores
URL https://opencores.org/ocsvn/or1k/or1k/trunk

Subversion Repositories or1k

[/] [or1k/] [trunk/] [linux/] [linux-2.4/] [fs/] [hfsplus/] [bfind.c] - Blame information for rev 1765

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 1275 phoenix 
/*
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 
}

powered by: WebSVN 2.1.0

© copyright 1999-2025 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.