| 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__␊ |
