STXXL  1.4.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
iterator_map.h
Go to the documentation of this file.
1 /***************************************************************************
2  * include/stxxl/bits/containers/btree/iterator_map.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2006 Roman Dementiev <[email protected]>
7  *
8  * Distributed under the Boost Software License, Version 1.0.
9  * (See accompanying file LICENSE_1_0.txt or copy at
10  * http://www.boost.org/LICENSE_1_0.txt)
11  **************************************************************************/
12 
13 #ifndef STXXL_CONTAINERS_BTREE_ITERATOR_MAP_HEADER
14 #define STXXL_CONTAINERS_BTREE_ITERATOR_MAP_HEADER
15 
16 #include <map>
17 
18 #include <stxxl/bits/noncopyable.h>
21 
23 
24 namespace btree {
25 
26 template <class BTreeType>
27 class iterator_map : private noncopyable
28 {
29 public:
30  typedef BTreeType btree_type;
31  typedef typename btree_type::leaf_bid_type bid_type;
33 
34 private:
35  struct Key
36  {
39  Key() { }
40  Key(const bid_type& b, unsigned_type p)
41  : bid(b), pos(p) { }
42  };
43 
44  struct bid_comp
45  {
46  bool operator () (const bid_type& a, const bid_type& b) const
47  {
48  return (a.storage < b.storage) || (a.storage == b.storage && a.offset < b.offset);
49  }
50  };
51  struct KeyCmp
52  {
54  bool operator () (const Key& a, const Key& b) const
55  {
56  return BIDComp(a.bid, b.bid) || (a.bid == b.bid && a.pos < b.pos);
57  }
58  };
59 
60  typedef std::multimap<Key, iterator_base*, KeyCmp> multimap_type;
61 
63  btree_type* m_btree;
64 
65  typedef typename multimap_type::value_type pair_type;
66  typedef typename multimap_type::iterator mmiterator_type;
67  typedef typename multimap_type::const_iterator mmconst_iterator_type;
68 
69  //! changes btree pointer in all contained iterators
70  void change_btree_pointers(btree_type* b)
71  {
72  for (mmconst_iterator_type it = m_it2addr.begin();
73  it != m_it2addr.end(); ++it)
74  {
75  (it->second)->btree = b;
76  }
77  }
78 
79 public:
80  iterator_map(btree_type* b)
81  : m_btree(b)
82  { }
83 
85  {
86  STXXL_VERBOSE2("btree::iterator_map register_iterator addr=" << &it <<
87  " BID: " << it.bid << " POS: " << it.pos);
88  m_it2addr.insert(pair_type(Key(it.bid, it.pos), &it));
89  }
91  {
92  STXXL_VERBOSE2("btree::iterator_map unregister_iterator addr=" << &it <<
93  " BID: " << it.bid << " POS: " << it.pos);
94  assert(!m_it2addr.empty());
95  Key key(it.bid, it.pos);
96  std::pair<mmiterator_type, mmiterator_type> range =
97  m_it2addr.equal_range(key);
98 
99  assert(range.first != range.second);
100 
101  mmiterator_type i = range.first;
102  for ( ; i != range.second; ++i)
103  {
104  assert(it.bid == i->first.bid);
105  assert(it.pos == i->first.pos);
106 
107  if (i->second == &it)
108  {
109  // found it
110  m_it2addr.erase(i);
111  return;
112  }
113  }
114 
115  STXXL_THROW2(std::runtime_error, "btree::iterator_map::unregister_iterator", "Panic in btree::iterator_map, can not find and unregister iterator");
116  }
117  template <class OutputContainer>
118  void find(const bid_type& bid,
119  unsigned_type first_pos,
120  unsigned_type last_pos,
121  OutputContainer& out)
122  {
123  Key firstkey(bid, first_pos);
124  Key lastkey(bid, last_pos);
125  mmconst_iterator_type begin = m_it2addr.lower_bound(firstkey);
126  mmconst_iterator_type end = m_it2addr.upper_bound(lastkey);
127 
128  for (mmconst_iterator_type i = begin;
129  i != end; ++i)
130  {
131  assert(bid == i->first.bid);
132  out.push_back(i->second);
133  }
134  }
135 
136  virtual ~iterator_map()
137  {
138  for (mmconst_iterator_type it = m_it2addr.begin();
139  it != m_it2addr.end(); ++it)
140  {
141  it->second->make_invalid();
142  }
143  }
144 
145  void swap(iterator_map& obj)
146  {
147  std::swap(m_it2addr, obj.m_it2addr);
148  change_btree_pointers(m_btree);
149  obj.change_btree_pointers(obj.m_btree);
150  }
151 };
152 
153 } // namespace btree
154 
156 
157 namespace std {
158 
159 template <class BTreeType>
162 {
163  a.swap(b);
164 }
165 
166 } // namespace std
167 
168 #endif // !STXXL_CONTAINERS_BTREE_ITERATOR_MAP_HEADER
multimap_type::value_type pair_type
Definition: iterator_map.h:65
#define STXXL_VERBOSE2(x)
Definition: verbose.h:107
multimap_type::const_iterator mmconst_iterator_type
Definition: iterator_map.h:67
void swap(iterator_map &obj)
Definition: iterator_map.h:145
multimap_type::iterator mmiterator_type
Definition: iterator_map.h:66
iterator_map(btree_type *b)
Definition: iterator_map.h:80
void unregister_iterator(iterator_base &it)
Definition: iterator_map.h:90
#define STXXL_BEGIN_NAMESPACE
Definition: namespace.h:16
void find(const bid_type &bid, unsigned_type first_pos, unsigned_type last_pos, OutputContainer &out)
Definition: iterator_map.h:118
std::multimap< Key, iterator_base *, KeyCmp > multimap_type
Definition: iterator_map.h:60
#define STXXL_THROW2(exception_type, location, error_message)
Throws exception_type with &quot;Error in [location] : [error_message]&quot;.
btree_iterator_base< btree_type > iterator_base
Definition: iterator_map.h:32
btree_type::leaf_bid_type bid_type
Definition: iterator_map.h:31
choose_int_types< my_pointer_size >::unsigned_type unsigned_type
Definition: types.h:64
Key(const bid_type &b, unsigned_type p)
Definition: iterator_map.h:40
void change_btree_pointers(btree_type *b)
changes btree pointer in all contained iterators
Definition: iterator_map.h:70
void register_iterator(iterator_base &it)
Definition: iterator_map.h:84
#define STXXL_END_NAMESPACE
Definition: namespace.h:17