LXR uboot/fs/btrfs/extent-cache.h

   1// SPDX-License-Identifier: GPL-2.0+
   2
   3/*
   4 * Crossported from the same named file of btrfs-progs.
   5 *
   6 * Minor modification to include headers.
   7 */
   8#ifndef __BTRFS_EXTENT_CACHE_H__
   9#define __BTRFS_EXTENT_CACHE_H__
  10
  11#include <linux/rbtree.h>
  12#include <linux/types.h>
  13
  14struct cache_tree {
  15        struct rb_root root;
  16};
  17
  18struct cache_extent {
  19        struct rb_node rb_node;
  20        u64 objectid;
  21        u64 start;
  22        u64 size;
  23};
  24
  25void cache_tree_init(struct cache_tree *tree);
  26
  27struct cache_extent *first_cache_extent(struct cache_tree *tree);
  28struct cache_extent *last_cache_extent(struct cache_tree *tree);
  29struct cache_extent *prev_cache_extent(struct cache_extent *pe);
  30struct cache_extent *next_cache_extent(struct cache_extent *pe);
  31
  32/*
  33 * Find a cache_extent which covers start.
  34 *
  35 * If not found, return next cache_extent if possible.
  36 */
  37struct cache_extent *search_cache_extent(struct cache_tree *tree, u64 start);
  38
  39/*
  40 * Find a cache_extent which restrictly covers start.
  41 *
  42 * If not found, return NULL.
  43 */
  44struct cache_extent *lookup_cache_extent(struct cache_tree *tree,
  45                                         u64 start, u64 size);
  46
  47/*
  48 * Add an non-overlap extent into cache tree
  49 *
  50 * If [start, start+size) overlap with existing one, it will return -EEXIST.
  51 */
  52int add_cache_extent(struct cache_tree *tree, u64 start, u64 size);
  53
  54/*
  55 * Same with add_cache_extent, but with cache_extent strcut.
  56 */
  57int insert_cache_extent(struct cache_tree *tree, struct cache_extent *pe);
  58void remove_cache_extent(struct cache_tree *tree, struct cache_extent *pe);
  59
  60static inline int cache_tree_empty(struct cache_tree *tree)
  61{
  62        return RB_EMPTY_ROOT(&tree->root);
  63}
  64
  65typedef void (*free_cache_extent)(struct cache_extent *pe);
  66
  67void cache_tree_free_extents(struct cache_tree *tree,
  68                             free_cache_extent free_func);
  69
  70#define FREE_EXTENT_CACHE_BASED_TREE(name, free_func)           \
  71static void free_##name##_tree(struct cache_tree *tree)         \
  72{                                                               \
  73        cache_tree_free_extents(tree, free_func);               \
  74}
  75
  76void free_extent_cache_tree(struct cache_tree *tree);
  77
  78/*
  79 * Search a cache_extent with same objectid, and covers start.
  80 *
  81 * If not found, return next if possible.
  82 */
  83struct cache_extent *search_cache_extent2(struct cache_tree *tree,
  84                                          u64 objectid, u64 start);
  85/*
  86 * Search a cache_extent with same objectid, and covers the range
  87 * [start, start + size)
  88 *
  89 * If not found, return next cache_extent if possible.
  90 */
  91struct cache_extent *lookup_cache_extent2(struct cache_tree *tree,
  92                                          u64 objectid, u64 start, u64 size);
  93int insert_cache_extent2(struct cache_tree *tree, struct cache_extent *pe);
  94
  95/*
  96 * Insert a cache_extent range [start, start + size).
  97 *
  98 * This function may merge with existing cache_extent.
  99 * NOTE: caller must ensure the inserted range won't cover with any existing
 100 * range.
 101 */
 102int add_merge_cache_extent(struct cache_tree *tree, u64 start, u64 size);
 103
 104#endif
 105