]>
Commit | Line | Data |
---|---|---|
6513c29f JT |
1 | /* |
2 | * Copyright (C) 2012 Red Hat, Inc. | |
3 | * | |
4 | * This file is released under the GPL. | |
5 | */ | |
6 | #ifndef _LINUX_DM_ARRAY_H | |
7 | #define _LINUX_DM_ARRAY_H | |
8 | ||
9 | #include "dm-btree.h" | |
10 | ||
11 | /*----------------------------------------------------------------*/ | |
12 | ||
13 | /* | |
14 | * The dm-array is a persistent version of an array. It packs the data | |
15 | * more efficiently than a btree which will result in less disk space use, | |
16 | * and a performance boost. The element get and set operations are still | |
17 | * O(ln(n)), but with a much smaller constant. | |
18 | * | |
19 | * The value type structure is reused from the btree type to support proper | |
20 | * reference counting of values. | |
21 | * | |
22 | * The arrays implicitly know their length, and bounds are checked for | |
23 | * lookups and updated. It doesn't store this in an accessible place | |
24 | * because it would waste a whole metadata block. Make sure you store the | |
25 | * size along with the array root in your encompassing data. | |
26 | * | |
27 | * Array entries are indexed via an unsigned integer starting from zero. | |
28 | * Arrays are not sparse; if you resize an array to have 'n' entries then | |
29 | * 'n - 1' will be the last valid index. | |
30 | * | |
31 | * Typical use: | |
32 | * | |
33 | * a) initialise a dm_array_info structure. This describes the array | |
34 | * values and ties it into a specific transaction manager. It holds no | |
35 | * instance data; the same info can be used for many similar arrays if | |
36 | * you wish. | |
37 | * | |
38 | * b) Get yourself a root. The root is the index of a block of data on the | |
39 | * disk that holds a particular instance of an array. You may have a | |
40 | * pre existing root in your metadata that you wish to use, or you may | |
41 | * want to create a brand new, empty array with dm_array_empty(). | |
42 | * | |
43 | * Like the other data structures in this library, dm_array objects are | |
44 | * immutable between transactions. Update functions will return you the | |
45 | * root for a _new_ array. If you've incremented the old root, via | |
46 | * dm_tm_inc(), before calling the update function you may continue to use | |
47 | * it in parallel with the new root. | |
48 | * | |
49 | * c) resize an array with dm_array_resize(). | |
50 | * | |
51 | * d) Get a value from the array with dm_array_get_value(). | |
52 | * | |
53 | * e) Set a value in the array with dm_array_set_value(). | |
54 | * | |
55 | * f) Walk an array of values in index order with dm_array_walk(). More | |
56 | * efficient than making many calls to dm_array_get_value(). | |
57 | * | |
58 | * g) Destroy the array with dm_array_del(). This tells the transaction | |
59 | * manager that you're no longer using this data structure so it can | |
60 | * recycle it's blocks. (dm_array_dec() would be a better name for it, | |
61 | * but del is in keeping with dm_btree_del()). | |
62 | */ | |
63 | ||
64 | /* | |
65 | * Describes an array. Don't initialise this structure yourself, use the | |
66 | * init function below. | |
67 | */ | |
68 | struct dm_array_info { | |
69 | struct dm_transaction_manager *tm; | |
70 | struct dm_btree_value_type value_type; | |
71 | struct dm_btree_info btree_info; | |
72 | }; | |
73 | ||
74 | /* | |
75 | * Sets up a dm_array_info structure. You don't need to do anything with | |
76 | * this structure when you finish using it. | |
77 | * | |
78 | * info - the structure being filled in. | |
79 | * tm - the transaction manager that should supervise this structure. | |
80 | * vt - describes the leaf values. | |
81 | */ | |
82 | void dm_array_info_init(struct dm_array_info *info, | |
83 | struct dm_transaction_manager *tm, | |
84 | struct dm_btree_value_type *vt); | |
85 | ||
86 | /* | |
87 | * Create an empty, zero length array. | |
88 | * | |
89 | * info - describes the array | |
90 | * root - on success this will be filled out with the root block | |
91 | */ | |
92 | int dm_array_empty(struct dm_array_info *info, dm_block_t *root); | |
93 | ||
94 | /* | |
95 | * Resizes the array. | |
96 | * | |
97 | * info - describes the array | |
98 | * root - the root block of the array on disk | |
99 | * old_size - the caller is responsible for remembering the size of | |
100 | * the array | |
101 | * new_size - can be bigger or smaller than old_size | |
102 | * value - if we're growing the array the new entries will have this value | |
103 | * new_root - on success, points to the new root block | |
104 | * | |
105 | * If growing the inc function for 'value' will be called the appropriate | |
106 | * number of times. So if the caller is holding a reference they may want | |
107 | * to drop it. | |
108 | */ | |
109 | int dm_array_resize(struct dm_array_info *info, dm_block_t root, | |
110 | uint32_t old_size, uint32_t new_size, | |
111 | const void *value, dm_block_t *new_root) | |
112 | __dm_written_to_disk(value); | |
113 | ||
114 | /* | |
115 | * Frees a whole array. The value_type's decrement operation will be called | |
116 | * for all values in the array | |
117 | */ | |
118 | int dm_array_del(struct dm_array_info *info, dm_block_t root); | |
119 | ||
120 | /* | |
121 | * Lookup a value in the array | |
122 | * | |
123 | * info - describes the array | |
124 | * root - root block of the array | |
125 | * index - array index | |
126 | * value - the value to be read. Will be in on-disk format of course. | |
127 | * | |
128 | * -ENODATA will be returned if the index is out of bounds. | |
129 | */ | |
130 | int dm_array_get_value(struct dm_array_info *info, dm_block_t root, | |
131 | uint32_t index, void *value); | |
132 | ||
133 | /* | |
134 | * Set an entry in the array. | |
135 | * | |
136 | * info - describes the array | |
137 | * root - root block of the array | |
138 | * index - array index | |
139 | * value - value to be written to disk. Make sure you confirm the value is | |
140 | * in on-disk format with__dm_bless_for_disk() before calling. | |
141 | * new_root - the new root block | |
142 | * | |
143 | * The old value being overwritten will be decremented, the new value | |
144 | * incremented. | |
145 | * | |
146 | * -ENODATA will be returned if the index is out of bounds. | |
147 | */ | |
148 | int dm_array_set_value(struct dm_array_info *info, dm_block_t root, | |
149 | uint32_t index, const void *value, dm_block_t *new_root) | |
150 | __dm_written_to_disk(value); | |
151 | ||
152 | /* | |
153 | * Walk through all the entries in an array. | |
154 | * | |
155 | * info - describes the array | |
156 | * root - root block of the array | |
157 | * fn - called back for every element | |
158 | * context - passed to the callback | |
159 | */ | |
160 | int dm_array_walk(struct dm_array_info *info, dm_block_t root, | |
161 | int (*fn)(void *context, uint64_t key, void *leaf), | |
162 | void *context); | |
163 | ||
164 | /*----------------------------------------------------------------*/ | |
165 | ||
166 | #endif /* _LINUX_DM_ARRAY_H */ |