File Manager

003 File Manager

Current Path: /usr/src/sys/contrib/openzfs/include/sys

usr / src / sys / contrib / openzfs / include / sys /

📁 ..
📄 Makefile.am(2.18 KB)
📄 abd.h(4.25 KB)
📄 abd_impl.h(4.41 KB)
📄 aggsum.h(1.28 KB)
📄 arc.h(11.19 KB)
📄 arc_impl.h(33.15 KB)
📄 avl.h(9.16 KB)
📄 avl_impl.h(4.8 KB)
📄 bitops.h(3.2 KB)
📄 blkptr.h(914 B)
📄 bplist.h(1.6 KB)
📄 bpobj.h(3.21 KB)
📄 bptree.h(1.89 KB)
📄 bqueue.h(1.23 KB)
📄 btree.h(7.68 KB)
📁 crypto
📄 dataset_kstats.h(2.27 KB)
📄 dbuf.h(13.94 KB)
📄 ddt.h(7.96 KB)
📄 dmu.h(39.06 KB)
📄 dmu_impl.h(6.92 KB)
📄 dmu_objset.h(9.19 KB)
📄 dmu_recv.h(2.75 KB)
📄 dmu_redact.h(1.67 KB)
📄 dmu_send.h(2.54 KB)
📄 dmu_traverse.h(3.02 KB)
📄 dmu_tx.h(4.43 KB)
📄 dmu_zfetch.h(2.23 KB)
📄 dnode.h(22.41 KB)
📄 dsl_bookmark.h(5.05 KB)
📄 dsl_crypt.h(7.76 KB)
📄 dsl_dataset.h(18.62 KB)
📄 dsl_deadlist.h(4.21 KB)
📄 dsl_deleg.h(3.27 KB)
📄 dsl_destroy.h(2.19 KB)
📄 dsl_dir.h(7.67 KB)
📄 dsl_pool.h(6.23 KB)
📄 dsl_prop.h(4.38 KB)
📄 dsl_scan.h(7.11 KB)
📄 dsl_synctask.h(4.06 KB)
📄 dsl_userhold.h(1.84 KB)
📄 edonr.h(2.65 KB)
📄 efi_partition.h(16.28 KB)
📁 fm
📄 frame.h(935 B)
📁 fs
📄 hkdf.h(782 B)
📁 lua
📄 metaslab.h(5.48 KB)
📄 metaslab_impl.h(21.23 KB)
📄 mmp.h(2.37 KB)
📄 mntent.h(5.22 KB)
📄 mod.h(1.26 KB)
📄 multilist.h(3.27 KB)
📄 note.h(1.62 KB)
📄 nvpair.h(14.77 KB)
📄 nvpair_impl.h(2.23 KB)
📄 objlist.h(1.13 KB)
📄 pathname.h(2.12 KB)
📄 qat.h(5.86 KB)
📄 range_tree.h(9.73 KB)
📄 rrwlock.h(3.53 KB)
📄 sa.h(5.14 KB)
📄 sa_impl.h(8.29 KB)
📄 skein.h(6.69 KB)
📄 spa.h(46.07 KB)
📄 spa_boot.h(1.16 KB)
📄 spa_checkpoint.h(1.44 KB)
📄 spa_checksum.h(1.96 KB)
📄 spa_impl.h(18.25 KB)
📄 spa_log_spacemap.h(2.62 KB)
📄 space_map.h(8.7 KB)
📄 space_reftree.h(1.69 KB)
📁 sysevent
📄 sysevent.h(1.07 KB)
📄 txg.h(4.66 KB)
📄 txg_impl.h(4.77 KB)
📄 u8_textprep.h(3.59 KB)
📄 u8_textprep_data.h(1.41 MB)
📄 uberblock.h(1.36 KB)
📄 uberblock_impl.h(5.11 KB)
📄 uio_impl.h(1.58 KB)
📄 unique.h(1.56 KB)
📄 uuid.h(2.85 KB)
📄 vdev.h(8.18 KB)
📄 vdev_disk.h(1.65 KB)
📄 vdev_draid.h(3.43 KB)
📄 vdev_file.h(1.23 KB)
📄 vdev_impl.h(22.53 KB)
📄 vdev_indirect_births.h(2.31 KB)
📄 vdev_indirect_mapping.h(4.38 KB)
📄 vdev_initialize.h(1.39 KB)
📄 vdev_raidz.h(2.04 KB)
📄 vdev_raidz_impl.h(10.54 KB)
📄 vdev_rebuild.h(3.4 KB)
📄 vdev_removal.h(2.63 KB)
📄 vdev_trim.h(1.72 KB)
📄 xvattr.h(13.1 KB)
📄 zap.h(18.63 KB)
📄 zap_impl.h(6.79 KB)
📄 zap_leaf.h(7.84 KB)
📄 zcp.h(4.87 KB)
📄 zcp_global.h(742 B)
📄 zcp_iter.h(1.07 KB)
📄 zcp_prop.h(780 B)
📄 zcp_set.h(929 B)
📄 zfeature.h(2.42 KB)
📄 zfs_acl.h(8.08 KB)
📄 zfs_bootenv.h(1.41 KB)
📄 zfs_context.h(21.23 KB)
📄 zfs_debug.h(3.3 KB)
📄 zfs_delay.h(1.25 KB)
📄 zfs_file.h(2.06 KB)
📄 zfs_fuid.h(4.26 KB)
📄 zfs_ioctl.h(17.63 KB)
📄 zfs_ioctl_impl.h(3.1 KB)
📄 zfs_onexit.h(1.65 KB)
📄 zfs_project.h(2.35 KB)
📄 zfs_quota.h(1.57 KB)
📄 zfs_racct.h(1.12 KB)
📄 zfs_ratelimit.h(1.11 KB)
📄 zfs_refcount.h(4.15 KB)
📄 zfs_rlock.h(2.54 KB)
📄 zfs_sa.h(4.38 KB)
📄 zfs_stat.h(1.45 KB)
📄 zfs_sysfs.h(1.49 KB)
📄 zfs_vfsops.h(1.05 KB)
📄 zfs_vnops.h(2 KB)
📄 zfs_znode.h(10.93 KB)
📄 zil.h(18.27 KB)
📄 zil_impl.h(9.12 KB)
📄 zio.h(21.68 KB)
📄 zio_checksum.h(4.55 KB)
📄 zio_compress.h(5.91 KB)
📄 zio_crypt.h(5.21 KB)
📄 zio_impl.h(8.33 KB)
📄 zio_priority.h(1.2 KB)
📄 zrlock.h(1.7 KB)
📁 zstd
📄 zthr.h(1.23 KB)
📄 zvol.h(2.27 KB)
📄 zvol_impl.h(3.7 KB)

