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     const_iterator cbegin() const { return begin(); }
00108     const_iterator cend() const { return end(); }
00109     size_type size() const { return Impl.size(); }
00110     size_type max_size() const { return Impl.max_size(); }
00111     bool empty() const { return Impl.empty(); }
00112     key_compare key_comp() const { return Impl.key_comp(); }
00113     value_compare value_comp() const { return Impl.value_comp(); }
00114 
00118     map(unsigned_type node_cache_size_in_bytes,
00119         unsigned_type leaf_cache_size_in_bytes
00120         ) : Impl(node_cache_size_in_bytes, leaf_cache_size_in_bytes)
00121     { }
00122 
00127     map(const key_compare & c_,
00128         unsigned_type node_cache_size_in_bytes,
00129         unsigned_type leaf_cache_size_in_bytes
00130         ) : Impl(c_, node_cache_size_in_bytes, leaf_cache_size_in_bytes)
00131     { }
00132 
00142     template <class InputIterator>
00143     map(InputIterator b,
00144         InputIterator e,
00145         unsigned_type node_cache_size_in_bytes,
00146         unsigned_type leaf_cache_size_in_bytes,
00147         bool range_sorted = false,
00148         double node_fill_factor = 0.75,
00149         double leaf_fill_factor = 0.6
00150         ) : Impl(b, e, node_cache_size_in_bytes, leaf_cache_size_in_bytes,
00151                  range_sorted, node_fill_factor, leaf_fill_factor)
00152     { }
00153 
00164     template <class InputIterator>
00165     map(InputIterator b,
00166         InputIterator e,
00167         const key_compare & c_,
00168         unsigned_type node_cache_size_in_bytes,
00169         unsigned_type leaf_cache_size_in_bytes,
00170         bool range_sorted = false,
00171         double node_fill_factor = 0.75,
00172         double leaf_fill_factor = 0.6
00173         ) : Impl(b, e, c_, node_cache_size_in_bytes, leaf_cache_size_in_bytes,
00174                  range_sorted, node_fill_factor, leaf_fill_factor)
00175     { }
00176 
00177     void swap(map & obj) { std::swap(Impl, obj.Impl); }
00178     std::pair<iterator, bool> insert(const value_type & x)
00179     {
00180         return Impl.insert(x);
00181     }
00182     iterator insert(iterator pos, const value_type & x)
00183     {
00184         return Impl.insert(pos, x);
00185     }
00186     template <class InputIterator>
00187     void insert(InputIterator b, InputIterator e)
00188     {
00189         Impl.insert(b, e);
00190     }
00191     void erase(iterator pos)
00192     {
00193         Impl.erase(pos);
00194     }
00195     size_type erase(const key_type & k)
00196     {
00197         return Impl.erase(k);
00198     }
00199     void erase(iterator first, iterator last)
00200     {
00201         Impl.erase(first, last);
00202     }
00203     void clear()
00204     {
00205         Impl.clear();
00206     }
00207     iterator find(const key_type & k)
00208     {
00209         return Impl.find(k);
00210     }
00211     const_iterator find(const key_type & k) const
00212     {
00213         return Impl.find(k);
00214     }
00215     size_type count(const key_type & k)
00216     {
00217         return Impl.count(k);
00218     }
00219     iterator lower_bound(const key_type & k)
00220     {
00221         return Impl.lower_bound(k);
00222     }
00223     const_iterator lower_bound(const key_type & k) const
00224     {
00225         return Impl.lower_bound(k);
00226     }
00227     iterator upper_bound(const key_type & k)
00228     {
00229         return Impl.upper_bound(k);
00230     }
00231     const_iterator upper_bound(const key_type & k) const
00232     {
00233         return Impl.upper_bound(k);
00234     }
00235     std::pair<iterator, iterator> equal_range(const key_type & k)
00236     {
00237         return Impl.equal_range(k);
00238     }
00239     std::pair<const_iterator, const_iterator> equal_range(const key_type & k) const
00240     {
00241         return Impl.equal_range(k);
00242     }
00243     data_type & operator [] (const key_type & k)
00244     {
00245         return Impl[k];
00246     }
00247 
00249     void enable_prefetching()
00250     {
00251         Impl.enable_prefetching();
00252     }
00253 
00255     void disable_prefetching()
00256     {
00257         Impl.disable_prefetching();
00258     }
00259 
00261     bool prefetching_enabled()
00262     {
00263         return Impl.prefetching_enabled();
00264     }
00265 
00267     void print_statistics(std::ostream & o) const
00268     {
00269         Impl.print_statistics(o);
00270     }
00271 
00273     void reset_statistics()
00274     {
00275         Impl.reset_statistics();
00276     }
00277 
00279     template <class KeyType_,
00280               class DataType_,
00281               class CompareType_,
00282               unsigned RawNodeSize_,
00283               unsigned RawLeafSize_,
00284               class PDAllocStrategy_>
00285     friend bool operator == (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
00286                              const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
00288     template <class KeyType_,
00289               class DataType_,
00290               class CompareType_,
00291               unsigned RawNodeSize_,
00292               unsigned RawLeafSize_,
00293               class PDAllocStrategy_>
00294     friend bool operator < (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
00295                             const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
00297     template <class KeyType_,
00298               class DataType_,
00299               class CompareType_,
00300               unsigned RawNodeSize_,
00301               unsigned RawLeafSize_,
00302               class PDAllocStrategy_>
00303     friend bool operator > (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
00304                             const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
00306     template <class KeyType_,
00307               class DataType_,
00308               class CompareType_,
00309               unsigned RawNodeSize_,
00310               unsigned RawLeafSize_,
00311               class PDAllocStrategy_>
00312     friend bool operator != (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
00313                              const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
00315     template <class KeyType_,
00316               class DataType_,
00317               class CompareType_,
00318               unsigned RawNodeSize_,
00319               unsigned RawLeafSize_,
00320               class PDAllocStrategy_>
00321     friend bool operator <= (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
00322                              const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
00324     template <class KeyType_,
00325               class DataType_,
00326               class CompareType_,
00327               unsigned RawNodeSize_,
00328               unsigned RawLeafSize_,
00329               class PDAllocStrategy_>
00330     friend bool operator >= (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
00331                              const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
00333 };
00334 
00335 template <class KeyType,
00336           class DataType,
00337           class CompareType,
00338           unsigned RawNodeSize,
00339           unsigned RawLeafSize,
00340           class PDAllocStrategy
00341           >
00342 inline bool operator == (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
00343                          const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
00344 {
00345     return a.Impl == b.Impl;
00346 }
00347 
00348 template <class KeyType,
00349           class DataType,
00350           class CompareType,
00351           unsigned RawNodeSize,
00352           unsigned RawLeafSize,
00353           class PDAllocStrategy
00354           >
00355 inline bool operator < (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
00356                         const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
00357 {
00358     return a.Impl < b.Impl;
00359 }
00360 
00361 template <class KeyType,
00362           class DataType,
00363           class CompareType,
00364           unsigned RawNodeSize,
00365           unsigned RawLeafSize,
00366           class PDAllocStrategy
00367           >
00368 inline bool operator > (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
00369                         const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
00370 {
00371     return a.Impl > b.Impl;
00372 }
00373 
00374 template <class KeyType,
00375           class DataType,
00376           class CompareType,
00377           unsigned RawNodeSize,
00378           unsigned RawLeafSize,
00379           class PDAllocStrategy
00380           >
00381 inline bool operator != (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
00382                          const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
00383 {
00384     return a.Impl != b.Impl;
00385 }
00386 
00387 template <class KeyType,
00388           class DataType,
00389           class CompareType,
00390           unsigned RawNodeSize,
00391           unsigned RawLeafSize,
00392           class PDAllocStrategy
00393           >
00394 inline bool operator <= (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
00395                          const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
00396 {
00397     return a.Impl <= b.Impl;
00398 }
00399 
00400 template <class KeyType,
00401           class DataType,
00402           class CompareType,
00403           unsigned RawNodeSize,
00404           unsigned RawLeafSize,
00405           class PDAllocStrategy
00406           >
00407 inline bool operator >= (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
00408                          const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
00409 {
00410     return a.Impl >= b.Impl;
00411 }
00412 
00414 
00415 __STXXL_END_NAMESPACE
00416 
00417 namespace std
00418 {
00419     template <class KeyType,
00420               class DataType,
00421               class CompareType,
00422               unsigned RawNodeSize,
00423               unsigned RawLeafSize,
00424               class PDAllocStrategy
00425               >
00426     void swap(stxxl::map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
00427               stxxl::map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b
00428               )
00429     {
00430         a.swap(b);
00431     }
00432 }
00433 
00434 #endif // !STXXL_MAP_HEADER