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