b871e18f18c789fd84f1fa37b92266584e926a4e
[platform/upstream/btrfs-progs.git] / 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