extent-cache.h 2.8 KB

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