Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
dm-btree.h
Go to the documentation of this file.
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  * Infomation 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, 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, 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, void *value1, 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 #endif /* _LINUX_DM_BTREE_H */
Generated on Thu Jan 10 2013 13:44:15 for Linux Kernel by   doxygen 1.8.2