Root/
1 | /* |
2 | * Copyright (C) 2011 Red Hat, Inc. |
3 | * |
4 | * This file is released under the GPL. |
5 | */ |
6 | #ifndef _LINUX_DM_BTREE_H |
7 | #define _LINUX_DM_BTREE_H |
8 | |
9 | #include "dm-block-manager.h" |
10 | |
11 | struct dm_transaction_manager; |
12 | |
13 | /*----------------------------------------------------------------*/ |
14 | |
15 | /* |
16 | * Annotations used to check on-disk metadata is handled as little-endian. |
17 | */ |
18 | #ifdef __CHECKER__ |
19 | # define __dm_written_to_disk(x) __releases(x) |
20 | # define __dm_reads_from_disk(x) __acquires(x) |
21 | # define __dm_bless_for_disk(x) __acquire(x) |
22 | # define __dm_unbless_for_disk(x) __release(x) |
23 | #else |
24 | # define __dm_written_to_disk(x) |
25 | # define __dm_reads_from_disk(x) |
26 | # define __dm_bless_for_disk(x) |
27 | # define __dm_unbless_for_disk(x) |
28 | #endif |
29 | |
30 | /*----------------------------------------------------------------*/ |
31 | |
32 | /* |
33 | * Manipulates hierarchical B+ trees with 64-bit keys and arbitrary-sized |
34 | * values. |
35 | */ |
36 | |
37 | /* |
38 | * Information about the values stored within the btree. |
39 | */ |
40 | struct dm_btree_value_type { |
41 | void *context; |
42 | |
43 | /* |
44 | * The size in bytes of each value. |
45 | */ |
46 | uint32_t size; |
47 | |
48 | /* |
49 | * Any of these methods can be safely set to NULL if you do not |
50 | * need the corresponding feature. |
51 | */ |
52 | |
53 | /* |
54 | * The btree is making a duplicate of the value, for instance |
55 | * because previously-shared btree nodes have now diverged. |
56 | * @value argument is the new copy that the copy function may modify. |
57 | * (Probably it just wants to increment a reference count |
58 | * somewhere.) This method is _not_ called for insertion of a new |
59 | * value: It is assumed the ref count is already 1. |
60 | */ |
61 | void (*inc)(void *context, const void *value); |
62 | |
63 | /* |
64 | * This value is being deleted. The btree takes care of freeing |
65 | * the memory pointed to by @value. Often the del function just |
66 | * needs to decrement a reference count somewhere. |
67 | */ |
68 | void (*dec)(void *context, const void *value); |
69 | |
70 | /* |
71 | * A test for equality between two values. When a value is |
72 | * overwritten with a new one, the old one has the dec method |
73 | * called _unless_ the new and old value are deemed equal. |
74 | */ |
75 | int (*equal)(void *context, const void *value1, const void *value2); |
76 | }; |
77 | |
78 | /* |
79 | * The shape and contents of a btree. |
80 | */ |
81 | struct dm_btree_info { |
82 | struct dm_transaction_manager *tm; |
83 | |
84 | /* |
85 | * Number of nested btrees. (Not the depth of a single tree.) |
86 | */ |
87 | unsigned levels; |
88 | struct dm_btree_value_type value_type; |
89 | }; |
90 | |
91 | /* |
92 | * Set up an empty tree. O(1). |
93 | */ |
94 | int dm_btree_empty(struct dm_btree_info *info, dm_block_t *root); |
95 | |
96 | /* |
97 | * Delete a tree. O(n) - this is the slow one! It can also block, so |
98 | * please don't call it on an IO path. |
99 | */ |
100 | int dm_btree_del(struct dm_btree_info *info, dm_block_t root); |
101 | |
102 | /* |
103 | * All the lookup functions return -ENODATA if the key cannot be found. |
104 | */ |
105 | |
106 | /* |
107 | * Tries to find a key that matches exactly. O(ln(n)) |
108 | */ |
109 | int dm_btree_lookup(struct dm_btree_info *info, dm_block_t root, |
110 | uint64_t *keys, void *value_le); |
111 | |
112 | /* |
113 | * Insertion (or overwrite an existing value). O(ln(n)) |
114 | */ |
115 | int dm_btree_insert(struct dm_btree_info *info, dm_block_t root, |
116 | uint64_t *keys, void *value, dm_block_t *new_root) |
117 | __dm_written_to_disk(value); |
118 | |
119 | /* |
120 | * A variant of insert that indicates whether it actually inserted or just |
121 | * overwrote. Useful if you're keeping track of the number of entries in a |
122 | * tree. |
123 | */ |
124 | int dm_btree_insert_notify(struct dm_btree_info *info, dm_block_t root, |
125 | uint64_t *keys, void *value, dm_block_t *new_root, |
126 | int *inserted) |
127 | __dm_written_to_disk(value); |
128 | |
129 | /* |
130 | * Remove a key if present. This doesn't remove empty sub trees. Normally |
131 | * subtrees represent a separate entity, like a snapshot map, so this is |
132 | * correct behaviour. O(ln(n)). |
133 | */ |
134 | int dm_btree_remove(struct dm_btree_info *info, dm_block_t root, |
135 | uint64_t *keys, dm_block_t *new_root); |
136 | |
137 | /* |
138 | * Returns < 0 on failure. Otherwise the number of key entries that have |
139 | * been filled out. Remember trees can have zero entries, and as such have |
140 | * no highest key. |
141 | */ |
142 | int dm_btree_find_highest_key(struct dm_btree_info *info, dm_block_t root, |
143 | uint64_t *result_keys); |
144 | |
145 | /* |
146 | * Iterate through the a btree, calling fn() on each entry. |
147 | * It only works for single level trees and is internally recursive, so |
148 | * monitor stack usage carefully. |
149 | */ |
150 | int dm_btree_walk(struct dm_btree_info *info, dm_block_t root, |
151 | int (*fn)(void *context, uint64_t *keys, void *leaf), |
152 | void *context); |
153 | |
154 | #endif /* _LINUX_DM_BTREE_H */ |
155 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9