]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- |
2 | // vim: ts=8 sw=2 smarttab | |
3 | /* | |
4 | * Ceph - scalable distributed file system | |
5 | * | |
6 | * Copyright (C) 2004-2006 Sage Weil <sage@newdream.net> | |
7 | * | |
8 | * This is free software; you can redistribute it and/or | |
9 | * modify it under the terms of the GNU Lesser General Public | |
10 | * License version 2.1, as published by the Free Software | |
11 | * Foundation. See file COPYING. | |
12 | * | |
13 | */ | |
14 | ||
15 | ||
16 | #ifndef CEPH_RANGESET_H | |
17 | #define CEPH_RANGESET_H | |
18 | ||
19 | /* | |
20 | * | |
21 | * my first container with iterator! it's pretty ugly. | |
22 | * | |
23 | */ | |
24 | ||
25 | #include <map> | |
7c673cae FG |
26 | |
27 | //typedef int T; | |
28 | ||
29 | template <class T> | |
30 | struct _rangeset_base { | |
31 | map<T,T> ranges; // pair(first,last) (inclusive, e.g. [first,last]) | |
32 | ||
33 | typedef typename map<T,T>::iterator mapit; | |
34 | ||
35 | // get iterator for range including val. or ranges.end(). | |
36 | mapit get_range_for(T val) { | |
37 | mapit it = ranges.lower_bound(val); | |
38 | if (it == ranges.end()) { | |
39 | // search backwards | |
40 | typename map<T,T>::reverse_iterator it = ranges.rbegin(); | |
41 | if (it == ranges.rend()) return ranges.end(); | |
42 | if (it->first <= val && it->second >= val) | |
43 | return ranges.find(it->first); | |
44 | return ranges.end(); | |
45 | } else { | |
46 | if (it->first == val) return | |
47 | it--; | |
48 | if (it->first <= val && it->second >= val) | |
49 | return it; | |
50 | return ranges.end(); | |
51 | } | |
52 | } | |
53 | ||
54 | }; | |
55 | ||
56 | ||
57 | template <class T> | |
58 | class rangeset_iterator : | |
59 | public std::iterator<std::input_iterator_tag, T> | |
60 | { | |
61 | //typedef typename map<T,T>::iterator mapit; | |
62 | ||
63 | map<T,T> ranges; | |
64 | typename map<T,T>::iterator it; | |
65 | T current; | |
66 | ||
67 | public: | |
68 | // cons | |
69 | rangeset_iterator() {} | |
70 | ||
71 | rangeset_iterator(typename map<T,T>::iterator& it, map<T,T>& ranges) { | |
72 | this->ranges = ranges; | |
73 | this->it = it; | |
74 | if (this->it != ranges.end()) | |
75 | current = it->first; | |
76 | } | |
77 | ||
78 | bool operator==(rangeset_iterator<T> rit) { | |
79 | return (it == rit.it && rit.current == current); | |
80 | } | |
81 | bool operator!=(rangeset_iterator<T> rit) { | |
82 | return (it != rit.it) || (rit.current != current); | |
83 | } | |
84 | ||
85 | T& operator*() { | |
86 | return current; | |
87 | } | |
88 | ||
89 | rangeset_iterator<T> operator++(int) { | |
90 | if (current < it->second) | |
91 | current++; | |
92 | else { | |
93 | it++; | |
94 | if (it != ranges.end()) | |
95 | current = it->first; | |
96 | } | |
97 | ||
98 | return *this; | |
99 | } | |
100 | }; | |
101 | ||
102 | ||
103 | template <class T> | |
104 | class rangeset | |
105 | { | |
106 | typedef typename map<T,T>::iterator map_iterator; | |
107 | ||
108 | _rangeset_base<T> theset; | |
109 | inodeno_t _size; | |
110 | ||
111 | public: | |
112 | rangeset() { _size = 0; } | |
113 | typedef rangeset_iterator<T> iterator; | |
114 | ||
115 | iterator begin() { | |
116 | map_iterator it = theset.ranges.begin(); | |
117 | return iterator(it, theset.ranges); | |
118 | } | |
119 | ||
120 | iterator end() { | |
121 | map_iterator it = theset.ranges.end(); | |
122 | return iterator(it, theset.ranges); | |
123 | } | |
124 | ||
125 | map_iterator map_begin() { | |
126 | return theset.ranges.begin(); | |
127 | } | |
128 | map_iterator map_end() { | |
129 | return theset.ranges.end(); | |
130 | } | |
131 | int map_size() { | |
132 | return theset.ranges.size(); | |
133 | } | |
134 | ||
135 | void map_insert(T v1, T v2) { | |
136 | theset.ranges.insert(pair<T,T>(v1,v2)); | |
137 | _size += v2 - v1+1; | |
138 | } | |
139 | ||
140 | ||
141 | // ... | |
142 | bool contains(T val) { | |
143 | if (theset.get_range_for(val) == theset.ranges.end()) return false; | |
11fdf7f2 | 144 | ceph_assert(!empty()); |
7c673cae FG |
145 | return true; |
146 | } | |
147 | ||
148 | void insert(T val) { | |
11fdf7f2 | 149 | ceph_assert(!contains(val)); |
7c673cae FG |
150 | |
151 | map_iterator left = theset.get_range_for(val-1); | |
152 | map_iterator right = theset.get_range_for(val+1); | |
153 | ||
154 | if (left != theset.ranges.end() && | |
155 | right != theset.ranges.end()) { | |
156 | // join! | |
157 | left->second = right->second; | |
158 | theset.ranges.erase(right); | |
159 | _size++; | |
160 | return; | |
161 | } | |
162 | ||
163 | if (left != theset.ranges.end()) { | |
164 | // add to left range | |
165 | left->second = val; | |
166 | _size++; | |
167 | return; | |
168 | } | |
169 | ||
170 | if (right != theset.ranges.end()) { | |
171 | // add to right range | |
172 | theset.ranges.insert(pair<T,T>(val, right->second)); | |
173 | theset.ranges.erase(val+1); | |
174 | _size++; | |
175 | return; | |
176 | } | |
177 | ||
178 | // new range | |
179 | theset.ranges.insert(pair<T,T>(val,val)); | |
180 | _size++; | |
181 | return; | |
182 | } | |
183 | ||
184 | unsigned size() { | |
185 | return size(); | |
186 | } | |
187 | ||
188 | bool empty() { | |
189 | if (theset.ranges.empty()) { | |
11fdf7f2 | 190 | ceph_assert(_size == 0); |
7c673cae FG |
191 | return true; |
192 | } | |
11fdf7f2 | 193 | ceph_assert(_size>0); |
7c673cae FG |
194 | return false; |
195 | } | |
196 | ||
197 | ||
198 | T first() { | |
11fdf7f2 | 199 | ceph_assert(!empty()); |
7c673cae FG |
200 | map_iterator it = theset.ranges.begin(); |
201 | return it->first; | |
202 | } | |
203 | ||
204 | void erase(T val) { | |
11fdf7f2 | 205 | ceph_assert(contains(val)); |
7c673cae | 206 | map_iterator it = theset.get_range_for(val); |
11fdf7f2 | 207 | ceph_assert(it != theset.ranges.end()); |
7c673cae FG |
208 | |
209 | // entire range | |
210 | if (val == it->first && val == it->second) { | |
211 | theset.ranges.erase(it); | |
212 | _size--; | |
213 | return; | |
214 | } | |
215 | ||
216 | // beginning | |
217 | if (val == it->first) { | |
218 | theset.ranges.insert(pair<T,T>(val+1, it->second)); | |
219 | theset.ranges.erase(it); | |
220 | _size--; | |
221 | return; | |
222 | } | |
223 | ||
224 | // end | |
225 | if (val == it->second) { | |
226 | it->second = val-1; | |
227 | _size--; | |
228 | return; | |
229 | } | |
230 | ||
231 | // middle split | |
232 | theset.ranges.insert(pair<T,T>(it->first, val-1)); | |
233 | theset.ranges.insert(pair<T,T>(val+1, it->second)); | |
234 | theset.ranges.erase(it); | |
235 | _size--; | |
236 | return; | |
237 | } | |
238 | ||
239 | void dump() { | |
240 | for (typename map<T,T>::iterator it = theset.ranges.begin(); | |
241 | it != theset.ranges.end(); | |
242 | it++) { | |
243 | cout << " " << it->first << "-" << it->second << endl; | |
244 | } | |
245 | } | |
246 | ||
247 | }; | |
248 | ||
249 | ||
250 | #endif |