xref: /illumos-gate/usr/src/uts/common/fs/zfs/sys/btree.h (revision 616aa2dbfe5dffab5fbe77e81b10a221d2d2966a)
1 /*
2  * CDDL HEADER START
3  *
4  * This file and its contents are supplied under the terms of the
5  * Common Development and Distribution License ("CDDL"), version 1.0.
6  * You may only use this file in accordance with the terms of version
7  * 1.0 of the CDDL.
8  *
9  * A full copy of the text of the CDDL should have accompanied this
10  * source.  A copy of the CDDL is also available via the Internet at
11  * http://www.illumos.org/license/CDDL.
12  *
13  * CDDL HEADER END
14  */
15 /*
16  * Copyright (c) 2019 by Delphix. All rights reserved.
17  */
18 
19 #ifndef	_BTREE_H
20 #define	_BTREE_H
21 
22 #ifdef	__cplusplus
23 extern "C" {
24 #endif
25 
26 #include	<sys/zfs_context.h>
27 
28 /*
29  * This file defines the interface for a B-Tree implementation for ZFS. The
30  * tree can be used to store arbitrary sortable data types with low overhead
31  * and good operation performance. In addition the tree intelligently
32  * optimizes bulk in-order insertions to improve memory use and performance.
33  *
34  * Note that for all B-Tree functions, the values returned are pointers to the
35  * internal copies of the data in the tree. The internal data can only be
36  * safely mutated if the changes cannot change the ordering of the element
37  * with respect to any other elements in the tree.
38  *
39  * The major drawback of the B-Tree is that any returned elements or indexes
40  * are only valid until a side-effectful operation occurs, since these can
41  * result in reallocation or relocation of data. Side effectful operations are
42  * defined as insertion, removal, and zfs_btree_destroy_nodes.
43  *
44  * The B-Tree has two types of nodes: core nodes, and leaf nodes. Core
45  * nodes have an array of children pointing to other nodes, and an array of
46  * elements that act as separators between the elements of the subtrees rooted
47  * at its children. Leaf nodes only contain data elements, and form the bottom
48  * layer of the tree. Unlike B+ Trees, in this B-Tree implementation the
49  * elements in the core nodes are not copies of or references to leaf node
50  * elements.  Each element occcurs only once in the tree, no matter what kind
51  * of node it is in.
52  *
53  * The tree's height is the same throughout, unlike many other forms of search
54  * tree. Each node (except for the root) must be between half minus one and
55  * completely full of elements (and children) at all times. Any operation that
56  * would put the node outside of that range results in a rebalancing operation
57  * (taking, merging, or splitting).
58  *
59  * This tree was implemented using descriptions from Wikipedia's articles on
60  * B-Trees and B+ Trees.
61  */
62 
63 /*
64  * Decreasing these values results in smaller memmove operations, but more of
65  * them, and increased memory overhead. Increasing these values results in
66  * higher variance in operation time, and reduces memory overhead.
67  */
68 #define	BTREE_CORE_ELEMS	128
69 #define	BTREE_LEAF_SIZE		4096
70 
71 typedef struct zfs_btree_hdr {
72 	struct zfs_btree_core	*bth_parent;
73 	/*
74 	 * Set to -1 to indicate core nodes. Other values represent first
75 	 * valid element offset for leaf nodes.
76 	 */
77 	uint32_t		bth_first;
78 	/*
79 	 * For both leaf and core nodes, represents the number of elements in
80 	 * the node. For core nodes, they will have bth_count + 1 children.
81 	 */
82 	uint32_t		bth_count;
83 } zfs_btree_hdr_t;
84 
85 typedef struct zfs_btree_core {
86 	zfs_btree_hdr_t	btc_hdr;
87 	zfs_btree_hdr_t	*btc_children[BTREE_CORE_ELEMS + 1];
88 	uint8_t		btc_elems[];
89 } zfs_btree_core_t;
90 
91 typedef struct zfs_btree_leaf {
92 	zfs_btree_hdr_t	btl_hdr;
93 	uint8_t		btl_elems[];
94 } zfs_btree_leaf_t;
95 
96 #define	BTREE_LEAF_ESIZE	(BTREE_LEAF_SIZE - \
97     offsetof(zfs_btree_leaf_t, btl_elems))
98 
99 typedef struct zfs_btree_index {
100 	zfs_btree_hdr_t	*bti_node;
101 	uint32_t	bti_offset;
102 	/*
103 	 * True if the location is before the list offset, false if it's at
104 	 * the listed offset.
105 	 */
106 	boolean_t	bti_before;
107 } zfs_btree_index_t;
108 
109 typedef struct btree {
110 	zfs_btree_hdr_t		*bt_root;
111 	int64_t			bt_height;
112 	size_t			bt_elem_size;
113 	uint32_t		bt_leaf_cap;
114 	uint64_t		bt_num_elems;
115 	uint64_t		bt_num_nodes;
116 	zfs_btree_leaf_t	*bt_bulk; // non-null if bulk loading
117 	int (*bt_compar) (const void *, const void *);
118 } zfs_btree_t;
119 
120 /*
121  * Allocate and deallocate caches for btree nodes.
122  */
123 void zfs_btree_init(void);
124 void zfs_btree_fini(void);
125 
126 /*
127  * Initialize an B-Tree. Arguments are:
128  *
129  * tree   - the tree to be initialized
130  * compar - function to compare two nodes, it must return exactly: -1, 0, or +1
131  *          -1 for <, 0 for ==, and +1 for >
132  * size   - the value of sizeof(struct my_type)
133  */
134 void zfs_btree_create(zfs_btree_t *, int (*) (const void *, const void *),
135     size_t);
136 
137 /*
138  * Find a node with a matching value in the tree. Returns the matching node
139  * found. If not found, it returns NULL and then if "where" is not NULL it sets
140  * "where" for use with zfs_btree_add_idx() or zfs_btree_nearest().
141  *
142  * node   - node that has the value being looked for
143  * where  - position for use with zfs_btree_nearest() or zfs_btree_add_idx(),
144  *          may be NULL
145  */
146 void *zfs_btree_find(zfs_btree_t *, const void *, zfs_btree_index_t *);
147 
148 /*
149  * Insert a node into the tree.
150  *
151  * node   - the node to insert
152  * where  - position as returned from zfs_btree_find()
153  */
154 void zfs_btree_add_idx(zfs_btree_t *, const void *, const zfs_btree_index_t *);
155 
156 /*
157  * Return the first or last valued node in the tree. Will return NULL if the
158  * tree is empty. The index can be NULL if the location of the first or last
159  * element isn't required.
160  */
161 void *zfs_btree_first(zfs_btree_t *, zfs_btree_index_t *);
162 void *zfs_btree_last(zfs_btree_t *, zfs_btree_index_t *);
163 
164 /*
165  * Return the next or previous valued node in the tree. The second index can
166  * safely be NULL, if the location of the next or previous value isn't
167  * required.
168  */
169 void *zfs_btree_next(zfs_btree_t *, const zfs_btree_index_t *,
170     zfs_btree_index_t *);
171 void *zfs_btree_prev(zfs_btree_t *, const zfs_btree_index_t *,
172     zfs_btree_index_t *);
173 
174 /*
175  * Get a value from a tree and an index.
176  */
177 void *zfs_btree_get(zfs_btree_t *, zfs_btree_index_t *);
178 
179 /*
180  * Add a single value to the tree. The value must not compare equal to any
181  * other node already in the tree. Note that the value will be copied out, not
182  * inserted directly. It is safe to free or destroy the value once this
183  * function returns.
184  */
185 void zfs_btree_add(zfs_btree_t *, const void *);
186 
187 /*
188  * Remove a single value from the tree.  The value must be in the tree. The
189  * pointer passed in may be a pointer into a tree-controlled buffer, but it
190  * need not be.
191  */
192 void zfs_btree_remove(zfs_btree_t *, const void *);
193 
194 /*
195  * Remove the value at the given location from the tree.
196  */
197 void zfs_btree_remove_idx(zfs_btree_t *, zfs_btree_index_t *);
198 
199 /*
200  * Return the number of nodes in the tree
201  */
202 ulong_t zfs_btree_numnodes(zfs_btree_t *);
203 
204 /*
205  * Used to destroy any remaining nodes in a tree. The cookie argument should
206  * be initialized to NULL before the first call. Returns a node that has been
207  * removed from the tree and may be free()'d. Returns NULL when the tree is
208  * empty.
209  *
210  * Once you call zfs_btree_destroy_nodes(), you can only continuing calling it
211  * and finally zfs_btree_destroy(). No other B-Tree routines will be valid.
212  *
213  * cookie - an index used to save state between calls to
214  * zfs_btree_destroy_nodes()
215  *
216  * EXAMPLE:
217  *	zfs_btree_t *tree;
218  *	struct my_data *node;
219  *	zfs_btree_index_t *cookie;
220  *
221  *	cookie = NULL;
222  *	while ((node = zfs_btree_destroy_nodes(tree, &cookie)) != NULL)
223  *		data_destroy(node);
224  *	zfs_btree_destroy(tree);
225  */
226 void *zfs_btree_destroy_nodes(zfs_btree_t *, zfs_btree_index_t **);
227 
228 /*
229  * Destroys all nodes in the tree quickly. This doesn't give the caller an
230  * opportunity to iterate over each node and do its own cleanup; for that, use
231  * zfs_btree_destroy_nodes().
232  */
233 void zfs_btree_clear(zfs_btree_t *);
234 
235 /*
236  * Final destroy of an B-Tree. Arguments are:
237  *
238  * tree   - the empty tree to destroy
239  */
240 void zfs_btree_destroy(zfs_btree_t *tree);
241 
242 /* Runs a variety of self-checks on the btree to verify integrity. */
243 void zfs_btree_verify(zfs_btree_t *tree);
244 
245 #ifdef	__cplusplus
246 }
247 #endif
248 
249 #endif	/* _BTREE_H */
250