00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
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,
00076 unsigned RawLeafSize = 128 * 1024,
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::const_pointer const_pointer;
00097 typedef typename impl_type::reference reference;
00098 typedef typename impl_type::const_reference const_reference;
00099 typedef typename impl_type::size_type size_type;
00100 typedef typename impl_type::difference_type difference_type;
00101 typedef typename impl_type::iterator iterator;
00102 typedef typename impl_type::const_iterator const_iterator;
00103 typedef std::reverse_iterator<iterator> reverse_iterator;
00104 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00105
00106 iterator begin() { return Impl.begin(); }
00107 iterator end() { return Impl.end(); }
00108 const_iterator begin() const { return Impl.begin(); }
00109 const_iterator end() const { return Impl.end(); }
00110 const_iterator cbegin() const { return begin(); }
00111 const_iterator cend() const { return end(); }
00112
00113 reverse_iterator rbegin()
00114 {
00115 return reverse_iterator(end());
00116 }
00117 const_reverse_iterator rbegin() const
00118 {
00119 return const_reverse_iterator(end());
00120 }
00121 const_reverse_iterator crbegin() const
00122 {
00123 return const_reverse_iterator(end());
00124 }
00125 reverse_iterator rend()
00126 {
00127 return reverse_iterator(begin());
00128 }
00129 const_reverse_iterator rend() const
00130 {
00131 return const_reverse_iterator(begin());
00132 }
00133 const_reverse_iterator crend() const
00134 {
00135 return const_reverse_iterator(begin());
00136 }
00137
00138 size_type size() const { return Impl.size(); }
00139 size_type max_size() const { return Impl.max_size(); }
00140 bool empty() const { return Impl.empty(); }
00141 key_compare key_comp() const { return Impl.key_comp(); }
00142 value_compare value_comp() const { return Impl.value_comp(); }
00143
00147 map(unsigned_type node_cache_size_in_bytes,
00148 unsigned_type leaf_cache_size_in_bytes
00149 ) : Impl(node_cache_size_in_bytes, leaf_cache_size_in_bytes)
00150 { }
00151
00156 map(const key_compare & c_,
00157 unsigned_type node_cache_size_in_bytes,
00158 unsigned_type leaf_cache_size_in_bytes
00159 ) : Impl(c_, node_cache_size_in_bytes, leaf_cache_size_in_bytes)
00160 { }
00161
00171 template <class InputIterator>
00172 map(InputIterator b,
00173 InputIterator e,
00174 unsigned_type node_cache_size_in_bytes,
00175 unsigned_type leaf_cache_size_in_bytes,
00176 bool range_sorted = false,
00177 double node_fill_factor = 0.75,
00178 double leaf_fill_factor = 0.6
00179 ) : Impl(b, e, node_cache_size_in_bytes, leaf_cache_size_in_bytes,
00180 range_sorted, node_fill_factor, leaf_fill_factor)
00181 { }
00182
00193 template <class InputIterator>
00194 map(InputIterator b,
00195 InputIterator e,
00196 const key_compare & c_,
00197 unsigned_type node_cache_size_in_bytes,
00198 unsigned_type leaf_cache_size_in_bytes,
00199 bool range_sorted = false,
00200 double node_fill_factor = 0.75,
00201 double leaf_fill_factor = 0.6
00202 ) : Impl(b, e, c_, node_cache_size_in_bytes, leaf_cache_size_in_bytes,
00203 range_sorted, node_fill_factor, leaf_fill_factor)
00204 { }
00205
00206 void swap(map & obj) { std::swap(Impl, obj.Impl); }
00207 std::pair<iterator, bool> insert(const value_type & x)
00208 {
00209 return Impl.insert(x);
00210 }
00211 iterator insert(iterator pos, const value_type & x)
00212 {
00213 return Impl.insert(pos, x);
00214 }
00215 template <class InputIterator>
00216 void insert(InputIterator b, InputIterator e)
00217 {
00218 Impl.insert(b, e);
00219 }
00220 void erase(iterator pos)
00221 {
00222 Impl.erase(pos);
00223 }
00224 size_type erase(const key_type & k)
00225 {
00226 return Impl.erase(k);
00227 }
00228 void erase(iterator first, iterator last)
00229 {
00230 Impl.erase(first, last);
00231 }
00232 void clear()
00233 {
00234 Impl.clear();
00235 }
00236 iterator find(const key_type & k)
00237 {
00238 return Impl.find(k);
00239 }
00240 const_iterator find(const key_type & k) const
00241 {
00242 return Impl.find(k);
00243 }
00244 size_type count(const key_type & k)
00245 {
00246 return Impl.count(k);
00247 }
00248 iterator lower_bound(const key_type & k)
00249 {
00250 return Impl.lower_bound(k);
00251 }
00252 const_iterator lower_bound(const key_type & k) const
00253 {
00254 return Impl.lower_bound(k);
00255 }
00256 iterator upper_bound(const key_type & k)
00257 {
00258 return Impl.upper_bound(k);
00259 }
00260 const_iterator upper_bound(const key_type & k) const
00261 {
00262 return Impl.upper_bound(k);
00263 }
00264 std::pair<iterator, iterator> equal_range(const key_type & k)
00265 {
00266 return Impl.equal_range(k);
00267 }
00268 std::pair<const_iterator, const_iterator> equal_range(const key_type & k) const
00269 {
00270 return Impl.equal_range(k);
00271 }
00272 data_type & operator [] (const key_type & k)
00273 {
00274 return Impl[k];
00275 }
00276
00278 void enable_prefetching()
00279 {
00280 Impl.enable_prefetching();
00281 }
00282
00284 void disable_prefetching()
00285 {
00286 Impl.disable_prefetching();
00287 }
00288
00290 bool prefetching_enabled()
00291 {
00292 return Impl.prefetching_enabled();
00293 }
00294
00296 void print_statistics(std::ostream & o) const
00297 {
00298 Impl.print_statistics(o);
00299 }
00300
00302 void reset_statistics()
00303 {
00304 Impl.reset_statistics();
00305 }
00306
00308 template <class KeyType_,
00309 class DataType_,
00310 class CompareType_,
00311 unsigned RawNodeSize_,
00312 unsigned RawLeafSize_,
00313 class PDAllocStrategy_>
00314 friend bool operator == (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
00315 const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
00317 template <class KeyType_,
00318 class DataType_,
00319 class CompareType_,
00320 unsigned RawNodeSize_,
00321 unsigned RawLeafSize_,
00322 class PDAllocStrategy_>
00323 friend bool operator < (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
00324 const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
00326 template <class KeyType_,
00327 class DataType_,
00328 class CompareType_,
00329 unsigned RawNodeSize_,
00330 unsigned RawLeafSize_,
00331 class PDAllocStrategy_>
00332 friend bool operator > (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
00333 const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
00335 template <class KeyType_,
00336 class DataType_,
00337 class CompareType_,
00338 unsigned RawNodeSize_,
00339 unsigned RawLeafSize_,
00340 class PDAllocStrategy_>
00341 friend bool operator != (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
00342 const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
00344 template <class KeyType_,
00345 class DataType_,
00346 class CompareType_,
00347 unsigned RawNodeSize_,
00348 unsigned RawLeafSize_,
00349 class PDAllocStrategy_>
00350 friend bool operator <= (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
00351 const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
00353 template <class KeyType_,
00354 class DataType_,
00355 class CompareType_,
00356 unsigned RawNodeSize_,
00357 unsigned RawLeafSize_,
00358 class PDAllocStrategy_>
00359 friend bool operator >= (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
00360 const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
00362 };
00363
00364 template <class KeyType,
00365 class DataType,
00366 class CompareType,
00367 unsigned RawNodeSize,
00368 unsigned RawLeafSize,
00369 class PDAllocStrategy
00370 >
00371 inline bool operator == (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
00372 const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
00373 {
00374 return a.Impl == b.Impl;
00375 }
00376
00377 template <class KeyType,
00378 class DataType,
00379 class CompareType,
00380 unsigned RawNodeSize,
00381 unsigned RawLeafSize,
00382 class PDAllocStrategy
00383 >
00384 inline bool operator < (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
00385 const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
00386 {
00387 return a.Impl < b.Impl;
00388 }
00389
00390 template <class KeyType,
00391 class DataType,
00392 class CompareType,
00393 unsigned RawNodeSize,
00394 unsigned RawLeafSize,
00395 class PDAllocStrategy
00396 >
00397 inline bool operator > (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
00398 const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
00399 {
00400 return a.Impl > b.Impl;
00401 }
00402
00403 template <class KeyType,
00404 class DataType,
00405 class CompareType,
00406 unsigned RawNodeSize,
00407 unsigned RawLeafSize,
00408 class PDAllocStrategy
00409 >
00410 inline bool operator != (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
00411 const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
00412 {
00413 return a.Impl != b.Impl;
00414 }
00415
00416 template <class KeyType,
00417 class DataType,
00418 class CompareType,
00419 unsigned RawNodeSize,
00420 unsigned RawLeafSize,
00421 class PDAllocStrategy
00422 >
00423 inline bool operator <= (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
00424 const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
00425 {
00426 return a.Impl <= b.Impl;
00427 }
00428
00429 template <class KeyType,
00430 class DataType,
00431 class CompareType,
00432 unsigned RawNodeSize,
00433 unsigned RawLeafSize,
00434 class PDAllocStrategy
00435 >
00436 inline bool operator >= (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
00437 const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
00438 {
00439 return a.Impl >= b.Impl;
00440 }
00441
00443
00444 __STXXL_END_NAMESPACE
00445
00446 namespace std
00447 {
00448 template <class KeyType,
00449 class DataType,
00450 class CompareType,
00451 unsigned RawNodeSize,
00452 unsigned RawLeafSize,
00453 class PDAllocStrategy
00454 >
00455 void swap(stxxl::map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
00456 stxxl::map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b
00457 )
00458 {
00459 a.swap(b);
00460 }
00461 }
00462
00463 #endif // !STXXL_MAP_HEADER
