]>
Commit | Line | Data |
---|---|---|
7a87edfe JT |
1 | /* |
2 | * Copyright (C) 2012 Red Hat, Inc. | |
3 | * | |
4 | * This file is released under the GPL. | |
5 | */ | |
6 | #ifndef _LINUX_DM_BITSET_H | |
7 | #define _LINUX_DM_BITSET_H | |
8 | ||
9 | #include "dm-array.h" | |
10 | ||
11 | /*----------------------------------------------------------------*/ | |
12 | ||
13 | /* | |
14 | * This bitset type is a thin wrapper round a dm_array of 64bit words. It | |
15 | * uses a tiny, one word cache to reduce the number of array lookups and so | |
16 | * increase performance. | |
17 | * | |
18 | * Like the dm-array that it's based on, the caller needs to keep track of | |
19 | * the size of the bitset separately. The underlying dm-array implicitly | |
20 | * knows how many words it's storing and will return -ENODATA if you try | |
21 | * and access an out of bounds word. However, an out of bounds bit in the | |
22 | * final word will _not_ be detected, you have been warned. | |
23 | * | |
24 | * Bits are indexed from zero. | |
25 | ||
26 | * Typical use: | |
27 | * | |
28 | * a) Initialise a dm_disk_bitset structure with dm_disk_bitset_init(). | |
29 | * This describes the bitset and includes the cache. It's not called it | |
30 | * dm_bitset_info in line with other data structures because it does | |
31 | * include instance data. | |
32 | * | |
33 | * b) Get yourself a root. The root is the index of a block of data on the | |
34 | * disk that holds a particular instance of an bitset. You may have a | |
35 | * pre existing root in your metadata that you wish to use, or you may | |
36 | * want to create a brand new, empty bitset with dm_bitset_empty(). | |
37 | * | |
38 | * Like the other data structures in this library, dm_bitset objects are | |
39 | * immutable between transactions. Update functions will return you the | |
40 | * root for a _new_ array. If you've incremented the old root, via | |
41 | * dm_tm_inc(), before calling the update function you may continue to use | |
42 | * it in parallel with the new root. | |
43 | * | |
44 | * Even read operations may trigger the cache to be flushed and as such | |
45 | * return a root for a new, updated bitset. | |
46 | * | |
47 | * c) resize a bitset with dm_bitset_resize(). | |
48 | * | |
49 | * d) Set a bit with dm_bitset_set_bit(). | |
50 | * | |
51 | * e) Clear a bit with dm_bitset_clear_bit(). | |
52 | * | |
53 | * f) Test a bit with dm_bitset_test_bit(). | |
54 | * | |
55 | * g) Flush all updates from the cache with dm_bitset_flush(). | |
56 | * | |
57 | * h) Destroy the bitset with dm_bitset_del(). This tells the transaction | |
58 | * manager that you're no longer using this data structure so it can | |
59 | * recycle it's blocks. (dm_bitset_dec() would be a better name for it, | |
60 | * but del is in keeping with dm_btree_del()). | |
61 | */ | |
62 | ||
63 | /* | |
64 | * Opaque object. Unlike dm_array_info, you should have one of these per | |
65 | * bitset. Initialise with dm_disk_bitset_init(). | |
66 | */ | |
67 | struct dm_disk_bitset { | |
68 | struct dm_array_info array_info; | |
69 | ||
70 | uint32_t current_index; | |
71 | uint64_t current_bits; | |
72 | ||
73 | bool current_index_set:1; | |
428e4698 | 74 | bool dirty:1; |
7a87edfe JT |
75 | }; |
76 | ||
77 | /* | |
78 | * Sets up a dm_disk_bitset structure. You don't need to do anything with | |
79 | * this structure when you finish using it. | |
80 | * | |
81 | * tm - the transaction manager that should supervise this structure | |
82 | * info - the structure being initialised | |
83 | */ | |
84 | void dm_disk_bitset_init(struct dm_transaction_manager *tm, | |
85 | struct dm_disk_bitset *info); | |
86 | ||
87 | /* | |
88 | * Create an empty, zero length bitset. | |
89 | * | |
90 | * info - describes the bitset | |
91 | * new_root - on success, points to the new root block | |
92 | */ | |
93 | int dm_bitset_empty(struct dm_disk_bitset *info, dm_block_t *new_root); | |
94 | ||
2151249e JT |
95 | /* |
96 | * Creates a new bitset populated with values provided by a callback | |
97 | * function. This is more efficient than creating an empty bitset, | |
98 | * resizing, and then setting values since that process incurs a lot of | |
99 | * copying. | |
100 | * | |
101 | * info - describes the array | |
102 | * root - the root block of the array on disk | |
103 | * size - the number of entries in the array | |
104 | * fn - the callback | |
105 | * context - passed to the callback | |
106 | */ | |
107 | typedef int (*bit_value_fn)(uint32_t index, bool *value, void *context); | |
108 | int dm_bitset_new(struct dm_disk_bitset *info, dm_block_t *root, | |
109 | uint32_t size, bit_value_fn fn, void *context); | |
110 | ||
7a87edfe JT |
111 | /* |
112 | * Resize the bitset. | |
113 | * | |
114 | * info - describes the bitset | |
115 | * old_root - the root block of the array on disk | |
116 | * old_nr_entries - the number of bits in the old bitset | |
117 | * new_nr_entries - the number of bits you want in the new bitset | |
118 | * default_value - the value for any new bits | |
119 | * new_root - on success, points to the new root block | |
120 | */ | |
121 | int dm_bitset_resize(struct dm_disk_bitset *info, dm_block_t old_root, | |
122 | uint32_t old_nr_entries, uint32_t new_nr_entries, | |
123 | bool default_value, dm_block_t *new_root); | |
124 | ||
125 | /* | |
126 | * Frees the bitset. | |
127 | */ | |
128 | int dm_bitset_del(struct dm_disk_bitset *info, dm_block_t root); | |
129 | ||
130 | /* | |
131 | * Set a bit. | |
132 | * | |
133 | * info - describes the bitset | |
134 | * root - the root block of the bitset | |
135 | * index - the bit index | |
136 | * new_root - on success, points to the new root block | |
137 | * | |
138 | * -ENODATA will be returned if the index is out of bounds. | |
139 | */ | |
140 | int dm_bitset_set_bit(struct dm_disk_bitset *info, dm_block_t root, | |
141 | uint32_t index, dm_block_t *new_root); | |
142 | ||
143 | /* | |
144 | * Clears a bit. | |
145 | * | |
146 | * info - describes the bitset | |
147 | * root - the root block of the bitset | |
148 | * index - the bit index | |
149 | * new_root - on success, points to the new root block | |
150 | * | |
151 | * -ENODATA will be returned if the index is out of bounds. | |
152 | */ | |
153 | int dm_bitset_clear_bit(struct dm_disk_bitset *info, dm_block_t root, | |
154 | uint32_t index, dm_block_t *new_root); | |
155 | ||
156 | /* | |
157 | * Tests a bit. | |
158 | * | |
159 | * info - describes the bitset | |
160 | * root - the root block of the bitset | |
161 | * index - the bit index | |
162 | * new_root - on success, points to the new root block (cached values may have been written) | |
163 | * result - the bit value you're after | |
164 | * | |
165 | * -ENODATA will be returned if the index is out of bounds. | |
166 | */ | |
167 | int dm_bitset_test_bit(struct dm_disk_bitset *info, dm_block_t root, | |
168 | uint32_t index, dm_block_t *new_root, bool *result); | |
169 | ||
170 | /* | |
171 | * Flush any cached changes to disk. | |
172 | * | |
173 | * info - describes the bitset | |
174 | * root - the root block of the bitset | |
175 | * new_root - on success, points to the new root block | |
176 | */ | |
177 | int dm_bitset_flush(struct dm_disk_bitset *info, dm_block_t root, | |
178 | dm_block_t *new_root); | |
179 | ||
6fe28dbf JT |
180 | struct dm_bitset_cursor { |
181 | struct dm_disk_bitset *info; | |
182 | struct dm_array_cursor cursor; | |
183 | ||
184 | uint32_t entries_remaining; | |
185 | uint32_t array_index; | |
186 | uint32_t bit_index; | |
187 | uint64_t current_bits; | |
188 | }; | |
189 | ||
190 | /* | |
191 | * Make sure you've flush any dm_disk_bitset and updated the root before | |
192 | * using this. | |
193 | */ | |
194 | int dm_bitset_cursor_begin(struct dm_disk_bitset *info, | |
195 | dm_block_t root, uint32_t nr_entries, | |
196 | struct dm_bitset_cursor *c); | |
197 | void dm_bitset_cursor_end(struct dm_bitset_cursor *c); | |
198 | ||
199 | int dm_bitset_cursor_next(struct dm_bitset_cursor *c); | |
9b696229 | 200 | int dm_bitset_cursor_skip(struct dm_bitset_cursor *c, uint32_t count); |
6fe28dbf JT |
201 | bool dm_bitset_cursor_get_value(struct dm_bitset_cursor *c); |
202 | ||
7a87edfe JT |
203 | /*----------------------------------------------------------------*/ |
204 | ||
205 | #endif /* _LINUX_DM_BITSET_H */ |