drivers/md/persistent-data/dm-btree.h

Source file repositories/reference/linux-study-clean/drivers/md/persistent-data/dm-btree.h

File Facts

System
Linux kernel
Corpus path
drivers/md/persistent-data/dm-btree.h
Extension
.h
Size
6594 bytes
Lines
217
Domain
Driver Families
Bucket
drivers/md
Inferred role
Driver Families: implementation source
Status
source implementation candidate

Why This File Exists

Repeatable hardware-adapter layer. Deep compatibility for every driver is out of scope; this atlas records patterns, probe lifecycles, bus glue, IRQ/DMA usage, and links back to core abstractions.

Dependency Surface

Detected Declarations

Annotated Snippet

struct dm_btree_value_type {
	void *context;

	/*
	 * The size in bytes of each value.
	 */
	uint32_t size;

	/*
	 * Any of these methods can be safely set to NULL if you do not
	 * need the corresponding feature.
	 */

	/*
	 * The btree is making a duplicate of a run of values, for instance
	 * because previously-shared btree nodes have now diverged.
	 * @value argument is the new copy that the copy function may modify.
	 * (Probably it just wants to increment a reference count
	 * somewhere.) This method is _not_ called for insertion of a new
	 * value: It is assumed the ref count is already 1.
	 */
	void (*inc)(void *context, const void *value, unsigned int count);

	/*
	 * These values are being deleted.  The btree takes care of freeing
	 * the memory pointed to by @value.  Often the del function just
	 * needs to decrement a reference counts somewhere.
	 */
	void (*dec)(void *context, const void *value, unsigned int count);

	/*
	 * A test for equality between two values.  When a value is
	 * overwritten with a new one, the old one has the dec method
	 * called _unless_ the new and old value are deemed equal.
	 */
	int (*equal)(void *context, const void *value1, const void *value2);
};

/*
 * The shape and contents of a btree.
 */
struct dm_btree_info {
	struct dm_transaction_manager *tm;

	/*
	 * Number of nested btrees. (Not the depth of a single tree.)
	 */
	unsigned int levels;
	struct dm_btree_value_type value_type;
};

/*
 * Set up an empty tree.  O(1).
 */
int dm_btree_empty(struct dm_btree_info *info, dm_block_t *root);

/*
 * Delete a tree.  O(n) - this is the slow one!  It can also block, so
 * please don't call it on an IO path.
 */
int dm_btree_del(struct dm_btree_info *info, dm_block_t root);

/*
 * All the lookup functions return -ENODATA if the key cannot be found.
 */

/*
 * Tries to find a key that matches exactly.  O(ln(n))
 */
int dm_btree_lookup(struct dm_btree_info *info, dm_block_t root,
		    uint64_t *keys, void *value_le);

/*
 * Tries to find the first key where the bottom level key is >= to that
 * given.  Useful for skipping empty sections of the btree.
 */
int dm_btree_lookup_next(struct dm_btree_info *info, dm_block_t root,
			 uint64_t *keys, uint64_t *rkey, void *value_le);

/*
 * Insertion (or overwrite an existing value).  O(ln(n))
 */
int dm_btree_insert(struct dm_btree_info *info, dm_block_t root,
		    uint64_t *keys, void *value, dm_block_t *new_root)
	__dm_written_to_disk(value);

/*
 * A variant of insert that indicates whether it actually inserted or just
 * overwrote.  Useful if you're keeping track of the number of entries in a
 * tree.

Annotation

Implementation Notes