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