extent-cache.c

   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 #include <stdio.h>
  19 #include <stdlib.h>
  20 #include "kerncompat.h"
  21 #include "extent-cache.h"
  22
  23 void cache_tree_init(struct cache_tree *tree)
  24 {
  25         tree->root.rb_node = NULL;
  26 }
  27
  28 static struct rb_node *tree_insert(struct rb_root *root, u64 offset,
  29                                    u64 size, struct rb_node *node)
  30 {
  31         struct rb_node ** p = &root->rb_node;
  32         struct rb_node * parent = NULL;
  33         struct cache_extent *entry;
  34
  35         while(*p) {
  36                 parent = *p;
  37                 entry = rb_entry(parent, struct cache_extent, rb_node);
  38
  39                 if (offset + size <= entry->start)
  40                         p = &(*p)->rb_left;
  41                 else if (offset >= entry->start + entry->size)
  42                         p = &(*p)->rb_right;
  43                 else
  44                         return parent;
  45         }
  46
  47         entry = rb_entry(parent, struct cache_extent, rb_node);
  48         rb_link_node(node, parent, p);
  49         rb_insert_color(node, root);
  50         return NULL;
  51 }
  52
  53 static struct rb_node *__tree_search(struct rb_root *root, u64 offset,
  54                                      u64 size, struct rb_node **prev_ret)
  55 {
  56         struct rb_node * n = root->rb_node;
  57         struct rb_node *prev = NULL;
  58         struct cache_extent *entry;
  59         struct cache_extent *prev_entry = NULL;
  60
  61         while(n) {
  62                 entry = rb_entry(n, struct cache_extent, rb_node);
  63                 prev = n;
  64                 prev_entry = entry;
  65
  66                 if (offset + size <= entry->start)
  67                         n = n->rb_left;
  68                 else if (offset >= entry->start + entry->size)
  69                         n = n->rb_right;
  70                 else
  71                         return n;
  72         }
  73         if (!prev_ret)
  74                 return NULL;
  75
  76         while(prev && offset >= prev_entry->start + prev_entry->size) {
  77                 prev = rb_next(prev);
  78                 prev_entry = rb_entry(prev, struct cache_extent, rb_node);
  79         }
  80         *prev_ret = prev;
  81         return NULL;
  82 }
  83
  84 struct cache_extent *alloc_cache_extent(u64 start, u64 size)
  85 {
  86         struct cache_extent *pe = malloc(sizeof(*pe));
  87
  88         if (!pe)
  89                 return pe;
  90         pe->start = start;
  91         pe->size = size;
  92         return pe;
  93 }
  94
  95 int insert_existing_cache_extent(struct cache_tree *tree,
  96                                  struct cache_extent *pe)
  97 {
  98         struct rb_node *found;
  99
 100         found = tree_insert(&tree->root, pe->start, pe->size, &pe->rb_node);
 101         if (found)
 102                 return -EEXIST;
 103
 104         return 0;
 105 }
 106
 107 int insert_cache_extent(struct cache_tree *tree, u64 start, u64 size)
 108 {
 109         struct cache_extent *pe = alloc_cache_extent(start, size);
 110         int ret;
 111         ret = insert_existing_cache_extent(tree, pe);
 112         if (ret)
 113                 free(pe);
 114         return ret;
 115 }
 116
 117 struct cache_extent *find_cache_extent(struct cache_tree *tree,
 118                                            u64 start, u64 size)
 119 {
 120         struct rb_node *prev;
 121         struct rb_node *ret;
 122         struct cache_extent *entry;
 123         ret = __tree_search(&tree->root, start, size, &prev);
 124         if (!ret)
 125                 return NULL;
 126
 127         entry = rb_entry(ret, struct cache_extent, rb_node);
 128         return entry;
 129 }
 130
 131 struct cache_extent *find_first_cache_extent(struct cache_tree *tree,
 132                                                  u64 start)
 133 {
 134         struct rb_node *prev;
 135         struct rb_node *ret;
 136         struct cache_extent *entry;
 137
 138         ret = __tree_search(&tree->root, start, 1, &prev);
 139         if (!ret)
 140                 ret = prev;
 141         if (!ret)
 142                 return NULL;
 143         entry = rb_entry(ret, struct cache_extent, rb_node);
 144         return entry;
 145 }
 146
 147 struct cache_extent *prev_cache_extent(struct cache_extent *pe)
 148 {
 149         struct rb_node *node = rb_prev(&pe->rb_node);
 150
 151         if (!node)
 152                 return NULL;
 153         return rb_entry(node, struct cache_extent, rb_node);
 154 }
 155
 156 struct cache_extent *next_cache_extent(struct cache_extent *pe)
 157 {
 158         struct rb_node *node = rb_next(&pe->rb_node);
 159
 160         if (!node)
 161                 return NULL;
 162         return rb_entry(node, struct cache_extent, rb_node);
 163 }
 164
 165 void remove_cache_extent(struct cache_tree *tree,
 166                                  struct cache_extent *pe)
 167 {
 168         rb_erase(&pe->rb_node, &tree->root);
 169 }
 170