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 * Information 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, const 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, const 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, const void *value1, const 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 lowest key.
141 */
142int dm_btree_find_lowest_key(struct dm_btree_info *info, dm_block_t root,
143			     uint64_t *result_keys);
144
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 */
150int dm_btree_find_highest_key(struct dm_btree_info *info, dm_block_t root,
151			      uint64_t *result_keys);
152
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 */
158int 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
162#endif	/* _LINUX_DM_BTREE_H */
163