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