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 struct cache_extent_search_range {
  24         u64 start;
  25         u64 size;
  26 };
  27
  28 void cache_tree_init(struct cache_tree *tree)
  29 {
  30         tree->root = RB_ROOT;
  31 }
  32
  33 static int cache_tree_comp_range(struct rb_node *node, void *data)
  34 {
  35         struct cache_extent *entry;
  36         struct cache_extent_search_range *range;
  37
  38         range = (struct cache_extent_search_range *)data;
  39         entry = rb_entry(node, struct cache_extent, rb_node);
  40
  41         if (entry->start + entry->size <= range->start)
  42                 return 1;
  43         else if (range->start + range->size <= entry->start)
  44                 return -1;
  45         else
  46                 return 0;
  47 }
  48
  49 static int cache_tree_comp_nodes(struct rb_node *node1, struct rb_node *node2)
  50 {
  51         struct cache_extent *entry;
  52         struct cache_extent_search_range range;
  53
  54         entry = rb_entry(node2, struct cache_extent, rb_node);
  55         range.start = entry->start;
  56         range.size = entry->size;
  57
  58         return cache_tree_comp_range(node1, (void *)&range);
  59 }
  60
  61 struct cache_extent *alloc_cache_extent(u64 start, u64 size)
  62 {
  63         struct cache_extent *pe = malloc(sizeof(*pe));
  64
  65         if (!pe)
  66                 return pe;
  67
  68         pe->start = start;
  69         pe->size = size;
  70         return pe;
  71 }
  72
  73 int insert_cache_extent(struct cache_tree *tree, struct cache_extent *pe)
  74 {
  75         return rb_insert(&tree->root, &pe->rb_node, cache_tree_comp_nodes);
  76 }
  77
  78 int add_cache_extent(struct cache_tree *tree, u64 start, u64 size)
  79 {
  80         struct cache_extent *pe = alloc_cache_extent(start, size);
  81         int ret;
  82
  83         if (!pe) {
  84                 fprintf(stderr, "memory allocation failed\n");
  85                 exit(1);
  86         }
  87
  88         ret = insert_cache_extent(tree, pe);
  89         if (ret)
  90                 free(pe);
  91
  92         return ret;
  93 }
  94
  95 struct cache_extent *find_cache_extent(struct cache_tree *tree,
  96                                        u64 start, u64 size)
  97 {
  98         struct rb_node *node;
  99         struct cache_extent *entry;
 100         struct cache_extent_search_range range;
 101
 102         range.start = start;
 103         range.size = size;
 104         node = rb_search(&tree->root, &range, cache_tree_comp_range, NULL);
 105         if (!node)
 106                 return NULL;
 107
 108         entry = rb_entry(node, struct cache_extent, rb_node);
 109         return entry;
 110 }
 111
 112 struct cache_extent *find_first_cache_extent(struct cache_tree *tree, u64 start)
 113 {
 114         struct rb_node *next;
 115         struct rb_node *node;
 116         struct cache_extent *entry;
 117         struct cache_extent_search_range range;
 118
 119         range.start = start;
 120         range.size = 1;
 121         node = rb_search(&tree->root, &range, cache_tree_comp_range, &next);
 122         if (!node)
 123                 node = next;
 124         if (!node)
 125                 return NULL;
 126
 127         entry = rb_entry(node, struct cache_extent, rb_node);
 128         return entry;
 129 }
 130
 131 struct cache_extent *first_cache_extent(struct cache_tree *tree)
 132 {
 133         struct rb_node *node = rb_first(&tree->root);
 134
 135         if (!node)
 136                 return NULL;
 137         return rb_entry(node, struct cache_extent, rb_node);
 138 }
 139
 140 struct cache_extent *prev_cache_extent(struct cache_extent *pe)
 141 {
 142         struct rb_node *node = rb_prev(&pe->rb_node);
 143
 144         if (!node)
 145                 return NULL;
 146         return rb_entry(node, struct cache_extent, rb_node);
 147 }
 148
 149 struct cache_extent *next_cache_extent(struct cache_extent *pe)
 150 {
 151         struct rb_node *node = rb_next(&pe->rb_node);
 152
 153         if (!node)
 154                 return NULL;
 155         return rb_entry(node, struct cache_extent, rb_node);
 156 }
 157
 158 void remove_cache_extent(struct cache_tree *tree, struct cache_extent *pe)
 159 {
 160         rb_erase(&pe->rb_node, &tree->root);
 161 }
 162
 163 void cache_tree_free_extents(struct cache_tree *tree,
 164                              free_cache_extent free_func)
 165 {
 166         struct cache_extent *ce;
 167
 168         while ((ce = first_cache_extent(tree))) {
 169                 remove_cache_extent(tree, ce);
 170                 free_func(ce);
 171         }
 172 }