]>
Commit | Line | Data |
---|---|---|
3241b1d3 JT |
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 | /* | |
83f0d77a | 38 | * Information about the values stored within the btree. |
3241b1d3 JT |
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 | */ | |
018cede9 | 61 | void (*inc)(void *context, const void *value); |
3241b1d3 JT |
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 | */ | |
018cede9 | 68 | void (*dec)(void *context, const void *value); |
3241b1d3 JT |
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 | */ | |
018cede9 | 75 | int (*equal)(void *context, const void *value1, const void *value2); |
3241b1d3 JT |
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 | ||
f164e690 JT |
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 lowest key. | |
141 | */ | |
142 | int dm_btree_find_lowest_key(struct dm_btree_info *info, dm_block_t root, | |
143 | uint64_t *result_keys); | |
144 | ||
3241b1d3 JT |
145 | /* |
146 | * Returns < 0 on failure. Otherwise the number of key entries that have | |
147 | * been filled out. Remember trees can have zero entries, and as such have | |
148 | * no highest key. | |
149 | */ | |
150 | int dm_btree_find_highest_key(struct dm_btree_info *info, dm_block_t root, | |
151 | uint64_t *result_keys); | |
152 | ||
4e7f1f90 JT |
153 | /* |
154 | * Iterate through the a btree, calling fn() on each entry. | |
155 | * It only works for single level trees and is internally recursive, so | |
156 | * monitor stack usage carefully. | |
157 | */ | |
158 | int dm_btree_walk(struct dm_btree_info *info, dm_block_t root, | |
159 | int (*fn)(void *context, uint64_t *keys, void *leaf), | |
160 | void *context); | |
161 | ||
3241b1d3 | 162 | #endif /* _LINUX_DM_BTREE_H */ |