Editing: btree.h

/*
 * CDDL HEADER START
 *
 * This file and its contents are supplied under the terms of the
 * Common Development and Distribution License ("CDDL"), version 1.0.
 * You may only use this file in accordance with the terms of version
 * 1.0 of the CDDL.
 *
 * A full copy of the text of the CDDL should have accompanied this
 * source.  A copy of the CDDL is also available via the Internet at
 * http://www.illumos.org/license/CDDL.
 *
 * CDDL HEADER END
 */
/*
 * Copyright (c) 2019 by Delphix. All rights reserved.
 */

#ifndef	_BTREE_H
#define	_BTREE_H

#ifdef	__cplusplus
extern "C" {
#endif

#include	<sys/zfs_context.h>

/*
 * This file defines the interface for a B-Tree implementation for ZFS. The
 * tree can be used to store arbitrary sortable data types with low overhead
 * and good operation performance. In addition the tree intelligently
 * optimizes bulk in-order insertions to improve memory use and performance.
 *
 * Note that for all B-Tree functions, the values returned are pointers to the
 * internal copies of the data in the tree. The internal data can only be
 * safely mutated if the changes cannot change the ordering of the element
 * with respect to any other elements in the tree.
 *
 * The major drawback of the B-Tree is that any returned elements or indexes
 * are only valid until a side-effectful operation occurs, since these can
 * result in reallocation or relocation of data. Side effectful operations are
 * defined as insertion, removal, and zfs_btree_destroy_nodes.
 *
 * The B-Tree has two types of nodes: core nodes, and leaf nodes. Core
 * nodes have an array of children pointing to other nodes, and an array of
 * elements that act as separators between the elements of the subtrees rooted
 * at its children. Leaf nodes only contain data elements, and form the bottom
 * layer of the tree. Unlike B+ Trees, in this B-Tree implementation the
 * elements in the core nodes are not copies of or references to leaf node
 * elements.  Each element occurs only once in the tree, no matter what kind
 * of node it is in.
 *
 * The tree's height is the same throughout, unlike many other forms of search
 * tree. Each node (except for the root) must be between half minus one and
 * completely full of elements (and children) at all times. Any operation that
 * would put the node outside of that range results in a rebalancing operation
 * (taking, merging, or splitting).
 *
 * This tree was implemented using descriptions from Wikipedia's articles on
 * B-Trees and B+ Trees.
 */

/*
 * Decreasing these values results in smaller memmove operations, but more of
 * them, and increased memory overhead. Increasing these values results in
 * higher variance in operation time, and reduces memory overhead.
 */
#define	BTREE_CORE_ELEMS	128
#define	BTREE_LEAF_SIZE		4096

extern kmem_cache_t *zfs_btree_leaf_cache;

typedef struct zfs_btree_hdr {
	struct zfs_btree_core	*bth_parent;
	boolean_t		bth_core;
	/*
	 * For both leaf and core nodes, represents the number of elements in
	 * the node. For core nodes, they will have bth_count + 1 children.
	 */
	uint32_t		bth_count;
} zfs_btree_hdr_t;

typedef struct zfs_btree_core {
	zfs_btree_hdr_t	btc_hdr;
	zfs_btree_hdr_t	*btc_children[BTREE_CORE_ELEMS + 1];
	uint8_t		btc_elems[];
} zfs_btree_core_t;

typedef struct zfs_btree_leaf {
	zfs_btree_hdr_t	btl_hdr;
	uint8_t		btl_elems[];
} zfs_btree_leaf_t;

typedef struct zfs_btree_index {
	zfs_btree_hdr_t	*bti_node;
	uint64_t	bti_offset;
	/*
	 * True if the location is before the list offset, false if it's at
	 * the listed offset.
	 */
	boolean_t	bti_before;
} zfs_btree_index_t;

typedef struct btree {
	zfs_btree_hdr_t		*bt_root;
	int64_t			bt_height;
	size_t			bt_elem_size;
	uint64_t		bt_num_elems;
	uint64_t		bt_num_nodes;
	zfs_btree_leaf_t	*bt_bulk; // non-null if bulk loading
	int (*bt_compar) (const void *, const void *);
} zfs_btree_t;

/*
 * Allocate and deallocate caches for btree nodes.
 */
void zfs_btree_init(void);
void zfs_btree_fini(void);

/*
 * Initialize an B-Tree. Arguments are:
 *
 * tree   - the tree to be initialized
 * compar - function to compare two nodes, it must return exactly: -1, 0, or +1
 *          -1 for <, 0 for ==, and +1 for >
 * size   - the value of sizeof(struct my_type)
 */
void zfs_btree_create(zfs_btree_t *, int (*) (const void *, const void *),
    size_t);

/*
 * Find a node with a matching value in the tree. Returns the matching node
 * found. If not found, it returns NULL and then if "where" is not NULL it sets
 * "where" for use with zfs_btree_add_idx() or zfs_btree_nearest().
 *
 * node   - node that has the value being looked for
 * where  - position for use with zfs_btree_nearest() or zfs_btree_add_idx(),
 *          may be NULL
 */
void *zfs_btree_find(zfs_btree_t *, const void *, zfs_btree_index_t *);

/*
 * Insert a node into the tree.
 *
 * node   - the node to insert
 * where  - position as returned from zfs_btree_find()
 */
void zfs_btree_add_idx(zfs_btree_t *, const void *, const zfs_btree_index_t *);

/*
 * Return the first or last valued node in the tree. Will return NULL if the
 * tree is empty. The index can be NULL if the location of the first or last
 * element isn't required.
 */
void *zfs_btree_first(zfs_btree_t *, zfs_btree_index_t *);
void *zfs_btree_last(zfs_btree_t *, zfs_btree_index_t *);

/*
 * Return the next or previous valued node in the tree. The second index can
 * safely be NULL, if the location of the next or previous value isn't
 * required.
 */
void *zfs_btree_next(zfs_btree_t *, const zfs_btree_index_t *,
    zfs_btree_index_t *);
void *zfs_btree_prev(zfs_btree_t *, const zfs_btree_index_t *,
    zfs_btree_index_t *);

/*
 * Get a value from a tree and an index.
 */
void *zfs_btree_get(zfs_btree_t *, zfs_btree_index_t *);

/*
 * Add a single value to the tree. The value must not compare equal to any
 * other node already in the tree. Note that the value will be copied out, not
 * inserted directly. It is safe to free or destroy the value once this
 * function returns.
 */
void zfs_btree_add(zfs_btree_t *, const void *);

/*
 * Remove a single value from the tree.  The value must be in the tree. The
 * pointer passed in may be a pointer into a tree-controlled buffer, but it
 * need not be.
 */
void zfs_btree_remove(zfs_btree_t *, const void *);

/*
 * Remove the value at the given location from the tree.
 */
void zfs_btree_remove_idx(zfs_btree_t *, zfs_btree_index_t *);

/*
 * Return the number of nodes in the tree
 */
ulong_t zfs_btree_numnodes(zfs_btree_t *);

/*
 * Used to destroy any remaining nodes in a tree. The cookie argument should
 * be initialized to NULL before the first call. Returns a node that has been
 * removed from the tree and may be free()'d. Returns NULL when the tree is
 * empty.
 *
 * Once you call zfs_btree_destroy_nodes(), you can only continuing calling it
 * and finally zfs_btree_destroy(). No other B-Tree routines will be valid.
 *
 * cookie - an index used to save state between calls to
 * zfs_btree_destroy_nodes()
 *
 * EXAMPLE:
 *	zfs_btree_t *tree;
 *	struct my_data *node;
 *	zfs_btree_index_t *cookie;
 *
 *	cookie = NULL;
 *	while ((node = zfs_btree_destroy_nodes(tree, &cookie)) != NULL)
 *		data_destroy(node);
 *	zfs_btree_destroy(tree);
 */
void *zfs_btree_destroy_nodes(zfs_btree_t *, zfs_btree_index_t **);

/*
 * Destroys all nodes in the tree quickly. This doesn't give the caller an
 * opportunity to iterate over each node and do its own cleanup; for that, use
 * zfs_btree_destroy_nodes().
 */
void zfs_btree_clear(zfs_btree_t *);

/*
 * Final destroy of an B-Tree. Arguments are:
 *
 * tree   - the empty tree to destroy
 */
void zfs_btree_destroy(zfs_btree_t *tree);

/* Runs a variety of self-checks on the btree to verify integrity. */
void zfs_btree_verify(zfs_btree_t *tree);

#ifdef	__cplusplus
}
#endif

#endif	/* _BTREE_H */

003 File Manager

Editing: btree.h

Upload File

Create Folder