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::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