Stxxl: map.h Source File

00001 /***************************************************************************
00002  *  include/stxxl/bits/containers/map.h
00003  *
00004  *  Part of the STXXL. See http://stxxl.sourceforge.net
00005  *
00006  *  Copyright (C) 2006 Roman Dementiev <[email protected]>
00007  *
00008  *  Distributed under the Boost Software License, Version 1.0.
00009  *  (See accompanying file LICENSE_1_0.txt or copy at
00010  *  http://www.boost.org/LICENSE_1_0.txt)
00011  **************************************************************************/
00012 
00013 #ifndef STXXL_MAP_HEADER
00014 #define STXXL_MAP_HEADER
00015 
00016 #include <stxxl/bits/noncopyable.h>
00017 #include <stxxl/bits/containers/btree/btree.h>
00018 
00019 
00020 __STXXL_BEGIN_NAMESPACE
00021 
00022 namespace btree
00023 {
00024     template <class KeyType,
00025               class DataType,
00026               class CompareType,
00027               unsigned LogNodeSize,
00028               unsigned LogLeafSize,
00029               class PDAllocStrategy
00030               >
00031     class btree;
00032 }
00033 
00036 
00038 
00072 template <class KeyType,
00073           class DataType,
00074           class CompareType,
00075           unsigned RawNodeSize = 16 * 1024,     // 16 KBytes default
00076           unsigned RawLeafSize = 128 * 1024,    // 128 KBytes default
00077           class PDAllocStrategy = stxxl::SR
00078           >
00079 class map : private noncopyable
00080 {
00081     typedef btree::btree<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> impl_type;
00082 
00083     impl_type Impl;
00084 
00085 public:
00086     typedef typename impl_type::node_block_type node_block_type;
00087     typedef typename impl_type::leaf_block_type leaf_block_type;
00088 
00089     typedef typename impl_type::key_type key_type;
00090     typedef typename impl_type::data_type data_type;
00091     typedef typename impl_type::data_type mapped_type;
00092     typedef typename impl_type::value_type value_type;
00093     typedef typename impl_type::key_compare key_compare;
00094     typedef typename impl_type::value_compare value_compare;
00095     typedef typename impl_type::pointer pointer;
00096     typedef typename impl_type::reference reference;
00097     typedef typename impl_type::const_reference const_reference;
00098     typedef typename impl_type::size_type size_type;
00099     typedef typename impl_type::difference_type difference_type;
00100     typedef typename impl_type::iterator iterator;
00101     typedef typename impl_type::const_iterator const_iterator;
00102 
00103     iterator begin() { return Impl.begin(); }
00104     iterator end() { return Impl.end(); }
00105     const_iterator begin() const { return Impl.begin(); }
00106     const_iterator end() const { return Impl.end(); }
00107     size_type size() const { return Impl.size(); }
00108     size_type max_size() const { return Impl.max_size(); }
00109     bool empty() const { return Impl.empty(); }
00110     key_compare key_comp() const { return Impl.key_comp(); }
00111     value_compare value_comp() const { return Impl.value_comp(); }
00112 
00116     map(unsigned_type node_cache_size_in_bytes,
00117         unsigned_type leaf_cache_size_in_bytes
00118         ) : Impl(node_cache_size_in_bytes, leaf_cache_size_in_bytes)
00119     { }
00120 
00125     map(const key_compare & c_,
00126         unsigned_type node_cache_size_in_bytes,
00127         unsigned_type leaf_cache_size_in_bytes
00128         ) : Impl(c_, node_cache_size_in_bytes, leaf_cache_size_in_bytes)
00129     { }
00130 
00140     template <class InputIterator>
00141     map(InputIterator b,
00142         InputIterator e,
00143         unsigned_type node_cache_size_in_bytes,
00144         unsigned_type leaf_cache_size_in_bytes,
00145         bool range_sorted = false,
00146         double node_fill_factor = 0.75,
00147         double leaf_fill_factor = 0.6
00148         ) : Impl(b, e, node_cache_size_in_bytes, leaf_cache_size_in_bytes,
00149                  range_sorted, node_fill_factor, leaf_fill_factor)
00150     { }
00151 
00162     template <class InputIterator>
00163     map(InputIterator b,
00164         InputIterator e,
00165         const key_compare & c_,
00166         unsigned_type node_cache_size_in_bytes,
00167         unsigned_type leaf_cache_size_in_bytes,
00168         bool range_sorted = false,
00169         double node_fill_factor = 0.75,
00170         double leaf_fill_factor = 0.6
00171         ) : Impl(b, e, c_, node_cache_size_in_bytes, leaf_cache_size_in_bytes,
00172                  range_sorted, node_fill_factor, leaf_fill_factor)
00173     { }
00174 
00175     void swap(map & obj) { std::swap(Impl, obj.Impl); }
00176     std::pair<iterator, bool> insert(const value_type & x)
00177     {
00178         return Impl.insert(x);
00179     }
00180     iterator insert(iterator pos, const value_type & x)
00181     {
00182         return Impl.insert(pos, x);
00183     }
00184     template <class InputIterator>
00185     void insert(InputIterator b, InputIterator e)
00186     {
00187         Impl.insert(b, e);
00188     }
00189     void erase(iterator pos)
00190     {
00191         Impl.erase(pos);
00192     }
00193     size_type erase(const key_type & k)
00194     {
00195         return Impl.erase(k);
00196     }
00197     void erase(iterator first, iterator last)
00198     {
00199         Impl.erase(first, last);
00200     }
00201     void clear()
00202     {
00203         Impl.clear();
00204     }
00205     iterator find(const key_type & k)
00206     {
00207         return Impl.find(k);
00208     }
00209     const_iterator find(const key_type & k) const
00210     {
00211         return Impl.find(k);
00212     }
00213     size_type count(const key_type & k)
00214     {
00215         return Impl.count(k);
00216     }
00217     iterator lower_bound(const key_type & k)
00218     {
00219         return Impl.lower_bound(k);
00220     }
00221     const_iterator lower_bound(const key_type & k) const
00222     {
00223         return Impl.lower_bound(k);
00224     }
00225     iterator upper_bound(const key_type & k)
00226     {
00227         return Impl.upper_bound(k);
00228     }
00229     const_iterator upper_bound(const key_type & k) const
00230     {
00231         return Impl.upper_bound(k);
00232     }
00233     std::pair<iterator, iterator> equal_range(const key_type & k)
00234     {
00235         return Impl.equal_range(k);
00236     }
00237     std::pair<const_iterator, const_iterator> equal_range(const key_type & k) const
00238     {
00239         return Impl.equal_range(k);
00240     }
00241     data_type & operator [] (const key_type & k)
00242     {
00243         return Impl[k];
00244     }
00245 
00247     void enable_prefetching()
00248     {
00249         Impl.enable_prefetching();
00250     }
00251 
00253     void disable_prefetching()
00254     {
00255         Impl.disable_prefetching();
00256     }
00257 
00259     bool prefetching_enabled()
00260     {
00261         return Impl.prefetching_enabled();
00262     }
00263 
00265     void print_statistics(std::ostream & o) const
00266     {
00267         Impl.print_statistics(o);
00268     }
00269 
00271     void reset_statistics()
00272     {
00273         Impl.reset_statistics();
00274     }
00275 
00277     template <class KeyType_,
00278               class DataType_,
00279               class CompareType_,
00280               unsigned RawNodeSize_,
00281               unsigned RawLeafSize_,
00282               class PDAllocStrategy_>
00283     friend bool operator == (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
00284                              const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
00286     template <class KeyType_,
00287               class DataType_,
00288               class CompareType_,
00289               unsigned RawNodeSize_,
00290               unsigned RawLeafSize_,
00291               class PDAllocStrategy_>
00292     friend bool operator < (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
00293                             const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
00295     template <class KeyType_,
00296               class DataType_,
00297               class CompareType_,
00298               unsigned RawNodeSize_,
00299               unsigned RawLeafSize_,
00300               class PDAllocStrategy_>
00301     friend bool operator > (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
00302                             const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
00304     template <class KeyType_,
00305               class DataType_,
00306               class CompareType_,
00307               unsigned RawNodeSize_,
00308               unsigned RawLeafSize_,
00309               class PDAllocStrategy_>
00310     friend bool operator != (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
00311                              const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
00313     template <class KeyType_,
00314               class DataType_,
00315               class CompareType_,
00316               unsigned RawNodeSize_,
00317               unsigned RawLeafSize_,
00318               class PDAllocStrategy_>
00319     friend bool operator <= (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
00320                              const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
00322     template <class KeyType_,
00323               class DataType_,
00324               class CompareType_,
00325               unsigned RawNodeSize_,
00326               unsigned RawLeafSize_,
00327               class PDAllocStrategy_>
00328     friend bool operator >= (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
00329                              const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
00331 };
00332 
00333 template <class KeyType,
00334           class DataType,
00335           class CompareType,
00336           unsigned RawNodeSize,
00337           unsigned RawLeafSize,
00338           class PDAllocStrategy
00339           >
00340 inline bool operator == (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
00341                          const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
00342 {
00343     return a.Impl == b.Impl;
00344 }
00345 
00346 template <class KeyType,
00347           class DataType,
00348           class CompareType,
00349           unsigned RawNodeSize,
00350           unsigned RawLeafSize,
00351           class PDAllocStrategy
00352           >
00353 inline bool operator < (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
00354                         const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
00355 {
00356     return a.Impl < b.Impl;
00357 }
00358 
00359 template <class KeyType,
00360           class DataType,
00361           class CompareType,
00362           unsigned RawNodeSize,
00363           unsigned RawLeafSize,
00364           class PDAllocStrategy
00365           >
00366 inline bool operator > (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
00367                         const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
00368 {
00369     return a.Impl > b.Impl;
00370 }
00371 
00372 template <class KeyType,
00373           class DataType,
00374           class CompareType,
00375           unsigned RawNodeSize,
00376           unsigned RawLeafSize,
00377           class PDAllocStrategy
00378           >
00379 inline bool operator != (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
00380                          const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
00381 {
00382     return a.Impl != b.Impl;
00383 }
00384 
00385 template <class KeyType,
00386           class DataType,
00387           class CompareType,
00388           unsigned RawNodeSize,
00389           unsigned RawLeafSize,
00390           class PDAllocStrategy
00391           >
00392 inline bool operator <= (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
00393                          const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
00394 {
00395     return a.Impl <= b.Impl;
00396 }
00397 
00398 template <class KeyType,
00399           class DataType,
00400           class CompareType,
00401           unsigned RawNodeSize,
00402           unsigned RawLeafSize,
00403           class PDAllocStrategy
00404           >
00405 inline bool operator >= (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
00406                          const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
00407 {
00408     return a.Impl >= b.Impl;
00409 }
00410 
00412 
00413 __STXXL_END_NAMESPACE
00414 
00415 namespace std
00416 {
00417     template <class KeyType,
00418               class DataType,
00419               class CompareType,
00420               unsigned RawNodeSize,
00421               unsigned RawLeafSize,
00422               class PDAllocStrategy
00423               >
00424     void swap(stxxl::map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
00425               stxxl::map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b
00426               )
00427     {
00428         a.swap(b);
00429     }
00430 }
00431 
00432 #endif // !STXXL_MAP_HEADER