iterator_map.h

Go to the documentation of this file.

/***************************************************************************
 * include/stxxl/bits/containers/btree/iterator_map.h
 *
 * Part of the STXXL. See http://stxxl.sourceforge.net
 *
 * Copyright (C) 2006 Roman Dementiev <[email protected]>
 *
 * Distributed under the Boost Software License, Version 1.0.
 * (See accompanying file LICENSE_1_0.txt or copy at
 * http://www.boost.org/LICENSE_1_0.txt)
 **************************************************************************/

#ifndef STXXL_CONTAINERS_BTREE_ITERATOR_MAP_HEADER
#define STXXL_CONTAINERS_BTREE_ITERATOR_MAP_HEADER

#include <map>

#include <stxxl/bits/noncopyable.h>
#include <stxxl/bits/containers/btree/iterator.h>
#include <stxxl/bits/common/error_handling.h>


STXXL_BEGIN_NAMESPACE

namespace btree {

template <class BTreeType>
class iterator_map : private noncopyable
{
public:
 typedef BTreeType btree_type;
 typedef typename btree_type::leaf_bid_type bid_type;
 typedef btree_iterator_base<btree_type> iterator_base;

private:
 struct Key
 {
 bid_type bid;
 unsigned pos;
 Key() { }
 Key(const bid_type& b, unsigned p) : bid(b), pos(p) { }
 };

 struct bid_comp
 {
 bool operator () (const bid_type& a, const bid_type& b) const
 {
 return (a.storage < b.storage) || (a.storage == b.storage && a.offset < b.offset);
 }
 };
 struct KeyCmp
 {
 bid_comp BIDComp;
 bool operator () (const Key& a, const Key& b) const
 {
 return BIDComp(a.bid, b.bid) || (a.bid == b.bid && a.pos < b.pos);
 }
 };

 typedef std::multimap<Key, iterator_base*, KeyCmp> multimap_type;

 multimap_type It2Addr_;
 btree_type* btree_;

 typedef typename multimap_type::value_type pair_type;
 typedef typename multimap_type::iterator mmiterator_type;
 typedef typename multimap_type::const_iterator mmconst_iterator_type;


 // changes btree pointer in all contained iterators
 void change_btree_pointers(btree_type* b)
 {
 mmconst_iterator_type it = It2Addr_.begin();
 for ( ; it != It2Addr_.end(); ++it)
 {
 (it->second)->btree_ = b;
 }
 }

public:
 iterator_map(btree_type* b) : btree_(b)
 { }

 void register_iterator(iterator_base& it)
 {
 STXXL_VERBOSE2("btree::iterator_map register_iterator addr=" << &it <<
 " BID: " << it.bid << " POS: " << it.pos);
 It2Addr_.insert(pair_type(Key(it.bid, it.pos), &it));
 }
 void unregister_iterator(iterator_base& it)
 {
 STXXL_VERBOSE2("btree::iterator_map unregister_iterator addr=" << &it <<
 " BID: " << it.bid << " POS: " << it.pos);
 assert(!It2Addr_.empty());
 Key key(it.bid, it.pos);
 std::pair<mmiterator_type, mmiterator_type> range =
 It2Addr_.equal_range(key);

 assert(range.first != range.second);

 mmiterator_type i = range.first;
 for ( ; i != range.second; ++i)
 {
 assert(it.bid == (*i).first.bid);
 assert(it.pos == (*i).first.pos);

 if ((*i).second == &it)
 {
 // found it
 It2Addr_.erase(i);
 return;
 }
 }

 STXXL_THROW2(std::runtime_error, "btree::iterator_map::unregister_iterator", "Panic in btree::iterator_map, can not find and unregister iterator");
 }
 template <class OutputContainer>
 void find(const bid_type& bid,
 unsigned first_pos,
 unsigned last_pos,
 OutputContainer& out
 )
 {
 Key firstkey(bid, first_pos);
 Key lastkey(bid, last_pos);
 mmconst_iterator_type begin = It2Addr_.lower_bound(firstkey);
 mmconst_iterator_type end = It2Addr_.upper_bound(lastkey);

 mmconst_iterator_type i = begin;
 for ( ; i != end; ++i)
 {
 assert(bid == (*i).first.bid);
 out.push_back((*i).second);
 }
 }

 virtual ~iterator_map()
 {
 mmconst_iterator_type it = It2Addr_.begin();
 for ( ; it != It2Addr_.end(); ++it)
 (it->second)->make_invalid();
 }

 void swap(iterator_map& obj)
 {
 std::swap(It2Addr_, obj.It2Addr_);
 change_btree_pointers(btree_);
 obj.change_btree_pointers(obj.btree_);
 }
};

} // namespace btree

STXXL_END_NAMESPACE


namespace std {

template <class BTreeType>
void swap(stxxl::btree::iterator_map<BTreeType>& a,
 stxxl::btree::iterator_map<BTreeType>& b)
{
 a.swap(b);
}

} // namespace std

#endif // !STXXL_CONTAINERS_BTREE_ITERATOR_MAP_HEADER