Cross Reference: /illumos-gate/usr/src/uts/common/fs/zfs/zfs

Lines Matching defs:tree
41  * AVL tree
43  * An AVL tree is used to maintain the state of the existing ranges
45  * The starting range offset is used for searching and sorting the tree.
50  * locks. On entry to zfs_lock_range() a rl_t is allocated; the tree
51  * searched that finds no overlap, and *this* rl_t is placed in the tree.
106 	avl_tree_t *tree = &zp->z_range_avl;
149 		if (avl_numnodes(tree) == 0) {
151 			avl_add(tree, new);
158 		rl = avl_find(tree, new, &where);
162 		rl = (rl_t *)avl_nearest(tree, where, AVL_AFTER);
166 		rl = (rl_t *)avl_nearest(tree, where, AVL_BEFORE);
171 		avl_insert(tree, new, where);
191 zfs_range_proxify(avl_tree_t *tree, rl_t *rl)
201 	avl_remove(tree, rl);
213 	avl_add(tree, proxy);
223 zfs_range_split(avl_tree_t *tree, rl_t *rl, uint64_t off)
243 	front = zfs_range_proxify(tree, rl);
246 	avl_insert_here(tree, rear, front, AVL_AFTER);
254 zfs_range_new_proxy(avl_tree_t *tree, uint64_t off, uint64_t len)
267 	avl_add(tree, rl);
271 zfs_range_add_reader(avl_tree_t *tree, rl_t *new, rl_t *prev, avl_index_t where)
292 			prev = zfs_range_split(tree, prev, off);
293 			prev = AVL_NEXT(tree, prev); /* move to rear range */
301 		next = (rl_t *)avl_nearest(tree, where, AVL_AFTER);
304 		/* no overlaps, use the original new rl_t in the tree */
305 		avl_insert(tree, new, where);
311 		zfs_range_new_proxy(tree, off, next->r_off - off);
314 	new->r_cnt = 0; /* will use proxies in tree */
321 	for (prev = NULL; next; prev = next, next = AVL_NEXT(tree, next)) {
327 			zfs_range_new_proxy(tree, prev->r_off + prev->r_len,
332 			next = zfs_range_proxify(tree, next);
338 			next = zfs_range_split(tree, next, off + len);
343 		next = zfs_range_proxify(tree, next);
348 	zfs_range_new_proxy(tree, prev->r_off + prev->r_len,
358 	avl_tree_t *tree = &zp->z_range_avl;
368 	prev = avl_find(tree, new, &where);
370 		prev = (rl_t *)avl_nearest(tree, where, AVL_BEFORE);
393 		next = AVL_NEXT(tree, prev);
395 		next = (rl_t *)avl_nearest(tree, where, AVL_AFTER);
396 	for (; next; next = AVL_NEXT(tree, next)) {
416 	zfs_range_add_reader(tree, new, prev, where);
438 	new->r_cnt = 1; /* assume it's going to be in the tree */
465 	avl_tree_t *tree = &zp->z_range_avl;
470 	 * The common case is when the remove entry is in the tree
473 	 * removed from the tree and replaced by proxies (one or
477 		avl_remove(tree, remove);
495 		rl = avl_find(tree, remove, NULL);
502 				next = AVL_NEXT(tree, rl);
510 				avl_remove(tree, rl);
565  * entry in the tree.