diff options
Diffstat (limited to 'drivers/md/persistent-data/dm-btree.h')
| -rw-r--r-- | drivers/md/persistent-data/dm-btree.h | 76 |
1 files changed, 69 insertions, 7 deletions
diff --git a/drivers/md/persistent-data/dm-btree.h b/drivers/md/persistent-data/dm-btree.h index 8672d159e0b5..1b92acd7823d 100644 --- a/drivers/md/persistent-data/dm-btree.h +++ b/drivers/md/persistent-data/dm-btree.h @@ -1,3 +1,4 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ /* * Copyright (C) 2011 Red Hat, Inc. * @@ -51,21 +52,21 @@ struct dm_btree_value_type { */ /* - * The btree is making a duplicate of the value, for instance + * 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); + void (*inc)(void *context, const void *value, unsigned int count); /* - * This value is being deleted. The btree takes care of freeing + * 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 count somewhere. + * needs to decrement a reference counts somewhere. */ - void (*dec)(void *context, const void *value); + void (*dec)(void *context, const void *value, unsigned int count); /* * A test for equality between two values. When a value is @@ -84,7 +85,7 @@ struct dm_btree_info { /* * Number of nested btrees. (Not the depth of a single tree.) */ - unsigned levels; + unsigned int levels; struct dm_btree_value_type value_type; }; @@ -110,11 +111,18 @@ 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); + __dm_written_to_disk(value); /* * A variant of insert that indicates whether it actually inserted or just @@ -135,6 +143,24 @@ int dm_btree_remove(struct dm_btree_info *info, dm_block_t root, uint64_t *keys, dm_block_t *new_root); /* + * Removes a _contiguous_ run of values starting from 'keys' and not + * reaching keys2 (where keys2 is keys with the final key replaced with + * 'end_key'). 'end_key' is the one-past-the-end value. 'keys' may be + * altered. + */ +int dm_btree_remove_leaves(struct dm_btree_info *info, dm_block_t root, + uint64_t *keys, uint64_t end_key, + dm_block_t *new_root, unsigned int *nr_removed); + +/* + * Returns < 0 on failure. Otherwise the number of key entries that have + * been filled out. Remember trees can have zero entries, and as such have + * no lowest key. + */ +int dm_btree_find_lowest_key(struct dm_btree_info *info, dm_block_t root, + uint64_t *result_keys); + +/* * Returns < 0 on failure. Otherwise the number of key entries that have * been filled out. Remember trees can have zero entries, and as such have * no highest key. @@ -151,4 +177,40 @@ int dm_btree_walk(struct dm_btree_info *info, dm_block_t root, int (*fn)(void *context, uint64_t *keys, void *leaf), void *context); + +/*----------------------------------------------------------------*/ + +/* + * Cursor API. This does not follow the rolling lock convention. Since we + * know the order that values are required we can issue prefetches to speed + * up iteration. Use on a single level btree only. + */ +#define DM_BTREE_CURSOR_MAX_DEPTH 16 + +struct cursor_node { + struct dm_block *b; + unsigned int index; +}; + +struct dm_btree_cursor { + struct dm_btree_info *info; + dm_block_t root; + + bool prefetch_leaves; + unsigned int depth; + struct cursor_node nodes[DM_BTREE_CURSOR_MAX_DEPTH]; +}; + +/* + * Creates a fresh cursor. If prefetch_leaves is set then it is assumed + * the btree contains block indexes that will be prefetched. The cursor is + * quite large, so you probably don't want to put it on the stack. + */ +int dm_btree_cursor_begin(struct dm_btree_info *info, dm_block_t root, + bool prefetch_leaves, struct dm_btree_cursor *c); +void dm_btree_cursor_end(struct dm_btree_cursor *c); +int dm_btree_cursor_next(struct dm_btree_cursor *c); +int dm_btree_cursor_skip(struct dm_btree_cursor *c, uint32_t count); +int dm_btree_cursor_get_value(struct dm_btree_cursor *c, uint64_t *key, void *value_le); + #endif /* _LINUX_DM_BTREE_H */ |