1 | #ifndef __SMAP_HH__␊ |
2 | #define __SMAP_HH__␊ |
3 | ␊ |
4 | // Copyright (C) 2005 Graydon Hoare <graydon@pobox.com>␊ |
5 | //␊ |
6 | // This program is made available under the GNU GPL version 2.0 or␊ |
7 | // greater. See the accompanying file COPYING for details.␊ |
8 | //␊ |
9 | // This program is distributed WITHOUT ANY WARRANTY; without even the␊ |
10 | // implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR␊ |
11 | // PURPOSE.␊ |
12 | ␊ |
13 | #include <functional>␊ |
14 | #include <numeric>␊ |
15 | #include "vector.hh"␊ |
16 | ␊ |
17 | ␊ |
18 | // this is a map that works by storing a sorted vector and doing binary␊ |
19 | // search. for maps that are filled once and then used many times, it is␊ |
20 | // faster than other types of maps. it's a derived version of stl_map.h from␊ |
21 | // libstdc++; I *believe* deriving from its text and upgrading to GPL is␊ |
22 | // kosher.␊ |
23 | ␊ |
24 | // this is _not_ fully compatible with a std::map; in fact, it's not even a␊ |
25 | // Unique Sorted Associative Container. this is because:␊ |
26 | // -- our 'insert' operations return void, rather than an iterator␊ |
27 | // (this could be fixed by creating a very clever sort of iterator, that␊ |
28 | // knew how to sort the map and then initialize itself when dereferenced)␊ |
29 | // -- if you 'insert' two items with the same key, then later on find() will␊ |
30 | // throw an assertion␊ |
31 | // (this could be fixed by using stable_sort instead of sort, and then␊ |
32 | // deleting duplicates instead of asserting.)␊ |
33 | // it is, however, still close enough that STL algorithms generally work.␊ |
34 | ␊ |
35 | // FIXME: it is not clear how much of a win this really is; replacing our uses␊ |
36 | // of it with hash_map's in change_set.cc caused an 8% slowdown, but that may␊ |
37 | // have to do with smap using single_client_alloc and hash_map not.␊ |
38 | // Re-evaluate when later gcc automatically uses single_client_alloc when␊ |
39 | // possible...␊ |
40 | ␊ |
41 | // We don't use quick_alloc.hh's QA() macro here, because macros don't know␊ |
42 | // about <>'s as grouping mechanisms, so it thinks the "," in the middle of␊ |
43 | // std::pair<K, D> is breaking things into two arguments.␊ |
44 | template<typename K, typename D,␊ |
45 | typename compare = std::less<K>,␊ |
46 | #if defined(__GNUC__) && __GNUC__ < 3 || (__GNUC__ == 3 && __GNUC_MINOR__ < 4)␊ |
47 | typename alloc = std::__allocator<std::pair<K, D>, std::__single_client_alloc> >␊ |
48 | #else␊ |
49 | typename alloc = std::allocator<std::pair<K, D> > >␊ |
50 | #endif␊ |
51 | class␊ |
52 | smap␊ |
53 | {␊ |
54 | public:␊ |
55 | typedef K key_type;␊ |
56 | typedef D mapped_type;␊ |
57 | typedef std::pair<key_type, mapped_type> value_type;␊ |
58 | typedef compare key_compare;␊ |
59 | ␊ |
60 | protected:␊ |
61 | class value_compare␊ |
62 | : public std::binary_function<value_type, value_type, bool>␊ |
63 | {␊ |
64 | friend class smap<K,D,compare>;␊ |
65 | protected:␊ |
66 | compare comp;␊ |
67 | value_compare(compare c) : comp(c) {}␊ |
68 | ␊ |
69 | public:␊ |
70 | bool operator()(const value_type & a,␊ |
71 | const value_type & b) const␊ |
72 | {␊ |
73 | return comp(a.first, b.first);␊ |
74 | }␊ |
75 | };␊ |
76 | ␊ |
77 | value_compare val_cmp;␊ |
78 | ␊ |
79 | typedef std::vector<value_type> vec_type;␊ |
80 | mutable vec_type vec;␊ |
81 | mutable bool damaged;␊ |
82 | ␊ |
83 | inline void␊ |
84 | ensure_sort() const␊ |
85 | {␊ |
86 | if (damaged)␊ |
87 | {␊ |
88 | std::sort(vec.begin(), vec.end(), val_cmp);␊ |
89 | // make sure we don't have any duplicate entries␊ |
90 | const_iterator leader, lagged;␊ |
91 | lagged = vec.begin();␊ |
92 | leader = vec.begin();␊ |
93 | I(leader != vec.end());␊ |
94 | ++leader;␊ |
95 | for (; leader != vec.end(); ++lagged, ++leader)␊ |
96 | I(lagged->first != leader->first);␊ |
97 | damaged = false;␊ |
98 | }␊ |
99 | }␊ |
100 | ␊ |
101 | public:␊ |
102 | ␊ |
103 | typedef alloc allocator_type;␊ |
104 | ␊ |
105 | typedef typename alloc::pointer pointer;␊ |
106 | typedef typename alloc::const_pointer const_pointer;␊ |
107 | ␊ |
108 | typedef typename alloc::reference reference;␊ |
109 | typedef typename alloc::const_reference const_reference;␊ |
110 | ␊ |
111 | typedef typename vec_type::size_type size_type;␊ |
112 | typedef typename vec_type::difference_type difference_type;␊ |
113 | ␊ |
114 | typedef typename vec_type::iterator iterator;␊ |
115 | typedef typename vec_type::const_iterator const_iterator;␊ |
116 | typedef typename vec_type::reverse_iterator reverse_iterator;␊ |
117 | typedef typename vec_type::const_reverse_iterator const_reverse_iterator;␊ |
118 | ␊ |
119 | smap()␊ |
120 | : val_cmp(compare()),␊ |
121 | damaged(false)␊ |
122 | { };␊ |
123 | ␊ |
124 | explicit␊ |
125 | smap(compare const & cmp,␊ |
126 | alloc const & a = alloc())␊ |
127 | : val_cmp(cmp),␊ |
128 | vec(a),␊ |
129 | damaged(false)␊ |
130 | { }␊ |
131 | ␊ |
132 | smap(smap const & other)␊ |
133 | : val_cmp(other.val_cmp),␊ |
134 | vec(other.vec),␊ |
135 | damaged(other.damaged)␊ |
136 | { }␊ |
137 | ␊ |
138 | template <typename InputIterator>␊ |
139 | smap(InputIterator first, InputIterator last)␊ |
140 | : damaged(false)␊ |
141 | {␊ |
142 | insert(first, last);␊ |
143 | }␊ |
144 | ␊ |
145 | template <typename InputIterator>␊ |
146 | smap(InputIterator first, InputIterator last,␊ |
147 | compare const & cmp,␊ |
148 | alloc const & a = alloc())␊ |
149 | : val_cmp(cmp),␊ |
150 | vec(a),␊ |
151 | damaged(false)␊ |
152 | {␊ |
153 | insert(first, last);␊ |
154 | }␊ |
155 | ␊ |
156 | smap &␊ |
157 | operator=(smap const & other)␊ |
158 | {␊ |
159 | val_cmp = other.val_cmp;␊ |
160 | vec = other.vec;␊ |
161 | damaged = other.damaged;␊ |
162 | return *this;␊ |
163 | }␊ |
164 | ␊ |
165 | ␊ |
166 | allocator_type get_allocator() const { return vec.get_allocator(); }␊ |
167 | ␊ |
168 | iterator begin() { return vec.begin(); }␊ |
169 | iterator end() { return vec.end(); }␊ |
170 | reverse_iterator rbegin() { return vec.rbegin(); }␊ |
171 | reverse_iterator rend() { return vec.rend(); }␊ |
172 | ␊ |
173 | const_iterator begin() const { return vec.begin(); }␊ |
174 | const_iterator end() const { return vec.end(); }␊ |
175 | const_reverse_iterator rbegin() const { return vec.rbegin(); }␊ |
176 | const_reverse_iterator rend() const { return vec.rend(); }␊ |
177 | ␊ |
178 | bool empty() const { return vec.empty(); }␊ |
179 | size_type size() const { return vec.size(); }␊ |
180 | size_type max_size() const { return vec.max_size(); }␊ |
181 | ␊ |
182 | mapped_type &␊ |
183 | operator[](const key_type & k)␊ |
184 | {␊ |
185 | iterator i = find(k);␊ |
186 | if (i != end() && i->first == k)␊ |
187 | {␊ |
188 | return i->second;␊ |
189 | }␊ |
190 | ␊ |
191 | value_type v = std::make_pair(k, mapped_type());␊ |
192 | if (size() > 0 && val_cmp(v, *(begin() + size() - 1)))␊ |
193 | {␊ |
194 | damaged = true;␊ |
195 | }␊ |
196 | vec.push_back(v);␊ |
197 | return v.second;␊ |
198 | }␊ |
199 | ␊ |
200 | void␊ |
201 | insert(value_type const & v)␊ |
202 | {␊ |
203 | I(size() == 0 || v.first != vec.back().first);␊ |
204 | if (size() > 0 && val_cmp(v, *(begin() + size() - 1)))␊ |
205 | {␊ |
206 | damaged = true;␊ |
207 | }␊ |
208 | vec.push_back(v);␊ |
209 | }␊ |
210 | ␊ |
211 | void␊ |
212 | insert(iterator pos, value_type const & v)␊ |
213 | {␊ |
214 | insert(v);␊ |
215 | }␊ |
216 | ␊ |
217 | template <typename InputIterator>␊ |
218 | void␊ |
219 | insert(InputIterator first, InputIterator last)␊ |
220 | {␊ |
221 | iterator i = begin();␊ |
222 | while (first != last)␊ |
223 | {␊ |
224 | i = insert(i, *first++);␊ |
225 | }␊ |
226 | }␊ |
227 | ␊ |
228 | void␊ |
229 | erase(iterator i)␊ |
230 | {␊ |
231 | vec.erase(i);␊ |
232 | }␊ |
233 | ␊ |
234 | size_type␊ |
235 | erase(key_type const & k)␊ |
236 | {␊ |
237 | iterator i = find(k);␊ |
238 | size_type c = 0;␊ |
239 | while (i != end() && i->first == k)␊ |
240 | {␊ |
241 | erase(i);␊ |
242 | ++c;␊ |
243 | ++i;␊ |
244 | }␊ |
245 | return c;␊ |
246 | }␊ |
247 | ␊ |
248 | void␊ |
249 | erase(iterator first, iterator last)␊ |
250 | {␊ |
251 | while (first != last)␊ |
252 | {␊ |
253 | erase(first++);␊ |
254 | }␊ |
255 | }␊ |
256 | ␊ |
257 | void␊ |
258 | swap(smap & x)␊ |
259 | {␊ |
260 | ensure_sort();␊ |
261 | x.ensure_sort();␊ |
262 | vec.swap(x.vec);␊ |
263 | }␊ |
264 | ␊ |
265 | void␊ |
266 | clear()␊ |
267 | {␊ |
268 | vec.clear();␊ |
269 | damaged = false;␊ |
270 | }␊ |
271 | ␊ |
272 | key_compare␊ |
273 | key_comp() const␊ |
274 | {␊ |
275 | return val_cmp.comp;␊ |
276 | }␊ |
277 | ␊ |
278 | value_compare␊ |
279 | value_comp() const␊ |
280 | {␊ |
281 | return val_cmp;␊ |
282 | }␊ |
283 | ␊ |
284 | iterator␊ |
285 | find(key_type const & k)␊ |
286 | {␊ |
287 | iterator i = lower_bound(k);␊ |
288 | if (i != end() && i->first == k)␊ |
289 | {␊ |
290 | return i;␊ |
291 | }␊ |
292 | return end();␊ |
293 | }␊ |
294 | ␊ |
295 | const_iterator␊ |
296 | find(key_type const & k) const␊ |
297 | {␊ |
298 | // maybe-sort + binary search␊ |
299 | const_iterator i = lower_bound(k);␊ |
300 | if (i != end() && i->first == k)␊ |
301 | {␊ |
302 | return i;␊ |
303 | }␊ |
304 | return end();␊ |
305 | }␊ |
306 | ␊ |
307 | size_type␊ |
308 | count(key_type const & k) const␊ |
309 | {␊ |
310 | return (find(k) == end() ? 0 : 1);␊ |
311 | }␊ |
312 | ␊ |
313 | iterator␊ |
314 | lower_bound(key_type const & k)␊ |
315 | {␊ |
316 | ensure_sort();␊ |
317 | value_type v(k, mapped_type());␊ |
318 | return std::lower_bound(begin(), end(), v, val_cmp);␊ |
319 | }␊ |
320 | ␊ |
321 | const_iterator␊ |
322 | lower_bound(key_type const & k) const␊ |
323 | {␊ |
324 | ensure_sort();␊ |
325 | value_type v(k, mapped_type());␊ |
326 | return std::lower_bound(begin(), end(), v, val_cmp);␊ |
327 | }␊ |
328 | ␊ |
329 | iterator␊ |
330 | upper_bound(key_type const & k)␊ |
331 | {␊ |
332 | ensure_sort();␊ |
333 | value_type v(k, mapped_type());␊ |
334 | return std::upper_bound(begin(), end(), v, val_cmp);␊ |
335 | }␊ |
336 | ␊ |
337 | const_iterator␊ |
338 | upper_bound(key_type const & k) const␊ |
339 | {␊ |
340 | ensure_sort();␊ |
341 | value_type v(k, mapped_type());␊ |
342 | return std::upper_bound(begin(), end(), v, val_cmp);␊ |
343 | }␊ |
344 | ␊ |
345 | std::pair<iterator, iterator>␊ |
346 | equal_range(key_type const & k)␊ |
347 | {␊ |
348 | ensure_sort();␊ |
349 | value_type v(k, mapped_type());␊ |
350 | return std::equal_range(begin(), end(), v, val_cmp);␊ |
351 | }␊ |
352 | ␊ |
353 | std::pair<const_iterator, const_iterator>␊ |
354 | equal_range(key_type const & k) const␊ |
355 | {␊ |
356 | ensure_sort();␊ |
357 | value_type v(k, mapped_type());␊ |
358 | return std::equal_range(begin(), end(), v, val_cmp);␊ |
359 | }␊ |
360 | ␊ |
361 | ␊ |
362 | template <typename K1, typename T1, typename C1, typename A1>␊ |
363 | friend bool␊ |
364 | operator== (const smap<K1,T1,C1,A1>&,␊ |
365 | const smap<K1,T1,C1,A1>&);␊ |
366 | ␊ |
367 | template <typename K1, typename T1, typename C1, typename A1>␊ |
368 | friend bool␊ |
369 | operator< (const smap<K1,T1,C1,A1>&,␊ |
370 | const smap<K1,T1,C1,A1>&);␊ |
371 | ␊ |
372 | };␊ |
373 | ␊ |
374 | template <typename K, typename D,␊ |
375 | typename compare,␊ |
376 | typename alloc>␊ |
377 | inline bool␊ |
378 | operator==(smap<K, D, compare, alloc> const & a,␊ |
379 | smap<K, D, compare, alloc> const & b)␊ |
380 | {␊ |
381 | a.ensure_sort();␊ |
382 | b.ensure_sort();␊ |
383 | return a.vec == b.vec;␊ |
384 | }␊ |
385 | ␊ |
386 | template <typename K, typename D,␊ |
387 | typename compare,␊ |
388 | typename alloc>␊ |
389 | inline bool␊ |
390 | operator<(smap<K, D, compare, alloc> const & a,␊ |
391 | smap<K, D, compare, alloc> const & b)␊ |
392 | {␊ |
393 | a.ensure_sort();␊ |
394 | b.ensure_sort();␊ |
395 | return a.vec < b.vec;␊ |
396 | }␊ |
397 | ␊ |
398 | template <typename K, typename D,␊ |
399 | typename compare,␊ |
400 | typename alloc>␊ |
401 | inline bool␊ |
402 | operator!=(smap<K, D, compare, alloc> const & a,␊ |
403 | smap<K, D, compare, alloc> const & b)␊ |
404 | {␊ |
405 | return !(a == b);␊ |
406 | }␊ |
407 | ␊ |
408 | template <typename K, typename D,␊ |
409 | typename compare,␊ |
410 | typename alloc>␊ |
411 | inline bool␊ |
412 | operator>(smap<K, D, compare, alloc> const & a,␊ |
413 | smap<K, D, compare, alloc> const & b)␊ |
414 | {␊ |
415 | return b < a;␊ |
416 | }␊ |
417 | ␊ |
418 | template <typename K, typename D,␊ |
419 | typename compare,␊ |
420 | typename alloc>␊ |
421 | inline bool␊ |
422 | operator<=(smap<K, D, compare, alloc> const & a,␊ |
423 | smap<K, D, compare, alloc> const & b)␊ |
424 | {␊ |
425 | return !(b < a);␊ |
426 | }␊ |
427 | ␊ |
428 | template <typename K, typename D,␊ |
429 | typename compare,␊ |
430 | typename alloc>␊ |
431 | inline bool␊ |
432 | operator>=(smap<K, D, compare, alloc> const & a,␊ |
433 | smap<K, D, compare, alloc> const & b)␊ |
434 | {␊ |
435 | return !(a < b);␊ |
436 | }␊ |
437 | ␊ |
438 | template <typename K, typename D,␊ |
439 | typename compare,␊ |
440 | typename alloc>␊ |
441 | inline void␊ |
442 | swap(smap<K, D, compare, alloc> & a,␊ |
443 | smap<K, D, compare, alloc> & b)␊ |
444 | {␊ |
445 | a.swap(b);␊ |
446 | }␊ |
447 | ␊ |
448 | ␊ |
449 | // Local Variables:␊ |
450 | // mode: C++␊ |
451 | // fill-column: 76␊ |
452 | // c-file-style: "gnu"␊ |
453 | // indent-tabs-mode: nil␊ |
454 | // End:␊ |
455 | // vim: et:sw=2:sts=2:ts=2:cino=>2s,{s,\:s,+s,t0,g0,^-2,e-2,n-2,p2s,(0,=s:␊ |
456 | ␊ |
457 | #endif // __SMAP_HH__␊ |