Root/drivers/md/persistent-data/dm-btree.h

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
11struct 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 */
40struct 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 */
81struct 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 */
94int 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 */
100int 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 */
109int 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 */
115int 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 */
124int 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 */
134int 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 */
142int 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 */
146

Archive Download this file



interactive