Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
addressable_queues.hpp
Go to the documentation of this file.
1 /***************************************************************************
2  * foxxll/common/addressable_queues.hpp
3  *
4  * Part of FOXXLL. See http://foxxll.org
5  *
6  * Copyright (C) 2010-2011 Raoul Steffen <[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 FOXXLL_COMMON_ADDRESSABLE_QUEUES_HEADER
14 #define FOXXLL_COMMON_ADDRESSABLE_QUEUES_HEADER
15 
16 #include <cassert>
17 #include <functional>
18 #include <list>
19 #include <map>
20 #include <set>
21 #include <utility>
22 
23 namespace foxxll {
24 
25 //! An internal fifo queue that allows removing elements addressed with (a copy
26 //! of) themselves.
27 //! \tparam KeyType Type of contained elements.
28 template <typename KeyType>
30 {
31  using container_type = std::list<KeyType>;
32  using container_iterator = typename container_type::iterator;
33  using meta_type = std::map<KeyType, container_iterator>;
34  using meta_iterator = typename meta_type::iterator;
35 
38 
39 public:
40  //! Type of handle to an entry. For use with insert and remove.
42 
43  //! Create an empty queue.
46 
47  //! Check if queue is empty.
48  //! \return If queue is empty.
49  bool empty() const
50  { return vals.empty(); }
51 
52  //! Insert new element. If the element is already in, it is moved to the
53  //! back.
54  //! \param e Element to insert.
55  //! \return pair<handle, bool> Iterator to element; if element was newly
56  //! inserted.
57  std::pair<handle, bool> insert(const KeyType& e)
58  {
59  container_iterator ei = vals.insert(vals.end(), e);
60  std::pair<handle, bool> r = meta.insert(std::make_pair(e, ei));
61  if (! r.second)
62  {
63  // element was already in
64  vals.erase(r.first->second);
65  r.first->second = ei;
66  }
67  return r;
68  }
69 
70  //! Erase element from the queue.
71  //! \param e Element to remove.
72  //! \return If element was in.
73  bool erase(const KeyType& e)
74  {
75  handle mi = meta.find(e);
76  if (mi == meta.end())
77  return false;
78  vals.erase(mi->second);
79  meta.erase(mi);
80  return true;
81  }
82 
83  //! Erase element from the queue.
84  //! \param i Iterator to element to remove.
85  void erase(handle i)
86  {
87  vals.erase(i->second);
88  meta.erase(i);
89  }
90 
91  //! Access top element in the queue.
92  //! \return Const reference to top element.
93  const KeyType & top() const
94  { return vals.front(); }
95 
96  //! Remove top element from the queue.
97  //! \return Top element.
98  KeyType pop()
99  {
100  assert(! empty());
101  const KeyType e = top();
102  meta.erase(e);
103  vals.pop_front();
104  return e;
105  }
106 };
107 
108 //! An internal priority queue that allows removing elements addressed with (a
109 //! copy of) themselves.
110 //! \tparam KeyType Type of contained elements.
111 //! \tparam PriorityType Type of Priority.
112 template <typename KeyType, typename PriorityType, class Cmp = std::less<PriorityType> >
114 {
115  struct cmp // like < for pair, but uses Cmp for < on first
116  {
117  bool operator () (const std::pair<PriorityType, KeyType>& left,
118  const std::pair<PriorityType, KeyType>& right) const
119  {
120  Cmp c;
121  return c(left.first, right.first) ||
122  ((! c(right.first, left.first)) && left.second < right.second);
123  }
124  };
125 
126  using container_type = std::set<std::pair<PriorityType, KeyType>, cmp>;
127  using container_iterator = typename container_type::iterator;
128  using meta_type = std::map<KeyType, container_iterator>;
129  using meta_iterator = typename meta_type::iterator;
130 
133 
134 public:
135  //! Type of handle to an entry. For use with insert and remove.
137 
138  //! Create an empty queue.
141 
142  //! Check if queue is empty.
143  //! \return If queue is empty.
144  bool empty() const
145  { return vals.empty(); }
146 
147  //! Insert new element. If the element is already in, it's priority is updated.
148  //! \param e Element to insert.
149  //! \param o Priority of element.
150  //! \return pair<handle, bool> Iterator to element; if element was newly inserted.
151  std::pair<handle, bool> insert(const KeyType& e, const PriorityType o)
152  {
153  std::pair<container_iterator, bool> s = vals.insert(std::make_pair(o, e));
154  std::pair<handle, bool> r = meta.insert(std::make_pair(e, s.first));
155  if (! r.second && s.second)
156  {
157  // was already in with different priority
158  vals.erase(r.first->second);
159  r.first->second = s.first;
160  }
161  return r;
162  }
163 
164  //! Erase element from the queue.
165  //! \param e Element to remove.
166  //! \return If element was in.
167  bool erase(const KeyType& e)
168  {
169  handle mi = meta.find(e);
170  if (mi == meta.end())
171  return false;
172  vals.erase(mi->second);
173  meta.erase(mi);
174  return true;
175  }
176 
177  //! Erase element from the queue.
178  //! \param i Iterator to element to remove.
179  void erase(handle i)
180  {
181  vals.erase(i->second);
182  meta.erase(i);
183  }
184 
185  //! Access top (= min) element in the queue.
186  //! \return Const reference to top element.
187  const KeyType & top() const
188  { return vals.begin()->second; }
189 
190  //! Remove top (= min) element from the queue.
191  //! \return Top element.
192  KeyType pop()
193  {
194  assert(! empty());
195  const KeyType e = top();
196  meta.erase(e);
197  vals.erase(vals.begin());
198  return e;
199  }
200 };
201 
202 } // namespace foxxll
203 
204 #endif // !FOXXLL_COMMON_ADDRESSABLE_QUEUES_HEADER
205 
206 /**************************************************************************/
std::map< swappable_block_identifier_type, container_iterator > meta_type
std::list< swappable_block_identifier_type > container_type
std::pair< handle, bool > insert(const KeyType &e, const PriorityType o)
std::set< std::pair< foxxll::block_scheduler_algorithm_offline_lfd::priority, swappable_block_identifier_type >, cmp > container_type
bool operator()(const std::pair< PriorityType, KeyType > &left, const std::pair< PriorityType, KeyType > &right) const
addressable_fifo_queue()
Create an empty queue.
const KeyType & top() const
std::pair< handle, bool > insert(const KeyType &e)
meta_iterator handle
Type of handle to an entry. For use with insert and remove.
addressable_priority_queue()
Create an empty queue.