extent-cache.h

   1 /*
   2  * Copyright (C) 2007 Oracle.  All rights reserved.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public
   6  * License v2 as published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11  * General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public
  14  * License along with this program; if not, write to the
  15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  16  * Boston, MA 021110-1307, USA.
  17  */
  18
  19 #ifndef __BTRFS_EXTENT_CACHE_H__
  20 #define __BTRFS_EXTENT_CACHE_H__
  21
  22 #if BTRFS_FLAT_INCLUDES
  23 #include "kerncompat.h"
  24 #include "rbtree.h"
  25 #else
  26 #include <btrfs/kerncompat.h>
  27 #include <btrfs/rbtree.h>
  28 #endif /* BTRFS_FLAT_INCLUDES */
  29
  30 struct cache_tree {
  31         struct rb_root root;
  32 };
  33
  34 struct cache_extent {
  35         struct rb_node rb_node;
  36         u64 objectid;
  37         u64 start;
  38         u64 size;
  39 };
  40
  41 void cache_tree_init(struct cache_tree *tree);
  42
  43 struct cache_extent *first_cache_extent(struct cache_tree *tree);
  44 struct cache_extent *last_cache_extent(struct cache_tree *tree);
  45 struct cache_extent *prev_cache_extent(struct cache_extent *pe);
  46 struct cache_extent *next_cache_extent(struct cache_extent *pe);
  47
  48 /*
  49  * Find a cache_extent which covers start.
  50  *
  51  * If not found, return next cache_extent if possible.
  52  */
  53 struct cache_extent *search_cache_extent(struct cache_tree *tree, u64 start);
  54
  55 /*
  56  * Find a cache_extent which restrictly covers start.
  57  *
  58  * If not found, return NULL.
  59  */
  60 struct cache_extent *lookup_cache_extent(struct cache_tree *tree,
  61                                          u64 start, u64 size);
  62
  63 /*
  64  * Add an non-overlap extent into cache tree
  65  *
  66  * If [start, start+size) overlap with existing one, it will return -EEXIST.
  67  */
  68 int add_cache_extent(struct cache_tree *tree, u64 start, u64 size);
  69
  70 /*
  71  * Same with add_cache_extent, but with cache_extent strcut.
  72  */
  73 int insert_cache_extent(struct cache_tree *tree, struct cache_extent *pe);
  74 void remove_cache_extent(struct cache_tree *tree, struct cache_extent *pe);
  75
  76 static inline int cache_tree_empty(struct cache_tree *tree)
  77 {
  78         return RB_EMPTY_ROOT(&tree->root);
  79 }
  80
  81 typedef void (*free_cache_extent)(struct cache_extent *pe);
  82
  83 void cache_tree_free_extents(struct cache_tree *tree,
  84                              free_cache_extent free_func);
  85
  86 #define FREE_EXTENT_CACHE_BASED_TREE(name, free_func)           \
  87 static void free_##name##_tree(struct cache_tree *tree)         \
  88 {                                                               \
  89         cache_tree_free_extents(tree, free_func);               \
  90 }
  91
  92 void free_extent_cache_tree(struct cache_tree *tree);
  93
  94 /*
  95  * Search a cache_extent with same objectid, and covers start.
  96  *
  97  * If not found, return next if possible.
  98  */
  99 struct cache_extent *search_cache_extent2(struct cache_tree *tree,
 100                                           u64 objectid, u64 start);
 101 /*
 102  * Search a cache_extent with same objectid, and covers the range
 103  * [start, start + size)
 104  *
 105  * If not found, return next cache_extent if possible.
 106  */
 107 struct cache_extent *lookup_cache_extent2(struct cache_tree *tree,
 108                                           u64 objectid, u64 start, u64 size);
 109 int add_cache_extent2(struct cache_tree *tree,
 110                       u64 objectid, u64 start, u64 size);
 111 int insert_cache_extent2(struct cache_tree *tree, struct cache_extent *pe);
 112
 113 /*
 114  * Insert a cache_extent range [start, start + size).
 115  *
 116  * This function may merge with existing cache_extent.
 117  * NOTE: caller must ensure the inserted range won't cover with any existing
 118  * range.
 119  */
 120 int add_merge_cache_extent(struct cache_tree *tree, u64 start, u64 size);
 121 #endif