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         struct cache_extent *entry;
 100
 101         found = tree_insert(&tree->root, pe->start, pe->size, &pe->rb_node);
 102         if (found) {
 103                 entry = rb_entry(found, struct cache_extent, rb_node);
 104                 return -EEXIST;
 105         }
 106         return 0;
 107 }
 108
 109 int insert_cache_extent(struct cache_tree *tree, u64 start, u64 size)
 110 {
 111         struct cache_extent *pe = alloc_cache_extent(start, size);
 112         int ret;
 113         ret = insert_existing_cache_extent(tree, pe);
 114         if (ret)
 115                 free(pe);
 116         return ret;
 117 }
 118
 119 struct cache_extent *find_cache_extent(struct cache_tree *tree,
 120                                            u64 start, u64 size)
 121 {
 122         struct rb_node *prev;
 123         struct rb_node *ret;
 124         struct cache_extent *entry;
 125         ret = __tree_search(&tree->root, start, size, &prev);
 126         if (!ret)
 127                 return NULL;
 128
 129         entry = rb_entry(ret, struct cache_extent, rb_node);
 130         return entry;
 131 }
 132
 133 struct cache_extent *find_first_cache_extent(struct cache_tree *tree,
 134                                                  u64 start)
 135 {
 136         struct rb_node *prev;
 137         struct rb_node *ret;
 138         struct cache_extent *entry;
 139
 140         ret = __tree_search(&tree->root, start, 1, &prev);
 141         if (!ret)
 142                 ret = prev;
 143         if (!ret)
 144                 return NULL;
 145         entry = rb_entry(ret, struct cache_extent, rb_node);
 146         return entry;
 147 }
 148
 149 struct cache_extent *prev_cache_extent(struct cache_extent *pe)
 150 {
 151         struct rb_node *node = rb_prev(&pe->rb_node);
 152
 153         if (!node)
 154                 return NULL;
 155         return rb_entry(node, struct cache_extent, rb_node);
 156 }
 157
 158 struct cache_extent *next_cache_extent(struct cache_extent *pe)
 159 {
 160         struct rb_node *node = rb_next(&pe->rb_node);
 161
 162         if (!node)
 163                 return NULL;
 164         return rb_entry(node, struct cache_extent, rb_node);
 165 }
 166
 167 void remove_cache_extent(struct cache_tree *tree,
 168                                  struct cache_extent *pe)
 169 {
 170         rb_erase(&pe->rb_node, &tree->root);
 171 }
 172